build(deps-dev): bump @types/node
[poolifier.git] / src / deque.ts
CommitLineData
574b351d
JB
1// Copyright Jerome Benoit. 2023. All Rights Reserved.
2
4bffc062 3/**
4843c5e8
JB
4 * Node.
5 *
6 * @typeParam T - Type of node data.
4bffc062
JB
7 * @internal
8 */
fba4a5e2 9export class Node<T> {
4843c5e8 10 public data: T
574b351d
JB
11 public next?: Node<T>
12 public prev?: Node<T>
13
4843c5e8
JB
14 public constructor (data: T) {
15 this.data = data
574b351d
JB
16 }
17}
18
19/**
20 * Deque.
21 * Implemented with a doubly linked list.
22 *
4843c5e8 23 * @typeParam T - Type of deque data.
4bffc062 24 * @internal
574b351d
JB
25 */
26export 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 /**
4843c5e8 39 * Appends data to the deque.
574b351d 40 *
4843c5e8 41 * @param data - Data to append.
574b351d
JB
42 * @returns The new size of the queue.
43 */
4843c5e8
JB
44 public push (data: T): number {
45 const node = new Node(data)
574b351d
JB
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 /**
4843c5e8 56 * Prepends data to the deque.
574b351d 57 *
4843c5e8 58 * @param data - Data to prepend.
574b351d
JB
59 * @returns The new size of the queue.
60 */
4843c5e8
JB
61 public unshift (data: T): number {
62 const node = new Node(data)
574b351d
JB
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 /**
4843c5e8 73 * Pops data from the deque.
5e7eca0e 74 *
4843c5e8 75 * @returns The popped data or `undefined` if the deque is empty.
574b351d
JB
76 */
77 public pop (): T | undefined {
78 if (this.head == null) {
41072404 79 return
574b351d
JB
80 }
81 const tail = this.tail
c63a35a0 82 this.tail = this.tail?.prev
574b351d 83 if (this.tail == null) {
41072404 84 delete this.head
574b351d 85 } else {
41072404 86 delete this.tail.next
574b351d
JB
87 }
88 --this.size
4843c5e8 89 return tail?.data
574b351d
JB
90 }
91
92 /**
4843c5e8 93 * Shifts data from the deque.
574b351d 94 *
4843c5e8 95 * @returns The shifted data or `undefined` if the deque is empty.
574b351d
JB
96 */
97 public shift (): T | undefined {
98 if (this.head == null) {
41072404 99 return
574b351d
JB
100 }
101 const head = this.head
102 this.head = this.head.next
103 if (this.head == null) {
41072404 104 delete this.tail
574b351d 105 } else {
41072404 106 delete this.head.prev
574b351d
JB
107 }
108 --this.size
c63a35a0 109 return head.data
574b351d
JB
110 }
111
112 /**
4843c5e8
JB
113 * Peeks at the first data.
114 * @returns The first data or `undefined` if the deque is empty.
574b351d
JB
115 */
116 public peekFirst (): T | undefined {
4843c5e8 117 return this.head?.data
574b351d
JB
118 }
119
120 /**
4843c5e8
JB
121 * Peeks at the last data.
122 * @returns The last data or `undefined` if the deque is empty.
574b351d
JB
123 */
124 public peekLast (): T | undefined {
4843c5e8 125 return this.tail?.data
574b351d
JB
126 }
127
128 /**
129 * Clears the deque.
130 */
131 public clear (): void {
41072404
JB
132 delete this.head
133 delete this.tail
574b351d
JB
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 = {
4843c5e8 155 value: node.data,
574b351d
JB
156 done: false
157 }
c63a35a0 158 node = node.next
574b351d
JB
159 return ret
160 }
161 }
162 }
163
4de3d785
JB
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 */
31a7af93
JB
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 = {
4843c5e8 183 value: node.data,
31a7af93
JB
184 done: false
185 }
c63a35a0 186 node = node.prev
31a7af93
JB
187 return ret
188 }
189 }
190 }
191 }
192 }
193
574b351d
JB
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}