//! This crate implements a BTreeMap somewhat similar to std::collections::BTreeMap.

// #![deny(missing_docs)]
use std::borrow::Borrow;
use std::cmp::{Ord, Ordering};
use std::iter::{DoubleEndedIterator, FusedIterator};
use std::ops::{Bound, RangeBounds};

const LEAF_SPLIT: usize = 5;
const LEAF_FULL: usize = LEAF_SPLIT * 2 - 1;
const NON_LEAF_SPLIT: usize = 9;
const NON_LEAF_FULL: usize = NON_LEAF_SPLIT * 2 - 1;

/// BTreeMap somewhat similar to std::collections::BTreeMap.
pub struct BTreeMap<K, V> {
    len: usize,
    tree: Tree<K, V>,
}

impl<K, V> Default for BTreeMap<K, V> {
    fn default() -> Self {
        Self::new()
    }
}

impl<K, V> BTreeMap<K, V> {
    /// Returns a new, empty map.
    pub fn new() -> Self {
        Self {
            len: 0,
            tree: Tree::default(),
        }
    }

    /// Clear the map.
    pub fn clear(&mut self) {
        self.len = 0;
        self.tree = Tree::default();
    }

    /// Insert key-value pair into map.
    pub fn insert(&mut self, key: K, value: V)
    where
        K: Ord,
    {
        if let Some(s) = self.tree.insert(key, value) {
            self.tree.new_root(s);
        }
        self.len += 1;
    }

    /// Remove key-value pair from map, returning just the value.
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.remove_entry(key).map(|(_k, v)| v)
    }

    /// Remove key-value pair from map.
    pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        let result = self.tree.remove(key);
        if result.is_some() {
            self.len -= 1;
        }
        result
    }

    /// Remove first key-value pair from map.
    pub fn pop_first(&mut self) -> Option<(K, V)> {
        let result = self.tree.pop_first();
        if result.is_some() {
            self.len -= 1;
        }
        result
    }

    /// Remove last key-value pair from map.
    pub fn pop_last(&mut self) -> Option<(K, V)> {
        let result = self.tree.pop_last();
        if result.is_some() {
            self.len -= 1;
        }
        result
    }

    /// Returns a reference to the value corresponding to the key.
    pub fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.get_key_value(key).map(|(_k, v)| v)
    }

    /// Returns references to the corresponding key and value.
    pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.tree.get_key_value(key)
    }

    /// Returns references to first key and value.
    pub fn first_key_value(&self) -> Option<(&K, &V)>
    {
        self.tree.first_key_value()
    }

    /// Returns references to last key and value.
    pub fn last_key_value(&self) -> Option<(&K, &V)>
    {
        self.tree.last_key_value()
    }

    /// Returns a mutable reference to the value corresponding to the key.
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.tree.get_mut(key)
    }

    /// Returns true if the map contains a value for the specified key.
    pub fn contains_key<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q> + Ord,
        Q: Ord + ?Sized,
    {
        self.get_key_value(key).is_some()
    }

    /// Get number of key-value pairs in the map.
    pub fn len(&self) -> usize {
        self.len
    }

    /// Is the map empty?
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Get non-mutable iterator.
    pub fn iter(&mut self) -> Iter<'_, K, V> {
        self.tree.iter()
    }

    /// Get mutable iterator.
    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
        self.tree.iter_mut()
    }

    /// Get non-mutable iterator for range.
    pub fn range<T, R>(&self, range: R) -> Iter<'_, K, V>
    where
        T: Ord + ?Sized,
        K: Borrow<T> + Ord,
        R: RangeBounds<T>,
    {
        self.tree.range(&range)
    }

    /// Get mutable iterator for range.
    pub fn range_mut<T, R>(&mut self, range: R) -> IterMut<'_, K, V>
    where
        T: Ord + ?Sized,
        K: Borrow<T> + Ord,
        R: RangeBounds<T>,
    {
        self.tree.range_mut(&range)
    }

    /// Walk the map in sorted order, calling action with reference to key-value pair for each key >= start.
    /// If action returns true the walk terminates.
    pub fn walk<F, Q>(&self, start: &Q, action: &mut F) -> bool
    where
        F: FnMut(&(K, V)) -> bool,
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.tree.walk(start, action)
    }

    /// Walk the map in sorted order, calling action with mutable reference to key-value pair for each key >= start.
    /// If action returns true the walk terminates.
    /// The key can be mutated by action if it does not change the map order.
    pub fn walk_mut<F, Q>(&mut self, start: &Q, action: &mut F) -> bool
    where
        F: FnMut(&mut (K, V)) -> bool,
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.tree.walk_mut(start, action)
    }
} // End impl BTreeMap

