Commit | Line | Data |
---|---|---|
95d1a734 JB |
1 | // Copyright Jerome Benoit. 2024. All Rights Reserved. |
2 | ||
9df282a0 | 3 | import { FixedPriorityQueue } from './fixed-priority-queue.js' |
097dea68 JB |
4 | import { FixedQueue } from './fixed-queue.js' |
5 | import { defaultBucketSize, type FixedQueueNode, type IFixedQueue, type PriorityQueueNode } from './utility-types.js' | |
bcfb06ce JB |
6 | |
7 | /** | |
95d1a734 | 8 | * Priority queue. |
bcfb06ce JB |
9 | * @typeParam T - Type of priority queue data. |
10 | * @internal | |
11 | */ | |
12 | export class PriorityQueue<T> { | |
9df282a0 JB |
13 | private head!: PriorityQueueNode<T> |
14 | private tail!: PriorityQueueNode<T> | |
2107bc57 | 15 | private readonly bucketSize: number |
097dea68 | 16 | private priorityEnabled: boolean |
13ed544a | 17 | /** The priority queue maximum size. */ |
bcfb06ce JB |
18 | public maxSize!: number |
19 | ||
bd8b441c | 20 | /** |
95d1a734 | 21 | * Constructs a priority queue. |
9df282a0 | 22 | * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize |
fcfc3353 | 23 | * @param enablePriority - Whether to enable priority. @defaultValue false |
9df282a0 | 24 | * @returns PriorityQueue. |
bd8b441c | 25 | */ |
fcfc3353 JB |
26 | public constructor ( |
27 | bucketSize: number = defaultBucketSize, | |
28 | enablePriority = false | |
29 | ) { | |
e75373e6 | 30 | if (!Number.isSafeInteger(bucketSize)) { |
579aa5bd | 31 | throw new TypeError( |
6e5d7052 | 32 | `Invalid bucket size: '${bucketSize.toString()}' is not an integer` |
579aa5bd | 33 | ) |
e75373e6 | 34 | } |
579aa5bd | 35 | if (bucketSize < 0) { |
6e5d7052 | 36 | throw new RangeError(`Invalid bucket size: ${bucketSize.toString()} < 0`) |
e75373e6 | 37 | } |
2107bc57 | 38 | this.bucketSize = bucketSize |
097dea68 JB |
39 | this.priorityEnabled = enablePriority |
40 | this.clear() | |
bcfb06ce JB |
41 | } |
42 | ||
e75373e6 | 43 | /** |
13ed544a | 44 | * The priority queue size. |
ed20267e | 45 | * @returns The priority queue size. |
e75373e6 | 46 | */ |
9df282a0 JB |
47 | public get size (): number { |
48 | let node: PriorityQueueNode<T> | undefined = this.tail | |
49 | let size = 0 | |
50 | while (node != null) { | |
51 | size += node.size | |
52 | node = node.next | |
53 | } | |
54 | return size | |
55 | } | |
56 | ||
fcfc3353 | 57 | public get enablePriority (): boolean { |
097dea68 | 58 | return this.priorityEnabled |
fcfc3353 JB |
59 | } |
60 | ||
61 | public set enablePriority (enablePriority: boolean) { | |
097dea68 | 62 | if (this.priorityEnabled === enablePriority) { |
fcfc3353 JB |
63 | return |
64 | } | |
097dea68 JB |
65 | this.priorityEnabled = enablePriority |
66 | let head: PriorityQueueNode<T> | |
67 | let tail: PriorityQueueNode<T> | |
68 | let prevNode : PriorityQueueNode<T> | undefined | |
fcfc3353 | 69 | let node: PriorityQueueNode<T> | undefined = this.tail |
097dea68 | 70 | let buckets = 0 |
fcfc3353 | 71 | while (node != null) { |
097dea68 JB |
72 | const currentNode = this.getPriorityQueueNode(node.nodeArray) |
73 | if (buckets === 0) { | |
74 | tail = currentNode | |
75 | } | |
76 | if (prevNode != null) { | |
77 | prevNode.next = currentNode | |
78 | } | |
79 | prevNode = currentNode | |
80 | if (node.next == null) { | |
81 | head = currentNode | |
82 | } | |
83 | ++buckets | |
fcfc3353 JB |
84 | node = node.next |
85 | } | |
097dea68 JB |
86 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
87 | this.head = head! | |
88 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
89 | this.tail = tail! | |
fcfc3353 JB |
90 | } |
91 | ||
e75373e6 JB |
92 | /** |
93 | * The number of filled prioritized buckets. | |
ed20267e | 94 | * @returns The number of filled prioritized buckets. |
e75373e6 JB |
95 | */ |
96 | public get buckets (): number { | |
97 | return Math.trunc(this.size / this.bucketSize) | |
98 | } | |
99 | ||
bcfb06ce JB |
100 | /** |
101 | * Enqueue data into the priority queue. | |
bcfb06ce JB |
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. | |
105 | */ | |
106 | public enqueue (data: T, priority?: number): number { | |
9df282a0 | 107 | if (this.head.full()) { |
097dea68 | 108 | this.head = this.head.next = this.getPriorityQueueNode() |
bcfb06ce | 109 | } |
9df282a0 JB |
110 | this.head.enqueue(data, priority) |
111 | const size = this.size | |
112 | if (size > this.maxSize) { | |
113 | this.maxSize = size | |
bcfb06ce | 114 | } |
9df282a0 | 115 | return size |
bcfb06ce JB |
116 | } |
117 | ||
118 | /** | |
119 | * Dequeue data from the priority queue. | |
9df282a0 | 120 | * @param bucket - The prioritized bucket to dequeue from. |
bcfb06ce JB |
121 | * @returns The dequeued data or `undefined` if the priority queue is empty. |
122 | */ | |
9df282a0 JB |
123 | public dequeue (bucket?: number): T | undefined { |
124 | let tail: PriorityQueueNode<T> | undefined = this.tail | |
1d98bad2 JB |
125 | let tailChanged = false |
126 | if (bucket != null && bucket > 0) { | |
127 | let currentBucket = 1 | |
9df282a0 | 128 | while (tail != null) { |
9df282a0 JB |
129 | if (currentBucket === bucket) { |
130 | break | |
95d1a734 | 131 | } |
1d98bad2 | 132 | ++currentBucket |
9df282a0 | 133 | tail = tail.next |
95d1a734 | 134 | } |
017f9985 | 135 | tailChanged = tail !== this.tail |
95d1a734 | 136 | } |
9df282a0 JB |
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 | |
017f9985 JB |
140 | if (tail!.empty()) { |
141 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
142 | if (!tailChanged && tail!.next != null) { | |
1d98bad2 JB |
143 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
144 | this.tail = tail!.next | |
017f9985 JB |
145 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
146 | delete tail!.next | |
147 | } else if (tailChanged) { | |
9df282a0 JB |
148 | let node: PriorityQueueNode<T> | undefined = this.tail |
149 | while (node != null) { | |
017f9985 JB |
150 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
151 | if (node.next === tail && tail!.next != null) { | |
9df282a0 JB |
152 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
153 | node.next = tail!.next | |
017f9985 JB |
154 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
155 | delete tail!.next | |
156 | break | |
157 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
158 | } else if (node.next === tail && tail!.next == null) { | |
159 | delete node.next | |
160 | this.head = node | |
9df282a0 JB |
161 | break |
162 | } | |
163 | node = node.next | |
164 | } | |
165 | } | |
9df282a0 JB |
166 | } |
167 | return data | |
bcfb06ce JB |
168 | } |
169 | ||
170 | /** | |
171 | * Clears the priority queue. | |
172 | */ | |
173 | public clear (): void { | |
097dea68 | 174 | this.head = this.tail = this.getPriorityQueueNode() |
bcfb06ce JB |
175 | this.maxSize = 0 |
176 | } | |
177 | ||
178 | /** | |
95d1a734 | 179 | * Returns an iterator for the priority queue. |
2be9b405 | 180 | * @returns An iterator for the priority queue. |
95d1a734 JB |
181 | * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols |
182 | */ | |
9df282a0 | 183 | public [Symbol.iterator] (): Iterator<T> { |
1d98bad2 | 184 | let index = 0 |
9df282a0 | 185 | let node = this.tail |
95d1a734 JB |
186 | return { |
187 | next: () => { | |
1d98bad2 JB |
188 | const value = node.get(index) as T |
189 | if (value == null) { | |
95d1a734 JB |
190 | return { |
191 | value: undefined, | |
3a502712 | 192 | done: true, |
95d1a734 JB |
193 | } |
194 | } | |
1d98bad2 JB |
195 | ++index |
196 | if (index === node.capacity && node.next != null) { | |
9df282a0 | 197 | node = node.next |
1d98bad2 | 198 | index = 0 |
9df282a0 | 199 | } |
95d1a734 JB |
200 | return { |
201 | value, | |
3a502712 | 202 | done: false, |
95d1a734 | 203 | } |
3a502712 | 204 | }, |
95d1a734 JB |
205 | } |
206 | } | |
097dea68 JB |
207 | |
208 | private getPriorityQueueNode (nodeArray?: FixedQueueNode<T>[]): PriorityQueueNode<T> { | |
209 | let fixedQueue: IFixedQueue<T> | |
210 | if (this.priorityEnabled) { | |
211 | fixedQueue = new FixedPriorityQueue(this.bucketSize) | |
212 | } else { | |
213 | fixedQueue = new FixedQueue(this.bucketSize) | |
214 | } | |
215 | if (nodeArray != null) { | |
216 | fixedQueue.nodeArray = nodeArray | |
217 | } | |
218 | return fixedQueue | |
219 | } | |
bcfb06ce | 220 | } |