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     rtSize = priorityQueue.enqueue(3, -1)
 141     expect(priorityQueue.buckets).toBe(2)
 142     expect(priorityQueue.size).toBe(4)
 143     expect(priorityQueue.maxSize).toBe(4)
 144     expect(rtSize).toBe(priorityQueue.size)
 145     expect(priorityQueue.head.nodeArray).toMatchObject([
 146       { data: 3, priority: -1 },
 147       { data: 3, priority: 0 }
 148     ])
 149     expect(priorityQueue.head.next).toBe(undefined)
 150     expect(priorityQueue.tail.nodeArray).toMatchObject([
 151       { data: 1, priority: 0 },
 152       { data: 2, priority: 0 }
 153     ])
 154     expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head)
 155     rtSize = priorityQueue.enqueue(1, 1)
 156     expect(priorityQueue.buckets).toBe(2)
 157     expect(priorityQueue.size).toBe(5)
 158     expect(priorityQueue.maxSize).toBe(5)
 159     expect(rtSize).toBe(priorityQueue.size)
 160     expect(priorityQueue.head.nodeArray).toMatchObject([
 161       { data: 1, priority: 1 }
 162     ])
 163     expect(priorityQueue.head.next).toBe(undefined)
 164     expect(priorityQueue.tail.nodeArray).toMatchObject([
 165       { data: 1, priority: 0 },
 166       { data: 2, priority: 0 }
 167     ])
 168     expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
 169     expect(priorityQueue.tail.next.nodeArray).toMatchObject([
 170       { data: 3, priority: -1 },
 171       { data: 3, priority: 0 }
 172     ])
 173     rtSize = priorityQueue.enqueue(3, -2)
 174     expect(priorityQueue.buckets).toBe(3)
 175     expect(priorityQueue.size).toBe(6)
 176     expect(priorityQueue.maxSize).toBe(6)
 177     expect(rtSize).toBe(priorityQueue.size)
 178     expect(priorityQueue.head.nodeArray).toMatchObject([
 179       { data: 3, priority: -2 },
 180       { data: 1, priority: 1 }
 181     ])
 182     expect(priorityQueue.head.next).toBe(undefined)
 183     expect(priorityQueue.tail.nodeArray).toMatchObject([
 184       { data: 1, priority: 0 },
 185       { data: 2, priority: 0 }
 186     ])
 187     expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
 188     expect(priorityQueue.tail.next.nodeArray).toMatchObject([
 189       { data: 3, priority: -1 },
 190       { data: 3, priority: 0 }
 191     ])
 192   })
 193
 194   it('Verify default bucket size dequeue() behavior', () => {
 195     const priorityQueue = new PriorityQueue(defaultBucketSize, true)
 196     priorityQueue.enqueue(1)
 197     priorityQueue.enqueue(2, -1)
 198     priorityQueue.enqueue(3)
 199     expect(priorityQueue.buckets).toBe(0)
 200     expect(priorityQueue.size).toBe(3)
 201     expect(priorityQueue.maxSize).toBe(3)
 202     expect(priorityQueue.tail.empty()).toBe(false)
 203     expect(priorityQueue.tail.next).toBe(undefined)
 204     let rtItem = priorityQueue.dequeue()
 205     expect(priorityQueue.buckets).toBe(0)
 206     expect(priorityQueue.size).toBe(2)
 207     expect(priorityQueue.maxSize).toBe(3)
 208     expect(rtItem).toBe(2)
 209     expect(priorityQueue.tail.empty()).toBe(false)
 210     expect(priorityQueue.tail.next).toBe(undefined)
 211     rtItem = priorityQueue.dequeue()
 212     expect(priorityQueue.buckets).toBe(0)
 213     expect(priorityQueue.size).toBe(1)
 214     expect(priorityQueue.maxSize).toBe(3)
 215     expect(rtItem).toBe(1)
 216     expect(priorityQueue.tail.empty()).toBe(false)
 217     expect(priorityQueue.tail.next).toBe(undefined)
 218     rtItem = priorityQueue.dequeue()
 219     expect(priorityQueue.buckets).toBe(0)
 220     expect(priorityQueue.size).toBe(0)
 221     expect(priorityQueue.maxSize).toBe(3)
 222     expect(rtItem).toBe(3)
 223     expect(priorityQueue.tail.empty()).toBe(true)
 224     expect(priorityQueue.tail.next).toBe(undefined)
 225   })
 226
 227   it('Verify bucketSize=2 dequeue() behavior', () => {
 228     const priorityQueue = new PriorityQueue(2, true)
 229     priorityQueue.enqueue(1)
 230     priorityQueue.enqueue(2)
 231     priorityQueue.enqueue(3)
 232     priorityQueue.enqueue(3, -1)
 233     priorityQueue.enqueue(1, 1)
 234     priorityQueue.enqueue(3, -2)
 235     expect(priorityQueue.buckets).toBe(3)
 236     expect(priorityQueue.size).toBe(6)
 237     expect(priorityQueue.maxSize).toBe(6)
 238     expect(priorityQueue.tail.empty()).toBe(false)
 239     expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
 240     let rtItem = priorityQueue.dequeue(3)
 241     expect(priorityQueue.buckets).toBe(2)
 242     expect(priorityQueue.size).toBe(5)
 243     expect(priorityQueue.maxSize).toBe(6)
 244     expect(rtItem).toBe(3)
 245     expect(priorityQueue.tail.empty()).toBe(false)
 246     expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
 247     rtItem = priorityQueue.dequeue()
 248     expect(priorityQueue.buckets).toBe(2)
 249     expect(priorityQueue.size).toBe(4)
 250     expect(priorityQueue.maxSize).toBe(6)
 251     expect(rtItem).toBe(1)
 252     expect(priorityQueue.tail.empty()).toBe(false)
 253     expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
 254     rtItem = priorityQueue.dequeue(2)
 255     expect(priorityQueue.buckets).toBe(1)
 256     expect(priorityQueue.size).toBe(3)
 257     expect(priorityQueue.maxSize).toBe(6)
 258     expect(rtItem).toBe(3)
 259     expect(priorityQueue.tail.empty()).toBe(false)
 260     expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
 261     rtItem = priorityQueue.dequeue(2)
 262     expect(priorityQueue.buckets).toBe(1)
 263     expect(priorityQueue.size).toBe(2)
 264     expect(priorityQueue.maxSize).toBe(6)
 265     expect(rtItem).toBe(3)
 266     expect(priorityQueue.tail.empty()).toBe(false)
 267     expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
 268     rtItem = priorityQueue.dequeue(2)
 269     expect(priorityQueue.buckets).toBe(0)
 270     expect(priorityQueue.size).toBe(1)
 271     expect(priorityQueue.maxSize).toBe(6)
 272     expect(rtItem).toBe(1)
 273     expect(priorityQueue.tail.empty()).toBe(false)
 274     expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
 275     rtItem = priorityQueue.dequeue()
 276     expect(priorityQueue.buckets).toBe(0)
 277     expect(priorityQueue.size).toBe(0)
 278     expect(priorityQueue.maxSize).toBe(6)
 279     expect(rtItem).toBe(2)
 280     expect(priorityQueue.tail.empty()).toBe(true)
 281     expect(priorityQueue.tail.next).toBe(undefined)
 282   })
 283
 284   it('Verify enablePriority setter behavior', () => {
 285     const priorityQueue = new PriorityQueue(2)
 286     expect(priorityQueue.enablePriority).toBe(false)
 287     priorityQueue.enqueue(1)
 288     priorityQueue.enqueue(2)
 289     priorityQueue.enqueue(3)
 290     priorityQueue.enqueue(4)
 291     let buckets = 0
 292     let node = priorityQueue.tail
 293     while (node != null) {
 294       expect(node.enablePriority).toBe(false)
 295       node = node.next
 296       ++buckets
 297     }
 298     expect(buckets).toBe(2)
 299     priorityQueue.enablePriority = true
 300     expect(priorityQueue.enablePriority).toBe(true)
 301     node = priorityQueue.tail
 302     while (node != null) {
 303       expect(node.enablePriority).toBe(true)
 304       node = node.next
 305     }
 306   })
 307
 308   it('Verify iterator behavior', () => {
 309     const priorityQueue = new PriorityQueue(2)
 310     priorityQueue.enqueue(1)
 311     priorityQueue.enqueue(2)
 312     priorityQueue.enqueue(3)
 313     let i = 1
 314     for (const value of priorityQueue) {
 315       expect(value).toBe(i)
 316       ++i
 317     }
 318   })
 319
 320   it('Verify clear() behavior', () => {
 321     const priorityQueue = new PriorityQueue(2)
 322     priorityQueue.enqueue(1)
 323     priorityQueue.enqueue(2)
 324     priorityQueue.enqueue(3)
 325     expect(priorityQueue.buckets).toBe(1)
 326     expect(priorityQueue.size).toBe(3)
 327     expect(priorityQueue.maxSize).toBe(3)
 328     expect(priorityQueue.head.empty()).toBe(false)
 329     expect(priorityQueue.tail.empty()).toBe(false)
 330     expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
 331     priorityQueue.clear()
 332     expect(priorityQueue.buckets).toBe(0)
 333     expect(priorityQueue.size).toBe(0)
 334     expect(priorityQueue.maxSize).toBe(0)
 335     expect(priorityQueue.head.empty()).toBe(true)
 336     expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
 337   })
 338 })