qcollect 0.3.0

//! 
//! ### TODO
//!
//! * Are zero-sized-types properly covered?
//! * IntoIterator
//! * impl From/Into-traits?
//! * index ranges

use traits::*;

use qindex_multi::MultiIndexable;
use core::array::FixedSizeArray;
use rustc_serialize::{self, Encodable, Decodable};

use std::borrow::{Borrow, BorrowMut};
use std::fmt::{self, Debug};
use std::hash::{self, Hash};
use std::iter::FromIterator;
use std::marker::PhantomData;
use std::ops::{Deref, DerefMut, Index, IndexMut};
use std::{cmp, slice, mem, ptr};

#[unsafe_no_drop_flag]
pub struct ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    len: usize,
    array: A,
    _phantom: PhantomData<T>,
}

impl<T, A> ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    pub fn inline_capacity() -> usize {
        mem::size_of::<A>() / mem::size_of::<T>()
    }

    pub fn from_fixed(array: A) -> Self {
        ArrayVec{
            len: Self::inline_capacity(),
            array: array,
            _phantom: PhantomData,
        }
    }

    /// Panics if length doesn't match capacity.
    pub fn into_fixed(self) -> A {
        assert!(self.len() == self.capacity());
        
        let ret = unsafe { ptr::read(self.as_ptr() as *const A) };
        mem::forget(self);
        ret
    }

    pub fn new() -> Self {
        let mut ret = Self::from_fixed(unsafe { mem::uninitialized() });
        ret.len = 0;
        ret
    }

    pub unsafe fn set_len(&mut self, len: usize){ self.len = len; }

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

    #[inline]
    pub fn as_slice(&self) -> &[T] {
        let len = self.len;
        self.array.as_slice().split_at(len).0
    }

    #[inline]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        let len = self.len;
        self.array.as_mut_slice().split_at_mut(len).0
    }

    pub fn as_ptr(&self) -> *const T { self.as_slice().as_ptr() }
    pub fn as_mut_ptr(&mut self) -> *mut T { self.as_mut_slice().as_mut_ptr() }

    pub fn capacity(&self) -> usize { Self::inline_capacity() }

    pub fn insert(&mut self, idx: usize, val: T){
        let len = self.len;
        assert!(idx <= len);

        unsafe { 
            let ptr = self.as_mut_ptr().offset(idx as isize);
            ptr::copy(ptr, ptr.offset(1), len - idx);
            ptr::write(ptr, val);
        }
        self.len += 1;
    }

    pub fn remove(&mut self, idx: usize) -> T {
        let len = self.len;
        assert!(idx < len);

        unsafe {
            let ptr = self.as_mut_ptr().offset(idx as isize);
            let ret = ptr::read(ptr);
            ptr::copy(ptr.offset(1), ptr, len - idx - 1);
            self.len -= 1;
            ret
        }
    }

    pub fn clear(&mut self) {
        for idx in 0..self.len {
            unsafe { ptr::read(self.as_ptr().offset(idx as isize)); }
        }
        self.len = 0;
    }
    
    fn needs_drop(&self) -> bool {
        self.len != mem::POST_DROP_USIZE
    }
}

impl<T, A> Drop for ArrayVec<T, A> 
    where A: FixedSizeArray<T>,
{
    fn drop(&mut self){
        if self.needs_drop() {
            self.clear();
        }
    }
}

// ++++++++++++++++++++ QCollect-stuff ++++++++++++++++++++

// impl -> trait impl
impl<T, A> ImmutableCollection for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    fn len(&self) -> usize { (*self).len() }
}

// impl -> trait impl
impl<T, A> MutableCollection for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{}

// impl -> trait impl
impl<T, A> GrowableCollection for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    fn capacity(&self) -> usize { Self::inline_capacity() }
    fn reserve(&mut self, _: usize){ /* */ }
    fn reserve_exact(&mut self, _: usize){ /* */ }
    fn clear(&mut self){ (*self).clear(); }
}

// impl -> trait impl
impl<'a, T, A> ImmutableSequenceTypes<'a, T> for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    type Iter = slice::Iter<'a, T>;
}

