mnemonist - npm Package Compare versions

Comparing version 0.21.0 to 0.22.0

bi-map.js

@@ -7,3 +7,3 @@ /**
  */
-var iterate = require('./utils/iterate.js');
+var iterate = require('./utils/iterables.js').iterate;
 
@@ -10,0 +10,0 @@ /**

bit-set.d.ts

@@ -28,3 +28,3 @@ /**
   inspect(): any;
-  toJSON(): Uint32Array;
+  toJSON(): Array<number>;
 }

bit-set.js

@@ -353,3 +353,3 @@ /**
 BitSet.prototype.toJSON = function() {
-  return this.array;
+  return Array.from(this.array);
 };
@@ -356,0 +356,0 @@

bit-vector.d.ts

@@ -41,3 +41,3 @@ /**
   inspect(): any;
-  toJSON(): Uint32Array;
+  toJSON(): Array<number>;
 }

bit-vector.js

@@ -527,3 +527,3 @@ /**
 BitVector.prototype.toJSON = function() {
-  return this.array;
+  return Array.from(this.array.slice(0, (this.length >> 5) + 1));
 };
@@ -530,0 +530,0 @@

bk-tree.js

@@ -16,3 +16,3 @@ /* eslint no-constant-condition: 0 */
  */
-var iterate = require('./utils/iterate.js');
+var iterate = require('./utils/iterables.js').iterate;
 
@@ -19,0 +19,0 @@ /**

bloom-filter.js

@@ -8,3 +8,3 @@ /**
 var murmurhash3 = require('./utils/murmurhash3.js'),
-    iterate = require('./utils/iterate.js');
+    iterate = require('./utils/iterables.js').iterate;
 
@@ -11,0 +11,0 @@ /**

CHANGELOG.md

 # Changelog
 
+## 0.22.0
+
+* Adding `FuzzyMultiMap.dimension`.
+* Adding `#.consume` to `Heap`.
+* Adding `#.replace` to `Heap`.
+* Adding `#.pushpop` to `Heap`.
+* Improving `BitSet` and `BitVector` `#.toJSON`.
+* Improving `FiniteStack.from` & `CircularBuffer.from` performance when handling arrays.
+* `Heap.from` is now linear time.
+* Refactoring `Heap` inner logic.
+* Fixing `CircularBuffer`'s `#.unshift` to `#.shift`.
+* Fixing `SparseSet.delete` return consistency.
+
 ## 0.21.0
@@ -4,0 +17,0 @@

circular-buffer.d.ts

@@ -20,3 +20,3 @@ /**
   pop(): T | undefined;
-  unshift(): T | undefined;
+  shift(): T | undefined;
   peekFirst(): T | undefined;
@@ -23,0 +23,0 @@ peekLast(): T | undefined;

circular-buffer.js

@@ -7,3 +7,3 @@ /**
  */
-var iterate = require('./utils/iterate.js'),
+var iterables = require('./utils/iterables.js'),
     Iterator = require('obliterator/iterator');
@@ -72,7 +72,7 @@
 /**
- * Method used to unshift the buffer.
+ * Method used to shift the buffer.
  *
- * @return {any} - Returns the unshifted item.
+ * @return {any} - Returns the shifted item.
  */
