Merge dependabot/npm_and_yarn/examples/typescript/http-server-pool/express-worker_thr...
[poolifier.git] / src / deque.ts
CommitLineData
b97b9dc2 1// Copyright Jerome Benoit. 2023-2024. All Rights Reserved.
574b351d 2
4bffc062 3/**
b1577cd9 4 * Linked list node interface.
4843c5e8 5 *
4335b463 6 * @typeParam T - Type of linked list node data.
4bffc062
JB
7 * @internal
8 */
b1577cd9
JB
9export interface ILinkedListNode<T> {
10 data: T
11 next?: ILinkedListNode<T>
12 prev?: ILinkedListNode<T>
574b351d
JB
13}
14
15/**
16 * Deque.
17 * Implemented with a doubly linked list.
18 *
4843c5e8 19 * @typeParam T - Type of deque data.
4bffc062 20 * @internal
574b351d
JB
21 */
22export class Deque<T> {
b1577cd9
JB
23 private head?: ILinkedListNode<T>
24 private tail?: ILinkedListNode<T>
574b351d
JB
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 /**
4843c5e8 35 * Appends data to the deque.
574b351d 36 *
4843c5e8 37 * @param data - Data to append.
3b8a84f6 38 * @returns The new size of the deque.
574b351d 39 */
4843c5e8 40 public push (data: T): number {
938ced1a 41 const node: ILinkedListNode<T> = { data }
574b351d
JB
42 if (this.tail == null) {
43 this.head = this.tail = node
44 } else {
938ced1a 45 node.prev = this.tail
574b351d
JB
46 this.tail = this.tail.next = node
47 }
48 return this.incrementSize()
49 }
50
51 /**
4843c5e8 52 * Prepends data to the deque.
574b351d 53 *
4843c5e8 54 * @param data - Data to prepend.
3b8a84f6 55 * @returns The new size of the deque.
574b351d 56 */
4843c5e8 57 public unshift (data: T): number {
938ced1a 58 const node: ILinkedListNode<T> = { data }
574b351d
JB
59 if (this.head == null) {
60 this.head = this.tail = node
61 } else {
938ced1a 62 node.next = this.head
574b351d
JB
63 this.head = this.head.prev = node
64 }
65 return this.incrementSize()
66 }
67
68 /**
4843c5e8 69 * Pops data from the deque.
5e7eca0e 70 *
4843c5e8 71 * @returns The popped data or `undefined` if the deque is empty.
574b351d
JB
72 */
73 public pop (): T | undefined {
74 if (this.head == null) {
41072404 75 return
574b351d
JB
76 }
77 const tail = this.tail
c63a35a0 78 this.tail = this.tail?.prev
574b351d 79 if (this.tail == null) {
41072404 80 delete this.head
574b351d 81 } else {
41072404 82 delete this.tail.next
574b351d
JB
83 }
84 --this.size
4843c5e8 85 return tail?.data
574b351d
JB
86 }
87
88 /**
4843c5e8 89 * Shifts data from the deque.
574b351d 90 *
4843c5e8 91 * @returns The shifted data or `undefined` if the deque is empty.
574b351d
JB
92 */
93 public shift (): T | undefined {
94 if (this.head == null) {
41072404 95 return
574b351d
JB
96 }
97 const head = this.head
98 this.head = this.head.next
99 if (this.head == null) {
41072404 100 delete this.tail
574b351d 101 } else {
41072404 102 delete this.head.prev
574b351d
JB
103 }
104 --this.size
c63a35a0 105 return head.data
574b351d
JB
106 }
107
108 /**
4843c5e8
JB
109 * Peeks at the first data.
110 * @returns The first data or `undefined` if the deque is empty.
574b351d
JB
111 */
112 public peekFirst (): T | undefined {
4843c5e8 113 return this.head?.data
574b351d
JB
114 }
115
116 /**
4843c5e8
JB
117 * Peeks at the last data.
118 * @returns The last data or `undefined` if the deque is empty.
574b351d
JB
119 */
120 public peekLast (): T | undefined {
4843c5e8 121 return this.tail?.data
574b351d
JB
122 }
123
124 /**
125 * Clears the deque.
126 */
127 public clear (): void {
41072404
JB
128 delete this.head
129 delete this.tail
574b351d
JB
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 = {
4843c5e8 151 value: node.data,
574b351d
JB
152 done: false
153 }
c63a35a0 154 node = node.next
574b351d
JB
155 return ret
156 }
157 }
158 }
159
4de3d785
JB
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 */
31a7af93
JB
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 = {
4843c5e8 179 value: node.data,
31a7af93
JB
180 done: false
181 }
c63a35a0 182 node = node.prev
31a7af93
JB
183 return ret
184 }
185 }
186 }
187 }
188 }
189
574b351d
JB
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}