gvec 0.5.0

use crate::{index::GenerationalIndex, Error};
use std::collections::{HashMap, VecDeque};

/// Allocator for the LightVec
///
/// Although not really an allocator, this entity guarantees that an action
/// done to the vector will not violate the Generational scheme, or versioning
/// scheme. For the time being, this *must* be passed as parameter to any
/// LightVec function, such as insert or remove, in order to make those
/// guarantees. The allocator can be instantiated with the lvec! macro, or with
/// the ```new()``` function.
///
/// Similar to the LightVec itself, the allocator can handle reallocations in
/// case of insertion when the Vec is above capacity. In order to reduce
/// overhead due to frequent reallocations, there is a setting in the
/// allocator, called loan, which is used as way to assure how much memory is
/// "loaned" when there is a reallocation. Default value for the loan is 1.
pub struct LightVecAllocator {
    loan: usize,
    generations: HashMap<usize, usize>,
    free: VecDeque<usize>,
}

impl LightVecAllocator {
    /// Creates a new LightVecAllocator
    ///
    /// Creates a new LightVecAllocator, with the given capacity and with
    /// default values.
    fn with_capacity(capacity: usize) -> LightVecAllocator {
        let mut gens: HashMap<usize, usize> = HashMap::with_capacity(capacity);
        for i in 0..capacity {
            gens.insert(i, 0);
        }
        LightVecAllocator {
            loan: 1,
            generations: gens,
            free: VecDeque::with_capacity(capacity),
        }
    }

    /// Checks the generation
    ///
    /// Checks if the generation in the given GenerationalIndex does match what
    /// is allocated/store in the allocator
    fn match_generation(&self, index: &GenerationalIndex) -> bool {
        self.generations[&index.index()] == index.generation()
    }

    /// Allocates an index in the Generational mechanism
    fn allocate(&mut self, vec_len: usize) -> GenerationalIndex {
        if let Some(idx) = self.free.pop_front() {
            GenerationalIndex::new(idx, self.generations[&idx])
        } else {
            self.generations.reserve(self.loan);
            self.generations.insert(vec_len, 0);
            self.free.reserve(self.loan);
            GenerationalIndex::new(vec_len, 0)
        }
    }

    /// Deallocates an index in the Generational mechanism
    fn deallocate(&mut self, index: GenerationalIndex) -> Result<(), Error> {
        if self.generations[&index.index()] == index.generation() {
            let x = self.generations.get_mut(&index.index()).unwrap();
            self.free.push_back(index.index());
            *x += 1;
            Ok(())
        } else {
            Err(Error::WrongGeneration)
        }
    }

    /// Sets the loan
    ///
    /// Sets the loan strategy, or a simple value, to be used in reallocations
    /// during insertion.
    ///
    /// Default value on Allocator creation is set to 1.
    pub fn set_loan(&mut self, loan: usize) {
        self.loan = loan;
    }

    /// Returns the loan value
    ///
    /// Returns the loan value used in the loan strategy for reallocation
    pub fn loan(&self) -> usize {
        self.loan
    }
}

/// Light version of a Vec with Generational scheme
///
/// LightVec is a lighter version of DenseVec, a Vec with a so-called
/// Generational scheme, akin to the idea of versioning the indices to prevent
/// use-after-free scenarions when using a given index.
///
/// It is so called a lighter version due to the fact that the allocation of
/// indices, i.e. the process that guarantees that indices are versioned, is
/// placed outside the Vec itself.
pub struct LightVec<T>(Vec<T>);

impl<T> LightVec<T> {
    /// Creates a new Vec with the given capacity
    ///
    /// Creates a new Vec with the given capacity. It also creates an
    /// allocator, that is returned alongside the Vec itself.
    pub fn with_capacity(capacity: usize) -> (LightVec<T>, LightVecAllocator) {
        (
            LightVec(Vec::with_capacity(capacity)),
            LightVecAllocator::with_capacity(capacity),
        )
    }

    /// Returns a value with the given index
    ///
    /// # Examples
    ///
    /// ```{rust}
    /// use gvec::{lvec, LightVec, GenerationalIndex};
    ///
    /// let (mut example, mut example_alloc, example_indices) = lvec![3; 1];
    /// assert_eq!(example.get(&example_indices[0], &example_alloc), Some(&1));
    /// ```
    pub fn get(&self, index: &GenerationalIndex, allocator: &LightVecAllocator) -> Option<&T> {
        if allocator.match_generation(index) {
            self.0.get(index.index())
        } else {
            None
        }
    }

    /// Inserts a value on the Vec
    ///
    /// If the Vec is full, it will reallocate itself (and the allocator) with
    /// the 'loan strategy' set on the allocator. If not altered, default loan
    /// strategy is set to 1.
    ///
    /// # Examples
    ///
    /// ```{rust}
    /// use gvec::LightVec;
    ///
    /// let (mut example, mut example_alloc) = LightVec::with_capacity(3);
    /// let idx = example.insert(1_f32, &mut example_alloc);
    /// assert_eq!(example.get(&idx, &example_alloc), Some(&1_f32));
    /// ```
    pub fn insert(&mut self, value: T, allocator: &mut LightVecAllocator) -> GenerationalIndex {
        let temp_idx = allocator.allocate(self.0.len());
        self.0.insert(temp_idx.index(), value);
        temp_idx
    }

    /// Removes a value of the Vec
    ///
    /// Removes a value of the Vec with the given index. Index is checked
    /// before removal in order to guarantee that the index version is correct.
    /// Otherwise, returns an error.
    ///
    /// # Examples
    ///
    /// ```{rust}
    /// use gvec::LightVec;
    ///
    /// let (mut example, mut example_alloc) = LightVec::with_capacity(3);
    /// let idx = example.insert(1, &mut example_alloc);
    /// assert_eq!(example.remove(idx, &mut example_alloc), Ok(()));
    /// ```
    pub fn remove(
        &mut self,
        index: GenerationalIndex,
        allocator: &mut LightVecAllocator,
    ) -> Result<(), Error> {
        if let Some(_val) = self.0.get(index.index()) {
            allocator.deallocate(index)?;
            self.0.remove(index.index());
            Ok(())
        } else {
            Err(Error::ElementNotFound)
        }
    }
}