qcollect 0.3.0

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

use traits::*;

use qindex_multi::MultiIndexable;
use raw_vec::RawVec;
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::ops::{Deref, DerefMut, Index, IndexMut};
use std::{cmp, slice, mem, ptr};

enum SmallVecData<T, A>
    where A: FixedSizeArray<T>,
{
    Inline(A),
    Heap(RawVec<T>),
}

#[unsafe_no_drop_flag]
pub struct SmallVec<T, A>
    where A: FixedSizeArray<T>,
{
    len: usize,
    data: SmallVecData<T, A>,
}

impl<T, A> SmallVec<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 {
        SmallVec{
            len: Self::inline_capacity(),
            data: SmallVecData::Inline(array),
        }
    }

    /// Panics if _spilled_ or length doesn't match capacity.
    pub fn into_fixed(self) -> A {
        assert!(!self.spilled());
        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
    }

    /// Note that this might defeat the actual purpose of a `SmallVec`.
    pub fn with_capacity(cap: usize) -> Self {
        let mut ret = Self::new();
        if cap > Self::inline_capacity() {
            ret.reserve(cap);
        }
        ret
    }

    pub fn spilled(&self) -> bool {
        match self.data {
            SmallVecData::Inline(_) => false,
            SmallVecData::Heap(_) => true,
        }
    }

    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] {
        match &self.data {
            &SmallVecData::Inline(ref array) => unsafe {
                slice::from_raw_parts(array as *const A as *const T, self.len)
            },
            &SmallVecData::Heap(ref raw_vec) => unsafe {
                slice::from_raw_parts(raw_vec.ptr(), self.len)
            },
        }
    }

    #[inline]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        match &mut self.data {
            &mut SmallVecData::Inline(ref mut array) => unsafe {
                slice::from_raw_parts_mut(array as *const A as *mut T, self.len)
            },
            &mut SmallVecData::Heap(ref raw_vec) => unsafe {
                slice::from_raw_parts_mut(raw_vec.ptr() as *mut _, self.len)
            },
        }
    }

    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 {
        if mem::size_of::<T>() == 0 { return !0; }

        match self.data {
            SmallVecData::Inline(_) => Self::inline_capacity(),
            SmallVecData::Heap(ref raw_vec) => raw_vec.cap(),
        }
    }

    pub fn reserve(&mut self, additional: usize){
        if mem::size_of::<T>() == 0 { return }

        if !self.spilled() {
            // Move data from inline to heap.

            let old_ptr = self.as_mut_ptr();
            let raw_vec: RawVec<T> = RawVec::with_capacity(self.len + additional);
            unsafe { 
                ptr::copy_nonoverlapping(old_ptr, raw_vec.ptr() as *mut _, self.len); 
                ptr::write(&mut self.data, SmallVecData::Heap(raw_vec));
            }
        } else {
            match &mut self.data {
                &mut SmallVecData::Heap(ref mut raw_vec) => { 
                    raw_vec.reserve(self.len, additional); 
                }
                _ => unreachable!(),
            }
        }
    }

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

        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 SmallVec<T, A> 
    where A: FixedSizeArray<T>,
{
    fn drop(&mut self){
        if self.needs_drop() {
            self.clear();
            if !self.spilled() {
                unsafe { ptr::write(&mut self.data, SmallVecData::Heap(RawVec::new())); }
            }
        }
    }
}

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

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

impl<T, A> MutableCollection for SmallVec<T, A>
    where A: FixedSizeArray<T>,
{}

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

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

// impl -> trait impl
impl<T, A> ImmutableSequence<T> for SmallVec<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 SmallVec<T, A>
    where A: FixedSizeArray<T>,
{
    type IterMut = slice::IterMut<'a, T>;
}

// impl -> trait impl
impl<T, A> MutableSequence<T> for SmallVec<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 SmallVec<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> SmallVec<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 SmallVec<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 = SmallVec::new();
        Extend::extend(&mut ret, iter);
        ret
    }
}

impl<T, A> Extend<T> for SmallVec<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 SmallVec<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 SmallVec<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 SmallVec<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 SmallVec<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 SmallVec<T, A>
    where A: FixedSizeArray<T>,
{}

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

impl<T, A> Clone for SmallVec<T, A>
    where A: FixedSizeArray<T>, T: Clone,
{
    fn clone(&self) -> Self {
        SmallVec::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 SmallVec<T, A> 
    where A: FixedSizeArray<T>,
{
    fn default() -> Self { Self::new() }
}

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

impl<T, A> DerefMut for SmallVec<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 SmallVec<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 SmallVec<T, A>
    where T: Eq, A: FixedSizeArray<T>,
{}

impl<Rhs, T, A> PartialOrd<Rhs> for SmallVec<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 SmallVec<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 SmallVec<T, A> 
    where A: FixedSizeArray<T>,
{
    fn borrow(&self) -> &[T] { self.as_slice() }
}

impl<T, A> BorrowMut<[T]> for SmallVec<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 SmallVec<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 SmallVec<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 SmallVec<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 SmallVec<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 SmallVec<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::with_capacity(len);
            for i in 0..len {
                v.push(try!(d.read_seq_elt(i, |d| T::decode(d))));
            }
            Ok(v)
        })
    }
}

// ++++++++++++++++++++ Tests ++++++++++++++++++++

#[test]
fn push_n_spill_n_pop(){
    let mut v = SmallVec::<u8, [u8; 2]>::new();
    v.push(1);
    v.push(2);
    assert!(!v.spilled());
    v.push(3);
    assert!(v.spilled());
    v.push(4);
    assert_eq!(v.pop().unwrap(), 4);
    assert_eq!(v.pop().unwrap(), 3);
    assert_eq!(v.pop().unwrap(), 2);
    assert_eq!(v.pop().unwrap(), 1);
    assert!(v.spilled());
}

#[test]
fn clone(){
    let mut v = SmallVec::<u8, [u8; 4]>::new();
    Extend::extend(&mut v, vec![1, 2, 3, 4, 5]);

    let cloned = v.clone();
    assert_eq!(cloned.len(), 5);
    assert!(cloned.spilled());

    v.pop();
    let cloned = v.clone();
    assert_eq!(cloned.len(), 4);
    assert!(!cloned.spilled());
}