src/queues/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 './queue-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 readonly bucketSize: number
  19   private head!: PriorityQueueNode<T>
  20   private priorityEnabled: boolean
  21   private tail!: PriorityQueueNode<T>
  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   private getPriorityQueueNode (
  49     nodeArray?: FixedQueueNode<T>[]
  50   ): PriorityQueueNode<T> {
  51     let fixedQueue: IFixedQueue<T>
  52     if (this.priorityEnabled) {
  53       fixedQueue = new FixedPriorityQueue(this.bucketSize)
  54     } else {
  55       fixedQueue = new FixedQueue(this.bucketSize)
  56     }
  57     if (nodeArray != null) {
  58       fixedQueue.nodeArray = nodeArray
  59     }
  60     return fixedQueue
  61   }
  62
  63   /**
  64    * Clears the priority queue.
  65    */
  66   public clear (): void {
  67     this.head = this.tail = this.getPriorityQueueNode()
  68     this.maxSize = 0
  69   }
  70
  71   /**
  72    * Dequeue data from the priority queue.
  73    * @param bucket - The prioritized bucket to dequeue from.
  74    * @returns The dequeued data or `undefined` if the priority queue is empty.
  75    */
  76   public dequeue (bucket?: number): T | undefined {
  77     let tail: PriorityQueueNode<T> | undefined = this.tail
  78     let tailChanged = false
  79     if (bucket != null && bucket > 0) {
  80       let currentBucket = 1
  81       while (tail != null) {
  82         if (currentBucket === bucket) {
  83           break
  84         }
  85         ++currentBucket
  86         tail = tail.next
  87       }
  88       tailChanged = tail !== this.tail
  89     }
  90     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
  91     const data = tail!.dequeue()
  92     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
  93     if (tail!.empty()) {
  94       // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
  95       if (!tailChanged && tail!.next != null) {
  96         // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
  97         this.tail = tail!.next
  98         // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
  99         delete tail!.next
 100       } else if (tailChanged) {
 101         let node: PriorityQueueNode<T> | undefined = this.tail
 102         while (node != null) {
 103           // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 104           if (node.next === tail && tail!.next != null) {
 105             // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 106             node.next = tail!.next
 107             // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 108             delete tail!.next
 109             break
 110             // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 111           } else if (node.next === tail && tail!.next == null) {
 112             delete node.next
 113             this.head = node
 114             break
 115           }
 116           node = node.next
 117         }
 118       }
 119     }
 120     return data
 121   }
 122
 123   /**
 124    * Enqueue data into the priority queue.
 125    * @param data - Data to enqueue.
 126    * @param priority - Priority of the data. Lower values have higher priority.
 127    * @returns The new size of the priority queue.
 128    */
 129   public enqueue (data: T, priority?: number): number {
 130     if (this.head.full()) {
 131       this.head = this.head.next = this.getPriorityQueueNode()
 132     }
 133     this.head.enqueue(data, priority)
 134     const size = this.size
 135     if (size > this.maxSize) {
 136       this.maxSize = size
 137     }
 138     return size
 139   }
 140
 141   /**
 142    * Returns an iterator for the priority queue.
 143    * @returns An iterator for the priority queue.
 144    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 145    */
 146   public [Symbol.iterator] (): Iterator<T> {
 147     let index = 0
 148     let node = this.tail
 149     return {
 150       next: () => {
 151         const value = node.get(index) as T
 152         if (value == null) {
 153           return {
 154             done: true,
 155             value: undefined,
 156           }
 157         }
 158         ++index
 159         if (index === node.capacity && node.next != null) {
 160           node = node.next
 161           index = 0
 162         }
 163         return {
 164           done: false,
 165           value,
 166         }
 167       },
 168     }
 169   }
 170
 171   /**
 172    * The number of filled prioritized buckets.
 173    * @returns The number of filled prioritized buckets.
 174    */
 175   public get buckets (): number {
 176     return Math.trunc(this.size / this.bucketSize)
 177   }
 178
 179   /**
 180    * Whether priority is enabled.
 181    * @returns Whether priority is enabled.
 182    */
 183   public get enablePriority (): boolean {
 184     return this.priorityEnabled
 185   }
 186
 187   /**
 188    * Enables/disables priority.
 189    * @param enablePriority - Whether to enable priority.
 190    */
 191   public set enablePriority (enablePriority: boolean) {
 192     if (this.priorityEnabled === enablePriority) {
 193       return
 194     }
 195     this.priorityEnabled = enablePriority
 196     let head: PriorityQueueNode<T>
 197     let tail: PriorityQueueNode<T>
 198     let prev: PriorityQueueNode<T> | undefined
 199     let node: PriorityQueueNode<T> | undefined = this.tail
 200     let buckets = 0
 201     while (node != null) {
 202       const currentNode = this.getPriorityQueueNode(node.nodeArray)
 203       if (buckets === 0) {
 204         tail = currentNode
 205       }
 206       if (prev != null) {
 207         prev.next = currentNode
 208       }
 209       prev = currentNode
 210       if (node.next == null) {
 211         head = currentNode
 212       }
 213       ++buckets
 214       node = node.next
 215     }
 216     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 217     this.head = head!
 218     // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
 219     this.tail = tail!
 220   }
 221
 222   /**
 223    * The priority queue size.
 224    * @returns The priority queue size.
 225    */
 226   public get size (): number {
 227     let node: PriorityQueueNode<T> | undefined = this.tail
 228     let size = 0
 229     while (node != null) {
 230       size += node.size
 231       node = node.next
 232     }
 233     return size
 234   }
 235 }