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

import { expect } from 'expect'

import { FixedPriorityQueue } from '../lib/fixed-priority-queue.cjs'
import { defaultBucketSize, PriorityQueue } from '../lib/priority-queue.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.head).toBeInstanceOf(FixedPriorityQueue)
    expect(priorityQueue.head.next).toBe(undefined)
    expect(priorityQueue.head.capacity).toBe(defaultBucketSize)
    expect(priorityQueue.tail).toBeInstanceOf(FixedPriorityQueue)
    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
    const bucketSize = 2
    priorityQueue = new PriorityQueue(bucketSize)
    expect(priorityQueue.bucketSize).toBe(bucketSize)
    expect(priorityQueue.buckets).toBe(0)
    expect(priorityQueue.size).toBe(0)
    expect(priorityQueue.maxSize).toBe(0)
    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()
    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)
    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)
    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)
    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).not.toStrictEqual(priorityQueue.head)
    expect(priorityQueue.tail.next.nodeArray).toMatchObject([
      { data: 3, priority: -1 },
      { data: 3, priority: 0 }
    ])
    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).not.toStrictEqual(priorityQueue.head)
    expect(priorityQueue.tail.next.nodeArray).toMatchObject([
      { data: 3, priority: -1 },
      { data: 3, priority: 0 }
    ])
  })

  it('Verify default bucket size dequeue() behavior', () => {
    const priorityQueue = new PriorityQueue()
    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)
    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)
    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)
    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)
  })

  it('Verify bucketSize=2 dequeue() behavior', () => {
    const priorityQueue = new PriorityQueue(2)
    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)
    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)
    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)
    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)
    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)
    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).toBeInstanceOf(FixedPriorityQueue)
    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)
  })

  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 JB	3	import { FixedPriorityQueue } from '../lib/fixed-priority-queue.cjs'
9df282a0 JB	4	import { defaultBucketSize, PriorityQueue } from '../lib/priority-queue.cjs'
bd8b441c	5
95d1a734	6	describe('Priority queue test suite', () => {
e41b0271	7	it('Verify constructor() behavior', () => {
e75373e6	8	expect(() => new PriorityQueue('')).toThrow(
579aa5bd	9	new TypeError("Invalid bucket size: '' is not an integer")
e75373e6 JB	10	)
e75373e6 JB	11	expect(() => new PriorityQueue(-1)).toThrow(
579aa5bd	12	new RangeError('Invalid bucket size: -1 < 0')
e75373e6 JB	13	)
	14	let priorityQueue = new PriorityQueue()
	15	expect(priorityQueue.bucketSize).toBe(defaultBucketSize)
	16	expect(priorityQueue.buckets).toBe(0)
e41b0271 JB	17	expect(priorityQueue.size).toBe(0)
e41b0271 JB	18	expect(priorityQueue.maxSize).toBe(0)
9df282a0 JB	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)
e75373e6 JB	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)
e41b0271 JB	35	})
e41b0271 JB	36
9df282a0	37	it('Verify default bucket size enqueue() behavior', () => {
bd8b441c JB	38	const priorityQueue = new PriorityQueue()
bd8b441c JB	39	let rtSize = priorityQueue.enqueue(1)
e75373e6	40	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	41	expect(priorityQueue.size).toBe(1)
	42	expect(priorityQueue.maxSize).toBe(1)
	43	expect(rtSize).toBe(priorityQueue.size)
9df282a0 JB	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)
bd8b441c	49	rtSize = priorityQueue.enqueue(2)
e75373e6	50	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	51	expect(priorityQueue.size).toBe(2)
	52	expect(priorityQueue.maxSize).toBe(2)
	53	expect(rtSize).toBe(priorityQueue.size)
9df282a0	54	expect(priorityQueue.head.nodeArray).toMatchObject([
bd8b441c JB	55	{ data: 1, priority: 0 },
	56	{ data: 2, priority: 0 }
	57	])
9df282a0 JB	58	expect(priorityQueue.head.next).toBe(undefined)
9df282a0 JB	59	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c	60	rtSize = priorityQueue.enqueue(3)
e75373e6	61	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	62	expect(priorityQueue.size).toBe(3)
	63	expect(priorityQueue.maxSize).toBe(3)
	64	expect(rtSize).toBe(priorityQueue.size)
9df282a0	65	expect(priorityQueue.head.nodeArray).toMatchObject([
bd8b441c JB	66	{ data: 1, priority: 0 },
	67	{ data: 2, priority: 0 },
	68	{ data: 3, priority: 0 }
	69	])
9df282a0 JB	70	expect(priorityQueue.head.next).toBe(undefined)
9df282a0 JB	71	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c	72	rtSize = priorityQueue.enqueue(3, -1)
e75373e6	73	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	74	expect(priorityQueue.size).toBe(4)
	75	expect(priorityQueue.maxSize).toBe(4)
	76	expect(rtSize).toBe(priorityQueue.size)
9df282a0	77	expect(priorityQueue.head.nodeArray).toMatchObject([
bd8b441c JB	78	{ data: 3, priority: -1 },
	79	{ data: 1, priority: 0 },
	80	{ data: 2, priority: 0 },
	81	{ data: 3, priority: 0 }
	82	])
9df282a0 JB	83	expect(priorityQueue.head.next).toBe(undefined)
9df282a0 JB	84	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c	85	rtSize = priorityQueue.enqueue(1, 1)
e75373e6	86	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	87	expect(priorityQueue.size).toBe(5)
	88	expect(priorityQueue.maxSize).toBe(5)
	89	expect(rtSize).toBe(priorityQueue.size)
9df282a0	90	expect(priorityQueue.head.nodeArray).toMatchObject([
bd8b441c JB	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	])
9df282a0 JB	97	expect(priorityQueue.head.next).toBe(undefined)
9df282a0 JB	98	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c JB	99	})
bd8b441c JB	100
2107bc57	101	it('Verify bucketSize=2 enqueue() behavior', () => {
e41b0271 JB	102	const priorityQueue = new PriorityQueue(2)
e41b0271 JB	103	let rtSize = priorityQueue.enqueue(1)
e75373e6	104	expect(priorityQueue.buckets).toBe(0)
e41b0271 JB	105	expect(priorityQueue.size).toBe(1)
	106	expect(priorityQueue.maxSize).toBe(1)
	107	expect(rtSize).toBe(priorityQueue.size)
9df282a0 JB	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)
e41b0271	113	rtSize = priorityQueue.enqueue(2)
e75373e6	114	expect(priorityQueue.buckets).toBe(1)
e41b0271 JB	115	expect(priorityQueue.size).toBe(2)
	116	expect(priorityQueue.maxSize).toBe(2)
	117	expect(rtSize).toBe(priorityQueue.size)
9df282a0	118	expect(priorityQueue.head.nodeArray).toMatchObject([
e41b0271 JB	119	{ data: 1, priority: 0 },
	120	{ data: 2, priority: 0 }
	121	])
9df282a0 JB	122	expect(priorityQueue.head.next).toBe(undefined)
9df282a0 JB	123	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
e41b0271	124	rtSize = priorityQueue.enqueue(3)
e75373e6	125	expect(priorityQueue.buckets).toBe(1)
e41b0271 JB	126	expect(priorityQueue.size).toBe(3)
	127	expect(priorityQueue.maxSize).toBe(3)
	128	expect(rtSize).toBe(priorityQueue.size)
9df282a0	129	expect(priorityQueue.head.nodeArray).toMatchObject([
e41b0271 JB	130	{ data: 3, priority: 0 }
e41b0271 JB	131	])
9df282a0 JB	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)
e41b0271	138	rtSize = priorityQueue.enqueue(3, -1)
e75373e6	139	expect(priorityQueue.buckets).toBe(2)
e41b0271 JB	140	expect(priorityQueue.size).toBe(4)
	141	expect(priorityQueue.maxSize).toBe(4)
	142	expect(rtSize).toBe(priorityQueue.size)
