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