+// Copyright Jerome Benoit. 2024. All Rights Reserved.
+
/**
+ * Priority queue node.
+ *
+ * @typeParam T - Type of priority queue node data.
* @internal
*/
-interface PriorityQueueNode<T> {
+export interface PriorityQueueNode<T> {
data: T
priority: number
}
*/
export class PriorityQueue<T> {
private nodeArray!: Array<PriorityQueueNode<T>>
+ /** 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 () {
+ /**
+ * The number of filled prioritized buckets.
+ */
+ public get buckets (): number {
+ return this.k === Infinity ? 1 : Math.trunc(this.nodeArray.length / this.k)
+ }
+
+ /**
+ * Constructs a priority queue.
+ *
+ * @param k - Prioritized bucket size. @defaultValue Infinity
+ */
+ public constructor (k = Infinity) {
+ if (k !== Infinity && !Number.isSafeInteger(k)) {
+ throw new TypeError('k must be an integer')
+ }
+ if (k < 1) {
+ throw new RangeError('k must be greater than or equal to 1')
+ }
+ this.k = k
this.clear()
}
*/
public enqueue (data: T, priority?: number): number {
priority = priority ?? 0
+ const startIndex = this.k === Infinity ? 0 : this.buckets * this.k
let inserted = false
- for (const [index, node] of this.nodeArray.entries()) {
- if (node.priority > priority) {
+ for (let index = startIndex; index < this.nodeArray.length; index++) {
+ if (this.nodeArray[index].priority > priority) {
this.nodeArray.splice(index, 0, { data, priority })
inserted = true
break
/**
* Dequeue data from the priority queue.
*
+ * @param bucket - The prioritized bucket to dequeue from. @defaultValue 0
* @returns The dequeued data or `undefined` if the priority queue is empty.
*/
- public dequeue (): T | undefined {
- if (this.size > 0) {
- --this.size
+ public dequeue (bucket = 0): T | undefined {
+ if (this.k !== Infinity && bucket > 0) {
+ while (bucket > 0) {
+ const index = bucket * this.k
+ // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
+ if (this.nodeArray[index] != null) {
+ --this.size
+ return this.nodeArray.splice(index, 1)[0].data
+ }
+ --bucket
+ }
}
+ this.decrementSize()
return this.nodeArray.shift()?.data
}
}
/**
- * Increments the size of the deque.
+ * Returns an iterator for the priority queue.
+ *
+ * @returns An iterator for the priority queue.
+ * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
+ */
+ [Symbol.iterator] (): Iterator<T> {
+ let i = 0
+ return {
+ next: () => {
+ if (i >= this.nodeArray.length) {
+ return {
+ value: undefined,
+ done: true
+ }
+ }
+ const value = this.nodeArray[i].data
+ i++
+ return {
+ value,
+ done: false
+ }
+ }
+ }
+ }
+
+ /**
+ * Increments the size of the priority queue.
*
- * @returns The new size of the deque.
+ * @returns The new size of the priority queue.
*/
private incrementSize (): number {
++this.size
}
return this.size
}
+
+ /**
+ * Decrements the size of the priority queue.
+ *
+ * @returns The new size of the priority queue.
+ */
+ private decrementSize (): number {
+ if (this.size > 0) {
+ --this.size
+ }
+ return this.size
+ }
}