enum Tree<K, V> {
    L(Leaf<K, V>),
    NL(NonLeaf<K, V>),
}

impl<K, V> Default for Tree<K, V> {
    fn default() -> Self {
        Tree::L(Leaf(Vec::new()))
    }
}

impl<K, V> Tree<K, V> {
    fn insert(&mut self, key: K, value: V) -> Option<(Tree<K, V>, (K, V))>
    where
        K: Ord,
    {
        match self {
            Tree::L(leaf) => leaf.insert(key, value),
            Tree::NL(nonleaf) => nonleaf.insert(key, value),
        }
    }

    fn new_root(&mut self, (right, med): (Tree<K, V>, (K, V))) {
        let left = std::mem::take(self);
        *self = Tree::NL(NonLeaf {
            v: vec![med],
            c: vec![left, right],
        });
    }

    fn remove<Q>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        match self {
            Tree::L(leaf) => leaf.remove(key),
            Tree::NL(nonleaf) => nonleaf.remove(key),
        }
    }

    fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        match self {
            Tree::L(leaf) => leaf.get_key_value(key),
            Tree::NL(nonleaf) => nonleaf.get_key_value(key),
        }
    }


    fn first_key_value(&self) -> Option<(&K, &V)>
    {
        match self {
            Tree::L(leaf) => leaf.first_key_value(),
            Tree::NL(nonleaf) => nonleaf.first_key_value(),
        }
    }


    fn last_key_value(&self) -> Option<(&K, &V)>
    {
        match self {
            Tree::L(leaf) => leaf.last_key_value(),
            Tree::NL(nonleaf) => nonleaf.last_key_value(),
        }
    }

    fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        match self {
            Tree::L(leaf) => leaf.get_mut(key),
            Tree::NL(nonleaf) => nonleaf.get_mut(key),
        }
    }

    fn pop_first(&mut self) -> Option<(K, V)> {
        match self {
            Tree::L(leaf) => leaf.pop_first(),
            Tree::NL(nonleaf) => nonleaf.pop_first(),
        }
    }

    fn pop_last(&mut self) -> Option<(K, V)> {
        match self {
            Tree::L(leaf) => leaf.0.pop(),
            Tree::NL(nonleaf) => nonleaf.pop_last(),
        }
    }

    fn iter_mut(&mut self) -> IterMut<'_, K, V> {
        IterMut(match self {
            Tree::L(leaf) => Box::new(leaf.iter_mut()),
            Tree::NL(nonleaf) => Box::new(nonleaf.iter_mut()),
        })
    }

    fn iter(&self) -> Iter<'_, K, V> {
        Iter(match self {
            Tree::L(leaf) => Box::new(leaf.iter()),
            Tree::NL(nonleaf) => Box::new(nonleaf.iter()),
        })
    }

    fn range_mut<T, R>(&mut self, range: &R) -> IterMut<'_, K, V>
    where
        T: Ord + ?Sized,
        K: Borrow<T> + Ord,
        R: RangeBounds<T>,
    {
        IterMut(match self {
            Tree::L(leaf) => Box::new(leaf.range_mut(range)),
            Tree::NL(nonleaf) => Box::new(nonleaf.range_mut(range)),
        })
    }

    fn range<T, R>(&self, range: &R) -> Iter<'_, K, V>
    where
        T: Ord + ?Sized,
        K: Borrow<T> + Ord,
        R: RangeBounds<T>,
    {
        Iter(match self {
            Tree::L(leaf) => Box::new(leaf.range(range)),
            Tree::NL(nonleaf) => Box::new(nonleaf.range(range)),
        })
    }

    fn walk<F, Q>(&self, start: &Q, action: &mut F) -> bool
    where
        F: FnMut(&(K, V)) -> bool,
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        match self {
            Tree::L(leaf) => {
                for i in leaf.skip(start)..leaf.0.len() {
                    if action(&leaf.0[i]) {
                        return true;
                    }
                }
            }
            Tree::NL(nonleaf) => {
                let i = nonleaf.skip(start);
                if nonleaf.c[i].walk(start, action) {
                    return true;
                }
                for i in i..nonleaf.v.len() {
                    let v = &nonleaf.v[i];
                    if start <= v.0.borrow() && action(v) {
                        return true;
                    }
                    if nonleaf.c[i + 1].walk(start, action) {
                        return true;
                    }
                }
            }
        }
        false
    }

    fn walk_mut<F, Q>(&mut self, start: &Q, action: &mut F) -> bool
    where
        F: FnMut(&mut (K, V)) -> bool,
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        match self {
            Tree::L(leaf) => {
                for i in leaf.skip(start)..leaf.0.len() {
                    if action(&mut leaf.0[i]) {
                        return true;
                    }
                }
            }
            Tree::NL(nonleaf) => {
                let i = nonleaf.skip(start);
                if i < nonleaf.c.len() && nonleaf.c[i].walk_mut(start, action) {
                    return true;
                }
                for i in i..nonleaf.v.len() {
                    let v = &mut nonleaf.v[i];
                    if start <= v.0.borrow() && action(v) {
                        return true;
                    }
                    if nonleaf.c[i + 1].walk_mut(start, action) {
                        return true;
                    }
                }
            }
        }
        false
    }
} // End impl Tree

