data_structures_lib/
caches.rs1use std::collections::{HashMap, VecDeque};
2
3use crate::Error;
4
5#[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 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 pub fn len(&self) -> usize {
28 self.cache.len()
29 }
30
31 pub fn is_empty(&self) -> bool {
33 self.cache.is_empty()
34 }
35
36 pub fn has(&self, key: &K) -> bool {
38 self.cache.contains_key(key)
39 }
40
41 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 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}