ahrightos-fs 0.1.0

use alloc::vec::Vec;
use core::marker::PhantomData;

pub trait Cacheable<K> {
    fn key(&self) -> K;
}

#[derive(Debug)]
pub struct LruCache<K, V>
where
    K: PartialEq,
    V: Cacheable<K>,
{
    entries: Vec<V>,
    capacity: usize,
    _phantom: PhantomData<K>,
}

impl<K: PartialEq, V: Cacheable<K>> LruCache<K, V> {
    pub fn new(capacity: usize) -> Self {
        Self {
            entries: Vec::with_capacity(capacity),
            capacity,
            _phantom: PhantomData,
        }
    }

    pub fn get(&mut self, key: &K) -> Option<&V> {
        for i in 0..self.entries.len() {
            if self.entries[i].key() == *key {
                if i + 1 == self.entries.len() {
                    return self.entries.last();
                }
                let entry = self.entries.remove(i);
                self.entries.push(entry);
                return self.entries.last();
            }
        }
        None
    }

    pub fn insert(&mut self, value: V) {
        if self.capacity == 0 {
            return;
        }
        let key = value.key();
        if let Some(pos) = self.entries.iter().position(|entry| entry.key() == key) {
            self.entries.remove(pos);
        }
        if self.entries.len() >= self.capacity {
            self.entries.remove(0);
        }
        self.entries.push(value);
    }

    pub fn len(&self) -> usize {
        self.entries.len()
    }

    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }

    pub fn capacity(&self) -> usize {
        self.capacity
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[derive(Debug, PartialEq, Eq)]
    struct Entry {
        key: usize,
        value: usize,
    }

    impl Cacheable<usize> for Entry {
        fn key(&self) -> usize {
            self.key
        }
    }

    #[test]
    fn get_promotes_entry_to_mru() {
        let mut cache = LruCache::<usize, Entry>::new(2);
        cache.insert(Entry { key: 1, value: 10 });
        cache.insert(Entry { key: 2, value: 20 });
        assert_eq!(cache.get(&1).map(|entry| entry.value), Some(10));
        cache.insert(Entry { key: 3, value: 30 });
        assert_eq!(cache.get(&2).map(|entry| entry.value), None);
        assert_eq!(cache.get(&1).map(|entry| entry.value), Some(10));
    }
}