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    * @throws If the fixed priority queue is full.
  69    */
  70   public enqueue (data: T, priority?: number): number {
  71     if (this.full()) {
  72       throw new Error('Priority queue is full')
  73     }
  74     priority = priority ?? 0
  75     let index = this.start
  76     let inserted = false
  77     for (let i = 0; i < this.size; i++) {
  78       if (this.nodeArray[index].priority > priority) {
  79         this.nodeArray.splice(index, 0, { data, priority })
  80         this.nodeArray.length !== this.capacity &&
  81           (this.nodeArray.length = this.capacity)
  82         inserted = true
  83         break
  84       }
  85       ++index
  86       if (index === this.capacity) {
  87         index = 0
  88       }
  89     }
  90     if (!inserted) {
  91       let index = this.start + this.size
  92       if (index >= this.capacity) {
  93         index -= this.capacity
  94       }
  95       this.nodeArray[index] = { data, priority }
  96     }
  97     return ++this.size
  98   }
  99
 100   /**
 101    * Gets data from the fixed priority queue.
 102    *
 103    * @param index - The index of the data to get.
 104    * @returns The data at the index or `undefined` if the fixed priority queue is empty or the index is out of bounds.
 105    */
 106   public get (index: number): T | undefined {
 107     if (this.empty() || index >= this.size) {
 108       return undefined
 109     }
 110     index += this.start
 111     if (index >= this.capacity) {
 112       index -= this.capacity
 113     }
 114     return this.nodeArray[index].data
 115   }
 116
 117   /**
 118    * Dequeue data from the fixed priority queue.
 119    *
 120    * @returns The dequeued data or `undefined` if the priority queue is empty.
 121    */
 122   public dequeue (): T | undefined {
 123     if (this.empty()) {
 124       return undefined
 125     }
 126     const index = this.start
 127     --this.size
 128     ++this.start
 129     if (this.start === this.capacity) {
 130       this.start = 0
 131     }
 132     return this.nodeArray[index].data
 133   }
 134
 135   /**
 136    * Clears the fixed priority queue.
 137    */
 138   public clear (): void {
 139     this.start = 0
 140     this.size = 0
 141   }
 142
 143   /**
 144    * Returns an iterator for the fixed priority queue.
 145    *
 146    * @returns An iterator for the fixed priority queue.
 147    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 148    */
 149   public [Symbol.iterator] (): Iterator<T> {
 150     let index = this.start
 151     let i = 0
 152     return {
 153       next: () => {
 154         if (i >= this.size) {
 155           return {
 156             value: undefined,
 157             done: true
 158           }
 159         }
 160         const value = this.nodeArray[index].data
 161         ++index
 162         ++i
 163         if (index === this.capacity) {
 164           index = 0
 165         }
 166         return {
 167           value,
 168           done: false
 169         }
 170       }
 171     }
 172   }
 173
 174   /**
 175    * Checks the size.
 176    *
 177    * @param size - The size to check.
 178    */
 179   private checkSize (size: number): void {
 180     if (!Number.isSafeInteger(size)) {
 181       throw new TypeError(
 182         `Invalid fixed priority queue size: '${size}' is not an integer`
 183       )
 184     }
 185     if (size < 0) {
 186       throw new RangeError(`Invalid fixed priority queue size: ${size} < 0`)
 187     }
 188   }
 189 }