Commit | Line | Data |
---|---|---|
574b351d JB |
1 | // Copyright Jerome Benoit. 2023. All Rights Reserved. |
2 | ||
4bffc062 JB |
3 | /** |
4 | * @internal | |
5 | */ | |
fba4a5e2 | 6 | export class Node<T> { |
574b351d JB |
7 | public value: T |
8 | public next?: Node<T> | |
9 | public prev?: Node<T> | |
10 | ||
11 | public constructor (value: T) { | |
12 | this.value = value | |
13 | } | |
14 | } | |
15 | ||
16 | /** | |
17 | * Deque. | |
18 | * Implemented with a doubly linked list. | |
19 | * | |
20 | * @typeParam T - Type of deque values. | |
4bffc062 | 21 | * @internal |
574b351d JB |
22 | */ |
23 | export class Deque<T> { | |
24 | private head?: Node<T> | |
25 | private tail?: Node<T> | |
26 | /** The size of the deque. */ | |
27 | public size!: number | |
28 | /** The maximum size of the deque. */ | |
29 | public maxSize!: number | |
30 | ||
31 | public constructor () { | |
32 | this.clear() | |
33 | } | |
34 | ||
35 | /** | |
36 | * Appends a value to the deque. | |
37 | * | |
38 | * @param value - Value to append. | |
39 | * @returns The new size of the queue. | |
40 | */ | |
41 | public push (value: T): number { | |
42 | const node = new Node(value) | |
43 | if (this.tail == null) { | |
44 | this.head = this.tail = node | |
45 | } else { | |
46 | node.prev = this.tail | |
47 | this.tail = this.tail.next = node | |
48 | } | |
49 | return this.incrementSize() | |
50 | } | |
51 | ||
52 | /** | |
53 | * Prepends a value to the deque. | |
54 | * | |
55 | * @param value - Value to prepend. | |
56 | * @returns The new size of the queue. | |
57 | */ | |
58 | public unshift (value: T): number { | |
59 | const node = new Node(value) | |
60 | if (this.head == null) { | |
61 | this.head = this.tail = node | |
62 | } else { | |
63 | node.next = this.head | |
64 | this.head = this.head.prev = node | |
65 | } | |
66 | return this.incrementSize() | |
67 | } | |
68 | ||
69 | /** | |
70 | * Pops a value from the deque. | |
5e7eca0e JB |
71 | * |
72 | * @returns The popped value or `undefined` if the deque is empty. | |
574b351d JB |
73 | */ |
74 | public pop (): T | undefined { | |
75 | if (this.head == null) { | |
76 | return undefined | |
77 | } | |
78 | const tail = this.tail | |
79 | this.tail = (this.tail as Node<T>).prev | |
80 | if (this.tail == null) { | |
81 | this.head = undefined | |
82 | } else { | |
83 | this.tail.next = undefined | |
84 | } | |
85 | --this.size | |
86 | return tail?.value | |
87 | } | |
88 | ||
89 | /** | |
90 | * Shifts a value from the deque. | |
91 | * | |
92 | * @returns The shifted value or `undefined` if the deque is empty. | |
93 | */ | |
94 | public shift (): T | undefined { | |
95 | if (this.head == null) { | |
96 | return undefined | |
97 | } | |
98 | const head = this.head | |
99 | this.head = this.head.next | |
100 | if (this.head == null) { | |
101 | this.tail = undefined | |
102 | } else { | |
103 | this.head.prev = undefined | |
104 | } | |
105 | --this.size | |
106 | return head?.value | |
107 | } | |
108 | ||
109 | /** | |
110 | * Peeks at the first value. | |
5e7eca0e | 111 | * @returns The first value or `undefined` if the deque is empty. |
574b351d JB |
112 | */ |
113 | public peekFirst (): T | undefined { | |
114 | return this.head?.value | |
115 | } | |
116 | ||
117 | /** | |
118 | * Peeks at the last value. | |
5e7eca0e | 119 | * @returns The last value or `undefined` if the deque is empty. |
574b351d JB |
120 | */ |
121 | public peekLast (): T | undefined { | |
122 | return this.tail?.value | |
123 | } | |
124 | ||
125 | /** | |
126 | * Clears the deque. | |
127 | */ | |
128 | public clear (): void { | |
129 | this.head = undefined | |
130 | this.tail = undefined | |
131 | this.size = 0 | |
132 | this.maxSize = 0 | |
133 | } | |
134 | ||
135 | /** | |
136 | * Returns an iterator for the deque. | |
137 | * | |
138 | * @returns An iterator for the deque. | |
139 | * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols | |
140 | */ | |
141 | [Symbol.iterator] (): Iterator<T> { | |
142 | let node = this.head | |
143 | return { | |
144 | next: () => { | |
145 | if (node == null) { | |
146 | return { | |
147 | value: undefined, | |
148 | done: true | |
149 | } | |
150 | } | |
151 | const ret = { | |
152 | value: node.value, | |
153 | done: false | |
154 | } | |
155 | node = node.next as Node<T> | |
156 | return ret | |
157 | } | |
158 | } | |
159 | } | |
160 | ||
4de3d785 JB |
161 | /** |
162 | * Returns an backward iterator for the deque. | |
163 | * | |
164 | * @returns An backward iterator for the deque. | |
165 | * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols | |
166 | */ | |
31a7af93 JB |
167 | backward (): Iterable<T> { |
168 | return { | |
169 | [Symbol.iterator]: (): Iterator<T> => { | |
170 | let node = this.tail | |
171 | return { | |
172 | next: () => { | |
173 | if (node == null) { | |
174 | return { | |
175 | value: undefined, | |
176 | done: true | |
177 | } | |
178 | } | |
179 | const ret = { | |
180 | value: node.value, | |
181 | done: false | |
182 | } | |
183 | node = node.prev as Node<T> | |
184 | return ret | |
185 | } | |
186 | } | |
187 | } | |
188 | } | |
189 | } | |
190 | ||
574b351d JB |
191 | private incrementSize (): number { |
192 | ++this.size | |
193 | if (this.size > this.maxSize) { | |
194 | this.maxSize = this.size | |
195 | } | |
196 | return this.size | |
197 | } | |
198 | } |