mnemonist - npm Package Compare versions

Comparing version 0.16.0 to 0.17.0

bit-set.js

@@ -10,2 +10,4 @@ /**
  *   - (i & 0x0000001f) is the same as (i % 32)
+ *   - I could use a Float64Array to store more in less blocks but I would lose
+ *     the benefits of byte comparison to keep track of size without popcounts.
  */
@@ -49,14 +51,14 @@ var Iterator = require('obliterator/iterator'),
       pos = index & 0x0000001f,
-      oldByte = this.array[byteIndex],
-      newByte;
+      oldBytes = this.array[byteIndex],
+      newBytes;
 
-  if (value === 0)
-    newByte = this.array[byteIndex] &= ~(1 << pos);
+  if (value === 0 || value === false)
+    newBytes = this.array[byteIndex] &= ~(1 << pos);
   else
-    newByte = this.array[byteIndex] |= (1 << pos);
+    newBytes = this.array[byteIndex] |= (1 << pos);
 
   // Updating size
-  if (newByte > oldByte)
+  if (newBytes > oldBytes)
     this.size++;
-  else if (newByte < oldByte)
+  else if (newBytes < oldBytes)
     this.size--;
@@ -76,9 +78,9 @@
       pos = index & 0x0000001f,
-      oldByte = this.array[byteIndex],
-      newByte;
+      oldBytes = this.array[byteIndex],
+      newBytes;
 
-  newByte = this.array[byteIndex] &= ~(1 << pos);
+  newBytes = this.array[byteIndex] &= ~(1 << pos);
 
   // Updating size
-  if (newByte < oldByte)
+  if (newBytes < oldBytes)
     this.size--;
@@ -98,10 +100,10 @@
       pos = index & 0x0000001f,
-      oldByte = this.array[byteIndex];
+      oldBytes = this.array[byteIndex];
 
-  var newByte = this.array[byteIndex] ^= (1 << pos);
+  var newBytes = this.array[byteIndex] ^= (1 << pos);
 
   // Updating size
-  if (newByte > oldByte)
+  if (newBytes > oldBytes)
     this.size++;
-  else if (newByte < oldByte)
+  else if (newBytes < oldBytes)
     this.size--;
@@ -108,0 +110,0 @@

CHANGELOG.md

 # Changelog
 
+## 0.17.0
+
+* Adding `HashedArrayTree`.
+* Adding `BitVector`.
+* Adding `#.frequency` to `MultiSet`.
+* Adding `#.grow` to `DynamicArray`.
+* Adding `#.reallocate` to `DynamicArray`.
+* Adding `#.resize` to `DynamicArray`.
+* Fixing several `MultiSet` issues.
+* Renaming `DynamicArray` to `Vector`.
+* Renaming the `DynamicArray.initialLength` option to `initialCapacity`.
+* Renaming `DynamicArray.allocated` to `capacity`.
+* Optimizing `MultiSet` performance.
+* Optimizing `SparseSet` memory consumption.
+
 ## 0.16.0
@@ -4,0 +19,0 @@

hashed-array-tree.js

@@ -9,7 +9,2 @@ /**
 
-// TODO: initial size
-// TODO: set should adjust size
-// TODO: inspect
-// TODO: docs
-
 /**
@@ -32,13 +27,16 @@ * Defaults.
  * @param {function}      ArrayClass           - An array constructor.
- * @param {number|object} initialSizeOrOptions - Self-explanatory.
+ * @param {number|object} initialCapacityOrOptions - Self-explanatory.
  */
