[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)
    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(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)
    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, 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)
    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 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)
e41b0271	140	rtSize = priorityQueue.enqueue(3, -1)
e75373e6	141	expect(priorityQueue.buckets).toBe(2)
e41b0271 JB	142	expect(priorityQueue.size).toBe(4)
	143	expect(priorityQueue.maxSize).toBe(4)
	144	expect(rtSize).toBe(priorityQueue.size)
9df282a0	145	expect(priorityQueue.head.nodeArray).toMatchObject([
e41b0271	146	{ data: 3, priority: -1 },
3a502712	147	{ data: 3, priority: 0 },
e41b0271	148	])
9df282a0 JB	149	expect(priorityQueue.head.next).toBe(undefined)
	150	expect(priorityQueue.tail.nodeArray).toMatchObject([
	151	{ data: 1, priority: 0 },
3a502712	152	{ data: 2, priority: 0 },
9df282a0 JB	153	])
9df282a0 JB	154	expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head)
e41b0271	155	rtSize = priorityQueue.enqueue(1, 1)
e75373e6	156	expect(priorityQueue.buckets).toBe(2)
e41b0271 JB	157	expect(priorityQueue.size).toBe(5)
	158	expect(priorityQueue.maxSize).toBe(5)
	159	expect(rtSize).toBe(priorityQueue.size)
9df282a0	160	expect(priorityQueue.head.nodeArray).toMatchObject([
3a502712	161	{ data: 1, priority: 1 },
9df282a0 JB	162	])
	163	expect(priorityQueue.head.next).toBe(undefined)
	164	expect(priorityQueue.tail.nodeArray).toMatchObject([
e41b0271	165	{ data: 1, priority: 0 },
3a502712	166	{ data: 2, priority: 0 },
9df282a0 JB	167	])
	168	expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
	169	expect(priorityQueue.tail.next.nodeArray).toMatchObject([
e41b0271	170	{ data: 3, priority: -1 },
3a502712	171	{ data: 3, priority: 0 },
e41b0271	172	])
a4092a15	173	rtSize = priorityQueue.enqueue(3, -2)
e75373e6	174	expect(priorityQueue.buckets).toBe(3)
e41b0271 JB	175	expect(priorityQueue.size).toBe(6)
	176	expect(priorityQueue.maxSize).toBe(6)
	177	expect(rtSize).toBe(priorityQueue.size)
