Advertisement
klippa

LRU

Aug 19th, 2022
691
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class ListNode {
  2.   constructor(value = null, key = null, prev = null, next = null) {
  3.     this.value = value;
  4.     this.key = key;
  5.     this.prev = prev;
  6.     this.next = next;
  7.   }
  8. }
  9.  
  10. class LruCache {
  11.   constructor(MAX_SIZE) {
  12.     this.MAX_SIZE = MAX_SIZE;
  13.     this.size = 0;
  14.     this.headGuard = new ListNode();
  15.     this.tailGuard = new ListNode();
  16.     this.headGuard.next = this.tailGuard;
  17.     this.tailGuard.prev = this.headGuard;
  18.     this.lookup = new Map();
  19.   }
  20.  
  21.   #moveToFront(node) {
  22.     node.next.prev = node.prev;
  23.     node.prev.next = node.next;
  24.     this.#addToFront(node);
  25.   }
  26.  
  27.   #removeFromBack() {
  28.     if (this.headGuard.next === this.tailGuard) {
  29.       return;
  30.     }
  31.     this.headGuard.next = this.headGuard.next.next;
  32.     this.headGuard.next.prev = this.headGuard;
  33.   }
  34.  
  35.   #addToFront(node) {
  36.     node.prev = this.tailGuard.prev;
  37.     node.next = this.tailGuard;
  38.     this.tailGuard.prev = node;
  39.     node.prev.next = node;
  40.   }
  41.  
  42.   get(key) {
  43.     const node = this.lookup.get(key);
  44.     if (!node) return null;
  45.     this.#moveToFront(node);
  46.     return node.value;
  47.   }
  48.  
  49.   set(key, value) {
  50.     let node = this.lookup.get(key);
  51.     if (node) {
  52.       this.#moveToFront(node);
  53.       return;
  54.     }
  55.     if (this.size === this.MAX_SIZE) {
  56.       this.lookup.delete(this.headGuard.next.key);
  57.       this.#removeFromBack();
  58.     } else {
  59.       this.size++;
  60.     }
  61.     node = new ListNode(value, key);
  62.     this.#addToFront(node);
  63.     this.lookup.set(key, node);
  64.   }
  65. }
  66.  
  67. const cache = new LruCache(3);
  68. console.log(cache.get("a"));
  69. cache.set("a", "foo");
  70. console.log(cache.get("a"));
  71. cache.set("b", "bar");
  72. cache.set("c", "baz");
  73. console.log(cache.get("c"));
  74. console.log(cache.get("a"));
  75. console.log(cache.get("b"));
  76. cache.set("d", "qux");
  77. console.log(cache.lookup);
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement