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