4 export const defaultQueueSize
= 2048
7 * Fixed priority queue node.
9 * @typeParam T - Type of priority queue node data.
12 export interface FixedPriorityQueueNode
<T
> {
18 * Fixed priority queue.
20 * @typeParam T - Type of fixed priority queue data.
23 export class FixedPriorityQueue
<T
> {
24 private start
!: number
25 private readonly nodeArray
: Array<FixedPriorityQueueNode
<T
>>
26 /** The fixed priority queue capacity. */
27 public readonly capacity
: number
28 /** The fixed priority queue size. */
30 /** Whether to enable priority. */
31 public enablePriority
: boolean
34 * Constructs a fixed priority queue.
36 * @param size - Fixed priority queue size. @defaultValue defaultQueueSize
37 * @param enablePriority - Whether to enable priority. @defaultValue false
38 * @returns FixedPriorityQueue.
40 constructor (size
: number = defaultQueueSize
, enablePriority
= false) {
43 this.enablePriority
= enablePriority
44 this.nodeArray
= new Array<FixedPriorityQueueNode
<T
>>(this.capacity
)
49 * Checks if the fixed priority queue is empty.
51 * @returns `true` if the fixed priority queue is empty, `false` otherwise.
53 public empty (): boolean {
54 return this.size
=== 0
58 * Checks if the fixed priority queue is full.
60 * @returns `true` if the fixed priority queue is full, `false` otherwise.
62 public full (): boolean {
63 return this.size
=== this.capacity
67 * Enqueue data into the fixed priority queue.
69 * @param data - Data to enqueue.
70 * @param priority - Priority of the data. Lower values have higher priority.
71 * @returns The new size of the priority queue.
72 * @throws If the fixed priority queue is full.
74 public enqueue (data
: T
, priority
?: number): number {
76 throw new Error('Priority queue is full')
78 priority
= priority
?? 0
80 if (this.enablePriority
) {
81 let index
= this.start
82 for (let i
= 0; i
< this.size
; i
++) {
83 if (this.nodeArray
[index
].priority
> priority
) {
84 this.nodeArray
.splice(index
, 0, { data
, priority
})
85 this.nodeArray
.length
!== this.capacity
&&
86 (this.nodeArray
.length
= this.capacity
)
91 if (index
=== this.capacity
) {
97 let index
= this.start
+ this.size
98 if (index
>= this.capacity
) {
99 index
-= this.capacity
101 this.nodeArray
[index
] = { data
, priority
}
107 * Gets data from the fixed priority queue.
109 * @param index - The index of the data to get.
110 * @returns The data at the index or `undefined` if the fixed priority queue is empty or the index is out of bounds.
112 public get (index
: number): T
| undefined {
113 if (this.empty() || index
>= this.size
) {
117 if (index
>= this.capacity
) {
118 index
-= this.capacity
120 return this.nodeArray
[index
].data
124 * Dequeue data from the fixed priority queue.
126 * @returns The dequeued data or `undefined` if the priority queue is empty.
128 public dequeue (): T
| undefined {
132 const index
= this.start
135 if (this.start
=== this.capacity
) {
138 return this.nodeArray
[index
].data
142 * Clears the fixed priority queue.
144 public clear (): void {
150 * Returns an iterator for the fixed priority queue.
152 * @returns An iterator for the fixed priority queue.
153 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
155 public [Symbol
.iterator
] (): Iterator
<T
> {
156 let index
= this.start
160 if (i
>= this.size
) {
166 const value
= this.nodeArray
[index
].data
169 if (index
=== this.capacity
) {
181 * Checks the queue size.
183 * @param size - Queue size.
185 private checkSize (size
: number): void {
186 if (!Number.isSafeInteger(size
)) {
188 `Invalid fixed priority queue size: '${size}' is not an integer`
192 throw new RangeError(`Invalid fixed priority queue size: ${size} < 0`)