id_vector.rs.html -- source

use {Identifier, FromIndex, ToIndex, IdRange};
use std::default::Default;
use std::slice;
use std::marker::PhantomData;
use std::ops;
use std::iter::IntoIterator;
use num_traits::Zero;

/// Similar to Vec except that it is indexed using an Id rather than an usize index.
/// if the stored type implements Default, IdVec can also use the set(...) method which can
/// grow the vector to accomodate for the requested id.
pub struct IdVec<ID: Identifier, T> {
    data: Vec<T>,
    _idtype: PhantomData<ID>,
}

impl<ID: Identifier, T> IdVec<ID, T> {
    /// Create an empty IdVec
    #[inline]
    pub fn new() -> Self {
        IdVec {
            data: Vec::new(),
            _idtype: PhantomData,
        }
    }

    /// Create an IdVec with preallocated storage
    #[inline]
    pub fn with_capacity(size: ID::Handle) -> Self {
        IdVec {
            data: Vec::with_capacity(size.to_index()),
            _idtype: PhantomData,
        }
    }

    /// Create an IdVec by recycling a Vec and its content.
    #[inline]
    pub fn from_vec(vec: Vec<T>) -> Self {
        IdVec {
            data: vec,
            _idtype: PhantomData,
        }
    }

    /// Consume the IdVec and create a Vec.
    #[inline]
    pub fn into_vec(self) -> Vec<T> {
        self.data
    }

    /// Exposes the internal Vec.
    #[inline]
    pub fn as_vec(&self) -> &Vec<T> {
        &self.data
    }

    /// Number of elements in the IdVec
    #[inline]
    pub fn len(&self) -> ID::Handle {
        FromIndex::from_index(self.data.len())
    }

    /// Returns true if the vector contains no elements.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    /// Extracts a slice containing the entire vector.
    #[inline]
    pub fn as_slice(&self) -> IdSlice<ID, T> {
        IdSlice::new(self.data.as_slice())
    }

    /// Extracts a mutable slice containing the entire vector.
    #[inline]
    pub fn as_mut_slice(&mut self) -> MutIdSlice<ID, T> {
        MutIdSlice::new(self.data.as_mut_slice())
    }

    #[inline]
    pub fn range(&self, ids: IdRange<ID::Tag, ID::Handle>) -> IdSlice<ID, T> {
        IdSlice::new(&self.data[ids.start.to_index()..ids.end.to_index()])
    }

    #[inline]
    pub fn mut_range(&mut self, ids: IdRange<ID::Tag, ID::Handle>) -> MutIdSlice<ID, T> {
        MutIdSlice::new(&mut self.data[ids.start.to_index()..ids.end.to_index()])
    }

    #[inline]
    pub fn range_from(&self, id: ID) -> IdSlice<ID, T> {
        IdSlice::new(&self.data[id.to_index()..])
    }

    #[inline]
    pub fn mut_range_from(&mut self, id: ID) -> MutIdSlice<ID, T> {
        MutIdSlice::new(&mut self.data[id.to_index()..])
    }

    #[inline]
    pub fn range_to(&self, id: ID) -> IdSlice<ID, T> {
        IdSlice::new(&self.data[..id.to_index()])
    }

    #[inline]
    pub fn mut_range_to(&mut self, id: ID) -> MutIdSlice<ID, T> {
        MutIdSlice::new(&mut self.data[..id.to_index()])
    }

    /// Return the nth element of the IdVec using an usize index rather than an Id (à la Vec).
    #[inline]
    pub fn nth(&self, idx: ID::Handle) -> &T {
        &self.data[idx.to_index()]
    }

    /// Return the nth element of the IdVec using an usize index rather than an Id (à la Vec).
    #[inline]
    pub fn nth_mut(&mut self, idx: ID::Handle) -> &mut T {
        &mut self.data[idx.to_index()]
    }

