ac75fc064c4a891a7805e8e1428853cc173b6d17
1 // Copyright Jerome Benoit. 2024. All Rights Reserved.
3 import { FixedPriorityQueue
} from
'./fixed-priority-queue.js'
4 import { FixedQueue
} from
'./fixed-queue.js'
5 import { defaultBucketSize
, type FixedQueueNode
, type IFixedQueue
, type PriorityQueueNode
} from
'./utility-types.js'
9 * @typeParam T - Type of priority queue data.
12 export class PriorityQueue
<T
> {
13 private head
!: PriorityQueueNode
<T
>
14 private tail
!: PriorityQueueNode
<T
>
15 private readonly bucketSize
: number
16 private priorityEnabled
: boolean
17 /** The priority queue maximum size. */
18 public maxSize
!: number
21 * Constructs a priority queue.
22 * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize
23 * @param enablePriority - Whether to enable priority. @defaultValue false
24 * @returns PriorityQueue.
27 bucketSize
: number = defaultBucketSize
,
28 enablePriority
= false
30 if (!Number.isSafeInteger(bucketSize
)) {
32 `Invalid bucket size: '${bucketSize.toString()}' is not an integer`
36 throw new RangeError(`Invalid bucket size: ${bucketSize.toString()} < 0`)
38 this.bucketSize
= bucketSize
39 this.priorityEnabled
= enablePriority
44 * The priority queue size.
45 * @returns The priority queue size.
47 public get
size (): number {
48 let node
: PriorityQueueNode
<T
> | undefined = this.tail
50 while (node
!= null) {
57 public get
enablePriority (): boolean {
58 return this.priorityEnabled
61 public set
enablePriority (enablePriority
: boolean) {
62 if (this.priorityEnabled
=== enablePriority
) {
65 this.priorityEnabled
= enablePriority
66 let head
: PriorityQueueNode
<T
>
67 let tail
: PriorityQueueNode
<T
>
68 let prevNode
: PriorityQueueNode
<T
> | undefined
69 let node
: PriorityQueueNode
<T
> | undefined = this.tail
71 while (node
!= null) {
72 const currentNode
= this.getPriorityQueueNode(node
.nodeArray
)
76 if (prevNode
!= null) {
77 prevNode
.next
= currentNode
79 prevNode
= currentNode
80 if (node
.next
== null) {
86 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
88 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
93 * The number of filled prioritized buckets.
94 * @returns The number of filled prioritized buckets.
96 public get
buckets (): number {
97 return Math.trunc(this.size
/ this.bucketSize
)
101 * Enqueue data into the priority queue.
102 * @param data - Data to enqueue.
103 * @param priority - Priority of the data. Lower values have higher priority.
104 * @returns The new size of the priority queue.
106 public enqueue (data
: T
, priority
?: number): number {
107 if (this.head
.full()) {
108 this.head
= this.head
.next
= this.getPriorityQueueNode()
110 this.head
.enqueue(data
, priority
)
111 const size
= this.size
112 if (size
> this.maxSize
) {
119 * Dequeue data from the priority queue.
120 * @param bucket - The prioritized bucket to dequeue from.
121 * @returns The dequeued data or `undefined` if the priority queue is empty.
123 public dequeue (bucket
?: number): T
| undefined {
124 let tail
: PriorityQueueNode
<T
> | undefined = this.tail
125 let tailChanged
= false
126 if (bucket
!= null && bucket
> 0) {
127 let currentBucket
= 1
128 while (tail
!= null) {
129 if (currentBucket
=== bucket
) {
135 tailChanged
= tail
!== this.tail
137 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
138 const data
= tail
!.dequeue()
139 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
141 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
142 if (!tailChanged
&& tail
!.next
!= null) {
143 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
144 this.tail
= tail
!.next
145 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
147 } else if (tailChanged
) {
148 let node
: PriorityQueueNode
<T
> | undefined = this.tail
149 while (node
!= null) {
150 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
151 if (node
.next
=== tail
&& tail
!.next
!= null) {
152 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
153 node
.next
= tail
!.next
154 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
157 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
158 } else if (node
.next
=== tail
&& tail
!.next
== null) {
171 * Clears the priority queue.
173 public clear (): void {
174 this.head
= this.tail
= this.getPriorityQueueNode()
179 * Returns an iterator for the priority queue.
180 * @returns An iterator for the priority queue.
181 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
183 public [Symbol
.iterator
] (): Iterator
<T
> {
188 const value
= node
.get(index
) as T
196 if (index
=== node
.capacity
&& node
.next
!= null) {
208 private getPriorityQueueNode (nodeArray
?: FixedQueueNode
<T
>[]): PriorityQueueNode
<T
> {
209 let fixedQueue
: IFixedQueue
<T
>
210 if (this.priorityEnabled
) {
211 fixedQueue
= new FixedPriorityQueue(this.bucketSize
)
213 fixedQueue
= new FixedQueue(this.bucketSize
)
215 if (nodeArray
!= null) {
216 fixedQueue
.nodeArray
= nodeArray