1 // Copyright Jerome Benoit. 2024. All Rights Reserved.
3 import { FixedPriorityQueue
} from
'./fixed-priority-queue.js'
8 export const defaultBucketSize
= 2048
11 * Priority queue node.
12 * @typeParam T - Type of priority queue node data.
15 export interface PriorityQueueNode
<T
> extends FixedPriorityQueue
<T
> {
16 next
?: FixedPriorityQueue
<T
>
21 * @typeParam T - Type of priority queue data.
24 export class PriorityQueue
<T
> {
25 private head
!: PriorityQueueNode
<T
>
26 private tail
!: PriorityQueueNode
<T
>
27 private readonly bucketSize
: number
28 /** The priority queue maximum size. */
29 public maxSize
!: number
32 * Constructs a priority queue.
33 * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize
34 * @param enablePriority - Whether to enable priority. @defaultValue false
35 * @returns PriorityQueue.
38 bucketSize
: number = defaultBucketSize
,
39 enablePriority
= false
41 if (!Number.isSafeInteger(bucketSize
)) {
43 `Invalid bucket size: '${bucketSize.toString()}' is not an integer`
47 throw new RangeError(`Invalid bucket size: ${bucketSize.toString()} < 0`)
49 this.bucketSize
= bucketSize
50 this.head
= this.tail
= new FixedPriorityQueue(
58 * The priority queue size.
59 * @returns The priority queue size.
61 public get
size (): number {
62 let node
: PriorityQueueNode
<T
> | undefined = this.tail
64 while (node
!= null) {
71 public get
enablePriority (): boolean {
72 return this.head
.enablePriority
75 public set
enablePriority (enablePriority
: boolean) {
76 if (this.head
.enablePriority
=== enablePriority
) {
79 let node
: PriorityQueueNode
<T
> | undefined = this.tail
80 while (node
!= null) {
81 node
.enablePriority
= enablePriority
87 * The number of filled prioritized buckets.
88 * @returns The number of filled prioritized buckets.
90 public get
buckets (): number {
91 return Math.trunc(this.size
/ this.bucketSize
)
95 * Enqueue data into the priority queue.
96 * @param data - Data to enqueue.
97 * @param priority - Priority of the data. Lower values have higher priority.
98 * @returns The new size of the priority queue.
100 public enqueue (data
: T
, priority
?: number): number {
101 if (this.head
.full()) {
102 this.head
= this.head
.next
= new FixedPriorityQueue(
107 this.head
.enqueue(data
, priority
)
108 const size
= this.size
109 if (size
> this.maxSize
) {
116 * Dequeue data from the priority queue.
117 * @param bucket - The prioritized bucket to dequeue from.
118 * @returns The dequeued data or `undefined` if the priority queue is empty.
120 public dequeue (bucket
?: number): T
| undefined {
121 let tail
: PriorityQueueNode
<T
> | undefined = this.tail
122 let tailChanged
= false
123 if (bucket
!= null && bucket
> 0) {
124 let currentBucket
= 1
125 while (tail
!= null) {
126 if (currentBucket
=== bucket
) {
134 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
135 const data
= tail
!.dequeue()
136 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
137 if (tail
!.empty() && tail
!.next
!= null) {
139 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
140 this.tail
= tail
!.next
142 let node
: PriorityQueueNode
<T
> | undefined = this.tail
143 while (node
!= null) {
144 if (node
.next
=== tail
) {
145 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
146 node
.next
= tail
!.next
152 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
159 * Clears the priority queue.
161 public clear (): void {
162 this.head
= this.tail
= new FixedPriorityQueue(
170 * Returns an iterator for the priority queue.
171 * @returns An iterator for the priority queue.
172 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
174 public [Symbol
.iterator
] (): Iterator
<T
> {
179 const value
= node
.get(index
) as T
187 if (index
=== node
.capacity
&& node
.next
!= null) {