From f8d5d8fdf46b7182f5efa3503bb5172ec199fb45 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Sat, 25 May 2024 17:33:44 +0200 Subject: [PATCH] feat: add fixed priority queue implementation MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Expected usage is priority queue optimization Signed-off-by: Jérôme Benoit --- src/circular-buffer.ts | 6 +- src/fixed-priority-queue.ts | 131 ++++++++++++++++++++++ tests/fixed-priority-queue.test.mjs | 161 ++++++++++++++++++++++++++++ 3 files changed, 295 insertions(+), 3 deletions(-) create mode 100644 src/fixed-priority-queue.ts create mode 100644 tests/fixed-priority-queue.test.mjs diff --git a/src/circular-buffer.ts b/src/circular-buffer.ts index a56cd09d..55f5f9bf 100644 --- a/src/circular-buffer.ts +++ b/src/circular-buffer.ts @@ -65,14 +65,14 @@ export class CircularBuffer { * @returns Number from buffer. */ public get (): number | undefined { - const data = this.items[this.readIdx] - if (data === -1) { + const number = this.items[this.readIdx] + if (number === -1) { return } this.items[this.readIdx] = -1 this.readIdx = this.readIdx === this.maxArrayIdx ? 0 : this.readIdx + 1 --this.size - return data + return number } /** diff --git a/src/fixed-priority-queue.ts b/src/fixed-priority-queue.ts new file mode 100644 index 00000000..60096ce0 --- /dev/null +++ b/src/fixed-priority-queue.ts @@ -0,0 +1,131 @@ +/** + * Default buffer size. + */ +export const defaultQueueSize = 2048 + +/** + * Priority queue node. + * + * @typeParam T - Type of priority queue node data. + * @internal + */ +export interface PriorityQueueNode { + data: T + priority: number +} + +export class FixedPriorityQueue { + private start!: number + private readonly nodeArray: Array> + public size!: number + public maxSize!: number + + constructor (size: number = defaultQueueSize) { + this.checkSize(size) + this.nodeArray = new Array>(size) + this.clear() + } + + public empty (): boolean { + return this.size === 0 + } + + public full (): boolean { + return this.size === this.nodeArray.length + } + + public enqueue (data: T, priority?: number): number { + if (this.full()) { + throw new Error('Priority queue is full') + } + priority = priority ?? 0 + let inserted = false + for (let index = this.start; index < this.nodeArray.length; index++) { + if (this.nodeArray[index]?.priority > priority) { + this.nodeArray.splice(index, 0, { data, priority }) + inserted = true + break + } + } + if (!inserted) { + let index = this.start + this.size + if (index >= this.nodeArray.length) { + index -= this.nodeArray.length + } + this.nodeArray[index] = { data, priority } + } + return this.incrementSize() + } + + public dequeue (): T | undefined { + if (this.empty()) { + return undefined + } + const index = this.start + --this.size + ++this.start + if (this.start === this.nodeArray.length) { + this.start = 0 + } + return this.nodeArray[index].data + } + + /** + * Clears the fixed priority queue. + */ + public clear (): void { + this.start = 0 + this.size = 0 + this.maxSize = 0 + } + + /** + * Returns an iterator for the fixed priority queue. + * + * @returns An iterator for the fixed priority queue. + * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols + */ + [Symbol.iterator] (): Iterator { + let i = this.start + return { + next: () => { + if (i >= this.size) { + return { + value: undefined, + done: true + } + } + const value = this.nodeArray[i].data + i++ + return { + value, + done: false + } + } + } + } + + /** + * Increments the size of the fixed priority queue. + * + * @returns The new size of the fixed priority queue. + */ + private incrementSize (): number { + ++this.size + if (this.size > this.maxSize) { + this.maxSize = this.size + } + return this.size + } + + private checkSize (size: number): void { + if (!Number.isSafeInteger(size)) { + throw new TypeError( + `Invalid fixed priority queue size: ${size} is not an integer` + ) + } + if (size < 0) { + throw new RangeError(`Invalid fixed priority queue size: ${size} < 0`) + } + } +} diff --git a/tests/fixed-priority-queue.test.mjs b/tests/fixed-priority-queue.test.mjs new file mode 100644 index 00000000..4821d387 --- /dev/null +++ b/tests/fixed-priority-queue.test.mjs @@ -0,0 +1,161 @@ +import { expect } from 'expect' + +import { + defaultQueueSize, + FixedPriorityQueue +} from '../lib/fixed-priority-queue.cjs' + +describe.skip('Fixed Priority queue test suite', () => { + it('Verify constructor() behavior', () => { + expect(() => new FixedPriorityQueue('')).toThrow( + new TypeError('Invalid fixed priority queue size: is not an integer') + ) + expect(() => new FixedPriorityQueue(-1)).toThrow( + new RangeError('Invalid fixed priority queue size: -1 < 0') + ) + let fixedPriorityQueue = new FixedPriorityQueue() + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(0) + expect(fixedPriorityQueue.maxSize).toBe(0) + expect(fixedPriorityQueue.nodeArray).toBeInstanceOf(Array) + expect(fixedPriorityQueue.nodeArray.length).toBe(defaultQueueSize) + fixedPriorityQueue = new FixedPriorityQueue(2) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(0) + expect(fixedPriorityQueue.maxSize).toBe(0) + expect(fixedPriorityQueue.nodeArray).toBeInstanceOf(Array) + expect(fixedPriorityQueue.nodeArray.length).toBe(2) + }) + + it('Verify enqueue() behavior', () => { + const fixedPriorityQueue = new FixedPriorityQueue() + let rtSize = fixedPriorityQueue.enqueue(1) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(1) + expect(fixedPriorityQueue.maxSize).toBe(1) + expect(rtSize).toBe(fixedPriorityQueue.size) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 } + ]) + rtSize = fixedPriorityQueue.enqueue(2) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(2) + expect(fixedPriorityQueue.maxSize).toBe(2) + expect(rtSize).toBe(fixedPriorityQueue.size) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 } + ]) + rtSize = fixedPriorityQueue.enqueue(3) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(3) + expect(fixedPriorityQueue.maxSize).toBe(3) + expect(rtSize).toBe(fixedPriorityQueue.size) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 } + ]) + rtSize = fixedPriorityQueue.enqueue(3, -1) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(4) + expect(fixedPriorityQueue.maxSize).toBe(4) + expect(rtSize).toBe(fixedPriorityQueue.size) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 3, priority: -1 }, + { data: 1, priority: 0 }, + { data: 2, priority: 0 }, + { data: 3, priority: 0 } + ]) + rtSize = fixedPriorityQueue.enqueue(1, 1) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(5) + expect(fixedPriorityQueue.maxSize).toBe(5) + expect(rtSize).toBe(fixedPriorityQueue.size) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { 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 fixedPriorityQueue = new FixedPriorityQueue() + fixedPriorityQueue.enqueue(1) + fixedPriorityQueue.enqueue(2, -1) + fixedPriorityQueue.enqueue(3) + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(3) + expect(fixedPriorityQueue.maxSize).toBe(3) + let rtItem = fixedPriorityQueue.dequeue() + expect(fixedPriorityQueue.start).toBe(1) + expect(fixedPriorityQueue.size).toBe(2) + expect(fixedPriorityQueue.maxSize).toBe(3) + expect(rtItem).toBe(2) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 2, priority: -1 }, + { data: 1, priority: 0 }, + { data: 3, priority: 0 } + ]) + rtItem = fixedPriorityQueue.dequeue() + expect(fixedPriorityQueue.start).toBe(2) + expect(fixedPriorityQueue.size).toBe(1) + expect(fixedPriorityQueue.maxSize).toBe(3) + expect(rtItem).toBe(1) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 2, priority: -1 }, + { data: 1, priority: 0 }, + { data: 3, priority: 0 } + ]) + rtItem = fixedPriorityQueue.dequeue() + expect(fixedPriorityQueue.start).toBe(3) + expect(fixedPriorityQueue.size).toBe(0) + expect(fixedPriorityQueue.maxSize).toBe(3) + expect(rtItem).toBe(3) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 2, priority: -1 }, + { data: 1, priority: 0 }, + { data: 3, priority: 0 } + ]) + expect(fixedPriorityQueue.dequeue()).toBe(undefined) + }) + + it('Verify iterator behavior', () => { + const fixedPriorityQueue = new FixedPriorityQueue() + fixedPriorityQueue.enqueue(1) + fixedPriorityQueue.enqueue(2) + fixedPriorityQueue.enqueue(3) + let i = fixedPriorityQueue.start + 1 + for (const value of fixedPriorityQueue) { + expect(value).toBe(i) + ++i + } + fixedPriorityQueue.dequeue() + i = fixedPriorityQueue.start + 1 + for (const value of fixedPriorityQueue) { + expect(value).toBe(i) + ++i + } + }) + + it('Verify clear() behavior', () => { + const fixedPriorityQueue = new FixedPriorityQueue() + fixedPriorityQueue.start = 1 + fixedPriorityQueue.size = 2 + fixedPriorityQueue.maxSize = 2 + fixedPriorityQueue.nodeArray = [ + { data: 2, priority: 0 }, + { data: 3, priority: 0 } + ] + fixedPriorityQueue.clear() + expect(fixedPriorityQueue.start).toBe(0) + expect(fixedPriorityQueue.size).toBe(0) + expect(fixedPriorityQueue.maxSize).toBe(0) + expect(fixedPriorityQueue.nodeArray).toMatchObject([ + { data: 2, priority: 0 }, + { data: 3, priority: 0 } + ]) + }) +}) -- 2.34.1