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