src/fixed-priority-queue.ts

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