im 11.0.0

// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

use std::borrow::Borrow;
use std::cmp::Ordering;
use std::mem;
use std::ops::IndexMut;

use util::Ref;

use self::Insert::*;
use self::InsertAction::*;

const NODE_SIZE: usize = 16; // Must be an even number!
const MEDIAN: usize = (NODE_SIZE + 1) >> 1;

pub trait BTreeValue: Clone {
    type Key;
    fn ptr_eq(&self, other: &Self) -> bool;
    fn search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize>
    where
        BK: Ord + ?Sized,
        Self::Key: Borrow<BK>;
    fn search_value(slice: &[Self], value: &Self) -> Result<usize, usize>;
    fn cmp_keys(&self, other: &Self) -> Ordering;
}

pub struct Node<A>(Ref<NodeData<A>>);

struct NodeData<A> {
    count: usize,
    keys: Vec<A>,
    children: Vec<Option<Node<A>>>,
}

pub enum Insert<A> {
    Added,
    Replaced(A),
    Update(Node<A>),
    Split(Node<A>, A, Node<A>),
}

enum InsertAction<A> {
    AddedAction,
    ReplacedAction(A),
    InsertAt,
    InsertSplit(Node<A>, A, Node<A>),
}

pub enum Remove<A> {
    NoChange,
    Removed(A),
    Update(A, Node<A>),
}

enum RemoveAction {
    DeleteAt(usize),
    PullUp(usize, usize, usize),
    Merge(usize),
    StealFromLeft(usize),
    StealFromRight(usize),
    MergeFirst(usize),
    ContinueDown(usize),
}

impl<A> Clone for Node<A> {
    fn clone(&self) -> Self {
        Node(self.0.clone())
    }
}

impl<A: Clone> Clone for NodeData<A> {
    fn clone(&self) -> Self {
        NodeData {
            count: self.count,
            keys: self.keys.clone(),
            children: self.children.clone(),
        }
    }
}

impl<A> NodeData<A> {
    #[inline]
    fn has_room(&self) -> bool {
        self.keys.len() < NODE_SIZE
    }

    #[inline]
    fn too_small(&self) -> bool {
        self.keys.len() < MEDIAN
    }

    fn sum_up_children(&self) -> usize {
        let mut c = self.count;
        for n in &self.children {
            match *n {
                None => continue,
                Some(ref node) => c += node.len(),
            }
        }
        c
    }
}

impl<A> Default for Node<A> {
    fn default() -> Self {
        let mut children = Vec::with_capacity(NODE_SIZE + 1);
        children.push(None);
        Node(Ref::new(NodeData {
            count: 0,
            keys: Vec::with_capacity(NODE_SIZE),
            children,
        }))
    }
}

impl<A> Node<A> {
    #[inline]
    pub fn len(&self) -> usize {
        self.0.count
    }

    #[inline]
    fn maybe_len(node_or: &Option<Node<A>>) -> usize {
        match *node_or {
            None => 0,
            Some(ref node) => node.len(),
        }
    }

    #[inline]
    fn has_room(&self) -> bool {
        self.0.has_room()
    }

    #[inline]
    fn too_small(&self) -> bool {
        self.0.too_small()
    }

    #[inline]
    pub fn new() -> Self {
        Self::default()
    }

    #[inline]
    pub fn singleton(value: A) -> Self {
        let mut keys = Vec::with_capacity(NODE_SIZE);
        keys.push(value);
        let mut children = Vec::with_capacity(NODE_SIZE + 1);
        children.push(None);
        children.push(None);
        Node(Ref::new(NodeData {
            count: 1,
            keys,
            children,
        }))
    }

    #[inline]
    pub fn from_split(left: Node<A>, median: A, right: Node<A>) -> Self {
        let count = left.len() + right.len() + 1;
        let mut keys = Vec::with_capacity(NODE_SIZE);
        keys.push(median);
        let mut children = Vec::with_capacity(NODE_SIZE + 1);
        children.push(Some(left));
        children.push(Some(right));
        Node(Ref::new(NodeData {
            count,
            keys,
            children,
        }))
    }

