perf: optimize tasks queuing implementation
[poolifier.git] / src / priority-queue.ts
CommitLineData
95d1a734
JB
1// Copyright Jerome Benoit. 2024. All Rights Reserved.
2
9df282a0 3import { FixedPriorityQueue } from './fixed-priority-queue.js'
097dea68
JB
4import { FixedQueue } from './fixed-queue.js'
5import { defaultBucketSize, type FixedQueueNode, type IFixedQueue, type PriorityQueueNode } from './utility-types.js'
bcfb06ce
JB
6
7/**
95d1a734 8 * Priority queue.
bcfb06ce
JB
9 * @typeParam T - Type of priority queue data.
10 * @internal
11 */
12export class PriorityQueue<T> {
9df282a0
JB
13 private head!: PriorityQueueNode<T>
14 private tail!: PriorityQueueNode<T>
2107bc57 15 private readonly bucketSize: number
097dea68 16 private priorityEnabled: boolean
13ed544a 17 /** The priority queue maximum size. */
bcfb06ce
JB
18 public maxSize!: number
19
bd8b441c 20 /**
95d1a734 21 * Constructs a priority queue.
9df282a0 22 * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize
fcfc3353 23 * @param enablePriority - Whether to enable priority. @defaultValue false
9df282a0 24 * @returns PriorityQueue.
bd8b441c 25 */
fcfc3353
JB
26 public constructor (
27 bucketSize: number = defaultBucketSize,
28 enablePriority = false
29 ) {
e75373e6 30 if (!Number.isSafeInteger(bucketSize)) {
579aa5bd 31 throw new TypeError(
6e5d7052 32 `Invalid bucket size: '${bucketSize.toString()}' is not an integer`
579aa5bd 33 )
e75373e6 34 }
579aa5bd 35 if (bucketSize < 0) {
6e5d7052 36 throw new RangeError(`Invalid bucket size: ${bucketSize.toString()} < 0`)
e75373e6 37 }
2107bc57 38 this.bucketSize = bucketSize
097dea68
JB
39 this.priorityEnabled = enablePriority
40 this.clear()
bcfb06ce
JB
41 }
42
e75373e6 43 /**
13ed544a 44 * The priority queue size.
ed20267e 45 * @returns The priority queue size.
e75373e6 46 */
9df282a0
JB
47 public get size (): number {
48 let node: PriorityQueueNode<T> | undefined = this.tail
49 let size = 0
50 while (node != null) {
51 size += node.size
52 node = node.next
53 }
54 return size
55 }
56
fcfc3353 57 public get enablePriority (): boolean {
097dea68 58 return this.priorityEnabled
fcfc3353
JB
59 }
60
61 public set enablePriority (enablePriority: boolean) {
097dea68 62 if (this.priorityEnabled === enablePriority) {
fcfc3353
JB
63 return
64 }
097dea68
JB
65 this.priorityEnabled = enablePriority
66 let head: PriorityQueueNode<T>
67 let tail: PriorityQueueNode<T>
68 let prevNode : PriorityQueueNode<T> | undefined
fcfc3353 69 let node: PriorityQueueNode<T> | undefined = this.tail
097dea68 70 let buckets = 0
fcfc3353 71 while (node != null) {
097dea68
JB
72 const currentNode = this.getPriorityQueueNode(node.nodeArray)
73 if (buckets === 0) {
74 tail = currentNode
75 }
76 if (prevNode != null) {
77 prevNode.next = currentNode
78 }
79 prevNode = currentNode
80 if (node.next == null) {
81 head = currentNode
82 }
83 ++buckets
fcfc3353
JB
84 node = node.next
85 }
097dea68
JB
86 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
87 this.head = head!
88 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
89 this.tail = tail!
fcfc3353
JB
90 }
91
e75373e6
JB
92 /**
93 * The number of filled prioritized buckets.
ed20267e 94 * @returns The number of filled prioritized buckets.
e75373e6
JB
95 */
96 public get buckets (): number {
97 return Math.trunc(this.size / this.bucketSize)
98 }
99
bcfb06ce
JB
100 /**
101 * Enqueue data into the priority queue.
bcfb06ce
JB
102 * @param data - Data to enqueue.
103 * @param priority - Priority of the data. Lower values have higher priority.
104 * @returns The new size of the priority queue.
105 */
106 public enqueue (data: T, priority?: number): number {
9df282a0 107 if (this.head.full()) {
097dea68 108 this.head = this.head.next = this.getPriorityQueueNode()
bcfb06ce 109 }
9df282a0
JB
110 this.head.enqueue(data, priority)
111 const size = this.size
112 if (size > this.maxSize) {
113 this.maxSize = size
bcfb06ce 114 }
9df282a0 115 return size
bcfb06ce
JB
116 }
117
118 /**
119 * Dequeue data from the priority queue.
9df282a0 120 * @param bucket - The prioritized bucket to dequeue from.
bcfb06ce
JB
121 * @returns The dequeued data or `undefined` if the priority queue is empty.
122 */
9df282a0
JB
123 public dequeue (bucket?: number): T | undefined {
124 let tail: PriorityQueueNode<T> | undefined = this.tail
1d98bad2
JB
125 let tailChanged = false
126 if (bucket != null && bucket > 0) {
127 let currentBucket = 1
9df282a0 128 while (tail != null) {
9df282a0
JB
129 if (currentBucket === bucket) {
130 break
95d1a734 131 }
1d98bad2 132 ++currentBucket
9df282a0 133 tail = tail.next
95d1a734 134 }
017f9985 135 tailChanged = tail !== this.tail
95d1a734 136 }
9df282a0
JB
137 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
138 const data = tail!.dequeue()
139 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
017f9985
JB
140 if (tail!.empty()) {
141 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
142 if (!tailChanged && tail!.next != null) {
1d98bad2
JB
143 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
144 this.tail = tail!.next
017f9985
JB
145 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
146 delete tail!.next
147 } else if (tailChanged) {
9df282a0
JB
148 let node: PriorityQueueNode<T> | undefined = this.tail
149 while (node != null) {
017f9985
JB
150 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
151 if (node.next === tail && tail!.next != null) {
9df282a0
JB
152 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
153 node.next = tail!.next
017f9985
JB
154 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
155 delete tail!.next
156 break
157 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
158 } else if (node.next === tail && tail!.next == null) {
159 delete node.next
160 this.head = node
9df282a0
JB
161 break
162 }
163 node = node.next
164 }
165 }
9df282a0
JB
166 }
167 return data
bcfb06ce
JB
168 }
169
170 /**
171 * Clears the priority queue.
172 */
173 public clear (): void {
097dea68 174 this.head = this.tail = this.getPriorityQueueNode()
bcfb06ce
JB
175 this.maxSize = 0
176 }
177
178 /**
95d1a734 179 * Returns an iterator for the priority queue.
2be9b405 180 * @returns An iterator for the priority queue.
95d1a734
JB
181 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
182 */
9df282a0 183 public [Symbol.iterator] (): Iterator<T> {
1d98bad2 184 let index = 0
9df282a0 185 let node = this.tail
95d1a734
JB
186 return {
187 next: () => {
1d98bad2
JB
188 const value = node.get(index) as T
189 if (value == null) {
95d1a734
JB
190 return {
191 value: undefined,
3a502712 192 done: true,
95d1a734
JB
193 }
194 }
1d98bad2
JB
195 ++index
196 if (index === node.capacity && node.next != null) {
9df282a0 197 node = node.next
1d98bad2 198 index = 0
9df282a0 199 }
95d1a734
JB
200 return {
201 value,
3a502712 202 done: false,
95d1a734 203 }
3a502712 204 },
95d1a734
JB
205 }
206 }
097dea68
JB
207
208 private getPriorityQueueNode (nodeArray?: FixedQueueNode<T>[]): PriorityQueueNode<T> {
209 let fixedQueue: IFixedQueue<T>
210 if (this.priorityEnabled) {
211 fixedQueue = new FixedPriorityQueue(this.bucketSize)
212 } else {
213 fixedQueue = new FixedQueue(this.bucketSize)
214 }
215 if (nodeArray != null) {
216 fixedQueue.nodeArray = nodeArray
217 }
218 return fixedQueue
219 }
bcfb06ce 220}