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