src/priority-queue.ts

   1 // Copyright Jerome Benoit. 2024. All Rights Reserved.
   2
   3 import { FixedPriorityQueue } from './fixed-priority-queue.js'
   4
   5 /**
   6  * Default bucket size.
   7  */
   8 export const defaultBucketSize = 2048
   9
  10 /**
  11  * Priority queue node.
  12  * @typeParam T - Type of priority queue node data.
  13  * @internal
  14  */
  15 export interface PriorityQueueNode<T> extends FixedPriorityQueue<T> {
  16   next?: FixedPriorityQueue<T>
  17 }
  18
  19 /**
  20  * Priority queue.
  21  * @typeParam T - Type of priority queue data.
  22  * @internal
  23  */
  24 export class PriorityQueue<T> {
  25   private head!: PriorityQueueNode<T>
  26   private tail!: PriorityQueueNode<T>
  27   private readonly bucketSize: number
  28   /** The priority queue maximum size. */
  29   public maxSize!: number
  30
  31   /**
  32    * Constructs a priority queue.
  33    * @param bucketSize - Prioritized bucket size. @defaultValue defaultBucketSize
  34    * @param enablePriority - Whether to enable priority. @defaultValue false
  35    * @returns PriorityQueue.
  36    */
  37   public constructor (
  38     bucketSize: number = defaultBucketSize,
  39     enablePriority = false
  40   ) {
  41     if (!Number.isSafeInteger(bucketSize)) {
  42       throw new TypeError(
  43         `Invalid bucket size: '${bucketSize.toString()}' is not an integer`
  44       )
  45     }
  46     if (bucketSize < 0) {
  47       throw new RangeError(`Invalid bucket size: ${bucketSize.toString()} < 0`)
  48     }
  49     this.bucketSize = bucketSize
  50     this.head = this.tail = new FixedPriorityQueue(
  51       this.bucketSize,
  52       enablePriority
  53     )
  54     this.maxSize = 0
  55   }
  56
  57   /**
  58    * The priority queue size.
  59    */
  60   public get size (): number {
  61     let node: PriorityQueueNode<T> | undefined = this.tail
  62     let size = 0
  63     while (node != null) {
  64       size += node.size
  65       node = node.next
  66     }
  67     return size
  68   }
  69
  70   public get enablePriority (): boolean {
  71     return this.head.enablePriority
  72   }
  73
  74   public set enablePriority (enablePriority: boolean) {
  75     if (this.head.enablePriority === enablePriority) {
  76       return
  77     }
  78     let node: PriorityQueueNode<T> | undefined = this.tail
  79     while (node != null) {
  80       node.enablePriority = enablePriority
  81       node = node.next
  82     }
  83   }
  84
  85   /**
  86    * The number of filled prioritized buckets.
  87    */
  88   public get buckets (): number {
  89     return Math.trunc(this.size / this.bucketSize)
  90   }
  91
  92   /**
  93    * Enqueue data into the priority queue.
  94    * @param data - Data to enqueue.
  95    * @param priority - Priority of the data. Lower values have higher priority.
  96    * @returns The new size of the priority queue.
  97    */
  98   public enqueue (data: T, priority?: number): number {
  99     if (this.head.full()) {
 100       this.head = this.head.next = new FixedPriorityQueue(
 101         this.bucketSize,
 102         this.enablePriority
 103       )
 104     }
 105     this.head.enqueue(data, priority)
 106     const size = this.size
 107     if (size > this.maxSize) {
 108       this.maxSize = size
 109     }
 110     return size
 111   }
 112
 113   /**
 114    * Dequeue data from the priority queue.
 115    * @param bucket - The prioritized bucket to dequeue from.
 116    * @returns The dequeued data or `undefined` if the priority queue is empty.
 117    */
 118   public dequeue (bucket?: number): T | undefined {
 119     let tail: PriorityQueueNode<T> | undefined = this.tail
 120     let tailChanged = false
 121     if (bucket != null && bucket > 0) {
 122       let currentBucket = 1
 123       while (tail != null) {
 124         if (currentBucket === bucket) {
 125           break
 126         }
 127         ++currentBucket
 128         tail = tail.next
 129         tailChanged = true
 130       }
 131     }
 132     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 133     const data = tail!.dequeue()
 134     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 135     if (tail!.empty() && tail!.next != null) {
 136       if (!tailChanged) {
 137         // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 138         this.tail = tail!.next
 139       } else {
 140         let node: PriorityQueueNode<T> | undefined = this.tail
 141         while (node != null) {
 142           if (node.next === tail) {
 143             // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 144             node.next = tail!.next
 145             break
 146           }
 147           node = node.next
 148         }
 149       }
 150       // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 151       delete tail!.next
 152     }
 153     return data
 154   }
 155
 156   /**
 157    * Clears the priority queue.
 158    */
 159   public clear (): void {
 160     this.head = this.tail = new FixedPriorityQueue(
 161       this.bucketSize,
 162       this.enablePriority
 163     )
 164     this.maxSize = 0
 165   }
 166
 167   /**
 168    * Returns an iterator for the priority queue.
 169    * @returns An iterator for the priority queue.
 170    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 171    */
 172   public [Symbol.iterator] (): Iterator<T> {
 173     let index = 0
 174     let node = this.tail
 175     return {
 176       next: () => {
 177         const value = node.get(index) as T
 178         if (value == null) {
 179           return {
 180             value: undefined,
 181             done: true,
 182           }
 183         }
 184         ++index
 185         if (index === node.capacity && node.next != null) {
 186           node = node.next
 187           index = 0
 188         }
 189         return {
 190           value,
 191           done: false,
 192         }
 193       },
 194     }
 195   }
 196 }