describe('Priority queue test suite', () => {
it('Verify constructor() behavior', () => {
expect(() => new PriorityQueue('')).toThrow(
- new TypeError('k must be an integer')
+ new TypeError('bucketSize must be an integer')
)
expect(() => new PriorityQueue(-1)).toThrow(
- new RangeError('k must be greater than or equal to 1')
+ new RangeError('bucketSize must be greater than or equal to 1')
)
expect(() => new PriorityQueue(0)).toThrow(
- new RangeError('k must be greater than or equal to 1')
+ new RangeError('bucketSize must be greater than or equal to 1')
)
let priorityQueue = new PriorityQueue()
- expect(priorityQueue.k).toBe(Infinity)
+ expect(priorityQueue.bucketSize).toBe(Number.POSITIVE_INFINITY)
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(0)
expect(priorityQueue.maxSize).toBe(0)
expect(priorityQueue.nodeArray).toStrictEqual([])
priorityQueue = new PriorityQueue(2)
- expect(priorityQueue.k).toBe(2)
+ expect(priorityQueue.bucketSize).toBe(2)
+ expect(priorityQueue.buckets).toBe(0)
expect(priorityQueue.size).toBe(0)
expect(priorityQueue.maxSize).toBe(0)
expect(priorityQueue.nodeArray).toStrictEqual([])
})
- it('Verify default k enqueue() behavior', () => {
+ it('Verify default bucketSize enqueue() behavior', () => {
const priorityQueue = new PriorityQueue()
let rtSize = priorityQueue.enqueue(1)
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(1)
expect(priorityQueue.maxSize).toBe(1)
expect(rtSize).toBe(priorityQueue.size)
expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }])
rtSize = priorityQueue.enqueue(2)
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(2)
expect(priorityQueue.maxSize).toBe(2)
expect(rtSize).toBe(priorityQueue.size)
{ data: 2, priority: 0 }
])
rtSize = priorityQueue.enqueue(3)
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(3)
expect(priorityQueue.maxSize).toBe(3)
expect(rtSize).toBe(priorityQueue.size)
{ data: 3, priority: 0 }
])
rtSize = priorityQueue.enqueue(3, -1)
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(4)
expect(priorityQueue.maxSize).toBe(4)
expect(rtSize).toBe(priorityQueue.size)
{ data: 3, priority: 0 }
])
rtSize = priorityQueue.enqueue(1, 1)
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(5)
expect(priorityQueue.maxSize).toBe(5)
expect(rtSize).toBe(priorityQueue.size)
])
})
- it('Verify k=2 enqueue() behavior', () => {
+ it('Verify bucketSize=2 enqueue() behavior', () => {
const priorityQueue = new PriorityQueue(2)
let rtSize = priorityQueue.enqueue(1)
+ expect(priorityQueue.buckets).toBe(0)
expect(priorityQueue.size).toBe(1)
expect(priorityQueue.maxSize).toBe(1)
expect(rtSize).toBe(priorityQueue.size)
expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }])
rtSize = priorityQueue.enqueue(2)
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(2)
expect(priorityQueue.maxSize).toBe(2)
expect(rtSize).toBe(priorityQueue.size)
{ data: 2, priority: 0 }
])
rtSize = priorityQueue.enqueue(3)
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(3)
expect(priorityQueue.maxSize).toBe(3)
expect(rtSize).toBe(priorityQueue.size)
{ data: 3, priority: 0 }
])
rtSize = priorityQueue.enqueue(3, -1)
+ expect(priorityQueue.buckets).toBe(2)
expect(priorityQueue.size).toBe(4)
expect(priorityQueue.maxSize).toBe(4)
expect(rtSize).toBe(priorityQueue.size)
{ data: 3, priority: 0 }
])
rtSize = priorityQueue.enqueue(1, 1)
+ expect(priorityQueue.buckets).toBe(2)
expect(priorityQueue.size).toBe(5)
expect(priorityQueue.maxSize).toBe(5)
expect(rtSize).toBe(priorityQueue.size)
{ data: 1, priority: 1 }
])
rtSize = priorityQueue.enqueue(3, -2)
+ expect(priorityQueue.buckets).toBe(3)
expect(priorityQueue.size).toBe(6)
expect(priorityQueue.maxSize).toBe(6)
expect(rtSize).toBe(priorityQueue.size)
])
})
- it('Verify default k dequeue() behavior', () => {
+ it('Verify default bucketSize dequeue() behavior', () => {
const priorityQueue = new PriorityQueue()
priorityQueue.enqueue(1)
priorityQueue.enqueue(2, -1)
priorityQueue.enqueue(3)
+ expect(priorityQueue.buckets).toBe(1)
+ expect(priorityQueue.size).toBe(3)
+ expect(priorityQueue.maxSize).toBe(3)
let rtItem = priorityQueue.dequeue()
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(2)
expect(priorityQueue.maxSize).toBe(3)
expect(rtItem).toBe(2)
{ data: 3, priority: 0 }
])
rtItem = priorityQueue.dequeue()
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(1)
expect(priorityQueue.maxSize).toBe(3)
expect(rtItem).toBe(1)
expect(priorityQueue.nodeArray).toStrictEqual([{ data: 3, priority: 0 }])
rtItem = priorityQueue.dequeue()
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(0)
expect(priorityQueue.maxSize).toBe(3)
expect(rtItem).toBe(3)
expect(priorityQueue.nodeArray).toStrictEqual([])
})
- it('Verify k=2 dequeue() behavior', () => {
+ it('Verify bucketSize=2 dequeue() behavior', () => {
const priorityQueue = new PriorityQueue(2)
priorityQueue.enqueue(1)
priorityQueue.enqueue(2)
priorityQueue.enqueue(3, -1)
priorityQueue.enqueue(1, 1)
priorityQueue.enqueue(3, -2)
+ expect(priorityQueue.buckets).toBe(3)
+ expect(priorityQueue.size).toBe(6)
+ expect(priorityQueue.maxSize).toBe(6)
let rtItem = priorityQueue.dequeue(3)
+ expect(priorityQueue.buckets).toBe(2)
expect(priorityQueue.size).toBe(5)
expect(priorityQueue.maxSize).toBe(6)
expect(rtItem).toBe(3)
{ data: 1, priority: 1 }
])
rtItem = priorityQueue.dequeue()
+ expect(priorityQueue.buckets).toBe(2)
expect(priorityQueue.size).toBe(4)
expect(priorityQueue.maxSize).toBe(6)
expect(rtItem).toBe(1)
{ data: 1, priority: 1 }
])
rtItem = priorityQueue.dequeue(2)
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(3)
expect(priorityQueue.maxSize).toBe(6)
expect(rtItem).toBe(3)
{ data: 1, priority: 1 }
])
rtItem = priorityQueue.dequeue(2)
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(2)
expect(priorityQueue.maxSize).toBe(6)
expect(rtItem).toBe(1)
{ data: 3, priority: -1 }
])
rtItem = priorityQueue.dequeue(2)
+ expect(priorityQueue.buckets).toBe(0)
expect(priorityQueue.size).toBe(1)
expect(priorityQueue.maxSize).toBe(6)
expect(rtItem).toBe(2)
expect(priorityQueue.nodeArray).toStrictEqual([{ data: 3, priority: -1 }])
rtItem = priorityQueue.dequeue()
+ expect(priorityQueue.buckets).toBe(0)
expect(priorityQueue.size).toBe(0)
expect(priorityQueue.maxSize).toBe(6)
expect(rtItem).toBe(3)
priorityQueue.enqueue(1)
priorityQueue.enqueue(2)
priorityQueue.enqueue(3)
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(3)
expect(priorityQueue.maxSize).toBe(3)
expect(priorityQueue.nodeArray).toStrictEqual([
{ data: 3, priority: 0 }
])
priorityQueue.clear()
+ expect(priorityQueue.buckets).toBe(1)
expect(priorityQueue.size).toBe(0)
expect(priorityQueue.maxSize).toBe(0)
expect(priorityQueue.nodeArray).toStrictEqual([])