tests/priority-queue.test.mjs

   1 import { expect } from 'expect'
   2
   3 import { PriorityQueue } from '../lib/priority-queue.cjs'
   4
   5 describe('Priority queue test suite', () => {
   6   it('Verify constructor() behavior', () => {
   7     expect(() => new PriorityQueue('')).toThrow(
   8       new TypeError('bucketSize must be an integer')
   9     )
  10     expect(() => new PriorityQueue(-1)).toThrow(
  11       new RangeError('bucketSize must be greater than or equal to 1')
  12     )
  13     expect(() => new PriorityQueue(0)).toThrow(
  14       new RangeError('bucketSize must be greater than or equal to 1')
  15     )
  16     let priorityQueue = new PriorityQueue()
  17     expect(priorityQueue.bucketSize).toBe(Infinity)
  18     expect(priorityQueue.buckets).toBe(1)
  19     expect(priorityQueue.size).toBe(0)
  20     expect(priorityQueue.maxSize).toBe(0)
  21     expect(priorityQueue.nodeArray).toStrictEqual([])
  22     priorityQueue = new PriorityQueue(2)
  23     expect(priorityQueue.bucketSize).toBe(2)
  24     expect(priorityQueue.buckets).toBe(0)
  25     expect(priorityQueue.size).toBe(0)
  26     expect(priorityQueue.maxSize).toBe(0)
  27     expect(priorityQueue.nodeArray).toStrictEqual([])
  28   })
  29
  30   it('Verify default bucketSize enqueue() behavior', () => {
  31     const priorityQueue = new PriorityQueue()
  32     let rtSize = priorityQueue.enqueue(1)
  33     expect(priorityQueue.buckets).toBe(1)
  34     expect(priorityQueue.size).toBe(1)
  35     expect(priorityQueue.maxSize).toBe(1)
  36     expect(rtSize).toBe(priorityQueue.size)
  37     expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }])
  38     rtSize = priorityQueue.enqueue(2)
  39     expect(priorityQueue.buckets).toBe(1)
  40     expect(priorityQueue.size).toBe(2)
  41     expect(priorityQueue.maxSize).toBe(2)
  42     expect(rtSize).toBe(priorityQueue.size)
  43     expect(priorityQueue.nodeArray).toStrictEqual([
  44       { data: 1, priority: 0 },
  45       { data: 2, priority: 0 }
  46     ])
  47     rtSize = priorityQueue.enqueue(3)
  48     expect(priorityQueue.buckets).toBe(1)
  49     expect(priorityQueue.size).toBe(3)
  50     expect(priorityQueue.maxSize).toBe(3)
  51     expect(rtSize).toBe(priorityQueue.size)
  52     expect(priorityQueue.nodeArray).toStrictEqual([
  53       { data: 1, priority: 0 },
  54       { data: 2, priority: 0 },
  55       { data: 3, priority: 0 }
  56     ])
  57     rtSize = priorityQueue.enqueue(3, -1)
  58     expect(priorityQueue.buckets).toBe(1)
  59     expect(priorityQueue.size).toBe(4)
  60     expect(priorityQueue.maxSize).toBe(4)
  61     expect(rtSize).toBe(priorityQueue.size)
  62     expect(priorityQueue.nodeArray).toStrictEqual([
  63       { data: 3, priority: -1 },
  64       { data: 1, priority: 0 },
  65       { data: 2, priority: 0 },
  66       { data: 3, priority: 0 }
  67     ])
  68     rtSize = priorityQueue.enqueue(1, 1)
  69     expect(priorityQueue.buckets).toBe(1)
  70     expect(priorityQueue.size).toBe(5)
  71     expect(priorityQueue.maxSize).toBe(5)
  72     expect(rtSize).toBe(priorityQueue.size)
  73     expect(priorityQueue.nodeArray).toStrictEqual([
  74       { data: 3, priority: -1 },
  75       { data: 1, priority: 0 },
  76       { data: 2, priority: 0 },
  77       { data: 3, priority: 0 },
  78       { data: 1, priority: 1 }
  79     ])
  80   })
  81
  82   it('Verify bucketSize=2 enqueue() behavior', () => {
  83     const priorityQueue = new PriorityQueue(2)
  84     let rtSize = priorityQueue.enqueue(1)
  85     expect(priorityQueue.buckets).toBe(0)
  86     expect(priorityQueue.size).toBe(1)
  87     expect(priorityQueue.maxSize).toBe(1)
  88     expect(rtSize).toBe(priorityQueue.size)
  89     expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }])
  90     rtSize = priorityQueue.enqueue(2)
  91     expect(priorityQueue.buckets).toBe(1)
  92     expect(priorityQueue.size).toBe(2)
  93     expect(priorityQueue.maxSize).toBe(2)
  94     expect(rtSize).toBe(priorityQueue.size)
  95     expect(priorityQueue.nodeArray).toStrictEqual([
  96       { data: 1, priority: 0 },
  97       { data: 2, priority: 0 }
  98     ])
  99     rtSize = priorityQueue.enqueue(3)
 100     expect(priorityQueue.buckets).toBe(1)
 101     expect(priorityQueue.size).toBe(3)
 102     expect(priorityQueue.maxSize).toBe(3)
 103     expect(rtSize).toBe(priorityQueue.size)
 104     expect(priorityQueue.nodeArray).toStrictEqual([
 105       { data: 1, priority: 0 },
 106       { data: 2, priority: 0 },
 107       { data: 3, priority: 0 }
 108     ])
 109     rtSize = priorityQueue.enqueue(3, -1)
 110     expect(priorityQueue.buckets).toBe(2)
 111     expect(priorityQueue.size).toBe(4)
 112     expect(priorityQueue.maxSize).toBe(4)
 113     expect(rtSize).toBe(priorityQueue.size)
 114     expect(priorityQueue.nodeArray).toStrictEqual([
 115       { data: 1, priority: 0 },
 116       { data: 2, priority: 0 },
 117       { data: 3, priority: -1 },
 118       { data: 3, priority: 0 }
 119     ])
 120     rtSize = priorityQueue.enqueue(1, 1)
 121     expect(priorityQueue.buckets).toBe(2)
 122     expect(priorityQueue.size).toBe(5)
 123     expect(priorityQueue.maxSize).toBe(5)
 124     expect(rtSize).toBe(priorityQueue.size)
 125     expect(priorityQueue.nodeArray).toStrictEqual([
 126       { data: 1, priority: 0 },
 127       { data: 2, priority: 0 },
 128       { data: 3, priority: -1 },
 129       { data: 3, priority: 0 },
 130       { data: 1, priority: 1 }
 131     ])
 132     rtSize = priorityQueue.enqueue(3, -2)
 133     expect(priorityQueue.buckets).toBe(3)
 134     expect(priorityQueue.size).toBe(6)
 135     expect(priorityQueue.maxSize).toBe(6)
 136     expect(rtSize).toBe(priorityQueue.size)
 137     expect(priorityQueue.nodeArray).toStrictEqual([
 138       { data: 1, priority: 0 },
 139       { data: 2, priority: 0 },
 140       { data: 3, priority: -1 },
 141       { data: 3, priority: 0 },
 142       { data: 3, priority: -2 },
 143       { data: 1, priority: 1 }
 144     ])
 145   })
 146
 147   it('Verify default bucketSize dequeue() behavior', () => {
 148     const priorityQueue = new PriorityQueue()
 149     priorityQueue.enqueue(1)
 150     priorityQueue.enqueue(2, -1)
 151     priorityQueue.enqueue(3)
 152     expect(priorityQueue.buckets).toBe(1)
 153     expect(priorityQueue.size).toBe(3)
 154     expect(priorityQueue.maxSize).toBe(3)
 155     let rtItem = priorityQueue.dequeue()
 156     expect(priorityQueue.buckets).toBe(1)
 157     expect(priorityQueue.size).toBe(2)
 158     expect(priorityQueue.maxSize).toBe(3)
 159     expect(rtItem).toBe(2)
 160     expect(priorityQueue.nodeArray).toStrictEqual([
 161       { data: 1, priority: 0 },
 162       { data: 3, priority: 0 }
 163     ])
 164     rtItem = priorityQueue.dequeue()
 165     expect(priorityQueue.buckets).toBe(1)
 166     expect(priorityQueue.size).toBe(1)
 167     expect(priorityQueue.maxSize).toBe(3)
 168     expect(rtItem).toBe(1)
 169     expect(priorityQueue.nodeArray).toStrictEqual([{ data: 3, priority: 0 }])
 170     rtItem = priorityQueue.dequeue()
 171     expect(priorityQueue.buckets).toBe(1)
 172     expect(priorityQueue.size).toBe(0)
 173     expect(priorityQueue.maxSize).toBe(3)
 174     expect(rtItem).toBe(3)
 175     expect(priorityQueue.nodeArray).toStrictEqual([])
 176   })
 177
 178   it('Verify bucketSize=2 dequeue() behavior', () => {
 179     const priorityQueue = new PriorityQueue(2)
 180     priorityQueue.enqueue(1)
 181     priorityQueue.enqueue(2)
 182     priorityQueue.enqueue(3)
 183     priorityQueue.enqueue(3, -1)
 184     priorityQueue.enqueue(1, 1)
 185     priorityQueue.enqueue(3, -2)
 186     expect(priorityQueue.buckets).toBe(3)
 187     expect(priorityQueue.size).toBe(6)
 188     expect(priorityQueue.maxSize).toBe(6)
 189     let rtItem = priorityQueue.dequeue(3)
 190     expect(priorityQueue.buckets).toBe(2)
 191     expect(priorityQueue.size).toBe(5)
 192     expect(priorityQueue.maxSize).toBe(6)
 193     expect(rtItem).toBe(3)
 194     expect(priorityQueue.nodeArray).toStrictEqual([
 195       { data: 1, priority: 0 },
 196       { data: 2, priority: 0 },
 197       { data: 3, priority: -1 },
 198       { data: 3, priority: 0 },
 199       { data: 1, priority: 1 }
 200     ])
 201     rtItem = priorityQueue.dequeue()
 202     expect(priorityQueue.buckets).toBe(2)
 203     expect(priorityQueue.size).toBe(4)
 204     expect(priorityQueue.maxSize).toBe(6)
 205     expect(rtItem).toBe(1)
 206     expect(priorityQueue.nodeArray).toStrictEqual([
 207       { data: 2, priority: 0 },
 208       { data: 3, priority: -1 },
 209       { data: 3, priority: 0 },
 210       { data: 1, priority: 1 }
 211     ])
 212     rtItem = priorityQueue.dequeue(2)
 213     expect(priorityQueue.buckets).toBe(1)
 214     expect(priorityQueue.size).toBe(3)
 215     expect(priorityQueue.maxSize).toBe(6)
 216     expect(rtItem).toBe(3)
 217     expect(priorityQueue.nodeArray).toStrictEqual([
 218       { data: 2, priority: 0 },
 219       { data: 3, priority: -1 },
 220       { data: 1, priority: 1 }
 221     ])
 222     rtItem = priorityQueue.dequeue(2)
 223     expect(priorityQueue.buckets).toBe(1)
 224     expect(priorityQueue.size).toBe(2)
 225     expect(priorityQueue.maxSize).toBe(6)
 226     expect(rtItem).toBe(1)
 227     expect(priorityQueue.nodeArray).toStrictEqual([
 228       { data: 2, priority: 0 },
 229       { data: 3, priority: -1 }
 230     ])
 231     rtItem = priorityQueue.dequeue(2)
 232     expect(priorityQueue.buckets).toBe(0)
 233     expect(priorityQueue.size).toBe(1)
 234     expect(priorityQueue.maxSize).toBe(6)
 235     expect(rtItem).toBe(2)
 236     expect(priorityQueue.nodeArray).toStrictEqual([{ data: 3, priority: -1 }])
 237     rtItem = priorityQueue.dequeue()
 238     expect(priorityQueue.buckets).toBe(0)
 239     expect(priorityQueue.size).toBe(0)
 240     expect(priorityQueue.maxSize).toBe(6)
 241     expect(rtItem).toBe(3)
 242     expect(priorityQueue.nodeArray).toStrictEqual([])
 243   })
 244
 245   it('Verify peekFirst() behavior', () => {
 246     const priorityQueue = new PriorityQueue()
 247     priorityQueue.enqueue(1)
 248     priorityQueue.enqueue(2)
 249     priorityQueue.enqueue(3)
 250     expect(priorityQueue.size).toBe(3)
 251     expect(priorityQueue.peekFirst()).toBe(1)
 252     expect(priorityQueue.size).toBe(3)
 253   })
 254
 255   it('Verify peekLast() behavior', () => {
 256     const priorityQueue = new PriorityQueue()
 257     priorityQueue.enqueue(1)
 258     priorityQueue.enqueue(2)
 259     priorityQueue.enqueue(3)
 260     expect(priorityQueue.size).toBe(3)
 261     expect(priorityQueue.peekLast()).toBe(3)
 262     expect(priorityQueue.size).toBe(3)
 263   })
 264
 265   it('Verify iterator behavior', () => {
 266     const priorityQueue = new PriorityQueue()
 267     priorityQueue.enqueue(1)
 268     priorityQueue.enqueue(2)
 269     priorityQueue.enqueue(3)
 270     let i = 1
 271     for (const value of priorityQueue) {
 272       expect(value).toBe(i)
 273       ++i
 274     }
 275   })
 276
 277   it('Verify clear() behavior', () => {
 278     const priorityQueue = new PriorityQueue()
 279     priorityQueue.enqueue(1)
 280     priorityQueue.enqueue(2)
 281     priorityQueue.enqueue(3)
 282     expect(priorityQueue.buckets).toBe(1)
 283     expect(priorityQueue.size).toBe(3)
 284     expect(priorityQueue.maxSize).toBe(3)
 285     expect(priorityQueue.nodeArray).toStrictEqual([
 286       { data: 1, priority: 0 },
 287       { data: 2, priority: 0 },
 288       { data: 3, priority: 0 }
 289     ])
 290     priorityQueue.clear()
 291     expect(priorityQueue.buckets).toBe(1)
 292     expect(priorityQueue.size).toBe(0)
 293     expect(priorityQueue.maxSize).toBe(0)
 294     expect(priorityQueue.nodeArray).toStrictEqual([])
 295   })
 296 })