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