src/fixed-priority-queue.ts

   1 /**
   2  * Default buffer size.
   3  */
   4 export const defaultQueueSize = 2048
   5
   6 /**
   7  * Fixed priority queue node.
   8  * @typeParam T - Type of priority queue node data.
   9  * @internal
  10  */
  11 export interface FixedPriorityQueueNode<T> {
  12   data: T
  13   priority: number
  14 }
  15
  16 /**
  17  * Fixed priority queue.
  18  * @typeParam T - Type of fixed priority queue data.
  19  * @internal
  20  */
  21 export class FixedPriorityQueue<T> {
  22   private start!: number
  23   private readonly nodeArray: FixedPriorityQueueNode<T>[]
  24   /** The fixed priority queue capacity. */
  25   public readonly capacity: number
  26   /** The fixed priority queue size. */
  27   public size!: number
  28   /** Whether to enable priority. */
  29   public enablePriority: boolean
  30
  31   /**
  32    * Constructs a fixed priority queue.
  33    * @param size - Fixed priority queue size. @defaultValue defaultQueueSize
  34    * @param enablePriority - Whether to enable priority. @defaultValue false
  35    * @returns FixedPriorityQueue.
  36    */
  37   constructor (size: number = defaultQueueSize, enablePriority = false) {
  38     this.checkSize(size)
  39     this.capacity = size
  40     this.enablePriority = enablePriority
  41     this.nodeArray = new Array<FixedPriorityQueueNode<T>>(this.capacity)
  42     this.clear()
  43   }
  44
  45   /**
  46    * Checks if the fixed priority queue is empty.
  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    * @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    * @param data - Data to enqueue.
  64    * @param priority - Priority of the data. Lower values have higher priority.
  65    * @returns The new size of the priority queue.
  66    * @throws If the fixed priority queue is full.
  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 inserted = false
  74     if (this.enablePriority) {
  75       let index = this.start
  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           this.nodeArray.length !== this.capacity &&
  80             (this.nodeArray.length = this.capacity)
  81           inserted = true
  82           break
  83         }
  84         ++index
  85         if (index === this.capacity) {
  86           index = 0
  87         }
  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    * @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    * @returns The dequeued data or `undefined` if the priority queue is empty.
 119    */
 120   public dequeue (): T | undefined {
 121     if (this.empty()) {
 122       return undefined
 123     }
 124     const index = this.start
 125     --this.size
 126     ++this.start
 127     if (this.start === this.capacity) {
 128       this.start = 0
 129     }
 130     return this.nodeArray[index].data
 131   }
 132
 133   /**
 134    * Clears the fixed priority queue.
 135    */
 136   public clear (): void {
 137     this.start = 0
 138     this.size = 0
 139   }
 140
 141   /**
 142    * Returns an iterator for the fixed priority queue.
 143    * @returns An iterator for the fixed priority queue.
 144    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 145    */
 146   public [Symbol.iterator] (): Iterator<T> {
 147     let index = this.start
 148     let i = 0
 149     return {
 150       next: () => {
 151         if (i >= this.size) {
 152           return {
 153             value: undefined,
 154             done: true,
 155           }
 156         }
 157         const value = this.nodeArray[index].data
 158         ++index
 159         ++i
 160         if (index === this.capacity) {
 161           index = 0
 162         }
 163         return {
 164           value,
 165           done: false,
 166         }
 167       },
 168     }
 169   }
 170
 171   /**
 172    * Checks the queue size.
 173    * @param size - Queue size.
 174    */
 175   private checkSize (size: number): void {
 176     if (!Number.isSafeInteger(size)) {
 177       throw new TypeError(
 178         `Invalid fixed priority queue size: '${size.toString()}' is not an integer`
 179       )
 180     }
 181     if (size < 0) {
 182       throw new RangeError(
 183         `Invalid fixed priority queue size: ${size.toString()} < 0`
 184       )
 185     }
 186   }
 187 }