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 * Constructs a priority queue.
32 * @param k - Prioritized bucket size.
34 public constructor (k
= Infinity) {
35 if (k
!== Infinity && !Number.isSafeInteger(k
)) {
36 throw new TypeError('k must be an integer')
39 throw new RangeError('k must be greater than or equal to 1')
46 * Enqueue data into the priority queue.
48 * @param data - Data to enqueue.
49 * @param priority - Priority of the data. Lower values have higher priority.
50 * @returns The new size of the priority queue.
52 public enqueue (data
: T
, priority
?: number): number {
53 priority
= priority
?? 0
55 this.k
=== Infinity || this.nodeArray
.length
/ this.k
< 1
57 : Math.trunc(this.nodeArray
.length
/ this.k
) * this.k
59 for (let index
= startIndex
; index
< this.nodeArray
.length
; index
++) {
60 if (this.nodeArray
[index
].priority
> priority
) {
61 this.nodeArray
.splice(index
, 0, { data
, priority
})
67 this.nodeArray
.push({ data
, priority
})
69 return this.incrementSize()
73 * Dequeue data from the priority queue.
75 * @param bucket - The prioritized bucket to dequeue from. @defaultValue 0
76 * @returns The dequeued data or `undefined` if the priority queue is empty.
78 public dequeue (bucket
= 0): T
| undefined {
79 if (this.k
!== Infinity && bucket
> 0) {
81 const index
= bucket
* this.k
82 // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
83 if (this.nodeArray
[index
] != null) {
85 return this.nodeArray
.splice(index
, 1)[0].data
93 return this.nodeArray
.shift()?.data
97 * Peeks at the first data.
98 * @returns The first data or `undefined` if the priority queue is empty.
100 public peekFirst (): T
| undefined {
101 return this.nodeArray
[0]?.data
105 * Peeks at the last data.
106 * @returns The last data or `undefined` if the priority queue is empty.
108 public peekLast (): T
| undefined {
109 return this.nodeArray
[this.nodeArray
.length
- 1]?.data
113 * Clears the priority queue.
115 public clear (): void {
122 * Returns an iterator for the priority queue.
124 * @returns An iterator for the deque.
125 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
127 [Symbol
.iterator
] (): Iterator
<T
> {
131 if (i
>= this.nodeArray
.length
) {
137 const value
= this.nodeArray
[i
].data
148 * Increments the size of the priority queue.
150 * @returns The new size of the priority queue.
152 private incrementSize (): number {
154 if (this.size
> this.maxSize
) {
155 this.maxSize
= this.size