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