Skip to main content

data_structures_lib/
caches.rs

1use std::collections::{HashMap, VecDeque};
2
3use crate::Error;
4
5/// A least-recently-used cache with a fixed capacity.
6#[derive(Debug)]
7pub struct LruCache<K: Clone + Eq + std::hash::Hash, V> {
8    capacity: usize,
9    cache: HashMap<K, V>,
10    order: VecDeque<K>,
11}
12
13impl<K: Clone + Eq + std::hash::Hash, V> LruCache<K, V> {
14    /// Creates a new LruCache.
15    pub fn new(capacity: usize) -> Result<Self, Error> {
16        if capacity == 0 {
17            return Err(Error::InvalidArgument);
18        }
19        Ok(Self {
20            capacity,
21            cache: HashMap::new(),
22            order: VecDeque::new(),
23        })
24    }
25
26    /// Returns the number of entries.
27    pub fn len(&self) -> usize {
28        self.cache.len()
29    }
30
31    /// Returns true if the cache is empty.
32    pub fn is_empty(&self) -> bool {
33        self.cache.is_empty()
34    }
35
36    /// Returns true if the key exists.
37    pub fn has(&self, key: &K) -> bool {
38        self.cache.contains_key(key)
39    }
40
41    /// Returns a reference to the value for a key, marking it as recently used.
42    pub fn get(&mut self, key: &K) -> Result<&V, Error> {
43        if !self.cache.contains_key(key) {
44            return Err(Error::NotFound);
45        }
46        self.touch(key);
47        Ok(self.cache.get(key).unwrap())
48    }
49
50    /// Sets a key-value pair.
51    pub fn set(&mut self, key: K, value: V) {
52        if self.cache.contains_key(&key) {
53            self.cache.insert(key.clone(), value);
54            self.touch(&key);
55            return;
56        }
57        if self.cache.len() >= self.capacity {
58            if let Some(oldest) = self.order.pop_front() {
59                self.cache.remove(&oldest);
60            }
61        }
62        self.cache.insert(key.clone(), value);
63        self.order.push_back(key);
64    }
65
66    fn touch(&mut self, key: &K) {
67        if let Some(pos) = self.order.iter().position(|k| k == key) {
68            let k = self.order.remove(pos).unwrap();
69            self.order.push_back(k);
70        }
71    }
72}