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