// impl -> trait impl
impl<T, A> ImmutableSequence<T> for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{    
    fn get<'a>(&'a self, idx: usize) -> Option<<Self as ImmutableSequenceTypes<'a, T>>::Output> { self.as_slice().get(idx) }

    fn iter<'a>(&'a self) -> <Self as ImmutableSequenceTypes<'a, T>>::Iter { self.as_slice().iter() }

}

// impl -> trait impl
impl<'a, T, A> MutableSequenceTypes<'a, T> for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    type IterMut = slice::IterMut<'a, T>;
}

// impl -> trait impl
impl<T, A> MutableSequence<T> for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    fn get_mut<'a>(&'a mut self, idx: usize) -> Option<&mut T>
        where Self: ImmutableSequenceTypes<'a, T, Output = &'a T>
    {
        self.as_mut_slice().get_mut(idx)
    }

    fn iter_mut<'a>(&'a mut self) -> <Self as MutableSequenceTypes<'a, T>>::IterMut
        where Self: ImmutableSequenceTypes<'a, T, Output = &'a T>
    {
        self.as_mut_slice().iter_mut()
    }

    fn swap(&mut self, a: usize, b: usize){
        self.as_mut_slice().swap(a, b);
    }

    fn sort_by<F>(&mut self, compare: F)
        where F: FnMut(&T, &T) -> cmp::Ordering
    {
        self.as_mut_slice().sort_by(compare);
    }
}

// impl -> trait impl
impl<T, A> GrowableSequence<T> for ArrayVec<T, A>
    where A: FixedSizeArray<T>, 
{
    fn insert(&mut self, idx: usize, val: T){ (*self).insert(idx, val); }
    fn remove(&mut self, idx: usize) -> T { (*self).remove(idx) }
}

// trait defaults -> impl
impl<T, A> ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    pub fn push(&mut self, val: T){ GrowableSequence::push(self, val); }
    pub fn pop(&mut self) -> Option<T> { GrowableSequence::pop(self) }
 }

// ++++++++++++++++++++ Iteration-stuff ++++++++++++++++++++

impl<T, A> FromIterator<T> for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    fn from_iter<I>(iterable: I) -> Self 
        where I: IntoIterator<Item = T>
    {
        let iter = iterable.into_iter();
        let mut ret = ArrayVec::new();
        Extend::extend(&mut ret, iter);
        ret
    }
}

impl<T, A> Extend<T> for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    fn extend<I>(&mut self, iterable: I) 
        where I: IntoIterator<Item = T>
    {
        extend_sequence(self, iterable)
    }
}

impl<'a, T, A> IntoIterator for &'a ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    type Item = &'a T;
    type IntoIter = slice::Iter<'a, T>;
    fn into_iter(self) -> Self::IntoIter { self.iter() }
}

impl<'a, T, A> IntoIterator for &'a mut ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    type Item = &'a mut T;
    type IntoIter = slice::IterMut<'a, T>;
    fn into_iter(self) -> Self::IntoIter { self.iter_mut() }
}

/* TODO
pub use std::vec::IntoIter;

impl<T, A> IntoIterator for SmallVec<T, A>
    where A: FixedSizeArray<T>,
{
    type Item = T;
    type IntoIter = IntoIter<T>;
    fn into_iter(mut self) -> Self::IntoIter {
        let vec = if !self.spilled() {
            let mut vec: Vec<T> = Vec::with_capacity(self.capacity());
            unsafe { 
                ptr::copy_nonoverlapping(self.as_mut_ptr(), vec.as_mut_ptr(), self.len); 
            }
            vec
        } else {
            unsafe {
                Vec::from_raw_parts(self.as_mut_ptr(), self.len, self.capacity())
            }
        };
        vec.into_iter()
    }
}*/

// ++++++++++++++++++++ Index-trait ++++++++++++++++++++

impl<T, A> Index<usize> for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    type Output = T;
    fn index(&self, idx: usize) -> &Self::Output { &self.as_slice()[idx] }
}

impl<T, A> IndexMut<usize> for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    fn index_mut(&mut self, idx: usize) -> &mut Self::Output { &mut self.as_mut_slice()[idx] }
}

// TODO index ranges

