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
=== Infinity
35 : Math.trunc(this.nodeArray
.length
/ this.bucketSize
)
39 * Constructs a priority queue.
41 * @param bucketSize - Prioritized bucket size. @defaultValue Infinity
43 public constructor (bucketSize
= Infinity) {
44 if (bucketSize
!== Infinity && !Number.isSafeInteger(bucketSize
)) {
45 throw new TypeError('bucketSize must be an integer')
48 throw new RangeError('bucketSize must be greater than or equal to 1')
50 this.bucketSize
= bucketSize
55 * Enqueue data into the priority queue.
57 * @param data - Data to enqueue.
58 * @param priority - Priority of the data. Lower values have higher priority.
59 * @returns The new size of the priority queue.
61 public enqueue (data
: T
, priority
?: number): number {
62 priority
= priority
?? 0
64 this.bucketSize
=== Infinity ? 0 : this.buckets
* this.bucketSize
66 for (let index
= startIndex
; index
< this.nodeArray
.length
; index
++) {
67 if (this.nodeArray
[index
].priority
> priority
) {
68 this.nodeArray
.splice(index
, 0, { data
, priority
})
74 this.nodeArray
.push({ data
, priority
})
76 return this.incrementSize()
80 * Dequeue data from the priority queue.
82 * @param bucket - The prioritized bucket to dequeue from. @defaultValue 0
83 * @returns The dequeued data or `undefined` if the priority queue is empty.
85 public dequeue (bucket
= 0): T
| undefined {
86 if (this.bucketSize
!== Infinity && bucket
> 0) {
88 const index
= bucket
* this.bucketSize
89 // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
90 if (this.nodeArray
[index
] != null) {
92 return this.nodeArray
.splice(index
, 1)[0].data
98 return this.nodeArray
.shift()?.data
102 * Peeks at the first data.
103 * @returns The first data or `undefined` if the priority queue is empty.
105 public peekFirst (): T
| undefined {
106 return this.nodeArray
[0]?.data
110 * Peeks at the last data.
111 * @returns The last data or `undefined` if the priority queue is empty.
113 public peekLast (): T
| undefined {
114 return this.nodeArray
[this.nodeArray
.length
- 1]?.data
118 * Clears the priority queue.
120 public clear (): void {
127 * Returns an iterator for the priority queue.
129 * @returns An iterator for the priority queue.
130 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
132 [Symbol
.iterator
] (): Iterator
<T
> {
136 if (i
>= this.nodeArray
.length
) {
142 const value
= this.nodeArray
[i
].data
153 * Increments the size of the priority queue.
155 * @returns The new size of the priority queue.
157 private incrementSize (): number {
159 if (this.size
> this.maxSize
) {
160 this.maxSize
= this.size
166 * Decrements the size of the priority queue.
168 * @returns The new size of the priority queue.
170 private decrementSize (): number {