src/priority-queue.ts

   1 /**
   2  * @internal
   3  */
   4 interface PriorityQueueNode<T> {
   5   data: T
   6   priority: number
   7 }
   8
   9 /**
  10  * k-priority queue.
  11  *
  12  * @typeParam T - Type of priority queue data.
  13  * @internal
  14  */
  15 export class PriorityQueue<T> {
  16   private nodeArray!: Array<PriorityQueueNode<T>>
  17   /** Prioritized bucket size. */
  18   private readonly k: number
  19   /** The size of the priority queue. */
  20   public size!: number
  21   /** The maximum size of the priority queue. */
  22   public maxSize!: number
  23
  24   /**
  25    * Constructs a k-priority queue.
  26    *
  27    * @param k - Prioritized bucket size.
  28    */
  29   public constructor (k = Infinity) {
  30     if (k !== Infinity && !Number.isSafeInteger(k)) {
  31       throw new TypeError('k must be an integer')
  32     }
  33     if (k < 1) {
  34       throw new RangeError('k must be greater than or equal to 1')
  35     }
  36     this.k = k
  37     this.clear()
  38   }
  39
  40   /**
  41    * Enqueue data into the priority queue.
  42    *
  43    * @param data - Data to enqueue.
  44    * @param priority - Priority of the data. Lower values have higher priority.
  45    * @returns The new size of the priority queue.
  46    */
  47   public enqueue (data: T, priority?: number): number {
  48     priority = priority ?? 0
  49     const startIndex =
  50       this.k === Infinity || this.nodeArray.length / this.k < 1
  51         ? 0
  52         : Math.trunc(this.nodeArray.length / this.k) * this.k
  53     let inserted = false
  54     for (let index = startIndex; index < this.nodeArray.length; index++) {
  55       if (this.nodeArray[index].priority > priority) {
  56         this.nodeArray.splice(index, 0, { data, priority })
  57         inserted = true
  58         break
  59       }
  60     }
  61     if (!inserted) {
  62       this.nodeArray.push({ data, priority })
  63     }
  64     return this.incrementSize()
  65   }
  66
  67   /**
  68    * Dequeue data from the priority queue.
  69    *
  70    * @returns The dequeued data or `undefined` if the priority queue is empty.
  71    */
  72   public dequeue (): T | undefined {
  73     if (this.size > 0) {
  74       --this.size
  75     }
  76     return this.nodeArray.shift()?.data
  77   }
  78
  79   /**
  80    * Peeks at the first data.
  81    * @returns The first data or `undefined` if the priority queue is empty.
  82    */
  83   public peekFirst (): T | undefined {
  84     return this.nodeArray[0]?.data
  85   }
  86
  87   /**
  88    * Peeks at the last data.
  89    * @returns The last data or `undefined` if the priority queue is empty.
  90    */
  91   public peekLast (): T | undefined {
  92     return this.nodeArray[this.nodeArray.length - 1]?.data
  93   }
  94
  95   /**
  96    * Clears the priority queue.
  97    */
  98   public clear (): void {
  99     this.nodeArray = []
 100     this.size = 0
 101     this.maxSize = 0
 102   }
 103
 104   /**
 105    * Increments the size of the deque.
 106    *
 107    * @returns The new size of the deque.
 108    */
 109   private incrementSize (): number {
 110     ++this.size
 111     if (this.size > this.maxSize) {
 112       this.maxSize = this.size
 113     }
 114     return this.size
 115   }
 116 }