qecs 0.0.7

/// ### TODO
///
/// * make maximum-id-count configurable
/// * make min-freed-indicies configurable

use qecs_core::{
    Component, Id, IdWithIndex, Valid, PrimaryIdManager, 
    IdActivationError, IdActivationResult, IdGenerationError, IdGenerationResult,
    _PrimaryIdManager,
};

use num::{Unsigned, NumCast, ToPrimitive, Bounded};

use std::any::Any;
use std::collections::LinkedList;
use std::fmt::Debug;
use std::hash::Hash;
use std::marker::PhantomData;
use std::{cmp, iter, slice, mem};

// ++++++++++++++++++++ SimpleIndex ++++++++++++++++++++

pub trait SimpleIndex: IdWithIndex + From<usize> {}

impl<T> SimpleIndex for T 
    where T: IdWithIndex + From<usize>
{}

// ++++++++++++++++++++ Index ++++++++++++++++++++

#[derive(RustcEncodable, RustcDecodable)]
#[derive(Debug, Hash, Clone, Copy, PartialOrd, Ord, PartialEq, Eq)]
pub struct Index<U>(U);

impl<U, T> From<T> for Index<U>
where 
    U: Unsigned + NumCast + Bounded + Debug + Hash + Copy + Ord + Any + Send + Sync,
    T: Unsigned + ToPrimitive,
{
    fn from(val: T) -> Self { 
        Index(U::from(val).expect("Maximum id count exceeded.")) // TODO errmsg?
    }
}

// FIXME
/*impl<U> Into<U> for Index<U>
    where U: Unsigned + NumCast + Bounded + Debug + Hash + Copy + Ord + Any + Send + Sync
{
    fn into(self) -> U { self.0 }
}*/

impl<U> Component for Index<U>
    where U: Unsigned + NumCast + Bounded + Debug + Hash + Copy + Ord + Any + Send + Sync
{}

impl<U> Id for Index<U>
    where U: Unsigned + NumCast + Bounded + Debug + Hash + Copy + Ord + Any + Send + Sync
{}

impl<U> IdWithIndex for Index<U>
    where U: Unsigned + NumCast + Bounded + Debug + Hash + Copy + Ord + Any + Send + Sync
{
    fn max_index() -> usize { U::max_value().to_usize().unwrap() }
    fn index(&self) -> usize { self.0.to_usize().unwrap() }
}

pub type Index8 = Index<u8>;
pub type Index16 = Index<u16>;
pub type Index32 = Index<u32>;

// ++++++++++++++++++++ SimpleIndexManager ++++++++++++++++++++

pub struct SimpleIndexManager<MID, Extra = ()> {
    data: Vec<Option<Extra>>,
    freed_indicies: LinkedList<MID>,
}

impl<MID, Extra> Default for SimpleIndexManager<MID, Extra>
    where MID: SimpleIndex, Extra: Copy + Any + Send + Sync
{
    fn default() -> Self {
        SimpleIndexManager {
            data: Vec::new(),
            freed_indicies: LinkedList::new(),
        }
    }
}

// NOTE: Why not put this code directly into the `PrimaryIdManager`-impl?
// Well, we wanna add `SecondaryIdManager` at some point, which will wrap this 
// functionality like `PrimaryIdManager` does now.
impl<MID, Extra> SimpleIndexManager<MID, Extra> 
    where MID: SimpleIndex, Extra: Copy + Eq + Any + Send + Sync
{
    fn _len(&self) -> usize {
        self.data.len() - self.freed_indicies.len() 
    }

    fn _maximum_id_count(&self) -> usize { 
        MID::max_index() + 1
    }

    fn _validate(&self, m_id: MID) -> Option<&Extra> {
        match self.data.get(m_id.index()){
            Some(&Some(ref extra)) => Some(extra),
            _ => None
        }
    }

    fn _invalidate(&mut self, m_id: MID) -> Option<Extra> {
        if self._validate(m_id).is_none() { return None }
        self.freed_indicies.push_back(m_id);
        mem::replace(&mut self.data[m_id.index()], None)
    }

    fn _generate(&mut self, extra: Extra) -> IdGenerationResult<MID> {
        let min_freed_indicies = cmp::min(1024, self._maximum_id_count()); // TODO make this

        // TODO the second condition is quite confusing...
        if self.freed_indicies.len() >= min_freed_indicies
            || (!self.freed_indicies.is_empty() && self._len() == self._maximum_id_count())
        {
            // re-used a freed id

            let prev_id = self.freed_indicies.pop_front().unwrap();
            self.data[prev_id.index()] = Some(extra);
            Ok(prev_id)
        } else {
            // generate a new id

            let idx = self.data.len();
            if idx >= self._maximum_id_count() {
                return Err(IdGenerationError::MaximumIdCountReached(MID::max_index() + 1));
            }
            self.data.push(Some(extra));

            Ok(MID::from(idx))
        }
    }

    fn _activate(&mut self, id: MID, extra: Extra) -> IdActivationResult<(), (MID, Extra)> {
        let idx = id.index();

        match self.data.get(id.index()) {
            Some(&Some(occ_extra)) => if occ_extra == extra {
                return Err(IdActivationError::AlreadyActivated)
            } else {
                return Err(IdActivationError::SlotOccupied((id, occ_extra)))
            },
            _ => {}
        }

        if idx < self.data.len() {
            // activate a freed id

            let pos = self.freed_indicies.iter().position(|freed_id| {
                freed_id.index() == idx
            }).unwrap();

            // TODO is there a better way of doing this?
            let mut tail = self.freed_indicies.split_off(pos);
            tail.pop_front();
            self.freed_indicies.append(&mut tail);

            self.data[idx] = Some(extra)
        } else {
            // activate a new id

            if idx >= self._maximum_id_count() {
                return Err(IdActivationError::MaximumIdCountReached(MID::max_index() - 1));
            }

            for idx in self.data.len()..idx {
                self.data.push(None);
                self.freed_indicies.push_back(MID::from(idx));
            }
            self.data.push(Some(extra));
        }

        Ok(())
    }

    fn _clear(&mut self){ 
        self.data.clear();
        self.freed_indicies.clear();
    }
}

