tests/priority-queue.test.mjs

   1 import { expect } from 'expect'
   2
   3 // eslint-disable-next-line n/no-missing-import, import/no-unresolved
   4 import { PriorityQueue } from '../lib/priority-queue.cjs'
   5
   6 describe.skip('Priority queue test suite', () => {
   7   it('Verify constructor() behavior', () => {
   8     expect(() => new PriorityQueue('')).toThrow(
   9       new TypeError('k must be an integer')
  10     )
  11     expect(() => new PriorityQueue(-1)).toThrow(
  12       new RangeError('k must be greater than or equal to 1')
  13     )
  14     expect(() => new PriorityQueue(0)).toThrow(
  15       new RangeError('k must be greater than or equal to 1')
  16     )
  17     let priorityQueue = new PriorityQueue()
  18     expect(priorityQueue.k).toBe(Infinity)
  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.k).toBe(2)
  24     expect(priorityQueue.size).toBe(0)
  25     expect(priorityQueue.maxSize).toBe(0)
  26     expect(priorityQueue.nodeArray).toStrictEqual([])
  27   })
  28
  29   it('Verify default k enqueue() behavior', () => {
  30     const priorityQueue = new PriorityQueue()
  31     let rtSize = priorityQueue.enqueue(1)
  32     expect(priorityQueue.size).toBe(1)
  33     expect(priorityQueue.maxSize).toBe(1)
  34     expect(rtSize).toBe(priorityQueue.size)
  35     expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }])
  36     rtSize = priorityQueue.enqueue(2)
  37     expect(priorityQueue.size).toBe(2)
  38     expect(priorityQueue.maxSize).toBe(2)
  39     expect(rtSize).toBe(priorityQueue.size)
  40     expect(priorityQueue.nodeArray).toStrictEqual([
  41       { data: 1, priority: 0 },
  42       { data: 2, priority: 0 }
  43     ])
  44     rtSize = priorityQueue.enqueue(3)
  45     expect(priorityQueue.size).toBe(3)
  46     expect(priorityQueue.maxSize).toBe(3)
  47     expect(rtSize).toBe(priorityQueue.size)
  48     expect(priorityQueue.nodeArray).toStrictEqual([
  49       { data: 1, priority: 0 },
  50       { data: 2, priority: 0 },
  51       { data: 3, priority: 0 }
  52     ])
  53     rtSize = priorityQueue.enqueue(3, -1)
  54     expect(priorityQueue.size).toBe(4)
  55     expect(priorityQueue.maxSize).toBe(4)
  56     expect(rtSize).toBe(priorityQueue.size)
  57     expect(priorityQueue.nodeArray).toStrictEqual([
  58       { data: 3, priority: -1 },
  59       { data: 1, priority: 0 },
  60       { data: 2, priority: 0 },
  61       { data: 3, priority: 0 }
  62     ])
  63     rtSize = priorityQueue.enqueue(1, 1)
  64     expect(priorityQueue.size).toBe(5)
  65     expect(priorityQueue.maxSize).toBe(5)
  66     expect(rtSize).toBe(priorityQueue.size)
  67     expect(priorityQueue.nodeArray).toStrictEqual([
  68       { data: 3, priority: -1 },
  69       { data: 1, priority: 0 },
  70       { data: 2, priority: 0 },
  71       { data: 3, priority: 0 },
  72       { data: 1, priority: 1 }
  73     ])
  74   })
  75
  76   it('Verify k=2 enqueue() behavior', () => {
  77     const priorityQueue = new PriorityQueue(2)
  78     let rtSize = priorityQueue.enqueue(1)
  79     expect(priorityQueue.size).toBe(1)
  80     expect(priorityQueue.maxSize).toBe(1)
  81     expect(rtSize).toBe(priorityQueue.size)
  82     expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }])
  83     rtSize = priorityQueue.enqueue(2)
  84     expect(priorityQueue.size).toBe(2)
  85     expect(priorityQueue.maxSize).toBe(2)
  86     expect(rtSize).toBe(priorityQueue.size)
  87     expect(priorityQueue.nodeArray).toStrictEqual([
  88       { data: 1, priority: 0 },
  89       { data: 2, priority: 0 }
  90     ])
  91     rtSize = priorityQueue.enqueue(3)
  92     expect(priorityQueue.size).toBe(3)
  93     expect(priorityQueue.maxSize).toBe(3)
  94     expect(rtSize).toBe(priorityQueue.size)
  95     expect(priorityQueue.nodeArray).toStrictEqual([
  96       { data: 1, priority: 0 },
  97       { data: 2, priority: 0 },
  98       { data: 3, priority: 0 }
  99     ])
 100     rtSize = priorityQueue.enqueue(3, -1)
 101     expect(priorityQueue.size).toBe(4)
 102     expect(priorityQueue.maxSize).toBe(4)
 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: -1 },
 108       { data: 3, priority: 0 }
 109     ])
 110     rtSize = priorityQueue.enqueue(1, 1)
 111     expect(priorityQueue.size).toBe(5)
 112     expect(priorityQueue.maxSize).toBe(5)
 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       { data: 1, priority: 1 }
 120     ])
 121     rtSize = priorityQueue.enqueue(2, -2)
 122     expect(priorityQueue.size).toBe(6)
 123     expect(priorityQueue.maxSize).toBe(6)
 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: 2, priority: -2 },
 131       { data: 1, priority: 1 }
 132     ])
 133   })
 134
 135   it('Verify dequeue() behavior', () => {
 136     const priorityQueue = new PriorityQueue()
 137     priorityQueue.enqueue(1)
 138     priorityQueue.enqueue(2, -1)
 139     priorityQueue.enqueue(3)
 140     let rtItem = priorityQueue.dequeue()
 141     expect(priorityQueue.size).toBe(2)
 142     expect(priorityQueue.maxSize).toBe(3)
 143     expect(rtItem).toBe(2)
 144     expect(priorityQueue.nodeArray).toStrictEqual([
 145       { data: 1, priority: 0 },
 146       { data: 3, priority: 0 }
 147     ])
 148     rtItem = priorityQueue.dequeue()
 149     expect(priorityQueue.size).toBe(1)
 150     expect(priorityQueue.maxSize).toBe(3)
 151     expect(rtItem).toBe(1)
 152     expect(priorityQueue.nodeArray).toStrictEqual([{ data: 3, priority: 0 }])
 153     rtItem = priorityQueue.dequeue()
 154     expect(priorityQueue.size).toBe(0)
 155     expect(priorityQueue.maxSize).toBe(3)
 156     expect(rtItem).toBe(3)
 157     expect(priorityQueue.nodeArray).toStrictEqual([])
 158   })
 159
 160   it('Verify peekFirst() behavior', () => {
 161     const priorityQueue = new PriorityQueue()
 162     priorityQueue.enqueue(1)
 163     priorityQueue.enqueue(2)
 164     priorityQueue.enqueue(3)
 165     expect(priorityQueue.size).toBe(3)
 166     expect(priorityQueue.peekFirst()).toBe(1)
 167     expect(priorityQueue.size).toBe(3)
 168   })
 169
 170   it('Verify peekLast() behavior', () => {
 171     const priorityQueue = new PriorityQueue()
 172     priorityQueue.enqueue(1)
 173     priorityQueue.enqueue(2)
 174     priorityQueue.enqueue(3)
 175     expect(priorityQueue.size).toBe(3)
 176     expect(priorityQueue.peekLast()).toBe(3)
 177     expect(priorityQueue.size).toBe(3)
 178   })
 179
 180   it('Verify clear() behavior', () => {
 181     const priorityQueue = new PriorityQueue()
 182     priorityQueue.enqueue(1)
 183     priorityQueue.enqueue(2)
 184     priorityQueue.enqueue(3)
 185     expect(priorityQueue.size).toBe(3)
 186     expect(priorityQueue.maxSize).toBe(3)
 187     expect(priorityQueue.nodeArray).toStrictEqual([
 188       { data: 1, priority: 0 },
 189       { data: 2, priority: 0 },
 190       { data: 3, priority: 0 }
 191     ])
 192     priorityQueue.clear()
 193     expect(priorityQueue.size).toBe(0)
 194     expect(priorityQueue.maxSize).toBe(0)
 195     expect(priorityQueue.nodeArray).toStrictEqual([])
 196   })
 197 })