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 bucketSize
: 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.bucketSize
=== Number.POSITIVE_INFINITY
35 : Math.trunc(this.nodeArray
.length
/ this.bucketSize
)
39 * Constructs a priority queue.
41 * @param bucketSize - Prioritized bucket size. @defaultValue Number.POSITIVE_INFINITY
43 public constructor (bucketSize
= Number.POSITIVE_INFINITY
) {
45 bucketSize
!== Number.POSITIVE_INFINITY
&&
46 !Number.isSafeInteger(bucketSize
)
48 throw new TypeError('bucketSize must be an integer')
51 throw new RangeError('bucketSize must be greater than or equal to 1')
53 this.bucketSize
= bucketSize
58 * Enqueue data into the priority queue.
60 * @param data - Data to enqueue.
61 * @param priority - Priority of the data. Lower values have higher priority.
62 * @returns The new size of the priority queue.
64 public enqueue (data
: T
, priority
?: number): number {
65 priority
= priority
?? 0
67 this.bucketSize
=== Number.POSITIVE_INFINITY
69 : this.buckets
* this.bucketSize
71 for (let index
= startIndex
; index
< this.nodeArray
.length
; index
++) {
72 if (this.nodeArray
[index
].priority
> priority
) {
73 this.nodeArray
.splice(index
, 0, { data
, priority
})
79 this.nodeArray
.push({ data
, priority
})
81 return this.incrementSize()
85 * Dequeue data from the priority queue.
87 * @param bucket - The prioritized bucket to dequeue from. @defaultValue 0
88 * @returns The dequeued data or `undefined` if the priority queue is empty.
90 public dequeue (bucket
= 0): T
| undefined {
91 if (this.bucketSize
!== Number.POSITIVE_INFINITY
&& bucket
> 0) {
93 const index
= bucket
* this.bucketSize
94 // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
95 if (this.nodeArray
[index
] != null) {
97 return this.nodeArray
.splice(index
, 1)[0].data
103 return this.nodeArray
.shift()?.data
107 * Peeks at the first data.
108 * @returns The first data or `undefined` if the priority queue is empty.
110 public peekFirst (): T
| undefined {
111 return this.nodeArray
[0]?.data
115 * Peeks at the last data.
116 * @returns The last data or `undefined` if the priority queue is empty.
118 public peekLast (): T
| undefined {
119 return this.nodeArray
[this.nodeArray
.length
- 1]?.data
123 * Clears the priority queue.
125 public clear (): void {
132 * Returns an iterator for the priority queue.
134 * @returns An iterator for the priority queue.
135 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
137 [Symbol
.iterator
] (): Iterator
<T
> {
141 if (i
>= this.nodeArray
.length
) {
147 const value
= this.nodeArray
[i
].data
158 * Increments the size of the priority queue.
160 * @returns The new size of the priority queue.
162 private incrementSize (): number {
164 if (this.size
> this.maxSize
) {
165 this.maxSize
= this.size
171 * Decrements the size of the priority queue.
173 * @returns The new size of the priority queue.
175 private decrementSize (): number {