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