1 // Copyright Jerome Benoit. 2024. All Rights Reserved.
6 * @typeParam T - Type of priority queue node data.
9 export interface PriorityQueueNode
<T
> {
17 * @typeParam T - Type of priority queue data.
20 export class PriorityQueue
<T
> {
21 private nodeArray
!: Array<PriorityQueueNode
<T
>>
22 /** Prioritized bucket size. */
23 private readonly k
: number
24 /** The size of the priority queue. */
26 /** The maximum size of the priority queue. */
27 public maxSize
!: number
30 * The number of filled prioritized buckets.
32 public get
buckets (): number {
33 return this.k
=== Infinity ? 1 : Math.trunc(this.nodeArray
.length
/ this.k
)
37 * Constructs a priority queue.
39 * @param k - Prioritized bucket size. @defaultValue Infinity
41 public constructor (k
= Infinity) {
42 if (k
!== Infinity && !Number.isSafeInteger(k
)) {
43 throw new TypeError('k must be an integer')
46 throw new RangeError('k must be greater than or equal to 1')
53 * Enqueue data into the priority queue.
55 * @param data - Data to enqueue.
56 * @param priority - Priority of the data. Lower values have higher priority.
57 * @returns The new size of the priority queue.
59 public enqueue (data
: T
, priority
?: number): number {
60 priority
= priority
?? 0
61 const startIndex
= this.k
=== Infinity ? 0 : this.buckets
* this.k
63 for (let index
= startIndex
; index
< this.nodeArray
.length
; index
++) {
64 if (this.nodeArray
[index
].priority
> priority
) {
65 this.nodeArray
.splice(index
, 0, { data
, priority
})
71 this.nodeArray
.push({ data
, priority
})
73 return this.incrementSize()
77 * Dequeue data from the priority queue.
79 * @param bucket - The prioritized bucket to dequeue from. @defaultValue 0
80 * @returns The dequeued data or `undefined` if the priority queue is empty.
82 public dequeue (bucket
= 0): T
| undefined {
83 if (this.k
!== Infinity && bucket
> 0) {
85 const index
= bucket
* this.k
86 // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
87 if (this.nodeArray
[index
] != null) {
89 return this.nodeArray
.splice(index
, 1)[0].data
97 return this.nodeArray
.shift()?.data
101 * Peeks at the first data.
102 * @returns The first data or `undefined` if the priority queue is empty.
104 public peekFirst (): T
| undefined {
105 return this.nodeArray
[0]?.data
109 * Peeks at the last data.
110 * @returns The last data or `undefined` if the priority queue is empty.
112 public peekLast (): T
| undefined {
113 return this.nodeArray
[this.nodeArray
.length
- 1]?.data
117 * Clears the priority queue.
119 public clear (): void {
126 * Returns an iterator for the priority queue.
128 * @returns An iterator for the priority queue.
129 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
131 [Symbol
.iterator
] (): Iterator
<T
> {
135 if (i
>= this.nodeArray
.length
) {
141 const value
= this.nodeArray
[i
].data
152 * Increments the size of the priority queue.
154 * @returns The new size of the priority queue.
156 private incrementSize (): number {
158 if (this.size
> this.maxSize
) {
159 this.maxSize
= this.size