1 import { expect } from 'expect'
3 import { FixedPriorityQueue } from '../../lib/queues/fixed-priority-queue.cjs'
4 import { FixedQueue } from '../../lib/queues/fixed-queue.cjs'
5 import { PriorityQueue } from '../../lib/queues/priority-queue.cjs'
6 import { defaultBucketSize } from '../../lib/queues/queue-types.cjs'
8 describe('Priority queue test suite', () => {
9 it('Verify constructor() behavior', () => {
10 expect(() => new PriorityQueue('')).toThrow(
11 new TypeError("Invalid bucket size: '' is not an integer")
13 expect(() => new PriorityQueue(-1)).toThrow(
14 new RangeError('Invalid bucket size: -1 < 0')
16 let priorityQueue = new PriorityQueue()
17 expect(priorityQueue.bucketSize).toBe(defaultBucketSize)
18 expect(priorityQueue.buckets).toBe(0)
19 expect(priorityQueue.size).toBe(0)
20 expect(priorityQueue.maxSize).toBe(0)
21 expect(priorityQueue.enablePriority).toBe(false)
22 expect(priorityQueue.head).toBeInstanceOf(FixedQueue)
23 expect(priorityQueue.head.next).toBe(undefined)
24 expect(priorityQueue.head.capacity).toBe(defaultBucketSize)
25 expect(priorityQueue.tail).toBeInstanceOf(FixedQueue)
26 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
28 priorityQueue = new PriorityQueue(bucketSize, true)
29 expect(priorityQueue.bucketSize).toBe(bucketSize)
30 expect(priorityQueue.buckets).toBe(0)
31 expect(priorityQueue.size).toBe(0)
32 expect(priorityQueue.maxSize).toBe(0)
33 expect(priorityQueue.enablePriority).toBe(true)
34 expect(priorityQueue.head).toBeInstanceOf(FixedPriorityQueue)
35 expect(priorityQueue.head.next).toBe(undefined)
36 expect(priorityQueue.head.capacity).toBe(bucketSize)
37 expect(priorityQueue.tail).toBeInstanceOf(FixedPriorityQueue)
38 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
41 it('Verify default bucket size enqueue() behavior', () => {
42 const priorityQueue = new PriorityQueue(defaultBucketSize, true)
43 let rtSize = priorityQueue.enqueue(1)
44 expect(priorityQueue.buckets).toBe(0)
45 expect(priorityQueue.size).toBe(1)
46 expect(priorityQueue.maxSize).toBe(1)
47 expect(rtSize).toBe(priorityQueue.size)
48 expect(priorityQueue.head.nodeArray).toMatchObject([
49 { data: 1, priority: 0 },
51 expect(priorityQueue.head.next).toBe(undefined)
52 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
53 rtSize = priorityQueue.enqueue(2)
54 expect(priorityQueue.buckets).toBe(0)
55 expect(priorityQueue.size).toBe(2)
56 expect(priorityQueue.maxSize).toBe(2)
57 expect(rtSize).toBe(priorityQueue.size)
58 expect(priorityQueue.head.nodeArray).toMatchObject([
59 { data: 1, priority: 0 },
60 { data: 2, priority: 0 },
62 expect(priorityQueue.head.next).toBe(undefined)
63 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
64 rtSize = priorityQueue.enqueue(3)
65 expect(priorityQueue.buckets).toBe(0)
66 expect(priorityQueue.size).toBe(3)
67 expect(priorityQueue.maxSize).toBe(3)
68 expect(rtSize).toBe(priorityQueue.size)
69 expect(priorityQueue.head.nodeArray).toMatchObject([
70 { data: 1, priority: 0 },
71 { data: 2, priority: 0 },
72 { data: 3, priority: 0 },
74 expect(priorityQueue.head.next).toBe(undefined)
75 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
76 rtSize = priorityQueue.enqueue(3, -1)
77 expect(priorityQueue.buckets).toBe(0)
78 expect(priorityQueue.size).toBe(4)
79 expect(priorityQueue.maxSize).toBe(4)
80 expect(rtSize).toBe(priorityQueue.size)
81 expect(priorityQueue.head.nodeArray).toMatchObject([
82 { data: 3, priority: -1 },
83 { data: 1, priority: 0 },
84 { data: 2, priority: 0 },
85 { data: 3, priority: 0 },
87 expect(priorityQueue.head.next).toBe(undefined)
88 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
89 rtSize = priorityQueue.enqueue(1, 1)
90 expect(priorityQueue.buckets).toBe(0)
91 expect(priorityQueue.size).toBe(5)
92 expect(priorityQueue.maxSize).toBe(5)
93 expect(rtSize).toBe(priorityQueue.size)
94 expect(priorityQueue.head.nodeArray).toMatchObject([
95 { data: 3, priority: -1 },
96 { data: 1, priority: 0 },
97 { data: 2, priority: 0 },
98 { data: 3, priority: 0 },
99 { data: 1, priority: 1 },
101 expect(priorityQueue.head.next).toBe(undefined)
102 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
105 it('Verify bucketSize=2 enqueue() behavior', () => {
106 const priorityQueue = new PriorityQueue(2, true)
107 let rtSize = priorityQueue.enqueue(1)
108 expect(priorityQueue.buckets).toBe(0)
109 expect(priorityQueue.size).toBe(1)
110 expect(priorityQueue.maxSize).toBe(1)
111 expect(rtSize).toBe(priorityQueue.size)
112 expect(priorityQueue.head.nodeArray).toMatchObject([
113 { data: 1, priority: 0 },
115 expect(priorityQueue.head.next).toBe(undefined)
116 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
117 rtSize = priorityQueue.enqueue(2)
118 expect(priorityQueue.buckets).toBe(1)
119 expect(priorityQueue.size).toBe(2)
120 expect(priorityQueue.maxSize).toBe(2)
121 expect(rtSize).toBe(priorityQueue.size)
122 expect(priorityQueue.head.nodeArray).toMatchObject([
123 { data: 1, priority: 0 },
124 { data: 2, priority: 0 },
126 expect(priorityQueue.head.next).toBe(undefined)
127 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
128 rtSize = priorityQueue.enqueue(3)
129 expect(priorityQueue.buckets).toBe(1)
130 expect(priorityQueue.size).toBe(3)
131 expect(priorityQueue.maxSize).toBe(3)
132 expect(rtSize).toBe(priorityQueue.size)
133 expect(priorityQueue.head.nodeArray).toMatchObject([
134 { data: 3, priority: 0 },
136 expect(priorityQueue.head.next).toBe(undefined)
137 expect(priorityQueue.tail.nodeArray).toMatchObject([
138 { data: 1, priority: 0 },
139 { data: 2, priority: 0 },
141 expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head)
142 expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
143 rtSize = priorityQueue.enqueue(3, -1)
144 expect(priorityQueue.buckets).toBe(2)
145 expect(priorityQueue.size).toBe(4)
146 expect(priorityQueue.maxSize).toBe(4)
147 expect(rtSize).toBe(priorityQueue.size)
148 expect(priorityQueue.head.nodeArray).toMatchObject([
149 { data: 3, priority: -1 },
150 { data: 3, priority: 0 },
152 expect(priorityQueue.head.next).toBe(undefined)
153 expect(priorityQueue.tail.nodeArray).toMatchObject([
154 { data: 1, priority: 0 },
155 { data: 2, priority: 0 },
157 expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head)
158 expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
159 rtSize = priorityQueue.enqueue(1, 1)
160 expect(priorityQueue.buckets).toBe(2)
161 expect(priorityQueue.size).toBe(5)
162 expect(priorityQueue.maxSize).toBe(5)
163 expect(rtSize).toBe(priorityQueue.size)
164 expect(priorityQueue.head.nodeArray).toMatchObject([
165 { data: 1, priority: 1 },
167 expect(priorityQueue.head.next).toBe(undefined)
168 expect(priorityQueue.tail.nodeArray).toMatchObject([
169 { data: 1, priority: 0 },
170 { data: 2, priority: 0 },
172 expect(priorityQueue.tail.next.nodeArray).toMatchObject([
173 { data: 3, priority: -1 },
174 { data: 3, priority: 0 },
176 expect(priorityQueue.tail.next.next).toStrictEqual(priorityQueue.head)
177 expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
178 expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
179 rtSize = priorityQueue.enqueue(3, -2)
180 expect(priorityQueue.buckets).toBe(3)
181 expect(priorityQueue.size).toBe(6)
182 expect(priorityQueue.maxSize).toBe(6)
183 expect(rtSize).toBe(priorityQueue.size)
184 expect(priorityQueue.head.nodeArray).toMatchObject([
185 { data: 3, priority: -2 },
186 { data: 1, priority: 1 },
188 expect(priorityQueue.head.next).toBe(undefined)
189 expect(priorityQueue.tail.nodeArray).toMatchObject([
190 { data: 1, priority: 0 },
191 { data: 2, priority: 0 },
193 expect(priorityQueue.tail.next.nodeArray).toMatchObject([
194 { data: 3, priority: -1 },
195 { data: 3, priority: 0 },
197 expect(priorityQueue.tail.next.next).toStrictEqual(priorityQueue.head)
198 expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
199 expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
202 it('Verify default bucket size dequeue() behavior', () => {
203 const priorityQueue = new PriorityQueue(defaultBucketSize, true)
204 priorityQueue.enqueue(1)
205 priorityQueue.enqueue(2, -1)
206 priorityQueue.enqueue(3)
207 expect(priorityQueue.buckets).toBe(0)
208 expect(priorityQueue.size).toBe(3)
209 expect(priorityQueue.maxSize).toBe(3)
210 expect(priorityQueue.tail.empty()).toBe(false)
211 expect(priorityQueue.tail.next).toBe(undefined)
212 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
213 let rtItem = priorityQueue.dequeue()
214 expect(priorityQueue.buckets).toBe(0)
215 expect(priorityQueue.size).toBe(2)
216 expect(priorityQueue.maxSize).toBe(3)
217 expect(rtItem).toBe(2)
218 expect(priorityQueue.tail.empty()).toBe(false)
219 expect(priorityQueue.tail.next).toBe(undefined)
220 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
221 rtItem = priorityQueue.dequeue()
222 expect(priorityQueue.buckets).toBe(0)
223 expect(priorityQueue.size).toBe(1)
224 expect(priorityQueue.maxSize).toBe(3)
225 expect(rtItem).toBe(1)
226 expect(priorityQueue.tail.empty()).toBe(false)
227 expect(priorityQueue.tail.next).toBe(undefined)
228 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
229 rtItem = priorityQueue.dequeue()
230 expect(priorityQueue.buckets).toBe(0)
231 expect(priorityQueue.size).toBe(0)
232 expect(priorityQueue.maxSize).toBe(3)
233 expect(rtItem).toBe(3)
234 expect(priorityQueue.tail.empty()).toBe(true)
235 expect(priorityQueue.tail.next).toBe(undefined)
236 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
239 it('Verify bucketSize=2 dequeue() behavior', () => {
240 const priorityQueue = new PriorityQueue(2, true)
241 priorityQueue.enqueue(1)
242 priorityQueue.enqueue(2)
243 priorityQueue.enqueue(3)
244 priorityQueue.enqueue(3, -1)
245 priorityQueue.enqueue(1, 1)
246 priorityQueue.enqueue(3, -2)
247 expect(priorityQueue.buckets).toBe(3)
248 expect(priorityQueue.size).toBe(6)
249 expect(priorityQueue.maxSize).toBe(6)
250 expect(priorityQueue.tail.empty()).toBe(false)
251 expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
252 expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
253 let rtItem = priorityQueue.dequeue(3)
254 expect(priorityQueue.buckets).toBe(2)
255 expect(priorityQueue.size).toBe(5)
256 expect(priorityQueue.maxSize).toBe(6)
257 expect(rtItem).toBe(3)
258 expect(priorityQueue.tail.empty()).toBe(false)
259 expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
260 expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
261 rtItem = priorityQueue.dequeue()
262 expect(priorityQueue.buckets).toBe(2)
263 expect(priorityQueue.size).toBe(4)
264 expect(priorityQueue.maxSize).toBe(6)
265 expect(rtItem).toBe(1)
266 expect(priorityQueue.tail.empty()).toBe(false)
267 expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
268 expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
269 rtItem = priorityQueue.dequeue(2)
270 expect(priorityQueue.buckets).toBe(1)
271 expect(priorityQueue.size).toBe(3)
272 expect(priorityQueue.maxSize).toBe(6)
273 expect(rtItem).toBe(3)
274 expect(priorityQueue.tail.empty()).toBe(false)
275 expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
276 expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
277 rtItem = priorityQueue.dequeue(2)
278 expect(priorityQueue.buckets).toBe(1)
279 expect(priorityQueue.size).toBe(2)
280 expect(priorityQueue.maxSize).toBe(6)
281 expect(rtItem).toBe(3)
282 expect(priorityQueue.tail.empty()).toBe(false)
283 expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
284 expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
285 rtItem = priorityQueue.dequeue(2)
286 expect(priorityQueue.buckets).toBe(0)
287 expect(priorityQueue.size).toBe(1)
288 expect(priorityQueue.maxSize).toBe(6)
289 expect(rtItem).toBe(1)
290 expect(priorityQueue.tail.empty()).toBe(false)
291 expect(priorityQueue.tail.next).toBe(undefined)
292 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
293 rtItem = priorityQueue.dequeue()
294 expect(priorityQueue.buckets).toBe(0)
295 expect(priorityQueue.size).toBe(0)
296 expect(priorityQueue.maxSize).toBe(6)
297 expect(rtItem).toBe(2)
298 expect(priorityQueue.tail.empty()).toBe(true)
299 expect(priorityQueue.tail.next).toBe(undefined)
300 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
303 it('Verify enablePriority setter behavior', () => {
304 const priorityQueue = new PriorityQueue(2)
305 expect(priorityQueue.enablePriority).toBe(false)
306 priorityQueue.enqueue(1)
307 priorityQueue.enqueue(2)
308 priorityQueue.enqueue(3)
309 priorityQueue.enqueue(4)
311 let node = priorityQueue.tail
312 while (node != null) {
313 expect(node).toBeInstanceOf(FixedQueue)
317 expect(buckets).toBe(2)
318 priorityQueue.enablePriority = true
319 expect(priorityQueue.enablePriority).toBe(true)
321 node = priorityQueue.tail
322 while (node != null) {
323 expect(node).toBeInstanceOf(FixedPriorityQueue)
327 expect(buckets).toBe(2)
330 it('Verify iterator behavior', () => {
331 const priorityQueue = new PriorityQueue(2)
332 priorityQueue.enqueue(1)
333 priorityQueue.enqueue(2)
334 priorityQueue.enqueue(3)
336 for (const value of priorityQueue) {
337 expect(value).toBe(i)
342 it('Verify clear() behavior', () => {
343 const priorityQueue = new PriorityQueue(2)
344 priorityQueue.enqueue(1)
345 priorityQueue.enqueue(2)
346 priorityQueue.enqueue(3)
347 expect(priorityQueue.buckets).toBe(1)
348 expect(priorityQueue.size).toBe(3)
349 expect(priorityQueue.maxSize).toBe(3)
350 expect(priorityQueue.head.empty()).toBe(false)
351 expect(priorityQueue.tail.empty()).toBe(false)
352 expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
353 priorityQueue.clear()
354 expect(priorityQueue.buckets).toBe(0)
355 expect(priorityQueue.size).toBe(0)
356 expect(priorityQueue.maxSize).toBe(0)
357 expect(priorityQueue.head.empty()).toBe(true)
358 expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)