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