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