node-lfu-cache - npm Package Compare versions

Comparing version 4.1.1 to 5.0.0

index.js

@@ -54,3 +54,3 @@ 'use strict'
   }
-  this.LRU_LIST=LRU_LIST;
+
   if (!options) {
@@ -150,11 +150,8 @@ options = {}
 
-// LRUCache.prototype.rforEach = function (fn, thisp) {
-//   thisp = thisp || this
-//   for (var walker = this[LRU_LIST].tail; walker !== null;) {
-//     var prev = walker.prev
-//     forEachStep(this, fn, walker, thisp)
-//     walker = prev
-//   }
-// }
-
+LRUCache.prototype.rforEach = function (fn, thisp) {
+  thisp = thisp || this
+  this[LRU_LIST].forEachRawReverse(walker => {
+    forEachStep(this, fn, walker, thisp)
+  })
+}
 function forEachStep (self, fn, node, thisp) {
@@ -175,3 +172,3 @@ var hit = node.value
   thisp = thisp || this
-  this[LRU_LIST].forEachRaw(walker=> {
+  this[LRU_LIST].forEachRaw(walker => {
     forEachStep(this, fn, walker, thisp)
@@ -218,3 +215,3 @@ })
     return h
-  }).reverse();
+  })
 }
@@ -413,3 +410,3 @@
       if (doUse) {
-        node.bump();
+        node.bump()
       }
