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    * @returns PriorityQueue.
  38    */
  39   public constructor (bucketSize: number = defaultBucketSize) {
  40     if (!Number.isSafeInteger(bucketSize)) {
  41       throw new TypeError(
  42         `Invalid bucket size: '${bucketSize}' is not an integer`
  43       )
  44     }
  45     if (bucketSize < 0) {
  46       throw new RangeError(`Invalid bucket size: ${bucketSize} < 0`)
  47     }
  48     this.bucketSize = bucketSize
  49     this.clear()
  50   }
  51
  52   /**
  53    * The priority queue size.
  54    */
  55   public get size (): number {
  56     let node: PriorityQueueNode<T> | undefined = this.tail
  57     let size = 0
  58     while (node != null) {
  59       size += node.size
  60       node = node.next
  61     }
  62     return size
  63   }
  64
  65   /**
  66    * The number of filled prioritized buckets.
  67    */
  68   public get buckets (): number {
  69     return Math.trunc(this.size / this.bucketSize)
  70   }
  71
  72   /**
  73    * Enqueue data into the priority queue.
  74    *
  75    * @param data - Data to enqueue.
  76    * @param priority - Priority of the data. Lower values have higher priority.
  77    * @returns The new size of the priority queue.
  78    */
  79   public enqueue (data: T, priority?: number): number {
  80     if (this.head.full()) {
  81       this.head = this.head.next = new FixedPriorityQueue(this.bucketSize)
  82     }
  83     this.head.enqueue(data, priority)
  84     const size = this.size
  85     if (size > this.maxSize) {
  86       this.maxSize = size
  87     }
  88     return size
  89   }
  90
  91   /**
  92    * Dequeue data from the priority queue.
  93    *
  94    * @param bucket - The prioritized bucket to dequeue from.
  95    * @returns The dequeued data or `undefined` if the priority queue is empty.
  96    */
  97   public dequeue (bucket?: number): T | undefined {
  98     let tail: PriorityQueueNode<T> | undefined = this.tail
  99     let tailChanged = false
 100     if (bucket != null && bucket > 0) {
 101       let currentBucket = 1
 102       while (tail != null) {
 103         if (currentBucket === bucket) {
 104           break
 105         }
 106         ++currentBucket
 107         tail = tail.next
 108         tailChanged = true
 109       }
 110     }
 111     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 112     const data = tail!.dequeue()
 113     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 114     if (tail!.empty() && tail!.next != null) {
 115       if (!tailChanged) {
 116         // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 117         this.tail = tail!.next
 118       } else {
 119         let node: PriorityQueueNode<T> | undefined = this.tail
 120         while (node != null) {
 121           if (node.next === tail) {
 122             // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 123             node.next = tail!.next
 124             break
 125           }
 126           node = node.next
 127         }
 128       }
 129       // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 130       delete tail!.next
 131     }
 132     return data
 133   }
 134
 135   /**
 136    * Clears the priority queue.
 137    */
 138   public clear (): void {
 139     this.head = this.tail = new FixedPriorityQueue(this.bucketSize)
 140     this.maxSize = 0
 141   }
 142
 143   /**
 144    * Returns an iterator for the priority queue.
 145    *
 146    * @returns An iterator for the priority queue.
 147    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 148    */
 149   public [Symbol.iterator] (): Iterator<T> {
 150     let index = 0
 151     let node = this.tail
 152     return {
 153       next: () => {
 154         const value = node.get(index) as T
 155         if (value == null) {
 156           return {
 157             value: undefined,
 158             done: true
 159           }
 160         }
 161         ++index
 162         if (index === node.capacity && node.next != null) {
 163           node = node.next
 164           index = 0
 165         }
 166         return {
 167           value,
 168           done: false
 169         }
 170       }
 171     }
 172   }
 173 }