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