src/deque.ts

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