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