struct Leaf<K, V>(Vec<(K, V)>);

impl<K, V> Leaf<K, V> {
    fn full(&self) -> bool {
        self.0.len() == LEAF_FULL
    }

    fn split(&mut self) -> (Tree<K, V>, (K, V)) {
        let right = Tree::L(Self(self.0.split_off(LEAF_SPLIT)));
        let med = self.0.pop().unwrap();
        (right, med)
    }

    fn skip<Q>(&self, to: &Q) -> usize
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        let mut i = 0;
        while i < self.0.len() && self.0[i].0.borrow() < to {
            i += 1;
        }
        i
    }

    fn insert(&mut self, key: K, value: V) -> Option<(Tree<K, V>, (K, V))>
    where
        K: Ord,
    {
        let i = self.skip(&key);
        // Could check for full here and do split before insert so vec is never actually full.
        self.0.insert(i, (key, value));
        if self.full() {
            Some(self.split())
        } else {
            None
        }
    }

    fn remove<Q>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        for (i, x) in self.0.iter_mut().enumerate() {
            if x.0.borrow() == key {
                return Some(self.0.remove(i));
            }
        }
        None
    }

    fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        for x in self.0.iter() {
            if x.0.borrow() == key {
                return Some((&x.0, &x.1));
            }
        }
        None
    }

    fn first_key_value(&self) -> Option<(&K, &V)>
    {
        if self.0.is_empty() { None } else {
           let x = &self.0[0];
           Some((&x.0,&x.1))
        }
    }

    fn last_key_value(&self) -> Option<(&K, &V)>
    {
        if self.0.is_empty() { None } else {
           let x = &self.0[self.0.len()-1];
           Some((&x.0,&x.1))
        }
    }

    fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        for x in self.0.iter_mut() {
            if x.0.borrow() == key {
                return Some(&mut x.1);
            }
        }
        None
    }

    fn pop_first(&mut self) -> Option<(K, V)> {
        if self.0.is_empty() {
            return None;
        }
        Some(self.0.remove(0))
    }

    fn iter_mut(&mut self) -> IterLeafMut<'_, K, V> {
        IterLeafMut(self.0.iter_mut())
    }

    fn iter(&self) -> IterLeaf<'_, K, V> {
        IterLeaf(self.0.iter())
    }

    fn range_mut<T, R>(&mut self, range: &R) -> IterLeafMut<'_, K, V>
    where
        T: Ord + ?Sized,
        K: Borrow<T> + Ord,
        R: RangeBounds<T>,
    {
        let mut x = 0;
        while x < self.0.len() && !range.contains(self.0[x].0.borrow()) {
            x += 1;
        }
        let mut y = self.0.len();
        while y > x && !range.contains(self.0[y - 1].0.borrow()) {
            y -= 1;
        }
        IterLeafMut(self.0[x..y].iter_mut())
    }

    fn range<T, R>(&self, range: &R) -> IterLeaf<'_, K, V>
    where
        T: Ord + ?Sized,
        K: Borrow<T> + Ord,
        R: RangeBounds<T>,
    {
        let mut x = 0;
        while x < self.0.len() && !range.contains(self.0[x].0.borrow()) {
            x += 1;
        }
        let mut y = self.0.len();
        while y > x && !range.contains(self.0[y - 1].0.borrow()) {
            y -= 1;
        }
        IterLeaf(self.0[x..y].iter())
    }
} // End impl Leaf

