use core::mem;
use core::fmt;
use core::slice;
use core::borrow::Borrow;
use core::ops::{Bound, RangeBounds};

#[cfg(feature = "std")]
use std::collections::BTreeMap;
#[cfg(feature = "std")]
use std::collections::btree_map::{Iter as BTreeIter, IterMut as BTreeIterMut,
                                  Range as BTreeRange};
#[cfg(all(feature = "alloc", not(feature = "std")))]
use alloc::collections::btree_map::BTreeMap;
#[cfg(all(feature = "alloc", not(feature = "std")))]
use alloc::collections::btree_map::{Iter as BTreeIter, IterMut as BTreeIterMut,
                                    Range as BTreeRange};

/// A managed map.
///
/// This enum can be used to represent exclusive access to maps.
/// In Rust, exclusive access to an object is obtained by either owning the object,
/// or owning a mutable pointer to the object; hence, "managed".
///
/// The purpose of this enum is providing good ergonomics with `std` present while making
/// it possible to avoid having a heap at all (which of course means that `std` is not present).
/// To achieve this, the variants other than `Borrow` are only available when the corresponding
/// feature is opted in.
///
/// Unlike [Managed](enum.Managed.html) and [ManagedSlice](enum.ManagedSlice.html),
/// the managed map is implemented using a B-tree map when allocation is available,
/// and a sorted slice of key-value pairs when it is not. Thus, algorithmic complexity
/// of operations on it depends on the kind of map.
///
/// A function that requires a managed object should be generic over an `Into<ManagedMap<'a, T>>`
/// argument; then, it will be possible to pass either a `Vec<T>`, or a `&'a mut [T]`
/// without any conversion at the call site.
///
/// See also [Managed](enum.Managed.html).
pub enum ManagedMap<'a, K: 'a, V: 'a> {
    /// Borrowed variant.
    Borrowed(&'a mut [Option<(K, V)>]),
    /// Owned variant, only available with the `std` or `alloc` feature enabled.
    #[cfg(any(feature = "std", feature = "alloc"))]
    Owned(BTreeMap<K, V>)
}

impl<'a, K: 'a, V: 'a> fmt::Debug for ManagedMap<'a, K, V>
        where K: fmt::Debug, V: fmt::Debug {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            &ManagedMap::Borrowed(ref x) => write!(f, "Borrowed({:?})", x),
            #[cfg(any(feature = "std", feature = "alloc"))]
            &ManagedMap::Owned(ref x)    => write!(f, "Owned({:?})", x)
        }
    }
}

impl<'a, K: 'a, V: 'a> From<&'a mut [Option<(K, V)>]> for ManagedMap<'a, K, V> {
    fn from(value: &'a mut [Option<(K, V)>]) -> Self {
        ManagedMap::Borrowed(value)
    }
}

#[cfg(any(feature = "std", feature = "alloc"))]
impl<'a, K: 'a, V: 'a> From<BTreeMap<K, V>> for ManagedMap<'a, K, V> {
    fn from(value: BTreeMap<K, V>) -> Self {
        ManagedMap::Owned(value)
    }
}

/// Like `Option`, but with `Some` values sorting first.
#[derive(PartialEq, Eq, PartialOrd, Ord)]
enum RevOption<T> {
    Some(T),
    None
}

impl<T> From<Option<T>> for RevOption<T> {
    fn from(other: Option<T>) -> Self {
        match other {
            Some(x) => RevOption::Some(x),
            None => RevOption::None
        }
    }
}

impl<T> Into<Option<T>> for RevOption<T> {
    fn into(self) -> Option<T> {
        match self {
            RevOption::Some(x) => Some(x),
            RevOption::None => None
        }
    }
}

