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