src/fixed-priority-queue.ts

   1 import { defaultQueueSize, type FixedQueueNode, type IFixedQueue } from './utility-types.js'
   2
   3 /**
   4  * Fixed priority queue.
   5  * @typeParam T - Type of fixed priority queue data.
   6  * @internal
   7  */
   8 export class FixedPriorityQueue<T> implements IFixedQueue<T> {
   9   private start!: number
  10   /** @inheritdoc */
  11   public readonly capacity: number
  12   /** @inheritdoc */
  13   public size!: number
  14   /** @inheritdoc */
  15   public nodeArray: FixedQueueNode<T>[]
  16
  17   /**
  18    * Constructs a fixed priority queue.
  19    * @param size - Fixed priority queue size. @defaultValue defaultQueueSize
  20    * @returns FixedPriorityQueue.
  21    */
  22   constructor (size: number = defaultQueueSize) {
  23     this.checkSize(size)
  24     this.capacity = size
  25     this.nodeArray = new Array<FixedQueueNode<T>>(this.capacity)
  26     this.clear()
  27   }
  28
  29   /** @inheritdoc */
  30   public empty (): boolean {
  31     return this.size === 0
  32   }
  33
  34   /** @inheritdoc */
  35   public full (): boolean {
  36     return this.size === this.capacity
  37   }
  38
  39   /** @inheritdoc */
  40   public enqueue (data: T, priority?: number): number {
  41     if (this.full()) {
  42       throw new Error('Priority queue is full')
  43     }
  44     priority = priority ?? 0
  45     let inserted = false
  46     let index = this.start
  47     for (let i = 0; i < this.size; i++) {
  48       if (this.nodeArray[index].priority > priority) {
  49         this.nodeArray.splice(index, 0, { data, priority })
  50         this.nodeArray.length = this.capacity
  51         inserted = true
  52         break
  53       }
  54       ++index
  55       if (index === this.capacity) {
  56         index = 0
  57       }
  58     }
  59     if (!inserted) {
  60       let index = this.start + this.size
  61       if (index >= this.capacity) {
  62         index -= this.capacity
  63       }
  64       this.nodeArray[index] = { data, priority }
  65     }
  66     return ++this.size
  67   }
  68
  69   /** @inheritdoc */
  70   public get (index: number): T | undefined {
  71     if (this.empty() || index >= this.size) {
  72       return undefined
  73     }
  74     index += this.start
  75     if (index >= this.capacity) {
  76       index -= this.capacity
  77     }
  78     return this.nodeArray[index].data
  79   }
  80
  81   /** @inheritdoc */
  82   public dequeue (): T | undefined {
  83     if (this.empty()) {
  84       return undefined
  85     }
  86     const index = this.start
  87     --this.size
  88     ++this.start
  89     if (this.start === this.capacity) {
  90       this.start = 0
  91     }
  92     return this.nodeArray[index].data
  93   }
  94
  95   /** @inheritdoc */
  96   public clear (): void {
  97     this.start = 0
  98     this.size = 0
  99   }
 100
 101   /** @inheritdoc */
 102   public [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.capacity) {
 117           index = 0
 118         }
 119         return {
 120           value,
 121           done: false,
 122         }
 123       },
 124     }
 125   }
 126
 127   /**
 128    * Checks the fixed queue size.
 129    * @param size - Queue size.
 130    */
 131   private checkSize (size: number): void {
 132     if (!Number.isSafeInteger(size)) {
 133       throw new TypeError(
 134         `Invalid fixed priority queue size: '${size.toString()}' is not an integer`
 135       )
 136     }
 137     if (size < 0) {
 138       throw new RangeError(
 139         `Invalid fixed priority queue size: ${size.toString()} < 0`
 140       )
 141     }
 142   }
 143 }