mnemonist - npm Package Compare versions

Comparing version 0.24.0 to 0.25.0

CHANGELOG.md

 # Changelog
 
+## 0.25.0
+
+* Adding `LRUCache`.
+* Adding `LRUMap`.
+
 ## 0.24.0
@@ -4,0 +9,0 @@

index.d.ts

@@ -26,2 +26,4 @@ /**
 export {default as LinkedList} from './linked-list';
+export {default as LRUCache} from './lru-cache';
+export {default as LRUMap} from './lru-map';
 export {default as MultiMap} from './multi-map';
@@ -28,0 +30,0 @@ export {default as MultiSet} from './multi-set';

index.js

@@ -35,2 +35,4 @@ /**
   LinkedList: require('./linked-list.js'),
+  LRUCache: require('./lru-cache.js'),
+  LRUMap: require('./lru-map.js'),
   MultiMap: require('./multi-map.js'),
@@ -37,0 +39,0 @@ MultiSet: require('./multi-set.js'),

lru-cache.js

@@ -19,12 +19,6 @@ /**
 var Iterator = require('obliterator/iterator'),
-    typed = require('./utils/typed-arrays.js');
+    forEach = require('obliterator/foreach'),
+    typed = require('./utils/typed-arrays.js'),
+    iterables = require('./utils/iterables.js');
 
-// TODO: use singly linked list, hashmap points to precedent pointer instead?
-
-// TODO: possibility to type keys & values but not sure it results in better
-// perfs. just better memory in some corner cases
-
-// TODO: potential optimizations to be run in splayOnTop
-// TODO: possibiliy to drop the keys array by storing keys as head/tail pointers
-
 /**
@@ -34,7 +28,18 @@ * LRUCache.
  * @constructor
- * @param {number} capacity - Desired capacity.
+ * @param {function} Keys     - Array class for storing keys.
+ * @param {function} Values   - Array class for storing values.
+ * @param {number}   capacity - Desired capacity.
  */
