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
    uint32_t* idx_newest_bucket_of_group;
    uint32_t* idx_oldest_bucket_of_group;
    uint32_t* buckets;
    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));

    // m + m + m(k + 1)
    uint64_t memory = ((uint64_t)(self->m * (k + 3))) * sizeof(uint32_t);
    self->idx_newest_bucket_of_group = (uint32_t*)malloc(memory);
    self->idx_oldest_bucket_of_group = &(self->idx_newest_bucket_of_group[self->m]);
    self->buckets = &(self->idx_newest_bucket_of_group[self->m * 2]);

    for (uint32_t i = 0; i < self->m; i++) {
        self->idx_newest_bucket_of_group[i] = -1;
        self->idx_oldest_bucket_of_group[i] = -1;
    }
    for (uint32_t i = 0; i < (self->m * (k + 1)); i++) {
        self->buckets[i] = -1;
    }

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

void wnd_bit_count_apx_print(StateApx* self) {
    // This is useful for debugging.
    printf("--------------------------\n");
    printf("Current iteration %d\n", self->now);
    printf("idx_newest_bucket_of_group\n");
    for (uint32_t i = 0; i < self->m; i++) {
        printf("id:%d, newest: %d, oldest: %d\n", i, self->idx_newest_bucket_of_group[i], self->idx_oldest_bucket_of_group[i]);
    }
}

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->idx_oldest_group != -1) {  // Make sure there is at least a group
        if (self->now - self->buckets[self->idx_oldest_group * (self->k + 1) + self->idx_oldest_bucket_of_group[self->idx_oldest_group]] >= self->wnd_size) {
            if (self->idx_oldest_bucket_of_group[self->idx_oldest_group] == self->idx_newest_bucket_of_group[self->idx_oldest_group]) {
                // There is only one bucket left in the oldest group
                // Removing this bucket will remove the whole group
                // Reset the two pointers (oldest and newest) to -1
                self->idx_oldest_bucket_of_group[self->idx_oldest_group] = -1;
                self->idx_newest_bucket_of_group[self->idx_oldest_group] = -1;
                // The oldest group is now the previous group
                self->idx_oldest_group -= 1;
                if (self->idx_oldest_group == -1) {
                    self->bit_cnt = 0;
                } else {
                    self->bit_cnt -= pow(2, self->idx_oldest_group);
                }
            } else {
                // There are more than one bucket in the oldest group
                // Update oldest pointer
                self->idx_oldest_bucket_of_group[self->idx_oldest_group] = (self->idx_oldest_bucket_of_group[self->idx_oldest_group] + 1) % (self->k + 1);
                self->bit_cnt -= pow(2, self->idx_oldest_group);
            }
        }
    }

    if (item == 1) {
        uint32_t ts_for_merged_bucket;
        bool merge_triggered = false;

        self->bit_cnt += 1;

        // Add new bucket to the first group
        if (self->idx_oldest_bucket_of_group[0] == -1 && self->idx_newest_bucket_of_group[0] == -1) {
            // Case 1: The first group is completely empty
            // Update the two pointers to 0
            self->idx_oldest_bucket_of_group[0] = 0;
            self->idx_newest_bucket_of_group[0] = 0;
            // Record the timestamp
            self->buckets[0] = self->now;
            // The oldest group becomes the first group
            self->idx_oldest_group = 0;
        } else if ((self->idx_newest_bucket_of_group[0] + 1) % (self->k + 1) == self->idx_oldest_bucket_of_group[0]) {
            // Case 2: The first group is completely full (size == k + 1)
            // This case should trigger merge
            merge_triggered = true;
            // Update the newest pointer
            self->idx_newest_bucket_of_group[0] = (self->idx_newest_bucket_of_group[0] + 1) % (self->k + 1);
            // Record the timestamp
            self->buckets[self->idx_newest_bucket_of_group[0]] = self->now;
            // Record the timestamp for the merged bucket
            ts_for_merged_bucket = self->buckets[(self->idx_oldest_bucket_of_group[0] + 1) % (self->k + 1)];
            // Update the oldest pointer (move to steps forward)
            self->idx_oldest_bucket_of_group[0] = (self->idx_oldest_bucket_of_group[0] + 2) % (self->k + 1);
        } else {
            // Case 3: Nothing special
            // Update the newest pointer
            self->idx_newest_bucket_of_group[0] = (self->idx_newest_bucket_of_group[0] + 1) % (self->k + 1);
            // Record the timestamp
            self->buckets[self->idx_newest_bucket_of_group[0]] = self->now;
        }

        uint32_t idx_cur_group = 1;
        while (merge_triggered) {
            N_MERGES += 1;
            if (self->idx_oldest_bucket_of_group[idx_cur_group] == -1 && self->idx_newest_bucket_of_group[idx_cur_group] == -1) {
                // Case 1: The current group is completely empty
                // The merging process should terminate
                merge_triggered = false;
                // Update the two pointers to 0
                self->idx_oldest_bucket_of_group[idx_cur_group] = 0;
                self->idx_newest_bucket_of_group[idx_cur_group] = 0;
                // Record the timestamp
                self->buckets[idx_cur_group * (self->k + 1) + 0] = ts_for_merged_bucket;
                // The oldest group becomes the current group
                self->idx_oldest_group = idx_cur_group;
                self->bit_cnt -= pow(2, self->idx_oldest_group - 1);
            } else if ((self->idx_newest_bucket_of_group[idx_cur_group] + 1) % (self->k + 1) == self->idx_oldest_bucket_of_group[idx_cur_group]) {
                // Case 2: The current group is completely full (size == k + 1)
                // The merging process should continue
                // Update the newest pointer
                self->idx_newest_bucket_of_group[idx_cur_group] = (self->idx_newest_bucket_of_group[idx_cur_group] + 1) % (self->k + 1);
                // Record the timestamp
                self->buckets[idx_cur_group * (self->k + 1) + self->idx_newest_bucket_of_group[idx_cur_group]] = ts_for_merged_bucket;
                // Record the timestamp for the merged bucket
                ts_for_merged_bucket = self->buckets[(self->idx_oldest_bucket_of_group[idx_cur_group] + 1) % (self->k + 1)];
                // Update the oldest pointer (move to steps forward)
                self->idx_oldest_bucket_of_group[idx_cur_group] = (self->idx_oldest_bucket_of_group[idx_cur_group] + 2) % (self->k + 1);
            } else {
                // Case 3: The current group is not completely empty and still has some space to take a new bucket
                // The merging process should terminate
                merge_triggered = false;
                // Update the newest pointer
                self->idx_newest_bucket_of_group[idx_cur_group] = (self->idx_newest_bucket_of_group[idx_cur_group] + 1) % (self->k + 1);
                // Record the timestamp
                self->buckets[idx_cur_group * (self->k + 1) + self->idx_newest_bucket_of_group[idx_cur_group]] = ts_for_merged_bucket;
            }
            idx_cur_group += 1;
        }
    }

    return self->bit_cnt;
}

#endif  // _WINDOW_BIT_COUNT_APX_