    #[inline]
    fn wrap(data: NodeData<A>) -> Self {
        Node(Ref::new(data))
    }

    #[inline]
    pub fn ptr_eq(&self, other: &Self) -> bool {
        Ref::ptr_eq(&self.0, &other.0)
    }

    pub fn min(&self) -> Option<&A> {
        match *self.0.children.first().unwrap() {
            None => self.0.keys.first(),
            Some(ref child) => child.min(),
        }
    }

    pub fn max(&self) -> Option<&A> {
        match *self.0.children.last().unwrap() {
            None => self.0.keys.last(),
            Some(ref child) => child.max(),
        }
    }
}

impl<A: BTreeValue> Node<A> {
    pub fn lookup<BK>(&self, key: &BK) -> Option<&A>
    where
        BK: Ord + ?Sized,
        A::Key: Borrow<BK>,
    {
        if self.0.keys.is_empty() {
            return None;
        }
        // Perform a binary search, resulting in either a match or
        // the index of the first higher key, meaning we search the
        // child to the left of it.
        match A::search_key(&self.0.keys, key) {
            Ok(index) => Some(&self.0.keys[index]),
            Err(index) => match self.0.children[index] {
                None => None,
                Some(ref node) => node.lookup(key),
            },
        }
    }

    pub fn lookup_mut<BK>(&mut self, key: &BK) -> Option<&mut A>
    where
        BK: Ord + ?Sized,
        A::Key: Borrow<BK>,
    {
        if self.0.keys.is_empty() {
            return None;
        }
        let node = Ref::make_mut(&mut self.0);
        // Perform a binary search, resulting in either a match or
        // the index of the first higher key, meaning we search the
        // child to the left of it.
        match A::search_key(&node.keys, key) {
            Ok(index) => Some(&mut node.keys[index]),
            Err(index) => match node.children[index] {
                None => None,
                Some(ref mut child) => child.lookup_mut(key),
            },
        }
    }

    fn split(&self, value: A, ins_left: Option<Node<A>>, ins_right: Option<Node<A>>) -> Insert<A> {
        let mut new_keys = self.0.keys.clone();
        let mut new_children = self.0.children.clone();

        match A::search_value(&new_keys, &value) {
            Ok(_) => unreachable!(),
            Err(index) => {
                new_children[index] = ins_left;
                new_keys.insert(index, value);
                new_children.insert(index + 1, ins_right);
            }
        }
        let mut left = NodeData {
            count: MEDIAN,
            keys: new_keys.drain(0..MEDIAN).collect(),
            children: new_children.drain(0..MEDIAN + 1).collect(),
        };
        let mut right = NodeData {
            count: MEDIAN,
            keys: new_keys.drain(1..).collect(),
            children: new_children,
        };
        left.count = left.sum_up_children();
        right.count = right.sum_up_children();
        Split(Node::wrap(left), new_keys.pop().unwrap(), Node::wrap(right))
    }

    fn merge(pair: A, left: &Node<A>, right: &Node<A>) -> Node<A> {
        let mut keys = Vec::with_capacity(NODE_SIZE);
        keys.extend(left.0.keys.iter().cloned());
        keys.push(pair);
        keys.extend(right.0.keys.iter().cloned());
        let mut children = Vec::with_capacity(NODE_SIZE + 1);
        children.extend(left.0.children.iter().cloned());
        children.extend(right.0.children.iter().cloned());
        Node::wrap(NodeData {
            count: left.len() + right.len() + 1,
            keys,
            children,
        })
    }

    fn pop_min(&mut self) -> (A, Option<Node<A>>) {
        let node = Ref::make_mut(&mut self.0);
        let pair = node.keys.remove(0);
        let child = node.children.remove(0);
        node.count -= 1 + Node::maybe_len(&child);
        (pair, child)
    }

