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