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