All files / lib/internal priority_queue.js

100% Statements 117/117
97.29% Branches 36/37
100% Functions 8/8
100% Lines 117/117

Press n or j to go to the next uncovered block, b, p or k for the previous block.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 11829x 29x 29x 29x 29x 29x 29x 29x 29x 29x 29x 29x 29x 29x 29x 29x 29x 29x 29x 29x 1249x 1249x 1249x 1249x 1249x 1249x 1249x 1249x 29x 29x 52411x 52411x 29x 29x 6118x 6118x 6118x 6118x 6118x 6118x 6118x 6118x 6118x 29x 29x 18342x 18342x 29x 29x 10398x 10398x 10398x 10398x 10398x 10398x 10398x 19847x 19847x 19847x 19847x 19847x 19847x 17387x 18429x 17387x 17387x 17387x 10398x 10398x 10398x 10398x 29x 29x 6119x 6119x 6119x 6119x 6119x 6119x 20289x 20289x 20289x 19600x 19600x 19642x 19600x 19600x 6119x 6119x 6119x 6119x 29x 29x 4315x 4315x 4315x 4315x 4315x 4315x 2814x 2814x 2813x 2813x 2814x 4315x 29x 29x 3686x 3686x 3686x 3686x 3681x 3681x 3681x 3681x 3686x 29x  
'use strict';
 
const {
  Array,
  Symbol,
} = primordials;
 
const kCompare = Symbol('compare');
const kHeap = Symbol('heap');
const kSetPosition = Symbol('setPosition');
const kSize = Symbol('size');
 
// The PriorityQueue is a basic implementation of a binary heap that accepts
// a custom sorting function via its constructor. This function is passed
// the two nodes to compare, similar to the native Array#sort. Crucially
// this enables priority queues that are based on a comparison of more than
// just a single criteria.
 
module.exports = class PriorityQueue {
  constructor(comparator, setPosition) {
    if (comparator !== undefined)
      this[kCompare] = comparator;
    if (setPosition !== undefined)
      this[kSetPosition] = setPosition;
 
    this[kHeap] = new Array(64);
    this[kSize] = 0;
  }
 
  [kCompare](a, b) {
    return a - b;
  }
 
  insert(value) {
    const heap = this[kHeap];
    const pos = ++this[kSize];
    heap[pos] = value;
 
    if (heap.length === pos)
      heap.length *= 2;
 
    this.percolateUp(pos);
  }
 
  peek() {
    return this[kHeap][1];
  }
 
  percolateDown(pos) {
    const compare = this[kCompare];
    const setPosition = this[kSetPosition];
    const heap = this[kHeap];
    const size = this[kSize];
    const item = heap[pos];
 
    while (pos * 2 <= size) {
      let childIndex = pos * 2 + 1;
      if (childIndex > size || compare(heap[pos * 2], heap[childIndex]) < 0)
        childIndex = pos * 2;
      const child = heap[childIndex];
      if (compare(item, child) <= 0)
        break;
      if (setPosition !== undefined)
        setPosition(child, pos);
      heap[pos] = child;
      pos = childIndex;
    }
    heap[pos] = item;
    if (setPosition !== undefined)
      setPosition(item, pos);
  }
 
  percolateUp(pos) {
    const heap = this[kHeap];
    const compare = this[kCompare];
    const setPosition = this[kSetPosition];
    const item = heap[pos];
 
    while (pos > 1) {
      const parent = heap[pos / 2 | 0];
      if (compare(parent, item) <= 0)
        break;
      heap[pos] = parent;
      if (setPosition !== undefined)
        setPosition(parent, pos);
      pos = pos / 2 | 0;
    }
    heap[pos] = item;
    if (setPosition !== undefined)
      setPosition(item, pos);
  }
 
  removeAt(pos) {
    const heap = this[kHeap];
    const size = --this[kSize];
    heap[pos] = heap[size + 1];
    heap[size + 1] = undefined;
 
    if (size > 0 && pos <= size) {
      if (pos > 1 && this[kCompare](heap[pos / 2 | 0], heap[pos]) > 0)
        this.percolateUp(pos);
      else
        this.percolateDown(pos);
    }
  }
 
  shift() {
    const heap = this[kHeap];
    const value = heap[1];
    if (value === undefined)
      return;
 
    this.removeAt(1);
 
    return value;
  }
};