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
95 return this.nodeArray
.shift()?.data
99 * Peeks at the first data.
100 * @returns The first data or `undefined` if the priority queue is empty.
102 public peekFirst (): T
| undefined {
103 return this.nodeArray
[0]?.data
107 * Peeks at the last data.
108 * @returns The last data or `undefined` if the priority queue is empty.
110 public peekLast (): T
| undefined {
111 return this.nodeArray
[this.nodeArray
.length
- 1]?.data
115 * Clears the priority queue.
117 public clear (): void {
124 * Returns an iterator for the priority queue.
126 * @returns An iterator for the priority queue.
127 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
129 [Symbol
.iterator
] (): Iterator
<T
> {
133 if (i
>= this.nodeArray
.length
) {
139 const value
= this.nodeArray
[i
].data
150 * Increments the size of the priority queue.
152 * @returns The new size of the priority queue.
154 private incrementSize (): number {
156 if (this.size
> this.maxSize
) {
157 this.maxSize
= this.size
163 * Decrements the size of the priority queue.
165 * @returns The new size of the priority queue.
167 private decrementSize (): number {