src/deque.ts

   1 // Copyright Jerome Benoit. 2023. All Rights Reserved.
   2
   3 /**
   4  * @internal
   5  */
   6 export class Node<T> {
   7   public value: T
   8   public next?: Node<T>
   9   public prev?: Node<T>
  10
  11   public constructor (value: T) {
  12     this.value = value
  13   }
  14 }
  15
  16 /**
  17  * Deque.
  18  * Implemented with a doubly linked list.
  19  *
  20  * @typeParam T - Type of deque values.
  21  * @internal
  22  */
  23 export class Deque<T> {
  24   private head?: Node<T>
  25   private tail?: Node<T>
  26   /** The size of the deque. */
  27   public size!: number
  28   /** The maximum size of the deque. */
  29   public maxSize!: number
  30
  31   public constructor () {
  32     this.clear()
  33   }
  34
  35   /**
  36    * Appends a value to the deque.
  37    *
  38    * @param value - Value to append.
  39    * @returns The new size of the queue.
  40    */
  41   public push (value: T): number {
  42     const node = new Node(value)
  43     if (this.tail == null) {
  44       this.head = this.tail = node
  45     } else {
  46       node.prev = this.tail
  47       this.tail = this.tail.next = node
  48     }
  49     return this.incrementSize()
  50   }
  51
  52   /**
  53    * Prepends a value to the deque.
  54    *
  55    * @param value - Value to prepend.
  56    * @returns The new size of the queue.
  57    */
  58   public unshift (value: T): number {
  59     const node = new Node(value)
  60     if (this.head == null) {
  61       this.head = this.tail = node
  62     } else {
  63       node.next = this.head
  64       this.head = this.head.prev = node
  65     }
  66     return this.incrementSize()
  67   }
  68
  69   /**
  70    * Pops a value from the deque.
  71    *
  72    * @returns The popped value or `undefined` if the deque is empty.
  73    */
  74   public pop (): T | undefined {
  75     if (this.head == null) {
  76       return undefined
  77     }
  78     const tail = this.tail
  79     this.tail = (this.tail as Node<T>).prev
  80     if (this.tail == null) {
  81       this.head = undefined
  82     } else {
  83       this.tail.next = undefined
  84     }
  85     --this.size
  86     return tail?.value
  87   }
  88
  89   /**
  90    * Shifts a value from the deque.
  91    *
  92    * @returns The shifted value or `undefined` if the deque is empty.
  93    */
  94   public shift (): T | undefined {
  95     if (this.head == null) {
  96       return undefined
  97     }
  98     const head = this.head
  99     this.head = this.head.next
 100     if (this.head == null) {
 101       this.tail = undefined
 102     } else {
 103       this.head.prev = undefined
 104     }
 105     --this.size
 106     return head?.value
 107   }
 108
 109   /**
 110    * Peeks at the first value.
 111    * @returns The first value or `undefined` if the deque is empty.
 112    */
 113   public peekFirst (): T | undefined {
 114     return this.head?.value
 115   }
 116
 117   /**
 118    * Peeks at the last value.
 119    * @returns The last value or `undefined` if the deque is empty.
 120    */
 121   public peekLast (): T | undefined {
 122     return this.tail?.value
 123   }
 124
 125   /**
 126    * Clears the deque.
 127    */
 128   public clear (): void {
 129     this.head = undefined
 130     this.tail = undefined
 131     this.size = 0
 132     this.maxSize = 0
 133   }
 134
 135   /**
 136    * Returns an iterator for the deque.
 137    *
 138    * @returns An iterator for the deque.
 139    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 140    */
 141   [Symbol.iterator] (): Iterator<T> {
 142     let node = this.head
 143     return {
 144       next: () => {
 145         if (node == null) {
 146           return {
 147             value: undefined,
 148             done: true
 149           }
 150         }
 151         const ret = {
 152           value: node.value,
 153           done: false
 154         }
 155         node = node.next as Node<T>
 156         return ret
 157       }
 158     }
 159   }
 160
 161   /**
 162    * Returns an backward iterator for the deque.
 163    *
 164    * @returns An backward iterator for the deque.
 165    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 166    */
 167   backward (): Iterable<T> {
 168     return {
 169       [Symbol.iterator]: (): Iterator<T> => {
 170         let node = this.tail
 171         return {
 172           next: () => {
 173             if (node == null) {
 174               return {
 175                 value: undefined,
 176                 done: true
 177               }
 178             }
 179             const ret = {
 180               value: node.value,
 181               done: false
 182             }
 183             node = node.prev as Node<T>
 184             return ret
 185           }
 186         }
 187       }
 188     }
 189   }
 190
 191   private incrementSize (): number {
 192     ++this.size
 193     if (this.size > this.maxSize) {
 194       this.maxSize = this.size
 195     }
 196     return this.size
 197   }
 198 }