src/fixed-priority-queue.ts

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