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 11821x 21x 21x 21x 21x 21x 21x 21x 21x 21x 21x 21x 21x 21x 21x 21x 21x 21x 21x 21x 579x 579x 579x 579x 579x 579x 579x 579x 21x 21x 52411x 52411x 21x 21x 4987x 4987x 4987x 4987x 4987x 4987x 4987x 4987x 4987x 21x 21x 13907x 13907x 21x 21x 8175x 8175x 8175x 8175x 8175x 8175x 8175x 19221x 19221x 19221x 19221x 19221x 19221x 17197x 18239x 17197x 17197x 17197x 8175x 8175x 8175x 8175x 21x 21x 4988x 4988x 4988x 4988x 4988x 4988x 19347x 19347x 19347x 18859x 18859x 18901x 18859x 18859x 4988x 4988x 4988x 4988x 21x 21x 4093x 4093x 4093x 4093x 4093x 4093x 2635x 2635x 2634x 2634x 2635x 4093x 21x 21x 3515x 3515x 3515x 3515x 3510x 3510x 3510x 3510x 3515x 21x  
'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;
  }
};