Commit | Line | Data |
---|---|---|
95d1a734 JB |
1 | // Copyright Jerome Benoit. 2024. All Rights Reserved. |
2 | ||
9df282a0 JB |
3 | import { FixedPriorityQueue } from './fixed-priority-queue.js' |
4 | ||
5 | /** | |
6 | * Default bucket size. | |
7 | */ | |
8 | export const defaultBucketSize = 2048 | |
9 | ||
bcfb06ce | 10 | /** |
95d1a734 | 11 | * Priority queue node. |
95d1a734 | 12 | * @typeParam T - Type of priority queue node data. |
bcfb06ce JB |
13 | * @internal |
14 | */ | |
9df282a0 JB |
15 | export interface PriorityQueueNode<T> extends FixedPriorityQueue<T> { |
16 | next?: FixedPriorityQueue<T> | |
bcfb06ce JB |
17 | } |
18 | ||
19 | /** | |
95d1a734 | 20 | * Priority queue. |
bcfb06ce JB |
21 | * @typeParam T - Type of priority queue data. |
22 | * @internal | |
23 | */ | |
24 | export class PriorityQueue<T> { | |
9df282a0 JB |
25 | private head!: PriorityQueueNode<T> |
26 | private tail!: PriorityQueueNode<T> | |
2107bc57 | 27 | private readonly bucketSize: number |
13ed544a | 28 | /** The priority queue maximum size. */ |
bcfb06ce JB |
29 | public maxSize!: number |
30 | ||
bd8b441c | 31 | /** |
95d1a734 | 32 | * Constructs a priority queue. |
9df282a0 | 33 | * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize |
fcfc3353 | 34 | * @param enablePriority - Whether to enable priority. @defaultValue false |
9df282a0 | 35 | * @returns PriorityQueue. |
bd8b441c | 36 | */ |
fcfc3353 JB |
37 | public constructor ( |
38 | bucketSize: number = defaultBucketSize, | |
39 | enablePriority = false | |
40 | ) { | |
e75373e6 | 41 | if (!Number.isSafeInteger(bucketSize)) { |
579aa5bd | 42 | throw new TypeError( |
6e5d7052 | 43 | `Invalid bucket size: '${bucketSize.toString()}' is not an integer` |
579aa5bd | 44 | ) |
e75373e6 | 45 | } |
579aa5bd | 46 | if (bucketSize < 0) { |
6e5d7052 | 47 | throw new RangeError(`Invalid bucket size: ${bucketSize.toString()} < 0`) |
e75373e6 | 48 | } |
2107bc57 | 49 | this.bucketSize = bucketSize |
fcfc3353 JB |
50 | this.head = this.tail = new FixedPriorityQueue( |
51 | this.bucketSize, | |
52 | enablePriority | |
53 | ) | |
54 | this.maxSize = 0 | |
bcfb06ce JB |
55 | } |
56 | ||
e75373e6 | 57 | /** |
13ed544a | 58 | * The priority queue size. |
ed20267e | 59 | * @returns The priority queue size. |
e75373e6 | 60 | */ |
9df282a0 JB |
61 | public get size (): number { |
62 | let node: PriorityQueueNode<T> | undefined = this.tail | |
63 | let size = 0 | |
64 | while (node != null) { | |
65 | size += node.size | |
66 | node = node.next | |
67 | } | |
68 | return size | |
69 | } | |
70 | ||
fcfc3353 JB |
71 | public get enablePriority (): boolean { |
72 | return this.head.enablePriority | |
73 | } | |
74 | ||
75 | public set enablePriority (enablePriority: boolean) { | |
76 | if (this.head.enablePriority === enablePriority) { | |
77 | return | |
78 | } | |
79 | let node: PriorityQueueNode<T> | undefined = this.tail | |
80 | while (node != null) { | |
81 | node.enablePriority = enablePriority | |
82 | node = node.next | |
83 | } | |
84 | } | |
85 | ||
e75373e6 JB |
86 | /** |
87 | * The number of filled prioritized buckets. | |
ed20267e | 88 | * @returns The number of filled prioritized buckets. |
e75373e6 JB |
89 | */ |
90 | public get buckets (): number { | |
91 | return Math.trunc(this.size / this.bucketSize) | |
92 | } | |
93 | ||
bcfb06ce JB |
94 | /** |
95 | * Enqueue data into the priority queue. | |
bcfb06ce JB |
96 | * @param data - Data to enqueue. |
97 | * @param priority - Priority of the data. Lower values have higher priority. | |
98 | * @returns The new size of the priority queue. | |
99 | */ | |
100 | public enqueue (data: T, priority?: number): number { | |
9df282a0 | 101 | if (this.head.full()) { |
fcfc3353 JB |
102 | this.head = this.head.next = new FixedPriorityQueue( |
103 | this.bucketSize, | |
104 | this.enablePriority | |
105 | ) | |
bcfb06ce | 106 | } |
9df282a0 JB |
107 | this.head.enqueue(data, priority) |
108 | const size = this.size | |
109 | if (size > this.maxSize) { | |
110 | this.maxSize = size | |
bcfb06ce | 111 | } |
9df282a0 | 112 | return size |
bcfb06ce JB |
113 | } |
114 | ||
115 | /** | |
116 | * Dequeue data from the priority queue. | |
9df282a0 | 117 | * @param bucket - The prioritized bucket to dequeue from. |
bcfb06ce JB |
118 | * @returns The dequeued data or `undefined` if the priority queue is empty. |
119 | */ | |
9df282a0 JB |
120 | public dequeue (bucket?: number): T | undefined { |
121 | let tail: PriorityQueueNode<T> | undefined = this.tail | |
1d98bad2 JB |
122 | let tailChanged = false |
123 | if (bucket != null && bucket > 0) { | |
124 | let currentBucket = 1 | |
9df282a0 | 125 | while (tail != null) { |
9df282a0 JB |
126 | if (currentBucket === bucket) { |
127 | break | |
95d1a734 | 128 | } |
1d98bad2 | 129 | ++currentBucket |
9df282a0 | 130 | tail = tail.next |
95d1a734 | 131 | } |
017f9985 | 132 | tailChanged = tail !== this.tail |
95d1a734 | 133 | } |
9df282a0 JB |
134 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
135 | const data = tail!.dequeue() | |
136 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
017f9985 JB |
137 | if (tail!.empty()) { |
138 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
139 | if (!tailChanged && tail!.next != null) { | |
1d98bad2 JB |
140 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
141 | this.tail = tail!.next | |
017f9985 JB |
142 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
143 | delete tail!.next | |
144 | } else if (tailChanged) { | |
9df282a0 JB |
145 | let node: PriorityQueueNode<T> | undefined = this.tail |
146 | while (node != null) { | |
017f9985 JB |
147 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
148 | if (node.next === tail && tail!.next != null) { | |
9df282a0 JB |
149 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
150 | node.next = tail!.next | |
017f9985 JB |
151 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion |
152 | delete tail!.next | |
153 | break | |
154 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
155 | } else if (node.next === tail && tail!.next == null) { | |
156 | delete node.next | |
157 | this.head = node | |
9df282a0 JB |
158 | break |
159 | } | |
160 | node = node.next | |
161 | } | |
162 | } | |
9df282a0 JB |
163 | } |
164 | return data | |
bcfb06ce JB |
165 | } |
166 | ||
167 | /** | |
168 | * Clears the priority queue. | |
169 | */ | |
170 | public clear (): void { | |
fcfc3353 JB |
171 | this.head = this.tail = new FixedPriorityQueue( |
172 | this.bucketSize, | |
173 | this.enablePriority | |
174 | ) | |
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 | } | |
bcfb06ce | 207 | } |