@@ -438,5 +435,7 @@ }
   while (self[LENGTH] > self[MAX]) {
-    let walker = self[LRU_LIST].tail();
+    let walker = self[LRU_LIST].tail()
+    // I'm not sure how this if could be triggered, but I'm not certain it can't
+    /* istanbul ignore if */
     if (!walker) {
-      break;
+      break
     }
@@ -443,0 +442,0 @@ del(self, walker)

list.js

@@ -1,177 +0,190 @@
-var Yallist = require('yallist')
-
 class Item {
-  constructor(value, freq, list) {
-    this.value = value;
-    this.list = list;
-    this.freq = freq;
-    this.next = this.prev = null;
-    this.freq.pushItem(this);
+  constructor (value, freq, list) {
+    this.value = value
+    this.list = list
+    this.freq = freq
+    this.next = this.prev = null
+    this.freq.pushItem(this)
   }
-  bump() {
-    // console.log('bump', this);
-    var cur = this.freq;
-    var inc = cur.getNext();
-    cur.removeItem(this);
+  bump () {
+    // console.log('bump', this)
+    var cur = this.freq
+    var inc = cur.getNext()
+    if (!inc.next) {
+      this.list.max = inc
+    }
+    cur.removeItem(this)
     if (!cur.head && !cur.tail) {
-      this.list.removeFreq(cur);
+      this.list.removeFreq(cur)
     }
-    inc.pushItem(this);
+    inc.pushItem(this)
   }
 }
 class FreqItem {
-  constructor(num) {
-    this.num = num;
-    this.head = this.tail = null;
-    this.next = this.prev = null;
+  constructor (num) {
+    this.num = num
+    this.head = this.tail = null
+    this.next = this.prev = null
   }
-  pushItem(node) {
-    node.freq = this;
+  pushItem (node) {
+    node.freq = this
     if (!this.head && !this.tail) {
-      this.head = this.tail = node;
-      node.next = node.prev = null;
-      return;
+      this.head = this.tail = node
+      node.next = node.prev = null
+      return
     }
-    node.prev = this.tail;
-    node.next = null;
-    this.tail.next = node;
-    this.tail = node;
+    node.prev = this.tail
+    node.next = null
+    this.tail.next = node
+    this.tail = node
   }
-  // unshiftItem(node) {
-  //   if (!this.head && !this.tail) {
-  //     this.head = this.tail = node;
-  //     return;
-  //   }
-  //   node.next = this.head;
-  //   this.head.prev = node;
-  //   this.head = node;
-  // }
-  removeItem(node) {
+  removeItem (node) {
     if (this.head === node) {
       if (this.tail === node) {
-        this.head = this.tail = null;
-        return;
+        this.head = this.tail = null
+        return
       }
-      this.head = node.next;
-      this.head.prev = null;
-      return;
+      this.head = node.next
+      this.head.prev = null
+      return
     }
     if (this.tail === node) {
-      this.tail = node.prev;
-      this.tail.next = null;
-      return;
+      this.tail = node.prev
+      this.tail.next = null
+      return
     }
-    let prev = node.prev;
-    let next = node.next;
-    prev.next = next;
-    next.prev = prev;
+    let prev = node.prev
+    let next = node.next
+    prev.next = next
+    next.prev = prev
   }
-  insertBefore(node) {
-    node.next = this;
+  insertBefore (node) {
+    node.next = this
     // if (this.prev) {
-    //   this.prev.next = node;
-    //   node.prev = this.prev;
+    //   this.prev.next = node
+    //   node.prev = this.prev
     // }
-    this.prev = node;
+    this.prev = node
   }
-  getNext() {
+  getNext () {
     if (!this.next || this.next.num !== this.num + 1) {
-      this.insertAfter(new FreqItem(this.num + 1));
+      this.insertAfter(new FreqItem(this.num + 1))
     }
-    return this.next;
+    return this.next
   }
-  insertAfter(node) {
-    node.prev = this;
+  insertAfter (node) {
+    node.prev = this
     if (this.next) {
-      this.next.prev = node;
-      node.next = this.next;
+      this.next.prev = node
+      node.next = this.next
     }
-    this.next = node;
+    this.next = node
   }
 }
 class List {
-  constructor() {
-    this.root = new FreqItem(1);
-    this.length = 0;
+  constructor () {
+    this.root = new FreqItem(1)
+    this.max = this.root
+    this.length = 0
   }
-  insert(value) {
-    // console.log('add', value);
-    this.length++;
-    // if (!this.root) {
-    //   this.root = new FreqItem(1);
-    // }
+  insert (value) {
+    this.length++
     if (this.root.num !== 1) {
-      let newRoot = new FreqItem(1);
-      this.root.insertBefore(newRoot);
-      this.root = newRoot;
+      let newRoot = new FreqItem(1)
+      this.root.insertBefore(newRoot)
+      this.root = newRoot
     }
-    let item = new Item(value, this.root, this);
-    return item;
+    let item = new Item(value, this.root, this)
+    return item
   }
-  removeFreq(node) {
+  removeFreq (node) {
     if (this.root === node) {
-      if (node.next === null) {
-        this.root = new  FreqItem(1);
-        return;
+      if (this.max === node) {
+        this.root = this.max = new FreqItem(1)
+        return
       }
-      this.root = node.next;
-      this.root.prev = null;
-      return;
+      this.root = node.next
+      this.root.prev = null
+      return
     }
-    // console.log('this', this);
-    // console.log('node', node);
-    let prev = node.prev;
-    let next = node.next;
-    prev.next = next;
+    // console.log('this', this)
+    // console.log('node', node)
+    let prev = node.prev
+    let next = node.next
+    prev.next = next
     if (next) {
-      next.prev = prev;
+      next.prev = prev
+    } else {
+      this.max = prev
     }
   }
-  tail() {
-    return this.root.head;
+  tail () {
+    return this.root.head
   }
-  remove(node) {
-    // console.log('remove', node.value);
-    this.length--;
-    var freq = node.freq;
-    freq.removeItem(node);
+  head () {
+    return this.max.tail
+  }
+  remove (node) {
+    // console.log('remove', node.value)
+    this.length--
+    var freq = node.freq
+    freq.removeItem(node)
     if (!freq.head && !freq.tail) {
-      this.removeFreq(freq);
+      this.removeFreq(freq)
     }
   }
-  forEach(fn, self) {
-    self = self || this;
+  forEach (fn, self) {
+    self = self || this
     this.forEachRaw((node, i) => {
-      fn.call(self, node.value, i, this);
+      fn.call(self, node.value, i, this)
     })
   }
-  forEachRaw(fn, self) {
-    let freq = this.root;
-    let node = freq.head;
-    self = self || this;
-    var i = -1;
+  forEachRaw (fn, self) {
+    let freq = this.max
+    let node = freq.tail
+    self = self || this
+    var i = -1
     while (node) {
-      fn.call(self, node, ++i, this);
+      fn.call(self, node, ++i, this)
+      if (node.prev) {
+        node = node.prev
+        continue
+      }
+      if (freq.prev) {
+        freq = freq.prev
+        node = freq.tail
+        continue
+      }
+      return
+    }
+  }
+  forEachRawReverse (fn, self) {
+    let freq = this.root
+    let node = freq.head
+    self = self || this
+    var i = -1
+    while (node) {
+      fn.call(self, node, ++i, this)
       if (node.next) {
-        node = node.next;
-        continue;
+        node = node.next
+        continue
       }
       if (freq.next) {
-        freq = freq.next;
-        node = freq.head;
-        continue;
+        freq = freq.next
+        node = freq.head
+        continue
       }
-      return;
+      return
     }
   }
-  toArray() {
-    let out = new Array(this.length);
+  toArray () {
+    let out = new Array(this.length)
     this.forEach(function (node, i) {
-      // console.log(value, i);
-      out[i] = node;
-    });
-    return out;
+      // console.log(value, i)
+      out[i] = node
+    })
+    return out
   }
 }
 
-module.exports = List;
+module.exports = List

package.json

 {
   "name": "node-lfu-cache",
   "description": "A cache object that deletes the least-frequently-used items.",
-  "version": "4.1.1",
+  "version": "5.0.0",
   "author": "Isaac Z. Schlueter <[e-mail]>",
@@ -13,3 +13,3 @@ "keywords": [
     "test": "tap test/*.js --100 -J",
-    "posttest": "standard test/*.js index.js",
+    "posttest": "standard test/*.js index.js list.js",
     "preversion": "npm test",
@@ -16,0 +16,0 @@ "postversion": "npm publish",

README.md

 # lfu cache
 
-A cache object that deletes the least-frequently-used items.
+A cache object that deletes the least-frequently-used items.  A direct port of [lru-cache](https://github.com/isaacs/node-lru-cache) but using [this algorithm](http://dhruvbird.com/lfu.pdf).
 
@@ -15,20 +15,27 @@
 ```javascript
-var LRU = require("node-lfu-cache")
-  , options = { max: 500
-              , length: function (n, key) { return n * 2 + key.length }
-              , dispose: function (key, n) { n.close() }
-              , maxAge: 1000 * 60 * 60 }
-  , cache = LRU(options)
-  , otherCache = LRU(50) // sets just the max size
+var LFU = require('node-lfu-cache');
+var options = {
+  max: 500,
+  length: function (n, key) {
+    return n * 2 + key.length;
+  },
+  dispose: function (key, n) {
+    n.close();
+  },
+  maxAge: 1000 * 60 * 60
+};
+var cache = LFU(options);
+var otherCache = LFU(50); // sets just the max size
 
-cache.set("key", "value")
-cache.get("key") // "value"
+cache.set('key', 'value');
+cache.get('key'); // "value"
 
 // non-string keys ARE fully supported
-var someObject = {}
-cache.set(someObject, 'a value')
-cache.set('[object Object]', 'a different value')
-assert.equal(cache.get(someObject), 'a value')
+var someObject = {};
 
-cache.reset()    // empty the cache
+cache.set(someObject, 'a value');
+cache.set('[object Object]', 'a different value');
+assert.equal(cache.get(someObject), 'a value');
+
+cache.reset();    // empty the cache
 ```
@@ -112,3 +119,3 @@
     Just like `Array.prototype.forEach`.  Iterates over all the keys
-    in the cache, in order of least-frequent-ness.  (Ie, more recently used
+    in the cache, in order of frequent-ness.  (Ie, more frequently used
     items are iterated over first.)
@@ -118,8 +125,6 @@
 
-    Not implemented.
+    The same as `cache.forEach(...)` but items are iterated over in
+    reverse order.  (ie, least frequently used items are iterated over
+    first.)
 
-    ~~The same as `cache.forEach(...)` but items are iterated over in
-    reverse order.  (ie, most frequently used items are iterated over
-    first.)~~
-
 * `keys()`
@@ -126,0 +131,0 @@

No alert changes

Improved metrics

Total package byte prevSize

20911

0.91%

Lines of code

591

2.25%

Number of lines in readme file

163

3.16%

No dependency changes