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