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