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 JB |
11 | * Priority queue node. |
12 | * | |
13 | * @typeParam T - Type of priority queue node data. | |
bcfb06ce JB |
14 | * @internal |
15 | */ | |
9df282a0 JB |
16 | export interface PriorityQueueNode<T> extends FixedPriorityQueue<T> { |
17 | next?: FixedPriorityQueue<T> | |
bcfb06ce JB |
18 | } |
19 | ||
20 | /** | |
95d1a734 | 21 | * Priority queue. |
bcfb06ce JB |
22 | * |
23 | * @typeParam T - Type of priority queue data. | |
24 | * @internal | |
25 | */ | |
26 | export class PriorityQueue<T> { | |
9df282a0 JB |
27 | private head!: PriorityQueueNode<T> |
28 | private tail!: PriorityQueueNode<T> | |
2107bc57 | 29 | private readonly bucketSize: number |
13ed544a | 30 | /** The priority queue maximum size. */ |
bcfb06ce JB |
31 | public maxSize!: number |
32 | ||
bd8b441c | 33 | /** |
95d1a734 | 34 | * Constructs a priority queue. |
bd8b441c | 35 | * |
9df282a0 | 36 | * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize |
fcfc3353 | 37 | * @param enablePriority - Whether to enable priority. @defaultValue false |
9df282a0 | 38 | * @returns PriorityQueue. |
bd8b441c | 39 | */ |
fcfc3353 JB |
40 | public constructor ( |
41 | bucketSize: number = defaultBucketSize, | |
42 | enablePriority = false | |
43 | ) { | |
e75373e6 | 44 | if (!Number.isSafeInteger(bucketSize)) { |
579aa5bd JB |
45 | throw new TypeError( |
46 | `Invalid bucket size: '${bucketSize}' is not an integer` | |
47 | ) | |
e75373e6 | 48 | } |
579aa5bd JB |
49 | if (bucketSize < 0) { |
50 | throw new RangeError(`Invalid bucket size: ${bucketSize} < 0`) | |
e75373e6 | 51 | } |
2107bc57 | 52 | this.bucketSize = bucketSize |
fcfc3353 JB |
53 | this.head = this.tail = new FixedPriorityQueue( |
54 | this.bucketSize, | |
55 | enablePriority | |
56 | ) | |
57 | this.maxSize = 0 | |
bcfb06ce JB |
58 | } |
59 | ||
e75373e6 | 60 | /** |
13ed544a | 61 | * The priority queue size. |
e75373e6 | 62 | */ |
9df282a0 JB |
63 | public get size (): number { |
64 | let node: PriorityQueueNode<T> | undefined = this.tail | |
65 | let size = 0 | |
66 | while (node != null) { | |
67 | size += node.size | |
68 | node = node.next | |
69 | } | |
70 | return size | |
71 | } | |
72 | ||
fcfc3353 JB |
73 | public get enablePriority (): boolean { |
74 | return this.head.enablePriority | |
75 | } | |
76 | ||
77 | public set enablePriority (enablePriority: boolean) { | |
78 | if (this.head.enablePriority === enablePriority) { | |
79 | return | |
80 | } | |
81 | let node: PriorityQueueNode<T> | undefined = this.tail | |
82 | while (node != null) { | |
83 | node.enablePriority = enablePriority | |
84 | node = node.next | |
85 | } | |
86 | } | |
87 | ||
e75373e6 JB |
88 | /** |
89 | * The number of filled prioritized buckets. | |
90 | */ | |
91 | public get buckets (): number { | |
92 | return Math.trunc(this.size / this.bucketSize) | |
93 | } | |
94 | ||
bcfb06ce JB |
95 | /** |
96 | * Enqueue data into the priority queue. | |
97 | * | |
98 | * @param data - Data to enqueue. | |
99 | * @param priority - Priority of the data. Lower values have higher priority. | |
100 | * @returns The new size of the priority queue. | |
101 | */ | |
102 | public enqueue (data: T, priority?: number): number { | |
9df282a0 | 103 | if (this.head.full()) { |
fcfc3353 JB |
104 | this.head = this.head.next = new FixedPriorityQueue( |
105 | this.bucketSize, | |
106 | this.enablePriority | |
107 | ) | |
bcfb06ce | 108 | } |
9df282a0 JB |
109 | this.head.enqueue(data, priority) |
110 | const size = this.size | |
111 | if (size > this.maxSize) { | |
112 | this.maxSize = size | |
bcfb06ce | 113 | } |
9df282a0 | 114 | return size |
bcfb06ce JB |
115 | } |
116 | ||
117 | /** | |
118 | * Dequeue data from the priority queue. | |
119 | * | |
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 |
1d98bad2 | 134 | tailChanged = true |
95d1a734 JB |
135 | } |
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 | |
140 | if (tail!.empty() && tail!.next != null) { | |
1d98bad2 JB |
141 | if (!tailChanged) { |
142 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
143 | this.tail = tail!.next | |
9df282a0 JB |
144 | } else { |
145 | let node: PriorityQueueNode<T> | undefined = this.tail | |
146 | while (node != null) { | |
147 | if (node.next === tail) { | |
148 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
149 | node.next = tail!.next | |
150 | break | |
151 | } | |
152 | node = node.next | |
153 | } | |
154 | } | |
155 | // eslint-disable-next-line @typescript-eslint/no-non-null-assertion | |
156 | delete tail!.next | |
157 | } | |
158 | return data | |
bcfb06ce JB |
159 | } |
160 | ||
161 | /** | |
162 | * Clears the priority queue. | |
163 | */ | |
164 | public clear (): void { | |
fcfc3353 JB |
165 | this.head = this.tail = new FixedPriorityQueue( |
166 | this.bucketSize, | |
167 | this.enablePriority | |
168 | ) | |
bcfb06ce JB |
169 | this.maxSize = 0 |
170 | } | |
171 | ||
172 | /** | |
95d1a734 JB |
173 | * Returns an iterator for the priority queue. |
174 | * | |
2be9b405 | 175 | * @returns An iterator for the priority queue. |
95d1a734 JB |
176 | * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols |
177 | */ | |
9df282a0 | 178 | public [Symbol.iterator] (): Iterator<T> { |
1d98bad2 | 179 | let index = 0 |
9df282a0 | 180 | let node = this.tail |
95d1a734 JB |
181 | return { |
182 | next: () => { | |
1d98bad2 JB |
183 | const value = node.get(index) as T |
184 | if (value == null) { | |
95d1a734 JB |
185 | return { |
186 | value: undefined, | |
187 | done: true | |
188 | } | |
189 | } | |
1d98bad2 JB |
190 | ++index |
191 | if (index === node.capacity && node.next != null) { | |
9df282a0 | 192 | node = node.next |
1d98bad2 | 193 | index = 0 |
9df282a0 | 194 | } |
95d1a734 JB |
195 | return { |
196 | value, | |
197 | done: false | |
198 | } | |
199 | } | |
200 | } | |
201 | } | |
bcfb06ce | 202 | } |