#[derive(Clone)]
pub struct Iter<'a, MID> 
    where MID: SimpleIndex, 
{
    iter: iter::Enumerate<slice::Iter<'a, Option<()>>>,
    _phantom: PhantomData<MID>
}

impl<'a, MID> Iterator for Iter<'a, MID> 
    where MID: SimpleIndex,
{
    type Item = Valid<'a, MID>;
    fn next(&mut self) -> Option<Self::Item> {
        match self.iter.next() {
            Some((idx, &Some( _))) => unsafe { Some(Valid::new(MID::from(idx))) },
            Some((_, &None)) => self.next(),
            None => None
        }
    }
}

// TODO impl ExactSizeIterator, DoubleEndedIterator

impl<'a, MID> _PrimaryIdManager<'a> for SimpleIndexManager<MID> 
    where MID: SimpleIndex
{
    type _Id = MID;

    type Iter = Iter<'a, MID>;
}

impl<MID> PrimaryIdManager for SimpleIndexManager<MID> 
    where MID: SimpleIndex
{
    type Id = MID;

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

    fn maximum_id_count(&self) -> usize { self._maximum_id_count() }

    fn validate(&self, id: Self::Id) -> Option<Valid<Self::Id>> {
       self._validate(id).map(|_| unsafe { Valid::new(id) })
    }

    unsafe fn invalidate(&mut self, m_id: Self::Id) -> bool {
        self._invalidate(m_id).is_some()
    }

    fn generate(&mut self) -> IdGenerationResult<Valid<Self::Id>> {
        let id = try!{self._generate(())};
        Ok(self.validate(id).unwrap())
    }

    fn activate(&mut self, id: Self::Id) -> IdActivationResult<Valid<Self::Id>, Self::Id> {
        match self._activate(id, ()) {
            Err(IdActivationError::SlotOccupied(_)) => {
                return Err(IdActivationError::SlotOccupied(id))
            }
            Err(err) => { return Err(IdActivationError::from_err(err)); }
            Ok(_) => {}
        }
        Ok(self.validate(id).unwrap())
    }

    unsafe fn clear(&mut self){ self._clear(); }

    fn iter<'a>(&'a self) -> <Self as _PrimaryIdManager<'a>>::Iter {
        Iter{ iter: self.data.iter().enumerate(), _phantom: PhantomData }
    }
}

impl<'a, MID> IntoIterator for &'a SimpleIndexManager<MID> 
    where MID: SimpleIndex
{
    type Item = <Self::IntoIter as Iterator>::Item;
    type IntoIter = Iter<'a, MID>;
    fn into_iter(self) -> Self::IntoIter { self.iter() }
}

#[test]
fn generate_ids(){
    let mut ids = SimpleIndexManager::<Index8>::default();

    let zero = Index8::from(0u8);
    let one = Index8::from(1u8);

    assert_eq!(zero, *ids.generate().unwrap());
    assert_eq!(one, *ids.generate().unwrap());
    assert_eq!(2, ids.len());
    assert!(unsafe { ids.invalidate(zero) });
    assert_eq!(1, ids.len());

    unsafe { ids.clear(); }
    assert_eq!(ids.len(), 0);

    let mut gens = Vec::new();
    for _ in 0..Index8::max_index() + 1 {
        gens.push(*ids.generate().unwrap());
    }
    assert_eq!(
        IdGenerationError::MaximumIdCountReached(Index8::max_index() + 1),
        ids.generate().unwrap_err()
    );

    for id in gens {
        assert!(unsafe { ids.invalidate(id) });
    }
    assert_eq!(0, ids.len());
    assert_eq!(zero, *ids.generate().unwrap());

}