struct NonLeaf<K, V> {
    v: Vec<(K, V)>,
    c: Vec<Tree<K, V>>,
}

impl<K, V> NonLeaf<K, V> {
    fn full(&self) -> bool {
        self.v.len() == NON_LEAF_FULL
    }

    fn skip<Q>(&self, to: &Q) -> usize
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        let mut i = 0;
        while i < self.v.len() && self.v[i].0.borrow() <= to {
            i += 1;
        }
        i
    }

    fn split(&mut self) -> (Tree<K, V>, (K, V)) {
        let right = Self {
            v: self.v.split_off(NON_LEAF_SPLIT),
            c: self.c.split_off(NON_LEAF_SPLIT),
        };
        let med = self.v.pop().unwrap();
        (Tree::NL(right), med)
    }

    fn insert(&mut self, key: K, value: V) -> Option<(Tree<K, V>, (K, V))>
    where
        K: Ord,
    {
        let i = self.skip(&key);
        if let Some((right, med)) = self.c[i].insert(key, value) {
            // Could check for full here and do split before insert so vecs are never actually full.
            self.v.insert(i, med);
            self.c.insert(i + 1, right);
        }
        if self.full() {
            Some(self.split())
        } else {
            None
        }
    }

    fn remove<Q>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        let mut i = 0;
        while i < self.v.len() {
            match self.v[i].0.borrow().cmp(key) {
                Ordering::Equal => {
                    if let Some(x) = self.c[i].pop_last() {
                        return Some(std::mem::replace(&mut self.v[i], x));
                    } else {
                        self.c.remove(i);
                        return Some(self.v.remove(i));
                    }
                }
                Ordering::Greater => {
                    return self.c[i].remove(key);
                }
                Ordering::Less => {
                    i += 1;
                }
            }
        }
        self.c[i].remove(key)
    }

    fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        let mut i = 0;
        while i < self.v.len() {
            match self.v[i].0.borrow().cmp(key) {
                Ordering::Equal => {
                    return Some((&self.v[i].0, &self.v[i].1));
                }
                Ordering::Greater => {
                    return self.c[i].get_key_value(key);
                }
                Ordering::Less => {
                    i += 1;
                }
            }
        }
        self.c[i].get_key_value(key)
    }

    fn first_key_value(&self) -> Option<(&K, &V)>
    {
        self.c[0].first_key_value()
    }

    fn last_key_value(&self) -> Option<(&K, &V)>
    {
        self.c[self.c.len()-1].last_key_value()
    }

    fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        let mut i = 0;
        while i < self.v.len() {
            match self.v[i].0.borrow().cmp(key) {
                Ordering::Equal => {
                    return Some(&mut self.v[i].1);
                }
                Ordering::Greater => {
                    return self.c[i].get_mut(key);
                }
                Ordering::Less => {
                    i += 1;
                }
            }
        }
        self.c[i].get_mut(key)
    }

    fn pop_first(&mut self) -> Option<(K, V)> {
        if let Some(x) = self.c[0].pop_first() {
            return Some(x);
        }
        if self.v.is_empty() {
            None
        } else {
            self.c.remove(0);
            Some(self.v.remove(0))
        }
    }

    fn pop_last(&mut self) -> Option<(K, V)> {
        let i = self.c.len();
        if i == 0 {
            return None;
        }
        if let Some(x) = self.c[i - 1].pop_last() {
            return Some(x);
        }
        if self.v.is_empty() {
            None
        } else {
            self.c.pop();
            self.v.pop()
        }
    }

    fn iter_mut(&mut self) -> IterNonLeafMut<'_, K, V> {
        let v = self.v.iter_mut();
        let mut c = self.c.iter_mut();
        let current = if let Some(tree) = c.next() {
            tree.iter_mut()
        } else {
            IterMut::empty()
        };
        let current_back = if let Some(tree) = c.next_back() {
            tree.iter_mut()
        } else {
            IterMut::empty()
        };
        IterNonLeafMut {
            v,
            c,
            current,
            current_back,
        }
    }

    fn iter(&self) -> IterNonLeaf<'_, K, V> {
        let v = self.v.iter();
        let mut c = self.c.iter();
        let current = if let Some(tree) = c.next() {
            tree.iter()
        } else {
            Iter::empty()
        };
        let current_back = if let Some(tree) = c.next_back() {
            tree.iter()
        } else {
            Iter::empty()
        };
        IterNonLeaf {
            v,
            c,
            current,
            current_back,
        }
    }

    fn get_xy<T, R>(&self, range: &R) -> (usize, usize)
    where
        T: Ord + ?Sized,
        K: Borrow<T> + Ord,
        R: RangeBounds<T>,
    {
        let (mut x, b) = (0, range.start_bound());
        while x < self.v.len() {
            match b {
                Bound::Included(start) => {
                    if self.v[x].0.borrow() >= start {
                        break;
                    }
                }
                Bound::Excluded(start) => {
                    if self.v[x].0.borrow() > start {
                        break;
                    }
                }
                Bound::Unbounded => break,
            }
            x += 1;
        }
        let (mut y, b) = (self.v.len(), range.end_bound());
        while y > x {
            match b {
                Bound::Included(end) => {
                    if self.v[y - 1].0.borrow() <= end {
                        break;
                    }
                }
                Bound::Excluded(end) => {
                    if self.v[y - 1].0.borrow() < end {
                        break;
                    }
                }
                Bound::Unbounded => break,
            }
            y -= 1;
        }
        (x, y)
    }

    fn range_mut<T, R>(&mut self, range: &R) -> IterNonLeafMut<'_, K, V>
    where
        T: Ord + ?Sized,
        K: Borrow<T> + Ord,
        R: RangeBounds<T>,
    {
        let (x, y) = self.get_xy(range);
        let v = self.v[x..y].iter_mut();
        let mut c = self.c[x..y + 1].iter_mut();
        let current = if let Some(tree) = c.next() {
            tree.range_mut(range)
        } else {
            IterMut::empty()
        };
        let current_back = if let Some(tree) = c.next_back() {
            tree.range_mut(range)
        } else {
            IterMut::empty()
        };
        IterNonLeafMut {
            v,
            c,
            current,
            current_back,
        }
    }

    fn range<T, R>(&self, range: &R) -> IterNonLeaf<'_, K, V>
    where
        T: Ord + ?Sized,
        K: Borrow<T> + Ord,
        R: RangeBounds<T>,
    {
        let (x, y) = self.get_xy(range);
        let v = self.v[x..y].iter();
        let mut c = self.c[x..y + 1].iter();
        let current = if let Some(tree) = c.next() {
            tree.range(range)
        } else {
            Iter::empty()
        };
        let current_back = if let Some(tree) = c.next_back() {
            tree.range(range)
        } else {
            Iter::empty()
        };
        IterNonLeaf {
            v,
            c,
            current,
            current_back,
        }
    }
} // End impl NonLeaf