-function LRUCache(capacity) {
+function LRUCache(Keys, Values, capacity) {
+  if (arguments.length < 2) {
+    capacity = Keys;
+    Keys = null;
+    Values = null;
+  }
+
   this.capacity = capacity;
 
+  if (typeof this.capacity !== 'number' || this.capacity <= 0)
+    throw new Error('mnemonist/lru-cache: capacity should be positive number.');
+
   var PointerArray = typed.getPointerArray(capacity);
@@ -44,4 +49,4 @@
   this.backward = new PointerArray(capacity);
-  this.keys = new Array(capacity);
-  this.values = new Array(capacity);
+  this.K = typeof Keys === 'function' ? new Keys(capacity) : new Array(capacity);
+  this.V = typeof Values === 'function' ? new Values(capacity) : new Array(capacity);
 
@@ -60,4 +65,2 @@ // Properties
  */
-
-// TODO: test
 LRUCache.prototype.clear = function() {
@@ -115,3 +118,3 @@ this.size = 0;
     this.splayOnTop(existingPointer);
-    this.values[existingPointer] = value;
+    this.V[existingPointer] = value;
 
@@ -132,3 +135,3 @@ return;
     this.tail = this.backward[pointer];
-    delete this.items[this.keys[pointer]];
+    delete this.items[this.K[pointer]];
   }
@@ -138,4 +141,4 @@
   this.items[key] = pointer;
-  this.keys[pointer] = key;
-  this.values[pointer] = value;
+  this.K[pointer] = key;
+  this.V[pointer] = value;
 
@@ -158,6 +161,2 @@ // Moving the item at the front of the list
 
-// #.delete? through free pointers stack?
-
-// TODO: better eviction test/replicate bench
-
 /**
@@ -178,8 +177,97 @@ * Method used to get the value attached to the given key. Will move the
 
-  return this.values[pointer];
+  return this.V[pointer];
 };
 
-// TODO: #.keys, #.values
+/**
+ * Method used to iterate over the cache's entries using a callback.
+ *
+ * @param  {function}  callback - Function to call for each item.
+ * @param  {object}    scope    - Optional scope.
+ * @return {undefined}
+ */
+LRUCache.prototype.forEach = function(callback, scope) {
+  scope = arguments.length > 1 ? scope : this;
 
+  var i = 0,
+      l = this.size;
+
+  var pointer = this.head,
+      keys = this.K,
+      values = this.V,
+      forward = this.forward;
+
+  while (i < l) {
+
+    callback.call(scope, values[pointer], keys[pointer], this);
+    pointer = forward[pointer];
+
+    i++;
+  }
+};
+
 /**
+ * Method used to create an iterator over the cache's keys from most
+ * recently used to least recently used.
+ *
+ * @return {Iterator}
+ */
+LRUCache.prototype.keys = function() {
+  var i = 0,
+      l = this.size;
+
+  var pointer = this.head,
+      keys = this.K,
+      forward = this.forward;
+
+  return new Iterator(function() {
+    if (i >= l)
+      return {done: true};
+
+    var key = keys[pointer];
+
+    i++;
+
+    if (i < l)
+      pointer = forward[pointer];
+
+    return {
+      done: false,
+      value: key
+    };
+  });
+};
+
+/**
+ * Method used to create an iterator over the cache's values from most
+ * recently used to least recently used.
+ *
+ * @return {Iterator}
+ */
+LRUCache.prototype.values = function() {
+  var i = 0,
+      l = this.size;
+
+  var pointer = this.head,
+      values = this.V,
+      forward = this.forward;
+
+  return new Iterator(function() {
+    if (i >= l)
+      return {done: true};
+
+    var value = values[pointer];
+
+    i++;
+
+    if (i < l)
+      pointer = forward[pointer];
+
+    return {
+      done: false,
+      value: value
+    };
+  });
+};
+
+/**
  * Method used to create an iterator over the cache's entries from most
@@ -195,4 +283,4 @@ * recently used to least recently used.
   var pointer = this.head,
-      keys = this.keys,
-      values = this.values,
+      keys = this.K,
+      values = this.V,
       forward = this.forward;
@@ -220,2 +308,8 @@
 /**
+ * Attaching the #.entries method to Symbol.iterator if possible.
+ */
+if (typeof Symbol !== 'undefined')
+  LRUCache.prototype[Symbol.iterator] = LRUCache.prototype.entries;
+
+/**
  * Convenience known methods.
@@ -246,8 +340,29 @@ */
  * @param  {Iterable} iterable - Target iterable.
+ * @param  {function} Keys     - Array class for storing keys.
+ * @param  {function} Values   - Array class for storing values.
+ * @param  {number}   capacity - Cache's capacity.
  * @return {LRUCache}
  */
-// LRUCache.from = function(iterable) {
+LRUCache.from = function(iterable, Keys, Values, capacity) {
+  if (arguments.length < 2) {
+    capacity = iterables.guessLength(iterable);
 
-// };
+    if (typeof capacity !== 'number')
+      throw new Error('mnemonist/lru-cache.from: could not guess iterable length. Please provide desired capacity as last argument.');
+  }
+  else if (arguments.length === 2) {
+    capacity = Keys;
+    Keys = null;
+    Values = null;
+  }
 
+  var cache = new LRUCache(Keys, Values, capacity);
+
+  forEach(iterable, function(value, key) {
+    cache.set(key, value);
+  });
+
+  return cache;
+};
+
 /**
@@ -254,0 +369,0 @@ * Exporting.

package.json

 {
   "name": "mnemonist",
-  "version": "0.24.0",
+  "version": "0.25.0",
   "description": "Curated collection of data structures for the JavaScript language.",
@@ -29,2 +29,3 @@ "scripts": {
     "burkhard-keller tree",
+    "cache",
     "circular buffer",
@@ -42,2 +43,4 @@ "counter",
     "linked list",
+    "lru",
+    "lru cache",
     "multimap",
@@ -44,0 +47,0 @@ "multiset",

README.md

@@ -30,2 +30,3 @@ [![Build Status](https://travis-ci.org/Yomguithereal/mnemonist.svg)](https://travis-ci.org/Yomguithereal/mnemonist)
 * [Linked List](https://yomguithereal.github.io/mnemonist/linked-list)
+* [LRUCache](https://yomguithereal.github.io/mnemonist/lru-cache), [LRUMap](https://yomguithereal.github.io/mnemonist/lru-map)
 * [MultiMap](https://yomguithereal.github.io/mnemonist/multi-map)
@@ -32,0 +33,0 @@ * [MultiSet](https://yomguithereal.github.io/mnemonist/multi-set)

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

284355

increased by3.58%

Number of package files

82

increased by3.8%

Lines of code

10312

increased by3.27%

Number of lines in readme file

108

increased by0.93%

No dependency changes