#[derive(Debug, Clone)]
enum RangeInner<'a, K: 'a, V: 'a> {
    /// Borrowed variant.
    Borrowed { slice: &'a [Option<(K, V)>], begin: usize, end: usize },
    /// Owned variant, only available with the `std` or `alloc` feature enabled.
    #[cfg(any(feature = "std", feature = "alloc"))]
    Owned(BTreeRange<'a, K, V>),
}

#[derive(Debug, Clone)]
pub struct Range<'a, K: 'a, V: 'a>(RangeInner<'a, K, V>);

impl<'a, K: 'a, V: 'a> Iterator for Range<'a, K, V> {
    type Item = (&'a K, &'a V);

    fn next(&mut self) -> Option<Self::Item> {
        match self.0 {
            RangeInner::Borrowed { ref slice, ref mut begin, ref end } => {
                *begin += 1;
                if *begin-1 >= *end {
                    None
                } else {
                    match slice[*begin-1] {
                        None => None,
                        Some((ref k, ref v)) => Some((k, v))
                    }
                }
            },
            #[cfg(any(feature = "std", feature = "alloc"))]
            RangeInner::Owned(ref mut range) => range.next(),
        }
    }
}

impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Range<'a, K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        match self.0 {
            RangeInner::Borrowed { ref slice, ref begin, ref mut end } => {
                if *begin >= *end {
                    None
                } else {
                    *end -= 1;
                    match slice[*end] {
                        None => None,
                        Some((ref k, ref v)) => Some((k, v))
                    }
                }
            },
            #[cfg(any(feature = "std", feature = "alloc"))]
            RangeInner::Owned(ref mut range) => range.next_back(),
        }
    }
}

fn binary_search_by_key_range<'a, K, V, Q: 'a, R>(slice: &[Option<(K, V)>], range: R) -> Result<(usize, usize), ()>
    where K: Ord + Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>
{
    if slice.len() == 0 {
        return Err(())
    }
    let (mut left, mut right) = (0, slice.len() - 1);

    macro_rules! key {
        ( $e:expr) => { $e.as_ref().map(|&(ref key, _)| key.borrow()) }
    }

    // We cannot use slice.binary_search_by_key instead of each of the
    // two loops here, because we need the left-most match (for begin) and
    // the right-most match (for end), and the stdlib does not provide
    // any of these guarantees.

    // Find the beginning
    let begin;
    if let Bound::Unbounded = range.start_bound() {
        begin = 0;
    } else {
        macro_rules! is_before_range {
            ( $item: expr) => {
                match &range.start_bound() {
                    Bound::Included(ref key_begin) => $item < Some(key_begin.borrow()),
                    Bound::Excluded(ref key_begin) => $item <= Some(key_begin.borrow()),
                    Bound::Unbounded => unreachable!()
                }
            }
        };
        while left < right {
            let middle = left + (right - left) / 2;
            if is_before_range!(key!(slice[middle])) {
                left = middle + 1;
            } else if middle > 0 && !is_before_range!(key!(slice[middle - 1])) {
                right = middle - 1;
            } else {
                left = middle;
                break
            }
        }
        if left == slice.len() || is_before_range!(key!(slice[left])) {
            return Err(())
        }
        begin = left
    };

    // Find the ending
    let end;
    if let Bound::Unbounded = range.end_bound() {
        end = slice.len()
    } else {
        macro_rules! is_after_range {
            ( $item:expr ) => {
                match &range.end_bound() {
                    Bound::Included(ref key_end) => $item > Some(key_end.borrow()),
                    Bound::Excluded(ref key_end) => $item >= Some(key_end.borrow()),
                    Bound::Unbounded => unreachable!()
                }
            }
        };
        right = slice.len(); // no need to reset left
        while left < right {
            let middle = left + (right - left + 1) / 2;
            if is_after_range!(key!(slice[middle - 1])) {
                right = middle - 1;
            } else if middle < slice.len() && !is_after_range!(key!(slice[middle])) {
                left = middle + 1;
            } else {
                right = middle;
                break
            }
        }
        if right == 0 || is_after_range!(key!(slice[right - 1])) {
            return Err(())
        }
        end = right
    };

    Ok((begin, end))
}

