Commit | Line | Data |
---|---|---|
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 |
9 | export 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 | */ |
22 | export 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 | } |