Untitled

#ifndef _WINDOW_BIT_COUNT_APX_
#define _WINDOW_BIT_COUNT_APX_
#define max(a, b) (((a) > (b)) ? (a) : (b))
#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t N_MERGES = 0; // keep track of how many bucket merges occur

/*
    TODO: You can add code here.
*/
typedef struct Bucket {
  uint32_t count; // Count of 1's in the bucket
  uint32_t ts;    // ts or index of the most recent bit in the bucket
} Bucket;

typedef struct {
  // TODO: Fill me.
  Bucket *buckets;      // Array of buckets
  uint32_t maxBuckets;  // Maximum number of buckets
  uint32_t bucketCount; // Current number of buckets
  uint32_t wndSize;     // Size of the window
  uint32_t *bitBuffer;  // Circular buffer for bits
  uint32_t bufferIndex; // Current index in the circular bit buffer
  uint32_t k;           // 1/eps, controls precision
  uint32_t totalBitsProcessed;
} StateApx;

// k = 1/eps
// if eps = 0.01 (relative error 1%) then k = 100
// if eps = 0.001 (relative error 0.1%) the k = 1000
uint64_t wnd_bit_count_apx_new(StateApx *self, uint32_t wnd_size, uint32_t k) {
  assert(wnd_size >= 1);
  assert(k >= 1);

  // TODO: Fill me.
  self->maxBuckets = 2 * (uint32_t)log2(wnd_size);
  // TODO:
  // The function should return the total number of bytes allocated on the heap.
  size_t bucketsSize = sizeof(Bucket) * self->maxBuckets;
  size_t bufferSize = sizeof(uint32_t) * wnd_size;
  uint8_t *allocatedMemory = (uint8_t *)malloc(bucketsSize + bufferSize);
  if (!allocatedMemory) // Handle allocation failure
    return 0;
  self->buckets = (Bucket *)(allocatedMemory);
  self->bitBuffer = (uint32_t *)(allocatedMemory + bucketsSize);
  self->bucketCount = 0;
  self->wndSize = wnd_size;
  self->bufferIndex = 0;
  self->totalBitsProcessed = 0;
  self->k = k;

  // Return total bytes allocated
  return bucketsSize + bufferSize;
}

void wnd_bit_count_apx_destruct(StateApx *self) {
  // TODO: Fill me.
  // Make sure you free the memory allocated on the heap.
  free(self);
  return;
}

void wnd_bit_count_apx_print(StateApx *self) {
  printf("Total bits: %u\n", self->totalBitsProcessed);
  printf("Window Size: %u\n", self->wndSize);
  printf("Bucket Count: %u\n", self->bucketCount);
  printf("Buckets:\n");

  // Print details of each bucket
  for (uint32_t i = 0; i < self->bucketCount; ++i) {
    printf("  Bucket %u: Count = %u, Timestamp = %u\n", i,
           self->buckets[i].count, self->buckets[i].ts);
  }

  // Optionally, print the bit buffer if it's not too large
  // Uncomment the following lines if you want to include the bit buffer
  // contents in the debug output
  /*
  printf("Bit Buffer:\n  ");
  for (uint32_t i = 0; i < self->wndSize; ++i) {
      printf("%u", self->bitBuffer[i]);
      if ((i + 1) % 50 == 0) // Break line every 50 bits for readability
          printf("\n  ");
  }
  printf("\n");
  */

  printf("\n"); // Add an extra newline for readability
}

void discardOldBuckets(StateApx *self) {
  // This loop will check all buckets and discard those that are too old
  while (self->bucketCount > 0) {
    // Calculate the age of the oldest bucket
    uint64_t ageOfOldestBucket = self->totalBitsProcessed - self->buckets[0].ts;

    // If the oldest bucket is outside of our window of interest, we discard it
    if (ageOfOldestBucket >= self->wndSize) {
      // Shift all buckets to the left to discard the oldest one
      for (uint32_t i = 1; i < self->bucketCount; ++i) {
        self->buckets[i - 1] = self->buckets[i];
      }
      self->bucketCount--; // Decrease the bucket count
    } else {
      // If the oldest bucket is still within the window, we stop discarding
      break;
    }
  }
}

uint32_t wnd_bit_count_apx_next(StateApx *self, bool item) {
  // Update the circular buffer with the incoming bit
  self->bitBuffer[self->bufferIndex] = item;
  uint32_t ts = self->totalBitsProcessed;
  self->bufferIndex = (self->bufferIndex + 1) % self->wndSize;
  self->totalBitsProcessed++;
  // printf("buffer Index = %d\n", self->bufferIndex);
  if (item) {
    // Add a new bucket for the "1" bit if space allows
    if (self->bucketCount < self->maxBuckets) {
      self->buckets[self->bucketCount++] = (Bucket){1, ts};
    }

    // Merge buckets as necessary
    uint32_t size = 1;
    while (size <= self->wndSize) {
      int bucketIndex = -1;
      int count = 0;
      // Find the oldest buckets of the current size
      for (uint32_t i = 0; i < self->bucketCount; ++i) {
        if (self->buckets[i].count == size) {
          if (bucketIndex == -1 ||
              self->buckets[i].ts < self->buckets[bucketIndex].ts) {
            bucketIndex = i;
          }
          count++;
        }
      }

      // If there are more than two buckets of the same size, merge the oldest
      // two
      if (count > 2 && bucketIndex != -1) {
        int secondOldestIndex = -1;
        // Find the second oldest bucket of the current size
        for (uint32_t i = 0; i < self->bucketCount; ++i) {
          if (self->buckets[i].count == size && i != bucketIndex) {
            if (secondOldestIndex == -1 ||
                self->buckets[i].ts < self->buckets[secondOldestIndex].ts) {
              secondOldestIndex = i;
            }
          }
        }

        // Merge the two oldest buckets
        if (secondOldestIndex != -1) {
          self->buckets[bucketIndex].count *= 2;
          self->buckets[bucketIndex].ts =
              max(self->buckets[bucketIndex].ts,
                  self->buckets[secondOldestIndex].ts);
          // Move the last bucket to the position of the second oldest and
          // reduce the bucket count
          self->buckets[secondOldestIndex] = self->buckets[--self->bucketCount];
        }
      } else {
        break;
      }
      size *= 2; // Move to the next size of buckets
    }
  }

  discardOldBuckets(self);

  // Estimate the count of "1"s in the last N bits
  uint32_t count = 0;
  // Iterate through each bucket to compute the count of "1"s in the last N bits
  for (uint32_t i = 0; i < self->bucketCount; ++i) {
    // Calculate how far back in the stream this bucket's bits go
    uint64_t startOfWindow;
    if (self->totalBitsProcessed >= self->wndSize) {
      startOfWindow = self->totalBitsProcessed - self->wndSize + 1;
    } else {
      startOfWindow = 0;
    }
    uint64_t startOfBucket = self->buckets[i].ts - self->buckets[i].count + 1;
    // printf("start of window %u\n", startOfWindow);
    // printf("start of bucket %u\n", startOfBucket);
    //  Check if the bucket is completely within theprintf("start of window
    //  %d\n", startOfWindow); last N bits
    count += self->buckets[i].count;
    if (startOfBucket < startOfWindow)
      count -= self->buckets[i].count / self->k;
  }

  return count;
}

#endif // _WINDOW_BIT_COUNT_APX_