-function HashedArrayTree(ArrayClass, initialSizeOrOptions) {
+function HashedArrayTree(ArrayClass, initialCapacityOrOptions) {
+  if (arguments.length < 1)
+    throw new Error('mnemonist/hashed-array)-tree: expecting at least a byte array constructor.');
 
-  /* eslint no-unused-vars: 0 */
-  var initialSize = initialSizeOrOptions || 0,
-      blockSize = DEFAULT_BLOCK_SIZE;
+  var initialCapacity = initialCapacityOrOptions || 0,
+      blockSize = DEFAULT_BLOCK_SIZE,
+      initialLength = 0;
 
-  if (typeof initialSizeOrOptions === 'object') {
-    initialSize = initialSizeOrOptions.initialSize || 0;
-    blockSize = initialSizeOrOptions.blockSize || DEFAULT_BLOCK_SIZE;
+  if (typeof initialCapacityOrOptions === 'object') {
+    initialCapacity = initialCapacityOrOptions.initialCapacity || 0;
+    initialLength = initialCapacityOrOptions.initialLength || 0;
+    blockSize = initialCapacityOrOptions.blockSize || DEFAULT_BLOCK_SIZE;
   }
@@ -49,8 +47,17 @@
 
+  var capacity = Math.max(initialLength, initialCapacity),
+      initialBlocks = Math.ceil(capacity / blockSize);
+
   this.ArrayClass = ArrayClass;
-  this.length = 0;
-  this.capacity = 0;
+  this.length = initialLength;
+  this.capacity = initialBlocks * blockSize;
   this.blockSize = blockSize;
-  this.blockLg2 = Math.log2(blockSize);
-  this.blocks = new Array();
+  this.offsetMask = blockSize - 1;
+  this.blockMask = Math.log2(blockSize);
+
+  // Allocating initial blocks
+  this.blocks = new Array(initialBlocks);
+
+  for (var i = 0; i < initialBlocks; i++)
+    this.blocks[i] = new this.ArrayClass(this.blockSize);
 }
@@ -66,5 +73,10 @@
 HashedArrayTree.prototype.set = function(index, value) {
-  var block = index >> this.blockLg2,
-      i = index & (this.blockSize - 1);
 
+  // Out of bounds?
+  if (this.length < index)
+    throw new Error('HashedArrayTree(' + this.ArrayClass.name + ').set: index out of bounds.');
+
+  var block = index >> this.blockMask,
+      i = index & this.offsetMask;
+
   this.blocks[block][i] = value;
@@ -85,4 +97,4 @@
 
-  var block = index >> this.blockLg2,
-      i = index & (this.blockSize - 1);
+  var block = index >> this.blockMask,
+      i = index & this.offsetMask;
 
@@ -95,8 +107,17 @@ return this.blocks[block][i];
  *
+ * @param  {number}          capacity - Optional capacity to accomodate.
  * @return {HashedArrayTree}
  */
-HashedArrayTree.prototype.grow = function() {
-  this.blocks.push(new this.ArrayClass(this.blockSize));
-  this.capacity += this.blockSize;
+HashedArrayTree.prototype.grow = function(capacity) {
+  if (typeof capacity !== 'number')
+    capacity = this.capacity + this.blockSize;
 
+  if (this.capacity >= capacity)
+    return this;
+
+  while (this.capacity < capacity) {
+    this.blocks.push(new this.ArrayClass(this.blockSize));
+    this.capacity += this.blockSize;
+  }
+
   return this;
@@ -106,2 +127,23 @@ };
 /**
+ * Method used to resize the array. Won't deallocate.
+ *
+ * @param  {number}       length - Target length.
+ * @return {HashedArrayTree}
+ */
+HashedArrayTree.prototype.resize = function(length) {
+  if (length === this.length)
+    return this;
+
+  if (length < this.length) {
+    this.length = length;
+    return this;
+  }
+
+  this.length = length;
+  this.grow(length);
+
+  return this;
+};
+
+/**
  * Method used to push a value into the array.
@@ -113,3 +155,3 @@ *
 HashedArrayTree.prototype.push = function(value) {
-  if (this.length >= this.capacity)
+  if (this.capacity === this.length)
     this.grow();
@@ -119,4 +161,4 @@
 
-  var block = index >> this.blockLg2,
-      i = index & (this.blockSize - 1);
+  var block = index >> this.blockMask,
+      i = index & this.offsetMask;
 
@@ -134,5 +176,8 @@ this.blocks[block][i] = value;
 HashedArrayTree.prototype.pop = function() {
+  if (this.length === 0)
+    return;
+
   var lastBlock = this.blocks[this.blocks.length - 1];
 
-  var i = (--this.length) & (this.blockSize - 1);
+  var i = (--this.length) & this.offsetMask;
 
@@ -146,14 +191,22 @@ return lastBlock[i];
 HashedArrayTree.prototype.inspect = function() {
-  return this;
-  // var proxy = this.array.slice(0, this.length);
+  var proxy = new this.ArrayClass(this.length),
+      block;
 
-  // proxy.type = this.ArrayClass.name;
+  for (var i = 0, l = this.length; i < l; i++) {
+    block = i >> this.blockMask;
+    proxy[i] = this.blocks[block][i & this.offsetMask];
+  }
 
-  // // Trick so that node displays the name of the constructor
-  // Object.defineProperty(proxy, 'constructor', {
-  //   value: HashedArrayTree,
-  //   enumerable: false
-  // });
+  proxy.type = this.ArrayClass.name;
+  proxy.items = this.length;
+  proxy.capacity = this.capacity;
+  proxy.blockSize = this.blockSize;
 
-  // return proxy;
+  // Trick so that node displays the name of the constructor
+  Object.defineProperty(proxy, 'constructor', {
+    value: HashedArrayTree,
+    enumerable: false
+  });
+
+  return proxy;
 };
@@ -160,0 +213,0 @@

index.js

@@ -15,6 +15,6 @@ /**
   BitSet: require('./bit-set.js'),
+  BitVector: require('./bit-vector.js'),
   BloomFilter: require('./bloom-filter.js'),
   BKTree: require('./bk-tree.js'),
   StaticDisjointSet: require('./static-disjoint-set.js'),
-  DynamicArray: require('./dynamic-array.js'),
   FibonacciHeap: FibonacciHeap,
@@ -25,2 +25,3 @@ MinFibonacciHeap: FibonacciHeap.MinFibonacciHeap,
   FuzzyMultiMap: require('./fuzzy-multi-map.js'),
+  HashedArrayTree: require('./hashed-array-tree.js'),
   Heap: Heap,
@@ -42,3 +43,4 @@ MinHeap: Heap.MinHeap,
   Trie: require('./trie.js'),
+  Vector: require('./vector.js'),
   VPTree: require('./vp-tree.js')
 };

multi-set.js

@@ -10,2 +10,4 @@ /**
 
+// TODO: helper functions: union, intersection, sum, difference, subtract
+
 /**
@@ -48,2 +50,8 @@ * MultiSet.
 MultiSet.prototype.add = function(item, count) {
+  if (count === 0)
+    return this;
+
+  if (count < 0)
+    return this.remove(item, -count);
+
   count = count || 1;
@@ -65,4 +73,42 @@
 
-MultiSet.prototype.set = MultiSet.prototype.add;
+/**
+ * Method used to set the multiplicity of an item in the set.
+ *
+ * @param  {any}    item  - Target item.
+ * @param  {number} count - Desired multiplicity.
+ * @return {MultiSet}
+ */
+MultiSet.prototype.set = function(item, count) {
+  var currentCount;
 
+  // Setting an item to 0 or to a negative number means deleting it from the set
+  if (count <= 0) {
+    currentCount = this.items.get(item);
+
+    if (typeof currentCount !== 'undefined') {
+      this.size -= currentCount;
+      this.dimension--;
+    }
+
+    this.items.delete(item);
+    return this;
+  }
+
+  count = count || 1;
+
+  currentCount = this.items.get(item);
+
+  if (typeof currentCount === 'number') {
+    this.items.set(item, currentCount + count);
+  }
+  else {
+    this.dimension++;
+    this.items.set(item, count);
+  }
+
+  this.size += count;
+
+  return this;
+};
+
 /**
@@ -85,4 +131,7 @@ * Method used to return whether the item exists in the set.
 MultiSet.prototype.delete = function(item) {
-  var count = this.multiplicity(item);
+  var count = this.items.get(item);
 
+  if (count === 0)
+    return false;
+
   this.size -= count;
@@ -92,3 +141,3 @@ this.dimension--;
 
-  return !!count;
+  return true;
 };
@@ -104,2 +153,8 @@
 MultiSet.prototype.remove = function(item, count) {
+  if (count === 0)
+    return;
+
+  if (count < 0)
+    return this.add(item, -count);
+
   count = count || 1;
@@ -110,3 +165,3 @@
 
-  if (!newCount) {
+  if (newCount === 0) {
     this.delete(item);
@@ -131,3 +186,3 @@ }
 MultiSet.prototype.edit = function(a, b) {
-  const am = this.multiplicity(a);
+  var am = this.multiplicity(a);
 
@@ -138,3 +193,3 @@ // If a does not exist in the set, we can stop right there
 
-  const bm = this.multiplicity(b);
+  var bm = this.multiplicity(b);
 
@@ -154,6 +209,27 @@ this.items.set(b, am + bm);
 MultiSet.prototype.multiplicity = function(item) {
-  return this.items.get(item) || 0;
+  var count = this.items.get(item);
+
+  if (typeof count === 'undefined')
+    return 0;
+
+  return count;
 };
+MultiSet.prototype.get = MultiSet.prototype.multiplicity;
 
 /**
+ * Method used to return the frequency of the given item in the set.
+ *
+ * @param  {any} item - Item to get.
+ * @return {number}
+ */
+MultiSet.prototype.frequency = function(item) {
+  if (this.size === 0)
+    return 0;
+
+  var count = this.multiplicity(item);
+
+  return count / this.size;
+};
+
+/**
  * Method used to iterate over the set's values.
@@ -160,0 +236,0 @@ *

package.json

 {
   "name": "mnemonist",
-  "version": "0.16.0",
+  "version": "0.17.0",
   "description": "Curated collection of data structures for the JavaScript language.",
@@ -28,2 +28,3 @@ "scripts": {
     "structures",
+    "hashed array tree",
     "heap",
@@ -47,3 +48,4 @@ "fibonacci heap",
     "vp tree",
-    "vantage point tree"
+    "vantage point tree",
+    "vector"
   ],
@@ -50,0 +52,0 @@ "author": {

README.md

@@ -25,14 +25,6 @@ [![Build Status](https://travis-ci.org/Yomguithereal/mnemonist.svg)](https://travis-ci.org/Yomguithereal/mnemonist)
 
-* [BiMap](https://yomguithereal.github.io/mnemonist/bi-map)
-* [BitSet](https://yomguithereal.github.io/mnemonist/bit-set)
-* [Bloom Filter](https://yomguithereal.github.io/mnemonist/bloom-filter)
-* [Burkhard-Keller Tree](https://yomguithereal.github.io/mnemonist/bk-tree)
-* [StaticDisjointSet](https://yomguithereal.github.io/mnemonist/static-disjoint-set)
-* [Dynamic Arrays](https://yomguithereal.github.io/mnemonist/dynamic-array)
+**Classics**
+
 * [Fibonacci Heap](https://yomguithereal.github.io/mnemonist/fibonacci-heap)
-* [Fuzzy Map](https://yomguithereal.github.io/mnemonist/fuzzy-map)
-* [Fuzzy MultiMap](https://yomguithereal.github.io/mnemonist/fuzzy-multi-map)
 * [Heap](https://yomguithereal.github.io/mnemonist/heap)
-* [IncrementalMap](https://yomguithereal.github.io/mnemonist/incremental-map)
-* [Inverted Index](https://yomguithereal.github.io/mnemonist/inverted-index)
 * [Linked List](https://yomguithereal.github.io/mnemonist/linked-list)
@@ -43,10 +35,39 @@ * [MultiMap](https://yomguithereal.github.io/mnemonist/multi-map)
 * [Set (helpers)](https://yomguithereal.github.io/mnemonist/set)
+* [Stack](https://yomguithereal.github.io/mnemonist/stack)
+* [Trie](https://yomguithereal.github.io/mnemonist/trie)
+
+**Low-level & structures for very specific use cases**
+
+* [Hashed Array Tree](https://yomguithereal.github.io/mnemonist/hashed-array-tree)
+* [StaticDisjointSet](https://yomguithereal.github.io/mnemonist/static-disjoint-set)
 * [SparseSet](https://yomguithereal.github.io/mnemonist/sparse-set)
-* [Stack](https://yomguithereal.github.io/mnemonist/stack)
 * [Suffix Array](https://yomguithereal.github.io/mnemonist/suffix-array)
 * [Generalized Suffix Array](https://yomguithereal.github.io/mnemonist/generalized-suffix-array)
+* [Vector](https://yomguithereal.github.io/mnemonist/vector)
+
+**Information retrieval & Natural language processing**
+
+* [Fuzzy Map](https://yomguithereal.github.io/mnemonist/fuzzy-map)
+* [Fuzzy MultiMap](https://yomguithereal.github.io/mnemonist/fuzzy-multi-map)
+* [Inverted Index](https://yomguithereal.github.io/mnemonist/inverted-index)
 * [SymSpell](https://yomguithereal.github.io/mnemonist/symspell)
-* [Trie](https://yomguithereal.github.io/mnemonist/trie)
+
+**Metric space indexation**
+
+* [Burkhard-Keller Tree](https://yomguithereal.github.io/mnemonist/bk-tree)
 * [Vantage Point Tree](https://yomguithereal.github.io/mnemonist/vp-tree)
 
+**Probabilistic & succinct data structures**
+
+* [BitSet](https://yomguithereal.github.io/mnemonist/bit-set)
+* [BitVector](https://yomguithereal.github.io/mnemonist/bit-vector)
+* [Bloom Filter](https://yomguithereal.github.io/mnemonist/bloom-filter)
+
+**Utility classes**
+
+* [BiMap](https://yomguithereal.github.io/mnemonist/bi-map)
+* [IncrementalMap](https://yomguithereal.github.io/mnemonist/incremental-map)
+
+---
+
 Note that this list does not include a `Graph` data structure, whose implementation is usually far too complex for the scope of this library.
@@ -53,0 +74,0 @@

sparse-set.js

@@ -5,7 +5,8 @@ /**
  *
- * JavaScript sparse set implemented on top of a Uint32Array.
+ * JavaScript sparse set implemented on top of byte arrays.
  *
  * [Reference]: https://research.swtch.com/sparse
  */
-var Iterator = require('obliterator/iterator');
+var Iterator = require('obliterator/iterator'),
+    getPointerArray = require('./utils/typed-arrays.js').getPointerArray;
 
@@ -19,7 +20,9 @@ /**
 
+  var ByteArray = getPointerArray(length);
+
   // Properties
   this.size = 0;
   this.length = length;
-  this.dense = new Uint32Array(length);
-  this.sparse = new Uint32Array(length);
+  this.dense = new ByteArray(length);
+  this.sparse = new ByteArray(length);
 }
@@ -26,0 +29,0 @@

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

161636

increased by5.79%

Lines of code

6033

increased by4.56%

Number of lines in readme file

97

increased by27.63%

No dependency changes