src/deque.ts

   1 // Copyright Jerome Benoit. 2023. All Rights Reserved.
   2
   3 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   public pop (): T | undefined {
  69     if (this.head == null) {
  70       return undefined
  71     }
  72     const tail = this.tail
  73     this.tail = (this.tail as Node<T>).prev
  74     if (this.tail == null) {
  75       this.head = undefined
  76     } else {
  77       this.tail.next = undefined
  78     }
  79     --this.size
  80     return tail?.value
  81   }
  82
  83   /**
  84    * Shifts a value from the deque.
  85    *
  86    * @returns The shifted value or `undefined` if the deque is empty.
  87    */
  88   public shift (): T | undefined {
  89     if (this.head == null) {
  90       return undefined
  91     }
  92     const head = this.head
  93     this.head = this.head.next
  94     if (this.head == null) {
  95       this.tail = undefined
  96     } else {
  97       this.head.prev = undefined
  98     }
  99     --this.size
 100     return head?.value
 101   }
 102
 103   /**
 104    * Peeks at the first value.
 105    * @returns The first value or `undefined` if the queue is empty.
 106    */
 107   public peekFirst (): T | undefined {
 108     return this.head?.value
 109   }
 110
 111   /**
 112    * Peeks at the last value.
 113    * @returns The last value or `undefined` if the queue is empty.
 114    */
 115   public peekLast (): T | undefined {
 116     return this.tail?.value
 117   }
 118
 119   /**
 120    * Clears the deque.
 121    */
 122   public clear (): void {
 123     this.head = undefined
 124     this.tail = undefined
 125     this.size = 0
 126     this.maxSize = 0
 127   }
 128
 129   /**
 130    * Returns an iterator for the deque.
 131    *
 132    * @returns An iterator for the deque.
 133    * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
 134    */
 135   [Symbol.iterator] (): Iterator<T> {
 136     let node = this.head
 137     return {
 138       next: () => {
 139         if (node == null) {
 140           return {
 141             value: undefined,
 142             done: true
 143           }
 144         }
 145         const ret = {
 146           value: node.value,
 147           done: false
 148         }
 149         node = node.next as Node<T>
 150         return ret
 151       }
 152     }
 153   }
 154
 155   private incrementSize (): number {
 156     ++this.size
 157     if (this.size > this.maxSize) {
 158       this.maxSize = this.size
 159     }
 160     return this.size
 161   }
 162 }