tests/queues/priority-queue.test.mjs

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