#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 100
#define CACHE_CAPACITY 3
#define HASH_SIZE 1024

// Node cho doubly linked list và hash table
typedef struct Node {
    int key;
    char value[MAX_LEN];
    int freq;
    struct Node *prev, *next;
    struct Node *hnext; // next trong hash chain
} Node;

// Hash map đơn giản
Node* hashmap[HASH_SIZE];

// Hàm băm đơn giản
int hash(int key) {
    return key % HASH_SIZE;
}

Node* hash_get(int key) {
    int idx = hash(key);
    Node* cur = hashmap[idx];
    while (cur) {
        if (cur->key == key) return cur;
        cur = cur->hnext;
    }
    return NULL;
}

void hash_put(Node* node) {
    int idx = hash(node->key);
    node->hnext = hashmap[idx];
    hashmap[idx] = node;
}

void hash_remove(int key) {
    int idx = hash(key);
    Node *cur = hashmap[idx], *prev = NULL;
    while (cur) {
        if (cur->key == key) {
            if (prev) prev->hnext = cur->hnext;
            else hashmap[idx] = cur->hnext;
            return;
        }
        prev = cur;
        cur = cur->hnext;
    }
}

// ==== LRU ====
Node *lru_head = NULL, *lru_tail = NULL;
int lru_size = 0;

void lru_move_to_front(Node* node) {
    if (node == lru_head) return;
    if (node->prev) node->prev->next = node->next;
    if (node->next) node->next->prev = node->prev;
    if (node == lru_tail) lru_tail = node->prev;
    node->prev = NULL;
    node->next = lru_head;
    if (lru_head) lru_head->prev = node;
    lru_head = node;
    if (!lru_tail) lru_tail = lru_head;
}

void lru_remove_tail() {
    if (!lru_tail) return;
    Node* temp = lru_tail;
    if (lru_tail->prev) lru_tail->prev->next = NULL;
    lru_tail = lru_tail->prev;
    if (!lru_tail) lru_head = NULL;
    hash_remove(temp->key);
    free(temp);
    lru_size--;
}

void lru_put(int key, const char* value) {
    Node* node = hash_get(key);
    if (node) {
        strncpy(node->value, value, MAX_LEN);
        lru_move_to_front(node);
        return;
    }
    if (lru_size == CACHE_CAPACITY) lru_remove_tail();
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->key = key;
    strncpy(new_node->value, value, MAX_LEN);
    new_node->prev = new_node->next = new_node->hnext = NULL;
    new_node->freq = 1;
    new_node->next = lru_head;
    if (lru_head) lru_head->prev = new_node;
    lru_head = new_node;
    if (!lru_tail) lru_tail = lru_head;
    hash_put(new_node);
    lru_size++;
}

char* lru_get(int key) {
    Node* node = hash_get(key);
    if (!node) return NULL;
    node->freq++;
    lru_move_to_front(node);
    return node->value;
}

void print_lru_cache() {
    Node* cur = lru_head;
    printf("LRU Cache: ");
    while (cur) {
        printf("(%d:%s) ", cur->key, cur->value);
        cur = cur->next;
    }
    printf("\n");
}

// ==== MRU ====
Node *mru_head = NULL, *mru_tail = NULL;
int mru_size = 0;

void mru_remove_head() {
    if (!mru_head) return;
    Node* temp = mru_head;
    if (mru_head->next) mru_head->next->prev = NULL;
    mru_head = mru_head->next;
    if (!mru_head) mru_tail = NULL;
    hash_remove(temp->key);
    free(temp);
    mru_size--;
}

void mru_put(int key, const char* value) {
    Node* node = hash_get(key);
    if (node) {
        strncpy(node->value, value, MAX_LEN);
        return;
    }
    if (mru_size == CACHE_CAPACITY) mru_remove_head();
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->key = key;
    strncpy(new_node->value, value, MAX_LEN);
    new_node->prev = mru_tail;
    new_node->next = NULL;
    new_node->hnext = NULL;
    new_node->freq = 1;
    if (mru_tail) mru_tail->next = new_node;
    mru_tail = new_node;
    if (!mru_head) mru_head = new_node;
    hash_put(new_node);
    mru_size++;
}

void print_mru_cache() {
    Node* cur = mru_head;
    printf("MRU Cache: ");
    while (cur) {
        printf("(%d:%s) ", cur->key, cur->value);
        cur = cur->next;
    }
    printf("\n");
}

// ==== MFU ====
Node* mfu_list = NULL;
int mfu_size = 0;

void mfu_remove_most_frequent() {
    Node *prev = NULL, *cur = mfu_list, *target = NULL, *target_prev = NULL;
    int max_freq = -1;
    while (cur) {
        if (cur->freq > max_freq) {
            max_freq = cur->freq;
            target = cur;
            target_prev = prev;
        }
        prev = cur;
        cur = cur->next;
    }
    if (!target) return;
    if (target_prev) target_prev->next = target->next;
    else mfu_list = target->next;
    hash_remove(target->key);
    free(target);
    mfu_size--;
}

void mfu_put(int key, const char* value) {
    Node* node = hash_get(key);
    if (node) {
        strncpy(node->value, value, MAX_LEN);
        node->freq++;
        return;
    }
    if (mfu_size == CACHE_CAPACITY) mfu_remove_most_frequent();
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->key = key;
    strncpy(new_node->value, value, MAX_LEN);
    new_node->prev = new_node->next = NULL;
    new_node->hnext = NULL;
    new_node->freq = 1;
    new_node->next = mfu_list;
    mfu_list = new_node;
    hash_put(new_node);
    mfu_size++;
}

void print_mfu_cache() {
    Node* cur = mfu_list;
    printf("MFU Cache: ");
    while (cur) {
        printf("(%d:%s|f%d) ", cur->key, cur->value, cur->freq);
        cur = cur->next;
    }
    printf("\n");
}

int main() {
    printf("=== LRU Cache Test ===\n");
    lru_put(1, "A"); lru_put(2, "B"); lru_put(3, "C");
    print_lru_cache();
    lru_get(2); print_lru_cache();
    lru_put(4, "D"); print_lru_cache();

    memset(hashmap, 0, sizeof(hashmap));
    printf("\n=== MRU Cache Test ===\n");
    mru_put(1, "A"); mru_put(2, "B"); mru_put(3, "C");
    print_mru_cache();
    mru_put(4, "D"); print_mru_cache();

    memset(hashmap, 0, sizeof(hashmap));
    printf("\n=== MFU Cache Test ===\n");
    mfu_put(1, "A"); mfu_put(2, "B"); mfu_put(3, "C");
    print_mfu_cache();
    mfu_put(2, "B"); mfu_put(4, "D");
    print_mfu_cache();

    return 0;
}