Untitled

#ifndef _WINDOW_BIT_COUNT_APX_
#define _WINDOW_BIT_COUNT_APX_

#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 cur_ts; // Current index in the circular bit buffer
  uint32_t k;           // 1/eps, controls precision
} 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->wndSize = wnd_size;
  self->k = k+1;
  self->cur_ts = 0;

  uint32_t max_groups = 1 + log2((wnd_size - 1) / k + 1);
  uint32_t max_buckets_in_group = k + 1;
  self->maxBuckets = max_buckets_in_group * max_groups;
  uint64_t totalBytesAllocated = sizeof(Bucket) * self->maxBuckets;
  self->buckets = (Bucket *)malloc(totalBytesAllocated);
  self->bucketCount = 0;
  // TODO:
  // The function should return the total number of bytes allocated on the heap.
  return totalBytesAllocated;
}

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

void wnd_bit_count_apx_print(StateApx *self){
  /*printf("Total bits: %u\n", self->cur_ts);
  /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 mergeBuckets(StateApx *self){
  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 (count > self->k && 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 = self->buckets[secondOldestIndex].ts;
        for (uint32_t i = secondOldestIndex; i < self->bucketCount - 1; i++)
          self->buckets[i] = self->buckets[i + 1];
        self->bucketCount--;
      }
    }
    else
      break;
    size *= 2; // Move to the next size of buckets
  }
  return;
}

void discardOldBuckets(StateApx *self){
  while (self->bucketCount > 0){
    // Calculate the age of the oldest bucket
    uint64_t ageOfOldestBucket = self->cur_ts - 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
      break;
  }
  return;
}

uint32_t wnd_bit_count_apx_next(StateApx *self, bool item){
  // TODO: Fill me.
  uint32_t ts = self->cur_ts;
  self->cur_ts++;
  if(item){
    self->buckets[(self->bucketCount)%(self->maxBuckets)] = (Bucket){1, ts};
    self->bucketCount++;
    mergeBuckets(self);
    discardOldBuckets(self);
  }
  uint32_t val = 0;
  for (uint32_t i = 1; i < self->bucketCount; i++){
    val = val += self->buckets[i].count;
  }
  uint32_t startOfWindow = self->cur_ts - self->wndSize;
  if (startOfWindow < 0)
    startOfWindow = 0;
  if (self->bucketCount > 0 && (self->buckets[0].ts - startOfWindow) < self->buckets[0].count)
    val++;
  else
    val += self->buckets[0].count;
  return val;
}

#endif // _WINDOW_BIT_COUNT_APX_