src/priority-queue.ts

   1 // Copyright Jerome Benoit. 2024. All Rights Reserved.
   2
   3 import { FixedPriorityQueue } from './fixed-priority-queue.js'
   4
   5 /**
   6  * Default bucket size.
   7  */
   8 export const defaultBucketSize = 2048
   9
  10 /**
  11  * Priority queue node.
  12  *
  13  * @typeParam T - Type of priority queue node data.
  14  * @internal
  15  */
  16 export interface PriorityQueueNode<T> extends FixedPriorityQueue<T> {
  17   next?: FixedPriorityQueue<T>
  18 }
  19
  20 /**
  21  * Priority queue.
  22  *
  23  * @typeParam T - Type of priority queue data.
  24  * @internal
  25  */
  26 export class PriorityQueue<T> {
  27   private head!: PriorityQueueNode<T>
  28   private tail!: PriorityQueueNode<T>
  29   private readonly bucketSize: number
  30   public maxSize!: number
  31
  32   /**
  33    * Constructs a priority queue.
  34    *
  35    * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize
  36    * @returns PriorityQueue.
  37    */
  38   public constructor (bucketSize: number = defaultBucketSize) {
  39     if (!Number.isSafeInteger(bucketSize)) {
  40       throw new TypeError('bucketSize must be an integer')
  41     }
  42     if (bucketSize < 1) {
  43       throw new RangeError('bucketSize must be greater than or equal to 1')
  44     }
  45     this.bucketSize = bucketSize
  46     this.clear()
  47   }
  48
  49   /**
  50    * The size of the priority queue.
  51    */
  52   public get size (): number {
  53     let node: PriorityQueueNode<T> | undefined = this.tail
  54     let size = 0
  55     while (node != null) {
  56       size += node.size
  57       node = node.next
  58     }
  59     return size
  60   }
  61
  62   /**
  63    * The number of filled prioritized buckets.
  64    */
  65   public get buckets (): number {
  66     return Math.trunc(this.size / this.bucketSize)
  67   }
  68
  69   /**
  70    * Enqueue data into the priority queue.
  71    *
  72    * @param data - Data to enqueue.
  73    * @param priority - Priority of the data. Lower values have higher priority.
  74    * @returns The new size of the priority queue.
  75    */
  76   public enqueue (data: T, priority?: number): number {
  77     if (this.head.full()) {
  78       this.head = this.head.next = new FixedPriorityQueue(this.bucketSize)
  79     }
  80     this.head.enqueue(data, priority)
  81     const size = this.size
  82     if (size > this.maxSize) {
  83       this.maxSize = size
  84     }
  85     return size
  86   }
  87
  88   /**
  89    * Dequeue data from the priority queue.
  90    *
  91    * @param bucket - The prioritized bucket to dequeue from.
  92    * @returns The dequeued data or `undefined` if the priority queue is empty.
  93    */
  94   public dequeue (bucket?: number): T | undefined {
  95     let tail: PriorityQueueNode<T> | undefined = this.tail
  96     if (bucket != null) {
  97       let currentBucket = 0
  98       while (tail != null) {
  99         ++currentBucket
 100         if (currentBucket === bucket) {
 101           break
 102         }
 103         tail = tail.next
 104       }
 105     }
 106     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 107     const data = tail!.dequeue()
 108     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 109     if (tail!.empty() && tail!.next != null) {
 110       if (tail === this.tail) {
 111         this.tail = tail.next
 112       } else {
 113         let node: PriorityQueueNode<T> | undefined = this.tail
 114         while (node != null) {
 115           if (node.next === tail) {
 116             // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 117             node.next = tail!.next
 118             break
 119           }
 120           node = node.next
 121         }
 122       }
 123       // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 124       delete tail!.next
 125     }
 126     return data
 127   }
 128
 129   /**
 130    * Clears the priority queue.
 131    */
 132   public clear (): void {
 133     this.head = this.tail = new FixedPriorityQueue(this.bucketSize)
 134     this.maxSize = 0
 135   }
 136
 137   /**
 138    * Returns an iterator for the priority queue.
 139    *
 140    * @returns An iterator for the priority queue.
 141    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 142    */
 143   public [Symbol.iterator] (): Iterator<T> {
 144     let i = 0
 145     let node = this.tail
 146     return {
 147       next: () => {
 148         if (node.empty() || (i >= node.capacity && node.next == null)) {
 149           return {
 150             value: undefined,
 151             done: true
 152           }
 153         }
 154         const value = node.dequeue() as T
 155         ++i
 156         if (i === node.capacity && node.next != null) {
 157           node = node.next
 158           i = 0
 159         }
 160         return {
 161           value,
 162           done: false
 163         }
 164       }
 165     }
 166   }
 167 }