ed4d63f5fa9cb03b71f1e91b472f84d1978d2573
1 // Copyright Jerome Benoit. 2024. All Rights Reserved.
3 import { FixedPriorityQueue
} from
'./fixed-priority-queue.js'
8 export const defaultBucketSize
= 2048
11 * Priority queue node.
13 * @typeParam T - Type of priority queue node data.
16 export interface PriorityQueueNode
<T
> extends FixedPriorityQueue
<T
> {
17 next
?: FixedPriorityQueue
<T
>
23 * @typeParam T - Type of priority queue data.
26 export class PriorityQueue
<T
> {
27 private head
!: PriorityQueueNode
<T
>
28 private tail
!: PriorityQueueNode
<T
>
29 private readonly bucketSize
: number
30 public maxSize
!: number
33 * Constructs a priority queue.
35 * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize
36 * @returns PriorityQueue.
38 public constructor (bucketSize
: number = defaultBucketSize
) {
39 if (!Number.isSafeInteger(bucketSize
)) {
40 throw new TypeError('bucketSize must be an integer')
43 throw new RangeError('bucketSize must be greater than or equal to 1')
45 this.bucketSize
= bucketSize
50 * The size of the priority queue.
52 public get
size (): number {
53 let node
: PriorityQueueNode
<T
> | undefined = this.tail
55 while (node
!= null) {
63 * The number of filled prioritized buckets.
65 public get
buckets (): number {
66 return Math.trunc(this.size
/ this.bucketSize
)
70 * Enqueue data into the priority queue.
72 * @param data - Data to enqueue.
73 * @param priority - Priority of the data. Lower values have higher priority.
74 * @returns The new size of the priority queue.
76 public enqueue (data
: T
, priority
?: number): number {
77 if (this.head
.full()) {
78 this.head
= this.head
.next
= new FixedPriorityQueue(this.bucketSize
)
80 this.head
.enqueue(data
, priority
)
81 const size
= this.size
82 if (size
> this.maxSize
) {
89 * Dequeue data from the priority queue.
91 * @param bucket - The prioritized bucket to dequeue from.
92 * @returns The dequeued data or `undefined` if the priority queue is empty.
94 public dequeue (bucket
?: number): T
| undefined {
95 let tail
: PriorityQueueNode
<T
> | undefined = this.tail
98 while (tail
!= null) {
100 if (currentBucket
=== bucket
) {
106 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
107 const data
= tail
!.dequeue()
108 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
109 if (tail
!.empty() && tail
!.next
!= null) {
110 if (tail
=== this.tail
) {
111 this.tail
= tail
.next
113 let node
: PriorityQueueNode
<T
> | undefined = this.tail
114 while (node
!= null) {
115 if (node
.next
=== tail
) {
116 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
117 node
.next
= tail
!.next
123 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
130 * Clears the priority queue.
132 public clear (): void {
133 this.head
= this.tail
= new FixedPriorityQueue(this.bucketSize
)
138 * Returns an iterator for the priority queue.
140 * @returns An iterator for the priority queue.
141 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
143 public [Symbol
.iterator
] (): Iterator
<T
> {
148 if (node
.empty() || (i
>= node
.capacity
&& node
.next
== null)) {
154 const value
= node
.dequeue() as T
156 if (i
=== node
.capacity
&& node
.next
!= null) {