Commit | Line | Data |
---|---|---|
f8d5d8fd JB |
1 | /** |
2 | * Default buffer size. | |
3 | */ | |
4 | export const defaultQueueSize = 2048 | |
5 | ||
6 | /** | |
65c178f1 | 7 | * Fixed priority queue node. |
f8d5d8fd JB |
8 | * @typeParam T - Type of priority queue node data. |
9 | * @internal | |
10 | */ | |
65c178f1 | 11 | export interface FixedPriorityQueueNode<T> { |
f8d5d8fd JB |
12 | data: T |
13 | priority: number | |
14 | } | |
15 | ||
eadb37e2 JB |
16 | /** |
17 | * Fixed priority queue. | |
eadb37e2 JB |
18 | * @typeParam T - Type of fixed priority queue data. |
19 | * @internal | |
20 | */ | |
f8d5d8fd JB |
21 | export class FixedPriorityQueue<T> { |
22 | private start!: number | |
3a502712 | 23 | private readonly nodeArray: FixedPriorityQueueNode<T>[] |
10b1b252 | 24 | /** The fixed priority queue capacity. */ |
9df282a0 | 25 | public readonly capacity: number |
fcfc3353 | 26 | /** The fixed priority queue size. */ |
f8d5d8fd | 27 | public size!: number |
fcfc3353 JB |
28 | /** Whether to enable priority. */ |
29 | public enablePriority: boolean | |
f8d5d8fd | 30 | |
9df282a0 JB |
31 | /** |
32 | * Constructs a fixed priority queue. | |
9df282a0 | 33 | * @param size - Fixed priority queue size. @defaultValue defaultQueueSize |
fcfc3353 | 34 | * @param enablePriority - Whether to enable priority. @defaultValue false |
9df282a0 JB |
35 | * @returns FixedPriorityQueue. |
36 | */ | |
fcfc3353 | 37 | constructor (size: number = defaultQueueSize, enablePriority = false) { |
f8d5d8fd | 38 | this.checkSize(size) |
9df282a0 | 39 | this.capacity = size |
fcfc3353 | 40 | this.enablePriority = enablePriority |
65c178f1 | 41 | this.nodeArray = new Array<FixedPriorityQueueNode<T>>(this.capacity) |
f8d5d8fd JB |
42 | this.clear() |
43 | } | |
44 | ||
e75373e6 JB |
45 | /** |
46 | * Checks if the fixed priority queue is empty. | |
e75373e6 JB |
47 | * @returns `true` if the fixed priority queue is empty, `false` otherwise. |
48 | */ | |
f8d5d8fd JB |
49 | public empty (): boolean { |
50 | return this.size === 0 | |
51 | } | |
52 | ||
e75373e6 JB |
53 | /** |
54 | * Checks if the fixed priority queue is full. | |
e75373e6 JB |
55 | * @returns `true` if the fixed priority queue is full, `false` otherwise. |
56 | */ | |
f8d5d8fd | 57 | public full (): boolean { |
9df282a0 | 58 | return this.size === this.capacity |
f8d5d8fd JB |
59 | } |
60 | ||
e75373e6 JB |
61 | /** |
62 | * Enqueue data into the fixed priority queue. | |
e75373e6 JB |
63 | * @param data - Data to enqueue. |
64 | * @param priority - Priority of the data. Lower values have higher priority. | |
65 | * @returns The new size of the priority queue. | |
13ed544a | 66 | * @throws If the fixed priority queue is full. |
e75373e6 | 67 | */ |
f8d5d8fd JB |
68 | public enqueue (data: T, priority?: number): number { |
69 | if (this.full()) { | |
70 | throw new Error('Priority queue is full') | |
71 | } | |
72 | priority = priority ?? 0 | |
73 | let inserted = false | |
fcfc3353 JB |
74 | if (this.enablePriority) { |
75 | let index = this.start | |
76 | for (let i = 0; i < this.size; i++) { | |
77 | if (this.nodeArray[index].priority > priority) { | |
78 | this.nodeArray.splice(index, 0, { data, priority }) | |
ac1d96cd | 79 | this.nodeArray.length = this.capacity |
fcfc3353 JB |
80 | inserted = true |
81 | break | |
82 | } | |
83 | ++index | |
84 | if (index === this.capacity) { | |
85 | index = 0 | |
86 | } | |
3451940f | 87 | } |
f8d5d8fd JB |
88 | } |
89 | if (!inserted) { | |
90 | let index = this.start + this.size | |
9df282a0 JB |
91 | if (index >= this.capacity) { |
92 | index -= this.capacity | |
f8d5d8fd JB |
93 | } |
94 | this.nodeArray[index] = { data, priority } | |
95 | } | |
10b1b252 | 96 | return ++this.size |
f8d5d8fd JB |
97 | } |
98 | ||
1d98bad2 JB |
99 | /** |
100 | * Gets data from the fixed priority queue. | |
1d98bad2 JB |
101 | * @param index - The index of the data to get. |
102 | * @returns The data at the index or `undefined` if the fixed priority queue is empty or the index is out of bounds. | |
103 | */ | |
104 | public get (index: number): T | undefined { | |
105 | if (this.empty() || index >= this.size) { | |
106 | return undefined | |
107 | } | |
108 | index += this.start | |
109 | if (index >= this.capacity) { | |
110 | index -= this.capacity | |
111 | } | |
112 | return this.nodeArray[index].data | |
113 | } | |
114 | ||
e75373e6 JB |
115 | /** |
116 | * Dequeue data from the fixed priority queue. | |
e75373e6 JB |
117 | * @returns The dequeued data or `undefined` if the priority queue is empty. |
118 | */ | |
f8d5d8fd JB |
119 | public dequeue (): T | undefined { |
120 | if (this.empty()) { | |
121 | return undefined | |
122 | } | |
123 | const index = this.start | |
124 | --this.size | |
125 | ++this.start | |
9df282a0 | 126 | if (this.start === this.capacity) { |
f8d5d8fd JB |
127 | this.start = 0 |
128 | } | |
129 | return this.nodeArray[index].data | |
130 | } | |
131 | ||
132 | /** | |
133 | * Clears the fixed priority queue. | |
134 | */ | |
135 | public clear (): void { | |
136 | this.start = 0 | |
137 | this.size = 0 | |
f8d5d8fd JB |
138 | } |
139 | ||
140 | /** | |
141 | * Returns an iterator for the fixed priority queue. | |
f8d5d8fd JB |
142 | * @returns An iterator for the fixed priority queue. |
143 | * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols | |
144 | */ | |
9df282a0 | 145 | public [Symbol.iterator] (): Iterator<T> { |
3451940f JB |
146 | let index = this.start |
147 | let i = 0 | |
f8d5d8fd JB |
148 | return { |
149 | next: () => { | |
150 | if (i >= this.size) { | |
151 | return { | |
152 | value: undefined, | |
3a502712 | 153 | done: true, |
f8d5d8fd JB |
154 | } |
155 | } | |
3451940f | 156 | const value = this.nodeArray[index].data |
02c769d0 JB |
157 | ++index |
158 | ++i | |
9df282a0 | 159 | if (index === this.capacity) { |
3451940f JB |
160 | index = 0 |
161 | } | |
f8d5d8fd JB |
162 | return { |
163 | value, | |
3a502712 | 164 | done: false, |
f8d5d8fd | 165 | } |
3a502712 | 166 | }, |
f8d5d8fd JB |
167 | } |
168 | } | |
169 | ||
e75373e6 | 170 | /** |
fcfc3353 | 171 | * Checks the queue size. |
fcfc3353 | 172 | * @param size - Queue size. |
e75373e6 | 173 | */ |
f8d5d8fd JB |
174 | private checkSize (size: number): void { |
175 | if (!Number.isSafeInteger(size)) { | |
176 | throw new TypeError( | |
6e5d7052 | 177 | `Invalid fixed priority queue size: '${size.toString()}' is not an integer` |
f8d5d8fd JB |
178 | ) |
179 | } | |
180 | if (size < 0) { | |
6e5d7052 JB |
181 | throw new RangeError( |
182 | `Invalid fixed priority queue size: ${size.toString()} < 0` | |
183 | ) | |
f8d5d8fd JB |
184 | } |
185 | } | |
186 | } |