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. |
574b351d JB |
38 | * @returns The new size of the queue. |
39 | */ | |
4843c5e8 | 40 | public push (data: T): number { |
b1577cd9 | 41 | const node = { data, prev: this.tail } |
574b351d JB |
42 | if (this.tail == null) { |
43 | this.head = this.tail = node | |
44 | } else { | |
574b351d JB |
45 | this.tail = this.tail.next = node |
46 | } | |
47 | return this.incrementSize() | |
48 | } | |
49 | ||
50 | /** | |
4843c5e8 | 51 | * Prepends data to the deque. |
574b351d | 52 | * |
4843c5e8 | 53 | * @param data - Data to prepend. |
574b351d JB |
54 | * @returns The new size of the queue. |
55 | */ | |
4843c5e8 | 56 | public unshift (data: T): number { |
b1577cd9 | 57 | const node = { data, next: this.head } |
574b351d JB |
58 | if (this.head == null) { |
59 | this.head = this.tail = node | |
60 | } else { | |
574b351d JB |
61 | this.head = this.head.prev = node |
62 | } | |
63 | return this.incrementSize() | |
64 | } | |
65 | ||
66 | /** | |
4843c5e8 | 67 | * Pops data from the deque. |
5e7eca0e | 68 | * |
4843c5e8 | 69 | * @returns The popped data or `undefined` if the deque is empty. |
574b351d JB |
70 | */ |
71 | public pop (): T | undefined { | |
72 | if (this.head == null) { | |
41072404 | 73 | return |
574b351d JB |
74 | } |
75 | const tail = this.tail | |
c63a35a0 | 76 | this.tail = this.tail?.prev |
574b351d | 77 | if (this.tail == null) { |
41072404 | 78 | delete this.head |
574b351d | 79 | } else { |
41072404 | 80 | delete this.tail.next |
574b351d JB |
81 | } |
82 | --this.size | |
4843c5e8 | 83 | return tail?.data |
574b351d JB |
84 | } |
85 | ||
86 | /** | |
4843c5e8 | 87 | * Shifts data from the deque. |
574b351d | 88 | * |
4843c5e8 | 89 | * @returns The shifted data or `undefined` if the deque is empty. |
574b351d JB |
90 | */ |
91 | public shift (): T | undefined { | |
92 | if (this.head == null) { | |
41072404 | 93 | return |
574b351d JB |
94 | } |
95 | const head = this.head | |
96 | this.head = this.head.next | |
97 | if (this.head == null) { | |
41072404 | 98 | delete this.tail |
574b351d | 99 | } else { |
41072404 | 100 | delete this.head.prev |
574b351d JB |
101 | } |
102 | --this.size | |
c63a35a0 | 103 | return head.data |
574b351d JB |
104 | } |
105 | ||
106 | /** | |
4843c5e8 JB |
107 | * Peeks at the first data. |
108 | * @returns The first data or `undefined` if the deque is empty. | |
574b351d JB |
109 | */ |
110 | public peekFirst (): T | undefined { | |
4843c5e8 | 111 | return this.head?.data |
574b351d JB |
112 | } |
113 | ||
114 | /** | |
4843c5e8 JB |
115 | * Peeks at the last data. |
116 | * @returns The last data or `undefined` if the deque is empty. | |
574b351d JB |
117 | */ |
118 | public peekLast (): T | undefined { | |
4843c5e8 | 119 | return this.tail?.data |
574b351d JB |
120 | } |
121 | ||
122 | /** | |
123 | * Clears the deque. | |
124 | */ | |
125 | public clear (): void { | |
41072404 JB |
126 | delete this.head |
127 | delete this.tail | |
574b351d JB |
128 | this.size = 0 |
129 | this.maxSize = 0 | |
130 | } | |
131 | ||
132 | /** | |
133 | * Returns an iterator for the deque. | |
134 | * | |
135 | * @returns An iterator for the deque. | |
136 | * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols | |
137 | */ | |
138 | [Symbol.iterator] (): Iterator<T> { | |
139 | let node = this.head | |
140 | return { | |
141 | next: () => { | |
142 | if (node == null) { | |
143 | return { | |
144 | value: undefined, | |
145 | done: true | |
146 | } | |
147 | } | |
148 | const ret = { | |
4843c5e8 | 149 | value: node.data, |
574b351d JB |
150 | done: false |
151 | } | |
c63a35a0 | 152 | node = node.next |
574b351d JB |
153 | return ret |
154 | } | |
155 | } | |
156 | } | |
157 | ||
4de3d785 JB |
158 | /** |
159 | * Returns an backward iterator for the deque. | |
160 | * | |
161 | * @returns An backward iterator for the deque. | |
162 | * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols | |
163 | */ | |
31a7af93 JB |
164 | backward (): Iterable<T> { |
165 | return { | |
166 | [Symbol.iterator]: (): Iterator<T> => { | |
167 | let node = this.tail | |
168 | return { | |
169 | next: () => { | |
170 | if (node == null) { | |
171 | return { | |
172 | value: undefined, | |
173 | done: true | |
174 | } | |
175 | } | |
176 | const ret = { | |
4843c5e8 | 177 | value: node.data, |
31a7af93 JB |
178 | done: false |
179 | } | |
c63a35a0 | 180 | node = node.prev |
31a7af93 JB |
181 | return ret |
182 | } | |
183 | } | |
184 | } | |
185 | } | |
186 | } | |
187 | ||
574b351d JB |
188 | private incrementSize (): number { |
189 | ++this.size | |
190 | if (this.size > this.maxSize) { | |
191 | this.maxSize = this.size | |
192 | } | |
193 | return this.size | |
194 | } | |
195 | } |