fn binary_search_by_key<K, V, Q>(slice: &[Option<(K, V)>], key: &Q) -> Result<usize, usize>
    where K: Ord + Borrow<Q>, Q: Ord + ?Sized
{
    slice.binary_search_by_key(&RevOption::Some(key), |entry| {
        entry.as_ref().map(|&(ref key, _)| key.borrow()).into()
    })
}

fn pair_by_key<'a, K, Q, V>(slice: &'a [Option<(K, V)>], key: &Q) ->
                           Result<&'a (K, V), usize>
    where K: Ord + Borrow<Q>, Q: Ord + ?Sized
{
    binary_search_by_key(slice, key).map(move |idx| slice[idx].as_ref().unwrap())
}

fn pair_mut_by_key<'a, K, Q, V>(slice: &'a mut [Option<(K, V)>], key: &Q) ->
                               Result<&'a mut (K, V), usize>
    where K: Ord + Borrow<Q>, Q: Ord + ?Sized
{
    binary_search_by_key(slice, key).map(move |idx| slice[idx].as_mut().unwrap())
}

impl<'a, K: Ord + 'a, V: 'a> ManagedMap<'a, K, V> {
    pub fn clear(&mut self) {
        match self {
            &mut ManagedMap::Borrowed(ref mut pairs) => {
                for item in pairs.iter_mut() {
                    *item = None
                }
            },
            #[cfg(any(feature = "std", feature = "alloc"))]
            &mut ManagedMap::Owned(ref mut map) => map.clear()
        }
    }

    pub fn get<Q>(&self, key: &Q) -> Option<&V>
        where K: Borrow<Q>, Q: Ord + ?Sized
    {
        match self {
            &ManagedMap::Borrowed(ref pairs) => {
                match pair_by_key(pairs, key.borrow()) {
                    Ok(&(_, ref value)) => Some(value),
                    Err(_) => None
                }
            },
            #[cfg(any(feature = "std", feature = "alloc"))]
            &ManagedMap::Owned(ref map) => map.get(key)
        }
    }

    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
        where K: Borrow<Q>, Q: Ord + ?Sized
    {
        match self {
            &mut ManagedMap::Borrowed(ref mut pairs) => {
                match pair_mut_by_key(pairs, key.borrow()) {
                    Ok(&mut (_, ref mut value)) => Some(value),
                    Err(_) => None
                }
            },
            #[cfg(any(feature = "std", feature = "alloc"))]
            &mut ManagedMap::Owned(ref mut map) => map.get_mut(key)
        }
    }