    /// Iterate over the elements of the IdVec
    #[inline]
    pub fn iter<'l>(&'l self) -> slice::Iter<'l, T> {
        self.data.iter()
    }

    /// Iterate over the elements of the IdVec
    #[inline]
    pub fn iter_mut<'l>(&'l mut self) -> slice::IterMut<'l, T> {
        self.data.iter_mut()
    }

    /// Add an element to the IdVec and return its Id.
    /// This method can cause the storage to be reallocated.
    #[inline]
    pub fn push(&mut self, elt: T) -> ID {
        let index = self.data.len();
        self.data.push(elt);
        return FromIndex::from_index(index);
    }

    /// Reserves capacity for at least additional more elements to be inserted in the given vector.
    #[inline]
    pub fn reserve(&mut self, additional: ID::Handle) {
        self.data.reserve(additional.to_index());
    }

    /// Shrinks the capacity of the vector as much as possible.
    #[inline]
    pub fn shrink_to_fit(&mut self) {
        self.data.shrink_to_fit();
    }

    /// Drop all of the contained elements and clear the IdVec's storage.
    #[inline]
    pub fn clear(&mut self) {
        self.data.clear();
    }

    /// Removes and returns the element at position index within the vector,
    /// shifting all elements after it to the left.
    #[inline]
    pub fn remove(&mut self, index: ID) -> T {
        self.data.remove(index.to_index())
    }

    /// Removes an element from the vector and returns it.
    /// The removed element is replaced by the last element of the vector.
    #[inline]
    pub fn swap_remove(&mut self, index: ID) -> T {
        self.data.swap_remove(index.to_index())
    }

    #[inline]
    pub fn has_id(&self, id: ID) -> bool {
        id.to_index() < self.data.len()
    }

    #[inline]
    pub fn first_id(&self) -> Option<ID> {
        return if self.data.len() > 0 {
            Some(ID::from_index(0))
        } else {
            None
        };
    }
}

impl<ID: Identifier, T: Default> IdVec<ID, T> {
    /// Set the value for a certain Id, possibly adding default values if the Id's index is Greater
    /// than the size of the underlying vector.
    pub fn set(&mut self, id: ID, val: T) {
        while self.len().to_index() < id.to_index() {
            self.push(T::default());
        }
        if self.len().to_index() == id.to_index() {
            self.push(val);
        } else {
            self[id] = val;
        }
    }
}

impl<T: Default, ID: Identifier> IdVec<ID, T> {
    pub fn resize(&mut self, size: ID::Handle) {
        if size.to_index() > self.data.len() {
            let d = size.to_index() - self.data.len();
            self.data.reserve(d as usize);
            for _ in 0..d {
                self.data.push(Default::default());
            }
        } else {
            let d = self.data.len() - size.to_index();
            for _ in 0..d {
                self.data.pop();
            }
        }
    }

    /// Creates an IdVec with an n elements initialized to `Default::default`.
    pub fn with_len(n: ID::Handle) -> Self {
        let mut result: IdVec<ID, T> = IdVec::with_capacity(n);
        result.resize(n);
        return result;
    }
}

impl<ID: Identifier, T> ops::Index<ID> for IdVec<ID, T> {
    type Output = T;
    fn index<'l>(&'l self, id: ID) -> &'l T {
        &self.data[id.to_index()]
    }
}

impl<ID: Identifier, T> ops::IndexMut<ID> for IdVec<ID, T> {
    fn index_mut<'l>(&'l mut self, id: ID) -> &'l mut T {
        &mut self.data[id.to_index()]
    }
}


pub struct IdSlice<'l, ID: Identifier, T>
where
    T: 'l,
{
    slice: &'l [T],
    _idtype: PhantomData<ID>,
}

impl<'l, T, ID: Identifier> Copy for IdSlice<'l, ID, T>
where
    T: 'l,
{
}

impl<'l, T, ID: Identifier> Clone for IdSlice<'l, ID, T>
where
    T: 'l,
{
    #[inline]
    fn clone(&self) -> IdSlice<'l, ID, T> {
        IdSlice {
            slice: self.slice,
            _idtype: PhantomData,
        }
    }
}

impl<'l, T, ID: Identifier> IdSlice<'l, ID, T>
where
    T: 'l,
{
    #[inline]
    pub fn new(slice: &'l [T]) -> IdSlice<'l, ID, T> {
        IdSlice {
            slice: slice,
            _idtype: PhantomData,
        }
    }

    #[inline]
    pub fn len(&self) -> ID::Handle {
        FromIndex::from_index(self.slice.len())
    }

    #[inline]
    pub fn untyed<'a>(&'a self) -> &'a [T] {
        self.slice
    }

    #[inline]
    pub fn iter<'a>(&'a self) -> slice::Iter<'a, T> {
        self.slice.iter()
    }

    #[inline]
    pub fn ids(&self) -> IdRange<ID::Tag, ID::Handle> {
        IdRange::new(Zero::zero()..self.len())
    }

    #[inline]
    pub fn nth(&self, idx: ID::Handle) -> &T {
        &self.slice[idx.to_index()]
    }

    #[inline]
    pub fn range(&self, ids: IdRange<ID::Tag, ID::Handle>) -> IdSlice<ID, T> {
        IdSlice::new(&self.slice[ids.start.to_index()..ids.end.to_index()])
    }

    #[inline]
    pub fn range_from(&self, id: ID) -> IdSlice<ID, T> {
        IdSlice::new(&self.slice[id.to_index()..])
    }

    #[inline]
    pub fn range_to(&self, id: ID) -> IdSlice<ID, T> {
        IdSlice::new(&self.slice[..id.to_index()])
    }
}

