src/deque.ts

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