gvec 0.5.0

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

/// A Generational vector
///
/// A vector with a so-called Generational scheme, akin to a versioning scheme,
/// for its indices. This is done in order to prevent use-after-free scenarios,
/// where an attempt to access a specific position with a given index is denied
/// after the original item is removed and its position (or index) has been
/// freed. It also promotes memory reuse, since the memory allocated is not
/// released until the vector goes out of scope or the program ends, and it
/// _might_ lead to lower overall memory use.
///
/// ## Note
///
/// Due to the functionality of avoiding invalid access (use-after-free), this
/// type of vector consumes *much more* memory than a simple vector itself.
pub struct DenseVec<T> {
    vec: Vec<T>,
    free: VecDeque<usize>,
    generations: HashMap<usize, usize>,
}

impl<T> DenseVec<T> {
    /// Creates a GenVec with a specific capacity
    ///
    /// Creates a GenerationalVec with a pre-allocated memory in order to
    /// reduce the overhead of future reallocations.
    pub fn with_capacity(capacity: usize) -> DenseVec<T> {
        let mut temp_deque = VecDeque::with_capacity(capacity);
        let mut temp_map = HashMap::with_capacity(capacity);
        let temp_vec: Vec<T> = Vec::with_capacity(capacity);
        for i in 0..capacity {
            temp_deque.push_back(i);
            temp_map.insert(i, 0);
        }
        DenseVec {
            vec: temp_vec,
            free: temp_deque,
            generations: temp_map,
        }
    }

    /// Get a value by an index
    ///
    /// Returns the value if both the index and the generation do match.
    /// Otherwise returns None. A safe alternative to the index [] operator,
    /// which can panic if index out-of-bounds or generation does not match.
    pub fn get(&self, index: GenerationalIndex) -> Option<&T> {
        if self.generations[&index.index()] == index.generation() {
            self.vec.get(index.index())
        } else {
            None
        }
    }

    /// Insert a value on the vector
    ///
    /// Returns a GenerationalIndex with the index and the generation in which
    /// it was added.
    ///
    /// # Example
    ///
    /// ```
    /// use gvec::DenseVec as GenVec;
    ///
    /// let mut example = GenVec::with_capacity(2);
    /// let first = example.insert(2);
    /// assert_eq!(example[first], 2);
    /// ```
    pub fn insert(&mut self, value: T) -> GenerationalIndex {
        if let Some(idx) = self.free.pop_front() {
            self.vec.insert(idx, value);
            GenerationalIndex::new(idx, self.generations[&idx])
        } else {
            let vec_len = self.vec.len();
            self.generations.reserve(1);
            self.generations.insert(vec_len, 0);
            self.vec.push(value);
            self.free.reserve(1);
            GenerationalIndex::new(vec_len, 0)
        }
    }

    /// Remove a value of the vector by a given index
    ///
    /// Upon the removal of the value, the index is liberated for use, in order
    /// to reuse the space already allocated, and the generation is upped by
    /// one, in order to prevent use-after-free scenarios or "address
    /// violation" (access another value allocated in the same space (i.e. same
    /// index), but with a different generation)
    ///
    /// # Example
    ///
    /// ```,rust,should_panic
    /// use gvec::DenseVec as GenVec;
    ///
    /// let mut example = GenVec::with_capacity(2);
    /// let first = example.insert(1);
    /// assert_eq!(example[first], 1);
    /// example.remove(first);
    /// assert_eq!(example[first], 1); // produces a panic!
    /// ```
    pub fn remove(&mut self, index: GenerationalIndex) -> Result<(), Error> {
        if let Some(_val) = self.vec.get(index.index()) {
            if self.generations[&index.index()] == index.generation() {
                let x = self.generations.get_mut(&index.index()).unwrap();
                self.vec.remove(index.index());
                self.free.push_back(index.index());
                *x += 1;
                Ok(())
            } else {
                Err(Error::WrongGeneration)
            }
        } else {
            Err(Error::ElementNotFound)
        }
    }

    // Both these methods do need to be changed in order to avoid problems with
    // enumeration and Generation management, since the Enumerate struct
    // manages its own counter
    pub fn iter(&self) -> impl Iterator<Item = &T> {
        self.vec.iter()
    }
}

impl<T> IntoIterator for DenseVec<T> {
    type Item = T;
    type IntoIter = ::std::vec::IntoIter<T>;
    fn into_iter(self) -> Self::IntoIter {
        self.vec.into_iter()
    }
}

impl<T> Index<GenerationalIndex> for DenseVec<T> {
    type Output = T;

    /// # Panics
    ///
    /// Indexing will panic! when the generation of the given index does not
    /// match the generation in the vector. Use ```GenVec::get()``` instead
    /// as a non-panic version that will return an Option.
    fn index(&self, index: GenerationalIndex) -> &Self::Output {
        if self.generations[&index.index()] == index.generation() {
            &self.vec[index.index()]
        } else {
            panic!(format!(
                "Generation does not match!
                Index generation: \u{1b}[38:5:1m{}
                Current generation: \u{1b}[38:5:4m{}\n",
                index.generation(),
                self.generations[&index.index()]
            ))
        }
    }
}