    fn pop_max(&mut self) -> (A, Option<Node<A>>) {
        let node = Ref::make_mut(&mut self.0);
        let pair = node.keys.pop().unwrap();
        let child = node.children.pop().unwrap();
        node.count -= 1 + Node::maybe_len(&child);
        (pair, child)
    }

    fn push_min(&mut self, child: Option<Node<A>>, pair: A) {
        let node = Ref::make_mut(&mut self.0);
        node.count += 1 + Node::maybe_len(&child);
        node.keys.insert(0, pair);
        node.children.insert(0, child);
    }

    fn push_max(&mut self, child: Option<Node<A>>, pair: A) {
        let node = Ref::make_mut(&mut self.0);
        node.count += 1 + Node::maybe_len(&child);
        node.keys.push(pair);
        node.children.push(child);
    }

    pub fn insert(&mut self, value: A) -> Insert<A> {
        if self.0.keys.is_empty() {
            let node = Ref::make_mut(&mut self.0);
            node.keys.push(value);
            node.children.push(None);
            node.count += 1;
            return Insert::Added;
        }
        let (median, left, right) = match A::search_value(&self.0.keys, &value) {
            // Key exists in node
            Ok(index) => {
                let mut node = Ref::make_mut(&mut self.0);
                return Insert::Replaced(mem::replace(&mut node.keys[index], value));
            }
            // Key is adjacent to some key in node
            Err(index) => {
                let mut has_room = self.has_room();
                let mut node = Ref::make_mut(&mut self.0);
                let action = match node.children[index] {
                    // No child at location, this is the target node.
                    None => InsertAt,
                    // Child at location, pass it on.
                    Some(ref mut child) => match child.insert(value.clone()) {
                        Insert::Added => AddedAction,
                        Insert::Replaced(value) => ReplacedAction(value),
                        Insert::Update(_) => unreachable!(),
                        Insert::Split(left, median, right) => InsertSplit(left, median, right),
                    },
                };
                match action {
                    ReplacedAction(value) => return Insert::Replaced(value),
                    AddedAction => {
                        node.count += 1;
                        return Insert::Added;
                    }
                    InsertAt => {
                        if has_room {
                            node.keys.insert(index, value);
                            node.children.insert(index + 1, None);
                            node.count += 1;
                            return Insert::Added;
                        } else {
                            (value, None, None)
                        }
                    }
                    InsertSplit(left, median, right) => {
                        if has_room {
                            node.children[index] = Some(left);
                            node.keys.insert(index, median);
                            node.children.insert(index + 1, Some(right));
                            node.count += 1;
                            return Insert::Added;
                        } else {
                            (median, Some(left), Some(right))
                        }
                    }
                }
            }
        };
        self.split(median, left, right)
    }

    pub fn remove<BK>(&mut self, key: &BK) -> Remove<A>
    where
        BK: Ord + ?Sized,
        A::Key: Borrow<BK>,
    {
        let index = A::search_key(&self.0.keys, key);
        self.remove_index(index, key)
    }

