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. | |
67 | */ | |
68 | public pop (): T | undefined { | |
69 | if (this.head == null) { | |
70 | return undefined | |
71 | } | |
72 | const tail = this.tail | |
73 | this.tail = (this.tail as Node<T>).prev | |
74 | if (this.tail == null) { | |
75 | this.head = undefined | |
76 | } else { | |
77 | this.tail.next = undefined | |
78 | } | |
79 | --this.size | |
80 | return tail?.value | |
81 | } | |
82 | ||
83 | /** | |
84 | * Shifts a value from the deque. | |
85 | * | |
86 | * @returns The shifted value or `undefined` if the deque is empty. | |
87 | */ | |
88 | public shift (): T | undefined { | |
89 | if (this.head == null) { | |
90 | return undefined | |
91 | } | |
92 | const head = this.head | |
93 | this.head = this.head.next | |
94 | if (this.head == null) { | |
95 | this.tail = undefined | |
96 | } else { | |
97 | this.head.prev = undefined | |
98 | } | |
99 | --this.size | |
100 | return head?.value | |
101 | } | |
102 | ||
103 | /** | |
104 | * Peeks at the first value. | |
105 | * @returns The first value or `undefined` if the queue is empty. | |
106 | */ | |
107 | public peekFirst (): T | undefined { | |
108 | return this.head?.value | |
109 | } | |
110 | ||
111 | /** | |
112 | * Peeks at the last value. | |
113 | * @returns The last value or `undefined` if the queue is empty. | |
114 | */ | |
115 | public peekLast (): T | undefined { | |
116 | return this.tail?.value | |
117 | } | |
118 | ||
119 | /** | |
120 | * Clears the deque. | |
121 | */ | |
122 | public clear (): void { | |
123 | this.head = undefined | |
124 | this.tail = undefined | |
125 | this.size = 0 | |
126 | this.maxSize = 0 | |
127 | } | |
128 | ||
129 | /** | |
130 | * Returns an iterator for the deque. | |
131 | * | |
132 | * @returns An iterator for the deque. | |
133 | * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols | |
134 | */ | |
135 | [Symbol.iterator] (): Iterator<T> { | |
136 | let node = this.head | |
137 | return { | |
138 | next: () => { | |
139 | if (node == null) { | |
140 | return { | |
141 | value: undefined, | |
142 | done: true | |
143 | } | |
144 | } | |
145 | const ret = { | |
146 | value: node.value, | |
147 | done: false | |
148 | } | |
149 | node = node.next as Node<T> | |
150 | return ret | |
151 | } | |
152 | } | |
153 | } | |
154 | ||
155 | private incrementSize (): number { | |
156 | ++this.size | |
157 | if (this.size > this.maxSize) { | |
158 | this.maxSize = this.size | |
159 | } | |
160 | return this.size | |
161 | } | |
162 | } |