tests/priority-queue.test.mjs

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