X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=src%2Fpriority-queue.ts;h=93e7b76dbfa8051fd3783f2063460f6c86252753;hb=6e5d7052fe741b50e68f8614b33d3754be41415f;hp=d1d9307804822bd7a243fe51004ee1bb9b08a280;hpb=9df282a07ef35012409d7d08207e6df983a7e905;p=poolifier.git

diff --git a/src/priority-queue.ts b/src/priority-queue.ts
index d1d93078..93e7b76d 100644
--- a/src/priority-queue.ts
+++ b/src/priority-queue.ts
@@ -9,7 +9,6 @@ export const defaultBucketSize = 2048
 
 /**
  * Priority queue node.
- *
  * @typeParam T - Type of priority queue node data.
  * @internal
  */
@@ -19,7 +18,6 @@ export interface PriorityQueueNode<T> extends FixedPriorityQueue<T> {
 
 /**
  * Priority queue.
- *
  * @typeParam T - Type of priority queue data.
  * @internal
  */
@@ -27,20 +25,38 @@ export class PriorityQueue<T> {
   private head!: PriorityQueueNode<T>
   private tail!: PriorityQueueNode<T>
   private readonly bucketSize: number
+  /** The priority queue maximum size. */
   public maxSize!: number
 
   /**
    * Constructs a priority queue.
-   *
    * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize
+   * @param enablePriority - Whether to enable priority. @defaultValue false
    * @returns PriorityQueue.
    */
-  public constructor (bucketSize: number = defaultBucketSize) {
+  public constructor (
+    bucketSize: number = defaultBucketSize,
+    enablePriority = false
+  ) {
+    if (!Number.isSafeInteger(bucketSize)) {
+      throw new TypeError(
+        `Invalid bucket size: '${bucketSize.toString()}' is not an integer`
+      )
+    }
+    if (bucketSize < 0) {
+      throw new RangeError(`Invalid bucket size: ${bucketSize.toString()} < 0`)
+    }
     this.bucketSize = bucketSize
-    this.clear()
+    this.head = this.tail = new FixedPriorityQueue(
+      this.bucketSize,
+      enablePriority
+    )
+    this.maxSize = 0
   }
 
-  /** The size of the priority queue. */
+  /**
+   * The priority queue size.
+   */
   public get size (): number {
     let node: PriorityQueueNode<T> | undefined = this.tail
     let size = 0
@@ -51,16 +67,40 @@ export class PriorityQueue<T> {
     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
+    }
+  }
+
+  /**
+   * 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 {
     if (this.head.full()) {
-      this.head = this.head.next = new FixedPriorityQueue(this.bucketSize)
+      this.head = this.head.next = new FixedPriorityQueue(
+        this.bucketSize,
+        this.enablePriority
+      )
     }
     this.head.enqueue(data, priority)
     const size = this.size
@@ -72,28 +112,30 @@ export class PriorityQueue<T> {
 
   /**
    * Dequeue data from the priority queue.
-   *
    * @param bucket - The prioritized bucket to dequeue from.
    * @returns The dequeued data or `undefined` if the priority queue is empty.
    */
   public dequeue (bucket?: number): T | undefined {
     let tail: PriorityQueueNode<T> | undefined = this.tail
-    if (bucket != null) {
-      let currentBucket = 0
+    let tailChanged = false
+    if (bucket != null && bucket > 0) {
+      let currentBucket = 1
       while (tail != null) {
-        ++currentBucket
         if (currentBucket === bucket) {
           break
         }
+        ++currentBucket
         tail = tail.next
+        tailChanged = true
       }
     }
     // 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 (tail === this.tail) {
-        this.tail = tail.next
+      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) {
@@ -115,38 +157,40 @@ export class PriorityQueue<T> {
    * Clears the priority queue.
    */
   public clear (): void {
-    this.head = this.tail = new FixedPriorityQueue(this.bucketSize)
+    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
    */
   public [Symbol.iterator] (): Iterator<T> {
-    let i = 0
+    let index = 0
     let node = this.tail
     return {
       next: () => {
-        if (node.empty() || (i >= node.capacity && node.next == null)) {
+        const value = node.get(index) as T
+        if (value == null) {
           return {
             value: undefined,
-            done: true
+            done: true,
           }
         }
-        const value = node.dequeue() as T
-        ++i
-        if (i === node.capacity && node.next != null) {
+        ++index
+        if (index === node.capacity && node.next != null) {
           node = node.next
-          i = 0
+          index = 0
         }
         return {
           value,
-          done: false
+          done: false,
         }
-      }
+      },
     }
   }
 }