All files / lib/internal priority_queue.js

100% Statements 117/117
97.3% 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 11820x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 568x 568x 568x 568x 568x 568x 568x 568x 20x 20x 52411x 52411x 20x 20x 4972x 4972x 4972x 4972x 4972x 4972x 4972x 4972x 4972x 20x 20x 15020x 15020x 20x 20x 8742x 8742x 8742x 8742x 8742x 8742x 8742x 19365x 19365x 19365x 19365x 19365x 19365x 17222x 18264x 17222x 17222x 17222x 8742x 8742x 8742x 8742x 20x 20x 4973x 4973x 4973x 4973x 4973x 4973x 19338x 19338x 19338x 18853x 18853x 18895x 18853x 18853x 4973x 4973x 4973x 4973x 20x 20x 4083x 4083x 4083x 4083x 4083x 4083x 2628x 2628x 2627x 2627x 2628x 4083x 20x 20x 3503x 3503x 3503x 3503x 3498x 3498x 3498x 3498x 3503x 20x  
'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;
  }
};