    fn remove_index<BK>(&mut self, index: Result<usize, usize>, key: &BK) -> Remove<A>
    where
        BK: Ord + ?Sized,
        A::Key: Borrow<BK>,
    {
        let action = match index {
            // Key exists in node, remove it.
            Ok(index) => {
                match (&self.0.children[index], &self.0.children[index + 1]) {
                    // If we're a leaf, just delete the entry.
                    (&None, &None) => RemoveAction::DeleteAt(index),
                    // If the left hand child has capacity, pull the predecessor up.
                    (&Some(ref left), _) if !left.too_small() => {
                        RemoveAction::PullUp(left.0.keys.len() - 1, index, index)
                    }
                    // If the right hand child has capacity, pull the successor up.
                    (_, &Some(ref right)) if !right.too_small() => {
                        RemoveAction::PullUp(0, index, index + 1)
                    }
                    // If neither child has capacity, we'll have to merge them.
                    (&Some(_), &Some(_)) => RemoveAction::Merge(index),
                    // If one child exists and the other doesn't, we're in a bad state.
                    _ => unreachable!(),
                }
            }
            // Key is adjacent to some key in node
            Err(index) => match self.0.children[index] {
                // No child at location means key isn't in map.
                None => return Remove::NoChange,
                // Child at location, but it's at minimum capacity.
                Some(ref child) if child.too_small() => {
                    let left = if index > 0 {
                        self.0.children.get(index - 1)
                    } else {
                        None
                    }; // index is usize and can't be negative, best make sure it never is.
                    match (left, self.0.children.get(index + 1)) {
                        // If it has a left sibling with capacity, steal a key from it.
                        (Some(&Some(ref old_left)), _) if !old_left.too_small() => {
                            RemoveAction::StealFromLeft(index)
                        }
                        // If it has a right sibling with capacity, same as above.
                        (_, Some(&Some(ref old_right))) if !old_right.too_small() => {
                            RemoveAction::StealFromRight(index)
                        }
                        // If it has neither, we'll have to merge it with a sibling.
                        // If we have a right sibling, we'll merge with that.
                        (_, Some(&Some(_))) => RemoveAction::MergeFirst(index),
                        // If we have a left sibling, we'll merge with that.
                        (Some(&Some(_)), _) => RemoveAction::MergeFirst(index - 1),
                        // If none of the above, we're in a bad state.
                        _ => unreachable!(),
                    }
                }
                // Child at location, and it's big enough, we can recurse down.
                Some(_) => RemoveAction::ContinueDown(index),
            },
        };
        match action {
            RemoveAction::DeleteAt(index) => {
                let mut node = Ref::make_mut(&mut self.0);
                let pair = node.keys.remove(index);
                node.children.remove(index);
                node.count -= 1;
                Remove::Removed(pair)
            }
            RemoveAction::PullUp(target_index, pull_to, child_index) => {
                let mut node = Ref::make_mut(&mut self.0);
                let mut children = &mut node.children;
                let mut update = None;
                let mut pair;
                if let Some(&mut Some(ref mut child)) = children.get_mut(child_index) {
                    match child.remove_index(Ok(target_index), key) {
                        Remove::NoChange => unreachable!(),
                        Remove::Removed(pulled_pair) => {
                            node.keys.push(pulled_pair);
                            pair = node.keys.swap_remove(pull_to);
                            node.count -= 1;
                        }
                        Remove::Update(pulled_pair, new_child) => {
                            node.keys.push(pulled_pair);
                            pair = node.keys.swap_remove(pull_to);
                            node.count -= 1;
                            update = Some(new_child);
                        }
                    }
                } else {
                    unreachable!()
                }
                if let Some(new_child) = update {
                    children[child_index] = Some(new_child);
                }
                Remove::Removed(pair)
            }
            RemoveAction::Merge(index) => {
                let mut merged_child = if let (Some(&Some(ref left)), Some(&Some(ref right))) =
                    (self.0.children.get(index), self.0.children.get(index + 1))
                {
                    Node::merge(self.0.keys[index].clone(), left, right)
                } else {
                    unreachable!()
                };
                let mut node = Ref::make_mut(&mut self.0);
                let pair = node.keys.remove(index);
                let new_child = match merged_child.remove(key) {
                    Remove::NoChange | Remove::Removed(_) => merged_child,
                    Remove::Update(_, updated_child) => updated_child,
                };
                if node.keys.is_empty() {
                    // If we've depleted the root node, the merged child becomes the root.
                    Remove::Update(pair, new_child)
                } else {
                    node.count -= 1;
                    node.children.remove(index + 1);
                    node.children[index] = Some(new_child);
                    Remove::Removed(pair)
                }
            }
            RemoveAction::StealFromLeft(index) => {
                let mut node = Ref::make_mut(&mut self.0);
                let mut update = None;
                let mut out_pair;
                {
                    let mut children = node
                        .children
                        .index_mut(index - 1..index + 1)
                        .iter_mut()
                        .map(|n| {
                            if let Some(ref mut o) = *n {
                                o
                            } else {
                                unreachable!()
                            }
                        });
                    let mut left = children.next().unwrap();
                    let mut child = children.next().unwrap();
                    // Prepare the rebalanced node.
                    child.push_min(
                        left.0.children.last().unwrap().clone(),
                        node.keys[index - 1].clone(),
                    );
                    match child.remove(key) {
                        Remove::NoChange => {
                            // Key wasn't there, we need to revert the steal.
                            child.pop_min();
                            return Remove::NoChange;
                        }
                        Remove::Removed(pair) => {
                            // If we did remove something, we complete the rebalancing.
                            let (left_pair, _) = left.pop_max();
                            node.keys[index - 1] = left_pair;
                            node.count -= 1;
                            out_pair = pair;
                        }
                        Remove::Update(pair, new_child) => {
                            // If we did remove something, we complete the rebalancing.
                            let (left_pair, _) = left.pop_max();
                            node.keys[index - 1] = left_pair;
                            update = Some(new_child);
                            node.count -= 1;
                            out_pair = pair;
                        }
                    }
                }
                if let Some(new_child) = update {
                    node.children[index] = Some(new_child);
                }
                Remove::Removed(out_pair)
            }
            RemoveAction::StealFromRight(index) => {
                let mut node = Ref::make_mut(&mut self.0);
                let mut update = None;
                let mut out_pair;
                {
                    let mut children = node.children.index_mut(index..index + 2).iter_mut().map(
                        |n| {
                            if let Some(ref mut o) = *n {
                                o
                            } else {
                                unreachable!()
                            }
                        },
                    );
                    let mut child = children.next().unwrap();
                    let mut right = children.next().unwrap();
                    // Prepare the rebalanced node.
                    child.push_max(right.0.children[0].clone(), node.keys[index].clone());
                    match child.remove(key) {
                        Remove::NoChange => {
                            // Key wasn't there, we need to revert the steal.
                            child.pop_max();
                            return Remove::NoChange;
                        }
                        Remove::Removed(pair) => {
                            // If we did remove something, we complete the rebalancing.
                            let (right_pair, _) = right.pop_min();
                            node.keys[index] = right_pair;
                            node.count -= 1;
                            out_pair = pair;
                        }
                        Remove::Update(pair, new_child) => {
                            // If we did remove something, we complete the rebalancing.
                            let (right_pair, _) = right.pop_min();
                            node.keys[index] = right_pair;
                            update = Some(new_child);
                            node.count -= 1;
                            out_pair = pair;
                        }
                    }
                }
                if let Some(new_child) = update {
                    node.children[index] = Some(new_child);
                }
                Remove::Removed(out_pair)
            }
            RemoveAction::MergeFirst(index) => {
                let mut merged = if let (Some(&Some(ref left)), Some(&Some(ref right))) =
                    (self.0.children.get(index), self.0.children.get(index + 1))
                {
                    Node::merge(self.0.keys[index].clone(), left, right)
                } else {
                    unreachable!()
                };
                let mut node = Ref::make_mut(&mut self.0);
                let mut update;
                let mut out_pair;
                {
                    match merged.remove(key) {
                        Remove::NoChange => return Remove::NoChange,
                        Remove::Removed(pair) => {
                            if node.keys.len() == 1 {
                                return Remove::Update(pair, merged);
                            }
                            node.count -= 1;
                            node.keys.remove(index);
                            node.children.remove(index);
                            update = Some(merged);
                            out_pair = pair;
                        }
                        Remove::Update(pair, new_child) => {
                            if node.keys.len() == 1 {
                                return Remove::Update(pair, new_child);
                            }
                            node.count -= 1;
                            node.keys.remove(index);
                            node.children.remove(index);
                            update = Some(new_child);
                            out_pair = pair;
                        }
                    }
                }
                if let Some(new_child) = update {
                    node.children[index] = Some(new_child);
                }
                Remove::Removed(out_pair)
            }
            RemoveAction::ContinueDown(index) => {
                let mut node = Ref::make_mut(&mut self.0);
                let mut update = None;
                let mut out_pair;
                if let Some(&mut Some(ref mut child)) = node.children.get_mut(index) {
                    match child.remove(key) {
                        Remove::NoChange => return Remove::NoChange,
                        Remove::Removed(pair) => {
                            node.count -= 1;
                            out_pair = pair;
                        }
                        Remove::Update(pair, new_child) => {
                            update = Some(new_child);
                            node.count -= 1;
                            out_pair = pair;
                        }
                    }
                } else {
                    unreachable!()
                }
                if let Some(new_child) = update {
                    node.children[index] = Some(new_child);
                }
                Remove::Removed(out_pair)
            }
        }
    }
}

