toolbox_rs/lru.rs
1use crate::linked_list::{LinkedList, ListCursor};
2use std::{collections::HashMap, fmt::Debug, hash::Hash};
3
4/// A simple LRU (Least Recently Used) cache implementation with fixed capacity.
5///
6/// This implementation uses a combination of a linked list for maintaining access order
7/// and a hash map for O(1) lookups. The cache has a fixed capacity and automatically
8/// evicts the least recently used items when full.
9///
10/// # Type Parameters
11///
12/// * `Key`: The type of keys used in the cache. Must implement `Copy`, `Debug`, `Eq`, and `Hash`.
13/// * `Value`: The type of values stored in the cache.
14///
15/// # Examples
16///
17/// ```
18/// use toolbox_rs::lru::LRU;
19///
20/// // Create a new LRU cache with capacity 2
21/// let mut cache = LRU::new_with_capacity(2);
22///
23/// // Add some items
24/// cache.push(&1, "one");
25/// cache.push(&2, "two");
26///
27/// assert_eq!(cache.get(&1), Some(&"one"));
28/// assert_eq!(cache.len(), 2);
29///
30/// // Adding another item will evict the least recently used item (2)
31/// cache.push(&3, "three");
32/// assert!(!cache.contains(&2));
33/// assert!(cache.contains(&1));
34/// assert!(cache.contains(&3));
35/// ```
36pub struct LRU<Key: Copy + Debug + Eq + Hash, Value> {
37 lru_list: LinkedList<(Key, Value)>,
38 access_map: HashMap<Key, ListCursor<(Key, Value)>>,
39 capacity: usize,
40}
41
42impl<Key: Copy + Debug + Eq + Hash, Value> LRU<Key, Value> {
43 /// Creates a new LRU cache with the specified capacity.
44 ///
45 /// # Arguments
46 ///
47 /// * `capacity` - The maximum number of key-value pairs the cache can hold
48 ///
49 /// # Panics
50 ///
51 /// Panics in debug mode if capacity is 0.
52 ///
53 /// # Examples
54 ///
55 /// ```
56 /// use toolbox_rs::lru::LRU;
57 ///
58 /// let cache: LRU<i32, &str> = LRU::new_with_capacity(10);
59 /// assert_eq!(cache.capacity(), 10);
60 /// assert!(cache.is_empty());
61 /// ```
62 pub fn new_with_capacity(capacity: usize) -> Self {
63 debug_assert!(capacity > 0);
64 let storage = LinkedList::new();
65 let indices = HashMap::with_capacity(capacity);
66 LRU {
67 lru_list: storage,
68 access_map: indices,
69 capacity,
70 }
71 }
72
73 /// Inserts a key-value pair into the cache.
74 ///
75 /// If the cache is at capacity, the least recently used item will be evicted.
76 /// If the key already exists, the value will be updated and the entry will
77 /// become the most recently used.
78 ///
79 /// # Arguments
80 ///
81 /// * `key` - The key to insert
82 /// * `value` - The value to associate with the key
83 ///
84 /// # Examples
85 ///
86 /// ```
87 /// use toolbox_rs::lru::LRU;
88 ///
89 /// let mut cache = LRU::new_with_capacity(2);
90 /// cache.push(&1, "one");
91 /// cache.push(&2, "two");
92 /// cache.push(&3, "three"); // This will evict key 1
93 ///
94 /// assert!(!cache.contains(&1));
95 /// assert!(cache.contains(&2));
96 /// assert!(cache.contains(&3));
97 /// ```
98 pub fn push(&mut self, key: &Key, value: Value) {
99 debug_assert!(self.lru_list.len() <= self.capacity);
100
101 if let Some(handle) = self.access_map.get(key) {
102 // Key exists - move to front and update value
103 let handle = *handle;
104 self.lru_list.move_to_front(&handle);
105 // Update the value using a mutable reference
106 let front = self.lru_list.get_front_mut();
107 *front = (*key, value);
108 return;
109 }
110
111 // Key doesn't exist - handle capacity and insert new entry
112 if self.access_map.len() == self.capacity {
113 // evict least recently used element
114 debug_assert!(!self.access_map.is_empty());
115 if let Some((evicted_key, _)) = self.lru_list.pop_back() {
116 self.access_map.remove(&evicted_key);
117 }
118 }
119
120 // Insert new entry
121 let handle = self.lru_list.push_front((*key, value));
122 self.access_map.insert(*key, handle);
123 }
124
125 /// Returns true if the cache contains the specified key.
126 ///
127 /// This operation does not affect the order of items in the cache.
128 ///
129 /// # Arguments
130 ///
131 /// * `key` - The key to look up
132 ///
133 /// # Examples
134 ///
135 /// ```
136 /// use toolbox_rs::lru::LRU;
137 ///
138 /// let mut cache = LRU::new_with_capacity(1);
139 /// cache.push(&1, "one");
140 /// assert!(cache.contains(&1));
141 /// assert!(!cache.contains(&2));
142 /// ```
143 pub fn contains(&self, key: &Key) -> bool {
144 self.access_map.contains_key(key)
145 }
146
147 /// Gets the value associated with the key and marks it as most recently used.
148 ///
149 /// # Arguments
150 ///
151 /// * `key` - The key to look up
152 ///
153 /// # Returns
154 ///
155 /// Returns `Some(&Value)` if the key exists, or `None` if it doesn't.
156 ///
157 /// # Examples
158 ///
159 /// ```
160 /// use toolbox_rs::lru::LRU;
161 ///
162 /// let mut cache = LRU::new_with_capacity(2);
163 /// cache.push(&1, "one");
164 /// cache.push(&2, "two");
165 ///
166 /// assert_eq!(cache.get(&1), Some(&"one"));
167 /// cache.push(&3, "three"); // This will evict key 2, not 1
168 /// assert!(cache.contains(&1)); // 1 was most recently used
169 /// assert!(!cache.contains(&2)); // 2 was evicted
170 /// ```
171 pub fn get(&mut self, key: &Key) -> Option<&Value> {
172 if let Some(handle) = self.access_map.get(key) {
173 self.lru_list.move_to_front(handle);
174 return Some(&self.lru_list.get_front().1);
175 }
176 None
177 }
178
179 /// Returns a reference to the most recently used (front) item in the cache.
180 ///
181 /// # Returns
182 ///
183 /// Returns `Option<(&Key, &Value)>` - `Some` with references to the key and value if the cache
184 /// is not empty, or `None` if the cache is empty.
185 ///
186 /// # Examples
187 ///
188 /// ```
189 /// use toolbox_rs::lru::LRU;
190 ///
191 /// let mut cache = LRU::new_with_capacity(2);
192 /// assert_eq!(cache.get_front(), None);
193 ///
194 /// cache.push(&1, "one");
195 /// cache.push(&2, "two");
196 /// assert_eq!(cache.get_front(), Some((&2, &"two")));
197 /// ```
198 pub fn get_front(&self) -> Option<(&Key, &Value)> {
199 if self.is_empty() {
200 None
201 } else {
202 let front = self.lru_list.get_front();
203 Some((&front.0, &front.1))
204 }
205 }
206
207 /// Returns a mutable reference to the most recently used (front) item in the cache.
208 ///
209 /// # Returns
210 ///
211 /// Returns `Option<(&Key, &mut Value)>` - `Some` with a reference to the key and mutable reference
212 /// to the value if the cache is not empty, or `None` if the cache is empty.
213 ///
214 /// # Examples
215 ///
216 /// ```
217 /// use toolbox_rs::lru::LRU;
218 ///
219 /// let mut cache = LRU::new_with_capacity(2);
220 /// cache.push(&1, String::from("one"));
221 /// cache.push(&2, String::from("two"));
222 ///
223 /// if let Some((_, value)) = cache.get_front_mut() {
224 /// *value = String::from("TWO");
225 /// }
226 /// assert_eq!(cache.get(&2), Some(&String::from("TWO")));
227 /// ```
228 pub fn get_front_mut(&mut self) -> Option<(&Key, &mut Value)> {
229 if self.is_empty() {
230 None
231 } else {
232 let front = self.lru_list.get_front_mut();
233 Some((&front.0, &mut front.1))
234 }
235 }
236
237 /// Returns the maximum number of items the cache can hold.
238 ///
239 /// # Examples
240 ///
241 /// ```
242 /// use toolbox_rs::lru::LRU;
243 ///
244 /// let cache: LRU<i32, &str> = LRU::new_with_capacity(5);
245 /// assert_eq!(cache.capacity(), 5);
246 /// ```
247 pub fn capacity(&self) -> usize {
248 self.capacity
249 }
250
251 /// Returns the current number of items in the cache.
252 ///
253 /// # Examples
254 ///
255 /// ```
256 /// use toolbox_rs::lru::LRU;
257 ///
258 /// let mut cache = LRU::new_with_capacity(2);
259 /// assert_eq!(cache.len(), 0);
260 ///
261 /// cache.push(&1, "one");
262 /// assert_eq!(cache.len(), 1);
263 /// ```
264 pub fn len(&self) -> usize {
265 assert_eq!(self.lru_list.len(), self.access_map.len());
266 self.lru_list.len()
267 }
268
269 /// Returns true if the cache contains no items.
270 ///
271 /// # Examples
272 ///
273 /// ```
274 /// use toolbox_rs::lru::LRU;
275 ///
276 /// let mut cache = LRU::new_with_capacity(2);
277 /// assert!(cache.is_empty());
278 ///
279 /// cache.push(&1, "one");
280 /// assert!(!cache.is_empty());
281 ///
282 /// cache.clear();
283 /// assert!(cache.is_empty());
284 /// ```
285 pub fn is_empty(&self) -> bool {
286 self.len() == 0
287 }
288
289 /// Removes all items from the cache.
290 ///
291 /// # Examples
292 ///
293 /// ```
294 /// use toolbox_rs::lru::LRU;
295 ///
296 /// let mut cache = LRU::new_with_capacity(2);
297 /// cache.push(&1, "one");
298 /// cache.push(&2, "two");
299 ///
300 /// cache.clear();
301 /// assert!(cache.is_empty());
302 /// assert_eq!(cache.len(), 0);
303 /// ```
304 pub fn clear(&mut self) {
305 self.lru_list.clear();
306 self.access_map.clear();
307 }
308}
309
310#[cfg(test)]
311mod tests {
312 use super::LRU;
313
314 struct SomeTestStruct(i32);
315
316 #[test]
317 fn construct() {
318 let mut lru = LRU::new_with_capacity(10);
319 assert_eq!(0, lru.len());
320 lru.push(&1, SomeTestStruct(1));
321 assert_eq!(1, lru.len());
322 lru.push(&2, SomeTestStruct(2));
323 assert_eq!(2, lru.len());
324 lru.push(&3, SomeTestStruct(3));
325 assert_eq!(3, lru.len());
326 lru.push(&4, SomeTestStruct(4));
327 assert_eq!(4, lru.len());
328 lru.push(&5, SomeTestStruct(5));
329 assert_eq!(5, lru.len());
330 lru.push(&6, SomeTestStruct(6));
331 assert_eq!(6, lru.len());
332 lru.push(&7, SomeTestStruct(7));
333 assert_eq!(7, lru.len());
334 lru.push(&8, SomeTestStruct(8));
335 assert_eq!(8, lru.len());
336 lru.push(&9, SomeTestStruct(9));
337 assert_eq!(9, lru.len());
338 lru.push(&10, SomeTestStruct(10));
339 assert_eq!(10, lru.len());
340 assert_eq!(10, lru.capacity());
341
342 // access 1, make 2 the oldest element now
343 let handle = lru.get(&1).unwrap();
344 assert_eq!(1, handle.0);
345 // add 11, evict 2
346 lru.push(&11, SomeTestStruct(11));
347 assert!(!lru.contains(&2));
348 assert_eq!(lru.len(), 10);
349
350 // get handle for evicted element and verify it is None
351 let handle = lru.get(&2);
352 assert!(handle.is_none());
353
354 // assert that all other elements are still cached
355 let keys = vec![1, 3, 4, 5, 6, 7, 8, 9, 10, 11];
356 keys.into_iter().for_each(|key| {
357 assert!(lru.contains(&key));
358 });
359 }
360
361 #[test]
362 fn clear_is_empty() {
363 let mut lru = LRU::new_with_capacity(10);
364 for i in [0, 1, 2, 3] {
365 lru.push(&i, 2 * i);
366 }
367 assert!(!lru.is_empty());
368 lru.clear();
369 assert!(lru.is_empty());
370 }
371
372 #[test]
373 fn test_update_existing_key() {
374 let mut lru = LRU::new_with_capacity(2);
375 lru.push(&1, "one");
376 lru.push(&2, "two");
377
378 // Update existing key
379 lru.push(&1, "ONE");
380 assert_eq!(lru.get(&1), Some(&"ONE"));
381 assert_eq!(lru.len(), 2);
382 }
383
384 #[test]
385 fn test_get_updates_order() {
386 let mut lru = LRU::new_with_capacity(3);
387 lru.push(&1, "one");
388 lru.push(&2, "two");
389 lru.push(&3, "three");
390
391 // Access 1, making it most recently used
392 assert_eq!(lru.get(&1), Some(&"one"));
393
394 // Add new item - should evict 2, not 1
395 lru.push(&4, "four");
396 assert!(lru.contains(&1));
397 assert!(!lru.contains(&2));
398 assert!(lru.contains(&3));
399 assert!(lru.contains(&4));
400 }
401
402 #[test]
403 fn test_capacity_bounds() {
404 let mut lru = LRU::new_with_capacity(1);
405 lru.push(&1, "one");
406 assert_eq!(lru.len(), 1);
407 assert!(lru.contains(&1));
408
409 lru.push(&2, "two");
410 assert_eq!(lru.len(), 1);
411 assert!(!lru.contains(&1));
412 assert!(lru.contains(&2));
413 }
414
415 #[test]
416 fn test_clear_retains_capacity() {
417 let mut lru = LRU::new_with_capacity(5);
418 for i in 0..5 {
419 lru.push(&i, i.to_string());
420 }
421 assert_eq!(lru.len(), 5);
422
423 lru.clear();
424 assert_eq!(lru.len(), 0);
425 assert_eq!(lru.capacity(), 5);
426
427 // Can still add items up to capacity
428 for i in 0..5 {
429 lru.push(&i, i.to_string());
430 }
431 assert_eq!(lru.len(), 5);
432 }
433
434 #[test]
435 fn test_get_front_mut() {
436 let mut lru = LRU::new_with_capacity(3);
437 assert_eq!(lru.get_front_mut(), None);
438
439 lru.push(&1, String::from("one"));
440 lru.push(&2, String::from("two"));
441
442 // Test mutating the front element
443 if let Some((key, value)) = lru.get_front_mut() {
444 assert_eq!(key, &2);
445 assert_eq!(value, "two");
446 *value = String::from("TWO");
447 }
448
449 // Verify the change was applied
450 assert_eq!(lru.get(&2), Some(&String::from("TWO")));
451
452 // Add another element and verify front changes
453 lru.push(&3, String::from("three"));
454 if let Some((key, value)) = lru.get_front_mut() {
455 assert_eq!(key, &3);
456 assert_eq!(value, "three");
457 *value = String::from("THREE");
458 }
459
460 // Verify both modified values are still correct
461 assert_eq!(lru.get(&2), Some(&String::from("TWO")));
462 assert_eq!(lru.get(&3), Some(&String::from("THREE")));
463 }
464}