9df282a0	143	expect(priorityQueue.head.nodeArray).toMatchObject([
e41b0271 JB	144	{ data: 3, priority: -1 },
	145	{ data: 3, priority: 0 }
	146	])
9df282a0 JB	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)
e41b0271	153	rtSize = priorityQueue.enqueue(1, 1)
e75373e6	154	expect(priorityQueue.buckets).toBe(2)
e41b0271 JB	155	expect(priorityQueue.size).toBe(5)
	156	expect(priorityQueue.maxSize).toBe(5)
	157	expect(rtSize).toBe(priorityQueue.size)
9df282a0 JB	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([
e41b0271	163	{ data: 1, priority: 0 },
9df282a0 JB	164	{ data: 2, priority: 0 }
	165	])
	166	expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
	167	expect(priorityQueue.tail.next.nodeArray).toMatchObject([
e41b0271	168	{ data: 3, priority: -1 },
9df282a0	169	{ data: 3, priority: 0 }
e41b0271	170	])
a4092a15	171	rtSize = priorityQueue.enqueue(3, -2)
e75373e6	172	expect(priorityQueue.buckets).toBe(3)
e41b0271 JB	173	expect(priorityQueue.size).toBe(6)
	174	expect(priorityQueue.maxSize).toBe(6)
	175	expect(rtSize).toBe(priorityQueue.size)
