src/priority-queue.ts

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