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