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> { | |
9df282a0 JB |
18 | private head!: PriorityQueueNode<T> |
19 | private tail!: PriorityQueueNode<T> | |
2107bc57 | 20 | private readonly bucketSize: number |
097dea68 | 21 | private priorityEnabled: boolean |
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 | ||
e75373e6 | 48 | /** |
13ed544a | 49 | * The priority queue size. |
ed20267e | 50 | * @returns The priority queue size. |
e75373e6 | 51 | */ |
9df282a0 JB |
52 | public get size (): number { |
53 | let node: PriorityQueueNode<T> | undefined = this.tail | |
54 | let size = 0 | |
55 | while (node != null) { | |
56 | size += node.size | |
57 | node = node.next | |
58 | } | |
59 | return size | |
60 | } | |
61 | ||
fcfc3353 | 62 | public get enablePriority (): boolean { |
097dea68 | 63 | return this.priorityEnabled |
fcfc3353 JB |
64 | } |
65 | ||
66 | public set enablePriority (enablePriority: boolean) { | |
097dea68 | 67 | if (this.priorityEnabled === enablePriority) { |
fcfc3353 JB |
68 | return |
69 | } | |
097dea68 JB |
70 | this.priorityEnabled = enablePriority |
71 | let head: PriorityQueueNode<T> | |
72 | let tail: PriorityQueueNode<T> | |
9183b880 | 73 | let prevNode: PriorityQueueNode<T> | undefined |
fcfc3353 | 74 | let node: PriorityQueueNode<T> | undefined = this.tail |
097dea68 | 75 | let buckets = 0 |
fcfc3353 | 76 | while (node != null) { |
097dea68 JB |
77 | const currentNode = this.getPriorityQueueNode(node.nodeArray) |
78 | if (buckets === 0) { | |
79 | tail = currentNode | |
80 | } | |
81 | if (prevNode != null) { | |
82 | prevNode.next = currentNode | |
83 | } | |
84 | prevNode = currentNode | |
85 | if (node.next == null) { | |
86 | head = currentNode | |
87 | } | |
88 | ++buckets | |
fcfc3353 JB |
89 | node = node.next |
90 | } | |
097dea68 JB |
91 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
92 | this.head = head! | |
93 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
94 | this.tail = tail! | |
fcfc3353 JB |
95 | } |
96 | ||
e75373e6 JB |
97 | /** |
98 | * The number of filled prioritized buckets. | |
ed20267e | 99 | * @returns The number of filled prioritized buckets. |
e75373e6 JB |
100 | */ |
101 | public get buckets (): number { | |
102 | return Math.trunc(this.size / this.bucketSize) | |
103 | } | |
104 | ||
bcfb06ce JB |
105 | /** |
106 | * Enqueue data into the priority queue. | |
bcfb06ce JB |
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. | |
110 | */ | |
111 | public enqueue (data: T, priority?: number): number { | |
9df282a0 | 112 | if (this.head.full()) { |
097dea68 | 113 | this.head = this.head.next = this.getPriorityQueueNode() |
bcfb06ce | 114 | } |
9df282a0 JB |
115 | this.head.enqueue(data, priority) |
116 | const size = this.size | |
117 | if (size > this.maxSize) { | |
118 | this.maxSize = size | |
bcfb06ce | 119 | } |
9df282a0 | 120 | return size |
bcfb06ce JB |
121 | } |
122 | ||
123 | /** | |
124 | * Dequeue data from the priority queue. | |
9df282a0 | 125 | * @param bucket - The prioritized bucket to dequeue from. |
bcfb06ce JB |
126 | * @returns The dequeued data or `undefined` if the priority queue is empty. |
127 | */ | |
9df282a0 JB |
128 | public dequeue (bucket?: number): T | undefined { |
129 | let tail: PriorityQueueNode<T> | undefined = this.tail | |
1d98bad2 JB |
130 | let tailChanged = false |
131 | if (bucket != null && bucket > 0) { | |
132 | let currentBucket = 1 | |
9df282a0 | 133 | while (tail != null) { |
9df282a0 JB |
134 | if (currentBucket === bucket) { |
135 | break | |
95d1a734 | 136 | } |
1d98bad2 | 137 | ++currentBucket |
9df282a0 | 138 | tail = tail.next |
95d1a734 | 139 | } |
017f9985 | 140 | tailChanged = tail !== this.tail |
95d1a734 | 141 | } |
9df282a0 JB |
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 | |
017f9985 JB |
145 | if (tail!.empty()) { |
146 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
147 | if (!tailChanged && tail!.next != null) { | |
1d98bad2 JB |
148 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
149 | this.tail = tail!.next | |
017f9985 JB |
150 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
151 | delete tail!.next | |
152 | } else if (tailChanged) { | |
9df282a0 JB |
153 | let node: PriorityQueueNode<T> | undefined = this.tail |
154 | while (node != null) { | |
017f9985 JB |
155 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
156 | if (node.next === tail && tail!.next != null) { | |
9df282a0 JB |
157 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
158 | node.next = tail!.next | |
017f9985 JB |
159 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
160 | delete tail!.next | |
161 | break | |
162 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
163 | } else if (node.next === tail && tail!.next == null) { | |
164 | delete node.next | |
165 | this.head = node | |
9df282a0 JB |
166 | break |
167 | } | |
168 | node = node.next | |
169 | } | |
170 | } | |
9df282a0 JB |
171 | } |
172 | return data | |
bcfb06ce JB |
173 | } |
174 | ||
175 | /** | |
176 | * Clears the priority queue. | |
177 | */ | |
178 | public clear (): void { | |
097dea68 | 179 | this.head = this.tail = this.getPriorityQueueNode() |
bcfb06ce JB |
180 | this.maxSize = 0 |
181 | } | |
182 | ||
183 | /** | |
95d1a734 | 184 | * Returns an iterator for the priority queue. |
2be9b405 | 185 | * @returns An iterator for the priority queue. |
95d1a734 JB |
186 | * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols |
187 | */ | |
9df282a0 | 188 | public [Symbol.iterator] (): Iterator<T> { |
1d98bad2 | 189 | let index = 0 |
9df282a0 | 190 | let node = this.tail |
95d1a734 JB |
191 | return { |
192 | next: () => { | |
1d98bad2 JB |
193 | const value = node.get(index) as T |
194 | if (value == null) { | |
95d1a734 JB |
195 | return { |
196 | value: undefined, | |
3a502712 | 197 | done: true, |
95d1a734 JB |
198 | } |
199 | } | |
1d98bad2 JB |
200 | ++index |
201 | if (index === node.capacity && node.next != null) { | |
9df282a0 | 202 | node = node.next |
1d98bad2 | 203 | index = 0 |
9df282a0 | 204 | } |
95d1a734 JB |
205 | return { |
206 | value, | |
3a502712 | 207 | done: false, |
95d1a734 | 208 | } |
3a502712 | 209 | }, |
95d1a734 JB |
210 | } |
211 | } | |
097dea68 | 212 | |
9183b880 JB |
213 | private getPriorityQueueNode ( |
214 | nodeArray?: FixedQueueNode<T>[] | |
215 | ): PriorityQueueNode<T> { | |
097dea68 JB |
216 | let fixedQueue: IFixedQueue<T> |
217 | if (this.priorityEnabled) { | |
218 | fixedQueue = new FixedPriorityQueue(this.bucketSize) | |
219 | } else { | |
220 | fixedQueue = new FixedQueue(this.bucketSize) | |
221 | } | |
222 | if (nodeArray != null) { | |
223 | fixedQueue.nodeArray = nodeArray | |
224 | } | |
225 | return fixedQueue | |
226 | } | |
bcfb06ce | 227 | } |