-CircularBuffer.prototype.unshift = function() {
+CircularBuffer.prototype.shift = function() {
   if (this.size === 0)
@@ -288,7 +288,6 @@ return;
  */
-// TODO: can optimize if iterable is array-like
 CircularBuffer.from = function(iterable, ArrayClass, capacity) {
 
   if (arguments.length < 3) {
-    capacity = iterate.guessLength(iterable);
+    capacity = iterables.guessLength(iterable);
 
@@ -301,3 +300,14 @@ if (typeof capacity !== 'number')
 
-  iterate(iterable, function(value) {
+  if (iterables.isArrayLike(iterable)) {
+    var i, l;
+
+    for (i = 0, l = iterable.length; i < l; i++)
+      buffer.items[i] = iterable[i];
+
+    buffer.size = l;
+
+    return buffer;
+  }
+
+  iterables.iterate(iterable, function(value) {
     buffer.push(value);
@@ -304,0 +314,0 @@ });

fibonacci-heap.js

@@ -9,3 +9,3 @@ /* eslint no-constant-condition: 0 */
 var comparators = require('./utils/comparators.js'),
-    iterate = require('./utils/iterate.js');
+    iterate = require('./utils/iterables.js').iterate;
 
@@ -12,0 +12,0 @@ var DEFAULT_COMPARATOR = comparators.DEFAULT_COMPARATOR,

finite-stack.js

@@ -15,3 +15,3 @@ /**
 var Iterator = require('obliterator/iterator'),
-    iterate = require('./utils/iterate.js');
+    iterables = require('./utils/iterables.js');
 
@@ -208,7 +208,6 @@ /**
  */
-// TODO: can optimize if iterable is array-like
 FiniteStack.from = function(iterable, ArrayClass, capacity) {
 
   if (arguments.length < 3) {
-    capacity = iterate.guessLength(iterable);
+    capacity = iterables.guessLength(iterable);
 
@@ -221,3 +220,14 @@ if (typeof capacity !== 'number')
 
-  iterate(iterable, function(value) {
+  if (iterables.isArrayLike(iterable)) {
+    var i, l;
+
+    for (i = 0, l = iterable.length; i < l; i++)
+      stack.items[i] = iterable[i];
+
+    stack.size = l;
+
+    return stack;
+  }
+
+  iterables.iterate(iterable, function(value) {
     stack.push(value);
@@ -224,0 +234,0 @@ });

fuzzy-map.js

@@ -9,3 +9,3 @@ /**
  */
-var iterate = require('./utils/iterate.js');
+var iterate = require('./utils/iterables.js').iterate;
 
@@ -12,0 +12,0 @@ var identity = function(x) {

fuzzy-multi-map.d.ts

@@ -12,2 +12,3 @@ /**
   // Members
+  dimension: number;
   size: number;
@@ -14,0 +15,0 @@

fuzzy-multi-map.js

@@ -8,3 +8,3 @@ /**
 var MultiMap = require('./multi-map.js'),
-    iterate = require('./utils/iterate.js');
+    iterate = require('./utils/iterables.js').iterate;
 
@@ -57,2 +57,3 @@ var identity = function(x) {
   this.size = 0;
+  this.dimension = 0;
 };
@@ -71,2 +72,3 @@
   this.size = this.items.size;
+  this.dimension = this.items.dimension;
 
@@ -88,2 +90,3 @@ return this;
   this.size = this.items.size;
+  this.dimension = this.items.dimension;
 
@@ -90,0 +93,0 @@ return this;

hashed-array-tree.d.ts

@@ -32,2 +32,2 @@ /**
   inspect(): any;
-}
+}

heap.d.ts

@@ -20,3 +20,6 @@ /**
   pop(): T | undefined;
+  replace(): T | undefined;
+  pushpop(): T | undefined;
   toArray(): Array<T>;
+  consume(): Array<T>;
   inspect(): any;
@@ -44,3 +47,6 @@
   pop(): T | undefined;
+  replace(): T | undefined;
+  pushpop(): T | undefined;
   toArray(): Array<T>;
+  consume(): Array<T>;
   inspect(): any;
@@ -62,4 +68,7 @@ }
   pop(): T | undefined;
+  replace(): T | undefined;
+  pushpop(): T | undefined;
   toArray(): Array<T>;
+  consume(): Array<T>;
   inspect(): any;
-}
+}

heap.js

@@ -8,3 +8,3 @@ /**
 var comparators = require('./utils/comparators.js'),
-    iterate = require('./utils/iterate.js');
+    iterables = require('./utils/iterables.js');
 
@@ -15,98 +15,202 @@ var DEFAULT_COMPARATOR = comparators.DEFAULT_COMPARATOR,
 /**
- * Binary Minimum Heap.
+ * Heap helper functions.
+ */
+
+/**
+ * Function used to sift down.
  *
- * @constructor
+ * @param {function} compare    - Comparison function.
+ * @param {array}    heap       - Array storing the heap's data.
+ * @param {number}   startIndex - Starting index.
+ * @param {number}   i          - Index.
  */
-function Heap(comparator) {
-  this.clear();
-  this.comparator = comparator || DEFAULT_COMPARATOR;
+function siftDown(compare, heap, startIndex, i) {
+  var item = heap[i],
+      parentIndex,
+      parent;
 
-  if (typeof this.comparator !== 'function')
-    throw new Error('mnemonist/Heap.constructor: given comparator should be a function.');
+  while (i > startIndex) {
+    parentIndex = (i - 1) >> 1;
+    parent = heap[parentIndex];
+
+    if (compare(item, parent) < 0) {
+      heap[i] = parent;
+      i = parentIndex;
+      continue;
+    }
+
+    break;
+  }
+
+  heap[i] = item;
 }
 
 /**
- * Method used to clear the heap.
+ * Function used to sift up.
  *
- * @return {undefined}
+ * @param {function} compare - Comparison function.
+ * @param {array}    heap    - Array storing the heap's data.
+ * @param {number}   i       - Index.
  */
-Heap.prototype.clear = function() {
+function siftUp(compare, heap, i) {
+  var endIndex = heap.length,
+      startIndex = i,
+      item = heap[i],
+      childIndex = 2 * i + 1,
+      rightIndex;
 
-  // Properties
-  this.items = [];
-  this.size = 0;
-};
+  while (childIndex < endIndex) {
+    rightIndex = childIndex + 1;
 
+    if (
+      rightIndex < endIndex &&
+      compare(heap[childIndex], heap[rightIndex]) >= 0
+    ) {
+      childIndex = rightIndex;
+    }
+
+    heap[i] = heap[childIndex];
+    i = childIndex;
+    childIndex = 2 * i + 1;
+  }
+
+  heap[i] = item;
+  siftDown(compare, heap, startIndex, i);
+}
+
 /**
- * Function used to bubble up.
+ * Function used to push an item into a heap represented by a raw array.
  *
- * @param {function} compare - Comparator function.
- * @param {array}    data    - Data to edit.
- * @param {number}   index   - Target index.
+ * @param {function} compare - Comparison function.
+ * @param {array}    heap    - Array storing the heap's data.
+ * @param {any}      item    - Item to push.
  */
-function bubbleUp(compare, items, index) {
-  // Item needing to be moved
-  var item = items[index],
-      parentIndex = ((index - 1) / 2) | 0;
+function push(compare, heap, item) {
+  heap.push(item);
+  siftDown(compare, heap, 0, heap.length - 1);
+}
 
-  // Iterating
-  while (index > 0 && compare(items[parentIndex], item) > 0) {
-    items[index] = items[parentIndex];
-    items[parentIndex] = item;
-    index = parentIndex;
-    parentIndex = ((index - 1) / 2) | 0;
+/**
+ * Function used to pop an item from a heap represented by a raw array.
+ *
+ * @param  {function} compare - Comparison function.
+ * @param  {array}    heap    - Array storing the heap's data.
+ * @return {any}
+ */
+function pop(compare, heap) {
+  var lastItem = heap.pop();
+
+  if (heap.length !== 0) {
+    var item = heap[0];
+    heap[0] = lastItem;
+    siftUp(compare, heap, 0);
+
+    return item;
   }
+
+  return lastItem;
 }
 
 /**
- * Function used to sink down.
+ * Function used to pop the heap then push a new value into it, thus "replacing"
+ * it.
  *
- * @param {function} compare - Comparator function.
- * @param {array}    data    - Data to edit.
- * @param {number}   index   - Target index.
+ * @param  {function} compare - Comparison function.
+ * @param  {array}    heap    - Array storing the heap's data.
+ * @param  {any}      item    - The item to push.
+ * @return {any}
  */
-function sinkDown(compare, items, index) {
-  var size = items.length,
-      item = items[index],
-      left = 2 * index + 1,
-      right = 2 * index + 2,
-      min;
+function replace(compare, heap, item) {
+  if (heap.length === 0)
+    throw new Error('mnemonist/heap.replace: cannot pop an empty heap.');
 
-  if (right >= size) {
-    if (left >= size)
-      min = -1;
-    else
-      min = left;
-  }
-  else if (compare(items[left], items[right]) <= 0) {
-    min = left;
-  }
-  else {
-    min = right;
-  }
+  var popped = heap[0];
+  heap[0] = item;
+  siftUp(compare, heap, 0);
 
-  while (min >= 0 && compare(items[index], items[min]) > 0) {
-    items[index] = items[min];
-    items[min] = item;
-    index = min;
+  return popped;
+}
 
-    left = 2 * index + 1;
-    right = 2 * index + 2;
+/**
+ * Function used to push an item in the heap then pop the heap and return the
+ * popped value.
+ *
+ * @param  {function} compare - Comparison function.
+ * @param  {array}    heap    - Array storing the heap's data.
+ * @param  {any}      item    - The item to push.
+ * @return {any}
+ */
+function pushpop(compare, heap, item) {
+  var tmp;
 
-    if (right >= size) {
-      if (left >= size)
-        min = -1;
-      else
-        min = left;
-    }
-    else if (compare(items[left], items[right]) <= 0) {
-      min = left;
-    }
-    else {
-      min = right;
-    }
+  if (heap.length !== 0 && compare(heap[0], item) < 0) {
+    tmp = heap[0];
+    heap[0] = item;
+    item = tmp;
+    siftUp(compare, heap, 0);
   }
+
+  return item;
 }
 
 /**
+ * Converts and array into an abstract heap in linear time.
+ *
+ * @param {function} compare - Comparison function.
+ * @param {array}    array   - Target array.
+ */
+function heapify(compare, array) {
+  var n = array.length,
+      l = n >> 1,
+      i = l;
+
+  while (--i >= 0)
+    siftUp(compare, array, i);
+}
+
+/**
+ * Fully consumes the given heap.
+ *
+ * @param  {function} compare - Comparison function.
+ * @param  {array}    heap    - Array storing the heap's data.
+ * @return {array}
+ */
+function consume(compare, heap) {
+  var l = heap.length,
+      i = 0;
+
+  var array = new Array(heap.length);
+
+  while (i < l)
+    array[i++] = pop(compare, heap);
+
+  return array;
+}
+
+/**
+ * Binary Minimum Heap.
+ *
+ * @constructor
+ */
+function Heap(comparator) {
+  this.clear();
+  this.comparator = comparator || DEFAULT_COMPARATOR;
+
+  if (typeof this.comparator !== 'function')
+    throw new Error('mnemonist/Heap.constructor: given comparator should be a function.');
+}
+
+/**
+ * Method used to clear the heap.
+ *
+ * @return {undefined}
+ */
+Heap.prototype.clear = function() {
+
+  // Properties
+  this.items = [];
+  this.size = 0;
+};
+
+/**
  * Method used to push an item into the heap.
@@ -118,4 +222,3 @@ *
 Heap.prototype.push = function(item) {
-  this.items.push(item);
-  bubbleUp(this.comparator, this.items, this.size);
+  push(this.comparator, this.items, item);
   return ++this.size;
@@ -139,16 +242,37 @@ };
 Heap.prototype.pop = function() {
-  if (!this.size)
-    return undefined;
+  if (this.size !== 0)
+    this.size--;
 
-  var item = this.items[0],
-      last = this.items.pop();
+  return pop(this.comparator, this.items);
+};
 
-  this.size--;
+/**
+ * Method used to pop the heap, then push an item and return the popped
+ * item.
+ *
+ * @param  {any} item - Item to push into the heap.
+ * @return {any}
+ */
+Heap.prototype.replace = function(item) {
+  return replace(this.comparator, this.items, item);
+};
 
-  if (this.size) {
-    this.items[0] = last;
-    sinkDown(this.comparator, this.items, 0);
-  }
+/**
+ * Method used to push the heap, the pop it and return the pooped item.
+ *
+ * @param  {any} item - Item to push into the heap.
+ * @return {any}
+ */
+Heap.prototype.pushpop = function(item) {
+  return pushpop(this.comparator, this.items, item);
+};
 
-  return item;
+/**
+ * Method used to consume the heap fully and return its items as a sorted array.
+ *
+ * @return {array}
+ */
+Heap.prototype.consume = function() {
+  this.size = 0;
+  return consume(this.comparator, this.items);
 };
@@ -163,14 +287,3 @@
 Heap.prototype.toArray = function() {
-  var array = new Array(this.size);
-
-  var clone = new Heap(this.comparator);
-  clone.items = this.items.slice();
-  clone.size = this.size;
-
-  var i = 0;
-
-  while (clone.size)
-    array[i++] = clone.pop();
-
-  return array;
+  return consume(this.comparator, this.items.slice());
 };
@@ -203,3 +316,3 @@
   if (typeof this.comparator !== 'function')
-    throw new Error('mnemonist/Heap.constructor: given comparator should be a function.');
+    throw new Error('mnemonist/MaxHeap.constructor: given comparator should be a function.');
 
@@ -222,6 +335,14 @@ this.comparator = reverseComparator(this.comparator);
 
-  iterate(iterable, function(value) {
-    heap.push(value);
-  });
+  var items;
 
+  // If iterable is an array, we can be clever about it
+  if (iterables.isArrayLike(iterable))
+    items = iterable.slice();
+  else
+    items = iterables.toArray(iterable);
+
+  heapify(heap.comparator, items);
+  heap.items = items;
+  heap.size = items.length;
+
   return heap;
@@ -233,6 +354,14 @@ };
 
-  iterate(iterable, function(value) {
-    heap.push(value);
-  });
+  var items;
 
+  // If iterable is an array, we can be clever about it
+  if (iterables.isArrayLike(iterable))
+    items = iterable.slice();
+  else
+    items = iterables.toArray(iterable);
+
+  heapify(heap.comparator, items);
+  heap.items = items;
+  heap.size = items.length;
+
   return heap;
@@ -244,4 +373,14 @@ };
  */
+Heap.siftUp = siftUp;
+Heap.siftDown = siftDown;
+Heap.push = push;
+Heap.pop = pop;
+Heap.replace = replace;
+Heap.pushpop = pushpop;
+Heap.heapify = heapify;
+Heap.consume = consume;
+
 Heap.MinHeap = Heap;
 Heap.MaxHeap = MaxHeap;
+
 module.exports = Heap;

incremental-map.js

@@ -9,3 +9,3 @@ /**
  */
-var iterate = require('./utils/iterate.js');
+var iterate = require('./utils/iterables.js').iterate;
 
@@ -12,0 +12,0 @@ // TODO: maybe reverse iterators, since value is key etc.

inverted-index.js

@@ -8,3 +8,3 @@ /**
 var Iterator = require('obliterator/iterator'),
-    iterate = require('./utils/iterate.js'),
+    iterate = require('./utils/iterables.js').iterate,
     helpers = require('./utils/merge.js');
@@ -11,0 +11,0 @@

linked-list.js

@@ -9,3 +9,3 @@ /**
 var Iterator = require('obliterator/iterator'),
-    iterate = require('./utils/iterate.js');
+    iterate = require('./utils/iterables.js').iterate;
 
@@ -12,0 +12,0 @@ /**

multi-map.js

@@ -8,3 +8,3 @@ /**
 var Iterator = require('obliterator/iterator'),
-    iterate = require('./utils/iterate.js');
+    iterate = require('./utils/iterables.js').iterate;
 
@@ -11,0 +11,0 @@ /**

multi-set.js

@@ -8,3 +8,3 @@ /**
 var Iterator = require('obliterator/iterator'),
-    iterate = require('./utils/iterate.js');
+    iterate = require('./utils/iterables.js').iterate;
 
@@ -11,0 +11,0 @@ // TODO: helper functions: union, intersection, sum, difference, subtract

package.json

 {
   "name": "mnemonist",
-  "version": "0.21.0",
+  "version": "0.22.0",
   "description": "Curated collection of data structures for the JavaScript language.",
@@ -64,3 +64,3 @@ "scripts": {
   "dependencies": {
-    "obliterator": "^1.2.1"
+    "obliterator": "^1.3.0"
   },
@@ -70,7 +70,7 @@ "devDependencies": {
     "damerau-levenshtein": "^1.0.3",
-    "eslint": "^4.19.0",
+    "eslint": "^4.19.1",
     "leven": "^2.0.0",
     "lodash": "^4.17.5",
     "matcha": "^0.7.0",
-    "mocha": "^5.0.4",
+    "mocha": "^5.0.5",
     "pandemonium": "^1.2.1",
@@ -77,0 +77,0 @@ "seedrandom": "^2.4.3",

queue.js

@@ -9,3 +9,3 @@ /**
 var Iterator = require('obliterator/iterator'),
-    iterate = require('./utils/iterate.js');
+    iterate = require('./utils/iterables.js').iterate;
 
@@ -12,0 +12,0 @@ /**

sparse-set.d.ts

@@ -17,3 +17,3 @@ /**
   add(value: number): this;
-  delete(value: number): this | undefined;
+  delete(value: number): boolean;
   forEach(callback: (value: number, key: number, set: this) => void, scope?: any): void;
@@ -23,2 +23,2 @@ values(): Iterator<number>;
   inspect(): any;
-}
+}

sparse-set.js

@@ -73,7 +73,7 @@ /**
  * @param  {number} member - Member to delete.
- * @return {SparseSet}
+ * @return {boolean}
  */
 SparseSet.prototype.delete = function(member) {
   if (!this.has(member))
-    return;
+    return false;
 
@@ -85,3 +85,3 @@ var index = this.dense[this.size - 1];
 
-  return this;
+  return true;
 };
@@ -88,0 +88,0 @@

stack.js

@@ -9,3 +9,3 @@ /**
 var Iterator = require('obliterator/iterator'),
-    iterate = require('./utils/iterate.js');
+    iterate = require('./utils/iterables.js').iterate;
 
@@ -12,0 +12,0 @@ /**

static-interval-tree.js

@@ -19,3 +19,3 @@ /*
  */
-var iterate = require('./utils/iterate.js'),
+var iterables = require('./utils/iterables.js'),
     typed = require('./utils/typed-arrays.js');
@@ -376,3 +376,3 @@
 StaticIntervalTree.from = function(iterable, getters) {
-  if (iterate.isArrayLike(iterable))
+  if (iterables.isArrayLike(iterable))
     return new StaticIntervalTree(iterable, getters);
@@ -379,0 +379,0 @@

symspell.js

@@ -17,3 +17,3 @@ /* eslint no-loop-func: 0 */
  */
-var iterate = require('./utils/iterate.js');
+var iterate = require('./utils/iterables.js').iterate;
 
@@ -20,0 +20,0 @@ /**

trie-map.js

@@ -13,3 +13,3 @@ /**
  */
-var iterate = require('./utils/iterate.js'),
+var iterate = require('./utils/iterables.js').iterate,
     Iterator = require('obliterator/iterator');
@@ -16,0 +16,0 @@

trie.js

@@ -13,3 +13,3 @@ /**
  */
-var iterate = require('./utils/iterate.js'),
+var iterate = require('./utils/iterables.js').iterate,
     TrieMap = require('./trie-map.js');
@@ -16,0 +16,0 @@

utils/merge.js

@@ -12,3 +12,3 @@ /* eslint no-constant-condition: 0 */
 var typed = require('./typed-arrays.js'),
-    isArrayLike = require('./iterate.js').isArrayLike,
+    isArrayLike = require('./iterables.js').isArrayLike,
     binarySearch = require('./binary-search.js'),
@@ -15,0 +15,0 @@ FibonacciHeap = require('../fibonacci-heap.js');

vector.js

@@ -11,3 +11,3 @@ /**
 var Iterator = require('obliterator/iterator'),
-    iterate = require('./utils/iterate.js'),
+    iterables = require('./utils/iterables.js'),
     typed = require('./utils/typed-arrays.js');
@@ -321,3 +321,3 @@
     // Attempting to guess the needed capacity
-    capacity = iterate.guessLength(iterable);
+    capacity = iterables.guessLength(iterable);
 
@@ -330,3 +330,3 @@ if (typeof capacity !== 'number')
 
-  iterate(iterable, function(value) {
+  iterables.iterate(iterable, function(value) {
     vector.push(value);
@@ -333,0 +333,0 @@ });

vp-tree.js

@@ -15,3 +15,3 @@ /**
  */
-var iterate = require('./utils/iterate.js'),
+var iterables = require('./utils/iterables.js'),
     Heap = require('./heap.js');
@@ -161,3 +161,3 @@
 
-  iterate(items, function(value) {
+  iterables.iterate(items, function(value) {
     self.items.push(value);
@@ -164,0 +164,0 @@ indexes.push(i++);

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

252742

increased by2.07%

Lines of code

9250

increased by1.78%

Dependency changes

• Updatedobliterator@^1.3.0