1 // Copyright Jerome Benoit. 2024. All Rights Reserved.
3 import { FixedPriorityQueue
} from
'./fixed-priority-queue.js'
4 import { FixedQueue
} from
'./fixed-queue.js'
9 type PriorityQueueNode
,
10 } from
'./queue-types.js'
14 * @typeParam T - Type of priority queue data.
17 export class PriorityQueue
<T
> {
18 private head
!: PriorityQueueNode
<T
>
19 private tail
!: PriorityQueueNode
<T
>
20 private readonly bucketSize
: number
21 private priorityEnabled
: boolean
22 /** The priority queue maximum size. */
23 public maxSize
!: number
26 * Constructs a priority queue.
27 * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize
28 * @param enablePriority - Whether to enable priority. @defaultValue false
29 * @returns PriorityQueue.
32 bucketSize
: number = defaultBucketSize
,
33 enablePriority
= false
35 if (!Number.isSafeInteger(bucketSize
)) {
37 `Invalid bucket size: '${bucketSize.toString()}' is not an integer`
41 throw new RangeError(`Invalid bucket size: ${bucketSize.toString()} < 0`)
43 this.bucketSize
= bucketSize
44 this.priorityEnabled
= enablePriority
49 * The priority queue size.
50 * @returns The priority queue size.
52 public get
size (): number {
53 let node
: PriorityQueueNode
<T
> | undefined = this.tail
55 while (node
!= null) {
62 public get
enablePriority (): boolean {
63 return this.priorityEnabled
66 public set
enablePriority (enablePriority
: boolean) {
67 if (this.priorityEnabled
=== enablePriority
) {
70 this.priorityEnabled
= enablePriority
71 let head
: PriorityQueueNode
<T
>
72 let tail
: PriorityQueueNode
<T
>
73 let prevNode
: PriorityQueueNode
<T
> | undefined
74 let node
: PriorityQueueNode
<T
> | undefined = this.tail
76 while (node
!= null) {
77 const currentNode
= this.getPriorityQueueNode(node
.nodeArray
)
81 if (prevNode
!= null) {
82 prevNode
.next
= currentNode
84 prevNode
= currentNode
85 if (node
.next
== null) {
91 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
93 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
98 * The number of filled prioritized buckets.
99 * @returns The number of filled prioritized buckets.
101 public get
buckets (): number {
102 return Math.trunc(this.size
/ this.bucketSize
)
106 * Enqueue data into the priority queue.
107 * @param data - Data to enqueue.
108 * @param priority - Priority of the data. Lower values have higher priority.
109 * @returns The new size of the priority queue.
111 public enqueue (data
: T
, priority
?: number): number {
112 if (this.head
.full()) {
113 this.head
= this.head
.next
= this.getPriorityQueueNode()
115 this.head
.enqueue(data
, priority
)
116 const size
= this.size
117 if (size
> this.maxSize
) {
124 * Dequeue data from the priority queue.
125 * @param bucket - The prioritized bucket to dequeue from.
126 * @returns The dequeued data or `undefined` if the priority queue is empty.
128 public dequeue (bucket
?: number): T
| undefined {
129 let tail
: PriorityQueueNode
<T
> | undefined = this.tail
130 let tailChanged
= false
131 if (bucket
!= null && bucket
> 0) {
132 let currentBucket
= 1
133 while (tail
!= null) {
134 if (currentBucket
=== bucket
) {
140 tailChanged
= tail
!== this.tail
142 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
143 const data
= tail
!.dequeue()
144 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
146 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
147 if (!tailChanged
&& tail
!.next
!= null) {
148 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
149 this.tail
= tail
!.next
150 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
152 } else if (tailChanged
) {
153 let node
: PriorityQueueNode
<T
> | undefined = this.tail
154 while (node
!= null) {
155 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
156 if (node
.next
=== tail
&& tail
!.next
!= null) {
157 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
158 node
.next
= tail
!.next
159 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
162 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
163 } else if (node
.next
=== tail
&& tail
!.next
== null) {
176 * Clears the priority queue.
178 public clear (): void {
179 this.head
= this.tail
= this.getPriorityQueueNode()
184 * Returns an iterator for the priority queue.
185 * @returns An iterator for the priority queue.
186 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
188 public [Symbol
.iterator
] (): Iterator
<T
> {
193 const value
= node
.get(index
) as T
201 if (index
=== node
.capacity
&& node
.next
!= null) {
213 private getPriorityQueueNode (
214 nodeArray
?: FixedQueueNode
<T
>[]
215 ): PriorityQueueNode
<T
> {
216 let fixedQueue
: IFixedQueue
<T
>
217 if (this.priorityEnabled
) {
218 fixedQueue
= new FixedPriorityQueue(this.bucketSize
)
220 fixedQueue
= new FixedQueue(this.bucketSize
)
222 if (nodeArray
!= null) {
223 fixedQueue
.nodeArray
= nodeArray