X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=src%2Fpriority-queue.ts;h=b4d70b5ea8424c444570ac8acc4b03d2e33d4530;hb=f45a8925025d4b76849ea359542bb6bafd39695d;hp=55a97169f757beb0f53c51843d6a8a87f6392612;hpb=bcfb06ce041a682baf396a099c633a848d6a4045;p=poolifier.git

diff --git a/src/priority-queue.ts b/src/priority-queue.ts
index 55a97169..b4d70b5e 100644
--- a/src/priority-queue.ts
+++ b/src/priority-queue.ts
@@ -1,7 +1,12 @@
+// Copyright Jerome Benoit. 2024. All Rights Reserved.
+
 /**
+ * Priority queue node.
+ *
+ * @typeParam T - Type of priority queue node data.
  * @internal
  */
-interface PriorityQueueNode<T> {
+export interface PriorityQueueNode<T> {
   data: T
   priority: number
 }
@@ -14,12 +19,38 @@ interface PriorityQueueNode<T> {
  */
 export class PriorityQueue<T> {
   private nodeArray!: Array<PriorityQueueNode<T>>
+  /** Prioritized bucket size. */
+  private readonly bucketSize: number
   /** The size of the priority queue. */
   public size!: number
   /** The maximum size of the priority queue. */
   public maxSize!: number
 
-  public constructor () {
+  /**
+   * 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 bucketSize - Prioritized bucket size. @defaultValue Number.POSITIVE_INFINITY
+   */
+  public constructor (bucketSize = Number.POSITIVE_INFINITY) {
+    if (
+      bucketSize !== Number.POSITIVE_INFINITY &&
+      !Number.isSafeInteger(bucketSize)
+    ) {
+      throw new TypeError('bucketSize must be an integer')
+    }
+    if (bucketSize < 1) {
+      throw new RangeError('bucketSize must be greater than or equal to 1')
+    }
+    this.bucketSize = bucketSize
     this.clear()
   }
 
@@ -32,9 +63,13 @@ export class PriorityQueue<T> {
    */
   public enqueue (data: T, priority?: number): number {
     priority = priority ?? 0
+    const startIndex =
+      this.bucketSize === Number.POSITIVE_INFINITY
+        ? 0
+        : this.buckets * this.bucketSize
     let inserted = false
-    for (const [index, node] of this.nodeArray.entries()) {
-      if (node.priority > priority) {
+    for (let index = startIndex; index < this.nodeArray.length; index++) {
+      if (this.nodeArray[index].priority > priority) {
         this.nodeArray.splice(index, 0, { data, priority })
         inserted = true
         break
@@ -49,12 +84,22 @@ export class PriorityQueue<T> {
   /**
    * Dequeue data from the priority queue.
    *
+   * @param bucket - The prioritized bucket to dequeue from. @defaultValue 0
    * @returns The dequeued data or `undefined` if the priority queue is empty.
    */
-  public dequeue (): T | undefined {
-    if (this.size > 0) {
-      --this.size
+  public dequeue (bucket = 0): T | undefined {
+    if (this.bucketSize !== Number.POSITIVE_INFINITY && bucket > 0) {
+      while (bucket > 0) {
+        const index = bucket * this.bucketSize
+        // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
+        if (this.nodeArray[index] != null) {
+          --this.size
+          return this.nodeArray.splice(index, 1)[0].data
+        }
+        --bucket
+      }
     }
+    this.decrementSize()
     return this.nodeArray.shift()?.data
   }
 
@@ -84,9 +129,35 @@ export class PriorityQueue<T> {
   }
 
   /**
-   * Increments the size of the deque.
+   * Returns an iterator for the priority queue.
+   *
+   * @returns An iterator for the priority queue.
+   * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
+   */
+  [Symbol.iterator] (): Iterator<T> {
+    let i = 0
+    return {
+      next: () => {
+        if (i >= this.nodeArray.length) {
+          return {
+            value: undefined,
+            done: true
+          }
+        }
+        const value = this.nodeArray[i].data
+        i++
+        return {
+          value,
+          done: false
+        }
+      }
+    }
+  }
+
+  /**
+   * Increments the size of the priority queue.
    *
-   * @returns The new size of the deque.
+   * @returns The new size of the priority queue.
    */
   private incrementSize (): number {
     ++this.size
@@ -95,4 +166,16 @@ export class PriorityQueue<T> {
     }
     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
+  }
 }