X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=src%2Fpriority-queue.ts;h=c613cd2e9ee393589a80950bda985bb7004f35ff;hb=3a5027122ca6401ae1d755843b20f714c61e3240;hp=1c0d8c929967b2fa52f728f7b395ed013f044fda;hpb=38e6b85b3247f847b61f30efc37851489f106e8a;p=poolifier.git

diff --git a/src/priority-queue.ts b/src/priority-queue.ts
index 1c0d8c92..c613cd2e 100644
--- a/src/priority-queue.ts
+++ b/src/priority-queue.ts
@@ -1,163 +1,196 @@
 // Copyright Jerome Benoit. 2024. All Rights Reserved.
 
+import { FixedPriorityQueue } from './fixed-priority-queue.js'
+
+/**
+ * Default bucket size.
+ */
+export const defaultBucketSize = 2048
+
 /**
  * Priority queue node.
- *
  * @typeParam T - Type of priority queue node data.
  * @internal
  */
-export interface PriorityQueueNode<T> {
-  data: T
-  priority: number
+export interface PriorityQueueNode<T> extends FixedPriorityQueue<T> {
+  next?: FixedPriorityQueue<T>
 }
 
 /**
  * Priority queue.
- *
  * @typeParam T - Type of priority queue data.
  * @internal
  */
 export class PriorityQueue<T> {
-  private nodeArray!: Array<PriorityQueueNode<T>>
-  /** Prioritized bucket size. */
-  private readonly k: number
-  /** The size of the priority queue. */
-  public size!: number
-  /** The maximum size of the priority queue. */
+  private head!: PriorityQueueNode<T>
+  private tail!: PriorityQueueNode<T>
+  private readonly bucketSize: number
+  /** The priority queue maximum size. */
   public maxSize!: number
 
   /**
-   * The number of filled prioritized buckets.
+   * Constructs a priority queue.
+   * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize
+   * @param enablePriority - Whether to enable priority. @defaultValue false
+   * @returns PriorityQueue.
    */
-  public get buckets (): number {
-    return this.k === Infinity ? 1 : Math.trunc(this.nodeArray.length / this.k)
+  public constructor (
+    bucketSize: number = defaultBucketSize,
+    enablePriority = false
+  ) {
+    if (!Number.isSafeInteger(bucketSize)) {
+      throw new TypeError(
+        `Invalid bucket size: '${bucketSize}' is not an integer`
+      )
+    }
+    if (bucketSize < 0) {
+      throw new RangeError(`Invalid bucket size: ${bucketSize} < 0`)
+    }
+    this.bucketSize = bucketSize
+    this.head = this.tail = new FixedPriorityQueue(
+      this.bucketSize,
+      enablePriority
+    )
+    this.maxSize = 0
   }
 
   /**
-   * Constructs a priority queue.
-   *
-   * @param k - Prioritized bucket size. @defaultValue Infinity
+   * The priority queue size.
    */
-  public constructor (k = Infinity) {
-    if (k !== Infinity && !Number.isSafeInteger(k)) {
-      throw new TypeError('k must be an integer')
+  public get size (): number {
+    let node: PriorityQueueNode<T> | undefined = this.tail
+    let size = 0
+    while (node != null) {
+      size += node.size
+      node = node.next
     }
-    if (k < 1) {
-      throw new RangeError('k must be greater than or equal to 1')
+    return size
+  }
+
+  public get enablePriority (): boolean {
+    return this.head.enablePriority
+  }
+
+  public set enablePriority (enablePriority: boolean) {
+    if (this.head.enablePriority === enablePriority) {
+      return
+    }
+    let node: PriorityQueueNode<T> | undefined = this.tail
+    while (node != null) {
+      node.enablePriority = enablePriority
+      node = node.next
     }
-    this.k = k
-    this.clear()
+  }
+
+  /**
+   * The number of filled prioritized buckets.
+   */
+  public get buckets (): number {
+    return Math.trunc(this.size / this.bucketSize)
   }
 
   /**
    * Enqueue data into the priority queue.
-   *
    * @param data - Data to enqueue.
    * @param priority - Priority of the data. Lower values have higher priority.
    * @returns The new size of the priority queue.
    */
   public enqueue (data: T, priority?: number): number {
-    priority = priority ?? 0
-    const startIndex = this.k === Infinity ? 0 : this.buckets * this.k
-    let inserted = false
-    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
-      }
+    if (this.head.full()) {
+      this.head = this.head.next = new FixedPriorityQueue(
+        this.bucketSize,
+        this.enablePriority
+      )
     }
-    if (!inserted) {
-      this.nodeArray.push({ data, priority })
+    this.head.enqueue(data, priority)
+    const size = this.size
+    if (size > this.maxSize) {
+      this.maxSize = size
     }
-    return this.incrementSize()
+    return size
   }
 
   /**
    * Dequeue data from the priority queue.
-   *
-   * @param bucket - The prioritized bucket to dequeue from. @defaultValue 0
+   * @param bucket - The prioritized bucket to dequeue from.
    * @returns The dequeued data or `undefined` if the priority queue is empty.
    */
-  public dequeue (bucket = 0): T | undefined {
-    if (this.k !== Infinity && bucket > 0) {
-      while (bucket > 0) {
-        const index = bucket * this.k
-        // eslint-disable-next-line @typescript-eslint/no-unnecessary-condition
-        if (this.nodeArray[index] != null) {
-          --this.size
-          return this.nodeArray.splice(index, 1)[0].data
+  public dequeue (bucket?: number): T | undefined {
+    let tail: PriorityQueueNode<T> | undefined = this.tail
+    let tailChanged = false
+    if (bucket != null && bucket > 0) {
+      let currentBucket = 1
+      while (tail != null) {
+        if (currentBucket === bucket) {
+          break
         }
-        --bucket
+        ++currentBucket
+        tail = tail.next
+        tailChanged = true
       }
     }
-    if (this.size > 0) {
-      --this.size
+    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
+    const data = tail!.dequeue()
+    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
+    if (tail!.empty() && tail!.next != null) {
+      if (!tailChanged) {
+        // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
+        this.tail = tail!.next
+      } else {
+        let node: PriorityQueueNode<T> | undefined = this.tail
+        while (node != null) {
+          if (node.next === tail) {
+            // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
+            node.next = tail!.next
+            break
+          }
+          node = node.next
+        }
+      }
+      // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
+      delete tail!.next
     }
-    return this.nodeArray.shift()?.data
-  }
-
-  /**
-   * Peeks at the first data.
-   * @returns The first data or `undefined` if the priority queue is empty.
-   */
-  public peekFirst (): T | undefined {
-    return this.nodeArray[0]?.data
-  }
-
-  /**
-   * Peeks at the last data.
-   * @returns The last data or `undefined` if the priority queue is empty.
-   */
-  public peekLast (): T | undefined {
-    return this.nodeArray[this.nodeArray.length - 1]?.data
+    return data
   }
 
   /**
    * Clears the priority queue.
    */
   public clear (): void {
-    this.nodeArray = []
-    this.size = 0
+    this.head = this.tail = new FixedPriorityQueue(
+      this.bucketSize,
+      this.enablePriority
+    )
     this.maxSize = 0
   }
 
   /**
    * 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
+  public [Symbol.iterator] (): Iterator<T> {
+    let index = 0
+    let node = this.tail
     return {
       next: () => {
-        if (i >= this.nodeArray.length) {
+        const value = node.get(index) as T
+        if (value == null) {
           return {
             value: undefined,
-            done: true
+            done: true,
           }
         }
-        const value = this.nodeArray[i].data
-        i++
+        ++index
+        if (index === node.capacity && node.next != null) {
+          node = node.next
+          index = 0
+        }
         return {
           value,
-          done: false
+          done: false,
         }
-      }
-    }
-  }
-
-  /**
-   * Increments the size of the priority queue.
-   *
-   * @returns The new size of the priority queue.
-   */
-  private incrementSize (): number {
-    ++this.size
-    if (this.size > this.maxSize) {
-      this.maxSize = this.size
+      },
     }
-    return this.size
   }
 }