mnemonist - npm Package Compare versions

Comparing version 0.32.0 to 0.33.0

CHANGELOG.md

 # Changelog
 
+## 0.33.0
+
+* Adding `KDTree`.
+* Adding `set.intersectionSize`.
+* Adding `set.unionSize`.
+* Adding `set.jaccard`.
+* Adding `FixedReverseHeap.peek`.
+
 ## 0.32.0
@@ -4,0 +12,0 @@

fixed-reverse-heap.js

@@ -158,2 +158,11 @@ /**
 /**
+ * Method used to peek the worst item in the heap.
+ *
+ * @return {any}
+ */
+FixedReverseHeap.prototype.peek = function() {
+  return this.items[0];
+};
+
+/**
  * Method used to consume the heap fully and return its items as a sorted array.
@@ -160,0 +169,0 @@ *

index.d.ts

@@ -25,2 +25,3 @@ /**
 export {default as InvertedIndex} from './inverted-index';
+export {default as KDTree} from './kd-tree';
 export {default as LinkedList} from './linked-list';
@@ -27,0 +28,0 @@ export {default as LRUCache} from './lru-cache';

index.js

@@ -34,2 +34,3 @@ /**
   InvertedIndex: require('./inverted-index.js'),
+  KDTree: require('./kd-tree.js'),
   LinkedList: require('./linked-list.js'),
@@ -36,0 +37,0 @@ LRUCache: require('./lru-cache.js'),

multi-map.d.ts

@@ -5,4 +5,5 @@ /**
  */
