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