refactor: cleanup package.json
[poolifier.git] / src / deque.ts
1 // Copyright Jerome Benoit. 2023. All Rights Reserved.
2
3 /**
4 * Node.
5 *
6 * @typeParam T - Type of node data.
7 * @internal
8 */
9 export 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 */
26 export 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 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
83 this.tail = this.tail!.prev
84 if (this.tail == null) {
85 delete this.head
86 } else {
87 delete this.tail.next
88 }
89 --this.size
90 return tail?.data
91 }
92
93 /**
94 * Shifts data from the deque.
95 *
96 * @returns The shifted data or `undefined` if the deque is empty.
97 */
98 public shift (): T | undefined {
99 if (this.head == null) {
100 return
101 }
102 const head = this.head
103 this.head = this.head.next
104 if (this.head == null) {
105 delete this.tail
106 } else {
107 delete this.head.prev
108 }
109 --this.size
110 return head?.data
111 }
112
113 /**
114 * Peeks at the first data.
115 * @returns The first data or `undefined` if the deque is empty.
116 */
117 public peekFirst (): T | undefined {
118 return this.head?.data
119 }
120
121 /**
122 * Peeks at the last data.
123 * @returns The last data or `undefined` if the deque is empty.
124 */
125 public peekLast (): T | undefined {
126 return this.tail?.data
127 }
128
129 /**
130 * Clears the deque.
131 */
132 public clear (): void {
133 delete this.head
134 delete this.tail
135 this.size = 0
136 this.maxSize = 0
137 }
138
139 /**
140 * Returns an iterator for the deque.
141 *
142 * @returns An iterator for the deque.
143 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
144 */
145 [Symbol.iterator] (): Iterator<T> {
146 let node = this.head
147 return {
148 next: () => {
149 if (node == null) {
150 return {
151 value: undefined,
152 done: true
153 }
154 }
155 const ret = {
156 value: node.data,
157 done: false
158 }
159 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
160 node = node.next!
161 return ret
162 }
163 }
164 }
165
166 /**
167 * Returns an backward iterator for the deque.
168 *
169 * @returns An backward iterator for the deque.
170 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
171 */
172 backward (): Iterable<T> {
173 return {
174 [Symbol.iterator]: (): Iterator<T> => {
175 let node = this.tail
176 return {
177 next: () => {
178 if (node == null) {
179 return {
180 value: undefined,
181 done: true
182 }
183 }
184 const ret = {
185 value: node.data,
186 done: false
187 }
188 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
189 node = node.prev!
190 return ret
191 }
192 }
193 }
194 }
195 }
196
197 private incrementSize (): number {
198 ++this.size
199 if (this.size > this.maxSize) {
200 this.maxSize = this.size
201 }
202 return this.size
203 }
204 }