9df282a0	178	expect(priorityQueue.head.nodeArray).toMatchObject([
a4092a15	179	{ data: 3, priority: -2 },
3a502712	180	{ data: 1, priority: 1 },
e41b0271	181	])
9df282a0 JB	182	expect(priorityQueue.head.next).toBe(undefined)
	183	expect(priorityQueue.tail.nodeArray).toMatchObject([
	184	{ data: 1, priority: 0 },
3a502712	185	{ data: 2, priority: 0 },
9df282a0 JB	186	])
	187	expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
	188	expect(priorityQueue.tail.next.nodeArray).toMatchObject([
	189	{ data: 3, priority: -1 },
3a502712	190	{ data: 3, priority: 0 },
9df282a0	191	])
e41b0271 JB	192	})
e41b0271 JB	193
9df282a0	194	it('Verify default bucket size dequeue() behavior', () => {
fcfc3353	195	const priorityQueue = new PriorityQueue(defaultBucketSize, true)
bd8b441c JB	196	priorityQueue.enqueue(1)
	197	priorityQueue.enqueue(2, -1)
	198	priorityQueue.enqueue(3)
e75373e6	199	expect(priorityQueue.buckets).toBe(0)
0d4e88b3 JB	200	expect(priorityQueue.size).toBe(3)
0d4e88b3 JB	201	expect(priorityQueue.maxSize).toBe(3)
9df282a0 JB	202	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	203	expect(priorityQueue.tail.next).toBe(undefined)
bd8b441c	204	let rtItem = priorityQueue.dequeue()
e75373e6	205	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	206	expect(priorityQueue.size).toBe(2)
	207	expect(priorityQueue.maxSize).toBe(3)
	208	expect(rtItem).toBe(2)
9df282a0 JB	209	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	210	expect(priorityQueue.tail.next).toBe(undefined)
bd8b441c	211	rtItem = priorityQueue.dequeue()
e75373e6	212	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	213	expect(priorityQueue.size).toBe(1)
	214	expect(priorityQueue.maxSize).toBe(3)
	215	expect(rtItem).toBe(1)
9df282a0 JB	216	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	217	expect(priorityQueue.tail.next).toBe(undefined)
bd8b441c	218	rtItem = priorityQueue.dequeue()
e75373e6	219	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	220	expect(priorityQueue.size).toBe(0)
	221	expect(priorityQueue.maxSize).toBe(3)
	222	expect(rtItem).toBe(3)
9df282a0 JB	223	expect(priorityQueue.tail.empty()).toBe(true)
9df282a0 JB	224	expect(priorityQueue.tail.next).toBe(undefined)
bd8b441c JB	225	})
bd8b441c JB	226
2107bc57	227	it('Verify bucketSize=2 dequeue() behavior', () => {
fcfc3353	228	const priorityQueue = new PriorityQueue(2, true)
a4092a15 JB	229	priorityQueue.enqueue(1)
	230	priorityQueue.enqueue(2)
	231	priorityQueue.enqueue(3)
	232	priorityQueue.enqueue(3, -1)
	233	priorityQueue.enqueue(1, 1)
	234	priorityQueue.enqueue(3, -2)
e75373e6	235	expect(priorityQueue.buckets).toBe(3)
0d4e88b3 JB	236	expect(priorityQueue.size).toBe(6)
0d4e88b3 JB	237	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	238	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	239	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	240	let rtItem = priorityQueue.dequeue(3)
e75373e6	241	expect(priorityQueue.buckets).toBe(2)
a4092a15 JB	242	expect(priorityQueue.size).toBe(5)
	243	expect(priorityQueue.maxSize).toBe(6)
	244	expect(rtItem).toBe(3)
9df282a0 JB	245	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	246	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	247	rtItem = priorityQueue.dequeue()
e75373e6	248	expect(priorityQueue.buckets).toBe(2)
a4092a15 JB	249	expect(priorityQueue.size).toBe(4)
	250	expect(priorityQueue.maxSize).toBe(6)
	251	expect(rtItem).toBe(1)
9df282a0 JB	252	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	253	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	254	rtItem = priorityQueue.dequeue(2)
e75373e6	255	expect(priorityQueue.buckets).toBe(1)
a4092a15 JB	256	expect(priorityQueue.size).toBe(3)
	257	expect(priorityQueue.maxSize).toBe(6)
	258	expect(rtItem).toBe(3)
9df282a0 JB	259	expect(priorityQueue.tail.empty()).toBe(false)
9df282a0 JB	260	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	261	rtItem = priorityQueue.dequeue(2)
e75373e6	262	expect(priorityQueue.buckets).toBe(1)
a4092a15 JB	263	expect(priorityQueue.size).toBe(2)
a4092a15 JB	264	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	265	expect(rtItem).toBe(3)
	266	expect(priorityQueue.tail.empty()).toBe(false)
	267	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	268	rtItem = priorityQueue.dequeue(2)
e75373e6	269	expect(priorityQueue.buckets).toBe(0)
a4092a15 JB	270	expect(priorityQueue.size).toBe(1)
a4092a15 JB	271	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	272	expect(rtItem).toBe(1)
	273	expect(priorityQueue.tail.empty()).toBe(false)
	274	expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
a4092a15	275	rtItem = priorityQueue.dequeue()
e75373e6	276	expect(priorityQueue.buckets).toBe(0)
a4092a15 JB	277	expect(priorityQueue.size).toBe(0)
a4092a15 JB	278	expect(priorityQueue.maxSize).toBe(6)
9df282a0 JB	279	expect(rtItem).toBe(2)
	280	expect(priorityQueue.tail.empty()).toBe(true)
	281	expect(priorityQueue.tail.next).toBe(undefined)
bd8b441c	282	})
fcfc3353 JB	283
	284	it('Verify enablePriority setter behavior', () => {
	285	const priorityQueue = new PriorityQueue(2)
	286	expect(priorityQueue.enablePriority).toBe(false)
	287	priorityQueue.enqueue(1)
	288	priorityQueue.enqueue(2)
	289	priorityQueue.enqueue(3)
	290	priorityQueue.enqueue(4)
	291	let buckets = 0
	292	let node = priorityQueue.tail
	293	while (node != null) {
	294	expect(node.enablePriority).toBe(false)
	295	node = node.next
	296	++buckets
	297	}
	298	expect(buckets).toBe(2)
	299	priorityQueue.enablePriority = true
	300	expect(priorityQueue.enablePriority).toBe(true)
	301	node = priorityQueue.tail
	302	while (node != null) {
	303	expect(node.enablePriority).toBe(true)
	304	node = node.next
	305	}
	306	})
bd8b441c	307
95d1a734	308	it('Verify iterator behavior', () => {
9df282a0	309	const priorityQueue = new PriorityQueue(2)
95d1a734 JB	310	priorityQueue.enqueue(1)
	311	priorityQueue.enqueue(2)
	312	priorityQueue.enqueue(3)
	313	let i = 1
	314	for (const value of priorityQueue) {
	315	expect(value).toBe(i)
	316	++i
	317	}
	318	})
	319
bd8b441c	320	it('Verify clear() behavior', () => {
9df282a0	321	const priorityQueue = new PriorityQueue(2)
bd8b441c JB	322	priorityQueue.enqueue(1)
	323	priorityQueue.enqueue(2)
	324	priorityQueue.enqueue(3)
e75373e6	325	expect(priorityQueue.buckets).toBe(1)
bd8b441c JB	326	expect(priorityQueue.size).toBe(3)
bd8b441c JB	327	expect(priorityQueue.maxSize).toBe(3)
9df282a0 JB	328	expect(priorityQueue.head.empty()).toBe(false)
	329	expect(priorityQueue.tail.empty()).toBe(false)
	330	expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
bd8b441c	331	priorityQueue.clear()
e75373e6	332	expect(priorityQueue.buckets).toBe(0)
bd8b441c JB	333	expect(priorityQueue.size).toBe(0)
bd8b441c JB	334	expect(priorityQueue.maxSize).toBe(0)
9df282a0 JB	335	expect(priorityQueue.head.empty()).toBe(true)
9df282a0 JB	336	expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
bd8b441c JB	337	})
bd8b441c JB	338	})