/// DoubleEnded mutable iterator.
pub struct IterMut<'a, K, V>(Box<dyn 'a + DoubleEndedIterator<Item = (&'a mut K, &'a mut V)>>);

impl<'a, K, V> IterMut<'a, K, V> {
    fn empty() -> Self {
        Self(Box::new(std::iter::empty()))
    }
}
impl<'a, K, V> Iterator for IterMut<'a, K, V> {
    type Item = (&'a mut K, &'a mut V);
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }
}
impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.next_back()
    }
}
impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}

/// DoubleEnded non-mutable iterator.
pub struct Iter<'a, K, V>(Box<dyn 'a + DoubleEndedIterator<Item = (&'a K, &'a V)>>);

impl<'a, K, V> Iter<'a, K, V> {
    fn empty() -> Self {
        Self(Box::new(std::iter::empty()))
    }
}
impl<'a, K, V> Iterator for Iter<'a, K, V> {
    type Item = (&'a K, &'a V);
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }
}
impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.next_back()
    }
}
impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}

// Leaf iterators.

struct IterLeafMut<'a, K, V>(std::slice::IterMut<'a, (K, V)>);

impl<'a, K, V> Iterator for IterLeafMut<'a, K, V> {
    type Item = (&'a mut K, &'a mut V);
    fn next(&mut self) -> Option<Self::Item> {
        let &mut (ref mut k, ref mut v) = self.0.next()?;
        Some((k, v))
    }
}
impl<'a, K, V> DoubleEndedIterator for IterLeafMut<'a, K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let &mut (ref mut k, ref mut v) = self.0.next_back()?;
        Some((k, v))
    }
}

