qcollect 0.3.0

//! TODO FromIterator, Ranges/Bounds,
//!
//! TODO implement the usual set-methods: union, difference usw
//!
//! TODO serialization-stuff

use traits::*;

use rustc_serialize::{self, Encodable, Decodable};

use std::borrow::{Borrow, BorrowMut};
use std::fmt::{self, Debug};
use std::hash::{self, Hash};
use std::marker::PhantomData;
use std::slice;

/// Adapts a flat ordered set ontop of a linear memory store.
///
/// TODO Naming? Call this just `FlatSet`?
///
/// TODO default S to `Vec<T>`?
///
/// TODO use Sequence-traits instead of Borrow[Mut]
///      (difficulties with S::Output -> FlatSetAdaptor::[Output[Key|Val]|Iter]).
pub struct FlatSetAdaptor<T, S>
    where T: Ord, S: Borrow<[T]>
{
    storage: S,
    _phantom: PhantomData<T>,
}

impl<T, S> FlatSetAdaptor<T, S>
    where T: Ord, S: Default + Borrow<[T]>,
{
    /// Creates a new `FlatSetAdaptor` using `S::default()`.
    ///
    /// TODO remove this?
    pub fn new() -> Self {
        FlatSetAdaptor{
            storage: S::default(),
            _phantom: PhantomData,
        }
    }
}

impl<T, S> FlatSetAdaptor<T, S>
    where T: Ord, S: Borrow<[T]>,
{
    /// Creates a new `FlatSetAdaptor` from a storage which is already sorted.
    ///
    /// Panics if `storage` is not sorted or contains duplicates.
    pub fn from_sorted(storage: S) -> Self {
        {
            let iter = storage.borrow().iter();
            let mut inner_iter = iter.clone();

            for idx in iter {
                inner_iter.next();
                for inner_idx in inner_iter.clone() {
                    assert!(idx < inner_idx, "storage is not sorted or contains duplicates!");
                }
            }
        }

        FlatSetAdaptor{
            storage: storage,
            _phantom: PhantomData,
        }
    }
}

impl<T, S> FlatSetAdaptor<T, S>
    where T: Ord, S: BorrowMut<[T]>,
{
    /// Creates a new `FlatSetAdaptor` from an unsorted storage.
    ///
    /// The storage will be sorted.
    ///
    /// TODO: test if there are duplicates
    pub fn from_unsorted(mut storage: S) -> Self {
        storage.borrow_mut().sort();
        FlatSetAdaptor{
            storage: storage,
            _phantom: PhantomData,
        }
    }
}

impl<T, S> FlatSetAdaptor<T, S>
    where T: Ord, S: Borrow<[T]>,
{
    pub fn into_inner(self) -> S {
        self.storage
    }
    pub fn as_slice(&self) -> &[T] {
        self.storage.borrow()
    }

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

    pub fn contains<Q: ?Sized>(&self, key: &Q) -> bool
        where Q: Ord, T: Borrow<Q>
    {
        // TODO use binary search
        for k in self.storage.borrow() { 
            if k.borrow() == key { return true }
        }
        false
    }

    pub fn iter(&self) -> slice::Iter<T> {
        self.storage.borrow().iter()
    }
}

impl<T, S> FlatSetAdaptor<T, S>
    where T: Ord, S: GrowableSequence<T> + BorrowMut<[T]>
{
    pub fn capacity(&self) -> usize {
        self.storage.capacity()
    }

    pub fn reserve(&mut self, additional: usize){ 
        self.storage.reserve(additional);
    }
    pub fn reserve_exact(&mut self, additional: usize){
        self.storage.reserve_exact(additional);
    }

    pub fn insert(&mut self, key: T) -> bool {
        match self.as_slice().binary_search_by(|k| key.cmp(k.borrow())){
            Ok(_) => false,
            Err(pos) => { self.storage.insert(pos, key); true }
        }
    }
    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> bool
        where Q: Ord, T: Borrow<Q>
    {
        match self.as_slice().binary_search_by(|k| key.cmp(k.borrow())){
            Ok(pos) => { self.storage.remove(pos); true }
            Err(_) => false
        }
    }

    pub fn clear(&mut self){
        self.storage.clear();
    }
}

// ++++++++++++++++++++ QCollect-Stuff ++++++++++++++++++++

// impl -> trait impl
impl<T, S> ImmutableCollection for FlatSetAdaptor<T, S> 
    where T: Ord, S: Borrow<[T]>,
{
    fn len(&self) -> usize { (*self).len() }
}

// impl -> trait impl
impl<T, S> MutableCollection for FlatSetAdaptor<T, S> 
    where T: Ord, S: BorrowMut<[T]>,
{}

