repositories / poolifier.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
perf: optimize tasks queue implementation
[poolifier.git] / tests / priority-queue.test.mjs
CommitLineData
bd8b441c
JB		 1import { expect } from 'expect'
2
9df282a0
JB		 3import { FixedPriorityQueue } from '../lib/fixed-priority-queue.cjs'
4import { defaultBucketSize, PriorityQueue } from '../lib/priority-queue.cjs'
bd8b441c 5
95d1a734 6describe('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})
Fast and small Node.js thread pool implementation mirror - https://github.com/poolifier/poolifier