// Iterator

enum IterItem<'a, A: 'a> {
    Consider(&'a Node<A>),
    Yield(&'a A),
}

pub struct Iter<'a, A: 'a> {
    fwd_last: Option<&'a A>,
    fwd_stack: Vec<IterItem<'a, A>>,
    back_last: Option<&'a A>,
    back_stack: Vec<IterItem<'a, A>>,
    remaining: usize,
}

impl<'a, A: 'a + Clone> Iter<'a, A> {
    pub fn new(root: &'a Node<A>) -> Self {
        Iter {
            fwd_last: None,
            fwd_stack: vec![IterItem::Consider(root)],
            back_last: None,
            back_stack: vec![IterItem::Consider(root)],
            remaining: root.len(),
        }
    }

    fn push_node(stack: &mut Vec<IterItem<'a, A>>, maybe_node: &'a Option<Node<A>>) {
        if let Some(ref node) = *maybe_node {
            stack.push(IterItem::Consider(node))
        }
    }

    fn push(stack: &mut Vec<IterItem<'a, A>>, node: &'a Node<A>) {
        for n in 0..node.0.keys.len() {
            let i = node.0.keys.len() - n;
            Iter::push_node(stack, &node.0.children[i]);
            stack.push(IterItem::Yield(&node.0.keys[i - 1]));
        }
        Iter::push_node(stack, &node.0.children[0]);
    }

    fn push_fwd(&mut self, node: &'a Node<A>) {
        Iter::push(&mut self.fwd_stack, node)
    }

    fn push_node_back(&mut self, maybe_node: &'a Option<Node<A>>) {
        if let Some(ref node) = *maybe_node {
            self.back_stack.push(IterItem::Consider(node))
        }
    }

    fn push_back(&mut self, node: &'a Node<A>) {
        for i in 0..node.0.keys.len() {
            self.push_node_back(&node.0.children[i]);
            self.back_stack.push(IterItem::Yield(&node.0.keys[i]));
        }
        self.push_node_back(&node.0.children[node.0.keys.len()]);
    }
}

impl<'a, A> Iterator for Iter<'a, A>
where
    A: 'a + BTreeValue,
{
    type Item = &'a A;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.fwd_stack.pop() {
                None => {
                    self.remaining = 0;
                    return None;
                }
                Some(IterItem::Consider(node)) => self.push_fwd(&node),
                Some(IterItem::Yield(value)) => {
                    if let Some(ref last) = self.back_last {
                        if value.cmp_keys(last) != Ordering::Less {
                            self.fwd_stack.clear();
                            self.back_stack.clear();
                            self.remaining = 0;
                            return None;
                        }
                    }
                    self.remaining -= 1;
                    self.fwd_last = Some(value);
                    return Some(value);
                }
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining))
    }
}

