qcollect 0.3.0

Collections; Collection-Traits.
//! TODO FromIterator, Ranges/Bounds,
//!
//! TODO serialization-stuff

use traits::*;

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

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

/// Adapts a flat ordered map 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 -> FlatMapAdaptor::[Output|Iter]).
pub struct FlatMapAdaptor<K, V, S>
    where K: Ord, S: Borrow<[(K, V)]>,
{
    storage: S,
    _phantom: PhantomData<(K, V)>,
}

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

    /// Creates a new `FlatMapAdaptor` from a storage which is already sorted.
    ///
    /// Panics if `storage` is not sorted.
    ///
    /// TODO: test if there are duplicates
    pub fn from_sorted(storage: S) -> Self {
        {
            let iter = storage.borrow().iter();
            let mut inner_iter = iter.clone();

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

        FlatMapAdaptor{
            storage: storage,
            _phantom: PhantomData,
        }
    }

    pub fn into_inner(self) -> S {
        self.storage
    }

    pub fn as_slice(&self) -> &[(K, V)] 
        where S: Borrow<[(K, V)]>
    {
        self.storage.borrow()
    }

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

    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
        where Q: Ord, K: Borrow<Q>
    {
        //TODO use binary search
        for &(ref k, ref v) in self.storage.borrow() {
            if k.borrow() == key { return Some(v) }
        }
        None
    }

    pub fn iter(&self) -> Iter<K, V> {
        //FIXME vvv uncomment this, see next FIXME-comment vvv
        /*fn map_fn<A, B>(&(ref a, ref b): &(A, B)) -> (&A, &B) {
            (a, b)
        }
        self.storage.borrow().iter().map(map_fn)*/
        self.storage.borrow().iter().map(_IterMapFn)
    }
}

// FIXME workaround for raw fns not implementing Clone.
//       relevant issue: https://github.com/rust-lang/rust/issues/24000
#[derive(Clone)]
pub struct _IterMapFn;

impl<'a, K, V> FnOnce<(&'a (K, V),)> for _IterMapFn {
    type Output = (&'a K, &'a V);
    extern "rust-call" fn call_once(self, (args,): (&'a (K, V),)) -> Self::Output {
        (&args.0, &args.1)
    }
}

impl<'a, K, V> FnMut<(&'a (K, V),)> for _IterMapFn {
    extern "rust-call" fn call_mut(&mut self, (args,): (&'a (K, V),)) -> Self::Output {
        (&args.0, &args.1)
    }
}

pub type Iter<'a, K, V>
    where K: Ord
= iter::Map<slice::Iter<'a, (K, V)>, _IterMapFn>;

// FIXME ^^^ this should replace above code ^^^
/*pub type Iter<'a, K, V>
    where K: Ord
= iter::Map<slice::Iter<'a, (K, V)>, fn(&(K, V)) -> (&K, &V)>;*/

impl<K, V, S> FlatMapAdaptor<K, V, S>
    where K: Ord, S: BorrowMut<[(K, V)]>,
{
    /// Creates a new `FlatMapAdaptor` from an unsorted storage.
    ///
    /// The storage will be sorted.
    ///
    /// TODO: test if there are duplicates. also: what do if there are duplicates?
    pub fn from_unsorted(mut storage: S) -> Self
        where S: BorrowMut<[(K, V)]>,
    {
        storage.borrow_mut().sort_by(|&(ref k1, _), &(ref k2, _)| k1.cmp(k2));
        FlatMapAdaptor{
            storage: storage,
            _phantom: PhantomData,
        }
    }

    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
        where Q: Ord, K: Borrow<Q>
    {
        //TODO use binary search
        for &mut(ref k, ref mut v) in self.storage.borrow_mut() {
            if k.borrow() == key { return Some(v) }
        }
        None
    }

    pub fn iter_mut(&mut self) -> IterMut<K, V> {
        fn map_fn<A, B>(&mut(ref a, ref mut b): &mut(A, B)) -> (&A, &mut B) {
            (a, b)
        }
        self.storage.borrow_mut().iter_mut().map(map_fn)
    }
}

pub type IterMut<'a, K, V> 
    where K: Ord
= iter::Map<slice::IterMut<'a, (K, V)>, fn(&mut (K, V)) -> (&K, &mut V)>;

impl<K, V, S> FlatMapAdaptor<K, V, S>
    where K: Ord, S: GrowableSequence<(K, V)> + BorrowMut<[(K, V)]>
{
    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: K, val: V) -> Option<V> {
        match self.storage.binary_search_by(|&(ref k, _)| key.cmp(k.borrow())){
            Ok(pos) => {
                Some(mem::replace(&mut self.storage.borrow_mut()[pos].1, val))
            }
            Err(pos) => { 
                self.storage.insert(pos, (key, val));
                None
            }
        }
    }
    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
        where Q: Ord, K: Borrow<Q>
    {
        match self.storage.binary_search_by(|&(ref k, _)| key.cmp(k.borrow())){
            Ok(pos) => Some(self.storage.remove(pos).1),
            Err(_) => None
        }
    }

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


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

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

// impl -> trait impl
impl<K, V, S> MutableCollection for FlatMapAdaptor<K, V, S> 
    where K: Ord, S: BorrowMut<[(K, V)]>,
{}

// impl -> trait impl
impl<K, V, S> GrowableCollection for FlatMapAdaptor<K, V, S> 
    where K: Ord, S: GrowableSequence<(K, V)> + BorrowMut<[(K, V)]>,
{
    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, K, V, S> ImmutableMapTypes<'a, K, V> for FlatMapAdaptor<K, V, S>
    where K: Ord, S: Borrow<[(K, V)]>
{
    type Iter = Iter<'a, K, V>;
}

// impl -> trait impl
impl<K, V, Q: ?Sized, S> ImmutableMap<K, V, Q> for FlatMapAdaptor<K, V, S>
    where Q: Ord, K: Borrow<Q> + Ord, S: Borrow<[(K, V)]>
{
    fn get<'a>(&'a self, key: &Q) -> Option<<Self as ImmutableMapTypes<'a, K, V>>::OutputVal> { (*self).get(key) }
    fn iter<'a>(&'a self) -> <Self as ImmutableMapTypes<'a, K, V>>::Iter { (*self).iter() }
}