    pub fn range<'b, 'c, Q: 'c, R>(&'b self, range: R) -> Range<'a, K, V>
            where K: Borrow<Q>, Q: Ord + ?Sized, R: RangeBounds<Q>, 'b: 'a
    {
        match self {
            &ManagedMap::Borrowed(ref pairs) => {
                match binary_search_by_key_range(&pairs[0..self.len()], range) {
                    Ok((begin, end)) => Range(RangeInner::Borrowed {
                        slice: &pairs[begin..end], begin: 0, end: end-begin }),
                    Err(()) => Range(RangeInner::Borrowed {
                        slice: &[], begin: 0, end: 0 }),
                }
            },
            #[cfg(any(feature = "std", feature = "alloc"))]
            &ManagedMap::Owned(ref map) => {
                Range(RangeInner::Owned(map.range(range)))
            },
        }
    }

    pub fn insert(&mut self, key: K, new_value: V) -> Result<Option<V>, (K, V)> {
        match self {
            &mut ManagedMap::Borrowed(ref mut pairs) if pairs.len() < 1 =>
                Err((key, new_value)), // no space at all
            &mut ManagedMap::Borrowed(ref mut pairs) => {
                match binary_search_by_key(pairs, &key) {
                    Err(_) if pairs[pairs.len() - 1].is_some() =>
                        Err((key, new_value)), // full
                    Err(idx) => {
                        let rotate_by = pairs.len() - idx - 1;
                        pairs[idx..].rotate_left(rotate_by);
                        assert!(pairs[idx].is_none(), "broken invariant");
                        pairs[idx] = Some((key, new_value));
                        Ok(None)
                    }
                    Ok(idx) => {
                        let mut swap_pair = Some((key, new_value));
                        mem::swap(&mut pairs[idx], &mut swap_pair);
                        let (_key, value) = swap_pair.expect("broken invariant");
                        Ok(Some(value))
                    }
                }
            },
            #[cfg(any(feature = "std", feature = "alloc"))]
            &mut ManagedMap::Owned(ref mut map) => Ok(map.insert(key, new_value))
        }
    }

    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
        where K: Borrow<Q>, Q: Ord + ?Sized
    {
        match self {
            &mut ManagedMap::Borrowed(ref mut pairs) => {
                match binary_search_by_key(pairs, key) {
                    Ok(idx) => {
                        let (_key, value) = pairs[idx].take().expect("broken invariant");
                        pairs[idx..].rotate_left(1);
                        Some(value)
                    }
                    Err(_) => None
                }
            },
            #[cfg(any(feature = "std", feature = "alloc"))]
            &mut ManagedMap::Owned(ref mut map) => map.remove(key)
        }
    }

    /// ManagedMap contains no elements?
    pub fn is_empty(&self) -> bool {
        match self {
            &ManagedMap::Borrowed(ref pairs) =>
                pairs.iter().all(|item| item.is_none()),
            #[cfg(any(feature = "std", feature = "alloc"))]
            &ManagedMap::Owned(ref map) =>
                map.is_empty()
        }
    }

    /// Returns the number of elements in the ManagedMap.
    pub fn len(&self) -> usize {
        match self {
            &ManagedMap::Borrowed(ref pairs) =>
                pairs.iter()
                .take_while(|item| item.is_some())
                .count(),
            #[cfg(any(feature = "std", feature = "alloc"))]
            &ManagedMap::Owned(ref map) =>
                map.len()
        }
    }

    pub fn iter(&self) -> Iter<K, V> {
        match self {
            &ManagedMap::Borrowed(ref pairs) =>
                Iter::Borrowed(pairs.iter()),
            #[cfg(any(feature = "std", feature = "alloc"))]
            &ManagedMap::Owned(ref map) =>
                Iter::Owned(map.iter()),
        }
    }

    pub fn iter_mut(&mut self) -> IterMut<K, V> {
        match self {
            &mut ManagedMap::Borrowed(ref mut pairs) =>
                IterMut::Borrowed(pairs.iter_mut()),
            #[cfg(any(feature = "std", feature = "alloc"))]
            &mut ManagedMap::Owned(ref mut map) =>
                IterMut::Owned(map.iter_mut()),
        }
    }
}