-export default class MultiMap<K, V> implements Iterable<[K, V]> {
 
+interface MultiMap<K, V, C extends V[] | Set<V> = V[]> extends Iterable<[K, V]> {
+
   // Members
@@ -12,5 +13,2 @@ dimension: number;
 
-  // Constructor
-  constructor(Container?: ArrayConstructor | SetConstructor);
-
   // Methods
@@ -22,20 +20,31 @@ clear(): void;
   has(key: K): boolean;
-  get(key: K): Array<V> | Set<V> | undefined;
+  get(key: K): C | undefined;
   multiplicity(key: K): number;
   forEach(callback: (value: V, key: K, map: this) => void, scope?: any): void;
-  forEachAssociation(callback: (value: Array<V> | Set<V>, key: K, map: this) => void, scope?: any): void;
-  keys(): Iterator<K>;
-  values(): Iterator<V>;
-  entries(): Iterator<[K, V]>;
-  containers(): Iterator<Array<V> | Set<V>>;
-  associations(): Iterator<[K, Array<V> | Set<V>]>;
-  [Symbol.iterator](): Iterator<[K, V]>;
+  forEachAssociation(callback: (value: C, key: K, map: this) => void, scope?: any): void;
+  keys(): IterableIterator<K>;
+  values(): IterableIterator<V>;
+  entries(): IterableIterator<[K, V]>;
+  containers(): IterableIterator<C>;
+  associations(): IterableIterator<[K, C]>;
+  [Symbol.iterator](): IterableIterator<[K, V]>;
   inspect(): any;
   toJSON(): any;
+}
 
-  // Statics
-  static from<I, J>(
-    iterable: Iterable<[I, J]> | {[key: string]: J},
-    Container?: ArrayConstructor | SetConstructor
-  ): MultiMap<I, J>;
+interface MultiMapConstructor {
+  new <K, V>(container: SetConstructor): MultiMap<K, V, Set<V>>;
+  new <K, V>(container?: ArrayConstructor): MultiMap<K, V, V[]>;
+
+  from<K, V>(
+    iterable: Iterable<[K, V]> | {[key: string]: V},
+    Container: SetConstructor
+  ): MultiMap<K, V, Set<V>>;
+  from<K, V>(
+    iterable: Iterable<[K, V]> | {[key: string]: V},
+    Container?: ArrayConstructor
+  ): MultiMap<K, V, V[]>;
 }
+
+declare const MultiMap: MultiMapConstructor;
+export default MultiMap;

package.json

 {
   "name": "mnemonist",
-  "version": "0.32.0",
+  "version": "0.33.0",
   "description": "Curated collection of data structures for the JavaScript language.",
@@ -9,3 +9,3 @@ "scripts": {
     "test": "mocha",
-    "test:types": "tsc --lib es2015,dom --noEmit --noImplicitAny --noImplicitReturns ./test/types.ts"
+    "test:types": "tsc --target es2015 --noEmit --noImplicitAny --noImplicitReturns ./test/types.ts"
   },
@@ -43,2 +43,3 @@ "files": [
     "inverted index",
+    "kd tree",
     "linked list",
@@ -72,3 +73,3 @@ "lru",
   "dependencies": {
-    "obliterator": "^1.5.0"
+    "obliterator": "^1.6.1"
   },
@@ -78,11 +79,11 @@ "devDependencies": {
     "asciitree": "^1.0.2",
-    "damerau-levenshtein": "^1.0.5",
-    "eslint": "^6.7.2",
+    "damerau-levenshtein": "^1.0.6",
+    "eslint": "^6.8.0",
     "leven": "^3.1.0",
     "lodash": "^4.17.15",
     "matcha": "^0.7.0",
-    "mocha": "^6.2.2",
+    "mocha": "^7.1.0",
     "pandemonium": "^1.2.1",
     "seedrandom": "^3.0.5",
-    "typescript": "^3.7.3"
+    "typescript": "^3.8.2"
   },
@@ -89,0 +90,0 @@ "eslintConfig": {

passjoin-index.js

@@ -7,3 +7,3 @@ /**
  * to index strings for Levenshtein distance queries. It features a complexity
- * related to the Levenhstein query threshold k rather than the number of
+ * related to the Levenshtein query threshold k rather than the number of
  * strings to test (roughly O(k^3)).
@@ -29,2 +29,7 @@ *
 
+// TODO: leveraging BagDistance as an upper bound of Levenshtein
+// TODO: leverage n-grams recursive indexing
+// TODO: try the MultiArray as a memory backend
+// TODO: what about damerau levenshtein
+
 /**
@@ -403,4 +408,6 @@ * Helpers.
           // distance for tiny strings
-          // NOTE: we could also maintain a set of non-matching candidates
-          // but this is unlikely to be useful
+
+          // NOTE: maintaining a Set of rejected candidate is not really useful
+          // because it consumes more memory and because non-matches are
+          // less likely to be candidates agains
           if (
@@ -407,0 +414,0 @@ s <= k && l <= k ||

set.d.ts

@@ -14,2 +14,5 @@ /**
 export function intersect<T>(a: Set<T>, b: Set<T>): void;
-export function disjunct<T>(a: Set<T>, b: Set<T>): void;
+export function disjunct<T>(a: Set<T>, b: Set<T>): void;
+export function intersectionSize<T>(a: Set<T>, b:Set<T>): number;
+export function unionSize<T>(a: Set<T>, b:Set<T>): number;
+export function jaccard<T>(a: Set<T>, b:Set<T>): number;

set.js

@@ -8,2 +8,4 @@ /**
 
+// TODO: optimize versions for less variadicities
+
 /**
@@ -273,1 +275,65 @@ * Variadic function computing the intersection of multiple sets.
 };
+
+/**
+ * Function returning the size of the intersection of A & B.
+ *
+ * @param  {Set} A - First set.
+ * @param  {Set} B - Second set.
+ */
+exports.intersectionSize = function(A, B) {
+  var tmp;
+
+  // We need to know the smallest set
+  if (A.size > B.size) {
+    tmp = A;
+    A = B;
+    B = tmp;
+  }
+
+  if (A.size === 0)
+    return 0;
+
+  if (A === B)
+    return A.size;
+
+  var iterator = A.values(),
+      step;
+
+  var I = 0;
+
+  while ((step = iterator.next(), !step.done)) {
+    if (B.has(step.value))
+      I++;
+  }
+
+  return I;
+};
+
+/**
+ * Function returning the size of the union of A & B.
+ *
+ * @param  {Set} A - First set.
+ * @param  {Set} B - Second set.
+ */
+exports.unionSize = function(A, B) {
+  var I = exports.intersectionSize(A, B);
+
+  return A.size + B.size - I;
+};
+
+/**
+ * Function returning the Jaccard similarity between A & B.
+ *
+ * @param  {Set} A - First set.
+ * @param  {Set} B - Second set.
+ */
+exports.jaccard = function(A, B) {
+  var I = exports.intersectionSize(A, B);
+
+  if (I === 0)
+    return 0;
+
+  var U = A.size + B.size - I;
+
+  return I / U;
+};

utils/comparators.js

@@ -35,2 +35,41 @@ /**
 /**
+ * Function returning a tuple comparator.
+ */
+function createTupleComparator(size) {
+  if (size === 2) {
+    return function(a, b) {
+      if (a[0] < b[0])
+        return -1;
+
+      if (a[0] > b[0])
+        return 1;
+
+      if (a[1] < b[1])
+        return -1;
+
+      if (a[1] > b[1])
+        return 1;
+
+      return 0;
+    };
+  }
+
+  return function(a, b) {
+    var i = 0;
+
+    while (i < size) {
+      if (a[i] < b[i])
+        return -1;
+
+      if (a[i] > b[i])
+        return 1;
+
+      i++;
+    }
+
+    return 0;
+  };
+}
+
+/**
  * Exporting.
@@ -41,1 +80,2 @@ */
 exports.reverseComparator = reverseComparator;
+exports.createTupleComparator = createTupleComparator;

utils/typed-arrays.js

@@ -171,1 +171,18 @@ /**
 };
+
+/**
+ * Function used to initialize a byte array of indices.
+ *
+ * @param  {number}    length - Length of target.
+ * @return {ByteArray}
+ */
+exports.indices = function(length) {
+  var PointerArray = exports.getPointerArray(length);
+
+  var array = new PointerArray(length);
+
+  for (var i = 0; i < length; i++)
+    array[i] = i;
+
+  return array;
+};

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

345592

increased by3.96%

Number of package files

89

increased by2.3%

Lines of code

12390

increased by4.12%

Dependency changes

• Updatedobliterator@^1.6.1