From bd8b441c7140491657341a2971940ae7fc35222a Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Mon, 29 Apr 2024 15:21:37 +0200 Subject: [PATCH] test: add priority queue test suite MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- src/circular-array.ts | 2 +- src/index.ts | 1 + src/priority-queue.ts | 12 +++- tests/priority-queue.test.mjs | 116 ++++++++++++++++++++++++++++++++++ 4 files changed, 128 insertions(+), 3 deletions(-) create mode 100644 tests/priority-queue.test.mjs diff --git a/src/circular-array.ts b/src/circular-array.ts index 511b699c..23473279 100644 --- a/src/circular-array.ts +++ b/src/circular-array.ts @@ -1,6 +1,6 @@ // Copyright Jerome Benoit. 2021-2024. All Rights Reserved. -export const DEFAULT_CIRCULAR_ARRAY_SIZE = 1024 +export const DEFAULT_CIRCULAR_ARRAY_SIZE = 385 /** * Array with a maximum length and shifting items when full. diff --git a/src/index.ts b/src/index.ts index a4482d58..1d778513 100644 --- a/src/index.ts +++ b/src/index.ts @@ -50,6 +50,7 @@ export type { WorkerUsage } from './pools/worker.js' export { WorkerTypes } from './pools/worker.js' +export type { PriorityQueue } from './priority-queue.js' export type { MessageValue, PromiseResponseWrapper, diff --git a/src/priority-queue.ts b/src/priority-queue.ts index 55a97169..168e6c34 100644 --- a/src/priority-queue.ts +++ b/src/priority-queue.ts @@ -7,20 +7,28 @@ interface PriorityQueueNode { } /** - * Priority queue. + * k-priority queue. * * @typeParam T - Type of priority queue data. * @internal */ export class PriorityQueue { private nodeArray!: Array> + /** Prioritized bucket size. */ + private readonly k: number /** The size of the priority queue. */ public size!: number /** The maximum size of the priority queue. */ public maxSize!: number - public constructor () { + /** + * Constructs a k-priority queue. + * + * @param k - Prioritized bucket size. + */ + public constructor (k = Infinity) { this.clear() + this.k = k } /** diff --git a/tests/priority-queue.test.mjs b/tests/priority-queue.test.mjs new file mode 100644 index 00000000..0c39e746 --- /dev/null +++ b/tests/priority-queue.test.mjs @@ -0,0 +1,116 @@ +import { expect } from 'expect' + +// eslint-disable-next-line n/no-missing-import, import/no-unresolved +import { PriorityQueue } from '../lib/priority-queue.cjs' + +describe.skip('Priority queue test suite', () => { + it('Verify enqueue() behavior', () => { + const priorityQueue = new PriorityQueue() + let rtSize = priorityQueue.enqueue(1) + expect(priorityQueue.size).toBe(1) + expect(priorityQueue.maxSize).toBe(1) + expect(rtSize).toBe(priorityQueue.size) + expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }]) + rtSize = priorityQueue.enqueue(2) + expect(priorityQueue.size).toBe(2) + expect(priorityQueue.maxSize).toBe(2) + expect(rtSize).toBe(priorityQueue.size) + expect(priorityQueue.nodeArray).toStrictEqual([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 } + ]) + rtSize = priorityQueue.enqueue(3) + expect(priorityQueue.size).toBe(3) + expect(priorityQueue.maxSize).toBe(3) + expect(rtSize).toBe(priorityQueue.size) + expect(priorityQueue.nodeArray).toStrictEqual([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 } + ]) + rtSize = priorityQueue.enqueue(3, -1) + expect(priorityQueue.size).toBe(4) + expect(priorityQueue.maxSize).toBe(4) + expect(rtSize).toBe(priorityQueue.size) + expect(priorityQueue.nodeArray).toStrictEqual([ + { data: 3, priority: -1 }, + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 } + ]) + rtSize = priorityQueue.enqueue(1, 1) + expect(priorityQueue.size).toBe(5) + expect(priorityQueue.maxSize).toBe(5) + expect(rtSize).toBe(priorityQueue.size) + expect(priorityQueue.nodeArray).toStrictEqual([ + { data: 3, priority: -1 }, + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 }, + { data: 1, priority: 1 } + ]) + }) + + it('Verify dequeue() behavior', () => { + const priorityQueue = new PriorityQueue() + priorityQueue.enqueue(1) + priorityQueue.enqueue(2, -1) + priorityQueue.enqueue(3) + let rtItem = priorityQueue.dequeue() + expect(priorityQueue.size).toBe(2) + expect(priorityQueue.maxSize).toBe(3) + expect(rtItem).toBe(2) + expect(priorityQueue.nodeArray).toStrictEqual([ + { data: 1, priority: 0 }, + { data: 3, priority: 0 } + ]) + rtItem = priorityQueue.dequeue() + expect(priorityQueue.size).toBe(1) + expect(priorityQueue.maxSize).toBe(3) + expect(rtItem).toBe(1) + expect(priorityQueue.nodeArray).toStrictEqual([{ data: 3, priority: 0 }]) + rtItem = priorityQueue.dequeue() + expect(priorityQueue.size).toBe(0) + expect(priorityQueue.maxSize).toBe(3) + expect(rtItem).toBe(3) + expect(priorityQueue.nodeArray).toStrictEqual([]) + }) + + it('Verify peekFirst() behavior', () => { + const priorityQueue = new PriorityQueue() + priorityQueue.enqueue(1) + priorityQueue.enqueue(2) + priorityQueue.enqueue(3) + expect(priorityQueue.size).toBe(3) + expect(priorityQueue.peekFirst()).toBe(1) + expect(priorityQueue.size).toBe(3) + }) + + it('Verify peekLast() behavior', () => { + const priorityQueue = new PriorityQueue() + priorityQueue.enqueue(1) + priorityQueue.enqueue(2) + priorityQueue.enqueue(3) + expect(priorityQueue.size).toBe(3) + expect(priorityQueue.peekLast()).toBe(3) + expect(priorityQueue.size).toBe(3) + }) + + it('Verify clear() behavior', () => { + const priorityQueue = new PriorityQueue() + priorityQueue.enqueue(1) + priorityQueue.enqueue(2) + priorityQueue.enqueue(3) + expect(priorityQueue.size).toBe(3) + expect(priorityQueue.maxSize).toBe(3) + expect(priorityQueue.nodeArray).toStrictEqual([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 } + ]) + priorityQueue.clear() + expect(priorityQueue.size).toBe(0) + expect(priorityQueue.maxSize).toBe(0) + expect(priorityQueue.nodeArray).toStrictEqual([]) + }) +}) -- 2.34.1