4 export const defaultQueueSize
= 2048
9 * @typeParam T - Type of priority queue node data.
12 export interface PriorityQueueNode
<T
> {
17 export class FixedPriorityQueue
<T
> {
18 private start
!: number
19 private readonly nodeArray
: Array<PriorityQueueNode
<T
>>
21 public maxSize
!: number
23 constructor (size
: number = defaultQueueSize
) {
25 this.nodeArray
= new Array<PriorityQueueNode
<T
>>(size
)
29 public empty (): boolean {
30 return this.size
=== 0
33 public full (): boolean {
34 return this.size
=== this.nodeArray
.length
37 public enqueue (data
: T
, priority
?: number): number {
39 throw new Error('Priority queue is full')
41 priority
= priority
?? 0
43 for (let index
= this.start
; index
< this.nodeArray
.length
; index
++) {
44 if (this.nodeArray
[index
]?.priority
> priority
) {
45 this.nodeArray
.splice(index
, 0, { data
, priority
})
51 let index
= this.start
+ this.size
52 if (index
>= this.nodeArray
.length
) {
53 index
-= this.nodeArray
.length
55 this.nodeArray
[index
] = { data
, priority
}
57 return this.incrementSize()
60 public dequeue (): T
| undefined {
64 const index
= this.start
67 if (this.start
=== this.nodeArray
.length
) {
70 return this.nodeArray
[index
].data
74 * Clears the fixed priority queue.
76 public clear (): void {
83 * Returns an iterator for the fixed priority queue.
85 * @returns An iterator for the fixed priority queue.
86 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
88 [Symbol
.iterator
] (): Iterator
<T
> {
98 const value
= this.nodeArray
[i
].data
109 * Increments the size of the fixed priority queue.
111 * @returns The new size of the fixed priority queue.
113 private incrementSize (): number {
115 if (this.size
> this.maxSize
) {
116 this.maxSize
= this.size
121 private checkSize (size
: number): void {
122 if (!Number.isSafeInteger(size
)) {
124 `Invalid fixed priority queue size: ${size} is not an integer`
128 throw new RangeError(`Invalid fixed priority queue size: ${size} < 0`)