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 export 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 size!: number
  27   public maxSize!: number
  28
  29   constructor (size: number = defaultQueueSize) {
  30     this.checkSize(size)
  31     this.nodeArray = new Array<PriorityQueueNode<T>>(size)
  32     this.clear()
  33   }
  34
  35   public empty (): boolean {
  36     return this.size === 0
  37   }
  38
  39   public full (): boolean {
  40     return this.size === this.nodeArray.length
  41   }
  42
  43   public enqueue (data: T, priority?: number): number {
  44     if (this.full()) {
  45       throw new Error('Priority queue is full')
  46     }
  47     priority = priority ?? 0
  48     const nodeArrayLength = this.nodeArray.length
  49     let index = this.start
  50     let inserted = false
  51     for (let i = 0; i < this.size; i++) {
  52       if (this.nodeArray[index]?.priority > priority) {
  53         this.nodeArray.splice(index, 0, { data, priority })
  54         inserted = true
  55         break
  56       }
  57       ++index
  58       if (index === nodeArrayLength) {
  59         index = 0
  60       }
  61     }
  62     this.nodeArray.length !== nodeArrayLength &&
  63       (this.nodeArray.length = nodeArrayLength)
  64     if (!inserted) {
  65       let index = this.start + this.size
  66       if (index >= nodeArrayLength) {
  67         index -= nodeArrayLength
  68       }
  69       this.nodeArray[index] = { data, priority }
  70     }
  71     return this.incrementSize()
  72   }
  73
  74   public dequeue (): T | undefined {
  75     if (this.empty()) {
  76       return undefined
  77     }
  78     const index = this.start
  79     --this.size
  80     ++this.start
  81     if (this.start === this.nodeArray.length) {
  82       this.start = 0
  83     }
  84     return this.nodeArray[index].data
  85   }
  86
  87   /**
  88    * Clears the fixed priority queue.
  89    */
  90   public clear (): void {
  91     this.start = 0
  92     this.size = 0
  93     this.maxSize = 0
  94   }
  95
  96   /**
  97    * Returns an iterator for the fixed priority queue.
  98    *
  99    * @returns An iterator for the fixed priority queue.
 100    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 101    */
 102   [Symbol.iterator] (): Iterator<T> {
 103     let index = this.start
 104     let i = 0
 105     return {
 106       next: () => {
 107         if (i >= this.size) {
 108           return {
 109             value: undefined,
 110             done: true
 111           }
 112         }
 113         const value = this.nodeArray[index].data
 114         ++index
 115         ++i
 116         if (index === this.nodeArray.length) {
 117           index = 0
 118         }
 119         return {
 120           value,
 121           done: false
 122         }
 123       }
 124     }
 125   }
 126
 127   /**
 128    * Increments the size of the fixed priority queue.
 129    *
 130    * @returns The new size of the fixed priority queue.
 131    */
 132   private incrementSize (): number {
 133     ++this.size
 134     if (this.size > this.maxSize) {
 135       this.maxSize = this.size
 136     }
 137     return this.size
 138   }
 139
 140   private checkSize (size: number): void {
 141     if (!Number.isSafeInteger(size)) {
 142       throw new TypeError(
 143         `Invalid fixed priority queue size: '${size}' is not an integer`
 144       )
 145     }
 146     if (size < 0) {
 147       throw new RangeError(`Invalid fixed priority queue size: ${size} < 0`)
 148     }
 149   }
 150 }