File Explorer

1/**2 * Mnemonist Fixed Reverse Heap3 * =============================4 *5 * Static heap implementation with fixed capacity. It's a "reverse" heap6 * because it stores the elements in reverse so we can replace the worst7 * item in logarithmic time. As such, one cannot pop this heap but can only8 * consume it at the end. This structure is very efficient when trying to9 * find the n smallest/largest items from a larger query (k nearest neigbors10 * for instance).11 */12var comparators = require('./utils/comparators.js'),13    Heap = require('./heap.js');14 15var DEFAULT_COMPARATOR = comparators.DEFAULT_COMPARATOR,16    reverseComparator = comparators.reverseComparator;17 18/**19 * Helper functions.20 */21 22/**23 * Function used to sift up.24 *25 * @param {function} compare - Comparison function.26 * @param {array}    heap    - Array storing the heap's data.27 * @param {number}   size    - Heap's true size.28 * @param {number}   i       - Index.29 */30function siftUp(compare, heap, size, i) {31  var endIndex = size,32      startIndex = i,33      item = heap[i],34      childIndex = 2 * i + 1,35      rightIndex;36 37  while (childIndex < endIndex) {38    rightIndex = childIndex + 1;39 40    if (41      rightIndex < endIndex &&42      compare(heap[childIndex], heap[rightIndex]) >= 043    ) {44      childIndex = rightIndex;45    }46 47    heap[i] = heap[childIndex];48    i = childIndex;49    childIndex = 2 * i + 1;50  }51 52  heap[i] = item;53  Heap.siftDown(compare, heap, startIndex, i);54}55 56/**57 * Fully consumes the given heap.58 *59 * @param  {function} ArrayClass - Array class to use.60 * @param  {function} compare    - Comparison function.61 * @param  {array}    heap       - Array storing the heap's data.62 * @param  {number}   size       - True size of the heap.63 * @return {array}64 */65function consume(ArrayClass, compare, heap, size) {66  var l = size,67      i = l;68 69  var array = new ArrayClass(size),70      lastItem,71      item;72 73  while (i > 0) {74    lastItem = heap[--i];75 76    if (i !== 0) {77      item = heap[0];78      heap[0] = lastItem;79      siftUp(compare, heap, --size, 0);80      lastItem = item;81    }82 83    array[i] = lastItem;84  }85 86  return array;87}88 89/**90 * Binary Minimum FixedReverseHeap.91 *92 * @constructor93 * @param {function} ArrayClass - The class of array to use.94 * @param {function} comparator - Comparator function.95 * @param {number}   capacity   - Maximum number of items to keep.96 */97function FixedReverseHeap(ArrayClass, comparator, capacity) {98 99  // Comparator can be omitted100  if (arguments.length === 2) {101    capacity = comparator;102    comparator = null;103  }104 105  this.ArrayClass = ArrayClass;106  this.capacity = capacity;107 108  this.items = new ArrayClass(capacity);109  this.clear();110  this.comparator = comparator || DEFAULT_COMPARATOR;111 112  if (typeof capacity !== 'number' && capacity <= 0)113    throw new Error('mnemonist/FixedReverseHeap.constructor: capacity should be a number > 0.');114 115  if (typeof this.comparator !== 'function')116    throw new Error('mnemonist/FixedReverseHeap.constructor: given comparator should be a function.');117 118  this.comparator = reverseComparator(this.comparator);119}120 121/**122 * Method used to clear the heap.123 *124 * @return {undefined}125 */126FixedReverseHeap.prototype.clear = function() {127 128  // Properties129  this.size = 0;130};131 132/**133 * Method used to push an item into the heap.134 *135 * @param  {any}    item - Item to push.136 * @return {number}137 */138FixedReverseHeap.prototype.push = function(item) {139 140  // Still some place141  if (this.size < this.capacity) {142    this.items[this.size] = item;143    Heap.siftDown(this.comparator, this.items, 0, this.size);144    this.size++;145  }146 147  // Heap is full, we need to replace worst item148  else {149 150    if (this.comparator(item, this.items[0]) > 0)151      Heap.replace(this.comparator, this.items, item);152  }153 154  return this.size;155};156 157/**158 * Method used to peek the worst item in the heap.159 *160 * @return {any}161 */162FixedReverseHeap.prototype.peek = function() {163  return this.items[0];164};165 166/**167 * Method used to consume the heap fully and return its items as a sorted array.168 *169 * @return {array}170 */171FixedReverseHeap.prototype.consume = function() {172  var items = consume(this.ArrayClass, this.comparator, this.items, this.size);173  this.size = 0;174 175  return items;176};177 178/**179 * Method used to convert the heap to an array. Note that it basically clone180 * the heap and consumes it completely. This is hardly performant.181 *182 * @return {array}183 */184FixedReverseHeap.prototype.toArray = function() {185  return consume(this.ArrayClass, this.comparator, this.items.slice(0, this.size), this.size);186};187 188/**189 * Convenience known methods.190 */191FixedReverseHeap.prototype.inspect = function() {192  var proxy = this.toArray();193 194  // Trick so that node displays the name of the constructor195  Object.defineProperty(proxy, 'constructor', {196    value: FixedReverseHeap,197    enumerable: false198  });199 200  return proxy;201};202 203if (typeof Symbol !== 'undefined')204  FixedReverseHeap.prototype[Symbol.for('nodejs.util.inspect.custom')] = FixedReverseHeap.prototype.inspect;205 206/**207 * Exporting.208 */209module.exports = FixedReverseHeap;210