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 queue.
  39    */
  40   public push (data: T): number {
  41     const node = { data, prev: this.tail }
  42     if (this.tail == null) {
  43       this.head = this.tail = node
  44     } else {
  45       this.tail = this.tail.next = node
  46     }
  47     return this.incrementSize()
  48   }
  49
  50   /**
  51    * Prepends data to the deque.
  52    *
  53    * @param data - Data to prepend.
  54    * @returns The new size of the queue.
  55    */
  56   public unshift (data: T): number {
  57     const node = { data, next: this.head }
  58     if (this.head == null) {
  59       this.head = this.tail = node
  60     } else {
  61       this.head = this.head.prev = node
  62     }
  63     return this.incrementSize()
  64   }
  65
  66   /**
  67    * Pops data from the deque.
  68    *
  69    * @returns The popped data or `undefined` if the deque is empty.
  70    */
  71   public pop (): T | undefined {
  72     if (this.head == null) {
  73       return
  74     }
  75     const tail = this.tail
  76     this.tail = this.tail?.prev
  77     if (this.tail == null) {
  78       delete this.head
  79     } else {
  80       delete this.tail.next
  81     }
  82     --this.size
  83     return tail?.data
  84   }
  85
  86   /**
  87    * Shifts data from the deque.
  88    *
  89    * @returns The shifted data or `undefined` if the deque is empty.
  90    */
  91   public shift (): T | undefined {
  92     if (this.head == null) {
  93       return
  94     }
  95     const head = this.head
  96     this.head = this.head.next
  97     if (this.head == null) {
  98       delete this.tail
  99     } else {
 100       delete this.head.prev
 101     }
 102     --this.size
 103     return head.data
 104   }
 105
 106   /**
 107    * Peeks at the first data.
 108    * @returns The first data or `undefined` if the deque is empty.
 109    */
 110   public peekFirst (): T | undefined {
 111     return this.head?.data
 112   }
 113
 114   /**
 115    * Peeks at the last data.
 116    * @returns The last data or `undefined` if the deque is empty.
 117    */
 118   public peekLast (): T | undefined {
 119     return this.tail?.data
 120   }
 121
 122   /**
 123    * Clears the deque.
 124    */
 125   public clear (): void {
 126     delete this.head
 127     delete this.tail
 128     this.size = 0
 129     this.maxSize = 0
 130   }
 131
 132   /**
 133    * Returns an iterator for the deque.
 134    *
 135    * @returns An iterator for the deque.
 136    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 137    */
 138   [Symbol.iterator] (): Iterator<T> {
 139     let node = this.head
 140     return {
 141       next: () => {
 142         if (node == null) {
 143           return {
 144             value: undefined,
 145             done: true
 146           }
 147         }
 148         const ret = {
 149           value: node.data,
 150           done: false
 151         }
 152         node = node.next
 153         return ret
 154       }
 155     }
 156   }
 157
 158   /**
 159    * Returns an backward iterator for the deque.
 160    *
 161    * @returns An backward iterator for the deque.
 162    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 163    */
 164   backward (): Iterable<T> {
 165     return {
 166       [Symbol.iterator]: (): Iterator<T> => {
 167         let node = this.tail
 168         return {
 169           next: () => {
 170             if (node == null) {
 171               return {
 172                 value: undefined,
 173                 done: true
 174               }
 175             }
 176             const ret = {
 177               value: node.data,
 178               done: false
 179             }
 180             node = node.prev
 181             return ret
 182           }
 183         }
 184       }
 185     }
 186   }
 187
 188   private incrementSize (): number {
 189     ++this.size
 190     if (this.size > this.maxSize) {
 191       this.maxSize = this.size
 192     }
 193     return this.size
 194   }
 195 }