From 2107bc577c9620f6140183691f8038e71304489b Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Sun, 19 May 2024 23:57:57 +0200 Subject: [PATCH] refactor: cleanup priority queue code MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- src/priority-queue.ts | 27 +++++++++++++++------------ tests/pools/abstract-pool.test.mjs | 4 ++-- tests/pools/worker-node.test.mjs | 4 ++-- tests/priority-queue.test.mjs | 18 +++++++++--------- 4 files changed, 28 insertions(+), 25 deletions(-) diff --git a/src/priority-queue.ts b/src/priority-queue.ts index e68fe37d..8e9c1ae2 100644 --- a/src/priority-queue.ts +++ b/src/priority-queue.ts @@ -20,7 +20,7 @@ export interface PriorityQueueNode { export class PriorityQueue { private nodeArray!: Array> /** Prioritized bucket size. */ - private readonly k: number + private readonly bucketSize: number /** The size of the priority queue. */ public size!: number /** The maximum size of the priority queue. */ @@ -30,22 +30,24 @@ export class PriorityQueue { * The number of filled prioritized buckets. */ public get buckets (): number { - return this.k === Infinity ? 1 : Math.trunc(this.nodeArray.length / this.k) + return this.bucketSize === Infinity + ? 1 + : Math.trunc(this.nodeArray.length / this.bucketSize) } /** * Constructs a priority queue. * - * @param k - Prioritized bucket size. @defaultValue Infinity + * @param bucketSize - Prioritized bucket size. @defaultValue Infinity */ - public constructor (k = Infinity) { - if (k !== Infinity && !Number.isSafeInteger(k)) { - throw new TypeError('k must be an integer') + public constructor (bucketSize = Infinity) { + if (bucketSize !== Infinity && !Number.isSafeInteger(bucketSize)) { + throw new TypeError('bucketSize must be an integer') } - if (k < 1) { - throw new RangeError('k must be greater than or equal to 1') + if (bucketSize < 1) { + throw new RangeError('bucketSize must be greater than or equal to 1') } - this.k = k + this.bucketSize = bucketSize this.clear() } @@ -58,7 +60,8 @@ export class PriorityQueue { */ public enqueue (data: T, priority?: number): number { priority = priority ?? 0 - const startIndex = this.k === Infinity ? 0 : this.buckets * this.k + const startIndex = + this.bucketSize === Infinity ? 0 : this.buckets * this.bucketSize let inserted = false for (let index = startIndex; index < this.nodeArray.length; index++) { if (this.nodeArray[index].priority > priority) { @@ -80,9 +83,9 @@ export class PriorityQueue { * @returns The dequeued data or `undefined` if the priority queue is empty. */ public dequeue (bucket = 0): T | undefined { - if (this.k !== Infinity && bucket > 0) { + if (this.bucketSize !== Infinity && bucket > 0) { while (bucket > 0) { - const index = bucket * this.k + const index = bucket * this.bucketSize // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition if (this.nodeArray[index] != null) { --this.size diff --git a/tests/pools/abstract-pool.test.mjs b/tests/pools/abstract-pool.test.mjs index 8cae47d6..e8dfcb8a 100644 --- a/tests/pools/abstract-pool.test.mjs +++ b/tests/pools/abstract-pool.test.mjs @@ -789,7 +789,7 @@ describe('Abstract pool test suite', () => { expect(workerNode.tasksQueue).toBeInstanceOf(PriorityQueue) expect(workerNode.tasksQueue.size).toBe(0) expect(workerNode.tasksQueue.maxSize).toBe(0) - expect(workerNode.tasksQueue.k).toBe(numberOfWorkers * 2) + expect(workerNode.tasksQueue.bucketSize).toBe(numberOfWorkers * 2) } await pool.destroy() pool = new DynamicThreadPool( @@ -802,7 +802,7 @@ describe('Abstract pool test suite', () => { expect(workerNode.tasksQueue).toBeInstanceOf(PriorityQueue) expect(workerNode.tasksQueue.size).toBe(0) expect(workerNode.tasksQueue.maxSize).toBe(0) - expect(workerNode.tasksQueue.k).toBe(numberOfWorkers * 2) + expect(workerNode.tasksQueue.bucketSize).toBe(numberOfWorkers * 2) } await pool.destroy() }) diff --git a/tests/pools/worker-node.test.mjs b/tests/pools/worker-node.test.mjs index a2932282..c4f84a51 100644 --- a/tests/pools/worker-node.test.mjs +++ b/tests/pools/worker-node.test.mjs @@ -224,7 +224,7 @@ describe('Worker node test suite', () => { expect(threadWorkerNode.tasksQueueBackPressureSize).toBe(12) expect(threadWorkerNode.tasksQueue).toBeInstanceOf(PriorityQueue) expect(threadWorkerNode.tasksQueue.size).toBe(0) - expect(threadWorkerNode.tasksQueue.k).toBe(6) + expect(threadWorkerNode.tasksQueue.bucketSize).toBe(6) expect(threadWorkerNode.tasksQueueSize()).toBe( threadWorkerNode.tasksQueue.size ) @@ -270,7 +270,7 @@ describe('Worker node test suite', () => { expect(clusterWorkerNode.tasksQueueBackPressureSize).toBe(12) expect(clusterWorkerNode.tasksQueue).toBeInstanceOf(PriorityQueue) expect(clusterWorkerNode.tasksQueue.size).toBe(0) - expect(clusterWorkerNode.tasksQueue.k).toBe(6) + expect(clusterWorkerNode.tasksQueue.bucketSize).toBe(6) expect(clusterWorkerNode.tasksQueueSize()).toBe( clusterWorkerNode.tasksQueue.size ) diff --git a/tests/priority-queue.test.mjs b/tests/priority-queue.test.mjs index 624d577a..f3da8734 100644 --- a/tests/priority-queue.test.mjs +++ b/tests/priority-queue.test.mjs @@ -5,29 +5,29 @@ import { PriorityQueue } from '../lib/priority-queue.cjs' describe('Priority queue test suite', () => { it('Verify constructor() behavior', () => { expect(() => new PriorityQueue('')).toThrow( - new TypeError('k must be an integer') + new TypeError('bucketSize must be an integer') ) expect(() => new PriorityQueue(-1)).toThrow( - new RangeError('k must be greater than or equal to 1') + new RangeError('bucketSize must be greater than or equal to 1') ) expect(() => new PriorityQueue(0)).toThrow( - new RangeError('k must be greater than or equal to 1') + new RangeError('bucketSize must be greater than or equal to 1') ) let priorityQueue = new PriorityQueue() - expect(priorityQueue.k).toBe(Infinity) + expect(priorityQueue.bucketSize).toBe(Infinity) expect(priorityQueue.buckets).toBe(1) expect(priorityQueue.size).toBe(0) expect(priorityQueue.maxSize).toBe(0) expect(priorityQueue.nodeArray).toStrictEqual([]) priorityQueue = new PriorityQueue(2) - expect(priorityQueue.k).toBe(2) + expect(priorityQueue.bucketSize).toBe(2) expect(priorityQueue.buckets).toBe(0) expect(priorityQueue.size).toBe(0) expect(priorityQueue.maxSize).toBe(0) expect(priorityQueue.nodeArray).toStrictEqual([]) }) - it('Verify default k enqueue() behavior', () => { + it('Verify default bucketSize enqueue() behavior', () => { const priorityQueue = new PriorityQueue() let rtSize = priorityQueue.enqueue(1) expect(priorityQueue.buckets).toBe(1) @@ -79,7 +79,7 @@ describe('Priority queue test suite', () => { ]) }) - it('Verify k=2 enqueue() behavior', () => { + it('Verify bucketSize=2 enqueue() behavior', () => { const priorityQueue = new PriorityQueue(2) let rtSize = priorityQueue.enqueue(1) expect(priorityQueue.buckets).toBe(0) @@ -144,7 +144,7 @@ describe('Priority queue test suite', () => { ]) }) - it('Verify default k dequeue() behavior', () => { + it('Verify default bucketSize dequeue() behavior', () => { const priorityQueue = new PriorityQueue() priorityQueue.enqueue(1) priorityQueue.enqueue(2, -1) @@ -175,7 +175,7 @@ describe('Priority queue test suite', () => { expect(priorityQueue.nodeArray).toStrictEqual([]) }) - it('Verify k=2 dequeue() behavior', () => { + it('Verify bucketSize=2 dequeue() behavior', () => { const priorityQueue = new PriorityQueue(2) priorityQueue.enqueue(1) priorityQueue.enqueue(2) -- 2.34.1