9df282a0	176	expect(priorityQueue.head.nodeArray).toMatchObject([
a4092a15	177	{ data: 3, priority: -2 },
e41b0271 JB	178	{ data: 1, priority: 1 }
e41b0271 JB	179	])
9df282a0 JB	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	])
e41b0271 JB	190	})
e41b0271 JB	191
9df282a0	192	it('Verify default bucket size dequeue() behavior', () => {
bd8b441c JB	193	const priorityQueue = new PriorityQueue()
	194	priorityQueue.enqueue(1)
	195	priorityQueue.enqueue(2, -1)
	196	priorityQueue.enqueue(3)
e75373e6	197	expect(priorityQueue.buckets).toBe(0)
0d4e88b3 JB	198	expect(priorityQueue.size).toBe(3)
0d4e88b3 JB	199	expect(priorityQueue.maxSize).toBe(3)
9df282a0 JB	200	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	201	expect(priorityQueue.tail.next).toBe(undefined)
bd8b441c	202	let rtItem = priorityQueue.dequeue()
e75373e6	203	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	204	expect(priorityQueue.size).toBe(2)
	205	expect(priorityQueue.maxSize).toBe(3)
	206	expect(rtItem).toBe(2)
9df282a0 JB	207	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	208	expect(priorityQueue.tail.next).toBe(undefined)
bd8b441c	209	rtItem = priorityQueue.dequeue()
e75373e6	210	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	211	expect(priorityQueue.size).toBe(1)
	212	expect(priorityQueue.maxSize).toBe(3)
	213	expect(rtItem).toBe(1)
9df282a0 JB	214	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	215	expect(priorityQueue.tail.next).toBe(undefined)
bd8b441c	216	rtItem = priorityQueue.dequeue()
e75373e6	217	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	218	expect(priorityQueue.size).toBe(0)
	219	expect(priorityQueue.maxSize).toBe(3)
	220	expect(rtItem).toBe(3)
9df282a0 JB	221	expect(priorityQueue.tail.empty()).toBe(true)
9df282a0 JB	222	expect(priorityQueue.tail.next).toBe(undefined)
bd8b441c JB	223	})
bd8b441c JB	224
2107bc57	225	it('Verify bucketSize=2 dequeue() behavior', () => {
a4092a15 JB	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)
e75373e6	233	expect(priorityQueue.buckets).toBe(3)
0d4e88b3 JB	234	expect(priorityQueue.size).toBe(6)
0d4e88b3 JB	235	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	236	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	237	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	238	let rtItem = priorityQueue.dequeue(3)
e75373e6	239	expect(priorityQueue.buckets).toBe(2)
a4092a15 JB	240	expect(priorityQueue.size).toBe(5)
	241	expect(priorityQueue.maxSize).toBe(6)
	242	expect(rtItem).toBe(3)
9df282a0 JB	243	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	244	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	245	rtItem = priorityQueue.dequeue()
e75373e6	246	expect(priorityQueue.buckets).toBe(2)
a4092a15 JB	247	expect(priorityQueue.size).toBe(4)
	248	expect(priorityQueue.maxSize).toBe(6)
	249	expect(rtItem).toBe(1)
9df282a0 JB	250	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	251	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	252	rtItem = priorityQueue.dequeue(2)
e75373e6	253	expect(priorityQueue.buckets).toBe(1)
a4092a15 JB	254	expect(priorityQueue.size).toBe(3)
	255	expect(priorityQueue.maxSize).toBe(6)
	256	expect(rtItem).toBe(3)
9df282a0 JB	257	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	258	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	259	rtItem = priorityQueue.dequeue(2)
e75373e6	260	expect(priorityQueue.buckets).toBe(1)
a4092a15 JB	261	expect(priorityQueue.size).toBe(2)
a4092a15 JB	262	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	263	expect(rtItem).toBe(3)
	264	expect(priorityQueue.tail.empty()).toBe(false)
	265	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	266	rtItem = priorityQueue.dequeue(2)
e75373e6	267	expect(priorityQueue.buckets).toBe(0)
a4092a15 JB	268	expect(priorityQueue.size).toBe(1)
a4092a15 JB	269	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	270	expect(rtItem).toBe(1)
	271	expect(priorityQueue.tail.empty()).toBe(false)
	272	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	273	rtItem = priorityQueue.dequeue()
e75373e6	274	expect(priorityQueue.buckets).toBe(0)
a4092a15 JB	275	expect(priorityQueue.size).toBe(0)
a4092a15 JB	276	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	277	expect(rtItem).toBe(2)
	278	expect(priorityQueue.tail.empty()).toBe(true)
	279	expect(priorityQueue.tail.next).toBe(undefined)
bd8b441c JB	280	})
bd8b441c JB	281
95d1a734	282	it('Verify iterator behavior', () => {
9df282a0	283	const priorityQueue = new PriorityQueue(2)
95d1a734 JB	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
bd8b441c	294	it('Verify clear() behavior', () => {
9df282a0	295	const priorityQueue = new PriorityQueue(2)
bd8b441c JB	296	priorityQueue.enqueue(1)
	297	priorityQueue.enqueue(2)
	298	priorityQueue.enqueue(3)
e75373e6	299	expect(priorityQueue.buckets).toBe(1)
bd8b441c JB	300	expect(priorityQueue.size).toBe(3)
bd8b441c JB	301	expect(priorityQueue.maxSize).toBe(3)
9df282a0 JB	302	expect(priorityQueue.head.empty()).toBe(false)
	303	expect(priorityQueue.tail.empty()).toBe(false)
	304	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
bd8b441c	305	priorityQueue.clear()
e75373e6	306	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	307	expect(priorityQueue.size).toBe(0)
bd8b441c JB	308	expect(priorityQueue.maxSize).toBe(0)
9df282a0 JB	309	expect(priorityQueue.head.empty()).toBe(true)
9df282a0 JB	310	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c JB	311	})
bd8b441c JB	312	})