1use std::fmt::Debug;
2
3#[derive(Debug)]
10pub struct History<T> {
11 entries: Vec<T>,
12 forward_entries: Vec<T>,
13 max_entries: usize,
14}
15
16impl<T> History<T> {
17 pub fn new() -> Self {
18 Self {
19 entries: Vec::new(),
20 forward_entries: Vec::new(),
21 max_entries: 1000,
22 }
23 }
24
25 pub fn max_entries(mut self, max_entries: usize) -> Self {
29 self.max_entries = max_entries;
30 self.enforce_max_entries();
31 self
32 }
33
34 pub fn push(&mut self, entry: T) {
36 self.forward_entries.clear();
37 if self.max_entries == 0 {
38 return;
39 }
40 self.entries.push(entry);
41 self.enforce_max_entries();
42 }
43
44 pub fn current(&self) -> Option<&T> {
46 self.entries.last()
47 }
48
49 pub fn replace_current(&mut self, entry: T) {
51 match self.entries.last_mut() {
52 Some(current) => *current = entry,
53 None => self.push(entry),
54 }
55 }
56
57 pub fn remove_current(&mut self) -> Option<T> {
59 self.entries.pop()
60 }
61
62 pub fn can_back(&self) -> bool {
64 self.entries.len() > 1
65 }
66
67 pub fn can_forward(&self) -> bool {
69 !self.forward_entries.is_empty()
70 }
71
72 pub fn back(&mut self) -> Option<T>
74 where
75 T: Clone,
76 {
77 if self.entries.len() <= 1 {
78 return None;
79 }
80 self.forward_entries.push(self.entries.pop().unwrap());
81 self.current().cloned()
82 }
83
84 pub fn forward(&mut self) -> Option<T>
86 where
87 T: Clone,
88 {
89 if self.max_entries == 0 {
90 return None;
91 }
92 let entry = self.forward_entries.pop()?;
93 self.entries.push(entry);
94 self.enforce_max_entries();
95 self.current().cloned()
96 }
97
98 pub fn entries(&self) -> impl DoubleEndedIterator<Item = &T> + ExactSizeIterator {
100 self.entries.iter()
101 }
102
103 pub fn forward_entries(&self) -> impl DoubleEndedIterator<Item = &T> + ExactSizeIterator {
105 self.forward_entries.iter().rev()
106 }
107
108 pub fn retain(&mut self, mut keep: impl FnMut(&T) -> bool) {
110 self.entries.retain(&mut keep);
111 self.forward_entries.retain(&mut keep);
112 }
113
114 pub fn clear(&mut self) {
116 self.entries.clear();
117 self.forward_entries.clear();
118 }
119
120 fn enforce_max_entries(&mut self) {
121 let excess = self.entries.len().saturating_sub(self.max_entries);
122 if excess > 0 {
123 self.entries.drain(..excess);
124 }
125 }
126}
127
128impl<T> Default for History<T> {
129 fn default() -> Self {
130 Self::new()
131 }
132}
133
134#[cfg(test)]
135mod tests {
136 use super::*;
137
138 #[test]
139 fn navigation_moves_between_entries_without_backing_past_the_root() {
140 let mut history = History::new().max_entries(3);
141 history.push(1);
142 history.push(2);
143 history.push(3);
144
145 assert_eq!(history.current(), Some(&3));
146 assert_eq!(history.back(), Some(2));
147 assert_eq!(history.back(), Some(1));
148 assert_eq!(history.back(), None);
149 assert_eq!(history.forward(), Some(2));
150 assert_eq!(history.entries().copied().collect::<Vec<_>>(), [1, 2]);
151 assert_eq!(history.entries().rev().copied().collect::<Vec<_>>(), [2, 1]);
152 assert_eq!(history.forward_entries().copied().collect::<Vec<_>>(), [3]);
153 assert!(history.can_back());
154 assert!(history.can_forward());
155 }
156
157 #[test]
158 fn pushing_after_back_truncates_the_forward_branch() {
159 let mut history = History::new();
160 history.push(1);
161 history.push(2);
162 history.push(3);
163 assert_eq!(history.back(), Some(2));
164
165 history.push(4);
166
167 assert_eq!(history.entries().copied().collect::<Vec<_>>(), [1, 2, 4]);
168 assert!(!history.can_forward());
169 assert_eq!(history.forward(), None);
170 }
171
172 #[test]
173 fn repeated_entries_preserve_every_navigation_step() {
174 let mut history = History::new();
175 history.push(1);
176 history.push(2);
177 history.push(1);
178
179 assert_eq!(history.entries().copied().collect::<Vec<_>>(), [1, 2, 1]);
180 assert_eq!(history.back(), Some(2));
181 assert_eq!(history.back(), Some(1));
182 }
183
184 #[test]
185 fn max_entries_evicts_the_oldest_entry() {
186 let mut history = History::new().max_entries(2);
187 history.push(1);
188 history.push(2);
189 history.push(3);
190
191 assert_eq!(history.entries().copied().collect::<Vec<_>>(), [2, 3]);
192 assert_eq!(history.back(), Some(2));
193 assert_eq!(history.back(), None);
194 }
195
196 #[test]
197 fn lowering_max_entries_truncates_populated_entries_and_caps_forward_restores() {
198 let mut history = History::new();
199 history.push(1);
200 history.push(2);
201 history.push(3);
202 assert_eq!(history.back(), Some(2));
203
204 history = history.max_entries(1);
205
206 assert_eq!(history.entries().copied().collect::<Vec<_>>(), [2]);
207 assert_eq!(history.forward(), Some(3));
208 assert_eq!(history.entries().copied().collect::<Vec<_>>(), [3]);
209 assert_eq!(history.back(), None);
210 }
211
212 #[test]
213 fn zero_max_entries_retains_nothing() {
214 let mut history = History::new().max_entries(0);
215 history.push(1);
216
217 assert_eq!(history.current(), None);
218 assert_eq!(history.entries().len(), 0);
219 assert!(!history.can_back());
220 assert!(!history.can_forward());
221 }
222
223 #[test]
224 fn replace_current_updates_in_place_and_pushes_when_empty() {
225 let mut history = History::new();
226 history.replace_current(1);
227 history.push(2);
228 history.replace_current(3);
229
230 assert_eq!(history.entries().copied().collect::<Vec<_>>(), [1, 3]);
231 }
232
233 #[test]
234 fn remove_current_preserves_forward_entries() {
235 let mut history = History::new();
236 history.push(1);
237 history.push(2);
238 history.push(3);
239 assert_eq!(history.back(), Some(2));
240
241 assert_eq!(history.remove_current(), Some(2));
242
243 assert_eq!(history.current(), Some(&1));
244 assert_eq!(history.forward_entries().copied().collect::<Vec<_>>(), [3]);
245 assert_eq!(history.forward(), Some(3));
246 }
247
248 #[test]
249 fn retain_filters_back_and_forward_entries_without_reordering() {
250 let mut history = History::new();
251 for entry in 1..=8 {
252 history.push(entry);
253 }
254 history.back();
255 history.back();
256 history.back();
257 history.back();
258
259 history.retain(|entry| entry % 2 == 0);
260
261 assert_eq!(history.entries().copied().collect::<Vec<_>>(), [2, 4]);
262 assert_eq!(
263 history.forward_entries().copied().collect::<Vec<_>>(),
264 [6, 8]
265 );
266 assert_eq!(history.forward(), Some(6));
267 assert_eq!(history.forward(), Some(8));
268 }
269
270 #[test]
271 fn clear_removes_back_and_forward_entries() {
272 let mut history = History::new();
273 history.push(1);
274 history.push(2);
275 history.back();
276
277 history.clear();
278
279 assert_eq!(history.current(), None);
280 assert_eq!(history.entries().len(), 0);
281 assert_eq!(history.forward_entries().len(), 0);
282 assert!(!history.can_back());
283 assert!(!history.can_forward());
284 }
285}