4 export const defaultQueueSize
= 2048
9 * @typeParam T - Type of priority queue node data.
12 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
>>
26 public readonly capacity
: number
28 public maxSize
!: number
31 * Constructs a fixed priority queue.
33 * @param size - Fixed priority queue size. @defaultValue defaultQueueSize
34 * @returns FixedPriorityQueue.
36 constructor (size
: number = defaultQueueSize
) {
39 this.nodeArray
= new Array<PriorityQueueNode
<T
>>(this.capacity
)
43 public empty (): boolean {
44 return this.size
=== 0
47 public full (): boolean {
48 return this.size
=== this.capacity
51 public enqueue (data
: T
, priority
?: number): number {
53 throw new Error('Priority queue is full')
55 priority
= priority
?? 0
56 let index
= this.start
58 for (let i
= 0; i
< this.size
; i
++) {
59 if (this.nodeArray
[index
]?.priority
> priority
) {
60 this.nodeArray
.splice(index
, 0, { data
, priority
})
65 if (index
=== this.capacity
) {
69 this.nodeArray
.length
!== this.capacity
&&
70 (this.nodeArray
.length
= this.capacity
)
72 let index
= this.start
+ this.size
73 if (index
>= this.capacity
) {
74 index
-= this.capacity
76 this.nodeArray
[index
] = { data
, priority
}
78 return this.incrementSize()
81 public dequeue (): T
| undefined {
85 const index
= this.start
88 if (this.start
=== this.capacity
) {
91 return this.nodeArray
[index
].data
95 * Clears the fixed priority queue.
97 public clear (): void {
104 * Returns an iterator for the fixed priority queue.
106 * @returns An iterator for the fixed priority queue.
107 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
109 public [Symbol
.iterator
] (): Iterator
<T
> {
110 let index
= this.start
114 if (i
>= this.size
) {
120 const value
= this.nodeArray
[index
].data
123 if (index
=== this.capacity
) {
135 * Increments the size of the fixed priority queue.
137 * @returns The new size of the fixed priority queue.
139 private incrementSize (): number {
141 if (this.size
> this.maxSize
) {
142 this.maxSize
= this.size
147 private checkSize (size
: number): void {
148 if (!Number.isSafeInteger(size
)) {
150 `Invalid fixed priority queue size: '${size}' is not an integer`
154 throw new RangeError(`Invalid fixed priority queue size: ${size} < 0`)