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 {
    uint32_t size;  // bucket size
    uint32_t ts;    // the timestamp
} Bucket;

typedef struct {
    // TODO: Fill me.
    uint32_t wnd_size;        // input
    uint32_t k;               // input
    uint32_t now;             // current ts
    uint32_t idx_oldest;      // index of the oldest bucket
    uint32_t idx_newest;      // index of the newest bucket
    uint32_t max_bucket_cnt;  // max count of the buckets (max_groups * max_buckets_in_group)
    Bucket* buckets;          // the bucket buffer
    uint32_t bit_cnt;         // the apx answer we are calculating
} 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->wnd_size = wnd_size;
    self->k = k;
    self->now = 0;
    self->idx_oldest = 0;
    self->idx_newest = 0;

    uint32_t max_groups = 1 + log2((wnd_size - 1) / k + 1);
    uint32_t max_buckets_in_group = k + 1;
    self->max_bucket_cnt = max_groups * max_buckets_in_group;

    uint64_t memory = ((uint64_t)self->max_bucket_cnt) * sizeof(Bucket);
    self->buckets = (Bucket*)malloc(memory);
    for (uint32_t i = 0; i < self->max_bucket_cnt; i++) {
        self->buckets[i].ts = -1;
        self->buckets[i].size = -1;
    }

    self->bit_cnt = 0;

    // TODO:
    // The function should return the total number of bytes allocated on the heap.
    return memory;
}

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) {
    // This is useful for debugging.
}

uint32_t wnd_bit_count_apx_next(StateApx* self, bool item) {
    // TODO: Fill me.
    self->now += 1;

    // If the oldest bucket falls out the window, remove it
    if (self->now - self->buckets[self->idx_oldest].ts >= self->wnd_size && self->buckets[self->idx_oldest].ts != -1) {
        self->idx_oldest = (self->idx_oldest + 1) % self->max_bucket_cnt;
        self->bit_cnt -= self->buckets[self->idx_oldest].size;
    }

    if (item == 1) {
        self->idx_newest = (self->idx_newest + 1) % self->max_bucket_cnt;
        self->bit_cnt += 1;

        // Add new bucket to the bucket buffer
        self->buckets[self->idx_newest].size = 1;
        self->buckets[self->idx_newest].ts = self->now;

        // Traverse bucket buffer from newest to oldest
        // If a group has (k + 2) buckets, merge the oldest two
        if (self->idx_newest > self->idx_oldest) { // Normal case

        } else { // The idx_newest is wrapped around

        }
    }

    return self->bit_cnt;
}

#endif  // _WINDOW_BIT_COUNT_APX_