//! 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)
})
}
}