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