[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.enablePriority).toBe(false)
    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, 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.enablePriority).toBe(false)
      node = node.next
      ++buckets
    }
    expect(buckets).toBe(2)
    priorityQueue.enablePriority = true
    expect(priorityQueue.enablePriority).toBe(true)
    node = priorityQueue.tail
    while (node != null) {
      expect(node.enablePriority).toBe(true)
      node = node.next
    }
  })

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