refactor: cleanup package.json
[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
67f3f2d6
JB
82 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
83 this.tail = this.tail!.prev
574b351d 84 if (this.tail == null) {
41072404 85 delete this.head
574b351d 86 } else {
41072404 87 delete this.tail.next
574b351d
JB
88 }
89 --this.size
4843c5e8 90 return tail?.data
574b351d
JB
91 }
92
93 /**
4843c5e8 94 * Shifts data from the deque.
574b351d 95 *
4843c5e8 96 * @returns The shifted data or `undefined` if the deque is empty.
574b351d
JB
97 */
98 public shift (): T | undefined {
99 if (this.head == null) {
41072404 100 return
574b351d
JB
101 }
102 const head = this.head
103 this.head = this.head.next
104 if (this.head == null) {
41072404 105 delete this.tail
574b351d 106 } else {
41072404 107 delete this.head.prev
574b351d
JB
108 }
109 --this.size
4843c5e8 110 return head?.data
574b351d
JB
111 }
112
113 /**
4843c5e8
JB
114 * Peeks at the first data.
115 * @returns The first data or `undefined` if the deque is empty.
574b351d
JB
116 */
117 public peekFirst (): T | undefined {
4843c5e8 118 return this.head?.data
574b351d
JB
119 }
120
121 /**
4843c5e8
JB
122 * Peeks at the last data.
123 * @returns The last data or `undefined` if the deque is empty.
574b351d
JB
124 */
125 public peekLast (): T | undefined {
4843c5e8 126 return this.tail?.data
574b351d
JB
127 }
128
129 /**
130 * Clears the deque.
131 */
132 public clear (): void {
41072404
JB
133 delete this.head
134 delete this.tail
574b351d
JB
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 = {
4843c5e8 156 value: node.data,
574b351d
JB
157 done: false
158 }
67f3f2d6
JB
159 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
160 node = node.next!
574b351d
JB
161 return ret
162 }
163 }
164 }
165
4de3d785
JB
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 */
31a7af93
JB
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 = {
4843c5e8 185 value: node.data,
31a7af93
JB
186 done: false
187 }
67f3f2d6
JB
188 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
189 node = node.prev!
31a7af93
JB
190 return ret
191 }
192 }
193 }
194 }
195 }
196
574b351d
JB
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}