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