---
[poolifier.git] / src / priority-queue.ts
... / ...
CommitLineData
1// Copyright Jerome Benoit. 2024. All Rights Reserved.
2
3/**
4 * Priority queue node.
5 *
6 * @typeParam T - Type of priority queue node data.
7 * @internal
8 */
9export interface PriorityQueueNode<T> {
10 data: T
11 priority: number
12}
13
14/**
15 * Priority queue.
16 *
17 * @typeParam T - Type of priority queue data.
18 * @internal
19 */
20export class PriorityQueue<T> {
21 private nodeArray!: Array<PriorityQueueNode<T>>
22 /** Prioritized bucket size. */
23 private readonly bucketSize: number
24 /** The size of the priority queue. */
25 public size!: number
26 /** The maximum size of the priority queue. */
27 public maxSize!: number
28
29 /**
30 * The number of filled prioritized buckets.
31 */
32 public get buckets (): number {
33 return this.bucketSize === Infinity
34 ? 1
35 : Math.trunc(this.nodeArray.length / this.bucketSize)
36 }
37
38 /**
39 * Constructs a priority queue.
40 *
41 * @param bucketSize - Prioritized bucket size. @defaultValue Infinity
42 */
43 public constructor (bucketSize = Infinity) {
44 if (bucketSize !== Infinity && !Number.isSafeInteger(bucketSize)) {
45 throw new TypeError('bucketSize must be an integer')
46 }
47 if (bucketSize < 1) {
48 throw new RangeError('bucketSize must be greater than or equal to 1')
49 }
50 this.bucketSize = bucketSize
51 this.clear()
52 }
53
54 /**
55 * Enqueue data into the priority queue.
56 *
57 * @param data - Data to enqueue.
58 * @param priority - Priority of the data. Lower values have higher priority.
59 * @returns The new size of the priority queue.
60 */
61 public enqueue (data: T, priority?: number): number {
62 priority = priority ?? 0
63 const startIndex =
64 this.bucketSize === Infinity ? 0 : this.buckets * this.bucketSize
65 let inserted = false
66 for (let index = startIndex; index < this.nodeArray.length; index++) {
67 if (this.nodeArray[index].priority > priority) {
68 this.nodeArray.splice(index, 0, { data, priority })
69 inserted = true
70 break
71 }
72 }
73 if (!inserted) {
74 this.nodeArray.push({ data, priority })
75 }
76 return this.incrementSize()
77 }
78
79 /**
80 * Dequeue data from the priority queue.
81 *
82 * @param bucket - The prioritized bucket to dequeue from. @defaultValue 0
83 * @returns The dequeued data or `undefined` if the priority queue is empty.
84 */
85 public dequeue (bucket = 0): T | undefined {
86 if (this.bucketSize !== Infinity && bucket > 0) {
87 while (bucket > 0) {
88 const index = bucket * this.bucketSize
89 // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
90 if (this.nodeArray[index] != null) {
91 --this.size
92 return this.nodeArray.splice(index, 1)[0].data
93 }
94 --bucket
95 }
96 }
97 this.decrementSize()
98 return this.nodeArray.shift()?.data
99 }
100
101 /**
102 * Peeks at the first data.
103 * @returns The first data or `undefined` if the priority queue is empty.
104 */
105 public peekFirst (): T | undefined {
106 return this.nodeArray[0]?.data
107 }
108
109 /**
110 * Peeks at the last data.
111 * @returns The last data or `undefined` if the priority queue is empty.
112 */
113 public peekLast (): T | undefined {
114 return this.nodeArray[this.nodeArray.length - 1]?.data
115 }
116
117 /**
118 * Clears the priority queue.
119 */
120 public clear (): void {
121 this.nodeArray = []
122 this.size = 0
123 this.maxSize = 0
124 }
125
126 /**
127 * Returns an iterator for the priority queue.
128 *
129 * @returns An iterator for the priority queue.
130 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
131 */
132 [Symbol.iterator] (): Iterator<T> {
133 let i = 0
134 return {
135 next: () => {
136 if (i >= this.nodeArray.length) {
137 return {
138 value: undefined,
139 done: true
140 }
141 }
142 const value = this.nodeArray[i].data
143 i++
144 return {
145 value,
146 done: false
147 }
148 }
149 }
150 }
151
152 /**
153 * Increments the size of the priority queue.
154 *
155 * @returns The new size of the priority queue.
156 */
157 private incrementSize (): number {
158 ++this.size
159 if (this.size > this.maxSize) {
160 this.maxSize = this.size
161 }
162 return this.size
163 }
164
165 /**
166 * Decrements the size of the priority queue.
167 *
168 * @returns The new size of the priority queue.
169 */
170 private decrementSize (): number {
171 if (this.size > 0) {
172 --this.size
173 }
174 return this.size
175 }
176}