src/fixed-priority-queue.ts

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