impl<'a, A> DoubleEndedIterator for Iter<'a, A>
where
    A: 'a + BTreeValue,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        loop {
            match self.back_stack.pop() {
                None => {
                    self.remaining = 0;
                    return None;
                }
                Some(IterItem::Consider(node)) => self.push_back(&node),
                Some(IterItem::Yield(value)) => {
                    if let Some(ref last) = self.fwd_last {
                        if value.cmp_keys(last) != Ordering::Greater {
                            self.fwd_stack.clear();
                            self.back_stack.clear();
                            self.remaining = 0;
                            return None;
                        }
                    }
                    self.remaining -= 1;
                    self.back_last = Some(value);
                    return Some(value);
                }
            }
        }
    }
}

impl<'a, A: 'a + BTreeValue> ExactSizeIterator for Iter<'a, A> {}

// Consuming iterator

enum ConsumingIterItem<A> {
    Consider(Node<A>),
    Yield(A),
}

pub struct ConsumingIter<A> {
    fwd_last: Option<A>,
    fwd_stack: Vec<ConsumingIterItem<A>>,
    back_last: Option<A>,
    back_stack: Vec<ConsumingIterItem<A>>,
    remaining: usize,
}

impl<A: Clone> ConsumingIter<A> {
    pub fn new(root: &Node<A>) -> Self {
        ConsumingIter {
            fwd_last: None,
            fwd_stack: vec![ConsumingIterItem::Consider(root.clone())],
            back_last: None,
            back_stack: vec![ConsumingIterItem::Consider(root.clone())],
            remaining: root.len(),
        }
    }

