mnemonist - npm Package Compare versions

Comparing version 0.22.0 to 0.23.0-beta1

CHANGELOG.md

 # Changelog
 
+## 0.23.0 (provisonal)
+
+* Adding `FixedReverseHeap`.
+* Adding `Heap.nsmallest` & `Heap.nlargest`.
+* Adding `#.top` to `MultiSet`.
+* Adding missing `Heap` types.
+* Renaming `FiniteStack` to `FixedStack`.
+
 ## 0.22.0
@@ -4,0 +12,0 @@

heap.d.ts

@@ -72,1 +72,14 @@ /**
 }
+
+// Static helpers
+export function push<T>(comparator: HeapComparator<T>, heap: Array<T>, item: T): void;
+export function pop<T>(comparator: HeapComparator<T>, heap: Array<T>): T;
+export function replace<T>(comparator: HeapComparator<T>, heap: Array<T>, item: T): T;
+export function pushpop<T>(comparator: HeapComparator<T>, heap: Array<T>, item: T): T;
+export function heapify<T>(comparator: HeapComparator<T>, array: Array<T>): void;
+export function consume<T>(comparator: HeapComparator<T>, heap: Array<T>): Array<T>;
+
+export function nsmallest<T>(n: number, comparator: HeapComparator<T>, values: Iterable<T>): Array<T>;
+export function nsmallest<T>(n: number, values: Iterable<T>): Array<T>;
+export function nlargest<T>(n: number, comparator: HeapComparator<T>, values: Iterable<T>): Array<T>;
+export function nlargest<T>(n: number, values: Iterable<T>): Array<T>;

heap.js

@@ -180,3 +180,3 @@ /**
 
-  var array = new Array(heap.length);
+  var array = new Array(l);
 
@@ -190,5 +190,196 @@ while (i < l)
 /**
+ * Function used to retrieve the n smallest items from the given iterable.
+ *
+ * @param {function} compare  - Comparison function.
+ * @param {number}   n        - Number of top items to retrieve.
+ * @param {any}      iterable - Arbitrary iterable.
+ * @param {array}
+ */
+function nsmallest(compare, n, iterable) {
+  if (arguments.length === 2) {
+    iterable = n;
+    n = compare;
+    compare = DEFAULT_COMPARATOR;
+  }
+
+  var reverseCompare = reverseComparator(compare);
+
+  var i, l, v;
+
+  var min = Infinity;
+
+  var result;
+
+  // If n is equal to 1, it's just a matter of find the minimum
+  if (n === 1) {
+    if (iterables.isArrayLike(iterable)) {
+      for (i = 0, l = iterable.length; i < l; i++) {
+        v = iterable[i];
+
+        if (v < min)
+          min = v;
+      }
+
+      result = new iterable.constructor(1);
+      result[0] = min;
+
+      return result;
+    }
+
+    iterables.iterate(iterable, function(value) {
+      if (value < min)
+        min = value;
+    });
+
+    return [min];
+  }
+
+  if (iterables.isArrayLike(iterable)) {
+
+    // If n > iterable length, we just clone and sort
+    if (n >= iterable.length)
+      return iterable.slice().sort(compare);
+
+    result = iterable.slice(0, n);
+    heapify(reverseCompare, result);
+
+    for (i = n, l = iterable.length; i < l; i++)
+      if (reverseCompare(iterable[i], result[0]) > 0)
+        replace(reverseCompare, result, iterable[i]);
+
+    // NOTE: if n is over some number, it becomes faster to consume the heap
+    return result.sort(compare);
+  }
+
+  // Correct for size
+  var size = iterables.guessLength(iterable);
+
+  if (size !== null && size < n)
+    n = size;
+
+  result = new Array(n);
+  i = 0;
+
+  iterables.iterate(iterable, function(value) {
+    if (i < n) {
+      result[i] = value;
+    }
+    else {
+      if (i === n)
+        heapify(reverseCompare, result);
+
+      if (reverseCompare(value, result[0]) > 0)
+        replace(reverseCompare, result, value);
+    }
+
+    i++;
+  });
+
+  if (result.length > i)
+    result.length = i;
+
+  // NOTE: if n is over some number, it becomes faster to consume the heap
+  return result.sort(compare);
+}
+
+/**
+ * Function used to retrieve the n largest items from the given iterable.
+ *
+ * @param {function} compare  - Comparison function.
+ * @param {number}   n        - Number of top items to retrieve.
+ * @param {any}      iterable - Arbitrary iterable.
+ * @param {array}
+ */
+function nlargest(compare, n, iterable) {
+  if (arguments.length === 2) {
+    iterable = n;
+    n = compare;
+    compare = DEFAULT_COMPARATOR;
+  }
+
+  var reverseCompare = reverseComparator(compare);
+
+  var i, l, v;
+
+  var max = -Infinity;
+
+  var result;
+
+  // If n is equal to 1, it's just a matter of find the maximum
+  if (n === 1) {
+    if (iterables.isArrayLike(iterable)) {
+      for (i = 0, l = iterable.length; i < l; i++) {
+        v = iterable[i];
+
+        if (v > max)
+          max = v;
+      }
+
+      result = new iterable.constructor(1);
+      result[0] = max;
+
+      return result;
+    }
+
+    iterables.iterate(iterable, function(value) {
+      if (value > max)
+        max = value;
+    });
+
+    return [max];
+  }
+
+  if (iterables.isArrayLike(iterable)) {
+
+    // If n > iterable length, we just clone and sort
+    if (n >= iterable.length)
+      return iterable.slice().sort(reverseCompare);
+
+    result = iterable.slice(0, n);
+    heapify(compare, result);
+
+    for (i = n, l = iterable.length; i < l; i++)
+      if (compare(iterable[i], result[0]) > 0)
+        replace(compare, result, iterable[i]);
+
+    // NOTE: if n is over some number, it becomes faster to consume the heap
+    return result.sort(reverseCompare);
+  }
+
+  // Correct for size
+  var size = iterables.guessLength(iterable);
+
+  if (size !== null && size < n)
+    n = size;
+
+  result = new Array(n);
+  i = 0;
+
+  iterables.iterate(iterable, function(value) {
+    if (i < n) {
+      result[i] = value;
+    }
+    else {
+      if (i === n)
+        heapify(compare, result);
+
+      if (compare(value, result[0]) > 0)
+        replace(compare, result, value);
+    }
+
+    i++;
+  });
+
+  if (result.length > i)
+    result.length = i;
+
+  // NOTE: if n is over some number, it becomes faster to consume the heap
+  return result.sort(reverseCompare);
+}
+
+/**
  * Binary Minimum Heap.
  *
  * @constructor
+ * @param {function} comparator - Comparator function to use.
  */
