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