unsafe impl<T, A> MultiIndexable<usize> for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{}

// ++++++++++++++++++++ StdPrelude-traits ++++++++++++++++++++

impl<T, A> Clone for ArrayVec<T, A>
    where A: FixedSizeArray<T>, T: Clone,
{
    fn clone(&self) -> Self {
        ArrayVec::from_iter(self.as_slice().iter().cloned())
    }
    fn clone_from(&mut self, src: &Self){
        self.clear();
        Extend::extend(self, src.iter().cloned());
    }
}

impl<T, A> Default for ArrayVec<T, A> 
    where A: FixedSizeArray<T>,
{
    fn default() -> Self { Self::new() }
}

impl<T, A> Deref for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    type Target = [T];
    fn deref(&self) -> &Self::Target { self.as_slice() }
}

impl<T, A> DerefMut for ArrayVec<T, A>
    where A: FixedSizeArray<T>,
{
    fn deref_mut(&mut self) -> &mut Self::Target { self.as_mut_slice() }
}

impl<Rhs, T, A> PartialEq<Rhs> for ArrayVec<T, A>
    where Rhs: Borrow<[T]>, T: PartialEq, A: FixedSizeArray<T>,
{
    fn eq(&self, other: &Rhs) -> bool { self.as_slice() == other.borrow() }
}

impl<T, A> Eq for ArrayVec<T, A>
    where T: Eq, A: FixedSizeArray<T>,
{}

impl<Rhs, T, A> PartialOrd<Rhs> for ArrayVec<T, A>
    where Rhs: Borrow<[T]>, T: PartialOrd, A: FixedSizeArray<T>,
{ 
    fn partial_cmp(&self, other: &Rhs) -> Option<cmp::Ordering> {
        self.as_slice().partial_cmp(other.borrow())
    }
}

impl<T, A> Ord for ArrayVec<T, A>
    where T: Ord, A: FixedSizeArray<T>,
{ 
    fn cmp(&self, other: &Self) -> cmp::Ordering {
        self.as_slice().cmp(other.as_slice())
    }
}

// ++++++++++++++++++++ StdLib-traits ++++++++++++++++++++

impl<T, A> Borrow<[T]> for ArrayVec<T, A> 
    where A: FixedSizeArray<T>,
{
    fn borrow(&self) -> &[T] { self.as_slice() }
}

impl<T, A> BorrowMut<[T]> for ArrayVec<T, A> 
    where A: FixedSizeArray<T>,
{
    fn borrow_mut(&mut self) -> &mut [T] { self.as_mut_slice() }
}

impl<'a, T, A> From<&'a [T]> for ArrayVec<T, A> 
    where T: Clone, A: FixedSizeArray<T>,
{
    fn from(src: &'a [T]) -> Self {
        Self::from_iter(src.iter().cloned())
    }
}

impl<T, A> Hash for ArrayVec<T, A> 
    where T: Hash, A: FixedSizeArray<T>,
{
    fn hash<H>(&self, state: &mut H) 
        where H: hash::Hasher
    {
        self.as_slice().hash(state)    
    }
}

impl<T, A> Debug for ArrayVec<T, A> 
    where T: Debug, A: FixedSizeArray<T>,
{
    fn fmt(&self, formatter: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        self.as_slice().fmt(formatter)
    }
}

// ++++++++++++++++++++ Serialization-traits ++++++++++++++++++++

impl<T, A> Encodable for ArrayVec<T, A>
    where T: Encodable, A: FixedSizeArray<T>,
{
    fn encode<E>(&self, e: &mut E) -> Result<(), E::Error>
        where E: rustc_serialize::Encoder
    {
        self.as_slice().encode(e)
    }
}

impl<T, A> Decodable for ArrayVec<T, A>
    where T: Decodable, A: FixedSizeArray<T>,
{
    fn decode<D>(d: &mut D) -> Result<Self, D::Error>
        where D: rustc_serialize::Decoder
    {
        d.read_seq(|d, len| {
            let mut v = Self::new();
            for i in 0..len {
                v.push(try!(d.read_seq_elt(i, |d| T::decode(d))));
            }
            Ok(v)
        })
    }
}