impl<'l, ID: Identifier, T> ops::Index<ID> for IdSlice<'l, ID, T>
where
    T: 'l,
{
    type Output = T;
    #[inline]
    fn index<'a>(&'a self, id: ID) -> &'a T {
        &self.slice[id.to_index()]
    }
}



pub struct MutIdSlice<'l, ID: Identifier, T: 'l> {
    slice: &'l mut [T],
    _idtype: PhantomData<ID>,
}

impl<'l, ID: Identifier, T: 'l> MutIdSlice<'l, ID, T> {
    #[inline]
    pub fn new(slice: &'l mut [T]) -> MutIdSlice<'l, ID, T> {
        MutIdSlice {
            slice: slice,
            _idtype: PhantomData,
        }
    }

    #[inline]
    pub fn untyped(&mut self) -> &mut [T] {
        self.slice
    }

    #[inline]
    pub fn iter<'a>(&'a self) -> slice::Iter<'a, T> {
        self.slice.iter()
    }

    #[inline]
    pub fn iter_mut<'a>(&'a mut self) -> slice::IterMut<'a, T> {
        self.slice.iter_mut()
    }

    #[inline]
    pub fn range(&self, ids: IdRange<ID::Tag, ID::Handle>) -> IdSlice<ID, T> {
        IdSlice::new(&self.slice[ids.start.to_index()..ids.end.to_index()])
    }

    #[inline]
    pub fn mut_range(&mut self, ids: IdRange<ID::Tag, ID::Handle>) -> MutIdSlice<ID, T> {
        MutIdSlice::new(&mut self.slice[ids.start.to_index()..ids.end.to_index()])
    }

    #[inline]
    pub fn range_from(&self, id: ID) -> IdSlice<ID, T> {
        IdSlice::new(&self.slice[id.to_index()..])
    }

    #[inline]
    pub fn mut_range_from(&mut self, id: ID) -> MutIdSlice<ID, T> {
        MutIdSlice::new(&mut self.slice[id.to_index()..])
    }

    #[inline]
    pub fn range_to(&self, id: ID) -> IdSlice<ID, T> {
        IdSlice::new(&self.slice[..id.to_index()])
    }

    #[inline]
    pub fn mut_range_to(&mut self, id: ID) -> MutIdSlice<ID, T> {
        MutIdSlice::new(&mut self.slice[..id.to_index()])
    }
}

impl<'l, ID: Identifier, T: 'l> IntoIterator for IdSlice<'l, ID, T> {
    type Item = &'l T;
    type IntoIter = slice::Iter<'l, T>;
    #[inline]
    fn into_iter(self) -> slice::Iter<'l, T> {
        self.slice.iter()
    }
}

impl<'l, ID: Identifier, T: 'l> IntoIterator for MutIdSlice<'l, ID, T> {
    type Item = &'l mut T;
    type IntoIter = slice::IterMut<'l, T>;
    #[inline]
    fn into_iter(self) -> slice::IterMut<'l, T> {
        self.slice.iter_mut()
    }
}

impl<'l, ID: Identifier, T: 'l> ops::Index<ID> for MutIdSlice<'l, ID, T> {
    type Output = T;
    #[inline]
    fn index<'a>(&'a self, id: ID) -> &'a T {
        &self.slice[id.to_index()]
    }
}

impl<'l, ID: Identifier, T: 'l> ops::IndexMut<ID> for MutIdSlice<'l, ID, T> {
    #[inline]
    fn index_mut<'a>(&'a mut self, id: ID) -> &'a mut T {
        &mut self.slice[id.to_index()]
    }
}

#[test]
fn test_id_vector() {
    use super::*;

    #[derive(Debug)]
    struct T;

    fn id(i: u16) -> Id<T, u16> {
        Id::new(i)
    }

    let mut v = IdVec::new();
    let a = v.push(42 as u32);
    assert_eq!(v[a], 42);
    v.set(a, 0);
    assert_eq!(v[a], 0);

    v.set(id(10), 100);
    assert_eq!(v[id(10)], 100);

    v.set(id(5), 50);
    assert_eq!(v[id(5)], 50);

    v.set(id(20), 200);
    assert_eq!(v[id(20)], 200);
    assert_eq!(v.len(), 21);
}

#[test]
fn test_id_vector_u32() {
    let _: IdVec<u32, u32> = IdVec::new();
    let _: IdVec<i32, i32> = IdVec::new();
}