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 {
    // TODO: Fill me.
    uint32_t wnd_size;  // input
    uint32_t k;         // input
    uint32_t now;       // current ts
    uint32_t m;         // total number of groups
    // the first m int is ptr to available buckets, the rest are m * (k + 1) buckets with ts
    uint32_t* arr;
    uint32_t* ptr_buckets;
    uint32_t* ptr_oldest_bucket;
    uint32_t idx_oldest_group;
    uint32_t bit_cnt;
} 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->m = ceil(1 + log2((wnd_size - 1) / k + 1));

    // (self->m + self->m * (k + 1))
    uint64_t memory = ((uint64_t)(self->m * (k + 2))) * sizeof(uint32_t);
    // store the next avaliable space for buckets
    self->arr = (uint32_t*)malloc(memory);
    // store the oldest bucket for each group
    self->ptr_oldest_bucket = &(self->arr[self->m]);
    // store the timestamp of each bucket
    self->ptr_buckets = &(self->arr[self->m * 2]);

    for (uint32_t i = 0; i < self->m; i++) {
        self->arr[i] = 0;
        self->ptr_oldest_bucket[i] = 0;
    }
    for (uint32_t i = 0; i < (self->m * (k + 1)); i++) {
        self->ptr_buckets[i] = -1;
    }

    self->idx_oldest_group = 0;
    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->arr);
}

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;

    uint32_t row = self->idx_oldest_group;
    uint32_t col = self->ptr_oldest_bucket[row];
    uint32_t point = row * (self->k + 1) + col;

    // If the oldest bucket falls out the window, remove it
    if (self->now - self->ptr_buckets[point] >= self->wnd_size && self->ptr_buckets[point] != -1) {
        // remove the bucket
        self->ptr_buckets[point] = -1;
        // update the ptr_oldest_bucket
        self->ptr_oldest_bucket[row] = (col + 1) % (self->k + 1);
        // no bucket in the oldest group
        if (self->arr[row] == self->ptr_oldest_bucket[row]) {
            self->idx_oldest_group -= 1;
            // new row
            row -= 1;
        }

        // update the count
        self->bit_cnt -= pow(2, row);
    }

    // check -> merge -> clear -> add -> next
    // if the bucket is occupied
    bool next = true;
    row = 0;
    
    uint32_t ts_cur = self->now;
    uint32_t ts_buffer = 0;

    while (next){
        // check
        col = self->arr[row];
        if(self->ptr_buckets[row * (self->k + 1) + col] > 0){
            // merge
            ts_buffer = self->ptr_buckets[row*(self->k + 1) + ((col+1)%(self->k + 1))];
            N_MERGES++;
            // clear
            self->ptr_buckets[row * (self->k + 1) + col] = -1;
            self->ptr_buckets[row*(self->k + 1) + ((col+1)%(self->k + 1))] = -1;
        }
        else{
            next = false;
        }
        // add
        self->ptr_buckets[row * (self->k + 1) + col] = ts_cur;
        // next
        ts_cur = ts_buffer;
        row += 1;
    }
    if(self->arr[row] != self->ptr_oldest_bucket[row]){
        self->bit_cnt -= pow(2, row-1);
    }

    return self->bit_cnt;
}

#endif  // _WINDOW_BIT_COUNT_APX_