// impl -> trait impl
impl<T, S> GrowableCollection for FlatSetAdaptor<T, S> 
    where T: Ord, S: GrowableSequence<T> + BorrowMut<[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, S> ImmutableSetTypes<'a, T> for FlatSetAdaptor<T, S>
    where T: Ord, S: Borrow<[T]>
{
    type Iter = slice::Iter<'a, T>;
}

// impl -> trait impl
impl<T, Q: ?Sized, S> ImmutableSet<T, Q> for FlatSetAdaptor<T, S>
    where Q: Ord, T: Borrow<Q> + Ord, S: Borrow<[T]>
{
    fn contains<'a>(&'a self, val: &Q) -> bool { (*self).contains(val) }
    fn iter<'a>(&'a self) -> <Self as ImmutableSetTypes<'a, T>>::Iter { (*self).iter() }
}

// impl -> trait impl
impl<T, Q: ?Sized, S> GrowableSet<T, Q> for FlatSetAdaptor<T, S>
    where Q: Ord, T: Borrow<Q> + Ord, S: GrowableSequence<T> + BorrowMut<[T]>
{
    fn insert(&mut self, val: T) -> bool { (*self).insert(val) }
    fn remove(&mut self, val: &Q) -> bool { (*self).remove(val) }
}

// trait defaults -> impl
impl<T, S> FlatSetAdaptor<T, S>
    where T: Ord, S: Borrow<[T]>,
{
    pub fn is_empty(&self) -> bool { ImmutableCollection::is_empty(self) }
}

// ++++++++++++++++++++ Iteration-Stuff ++++++++++++++++++++

// TODO FromIterator

impl<T, S> Extend<T> for FlatSetAdaptor<T, S>
    where T: Ord, S: GrowableSequence<T> + BorrowMut<[T]>
{
    fn extend<I>(&mut self, iterable: I) 
        where I: IntoIterator<Item = T>
    {
        extend_set(self, iterable)
    }
}

impl<'a, T, S> IntoIterator for &'a FlatSetAdaptor<T, S> 
    where T: Ord, S: Borrow<[T]>,
{
    type Item = &'a T;
    type IntoIter = slice::Iter<'a, T>;
    fn into_iter(self) -> Self::IntoIter { self.iter() }
}

impl<T, S> IntoIterator for FlatSetAdaptor<T, S> 
    where T: Ord, S: IntoIterator<Item = T> + Borrow<[T]>,
{
    type Item = T;
    type IntoIter = S::IntoIter;
    fn into_iter(self) -> Self::IntoIter { self.storage.into_iter() }
}

// ++++++++++++++++++++ StdPrelude-Stuff ++++++++++++++++++++

impl<T, S> Clone for FlatSetAdaptor<T, S>
    where T: Ord, S: Clone + Borrow<[T]>,
{
    fn clone(&self) -> Self {
        FlatSetAdaptor::from_sorted(self.storage.clone())
    }
    fn clone_from(&mut self, src: &Self){
        self.storage.clone_from(&src.storage);
    }
}

impl<T, S> Default for FlatSetAdaptor<T, S>
    where T: Ord, S: Default + Borrow<[T]>,
{
    fn default() -> Self { Self::new() }
}

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

impl<T, S> Eq for FlatSetAdaptor<T, S>
    where T: Ord, S: Borrow<[T]>,
{}

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

impl<T, S> Ord for FlatSetAdaptor<T, S>
    where T: Ord, S: Borrow<[T]>,
{ 
    fn cmp(&self, other: &Self) -> ::std::cmp::Ordering {
        self.as_slice().cmp(other.as_slice())
    }
}

// ++++++++++++++++++++ StdLib-Stuff ++++++++++++++++++++

impl<T, S> Borrow<[T]> for FlatSetAdaptor<T, S>
    where T: Ord, S: Borrow<[T]>,
{
    fn borrow(&self) -> &[T] { self.as_slice() }
}

impl<T, S> Hash for FlatSetAdaptor<T, S>
    where T: Hash + Ord, S: Borrow<[T]>,
{
    fn hash<H>(&self, state: &mut H) 
        where H: hash::Hasher
    {
        self.as_slice().hash(state)    
    }
}

impl<T, S> Debug for FlatSetAdaptor<T, S>
    where T: Debug + Ord, S: Borrow<[T]>,
{
    fn fmt(&self, formatter: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        self.as_slice().fmt(formatter)
    }
}

// ++++++++++++++++++++ Serialization-Stuff ++++++++++++++++++++

/// TODO should this only implemented if `S: VecLike<T>`?
impl<T, S> Encodable for FlatSetAdaptor<T, S>
    where T: Encodable + Ord, S: Borrow<[T]>
{
    fn encode<E: rustc_serialize::Encoder>(&self, e: &mut E) -> Result<(), E::Error> {
        self.storage.borrow().encode(e)
    }
}

impl<T, S> Decodable for FlatSetAdaptor<T, S>
    where T: Decodable + Ord, S: Default + GrowableSequence<T> + BorrowMut<[T]>
{
    fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<Self, D::Error> {
        d.read_map(|d, len| {
            let mut set = Self::new();
            for idx in 0..len {
                set.insert(try!{d.read_seq_elt(idx, |d| Decodable::decode(d))});
            }
            Ok(set)
        })
    }
}