export class PriorityQueue<T> {
private nodeArray!: Array<PriorityQueueNode<T>>
/** Prioritized bucket size. */
- private readonly k: number
+ private readonly bucketSize: number
/** The size of the priority queue. */
public size!: number
/** The maximum size of the priority queue. */
public maxSize!: number
+ /**
+ * The number of filled prioritized buckets.
+ */
+ public get buckets (): number {
+ return this.bucketSize === Number.POSITIVE_INFINITY
+ ? 1
+ : Math.trunc(this.nodeArray.length / this.bucketSize)
+ }
+
/**
* Constructs a priority queue.
*
- * @param k - Prioritized bucket size. @defaultValue Infinity
+ * @param bucketSize - Prioritized bucket size. @defaultValue Number.POSITIVE_INFINITY
*/
- public constructor (k = Infinity) {
- if (k !== Infinity && !Number.isSafeInteger(k)) {
- throw new TypeError('k must be an integer')
+ public constructor (bucketSize = Number.POSITIVE_INFINITY) {
+ if (
+ bucketSize !== Number.POSITIVE_INFINITY &&
+ !Number.isSafeInteger(bucketSize)
+ ) {
+ throw new TypeError('bucketSize must be an integer')
}
- if (k < 1) {
- throw new RangeError('k must be greater than or equal to 1')
+ if (bucketSize < 1) {
+ throw new RangeError('bucketSize must be greater than or equal to 1')
}
- this.k = k
+ this.bucketSize = bucketSize
this.clear()
}
public enqueue (data: T, priority?: number): number {
priority = priority ?? 0
const startIndex =
- this.k === Infinity || this.nodeArray.length / this.k < 1
+ this.bucketSize === Number.POSITIVE_INFINITY
? 0
- : Math.trunc(this.nodeArray.length / this.k) * this.k
+ : this.buckets * this.bucketSize
let inserted = false
for (let index = startIndex; index < this.nodeArray.length; index++) {
if (this.nodeArray[index].priority > priority) {
* @returns The dequeued data or `undefined` if the priority queue is empty.
*/
public dequeue (bucket = 0): T | undefined {
- if (this.k !== Infinity && bucket > 0) {
+ if (this.bucketSize !== Number.POSITIVE_INFINITY && bucket > 0) {
while (bucket > 0) {
- const index = bucket * this.k
+ const index = bucket * this.bucketSize
// eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
if (this.nodeArray[index] != null) {
--this.size
--bucket
}
}
- if (this.size > 0) {
- --this.size
- }
+ this.decrementSize()
return this.nodeArray.shift()?.data
}
}
return this.size
}
+
+ /**
+ * Decrements the size of the priority queue.
+ *
+ * @returns The new size of the priority queue.
+ */
+ private decrementSize (): number {
+ if (this.size > 0) {
+ --this.size
+ }
+ return this.size
+ }
}