struct IterLeaf<'a, K, V>(std::slice::Iter<'a, (K, V)>);

impl<'a, K, V> Iterator for IterLeaf<'a, K, V> {
    type Item = (&'a K, &'a V);
    fn next(&mut self) -> Option<Self::Item> {
        let (k, v) = self.0.next()?;
        Some((k, v))
    }
}
impl<'a, K, V> DoubleEndedIterator for IterLeaf<'a, K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let (k, v) = self.0.next_back()?;
        Some((k, v))
    }
}

// Non-Leaf iterators.

struct IterNonLeafMut<'a, K, V> {
    v: std::slice::IterMut<'a, (K, V)>,
    c: std::slice::IterMut<'a, Tree<K, V>>,
    current: IterMut<'a, K, V>,
    current_back: IterMut<'a, K, V>,
}
impl<'a, K, V> Iterator for IterNonLeafMut<'a, K, V> {
    type Item = (&'a mut K, &'a mut V);
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(x) = self.current.next() {
            Some(x)
        } else if let Some(&mut (ref mut k, ref mut v)) = self.v.next() {
            if let Some(next) = self.c.next() {
                self.current = next.iter_mut();
            }
            Some((k, v))
        } else {
            self.current_back.next()
        }
    }
}
impl<'a, K, V> DoubleEndedIterator for IterNonLeafMut<'a, K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if let Some(x) = self.current_back.next_back() {
            Some(x)
        } else if let Some(&mut (ref mut k, ref mut v)) = self.v.next_back() {
            if let Some(next_back) = self.c.next_back() {
                self.current_back = next_back.iter_mut();
            }
            Some((k, v))
        } else {
            self.current.next_back()
        }
    }
}

struct IterNonLeaf<'a, K, V> {
    v: std::slice::Iter<'a, (K, V)>,
    c: std::slice::Iter<'a, Tree<K, V>>,
    current: Iter<'a, K, V>,
    current_back: Iter<'a, K, V>,
}
impl<'a, K, V> Iterator for IterNonLeaf<'a, K, V> {
    type Item = (&'a K, &'a V);
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(x) = self.current.next() {
            Some(x)
        } else if let Some((k, v)) = self.v.next() {
            if let Some(next) = self.c.next() {
                self.current = next.iter();
            }
            Some((k, v))
        } else {
            self.current_back.next()
        }
    }
}
impl<'a, K, V> DoubleEndedIterator for IterNonLeaf<'a, K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if let Some(x) = self.current_back.next_back() {
            Some(x)
        } else if let Some((k, v)) = self.v.next_back() {
            if let Some(next_back) = self.c.next_back() {
                self.current_back = next_back.iter();
            }
            Some((k, v))
        } else {
            self.current.next_back()
        }
    }
}

#[test]
pub fn test() {
    let mut t = BTreeMap::<usize, usize>::default();
    let n = 1000000;

    for i in 0..n {
        t.insert(i, i);
    }
    println!("t.len()={}", t.len());

    assert!(t.first_key_value().unwrap().0 == &0);
    assert!(t.last_key_value().unwrap().0 == &(n-1));

    println!("doing range mut test");

    for x in t.range_mut(40..=60).rev() {
        print!("{:?};", x.0);
    }
    println!("done range mut test");

    println!("t.len()={} doing range non-mut test", t.len());

    for x in t.range(40..=60).rev() {
        print!("{:?};", x.0);
    }
    println!("done range non-mut test");

    println!("doing get test");
    for i in 0..n {
        assert_eq!(t.get(&i).unwrap(), &i);
    }

    println!("doing get_mut test");
    for i in 0..n {
        assert_eq!(t.get_mut(&i).unwrap(), &i);
    }

    println!("t.len()={} doing walk test", t.len());
    t.walk(&10, &mut |(k, _): &(usize, usize)| {
        if *k <= 50 {
            print!("{:?};", k);
            false
        } else {
            true
        }
    });
    println!();

    println!("doing remove evens test");
    for i in 0..n {
        if i % 2 == 0 {
            assert_eq!(t.remove(&i).unwrap(), i);
        }
    }
    println!("t.len()={}", t.len());

    println!("t.len()={} re-doing walk test", t.len());
    t.walk(&10, &mut |(k, _): &(usize, usize)| {
        if *k <= 50 {
            print!("{:?};", k);
            false
        } else {
            true
        }
    });
    println!();
}