fadaee750515b3de72bcc6c5a9f6cd70de0b68cd
4 export const defaultQueueSize
= 2048
9 * @typeParam T - Type of priority queue node data.
12 export interface PriorityQueueNode
<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<PriorityQueueNode
<T
>>
27 public maxSize
!: number
29 constructor (size
: number = defaultQueueSize
) {
31 this.nodeArray
= new Array<PriorityQueueNode
<T
>>(size
)
35 public empty (): boolean {
36 return this.size
=== 0
39 public full (): boolean {
40 return this.size
=== this.nodeArray
.length
43 public enqueue (data
: T
, priority
?: number): number {
45 throw new Error('Priority queue is full')
47 priority
= priority
?? 0
48 const nodeArrayLength
= this.nodeArray
.length
50 for (let index
= this.start
; index
< nodeArrayLength
; index
++) {
51 if (this.nodeArray
[index
]?.priority
> priority
) {
52 this.nodeArray
.splice(index
, 0, { data
, priority
})
57 this.nodeArray
.length
!== nodeArrayLength
&&
58 (this.nodeArray
.length
= nodeArrayLength
)
60 let index
= this.start
+ this.size
61 if (index
>= nodeArrayLength
) {
62 index
-= nodeArrayLength
64 this.nodeArray
[index
] = { data
, priority
}
66 return this.incrementSize()
69 public dequeue (): T
| undefined {
73 const index
= this.start
76 if (this.start
=== this.nodeArray
.length
) {
79 return this.nodeArray
[index
].data
83 * Clears the fixed priority queue.
85 public clear (): void {
92 * Returns an iterator for the fixed priority queue.
94 * @returns An iterator for the fixed priority queue.
95 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
97 [Symbol
.iterator
] (): Iterator
<T
> {
101 if (i
>= this.size
) {
107 const value
= this.nodeArray
[i
].data
118 * Increments the size of the fixed priority queue.
120 * @returns The new size of the fixed priority queue.
122 private incrementSize (): number {
124 if (this.size
> this.maxSize
) {
125 this.maxSize
= this.size
130 private checkSize (size
: number): void {
131 if (!Number.isSafeInteger(size
)) {
133 `Invalid fixed priority queue size: '${size}' is not an integer`
137 throw new RangeError(`Invalid fixed priority queue size: ${size} < 0`)