1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import { DoublyLinkedList } from "../design-linked-list/DoublyLinkedList.ts";import { MyLinkedList } from "./MyLinkedList.ts";
class LFUCache {    readonly #key_to_freq: Map<number, number> = new Map();    readonly #key_to_value: Map<number, number> = new Map();    readonly #freq_to_keys = new Map<number, Set<number>>();    readonly #freq_to_node = new Map<number, DoublyLinkedList<number>>();    readonly #capacity: number;    readonly #linked_list = new MyLinkedList<number>();    constructor(capacity: number) {        if (capacity < 0) throw Error("capacity invalid");        this.#capacity = capacity;    }
    #least_frequently_recently_used_key = (): number | undefined => {        const least_freq_node = this.#linked_list.firstNode();        const least_frequent = least_freq_node && least_freq_node.val;
        if (typeof least_frequent === "number") {            const least_freq_keys = this.#freq_to_keys.get(least_frequent);            if (least_freq_keys && least_freq_keys.size) {                for (const key of least_freq_keys) {                    return key;                }            }        }        return;    };    #delete(key: number): void {        const freq = this.#key_to_freq.get(key);        this.#key_to_freq.delete(key);        this.#key_to_value.delete(key);        if (typeof freq !== "undefined") {            this.#remove_key_empty_freq_node(freq, key);        }    }    #remove_key_empty_freq_node(freq: number, key: number) {        const freq_set = this.#freq_to_keys.get(freq);        freq_set && freq_set.delete(key);        if (freq_set && freq_set.size === 0) {            this.#freq_to_keys.delete(freq);            const node = this.#freq_to_node.get(freq);            this.#freq_to_node.delete(freq);            node && this.#linked_list.removeNode(node);        }    }
    get #size() {        return this.#key_to_freq.size;    }    #increase(key: number): void {        // debugger;        const freq = (this.#key_to_freq.get(key) ?? 0) + 1;
        this.#key_to_freq.set(key, freq);
        if (!this.#freq_to_keys.has(freq)) {            const node = DoublyLinkedList(freq);            this.#freq_to_keys.set(freq, new Set());            if (freq === 1) {                this.#linked_list.addFirst(node);
                this.#freq_to_node.set(freq, node);            } else {                const prev = this.#freq_to_node.get(freq - 1);                // debugger;                if (!prev) {                    throw new Error("accident prev is undefined");                }                this.#linked_list.addAfter(prev, node);
                this.#freq_to_node.set(freq, node);            }        }        const freq_set = this.#freq_to_keys.get(freq);        freq_set && freq_set.add(key);
        this.#remove_key_empty_freq_node(freq - 1, key);    }
    get(key: number): number {        if (this.#capacity === 0) return -1;        const value = this.#key_to_value.get(key);        // debugger;        if (typeof value === "number" && this.#has(key)) {            this.#increase(key);            return value;        }        return -1;    }    #has(key: number): boolean {        return this.#key_to_value.has(key);    }    put(key: number, value: number): void {        if (this.#capacity === 0) return;        // debugger;        if (!this.#has(key)) {            if (this.#size === this.#capacity) {                const to_be_removed_key = this                    .#least_frequently_recently_used_key();                if (typeof to_be_removed_key === "number") {                    this.#delete(to_be_removed_key);                }            }        }        this.#increase(key);        this.#key_to_value.set(key, value);    }}export default LFUCache;