[poolifier.git] / tests / priority-queue.test.mjs

import { expect } from 'expect'

import { FixedPriorityQueue } from '../lib/fixed-priority-queue.cjs'
import { FixedQueue } from '../lib/fixed-queue.cjs'
import { PriorityQueue } from '../lib/priority-queue.cjs'
import { defaultBucketSize } from '../lib/utility-types.cjs'

describe('Priority queue test suite', () => {
  it('Verify constructor() behavior', () => {
    expect(() => new PriorityQueue('')).toThrow(
      new TypeError("Invalid bucket size: '' is not an integer")
    )
    expect(() => new PriorityQueue(-1)).toThrow(
      new RangeError('Invalid bucket size: -1 < 0')
    )
    let priorityQueue = new PriorityQueue()
    expect(priorityQueue.bucketSize).toBe(defaultBucketSize)
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(0)
    expect(priorityQueue.maxSize).toBe(0)
    expect(priorityQueue.enablePriority).toBe(false)
    expect(priorityQueue.head).toBeInstanceOf(FixedQueue)
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.head.capacity).toBe(defaultBucketSize)
    expect(priorityQueue.tail).toBeInstanceOf(FixedQueue)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    const bucketSize = 2
    priorityQueue = new PriorityQueue(bucketSize, true)
    expect(priorityQueue.bucketSize).toBe(bucketSize)
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(0)
    expect(priorityQueue.maxSize).toBe(0)
    expect(priorityQueue.enablePriority).toBe(true)
    expect(priorityQueue.head).toBeInstanceOf(FixedPriorityQueue)
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.head.capacity).toBe(bucketSize)
    expect(priorityQueue.tail).toBeInstanceOf(FixedPriorityQueue)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
  })

  it('Verify default bucket size enqueue() behavior', () => {
    const priorityQueue = new PriorityQueue(defaultBucketSize, true)
    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.head.nodeArray).toMatchObject([
      { data: 1, priority: 0 },
    ])
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    rtSize = priorityQueue.enqueue(2)
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(2)
    expect(priorityQueue.maxSize).toBe(2)
    expect(rtSize).toBe(priorityQueue.size)
    expect(priorityQueue.head.nodeArray).toMatchObject([
      { data: 1, priority: 0 },
      { data: 2, priority: 0 },
    ])
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    rtSize = priorityQueue.enqueue(3)
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(3)
    expect(priorityQueue.maxSize).toBe(3)
    expect(rtSize).toBe(priorityQueue.size)
    expect(priorityQueue.head.nodeArray).toMatchObject([
      { data: 1, priority: 0 },
      { data: 2, priority: 0 },
      { data: 3, priority: 0 },
    ])
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    rtSize = priorityQueue.enqueue(3, -1)
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(4)
    expect(priorityQueue.maxSize).toBe(4)
    expect(rtSize).toBe(priorityQueue.size)
    expect(priorityQueue.head.nodeArray).toMatchObject([
      { data: 3, priority: -1 },
      { data: 1, priority: 0 },
      { data: 2, priority: 0 },
      { data: 3, priority: 0 },
    ])
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    rtSize = priorityQueue.enqueue(1, 1)
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(5)
    expect(priorityQueue.maxSize).toBe(5)
    expect(rtSize).toBe(priorityQueue.size)
    expect(priorityQueue.head.nodeArray).toMatchObject([
      { data: 3, priority: -1 },
      { data: 1, priority: 0 },
      { data: 2, priority: 0 },
      { data: 3, priority: 0 },
      { data: 1, priority: 1 },
    ])
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
  })

  it('Verify bucketSize=2 enqueue() behavior', () => {
    const priorityQueue = new PriorityQueue(2, true)
    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.head.nodeArray).toMatchObject([
      { data: 1, priority: 0 },
    ])
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    rtSize = priorityQueue.enqueue(2)
    expect(priorityQueue.buckets).toBe(1)
    expect(priorityQueue.size).toBe(2)
    expect(priorityQueue.maxSize).toBe(2)
    expect(rtSize).toBe(priorityQueue.size)
    expect(priorityQueue.head.nodeArray).toMatchObject([
      { data: 1, priority: 0 },
      { data: 2, priority: 0 },
    ])
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    rtSize = priorityQueue.enqueue(3)
    expect(priorityQueue.buckets).toBe(1)
    expect(priorityQueue.size).toBe(3)
    expect(priorityQueue.maxSize).toBe(3)
    expect(rtSize).toBe(priorityQueue.size)
    expect(priorityQueue.head.nodeArray).toMatchObject([
      { data: 3, priority: 0 },
    ])
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.tail.nodeArray).toMatchObject([
      { data: 1, priority: 0 },
      { data: 2, priority: 0 },
    ])
    expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head)
    expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
    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)
    expect(priorityQueue.head.nodeArray).toMatchObject([
      { data: 3, priority: -1 },
      { data: 3, priority: 0 },
    ])
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.tail.nodeArray).toMatchObject([
      { data: 1, priority: 0 },
      { data: 2, priority: 0 },
    ])
    expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head)
    expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
    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)
    expect(priorityQueue.head.nodeArray).toMatchObject([
      { data: 1, priority: 1 },
    ])
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.tail.nodeArray).toMatchObject([
      { data: 1, priority: 0 },
      { data: 2, priority: 0 },
    ])
    expect(priorityQueue.tail.next.nodeArray).toMatchObject([
      { data: 3, priority: -1 },
      { data: 3, priority: 0 },
    ])
    expect(priorityQueue.tail.next.next).toStrictEqual(priorityQueue.head)
    expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
    expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
    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)
    expect(priorityQueue.head.nodeArray).toMatchObject([
      { data: 3, priority: -2 },
      { data: 1, priority: 1 },
    ])
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.tail.nodeArray).toMatchObject([
      { data: 1, priority: 0 },
      { data: 2, priority: 0 },
    ])
    expect(priorityQueue.tail.next.nodeArray).toMatchObject([
      { data: 3, priority: -1 },
      { data: 3, priority: 0 },
    ])
    expect(priorityQueue.tail.next.next).toStrictEqual(priorityQueue.head)
    expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
    expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
  })

  it('Verify default bucket size dequeue() behavior', () => {
    const priorityQueue = new PriorityQueue(defaultBucketSize, true)
    priorityQueue.enqueue(1)
    priorityQueue.enqueue(2, -1)
    priorityQueue.enqueue(3)
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(3)
    expect(priorityQueue.maxSize).toBe(3)
    expect(priorityQueue.tail.empty()).toBe(false)
    expect(priorityQueue.tail.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    let rtItem = priorityQueue.dequeue()
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(2)
    expect(priorityQueue.maxSize).toBe(3)
    expect(rtItem).toBe(2)
    expect(priorityQueue.tail.empty()).toBe(false)
    expect(priorityQueue.tail.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    rtItem = priorityQueue.dequeue()
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(1)
    expect(priorityQueue.maxSize).toBe(3)
    expect(rtItem).toBe(1)
    expect(priorityQueue.tail.empty()).toBe(false)
    expect(priorityQueue.tail.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    rtItem = priorityQueue.dequeue()
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(0)
    expect(priorityQueue.maxSize).toBe(3)
    expect(rtItem).toBe(3)
    expect(priorityQueue.tail.empty()).toBe(true)
    expect(priorityQueue.tail.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
  })

  it('Verify bucketSize=2 dequeue() behavior', () => {
    const priorityQueue = new PriorityQueue(2, true)
    priorityQueue.enqueue(1)
    priorityQueue.enqueue(2)
    priorityQueue.enqueue(3)
    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)
    expect(priorityQueue.tail.empty()).toBe(false)
    expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
    expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
    let rtItem = priorityQueue.dequeue(3)
    expect(priorityQueue.buckets).toBe(2)
    expect(priorityQueue.size).toBe(5)
    expect(priorityQueue.maxSize).toBe(6)
    expect(rtItem).toBe(3)
    expect(priorityQueue.tail.empty()).toBe(false)
    expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
    expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
    rtItem = priorityQueue.dequeue()
    expect(priorityQueue.buckets).toBe(2)
    expect(priorityQueue.size).toBe(4)
    expect(priorityQueue.maxSize).toBe(6)
    expect(rtItem).toBe(1)
    expect(priorityQueue.tail.empty()).toBe(false)
    expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
    expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
    rtItem = priorityQueue.dequeue(2)
    expect(priorityQueue.buckets).toBe(1)
    expect(priorityQueue.size).toBe(3)
    expect(priorityQueue.maxSize).toBe(6)
    expect(rtItem).toBe(3)
    expect(priorityQueue.tail.empty()).toBe(false)
    expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
    expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
    rtItem = priorityQueue.dequeue(2)
    expect(priorityQueue.buckets).toBe(1)
    expect(priorityQueue.size).toBe(2)
    expect(priorityQueue.maxSize).toBe(6)
    expect(rtItem).toBe(3)
    expect(priorityQueue.tail.empty()).toBe(false)
    expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
    expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
    rtItem = priorityQueue.dequeue(2)
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(1)
    expect(priorityQueue.maxSize).toBe(6)
    expect(rtItem).toBe(1)
    expect(priorityQueue.tail.empty()).toBe(false)
    expect(priorityQueue.tail.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    rtItem = priorityQueue.dequeue()
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(0)
    expect(priorityQueue.maxSize).toBe(6)
    expect(rtItem).toBe(2)
    expect(priorityQueue.tail.empty()).toBe(true)
    expect(priorityQueue.tail.next).toBe(undefined)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
  })

  it('Verify enablePriority setter behavior', () => {
    const priorityQueue = new PriorityQueue(2)
    expect(priorityQueue.enablePriority).toBe(false)
    priorityQueue.enqueue(1)
    priorityQueue.enqueue(2)
    priorityQueue.enqueue(3)
    priorityQueue.enqueue(4)
    let buckets = 0
    let node = priorityQueue.tail
    while (node != null) {
      expect(node).toBeInstanceOf(FixedQueue)
      node = node.next
      ++buckets
    }
    expect(buckets).toBe(2)
    priorityQueue.enablePriority = true
    expect(priorityQueue.enablePriority).toBe(true)
    buckets = 0
    node = priorityQueue.tail
    while (node != null) {
      expect(node).toBeInstanceOf(FixedPriorityQueue)
      node = node.next
      ++buckets
    }
    expect(buckets).toBe(2)
  })

  it('Verify iterator behavior', () => {
    const priorityQueue = new PriorityQueue(2)
    priorityQueue.enqueue(1)
    priorityQueue.enqueue(2)
    priorityQueue.enqueue(3)
    let i = 1
    for (const value of priorityQueue) {
      expect(value).toBe(i)
      ++i
    }
  })

  it('Verify clear() behavior', () => {
    const priorityQueue = new PriorityQueue(2)
    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.head.empty()).toBe(false)
    expect(priorityQueue.tail.empty()).toBe(false)
    expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
    priorityQueue.clear()
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(0)
    expect(priorityQueue.maxSize).toBe(0)
    expect(priorityQueue.head.empty()).toBe(true)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
  })
})
Commit	Line	Data
bd8b441c JB	1	import { expect } from 'expect'
bd8b441c JB	2
9df282a0	3	import { FixedPriorityQueue } from '../lib/fixed-priority-queue.cjs'
097dea68 JB	4	import { FixedQueue } from '../lib/fixed-queue.cjs'
	5	import { PriorityQueue } from '../lib/priority-queue.cjs'
	6	import { defaultBucketSize } from '../lib/utility-types.cjs'
bd8b441c	7
95d1a734	8	describe('Priority queue test suite', () => {
e41b0271	9	it('Verify constructor() behavior', () => {
e75373e6	10	expect(() => new PriorityQueue('')).toThrow(
579aa5bd	11	new TypeError("Invalid bucket size: '' is not an integer")
e75373e6 JB	12	)
e75373e6 JB	13	expect(() => new PriorityQueue(-1)).toThrow(
579aa5bd	14	new RangeError('Invalid bucket size: -1 < 0')
e75373e6 JB	15	)
	16	let priorityQueue = new PriorityQueue()
	17	expect(priorityQueue.bucketSize).toBe(defaultBucketSize)
	18	expect(priorityQueue.buckets).toBe(0)
e41b0271 JB	19	expect(priorityQueue.size).toBe(0)
e41b0271 JB	20	expect(priorityQueue.maxSize).toBe(0)
fcfc3353	21	expect(priorityQueue.enablePriority).toBe(false)
097dea68	22	expect(priorityQueue.head).toBeInstanceOf(FixedQueue)
9df282a0 JB	23	expect(priorityQueue.head.next).toBe(undefined)
9df282a0 JB	24	expect(priorityQueue.head.capacity).toBe(defaultBucketSize)
097dea68	25	expect(priorityQueue.tail).toBeInstanceOf(FixedQueue)
9df282a0	26	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
e75373e6	27	const bucketSize = 2
fcfc3353	28	priorityQueue = new PriorityQueue(bucketSize, true)
e75373e6 JB	29	expect(priorityQueue.bucketSize).toBe(bucketSize)
	30	expect(priorityQueue.buckets).toBe(0)
	31	expect(priorityQueue.size).toBe(0)
	32	expect(priorityQueue.maxSize).toBe(0)
fcfc3353	33	expect(priorityQueue.enablePriority).toBe(true)
e75373e6 JB	34	expect(priorityQueue.head).toBeInstanceOf(FixedPriorityQueue)
	35	expect(priorityQueue.head.next).toBe(undefined)
	36	expect(priorityQueue.head.capacity).toBe(bucketSize)
	37	expect(priorityQueue.tail).toBeInstanceOf(FixedPriorityQueue)
	38	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
e41b0271 JB	39	})
e41b0271 JB	40
9df282a0	41	it('Verify default bucket size enqueue() behavior', () => {
fcfc3353	42	const priorityQueue = new PriorityQueue(defaultBucketSize, true)
bd8b441c	43	let rtSize = priorityQueue.enqueue(1)
e75373e6	44	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	45	expect(priorityQueue.size).toBe(1)
	46	expect(priorityQueue.maxSize).toBe(1)
	47	expect(rtSize).toBe(priorityQueue.size)
9df282a0	48	expect(priorityQueue.head.nodeArray).toMatchObject([
3a502712	49	{ data: 1, priority: 0 },
9df282a0 JB	50	])
	51	expect(priorityQueue.head.next).toBe(undefined)
	52	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c	53	rtSize = priorityQueue.enqueue(2)
e75373e6	54	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	55	expect(priorityQueue.size).toBe(2)
	56	expect(priorityQueue.maxSize).toBe(2)
	57	expect(rtSize).toBe(priorityQueue.size)
9df282a0	58	expect(priorityQueue.head.nodeArray).toMatchObject([
bd8b441c	59	{ data: 1, priority: 0 },
3a502712	60	{ data: 2, priority: 0 },
bd8b441c	61	])
9df282a0 JB	62	expect(priorityQueue.head.next).toBe(undefined)
9df282a0 JB	63	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c	64	rtSize = priorityQueue.enqueue(3)
e75373e6	65	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	66	expect(priorityQueue.size).toBe(3)
	67	expect(priorityQueue.maxSize).toBe(3)
	68	expect(rtSize).toBe(priorityQueue.size)
9df282a0	69	expect(priorityQueue.head.nodeArray).toMatchObject([
bd8b441c JB	70	{ data: 1, priority: 0 },
bd8b441c JB	71	{ data: 2, priority: 0 },
3a502712	72	{ data: 3, priority: 0 },
bd8b441c	73	])
9df282a0 JB	74	expect(priorityQueue.head.next).toBe(undefined)
9df282a0 JB	75	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c	76	rtSize = priorityQueue.enqueue(3, -1)
e75373e6	77	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	78	expect(priorityQueue.size).toBe(4)
	79	expect(priorityQueue.maxSize).toBe(4)
	80	expect(rtSize).toBe(priorityQueue.size)
9df282a0	81	expect(priorityQueue.head.nodeArray).toMatchObject([
bd8b441c JB	82	{ data: 3, priority: -1 },
	83	{ data: 1, priority: 0 },
	84	{ data: 2, priority: 0 },
3a502712	85	{ data: 3, priority: 0 },
bd8b441c	86	])
9df282a0 JB	87	expect(priorityQueue.head.next).toBe(undefined)
9df282a0 JB	88	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c	89	rtSize = priorityQueue.enqueue(1, 1)
e75373e6	90	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	91	expect(priorityQueue.size).toBe(5)
	92	expect(priorityQueue.maxSize).toBe(5)
	93	expect(rtSize).toBe(priorityQueue.size)
9df282a0	94	expect(priorityQueue.head.nodeArray).toMatchObject([
bd8b441c JB	95	{ data: 3, priority: -1 },
	96	{ data: 1, priority: 0 },
	97	{ data: 2, priority: 0 },
	98	{ data: 3, priority: 0 },
3a502712	99	{ data: 1, priority: 1 },
bd8b441c	100	])
9df282a0 JB	101	expect(priorityQueue.head.next).toBe(undefined)
9df282a0 JB	102	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c JB	103	})
bd8b441c JB	104
2107bc57	105	it('Verify bucketSize=2 enqueue() behavior', () => {
fcfc3353	106	const priorityQueue = new PriorityQueue(2, true)
e41b0271	107	let rtSize = priorityQueue.enqueue(1)
e75373e6	108	expect(priorityQueue.buckets).toBe(0)
e41b0271 JB	109	expect(priorityQueue.size).toBe(1)
	110	expect(priorityQueue.maxSize).toBe(1)
	111	expect(rtSize).toBe(priorityQueue.size)
9df282a0	112	expect(priorityQueue.head.nodeArray).toMatchObject([
3a502712	113	{ data: 1, priority: 0 },
9df282a0 JB	114	])
	115	expect(priorityQueue.head.next).toBe(undefined)
	116	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
e41b0271	117	rtSize = priorityQueue.enqueue(2)
e75373e6	118	expect(priorityQueue.buckets).toBe(1)
e41b0271 JB	119	expect(priorityQueue.size).toBe(2)
	120	expect(priorityQueue.maxSize).toBe(2)
	121	expect(rtSize).toBe(priorityQueue.size)
9df282a0	122	expect(priorityQueue.head.nodeArray).toMatchObject([
e41b0271	123	{ data: 1, priority: 0 },
3a502712	124	{ data: 2, priority: 0 },
e41b0271	125	])
9df282a0 JB	126	expect(priorityQueue.head.next).toBe(undefined)
9df282a0 JB	127	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
e41b0271	128	rtSize = priorityQueue.enqueue(3)
e75373e6	129	expect(priorityQueue.buckets).toBe(1)
e41b0271 JB	130	expect(priorityQueue.size).toBe(3)
	131	expect(priorityQueue.maxSize).toBe(3)
	132	expect(rtSize).toBe(priorityQueue.size)
9df282a0	133	expect(priorityQueue.head.nodeArray).toMatchObject([
3a502712	134	{ data: 3, priority: 0 },
e41b0271	135	])
9df282a0 JB	136	expect(priorityQueue.head.next).toBe(undefined)
	137	expect(priorityQueue.tail.nodeArray).toMatchObject([
	138	{ data: 1, priority: 0 },
3a502712	139	{ data: 2, priority: 0 },
9df282a0 JB	140	])
9df282a0 JB	141	expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head)
017f9985	142	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
e41b0271	143	rtSize = priorityQueue.enqueue(3, -1)
e75373e6	144	expect(priorityQueue.buckets).toBe(2)
e41b0271 JB	145	expect(priorityQueue.size).toBe(4)
	146	expect(priorityQueue.maxSize).toBe(4)
	147	expect(rtSize).toBe(priorityQueue.size)
9df282a0	148	expect(priorityQueue.head.nodeArray).toMatchObject([
e41b0271	149	{ data: 3, priority: -1 },
3a502712	150	{ data: 3, priority: 0 },
e41b0271	151	])
9df282a0 JB	152	expect(priorityQueue.head.next).toBe(undefined)
	153	expect(priorityQueue.tail.nodeArray).toMatchObject([
	154	{ data: 1, priority: 0 },
3a502712	155	{ data: 2, priority: 0 },
9df282a0 JB	156	])
9df282a0 JB	157	expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head)
017f9985	158	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
e41b0271	159	rtSize = priorityQueue.enqueue(1, 1)
e75373e6	160	expect(priorityQueue.buckets).toBe(2)
e41b0271 JB	161	expect(priorityQueue.size).toBe(5)
	162	expect(priorityQueue.maxSize).toBe(5)
	163	expect(rtSize).toBe(priorityQueue.size)
9df282a0	164	expect(priorityQueue.head.nodeArray).toMatchObject([
3a502712	165	{ data: 1, priority: 1 },
9df282a0 JB	166	])
	167	expect(priorityQueue.head.next).toBe(undefined)
	168	expect(priorityQueue.tail.nodeArray).toMatchObject([
e41b0271	169	{ data: 1, priority: 0 },
3a502712	170	{ data: 2, priority: 0 },
9df282a0	171	])
9df282a0	172	expect(priorityQueue.tail.next.nodeArray).toMatchObject([
e41b0271	173	{ data: 3, priority: -1 },
3a502712	174	{ data: 3, priority: 0 },
e41b0271	175	])
017f9985 JB	176	expect(priorityQueue.tail.next.next).toStrictEqual(priorityQueue.head)
	177	expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
	178	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
a4092a15	179	rtSize = priorityQueue.enqueue(3, -2)
e75373e6	180	expect(priorityQueue.buckets).toBe(3)
e41b0271 JB	181	expect(priorityQueue.size).toBe(6)
	182	expect(priorityQueue.maxSize).toBe(6)
	183	expect(rtSize).toBe(priorityQueue.size)
9df282a0	184	expect(priorityQueue.head.nodeArray).toMatchObject([
a4092a15	185	{ data: 3, priority: -2 },
3a502712	186	{ data: 1, priority: 1 },
e41b0271	187	])
9df282a0 JB	188	expect(priorityQueue.head.next).toBe(undefined)
	189	expect(priorityQueue.tail.nodeArray).toMatchObject([
	190	{ data: 1, priority: 0 },
3a502712	191	{ data: 2, priority: 0 },
9df282a0	192	])
9df282a0 JB	193	expect(priorityQueue.tail.next.nodeArray).toMatchObject([
9df282a0 JB	194	{ data: 3, priority: -1 },
3a502712	195	{ data: 3, priority: 0 },
9df282a0	196	])
017f9985 JB	197	expect(priorityQueue.tail.next.next).toStrictEqual(priorityQueue.head)
	198	expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
	199	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
e41b0271 JB	200	})
e41b0271 JB	201
9df282a0	202	it('Verify default bucket size dequeue() behavior', () => {
fcfc3353	203	const priorityQueue = new PriorityQueue(defaultBucketSize, true)
bd8b441c JB	204	priorityQueue.enqueue(1)
	205	priorityQueue.enqueue(2, -1)
	206	priorityQueue.enqueue(3)
e75373e6	207	expect(priorityQueue.buckets).toBe(0)
0d4e88b3 JB	208	expect(priorityQueue.size).toBe(3)
0d4e88b3 JB	209	expect(priorityQueue.maxSize).toBe(3)
9df282a0 JB	210	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	211	expect(priorityQueue.tail.next).toBe(undefined)
017f9985	212	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c	213	let rtItem = priorityQueue.dequeue()
e75373e6	214	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	215	expect(priorityQueue.size).toBe(2)
	216	expect(priorityQueue.maxSize).toBe(3)
	217	expect(rtItem).toBe(2)
9df282a0 JB	218	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	219	expect(priorityQueue.tail.next).toBe(undefined)
017f9985	220	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c	221	rtItem = priorityQueue.dequeue()
e75373e6	222	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	223	expect(priorityQueue.size).toBe(1)
	224	expect(priorityQueue.maxSize).toBe(3)
	225	expect(rtItem).toBe(1)
9df282a0 JB	226	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	227	expect(priorityQueue.tail.next).toBe(undefined)
017f9985	228	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c	229	rtItem = priorityQueue.dequeue()
e75373e6	230	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	231	expect(priorityQueue.size).toBe(0)
	232	expect(priorityQueue.maxSize).toBe(3)
	233	expect(rtItem).toBe(3)
9df282a0 JB	234	expect(priorityQueue.tail.empty()).toBe(true)
9df282a0 JB	235	expect(priorityQueue.tail.next).toBe(undefined)
017f9985	236	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c JB	237	})
bd8b441c JB	238
2107bc57	239	it('Verify bucketSize=2 dequeue() behavior', () => {
fcfc3353	240	const priorityQueue = new PriorityQueue(2, true)
a4092a15 JB	241	priorityQueue.enqueue(1)
	242	priorityQueue.enqueue(2)
	243	priorityQueue.enqueue(3)
	244	priorityQueue.enqueue(3, -1)
	245	priorityQueue.enqueue(1, 1)
	246	priorityQueue.enqueue(3, -2)
e75373e6	247	expect(priorityQueue.buckets).toBe(3)
0d4e88b3 JB	248	expect(priorityQueue.size).toBe(6)
0d4e88b3 JB	249	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	250	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	251	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
7e5b3ca1	252	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
a4092a15	253	let rtItem = priorityQueue.dequeue(3)
e75373e6	254	expect(priorityQueue.buckets).toBe(2)
a4092a15 JB	255	expect(priorityQueue.size).toBe(5)
	256	expect(priorityQueue.maxSize).toBe(6)
	257	expect(rtItem).toBe(3)
9df282a0 JB	258	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	259	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
7e5b3ca1	260	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
a4092a15	261	rtItem = priorityQueue.dequeue()
e75373e6	262	expect(priorityQueue.buckets).toBe(2)
a4092a15 JB	263	expect(priorityQueue.size).toBe(4)
	264	expect(priorityQueue.maxSize).toBe(6)
	265	expect(rtItem).toBe(1)
9df282a0 JB	266	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	267	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
7e5b3ca1	268	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
a4092a15	269	rtItem = priorityQueue.dequeue(2)
e75373e6	270	expect(priorityQueue.buckets).toBe(1)
a4092a15 JB	271	expect(priorityQueue.size).toBe(3)
	272	expect(priorityQueue.maxSize).toBe(6)
	273	expect(rtItem).toBe(3)
9df282a0 JB	274	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	275	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
7e5b3ca1	276	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
a4092a15	277	rtItem = priorityQueue.dequeue(2)
e75373e6	278	expect(priorityQueue.buckets).toBe(1)
a4092a15 JB	279	expect(priorityQueue.size).toBe(2)
a4092a15 JB	280	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	281	expect(rtItem).toBe(3)
	282	expect(priorityQueue.tail.empty()).toBe(false)
	283	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
7e5b3ca1	284	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
a4092a15	285	rtItem = priorityQueue.dequeue(2)
e75373e6	286	expect(priorityQueue.buckets).toBe(0)
a4092a15 JB	287	expect(priorityQueue.size).toBe(1)
a4092a15 JB	288	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	289	expect(rtItem).toBe(1)
9df282a0 JB	290	expect(priorityQueue.tail.empty()).toBe(false)
017f9985	291	expect(priorityQueue.tail.next).toBe(undefined)
7e5b3ca1	292	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
a4092a15	293	rtItem = priorityQueue.dequeue()
e75373e6	294	expect(priorityQueue.buckets).toBe(0)
a4092a15 JB	295	expect(priorityQueue.size).toBe(0)
a4092a15 JB	296	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	297	expect(rtItem).toBe(2)
	298	expect(priorityQueue.tail.empty()).toBe(true)
	299	expect(priorityQueue.tail.next).toBe(undefined)
7e5b3ca1	300	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c	301	})
fcfc3353 JB	302
	303	it('Verify enablePriority setter behavior', () => {
	304	const priorityQueue = new PriorityQueue(2)
	305	expect(priorityQueue.enablePriority).toBe(false)
	306	priorityQueue.enqueue(1)
	307	priorityQueue.enqueue(2)
	308	priorityQueue.enqueue(3)
	309	priorityQueue.enqueue(4)
	310	let buckets = 0
	311	let node = priorityQueue.tail
	312	while (node != null) {
097dea68	313	expect(node).toBeInstanceOf(FixedQueue)
fcfc3353 JB	314	node = node.next
	315	++buckets
	316	}
	317	expect(buckets).toBe(2)
	318	priorityQueue.enablePriority = true
	319	expect(priorityQueue.enablePriority).toBe(true)
097dea68	320	buckets = 0
fcfc3353 JB	321	node = priorityQueue.tail
fcfc3353 JB	322	while (node != null) {
097dea68	323	expect(node).toBeInstanceOf(FixedPriorityQueue)
fcfc3353	324	node = node.next
097dea68	325	++buckets
fcfc3353	326	}
097dea68	327	expect(buckets).toBe(2)
fcfc3353	328	})
bd8b441c	329
95d1a734	330	it('Verify iterator behavior', () => {
9df282a0	331	const priorityQueue = new PriorityQueue(2)
95d1a734 JB	332	priorityQueue.enqueue(1)
	333	priorityQueue.enqueue(2)
	334	priorityQueue.enqueue(3)
	335	let i = 1
	336	for (const value of priorityQueue) {
	337	expect(value).toBe(i)
	338	++i
	339	}
	340	})
	341
bd8b441c	342	it('Verify clear() behavior', () => {
9df282a0	343	const priorityQueue = new PriorityQueue(2)
bd8b441c JB	344	priorityQueue.enqueue(1)
	345	priorityQueue.enqueue(2)
	346	priorityQueue.enqueue(3)
e75373e6	347	expect(priorityQueue.buckets).toBe(1)
bd8b441c JB	348	expect(priorityQueue.size).toBe(3)
bd8b441c JB	349	expect(priorityQueue.maxSize).toBe(3)
9df282a0 JB	350	expect(priorityQueue.head.empty()).toBe(false)
	351	expect(priorityQueue.tail.empty()).toBe(false)
	352	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
bd8b441c	353	priorityQueue.clear()
e75373e6	354	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	355	expect(priorityQueue.size).toBe(0)
bd8b441c JB	356	expect(priorityQueue.maxSize).toBe(0)
9df282a0 JB	357	expect(priorityQueue.head.empty()).toBe(true)
9df282a0 JB	358	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c JB	359	})
bd8b441c JB	360	})