commons/
collections.rs

1//! Specialized data structures and collection utilities.
2
3use std::collections::HashMap;
4use std::hash::Hash;
5
6/// A cache with a maximum capacity that evicts the least recently used items.
7///
8/// This implementation uses a `Vec` for order tracking, giving O(N) access
9/// and insertion cost per operation. It is designed for small-capacity caches
10/// (up to ~100 entries). For high-throughput or large-capacity use cases,
11/// consider the [`lru`](https://crates.io/crates/lru) crate which provides
12/// O(1) operations via a doubly-linked list and `HashMap`.
13#[derive(Debug)]
14pub struct LruCache<K, V> {
15    capacity: usize,
16    data: HashMap<K, V>,
17    order: Vec<K>,
18}
19
20impl<K: Clone + Hash + Eq, V> LruCache<K, V> {
21    /// Create a new LRU cache with the given capacity
22    #[must_use]
23    pub fn new(capacity: usize) -> Self {
24        Self {
25            capacity,
26            data: HashMap::new(),
27            order: Vec::new(),
28        }
29    }
30
31    /// Insert a key-value pair into the cache
32    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
33        if let Some(old_value) = self.data.insert(key.clone(), value) {
34            // Key already existed, update order
35            self.move_to_front(&key);
36            Some(old_value)
37        } else {
38            // New key
39            self.order.insert(0, key);
40            self.evict_if_needed();
41            None
42        }
43    }
44
45    /// Get a value from the cache, updating its position
46    pub fn get(&mut self, key: &K) -> Option<&V> {
47        if self.data.contains_key(key) {
48            self.move_to_front(key);
49            self.data.get(key)
50        } else {
51            None
52        }
53    }
54
55    /// Get a value without updating its position
56    #[must_use]
57    pub fn peek(&self, key: &K) -> Option<&V> {
58        self.data.get(key)
59    }
60
61    /// Remove a key from the cache
62    pub fn remove(&mut self, key: &K) -> Option<V> {
63        if let Some(value) = self.data.remove(key) {
64            self.order.retain(|k| k != key);
65            Some(value)
66        } else {
67            None
68        }
69    }
70
71    /// Get the current size of the cache
72    #[must_use]
73    pub fn len(&self) -> usize {
74        self.data.len()
75    }
76
77    /// Check if the cache is empty
78    #[must_use]
79    pub fn is_empty(&self) -> bool {
80        self.data.is_empty()
81    }
82
83    /// Clear all items from the cache
84    pub fn clear(&mut self) {
85        self.data.clear();
86        self.order.clear();
87    }
88
89    fn move_to_front(&mut self, key: &K) {
90        if let Some(pos) = self.order.iter().position(|k| k == key) {
91            let key = self.order.remove(pos);
92            self.order.insert(0, key);
93        }
94    }
95
96    fn evict_if_needed(&mut self) {
97        while self.order.len() > self.capacity {
98            if let Some(key) = self.order.pop() {
99                self.data.remove(&key);
100            }
101        }
102    }
103}
104
105#[cfg(test)]
106mod tests {
107    use super::*;
108
109    #[test]
110    fn test_lru_cache_basic() {
111        let mut cache = LruCache::new(2);
112
113        cache.insert(1, "one");
114        cache.insert(2, "two");
115
116        assert_eq!(cache.get(&1), Some(&"one"));
117        assert_eq!(cache.get(&2), Some(&"two"));
118        assert_eq!(cache.len(), 2);
119    }
120
121    #[test]
122    fn test_lru_cache_eviction() {
123        let mut cache = LruCache::new(2);
124
125        cache.insert(1, "one");
126        cache.insert(2, "two");
127        cache.insert(3, "three"); // Should evict key 1
128
129        assert_eq!(cache.get(&1), None);
130        assert_eq!(cache.get(&2), Some(&"two"));
131        assert_eq!(cache.get(&3), Some(&"three"));
132    }
133}
commons/collections.rs

commons/
collections.rs
