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    * @returns The priority queue size.
  60    */
  61   public get size (): number {
  62     let node: PriorityQueueNode<T> | undefined = this.tail
  63     let size = 0
  64     while (node != null) {
  65       size += node.size
  66       node = node.next
  67     }
  68     return size
  69   }
  70
  71   public get enablePriority (): boolean {
  72     return this.head.enablePriority
  73   }
  74
  75   public set enablePriority (enablePriority: boolean) {
  76     if (this.head.enablePriority === enablePriority) {
  77       return
  78     }
  79     let node: PriorityQueueNode<T> | undefined = this.tail
  80     while (node != null) {
  81       node.enablePriority = enablePriority
  82       node = node.next
  83     }
  84   }
  85
  86   /**
  87    * The number of filled prioritized buckets.
  88    * @returns The number of filled prioritized buckets.
  89    */
  90   public get buckets (): number {
  91     return Math.trunc(this.size / this.bucketSize)
  92   }
  93
  94   /**
  95    * Enqueue data into the priority queue.
  96    * @param data - Data to enqueue.
  97    * @param priority - Priority of the data. Lower values have higher priority.
  98    * @returns The new size of the priority queue.
  99    */
 100   public enqueue (data: T, priority?: number): number {
 101     if (this.head.full()) {
 102       this.head = this.head.next = new FixedPriorityQueue(
 103         this.bucketSize,
 104         this.enablePriority
 105       )
 106     }
 107     this.head.enqueue(data, priority)
 108     const size = this.size
 109     if (size > this.maxSize) {
 110       this.maxSize = size
 111     }
 112     return size
 113   }
 114
 115   /**
 116    * Dequeue data from the priority queue.
 117    * @param bucket - The prioritized bucket to dequeue from.
 118    * @returns The dequeued data or `undefined` if the priority queue is empty.
 119    */
 120   public dequeue (bucket?: number): T | undefined {
 121     let tail: PriorityQueueNode<T> | undefined = this.tail
 122     let tailChanged = false
 123     if (bucket != null && bucket > 0) {
 124       let currentBucket = 1
 125       while (tail != null) {
 126         if (currentBucket === bucket) {
 127           break
 128         }
 129         ++currentBucket
 130         tail = tail.next
 131         tailChanged = true
 132       }
 133     }
 134     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 135     const data = tail!.dequeue()
 136     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 137     if (tail!.empty() && tail!.next != null) {
 138       if (!tailChanged) {
 139         // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 140         this.tail = tail!.next
 141       } else {
 142         let node: PriorityQueueNode<T> | undefined = this.tail
 143         while (node != null) {
 144           if (node.next === tail) {
 145             // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 146             node.next = tail!.next
 147             break
 148           }
 149           node = node.next
 150         }
 151       }
 152       // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 153       delete tail!.next
 154     }
 155     return data
 156   }
 157
 158   /**
 159    * Clears the priority queue.
 160    */
 161   public clear (): void {
 162     this.head = this.tail = new FixedPriorityQueue(
 163       this.bucketSize,
 164       this.enablePriority
 165     )
 166     this.maxSize = 0
 167   }
 168
 169   /**
 170    * Returns an iterator for the priority queue.
 171    * @returns An iterator for the priority queue.
 172    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 173    */
 174   public [Symbol.iterator] (): Iterator<T> {
 175     let index = 0
 176     let node = this.tail
 177     return {
 178       next: () => {
 179         const value = node.get(index) as T
 180         if (value == null) {
 181           return {
 182             value: undefined,
 183             done: true,
 184           }
 185         }
 186         ++index
 187         if (index === node.capacity && node.next != null) {
 188           node = node.next
 189           index = 0
 190         }
 191         return {
 192           value,
 193           done: false,
 194         }
 195       },
 196     }
 197   }
 198 }