4 export const defaultQueueSize
= 2048
7 * Fixed priority queue node.
8 * @typeParam T - Type of priority queue node data.
11 export interface FixedPriorityQueueNode
<T
> {
17 * Fixed priority queue.
18 * @typeParam T - Type of fixed priority queue data.
21 export class FixedPriorityQueue
<T
> {
22 private start
!: number
23 private readonly nodeArray
: FixedPriorityQueueNode
<T
>[]
24 /** The fixed priority queue capacity. */
25 public readonly capacity
: number
26 /** The fixed priority queue size. */
28 /** Whether to enable priority. */
29 public enablePriority
: boolean
32 * Constructs a fixed priority queue.
33 * @param size - Fixed priority queue size. @defaultValue defaultQueueSize
34 * @param enablePriority - Whether to enable priority. @defaultValue false
35 * @returns FixedPriorityQueue.
37 constructor (size
: number = defaultQueueSize
, enablePriority
= false) {
40 this.enablePriority
= enablePriority
41 this.nodeArray
= new Array<FixedPriorityQueueNode
<T
>>(this.capacity
)
46 * Checks if the fixed priority queue is empty.
47 * @returns `true` if the fixed priority queue is empty, `false` otherwise.
49 public empty (): boolean {
50 return this.size
=== 0
54 * Checks if the fixed priority queue is full.
55 * @returns `true` if the fixed priority queue is full, `false` otherwise.
57 public full (): boolean {
58 return this.size
=== this.capacity
62 * Enqueue data into the fixed priority queue.
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.
66 * @throws If the fixed priority queue is full.
68 public enqueue (data
: T
, priority
?: number): number {
70 throw new Error('Priority queue is full')
72 priority
= priority
?? 0
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
})
79 this.nodeArray
.length
= this.capacity
84 if (index
=== this.capacity
) {
90 let index
= this.start
+ this.size
91 if (index
>= this.capacity
) {
92 index
-= this.capacity
94 this.nodeArray
[index
] = { data
, priority
}
100 * Gets data from the fixed priority queue.
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.
104 public get (index
: number): T
| undefined {
105 if (this.empty() || index
>= this.size
) {
109 if (index
>= this.capacity
) {
110 index
-= this.capacity
112 return this.nodeArray
[index
].data
116 * Dequeue data from the fixed priority queue.
117 * @returns The dequeued data or `undefined` if the priority queue is empty.
119 public dequeue (): T
| undefined {
123 const index
= this.start
126 if (this.start
=== this.capacity
) {
129 return this.nodeArray
[index
].data
133 * Clears the fixed priority queue.
135 public clear (): void {
141 * Returns an iterator for the fixed priority queue.
142 * @returns An iterator for the fixed priority queue.
143 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
145 public [Symbol
.iterator
] (): Iterator
<T
> {
146 let index
= this.start
150 if (i
>= this.size
) {
156 const value
= this.nodeArray
[index
].data
159 if (index
=== this.capacity
) {
171 * Checks the queue size.
172 * @param size - Queue size.
174 private checkSize (size
: number): void {
175 if (!Number.isSafeInteger(size
)) {
177 `Invalid fixed priority queue size: '${size.toString()}' is not an integer`
181 throw new RangeError(
182 `Invalid fixed priority queue size: ${size.toString()} < 0`