    fn push_node(stack: &mut Vec<ConsumingIterItem<A>>, maybe_node: &Option<Node<A>>) {
        if let Some(ref node) = *maybe_node {
            stack.push(ConsumingIterItem::Consider(node.clone()))
        }
    }

    fn push(stack: &mut Vec<ConsumingIterItem<A>>, node: &Node<A>) {
        for n in 0..node.0.keys.len() {
            let i = node.0.keys.len() - n;
            ConsumingIter::push_node(stack, &node.0.children[i]);
            stack.push(ConsumingIterItem::Yield(node.0.keys[i - 1].clone()));
        }
        ConsumingIter::push_node(stack, &node.0.children[0]);
    }

    fn push_fwd(&mut self, node: &Node<A>) {
        ConsumingIter::push(&mut self.fwd_stack, node)
    }

    fn push_node_back(&mut self, maybe_node: &Option<Node<A>>) {
        if let Some(ref node) = *maybe_node {
            self.back_stack
                .push(ConsumingIterItem::Consider(node.clone()))
        }
    }

    fn push_back(&mut self, node: &Node<A>) {
        for i in 0..node.0.keys.len() {
            self.push_node_back(&node.0.children[i]);
            self.back_stack
                .push(ConsumingIterItem::Yield(node.0.keys[i].clone()));
        }
        self.push_node_back(&node.0.children[node.0.keys.len()]);
    }
}

impl<A> Iterator for ConsumingIter<A>
where
    A: BTreeValue,
{
    type Item = A;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match self.fwd_stack.pop() {
                None => {
                    self.remaining = 0;
                    return None;
                }
                Some(ConsumingIterItem::Consider(node)) => self.push_fwd(&node),
                Some(ConsumingIterItem::Yield(value)) => {
                    if let Some(ref last) = self.back_last {
                        if value.cmp_keys(last) != Ordering::Less {
                            self.fwd_stack.clear();
                            self.back_stack.clear();
                            self.remaining = 0;
                            return None;
                        }
                    }
                    self.remaining -= 1;
                    self.fwd_last = Some(value.clone());
                    return Some(value);
                }
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining))
    }
}

