src/queue.ts

   1 // Copyright Jerome Benoit. 2021-2023. All Rights Reserved.
   2
   3 /**
   4  * Queue
   5  *
   6  * @typeParam T - Type of queue items.
   7  */
   8 export class Queue<T> {
   9   private items!: T[]
  10   private offset!: number
  11   /** The size of the queue. */
  12   public size!: number
  13   /** The maximum size of the queue. */
  14   public maxSize!: number
  15
  16   public constructor () {
  17     this.clear()
  18   }
  19
  20   /**
  21    * Enqueue an item.
  22    *
  23    * @param item - Item to enqueue.
  24    * @returns The new size of the queue.
  25    */
  26   public enqueue (item: T): number {
  27     this.items.push(item)
  28     ++this.size
  29     if (this.size > this.maxSize) {
  30       this.maxSize = this.size
  31     }
  32     return this.size
  33   }
  34
  35   /**
  36    * Dequeue an item.
  37    *
  38    * @returns The dequeued item or `undefined` if the queue is empty.
  39    */
  40   public dequeue (): T | undefined {
  41     if (this.size <= 0) {
  42       return undefined
  43     }
  44     const item = this.items[this.offset]
  45     if (++this.offset * 2 >= this.items.length) {
  46       this.items = this.items.slice(this.offset)
  47       this.offset = 0
  48     }
  49     --this.size
  50     return item
  51   }
  52
  53   /**
  54    * Peeks at the first item.
  55    *
  56    * @returns The first item or `undefined` if the queue is empty.
  57    */
  58   public peek (): T | undefined {
  59     if (this.size <= 0) {
  60       return undefined
  61     }
  62     return this.items[this.offset]
  63   }
  64
  65   /**
  66    * Clears the queue.
  67    */
  68   public clear (): void {
  69     this.items = []
  70     this.offset = 0
  71     this.size = 0
  72     this.maxSize = 0
  73   }
  74
  75   /**
  76    * Returns an iterator for the queue.
  77    *
  78    * @returns An iterator for the queue.
  79    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
  80    */
  81   [Symbol.iterator] (): Iterator<T> {
  82     const items = this.items
  83     let i = this.offset
  84
  85     return {
  86       next: () => {
  87         if (i >= items.length) {
  88           return {
  89             value: undefined,
  90             done: true
  91           }
  92         }
  93         const value = items[i]
  94         ++i
  95         return {
  96           value,
  97           done: false
  98         }
  99       }
 100     }
 101   }
 102 }