Commit | Line | Data |
---|---|---|
95d1a734 JB |
1 | // Copyright Jerome Benoit. 2024. All Rights Reserved. |
2 | ||
bcfb06ce | 3 | /** |
95d1a734 JB |
4 | * Priority queue node. |
5 | * | |
6 | * @typeParam T - Type of priority queue node data. | |
bcfb06ce JB |
7 | * @internal |
8 | */ | |
95d1a734 | 9 | export interface PriorityQueueNode<T> { |
bcfb06ce JB |
10 | data: T |
11 | priority: number | |
12 | } | |
13 | ||
14 | /** | |
95d1a734 | 15 | * Priority queue. |
bcfb06ce JB |
16 | * |
17 | * @typeParam T - Type of priority queue data. | |
18 | * @internal | |
19 | */ | |
20 | export class PriorityQueue<T> { | |
21 | private nodeArray!: Array<PriorityQueueNode<T>> | |
bd8b441c | 22 | /** Prioritized bucket size. */ |
2107bc57 | 23 | private readonly bucketSize: number |
bcfb06ce JB |
24 | /** The size of the priority queue. */ |
25 | public size!: number | |
26 | /** The maximum size of the priority queue. */ | |
27 | public maxSize!: number | |
28 | ||
0d4e88b3 JB |
29 | /** |
30 | * The number of filled prioritized buckets. | |
31 | */ | |
32 | public get buckets (): number { | |
80115618 | 33 | return this.bucketSize === Number.POSITIVE_INFINITY |
2107bc57 JB |
34 | ? 1 |
35 | : Math.trunc(this.nodeArray.length / this.bucketSize) | |
0d4e88b3 JB |
36 | } |
37 | ||
bd8b441c | 38 | /** |
95d1a734 | 39 | * Constructs a priority queue. |
bd8b441c | 40 | * |
80115618 | 41 | * @param bucketSize - Prioritized bucket size. @defaultValue Number.POSITIVE_INFINITY |
bd8b441c | 42 | */ |
80115618 JB |
43 | public constructor (bucketSize = Number.POSITIVE_INFINITY) { |
44 | if ( | |
45 | bucketSize !== Number.POSITIVE_INFINITY && | |
46 | !Number.isSafeInteger(bucketSize) | |
47 | ) { | |
2107bc57 | 48 | throw new TypeError('bucketSize must be an integer') |
e41b0271 | 49 | } |
2107bc57 JB |
50 | if (bucketSize < 1) { |
51 | throw new RangeError('bucketSize must be greater than or equal to 1') | |
e41b0271 | 52 | } |
2107bc57 | 53 | this.bucketSize = bucketSize |
e41b0271 | 54 | this.clear() |
bcfb06ce JB |
55 | } |
56 | ||
57 | /** | |
58 | * Enqueue data into the priority queue. | |
59 | * | |
60 | * @param data - Data to enqueue. | |
61 | * @param priority - Priority of the data. Lower values have higher priority. | |
62 | * @returns The new size of the priority queue. | |
63 | */ | |
64 | public enqueue (data: T, priority?: number): number { | |
65 | priority = priority ?? 0 | |
2107bc57 | 66 | const startIndex = |
80115618 JB |
67 | this.bucketSize === Number.POSITIVE_INFINITY |
68 | ? 0 | |
69 | : this.buckets * this.bucketSize | |
bcfb06ce | 70 | let inserted = false |
e41b0271 JB |
71 | for (let index = startIndex; index < this.nodeArray.length; index++) { |
72 | if (this.nodeArray[index].priority > priority) { | |
bcfb06ce JB |
73 | this.nodeArray.splice(index, 0, { data, priority }) |
74 | inserted = true | |
75 | break | |
76 | } | |
77 | } | |
78 | if (!inserted) { | |
79 | this.nodeArray.push({ data, priority }) | |
80 | } | |
81 | return this.incrementSize() | |
82 | } | |
83 | ||
84 | /** | |
85 | * Dequeue data from the priority queue. | |
86 | * | |
95d1a734 | 87 | * @param bucket - The prioritized bucket to dequeue from. @defaultValue 0 |
bcfb06ce JB |
88 | * @returns The dequeued data or `undefined` if the priority queue is empty. |
89 | */ | |
95d1a734 | 90 | public dequeue (bucket = 0): T | undefined { |
80115618 | 91 | if (this.bucketSize !== Number.POSITIVE_INFINITY && bucket > 0) { |
95d1a734 | 92 | while (bucket > 0) { |
2107bc57 | 93 | const index = bucket * this.bucketSize |
95d1a734 JB |
94 | // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition |
95 | if (this.nodeArray[index] != null) { | |
96 | --this.size | |
97 | return this.nodeArray.splice(index, 1)[0].data | |
98 | } | |
99 | --bucket | |
100 | } | |
101 | } | |
65729b19 | 102 | this.decrementSize() |
bcfb06ce JB |
103 | return this.nodeArray.shift()?.data |
104 | } | |
105 | ||
106 | /** | |
107 | * Peeks at the first data. | |
108 | * @returns The first data or `undefined` if the priority queue is empty. | |
109 | */ | |
110 | public peekFirst (): T | undefined { | |
111 | return this.nodeArray[0]?.data | |
112 | } | |
113 | ||
114 | /** | |
115 | * Peeks at the last data. | |
116 | * @returns The last data or `undefined` if the priority queue is empty. | |
117 | */ | |
118 | public peekLast (): T | undefined { | |
119 | return this.nodeArray[this.nodeArray.length - 1]?.data | |
120 | } | |
121 | ||
122 | /** | |
123 | * Clears the priority queue. | |
124 | */ | |
125 | public clear (): void { | |
126 | this.nodeArray = [] | |
127 | this.size = 0 | |
128 | this.maxSize = 0 | |
129 | } | |
130 | ||
131 | /** | |
95d1a734 JB |
132 | * Returns an iterator for the priority queue. |
133 | * | |
2be9b405 | 134 | * @returns An iterator for the priority queue. |
95d1a734 JB |
135 | * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols |
136 | */ | |
137 | [Symbol.iterator] (): Iterator<T> { | |
138 | let i = 0 | |
139 | return { | |
140 | next: () => { | |
141 | if (i >= this.nodeArray.length) { | |
142 | return { | |
143 | value: undefined, | |
144 | done: true | |
145 | } | |
146 | } | |
147 | const value = this.nodeArray[i].data | |
148 | i++ | |
149 | return { | |
150 | value, | |
151 | done: false | |
152 | } | |
153 | } | |
154 | } | |
155 | } | |
156 | ||
157 | /** | |
158 | * Increments the size of the priority queue. | |
bcfb06ce | 159 | * |
95d1a734 | 160 | * @returns The new size of the priority queue. |
bcfb06ce JB |
161 | */ |
162 | private incrementSize (): number { | |
163 | ++this.size | |
164 | if (this.size > this.maxSize) { | |
165 | this.maxSize = this.size | |
166 | } | |
167 | return this.size | |
168 | } | |
65729b19 JB |
169 | |
170 | /** | |
171 | * Decrements the size of the priority queue. | |
172 | * | |
173 | * @returns The new size of the priority queue. | |
174 | */ | |
175 | private decrementSize (): number { | |
176 | if (this.size > 0) { | |
177 | --this.size | |
178 | } | |
179 | return this.size | |
180 | } | |
bcfb06ce | 181 | } |