impl<A> DoubleEndedIterator for ConsumingIter<A>
where
    A: BTreeValue,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        loop {
            match self.back_stack.pop() {
                None => {
                    self.remaining = 0;
                    return None;
                }
                Some(ConsumingIterItem::Consider(node)) => self.push_back(&node),
                Some(ConsumingIterItem::Yield(value)) => {
                    if let Some(ref last) = self.fwd_last {
                        if value.cmp_keys(last) != Ordering::Greater {
                            self.fwd_stack.clear();
                            self.back_stack.clear();
                            self.remaining = 0;
                            return None;
                        }
                    }
                    self.remaining -= 1;
                    self.back_last = Some(value.clone());
                    return Some(value);
                }
            }
        }
    }
}

impl<A: BTreeValue> ExactSizeIterator for ConsumingIter<A> {}

// DiffIter

pub struct DiffIter<'a, A: 'a> {
    old_stack: Vec<IterItem<'a, A>>,
    new_stack: Vec<IterItem<'a, A>>,
}

#[derive(PartialEq, Eq)]
pub enum DiffItem<'a, A: 'a> {
    Add(&'a A),
    Update { old: &'a A, new: &'a A },
    Remove(&'a A),
}

impl<'a, A: 'a> DiffIter<'a, A> {
    pub fn new(old: &'a Node<A>, new: &'a Node<A>) -> Self {
        DiffIter {
            old_stack: if old.0.keys.is_empty() {
                Vec::new()
            } else {
                vec![IterItem::Consider(old)]
            },
            new_stack: if new.0.keys.is_empty() {
                Vec::new()
            } else {
                vec![IterItem::Consider(new)]
            },
        }
    }
}

impl<'a, A> Iterator for DiffIter<'a, A>
where
    A: 'a + BTreeValue + PartialEq,
{
    type Item = DiffItem<'a, A>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match (self.old_stack.pop(), self.new_stack.pop()) {
                (None, None) => return None,
                (None, Some(new)) => match new {
                    IterItem::Consider(new) => Iter::push(&mut self.new_stack, &new),
                    IterItem::Yield(new) => return Some(DiffItem::Add(new)),
                },
                (Some(old), None) => match old {
                    IterItem::Consider(old) => Iter::push(&mut self.old_stack, &old),
                    IterItem::Yield(old) => return Some(DiffItem::Remove(old)),
                },
                (Some(old), Some(new)) => match (old, new) {
                    (IterItem::Consider(old), IterItem::Consider(new)) => {
                        if !Ref::ptr_eq(&old.0, &new.0) {
                            match old.0.keys[0].cmp_keys(&new.0.keys[0]) {
                                Ordering::Less => {
                                    Iter::push(&mut self.old_stack, &old);
                                    self.new_stack.push(IterItem::Consider(new));
                                }
                                Ordering::Greater => {
                                    self.old_stack.push(IterItem::Consider(old));
                                    Iter::push(&mut self.new_stack, &new);
                                }
                                Ordering::Equal => {
                                    Iter::push(&mut self.old_stack, &old);
                                    Iter::push(&mut self.new_stack, &new);
                                }
                            }
                        }
                    }
                    (IterItem::Consider(old), IterItem::Yield(new)) => {
                        Iter::push(&mut self.old_stack, &old);
                        self.new_stack.push(IterItem::Yield(new));
                    }
                    (IterItem::Yield(old), IterItem::Consider(new)) => {
                        self.old_stack.push(IterItem::Yield(old));
                        Iter::push(&mut self.new_stack, &new);
                    }
                    (IterItem::Yield(old), IterItem::Yield(new)) => match old.cmp_keys(&new) {
                        Ordering::Less => {
                            self.new_stack.push(IterItem::Yield(new));
                            return Some(DiffItem::Remove(old));
                        }
                        Ordering::Equal => if old != new {
                            return Some(DiffItem::Update { old, new });
                        },
                        Ordering::Greater => {
                            self.old_stack.push(IterItem::Yield(old));
                            return Some(DiffItem::Add(new));
                        }
                    },
                },
            }
        }
    }
}