• 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  // Checks that remove works as expected.
48  const queue = new PriorityQueue();
49  for (let i = 16; i > 0; i--)
50    queue.insert(i);
51
52  const removed = [5, 10, 15];
53  for (const id of removed)
54    assert(queue.remove(id));
55
56  assert(!queue.remove(100));
57  assert(!queue.remove(-100));
58
59  for (let i = 1; i < 17; i++) {
60    if (removed.indexOf(i) < 0)
61      assert.strictEqual(queue.shift(), i);
62  }
63
64  assert.strictEqual(queue.shift(), undefined);
65}
66
67{
68  // Make a max heap with a custom sort function.
69  const queue = new PriorityQueue((a, b) => b - a);
70  for (let i = 1; i < 17; i++)
71    queue.insert(i);
72
73  for (let i = 16; i > 0; i--) {
74    assert.strictEqual(queue.shift(), i);
75  }
76
77  assert.strictEqual(queue.shift(), undefined);
78}
79
80{
81  // Make a min heap that accepts objects as values, which necessitates
82  // a custom sorting function. In addition, add a setPosition function
83  // as 2nd param which provides a reference to the node in the heap
84  // and allows speedy deletions.
85  const queue = new PriorityQueue((a, b) => {
86    return a.value - b.value;
87  }, (node, pos) => (node.position = pos));
88  for (let i = 1; i < 17; i++)
89    queue.insert({ value: i, position: null });
90
91  for (let i = 1; i < 17; i++) {
92    assert.strictEqual(queue.peek().value, i);
93    queue.removeAt(queue.peek().position);
94  }
95
96  assert.strictEqual(queue.peek(), undefined);
97}
98
99{
100  const queue = new PriorityQueue((a, b) => {
101    return a.value - b.value;
102  }, (node, pos) => (node.position = pos));
103
104  queue.insert({ value: 1, position: null });
105  queue.insert({ value: 2, position: null });
106  queue.insert({ value: 3, position: null });
107  queue.insert({ value: 4, position: null });
108  queue.insert({ value: 5, position: null });
109
110  queue.insert({ value: 2, position: null });
111  const secondLargest = { value: 10, position: null };
112  queue.insert(secondLargest);
113  const largest = { value: 15, position: null };
114  queue.insert(largest);
115
116  queue.removeAt(5);
117  assert.strictEqual(largest.position, 5);
118
119  // Check that removing 2nd to last item works fine
120  queue.removeAt(6);
121  assert.strictEqual(secondLargest.position, 6);
122
123  // Check that removing the last item doesn't throw
124  queue.removeAt(6);
125
126  assert.strictEqual(queue.shift().value, 1);
127  assert.strictEqual(queue.shift().value, 2);
128  assert.strictEqual(queue.shift().value, 2);
129  assert.strictEqual(queue.shift().value, 4);
130  assert.strictEqual(queue.shift().value, 15);
131
132  assert.strictEqual(queue.shift(), undefined);
133}
134
135
136{
137  // Checks that removeAt respects binary heap properties
138  const queue = new PriorityQueue((a, b) => {
139    return a.value - b.value;
140  }, (node, pos) => (node.position = pos));
141
142  const i3 = { value: 3, position: null };
143  const i7 = { value: 7, position: null };
144  const i8 = { value: 8, position: null };
145
146  queue.insert({ value: 1, position: null });
147  queue.insert({ value: 6, position: null });
148  queue.insert({ value: 2, position: null });
149  queue.insert(i7);
150  queue.insert(i8);
151  queue.insert(i3);
152
153  assert.strictEqual(i7.position, 4);
154  queue.removeAt(4);
155
156  // 3 should percolate up to swap with 6 (up)
157  assert.strictEqual(i3.position, 2);
158
159  queue.removeAt(2);
160
161  // 8 should swap places with 6 (down)
162  assert.strictEqual(i8.position, 4);
163}
164