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