src/priority-queue.ts

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