src/deque.ts

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