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 ts;
} Bucket;

typedef struct {
    // TODO: Fill me.
    uint32_t wnd_size;
    uint32_t k;
    uint32_t now;
    Bucket** groups;
} 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;

    uint32_t max_buckets = (uint32_t)(k * log2((double)wnd_size / k)) + 1;
    uint64_t memory = ((uint64_t)max_buckets) * sizeof(Bucket*);
    self->groups = (Bucket**)malloc(memory);
    for (uint32_t i = 0; i < max_buckets; i++) {
        self->groups[i] = NULL;
    }

    // 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->groups);
}

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.
    return 0;
}

#endif  // _WINDOW_BIT_COUNT_APX_