@@ -307,2 +498,3 @@ function Heap(comparator) {
  * @constructor
+ * @param {function} comparator - Comparator function to use.
  */
@@ -377,2 +569,5 @@ function MaxHeap(comparator) {
 
+Heap.nsmallest = nsmallest;
+Heap.nlargest = nlargest;
+
 Heap.MinHeap = Heap;
@@ -379,0 +574,0 @@ Heap.MaxHeap = MaxHeap;

index.d.ts

@@ -16,3 +16,4 @@ /**
 export {default as FibonacciHeap, MinFibonacciHeap, MaxFibonacciHeap} from './fibonacci-heap';
-export {default as FiniteStack} from './finite-stack';
+export {default as FixedReverseHeap} from './fixed-reverse-heap';
+export {default as FixedStack} from './fixed-stack';
 export {default as FuzzyMap} from './fuzzy-map';
@@ -19,0 +20,0 @@ export {default as FuzzyMultiMap} from './fuzzy-multi-map';

index.js

@@ -23,2 +23,3 @@ /**
   MaxFibonacciHeap: FibonacciHeap.MaxFibonacciHeap,
+  FixedReverseHeap: require('./fixed-reverse-heap.js'),
   FuzzyMap: require('./fuzzy-map.js'),
@@ -37,3 +38,3 @@ FuzzyMultiMap: require('./fuzzy-multi-map.js'),
   Queue: require('./queue.js'),
-  FiniteStack: require('./finite-stack.js'),
+  FixedStack: require('./fixed-stack.js'),
   Stack: require('./stack.js'),
@@ -40,0 +41,0 @@ SuffixArray: SuffixArray,

multi-set.d.ts

@@ -23,2 +23,3 @@ /**
   frequency(key: K): number;
+  top(n: number): Array<[K, number]>;
   forEach(callback: (value: K, key: K, set: this) => void, scope?: any): void;
@@ -34,2 +35,2 @@ keys(): Iterator<K>;
   static from<I>(iterable: Iterable<I> | {[key: string]: I}): MultiSet<I>;
-}
+}

multi-set.js

@@ -8,4 +8,17 @@ /**
 var Iterator = require('obliterator/iterator'),
-    iterate = require('./utils/iterables.js').iterate;
+    iterate = require('./utils/iterables.js').iterate,
+    FixedReverseHeap = require('./fixed-reverse-heap.js');
 
+/**
+ * Helpers.
+ */
+var MULTISET_ITEM_COMPARATOR = function(a, b) {
+  if (a[1] > b[1])
+    return -1;
+  if (a[1] < b[1])
+    return 1;
+
+  return 0;
+};
+
 // TODO: helper functions: union, intersection, sum, difference, subtract
@@ -236,2 +249,23 @@
 /**
+ * Method used to return the n most common items from the set.
+ *
+ * @param  {number} n - Number of items to retrieve.
+ * @return {array}
+ */
+MultiSet.prototype.top = function(n) {
+  if (typeof n !== 'number' || n <= 0)
+    throw new Error('mnemonist/multi-set.mostCommon: n must be a number > 0.');
+
+  var heap = new FixedReverseHeap(Array, MULTISET_ITEM_COMPARATOR, n);
+
+  var iterator = this.items.entries(),
+      step;
+
+  while ((step = iterator.next(), !step.done))
+    heap.push(step.value);
+
+  return heap.consume();
+};
+
+/**
  * Method used to iterate over the set's values.
@@ -238,0 +272,0 @@ *

package.json

 {
   "name": "mnemonist",
-  "version": "0.22.0",
+  "version": "0.23.0-beta1",
   "description": "Curated collection of data structures for the JavaScript language.",
@@ -5,0 +5,0 @@ "scripts": {

README.md

@@ -28,3 +28,2 @@ [![Build Status](https://travis-ci.org/Yomguithereal/mnemonist.svg)](https://travis-ci.org/Yomguithereal/mnemonist)
 
-* [Fibonacci Heap](https://yomguithereal.github.io/mnemonist/fibonacci-heap)
 * [Heap](https://yomguithereal.github.io/mnemonist/heap)
@@ -43,3 +42,5 @@ * [Linked List](https://yomguithereal.github.io/mnemonist/linked-list)
 * [Circular Buffer](https://yomguithereal.github.io/mnemonist/circular-buffer)
-* [Finite Stack](https://yomguithereal.github.io/mnemonist/finite-stack)
+* [Fibonacci Heap](https://yomguithereal.github.io/mnemonist/fibonacci-heap)
+* [Fixed Reverse Heap](https://yomguithereal.github.io/mnemonist/fixed-reverse-heap)
+* [Fixed Stack](https://yomguithereal.github.io/mnemonist/fixed-stack)
 * [Hashed Array Tree](https://yomguithereal.github.io/mnemonist/hashed-array-tree)
@@ -46,0 +47,0 @@ * [Static DisjointSet](https://yomguithereal.github.io/mnemonist/static-disjoint-set)

static-interval-tree.js

@@ -22,3 +22,3 @@ /*
 
-var FiniteStack = require('./finite-stack.js');
+var FixedStack = require('./fixed-stack.js');
 
@@ -215,3 +215,3 @@
   // Initializing DFS stack
-  this.stack = new FiniteStack(IndicesArray, this.height);
+  this.stack = new FixedStack(IndicesArray, this.height);
 }
@@ -218,0 +218,0 @@

utils/comparators.js

@@ -16,2 +16,11 @@ /**
 
+var DEFAULT_REVERSE_COMPARATOR = function(a, b) {
+  if (a < b)
+    return 1;
+  if (a > b)
+    return -1;
+
+  return 0;
+};
+
 /**
@@ -30,2 +39,3 @@ * Function used to reverse a comparator.
 exports.DEFAULT_COMPARATOR = DEFAULT_COMPARATOR;
+exports.DEFAULT_REVERSE_COMPARATOR = DEFAULT_REVERSE_COMPARATOR;
 exports.reverseComparator = reverseComparator;

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

270189

increased by6.9%

Number of package files

77

increased by4.05%

Lines of code

9826

increased by6.23%

Number of lines in readme file

106

increased by0.95%

No dependency changes