// impl -> trait impl
impl<'a, K, V, S> MutableMapTypes<'a, K, V> for FlatMapAdaptor<K, V, S>
    where K: Ord, S: BorrowMut<[(K, V)]>
{
    type IterMut = IterMut<'a, K, V>;
}

impl<K, V, Q: ?Sized, S> MutableMap<K, V, Q> for FlatMapAdaptor<K, V, S>
    where Q: Ord, K: Borrow<Q> + Ord, S: BorrowMut<[(K, V)]>
{
    fn get_mut<'a>(&'a mut self, key: &Q) -> Option<&mut V>
        where Self: ImmutableMapTypes<'a, K, V, OutputVal = &'a V>
    { self.get_mut(key) }

    fn iter_mut<'a>(&'a mut self) -> <Self as MutableMapTypes<'a, K, V>>::IterMut
        where Self: ImmutableMapTypes<'a, K, V, OutputVal = &'a V>
    { self.iter_mut() }
}

// impl -> trait impl
impl<K, V, Q: ?Sized, S> GrowableMap<K, V, Q> for FlatMapAdaptor<K, V, S>
    where Q: Ord, K: Borrow<Q> + Ord, S: GrowableSequence<(K, V)> + BorrowMut<[(K, V)]>
{
    fn insert(&mut self, key: K, val: V) -> Option<V> { (*self).insert(key, val) }
    fn remove(&mut self, key: &Q) -> Option<V> { (*self).remove(key) }
}

// trait defaults -> impl
impl<K, V, S> FlatMapAdaptor<K, V, S>
    where K: Ord, S: Borrow<[(K, V)]>
{
    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
        where Q: Ord, K: Borrow<Q>
    {
        ImmutableMap::contains_key(self, key)
    }
}

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

// TODO FromIterator

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

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

impl<'a, K, V, S> IntoIterator for &'a mut FlatMapAdaptor<K, V, S> 
    where K: Ord, S: BorrowMut<[(K, V)]>,
{
    type Item = (&'a K, &'a mut V);
    type IntoIter = IterMut<'a, K, V>;
    fn into_iter(self) -> Self::IntoIter { self.iter_mut() }
}

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

// ++++++++++++++++++++ Indexing-Stuff ++++++++++++++++++++

impl<'a, Q: ?Sized, K, V, S> Index<&'a Q> for FlatMapAdaptor<K, V, S> 
    where Q: Ord, K: Borrow<Q> + Ord, S: Borrow<[(K, V)]>,
{
    type Output = V;
    fn index(&self, key: &Q) -> &V { self.get(key).unwrap() }
}

impl<'a, Q: ?Sized, K, V, S> IndexMut<&'a Q> for FlatMapAdaptor<K, V, S> 
    where Q: Ord, K: Borrow<Q> + Ord, S: BorrowMut<[(K, V)]>,
{
    fn index_mut(&mut self, key: &Q) -> &mut V { self.get_mut(key).unwrap() }
}

// TODO index ranges

unsafe impl<'a, K, V, Q: ?Sized, S> MultiIndexable<&'a Q> for FlatMapAdaptor<K, V, S>
    where Q: Ord, K: Borrow<Q> + Ord, S: MultiIndexable<usize> + BorrowMut<[(K, V)]>
{}

// ++++++++++++++++++++ Prelude-Stuff ++++++++++++++++++++

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

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

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

impl<K, V, S> Eq for FlatMapAdaptor<K, V, S>
    where K: Ord, V: Eq, S: Borrow<[(K, V)]>,
{}

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

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

// ++++++++++++++++++++ Std-Stuff ++++++++++++++++++++

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

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

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

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

/// TODO should this only implemented if `S: Default + VecLike<T>`?
impl<K, V, S> Encodable for FlatMapAdaptor<K, V, S>
    where K: Encodable + Ord, V: Encodable, S: Borrow<[(K, V)]>
{
    fn encode<E: rustc_serialize::Encoder>(&self, e: &mut E) -> Result<(), E::Error> {
        e.emit_map(self.len(), |e| {
            for (idx, (key, val)) in self.iter().enumerate() {
                try!{e.emit_map_elt_key(idx, |e| key.encode(e))};
                try!{e.emit_map_elt_val(idx, |e| val.encode(e))};
            }
            Ok(())
        })
    }
}

impl<K, V, S> Decodable for FlatMapAdaptor<K, V, S>
    where K: Decodable + Ord, 
          V: Decodable,  
          S: Default + GrowableSequence<(K, V)> + BorrowMut<[(K, V)]>
{
    fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<Self, D::Error> {
        d.read_map(|d, len| {
            let mut map = Self::new();
            for idx in 0..len {
                let key = try!{d.read_map_elt_key(idx, |d| Decodable::decode(d))};
                let val = try!{d.read_map_elt_val(idx, |d| Decodable::decode(d))};
                map.insert(key, val);
            }
            Ok(map)
        })
    }
}