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#[derive(Debug)]
8pub struct LruCache<K, V> {
9    capacity: usize,
10    data: HashMap<K, V>,
11    order: Vec<K>,
12}
13
14impl<K: Clone + Hash + Eq, V> LruCache<K, V> {
15    /// Create a new LRU cache with the given capacity
16    pub fn new(capacity: usize) -> Self {
17        Self {
18            capacity,
19            data: HashMap::new(),
20            order: Vec::new(),
21        }
22    }
23
24    /// Insert a key-value pair into the cache
25    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
26        if let Some(old_value) = self.data.insert(key.clone(), value) {
27            // Key already existed, update order
28            self.move_to_front(&key);
29            Some(old_value)
30        } else {
31            // New key
32            self.order.insert(0, key);
33            self.evict_if_needed();
34            None
35        }
36    }
37
38    /// Get a value from the cache, updating its position
39    pub fn get(&mut self, key: &K) -> Option<&V> {
40        if self.data.contains_key(key) {
41            self.move_to_front(key);
42            self.data.get(key)
43        } else {
44            None
45        }
46    }
47
48    /// Get a value without updating its position
49    pub fn peek(&self, key: &K) -> Option<&V> {
50        self.data.get(key)
51    }
52
53    /// Remove a key from the cache
54    pub fn remove(&mut self, key: &K) -> Option<V> {
55        if let Some(value) = self.data.remove(key) {
56            self.order.retain(|k| k != key);
57            Some(value)
58        } else {
59            None
60        }
61    }
62
63    /// Get the current size of the cache
64    pub fn len(&self) -> usize {
65        self.data.len()
66    }
67
68    /// Check if the cache is empty
69    pub fn is_empty(&self) -> bool {
70        self.data.is_empty()
71    }
72
73    /// Clear all items from the cache
74    pub fn clear(&mut self) {
75        self.data.clear();
76        self.order.clear();
77    }
78
79    fn move_to_front(&mut self, key: &K) {
80        if let Some(pos) = self.order.iter().position(|k| k == key) {
81            let key = self.order.remove(pos);
82            self.order.insert(0, key);
83        }
84    }
85
86    fn evict_if_needed(&mut self) {
87        while self.order.len() > self.capacity {
88            if let Some(key) = self.order.pop() {
89                self.data.remove(&key);
90            }
91        }
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn test_lru_cache_basic() {
101        let mut cache = LruCache::new(2);
102
103        cache.insert(1, "one");
104        cache.insert(2, "two");
105
106        assert_eq!(cache.get(&1), Some(&"one"));
107        assert_eq!(cache.get(&2), Some(&"two"));
108        assert_eq!(cache.len(), 2);
109    }
110
111    #[test]
112    fn test_lru_cache_eviction() {
113        let mut cache = LruCache::new(2);
114
115        cache.insert(1, "one");
116        cache.insert(2, "two");
117        cache.insert(3, "three"); // Should evict key 1
118
119        assert_eq!(cache.get(&1), None);
120        assert_eq!(cache.get(&2), Some(&"two"));
121        assert_eq!(cache.get(&3), Some(&"three"));
122    }
123}
commons/collections.rs

commons/
collections.rs
