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