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     this.tail = this.tail?.prev
  83     if (this.tail == null) {
  84       delete this.head
  85     } else {
  86       delete this.tail.next
  87     }
  88     --this.size
  89     return tail?.data
  90   }
  91
  92   /**
  93    * Shifts data from the deque.
  94    *
  95    * @returns The shifted data or `undefined` if the deque is empty.
  96    */
  97   public shift (): T | undefined {
  98     if (this.head == null) {
  99       return
 100     }
 101     const head = this.head
 102     this.head = this.head.next
 103     if (this.head == null) {
 104       delete this.tail
 105     } else {
 106       delete this.head.prev
 107     }
 108     --this.size
 109     return head.data
 110   }
 111
 112   /**
 113    * Peeks at the first data.
 114    * @returns The first data or `undefined` if the deque is empty.
 115    */
 116   public peekFirst (): T | undefined {
 117     return this.head?.data
 118   }
 119
 120   /**
 121    * Peeks at the last data.
 122    * @returns The last data or `undefined` if the deque is empty.
 123    */
 124   public peekLast (): T | undefined {
 125     return this.tail?.data
 126   }
 127
 128   /**
 129    * Clears the deque.
 130    */
 131   public clear (): void {
 132     delete this.head
 133     delete this.tail
 134     this.size = 0
 135     this.maxSize = 0
 136   }
 137
 138   /**
 139    * Returns an iterator for the deque.
 140    *
 141    * @returns An iterator for the deque.
 142    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 143    */
 144   [Symbol.iterator] (): Iterator<T> {
 145     let node = this.head
 146     return {
 147       next: () => {
 148         if (node == null) {
 149           return {
 150             value: undefined,
 151             done: true
 152           }
 153         }
 154         const ret = {
 155           value: node.data,
 156           done: false
 157         }
 158         node = node.next
 159         return ret
 160       }
 161     }
 162   }
 163
 164   /**
 165    * Returns an backward iterator for the deque.
 166    *
 167    * @returns An backward iterator for the deque.
 168    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 169    */
 170   backward (): Iterable<T> {
 171     return {
 172       [Symbol.iterator]: (): Iterator<T> => {
 173         let node = this.tail
 174         return {
 175           next: () => {
 176             if (node == null) {
 177               return {
 178                 value: undefined,
 179                 done: true
 180               }
 181             }
 182             const ret = {
 183               value: node.data,
 184               done: false
 185             }
 186             node = node.prev
 187             return ret
 188           }
 189         }
 190       }
 191     }
 192   }
 193
 194   private incrementSize (): number {
 195     ++this.size
 196     if (this.size > this.maxSize) {
 197       this.maxSize = this.size
 198     }
 199     return this.size
 200   }
 201 }