• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// Flags: --expose-internals
2'use strict';
3
4require('../common');
5
6const assert = require('assert');
7const PriorityQueue = require('internal/priority_queue');
8
9{
10  // Checks that the queue is fundamentally correct.
11  const queue = new PriorityQueue();
12  for (let i = 15; i > 0; i--)
13    queue.insert(i);
14
15  for (let i = 1; i < 16; i++) {
16    assert.strictEqual(queue.peek(), i);
17    assert.strictEqual(queue.shift(), i);
18  }
19
20  assert.strictEqual(queue.shift(), undefined);
21
22  // Reverse the order.
23  for (let i = 1; i < 16; i++)
24    queue.insert(i);
25
26  for (let i = 1; i < 16; i++) {
27    assert.strictEqual(queue.shift(), i);
28  }
29
30  assert.strictEqual(queue.shift(), undefined);
31}
32
33{
34  // Checks that the queue is capable of resizing and fitting more elements.
35  const queue = new PriorityQueue();
36  for (let i = 2048; i > 0; i--)
37    queue.insert(i);
38
39  for (let i = 1; i < 2049; i++) {
40    assert.strictEqual(queue.shift(), i);
41  }
42
43  assert.strictEqual(queue.shift(), undefined);
44}
45
46{
47  // Make a max heap with a custom sort function.
48  const queue = new PriorityQueue((a, b) => b - a);
49  for (let i = 1; i < 17; i++)
50    queue.insert(i);
51
52  for (let i = 16; i > 0; i--) {
53    assert.strictEqual(queue.shift(), i);
54  }
55
56  assert.strictEqual(queue.shift(), undefined);
57}
58
59{
60  // Make a min heap that accepts objects as values, which necessitates
61  // a custom sorting function. In addition, add a setPosition function
62  // as 2nd param which provides a reference to the node in the heap
63  // and allows speedy deletions.
64  const queue = new PriorityQueue((a, b) => {
65    return a.value - b.value;
66  }, (node, pos) => (node.position = pos));
67  for (let i = 1; i < 17; i++)
68    queue.insert({ value: i, position: null });
69
70  for (let i = 1; i < 17; i++) {
71    assert.strictEqual(queue.peek().value, i);
72    queue.removeAt(queue.peek().position);
73  }
74
75  assert.strictEqual(queue.peek(), undefined);
76}
77
78{
79  const queue = new PriorityQueue((a, b) => {
80    return a.value - b.value;
81  }, (node, pos) => (node.position = pos));
82
83  queue.insert({ value: 1, position: null });
84  queue.insert({ value: 2, position: null });
85  queue.insert({ value: 3, position: null });
86  queue.insert({ value: 4, position: null });
87  queue.insert({ value: 5, position: null });
88
89  queue.insert({ value: 2, position: null });
90  const secondLargest = { value: 10, position: null };
91  queue.insert(secondLargest);
92  const largest = { value: 15, position: null };
93  queue.insert(largest);
94
95  queue.removeAt(5);
96  assert.strictEqual(largest.position, 5);
97
98  // Check that removing 2nd to last item works fine
99  queue.removeAt(6);
100  assert.strictEqual(secondLargest.position, 6);
101
102  // Check that removing the last item doesn't throw
103  queue.removeAt(6);
104
105  assert.strictEqual(queue.shift().value, 1);
106  assert.strictEqual(queue.shift().value, 2);
107  assert.strictEqual(queue.shift().value, 2);
108  assert.strictEqual(queue.shift().value, 4);
109  assert.strictEqual(queue.shift().value, 15);
110
111  assert.strictEqual(queue.shift(), undefined);
112}
113
114
115{
116  // Checks that removeAt respects binary heap properties
117  const queue = new PriorityQueue((a, b) => {
118    return a.value - b.value;
119  }, (node, pos) => (node.position = pos));
120
121  const i3 = { value: 3, position: null };
122  const i7 = { value: 7, position: null };
123  const i8 = { value: 8, position: null };
124
125  queue.insert({ value: 1, position: null });
126  queue.insert({ value: 6, position: null });
127  queue.insert({ value: 2, position: null });
128  queue.insert(i7);
129  queue.insert(i8);
130  queue.insert(i3);
131
132  assert.strictEqual(i7.position, 4);
133  queue.removeAt(4);
134
135  // 3 should percolate up to swap with 6 (up)
136  assert.strictEqual(i3.position, 2);
137
138  queue.removeAt(2);
139
140  // 8 should swap places with 6 (down)
141  assert.strictEqual(i8.position, 4);
142}
143