pub enum Iter<'a, K: 'a, V: 'a> {
    /// Borrowed variant.
    Borrowed(slice::Iter<'a, Option<(K, V)>>),
    /// Owned variant, only available with the `std` or `alloc` feature enabled.
    #[cfg(any(feature = "std", feature = "alloc"))]
    Owned(BTreeIter<'a, K, V>),
}

impl<'a, K: Ord + 'a, V: 'a> Iterator for Iter<'a, K, V> {
    type Item = (&'a K, &'a V);

    fn next(&mut self) -> Option<Self::Item> {
        match self {
            &mut Iter::Borrowed(ref mut iter) =>
                match iter.next() {
                    Some(&Some((ref k, ref v))) => Some((&k, &v)),
                    Some(&None) => None,
                    None => None,
                },
            #[cfg(any(feature = "std", feature = "alloc"))]
            &mut Iter::Owned(ref mut iter) =>
                iter.next(),
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        match self {
            &Iter::Borrowed(ref iter) => {
                let len = iter.clone()
                    .take_while(|item| item.is_some())
                    .count();
                (len, Some(len))
            },
            #[cfg(any(feature = "std", feature = "alloc"))]
            &Iter::Owned(ref iter) =>
                iter.size_hint(),
        }
    }
}

pub enum IterMut<'a, K: 'a, V: 'a> {
    /// Borrowed variant.
    Borrowed(slice::IterMut<'a, Option<(K, V)>>),
    /// Owned variant, only available with the `std` or `alloc` feature enabled.
    #[cfg(any(feature = "std", feature = "alloc"))]
    Owned(BTreeIterMut<'a, K, V>),
}

impl<'a, K: Ord + 'a, V: 'a> Iterator for IterMut<'a, K, V> {
    type Item = (&'a K, &'a mut V);

    fn next(&mut self) -> Option<Self::Item> {
        match self {
            &mut IterMut::Borrowed(ref mut iter) =>
                match iter.next() {
                    Some(&mut Some((ref k, ref mut v))) => Some((&k, v)),
                    Some(&mut None) => None,
                    None => None,
                },
            #[cfg(any(feature = "std", feature = "alloc"))]
            &mut IterMut::Owned(ref mut iter) =>
                iter.next(),
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        match self {
            &IterMut::Borrowed(ref iter) => {
                let (_, upper) = iter.size_hint();
                (0, upper)
            },
            #[cfg(any(feature = "std", feature = "alloc"))]
            &IterMut::Owned(ref iter) =>
                iter.size_hint(),
        }
    }
}

// LCOV_EXCL_START
#[cfg(test)]
mod test {
    use super::ManagedMap;
    use core::ops::Bound::*;

    fn all_pairs_empty() -> [Option<(&'static str, u32)>; 4] {
        [None; 4]
    }

    fn one_pair_full() -> [Option<(&'static str, u32)>; 4] {
        [Some(("a", 1)), None, None, None]
    }

    fn all_pairs_full() -> [Option<(&'static str, u32)>; 4] {
        [Some(("a", 1)), Some(("b", 2)), Some(("c", 3)), Some(("d", 4))]
    }

    fn unwrap<'a, K, V>(map: &'a ManagedMap<'a, K, V>) -> &'a [Option<(K, V)>] {
        match map {
            &ManagedMap::Borrowed(ref map) => map,
            _ => unreachable!()
        }
    }

    #[test]
    fn test_clear() {
        let mut pairs = all_pairs_full();
        let mut map = ManagedMap::Borrowed(&mut pairs);
        map.clear();
        assert!(map.is_empty());
        assert_eq!(map.len(), 0);
        assert_eq!(unwrap(&map), all_pairs_empty());
    }

    #[test]
    fn test_get_some() {
        let mut pairs = all_pairs_full();
        let map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 4);
        assert_eq!(map.get("a"), Some(&1));
        assert_eq!(map.get("b"), Some(&2));
        assert_eq!(map.get("c"), Some(&3));
        assert_eq!(map.get("d"), Some(&4));
    }

    #[test]
    fn test_get_some_one_pair() {
        let mut pairs = one_pair_full();
        let map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 1);
        assert_eq!(map.get("a"), Some(&1));
    }

    #[test]
    fn test_get_none_full() {
        let mut pairs = all_pairs_full();
        let map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 4);
        assert!(!map.is_empty());
        assert_eq!(map.get("q"), None);
        assert_eq!(map.get("0"), None);
    }

    #[test]
    fn test_get_none() {
        let mut pairs = one_pair_full();
        let map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 1);
        assert!(!map.is_empty());
        assert_eq!(map.get("0"), None);
        assert_eq!(map.get("q"), None);
    }

    #[test]
    fn test_get_none_empty() {
        let mut pairs = all_pairs_empty();
        let map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 0);
        assert!(map.is_empty());
        assert_eq!(map.get("q"), None);
    }

    #[test]
    fn test_range_full_unbounded() {
        let mut pairs = all_pairs_full();
        let map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 4);

        let mut range = map.range("a"..);
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);
        assert_eq!(range.next_back(), None);

        let mut range = map.range("a"..);
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next_back(), Some((&"d", &4)));
        assert_eq!(range.next_back(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next_back(), None);
        assert_eq!(range.next(), None);

        let mut range = map.range("b"..);
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);
        assert_eq!(range.next_back(), None);

        let mut range = map.range("d"..);
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);
        assert_eq!(range.next_back(), None);

        let mut range = map.range(.."e");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);
        assert_eq!(range.next_back(), None);

        let mut range = map.range(.."d");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), None);
        assert_eq!(range.next_back(), None);

        let mut range = map.range(.."b");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), None);
        assert_eq!(range.next_back(), None);

        let mut range = map.range(.."a");
        assert_eq!(range.next(), None);
        assert_eq!(range.next_back(), None);

        let mut range = map.range::<&str, _>(..);
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);
        assert_eq!(range.next_back(), None);
    }

    #[test]
    fn test_range_full_exclude_left() {
        let mut pairs = all_pairs_full();
        let map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 4);

        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("a")));
        assert_eq!(range.next(), None);
        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("b")));
        assert_eq!(range.next(), None);
        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("c")));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), None);
        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("d")));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), None);
        let mut range = map.range::<&str, _>((Excluded("a"), Excluded("e")));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);
    }

    #[test]
    fn test_range_full_include_right() {
        let mut pairs = all_pairs_full();
        let map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 4);

        let mut range = map.range::<&str, _>((Included("b"), Included("a")));
        assert_eq!(range.next(), None);
        let mut range = map.range::<&str, _>((Included("b"), Included("b")));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), None);
        let mut range = map.range::<&str, _>((Included("b"), Included("c")));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), None);
        let mut range = map.range::<&str, _>((Included("b"), Included("d")));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);
        let mut range = map.range::<&str, _>((Included("b"), Included("e")));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);

        let mut range = map.range::<&str, _>((Included("b"), Included("a")));
        assert_eq!(range.next_back(), None);
        let mut range = map.range::<&str, _>((Included("b"), Included("b")));
        assert_eq!(range.next_back(), Some((&"b", &2)));
        assert_eq!(range.next_back(), None);
        let mut range = map.range::<&str, _>((Included("b"), Included("c")));
        assert_eq!(range.next_back(), Some((&"c", &3)));
        assert_eq!(range.next_back(), Some((&"b", &2)));
        assert_eq!(range.next_back(), None);
        let mut range = map.range::<&str, _>((Included("b"), Included("d")));
        assert_eq!(range.next_back(), Some((&"d", &4)));
        assert_eq!(range.next_back(), Some((&"c", &3)));
        assert_eq!(range.next_back(), Some((&"b", &2)));
        assert_eq!(range.next_back(), None);
        let mut range = map.range::<&str, _>((Included("b"), Included("e")));
        assert_eq!(range.next_back(), Some((&"d", &4)));
        assert_eq!(range.next_back(), Some((&"c", &3)));
        assert_eq!(range.next_back(), Some((&"b", &2)));
        assert_eq!(range.next_back(), None);
    }

    #[test]
    fn test_range_full() {
        let mut pairs = all_pairs_full();
        let map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 4);

        let mut range = map.range("0".."a");
        assert_eq!(range.next(), None);
        let mut range = map.range("0".."b");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), None);
        let mut range = map.range("0".."c");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), None);
        let mut range = map.range("0".."d");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), None);
        let mut range = map.range("0".."e");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);

        let mut range = map.range("a".."a");
        assert_eq!(range.next(), None);
        let mut range = map.range("a".."b");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), None);
        let mut range = map.range("a".."c");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), None);
        let mut range = map.range("a".."d");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), None);
        let mut range = map.range("a".."e");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);

        let mut range = map.range("b".."a");
        assert_eq!(range.next(), None);
        let mut range = map.range("b".."b");
        assert_eq!(range.next(), None);
        let mut range = map.range("b".."c");
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), None);
        let mut range = map.range("b".."d");
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), None);
        let mut range = map.range("b".."e");
        assert_eq!(range.next(), Some((&"b", &2)));
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);

        let mut range = map.range("c".."a");
        assert_eq!(range.next(), None);
        let mut range = map.range("c".."b");
        assert_eq!(range.next(), None);
        let mut range = map.range("c".."c");
        assert_eq!(range.next(), None);
        let mut range = map.range("c".."d");
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), None);
        let mut range = map.range("c".."e");
        assert_eq!(range.next(), Some((&"c", &3)));
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);

        let mut range = map.range("d".."a");
        assert_eq!(range.next(), None);
        let mut range = map.range("d".."b");
        assert_eq!(range.next(), None);
        let mut range = map.range("d".."c");
        assert_eq!(range.next(), None);
        let mut range = map.range("d".."d");
        assert_eq!(range.next(), None);
        let mut range = map.range("d".."e");
        assert_eq!(range.next(), Some((&"d", &4)));
        assert_eq!(range.next(), None);

        let mut range = map.range("e".."a");
        assert_eq!(range.next(), None);
        let mut range = map.range("e".."b");
        assert_eq!(range.next(), None);
        let mut range = map.range("e".."c");
        assert_eq!(range.next(), None);
        let mut range = map.range("e".."d");
        assert_eq!(range.next(), None);
        let mut range = map.range("e".."e");
        assert_eq!(range.next(), None);
    }

    #[test]
    fn test_range_one_pair() {
        let mut pairs = one_pair_full();
        let map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 1);

        let mut range = map.range("0".."a");
        assert_eq!(range.next(), None);
        let mut range = map.range("0".."b");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), None);
        let mut range = map.range("0".."c");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), None);

        let mut range = map.range("a".."a");
        assert_eq!(range.next(), None);
        let mut range = map.range("a".."b");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), None);
        let mut range = map.range("a".."c");
        assert_eq!(range.next(), Some((&"a", &1)));
        assert_eq!(range.next(), None);

        let mut range = map.range("b".."a");
        assert_eq!(range.next(), None);
        let mut range = map.range("b".."b");
        assert_eq!(range.next(), None);
        let mut range = map.range("b".."c");
        assert_eq!(range.next(), None);
    }

    #[test]
    fn test_range_empty() {
        let mut pairs = all_pairs_empty();
        let map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 0);

        let mut range = map.range("b".."a");
        assert_eq!(range.next(), None);
        let mut range = map.range("b".."b");
        assert_eq!(range.next(), None);
        let mut range = map.range("b".."c");
        assert_eq!(range.next(), None);
    }

    #[test]
    fn test_get_mut_some() {
        let mut pairs = all_pairs_full();
        let mut map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 4);
        assert!(!map.is_empty());
        assert_eq!(map.get_mut("a"), Some(&mut 1));
        assert_eq!(map.get_mut("b"), Some(&mut 2));
        assert_eq!(map.get_mut("c"), Some(&mut 3));
        assert_eq!(map.get_mut("d"), Some(&mut 4));
    }

    #[test]
    fn test_get_mut_none() {
        let mut pairs = one_pair_full();
        let mut map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.get_mut("q"), None);
    }

    #[test]
    fn test_insert_empty() {
        let mut pairs = all_pairs_empty();
        let mut map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.len(), 0);
        assert!(map.is_empty());

        assert_eq!(map.insert("a", 1), Ok(None));
        assert_eq!(map.len(), 1);
        assert!(!map.is_empty());
        assert_eq!(unwrap(&map),       [Some(("a", 1)), None, None, None]);
    }

    #[test]
    fn test_insert_replace() {
        let mut pairs = all_pairs_empty();
        let mut map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.insert("a", 1), Ok(None));
        assert_eq!(map.insert("a", 2), Ok(Some(1)));
        assert_eq!(map.len(), 1);
        assert!(!map.is_empty());
        assert_eq!(unwrap(&map),       [Some(("a", 2)), None, None, None]);
    }

    #[test]
    fn test_insert_full() {
        let mut pairs = all_pairs_full();
        let mut map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.insert("q", 1), Err(("q", 1)));
        assert_eq!(map.len(), 4);
        assert_eq!(unwrap(&map),       all_pairs_full());
    }

    #[test]
    fn test_insert_one() {
        let mut pairs = one_pair_full();
        let mut map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.insert("b", 2), Ok(None));
        assert_eq!(unwrap(&map),       [Some(("a", 1)), Some(("b", 2)), None, None]);
    }

    #[test]
    fn test_insert_shift() {
        let mut pairs = one_pair_full();
        let mut map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.insert("c", 3), Ok(None));
        assert_eq!(map.insert("b", 2), Ok(None));
        assert_eq!(unwrap(&map),       [Some(("a", 1)), Some(("b", 2)), Some(("c", 3)), None]);
    }

    #[test]
    fn test_insert_no_space() {
        // Zero-sized backing store
        let mut map = ManagedMap::Borrowed(&mut []);
        assert_eq!(map.insert("a", 1), Err(("a", 1)));
    }

    #[test]
    fn test_remove_nonexistent() {
        let mut pairs = one_pair_full();
        let mut map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.remove("b"), None);
        assert_eq!(map.len(), 1);
    }

    #[test]
    fn test_remove_one() {
        let mut pairs = all_pairs_full();
        let mut map = ManagedMap::Borrowed(&mut pairs);
        assert_eq!(map.remove("a"), Some(1));
        assert_eq!(map.len(), 3);
        assert_eq!(unwrap(&map),    [Some(("b", 2)), Some(("c", 3)), Some(("d", 4)), None]);
    }

    #[test]
    fn test_iter_none() {
        let mut pairs = all_pairs_empty();
        let map = ManagedMap::Borrowed(&mut pairs);
        let mut iter = map.iter();
        assert_eq!(iter.size_hint(), (0, Some(0)));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_iter_one() {
        let mut pairs = one_pair_full();
        let map = ManagedMap::Borrowed(&mut pairs);
        let mut iter = map.iter();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        assert_eq!(iter.next(), Some((&"a", &1)));
        assert_eq!(iter.size_hint(), (0, Some(0)));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_iter_full() {
        let mut pairs = all_pairs_full();
        let map = ManagedMap::Borrowed(&mut pairs);
        let mut iter = map.iter();
        assert_eq!(iter.size_hint(), (4, Some(4)));
        assert_eq!(iter.next(), Some((&"a", &1)));
        assert_eq!(iter.next(), Some((&"b", &2)));
        assert_eq!(iter.next(), Some((&"c", &3)));
        assert_eq!(iter.next(), Some((&"d", &4)));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_iter_mut_full() {
        let mut pairs = all_pairs_full();
        let mut map = ManagedMap::Borrowed(&mut pairs);

        {
            let mut iter = map.iter_mut();
            assert_eq!(iter.size_hint(), (0, Some(4)));
            for (_k, mut v) in &mut iter {
                *v += 1;
            }
            assert_eq!(iter.size_hint(), (0, Some(0)));
            // Scope for `iter` ends here so that it can be borrowed
            // again with the following `iter`.
        }
        {
            let mut iter = map.iter();
            assert_eq!(iter.next(), Some((&"a", &2)));
            assert_eq!(iter.next(), Some((&"b", &3)));
            assert_eq!(iter.next(), Some((&"c", &4)));
            assert_eq!(iter.next(), Some((&"d", &5)));
            assert_eq!(iter.next(), None);
        }
    }
}