// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! An ordered map based on a trie.

pub use self::Entry::*;
use self::TrieNode::*;

use std::cmp::Ordering;
use std::fmt::{self, Debug};
use std::hash::{Hash, Hasher};
use std::iter;
use std::mem;
use std::ops;
use std::ptr;
use std::slice;

#[cfg(target_pointer_width = "32")]
pub const USIZE_BITS: usize = 32;

#[cfg(target_pointer_width = "64")]
pub const USIZE_BITS: usize = 64;

// FIXME(conventions): implement bounded iterators
// FIXME(conventions): implement into_iter
// FIXME(conventions): replace each_reverse by making iter DoubleEnded

// FIXME: #5244: need to manually update the InternalNode constructor
const SHIFT: usize = 4;
const SIZE: usize = 1 << SHIFT;
const MASK: usize = SIZE - 1;
// The number of chunks that the key is divided into. Also the maximum depth of the map.
const MAX_DEPTH: usize = USIZE_BITS / SHIFT;

/// A map implemented as a radix trie.
///
/// Keys are split into sequences of 4 bits, which are used to place elements in
/// 16-entry arrays which are nested to form a tree structure. Inserted elements are placed
/// as close to the top of the tree as possible. The most significant bits of the key are used to
/// assign the key to a node/bucket in the first layer. If there are no other elements keyed by
/// the same 4 bits in the first layer, a leaf node will be created in the first layer.
/// When keys coincide, the next 4 bits are used to assign the node to a bucket in the next layer,
/// with this process continuing until an empty spot is found or there are no more bits left in the
/// key. As a result, the maximum depth using 32-bit `usize` keys is 8. The worst collisions occur
/// for very small numbers. For example, 1 and 2 are identical in all but their least significant
/// 4 bits. If both numbers are used as keys, a chain of maximum length will be created to
/// differentiate them.
///
/// # Examples
///
/// ```
/// let mut map = trie::Map::new();
/// map.insert(27, "Olaf");
/// map.insert(1, "Edgar");
/// map.insert(13, "Ruth");
/// map.insert(1, "Martin");
///
/// assert_eq!(map.len(), 3);
/// assert_eq!(map.get(&1), Some(&"Martin"));
///
/// if !map.contains_key(&90) {
///     println!("Nobody is keyed 90");
/// }
///
/// // Update a key
/// match map.get_mut(&1) {
///     Some(value) => *value = "Olga",
///     None => (),
/// }
///
/// map.remove(&13);
/// assert_eq!(map.len(), 2);
///
/// // Print the key value pairs, ordered by key.
/// for (key, value) in map.iter() {
///     // Prints `1: Olga` then `27: Olaf`
///     println!("{}: {}", key, value);
/// }
///
/// map.clear();
/// assert!(map.is_empty());
/// ```
#[derive(Clone)]
pub struct Map<T> {
    root: InternalNode<T>,
    length: usize
}

// An internal node holds SIZE child nodes, which may themselves contain more internal nodes.
//
// Throughout this implementation, "idx" is used to refer to a section of key that is used
// to access a node. The layer of the tree directly below the root corresponds to idx 0.
struct InternalNode<T> {
    // The number of direct children which are external (i.e. that store a value).
    count: usize,
    children: [TrieNode<T>; SIZE]
}

// Each child of an InternalNode may be internal, in which case nesting continues,
// external (containing a value), or empty
#[derive(Clone)]
enum TrieNode<T> {
    Internal(Box<InternalNode<T>>),
    External(usize, T),
    Nothing
}

impl<T: PartialEq> PartialEq for Map<T> {
    fn eq(&self, other: &Map<T>) -> bool {
        self.len() == other.len() &&
            self.iter().zip(other.iter()).all(|(a, b)| a == b)
    }
}

impl<T: Eq> Eq for Map<T> {}

impl<T: PartialOrd> PartialOrd for Map<T> {
    #[inline]
    fn partial_cmp(&self, other: &Map<T>) -> Option<Ordering> {
        self.iter().partial_cmp(other.iter())
    }
}

impl<T: Ord> Ord for Map<T> {
    #[inline]
    fn cmp(&self, other: &Map<T>) -> Ordering {
        self.iter().cmp(other.iter())
    }
}

impl<T: Debug> Debug for Map<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.debug_map().entries(self.iter()).finish()
    }
}

impl<T> Default for Map<T> {
    #[inline]
    fn default() -> Map<T> { Map::new() }
}

impl<T> Map<T> {
    /// Creates an empty map.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut map: trie::Map<&str> = trie::Map::new();
    /// ```
    #[inline]
    pub fn new() -> Map<T> {
        Map{root: InternalNode::new(), length: 0}
    }

    /// Visits all key-value pairs in reverse order. Aborts traversal when `f` returns `false`.
    /// Returns `true` if `f` returns `true` for all elements.
    ///
    /// # Examples
    ///
    /// ```
    /// let map: trie::Map<&str> = [(1, "a"), (2, "b"), (3, "c")].iter().cloned().collect();
    ///
    /// let mut vec = vec![];
    /// assert_eq!(true, map.each_reverse(|&key, &value| { vec.push((key, value)); true }));
    /// assert_eq!(vec, [(3, "c"), (2, "b"), (1, "a")]);
    ///
    /// // Stop when we reach 2
    /// let mut vec = vec![];
    /// assert_eq!(false, map.each_reverse(|&key, &value| { vec.push(value); key != 2 }));
    /// assert_eq!(vec, ["c", "b"]);
    /// ```
    #[inline]
    pub fn each_reverse<'a, F>(&'a self, mut f: F) -> bool
        where F: FnMut(&usize, &'a T) -> bool {
        self.root.each_reverse(&mut f)
    }

    /// Gets an iterator visiting all keys in ascending order by the keys.
    /// The iterator's element type is `usize`.
    pub fn keys(&self) -> Keys<T> { Keys(self.iter()) }

    /// Gets an iterator visiting all values in ascending order by the keys.
    /// The iterator's element type is `&'r T`.
    pub fn values(&self) -> Values<T> { Values(self.iter()) }

    /// Gets an iterator over the key-value pairs in the map, ordered by keys.
    ///
    /// # Examples
    ///
    /// ```
    /// let map: trie::Map<&str> = [(3, "c"), (1, "a"), (2, "b")].iter().cloned().collect();
    ///
    /// for (key, value) in map.iter() {
    ///     println!("{}: {}", key, value);
    /// }
    /// ```
    pub fn iter(&self) -> Iter<T> {
        let mut iter = unsafe {Iter::new()};
        iter.stack[0] = self.root.children.iter();
        iter.length = 1;
        iter.remaining = self.length;

        iter
    }

    /// Gets an iterator over the key-value pairs in the map, with the
    /// ability to mutate the values.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut map: trie::Map<i32> = [(1, 2), (2, 4), (3, 6)].iter().cloned().collect();
    ///
    /// for (key, value) in map.iter_mut() {
    ///     *value = -(key as i32);
    /// }
    ///
    /// assert_eq!(map.get(&1), Some(&-1));
    /// assert_eq!(map.get(&2), Some(&-2));
    /// assert_eq!(map.get(&3), Some(&-3));
    /// ```
    pub fn iter_mut(&mut self) -> IterMut<T> {
        let mut iter = unsafe {IterMut::new()};
        iter.stack[0] = self.root.children.iter_mut();
        iter.length = 1;
        iter.remaining = self.length;

        iter
    }

    /// Return the number of elements in the map.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut a = trie::Map::new();
    /// assert_eq!(a.len(), 0);
    /// a.insert(1, "a");
    /// assert_eq!(a.len(), 1);
    /// ```
    #[inline]
    pub fn len(&self) -> usize { self.length }

    /// Return true if the map contains no elements.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut a = trie::Map::new();
    /// assert!(a.is_empty());
    /// a.insert(1, "a");
    /// assert!(!a.is_empty());
    /// ```
    #[inline]
    pub fn is_empty(&self) -> bool { self.len() == 0 }

    /// Clears the map, removing all values.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut a = trie::Map::new();
    /// a.insert(1, "a");
    /// a.clear();
    /// assert!(a.is_empty());
    /// ```
    #[inline]
    pub fn clear(&mut self) {
        self.root = InternalNode::new();
        self.length = 0;
    }

    /// Returns a reference to the value corresponding to the key.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut map = trie::Map::new();
    /// map.insert(1, "a");
    /// assert_eq!(map.get(&1), Some(&"a"));
    /// assert_eq!(map.get(&2), None);
    /// ```
    #[inline]
    pub fn get(&self, key: &usize) -> Option<&T> {
        let mut node = &self.root;
        let mut idx = 0;
        loop {
            match node.children[chunk(*key, idx)] {
              Internal(ref x) => node = &**x,
              External(stored, ref value) => {
                if stored == *key {
                    return Some(value)
                } else {
                    return None
                }
              }
              Nothing => return None
            }
            idx += 1;
        }
    }

    /// Returns true if the map contains a value for the specified key.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut map = trie::Map::new();
    /// map.insert(1, "a");
    /// assert_eq!(map.contains_key(&1), true);
    /// assert_eq!(map.contains_key(&2), false);
    /// ```
    #[inline]
    pub fn contains_key(&self, key: &usize) -> bool {
        self.get(key).is_some()
    }

    /// Returns a mutable reference to the value corresponding to the key.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut map = trie::Map::new();
    /// map.insert(1, "a");
    /// match map.get_mut(&1) {
    ///     Some(x) => *x = "b",
    ///     None => (),
    /// }
    /// assert_eq!(map[&1], "b");
    /// ```
    #[inline]
    pub fn get_mut(&mut self, key: &usize) -> Option<&mut T> {
        find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1)
    }

    /// Inserts a key-value pair from the map. If the key already had a value
    /// present in the map, that value is returned. Otherwise, `None` is returned.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut map = trie::Map::new();
    /// assert_eq!(map.insert(37, "a"), None);
    /// assert_eq!(map.is_empty(), false);
    ///
    /// map.insert(37, "b");
    /// assert_eq!(map.insert(37, "c"), Some("b"));
    /// assert_eq!(map[&37], "c");
    /// ```
    pub fn insert(&mut self, key: usize, value: T) -> Option<T> {
        let (_, old_val) = insert(&mut self.root.count,
                                    &mut self.root.children[chunk(key, 0)],
                                    key, value, 1);
        if old_val.is_none() { self.length += 1 }
        old_val
    }

    /// Removes a key from the map, returning the value at the key if the key
    /// was previously in the map.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut map = trie::Map::new();
    /// map.insert(1, "a");
    /// assert_eq!(map.remove(&1), Some("a"));
    /// assert_eq!(map.remove(&1), None);
    /// ```
    pub fn remove(&mut self, key: &usize) -> Option<T> {
        let ret = remove(&mut self.root.count,
                         &mut self.root.children[chunk(*key, 0)],
                         *key, 1);
        if ret.is_some() { self.length -= 1 }
        ret
    }
}

// FIXME #5846 we want to be able to choose between &x and &mut x
// (with many different `x`) below, so we need to optionally pass mut
// as a tt, but the only thing we can do with a `tt` is pass them to
// other macros, so this takes the `& <mutability> <operand>` token
// sequence and forces their evaluation as an expression. (see also
// `item!` below.)
macro_rules! addr { ($e:expr) => { $e } }

macro_rules! bound {
    ($iterator_name:ident,
     // the current treemap
     self = $this:expr,
     // the key to look for
     key = $key:expr,
     // are we looking at the upper bound?
     is_upper = $upper:expr,

     // method name for iterating.
     iter = $iter:ident,

     // see the comment on `addr!`, this is just an optional mut, but
     // there's no 0-or-1 repeats yet.
     mutability = $($mut_:tt)*) => {
        {
            // # For `mut`
            // We need an unsafe pointer here because we are borrowing
            // mutable references to the internals of each of these
            // mutable nodes, while still using the outer node.
            //
            // However, we're allowed to flaunt rustc like this because we
            // never actually modify the "shape" of the nodes. The only
            // place that mutation is can actually occur is of the actual
            // values of the map (as the return value of the
            // iterator), i.e. we can never cause a deallocation of any
            // InternalNodes so the raw pointer is always valid.
            //
            // # For non-`mut`
            // We like sharing code so much that even a little unsafe won't
            // stop us.
            let this = $this;
            let mut node = unsafe {
                mem::transmute::<_, usize>(&this.root) as *mut InternalNode<T>
            };

            let key = $key;

            let mut it = unsafe {$iterator_name::new()};
            // everything else is zero'd, as we want.
            it.remaining = this.length;

            // this addr is necessary for the `Internal` pattern.
            addr!(loop {
                    let children = unsafe {addr!(& $($mut_)* (*node).children)};
                    // it.length is the current depth in the iterator and the
                    // current depth through the `usize` key we've traversed.
                    let child_id = chunk(key, it.length);
                    let (slice_idx, ret) = match children[child_id] {
                        Internal(ref $($mut_)* n) => {
                            node = unsafe {
                                mem::transmute::<_, usize>(&**n)
                                    as *mut InternalNode<T>
                            };
                            (child_id + 1, false)
                        }
                        External(stored, _) => {
                            (if stored < key || ($upper && stored == key) {
                                child_id + 1
                            } else {
                                child_id
                            }, true)
                        }
                        Nothing => {
                            (child_id + 1, true)
                        }
                    };
                    // push to the stack.
                    it.stack[it.length] = children[slice_idx..].$iter();
                    it.length += 1;
                    if ret { break }
                });

            it
        }
    }
}

impl<T> Map<T> {
    // If `upper` is true then returns upper_bound else returns lower_bound.
    #[inline]
    fn bound(&self, key: usize, upper: bool) -> Range<T> {
        Range(bound!(Iter, self = self,
               key = key, is_upper = upper,
               iter = iter,
               mutability = ))
    }

    /// Gets an iterator pointing to the first key-value pair whose key is not less than `key`.
    /// If all keys in the map are less than `key` an empty iterator is returned.
    ///
    /// # Examples
    ///
    /// ```
    /// let map: trie::Map<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().cloned().collect();
    ///
    /// assert_eq!(map.lower_bound(4).next(), Some((4, &"b")));
    /// assert_eq!(map.lower_bound(5).next(), Some((6, &"c")));
    /// assert_eq!(map.lower_bound(10).next(), None);
    /// ```
    pub fn lower_bound(&self, key: usize) -> Range<T> {
        self.bound(key, false)
    }

    /// Gets an iterator pointing to the first key-value pair whose key is greater than `key`.
    /// If all keys in the map are not greater than `key` an empty iterator is returned.
    ///
    /// # Examples
    ///
    /// ```
    /// let map: trie::Map<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().cloned().collect();
    ///
    /// assert_eq!(map.upper_bound(4).next(), Some((6, &"c")));
    /// assert_eq!(map.upper_bound(5).next(), Some((6, &"c")));
    /// assert_eq!(map.upper_bound(10).next(), None);
    /// ```
    pub fn upper_bound(&self, key: usize) -> Range<T> {
        self.bound(key, true)
    }
    // If `upper` is true then returns upper_bound else returns lower_bound.
    #[inline]
    fn bound_mut(&mut self, key: usize, upper: bool) -> RangeMut<T> {
        RangeMut(bound!(IterMut, self = self,
               key = key, is_upper = upper,
               iter = iter_mut,
               mutability = mut))
    }

    /// Gets an iterator pointing to the first key-value pair whose key is not less than `key`.
    /// If all keys in the map are less than `key` an empty iterator is returned.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut map: trie::Map<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().cloned().collect();
    ///
    /// assert_eq!(map.lower_bound_mut(4).next(), Some((4, &mut "b")));
    /// assert_eq!(map.lower_bound_mut(5).next(), Some((6, &mut "c")));
    /// assert_eq!(map.lower_bound_mut(10).next(), None);
    ///
    /// for (key, value) in map.lower_bound_mut(4) {
    ///     *value = "changed";
    /// }
    ///
    /// assert_eq!(map.get(&2), Some(&"a"));
    /// assert_eq!(map.get(&4), Some(&"changed"));
    /// assert_eq!(map.get(&6), Some(&"changed"));
    /// ```
    pub fn lower_bound_mut(&mut self, key: usize) -> RangeMut<T> {
        self.bound_mut(key, false)
    }

    /// Gets an iterator pointing to the first key-value pair whose key is greater than `key`.
    /// If all keys in the map are not greater than `key` an empty iterator is returned.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut map: trie::Map<&str> = [(2, "a"), (4, "b"), (6, "c")].iter().cloned().collect();
    ///
    /// assert_eq!(map.upper_bound_mut(4).next(), Some((6, &mut "c")));
    /// assert_eq!(map.upper_bound_mut(5).next(), Some((6, &mut "c")));
    /// assert_eq!(map.upper_bound_mut(10).next(), None);
    ///
    /// for (key, value) in map.upper_bound_mut(4) {
    ///     *value = "changed";
    /// }
    ///
    /// assert_eq!(map.get(&2), Some(&"a"));
    /// assert_eq!(map.get(&4), Some(&"b"));
    /// assert_eq!(map.get(&6), Some(&"changed"));
    /// ```
    pub fn upper_bound_mut(&mut self, key: usize) -> RangeMut<T> {
        self.bound_mut(key, true)
    }
}

impl<T> iter::FromIterator<(usize, T)> for Map<T> {
    fn from_iter<I: IntoIterator<Item=(usize, T)>>(iter: I) -> Map<T> {
        let mut map = Map::new();
        map.extend(iter);
        map
    }
}

impl<T> Extend<(usize, T)> for Map<T> {
    fn extend<I: IntoIterator<Item=(usize, T)>>(&mut self, iter: I) {
        for (k, v) in iter {
            self.insert(k, v);
        }
    }
}

impl<T: Hash> Hash for Map<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        for elt in self.iter() {
            elt.hash(state);
        }
    }
}

impl<'a, T> ops::Index<&'a usize> for Map<T> {
    type Output = T;
    #[inline]
    fn index(&self, i: &'a usize) -> &T {
        self.get(i).expect("key not present")
    }
}

impl<'a, T> ops::IndexMut<&'a usize> for Map<T> {
    #[inline]
    fn index_mut(&mut self, i: &'a usize) -> &mut T {
        self.get_mut(i).expect("key not present")
    }
}

impl<T:Clone> Clone for InternalNode<T> {
    #[inline]
    fn clone(&self) -> InternalNode<T> {
        let ch = &self.children;
        InternalNode {
            count: self.count,
             children: [ch[0].clone(), ch[1].clone(), ch[2].clone(), ch[3].clone(),
                        ch[4].clone(), ch[5].clone(), ch[6].clone(), ch[7].clone(),
                        ch[8].clone(), ch[9].clone(), ch[10].clone(), ch[11].clone(),
                        ch[12].clone(), ch[13].clone(), ch[14].clone(), ch[15].clone()]}
    }
}

impl<T> InternalNode<T> {
    #[inline]
    fn new() -> InternalNode<T> {
        // FIXME: #5244: [Nothing, ..SIZE] should be possible without implicit
        // copyability
        InternalNode{count: 0,
                 children: [Nothing, Nothing, Nothing, Nothing,
                            Nothing, Nothing, Nothing, Nothing,
                            Nothing, Nothing, Nothing, Nothing,
                            Nothing, Nothing, Nothing, Nothing]}
    }
}

impl<T> InternalNode<T> {
    fn each_reverse<'a, F>(&'a self, f: &mut F) -> bool
        where F: FnMut(&usize, &'a T) -> bool {
        for elt in self.children.iter().rev() {
            match *elt {
                Internal(ref x) => if !x.each_reverse(f) { return false },
                External(k, ref v) => if !f(&k, v) { return false },
                Nothing => ()
            }
        }
        true
    }
}

// if this was done via a trait, the key could be generic
#[inline]
fn chunk(n: usize, idx: usize) -> usize {
    let sh = USIZE_BITS - (SHIFT * (idx + 1));
    (n >> sh) & MASK
}

fn find_mut<T>(child: &mut TrieNode<T>, key: usize, idx: usize) -> Option<&mut T> {
    match *child {
        External(stored, ref mut value) if stored == key => Some(value),
        External(..) => None,
        Internal(ref mut x) => find_mut(&mut x.children[chunk(key, idx)], key, idx + 1),
        Nothing => None
    }
}

/// Inserts a new node for the given key and value, at or below `start_node`.
///
/// The index (`idx`) is the index of the next node, such that the start node
/// was accessed via parent.children[chunk(key, idx - 1)].
///
/// The count is the external node counter for the start node's parent,
/// which will be incremented only if `start_node` is transformed into a *new* external node.
///
/// Returns a mutable reference to the inserted value and an optional previous value.
fn insert<'a, T>(count: &mut usize, start_node: &'a mut TrieNode<T>, key: usize, value: T, idx: usize)
    -> (&'a mut T, Option<T>) {
    // We branch twice to avoid having to do the `replace` when we
    // don't need to; this is much faster, especially for keys that
    // have long shared prefixes.

    let mut hack = false;
    match *start_node {
        Nothing => {
            *count += 1;
            *start_node = External(key, value);
            match *start_node {
                External(_, ref mut value_ref) => return (value_ref, None),
                _ => unreachable!()
            }
        }
        Internal(ref mut x) => {
            let x = &mut **x;
            return insert(&mut x.count, &mut x.children[chunk(key, idx)], key, value, idx + 1);
        }
        External(stored_key, _) if stored_key == key => {
            hack = true;
        }
        _ => {}
    }

    if !hack {
        // Conflict, an external node with differing keys.
        // We replace the old node by an internal one, then re-insert the two values beneath it.
        match mem::replace(start_node, Internal(Box::new(InternalNode::new()))) {
            External(stored_key, stored_value) => {
                match *start_node {
                    Internal(ref mut new_node) => {
                        let new_node = &mut **new_node;
                        // Re-insert the old value.
                        insert(&mut new_node.count,
                               &mut new_node.children[chunk(stored_key, idx)],
                               stored_key, stored_value, idx + 1);

                        // Insert the new value, and return a reference to it directly.
                        return insert(&mut new_node.count,
                               &mut new_node.children[chunk(key, idx)],
                               key, value, idx + 1);
                    }
                    // Value that was just copied disappeared.
                    _ => unreachable!()
                }
            }
            // Logic error in previous match.
            _ => unreachable!(),
        }
    }

    if let External(_, ref mut stored_value) = *start_node {
            // Swap in the new value and return the old.
            let old_value = mem::replace(stored_value, value);
            return (stored_value, Some(old_value));
    }

    unreachable!();
}

fn remove<T>(count: &mut usize, child: &mut TrieNode<T>, key: usize,
             idx: usize) -> Option<T> {
    let (ret, this) = match *child {
      External(stored, _) if stored == key => {
        match mem::replace(child, Nothing) {
            External(_, value) => (Some(value), true),
            _ => unreachable!()
        }
      }
      External(..) => (None, false),
      Internal(ref mut x) => {
          let x = &mut **x;
          let ret = remove(&mut x.count, &mut x.children[chunk(key, idx)],
                           key, idx + 1);
          (ret, x.count == 0)
      }
      Nothing => (None, false)
    };

    if this {
        *child = Nothing;
        *count -= 1;
    }
    return ret;
}

/// A view into a single entry in a map, which may be vacant or occupied.
pub enum Entry<'a, T: 'a> {
    /// An occupied entry.
    Occupied(OccupiedEntry<'a, T>),
    /// A vacant entry.
    Vacant(VacantEntry<'a, T>)
}

impl<'a, T> Entry<'a, T> {
    /// Ensures a value is in the entry by inserting the default if empty, and returns
    /// a mutable reference to the value in the entry.
    pub fn or_insert(self, default: T) -> &'a mut T {
        match self {
            Occupied(entry) => entry.into_mut(),
            Vacant(entry) => entry.insert(default),
        }
    }

    /// Ensures a value is in the entry by inserting the result of the default function if empty,
    /// and returns a mutable reference to the value in the entry.
    pub fn or_insert_with<F: FnOnce() -> T>(self, default: F) -> &'a mut T {
        match self {
            Occupied(entry) => entry.into_mut(),
            Vacant(entry) => entry.insert(default()),
        }
    }
}

/// A view into an occupied entry in a map.
pub struct OccupiedEntry<'a, T: 'a> {
    search_stack: SearchStack<'a, T>
}

/// A view into a vacant entry in a map.
pub struct VacantEntry<'a, T: 'a> {
    search_stack: SearchStack<'a, T>
}

/// A list of nodes encoding a path from the root of a map to a node.
///
/// Invariants:
/// * The last node is either `External` or `Nothing`.
/// * Pointers at indexes less than `length` can be safely dereferenced.
struct SearchStack<'a, T: 'a> {
    map: &'a mut Map<T>,
    length: usize,
    key: usize,
    items: [*mut TrieNode<T>; MAX_DEPTH]
}

impl<'a, T> SearchStack<'a, T> {
    /// Creates a new search-stack with empty entries.
    fn new(map: &'a mut Map<T>, key: usize) -> SearchStack<'a, T> {
        SearchStack {
            map: map,
            length: 0,
            key: key,
            items: [ptr::null_mut(); MAX_DEPTH]
        }
    }

    fn push(&mut self, node: *mut TrieNode<T>) {
        self.length += 1;
        self.items[self.length - 1] = node;
    }

    fn peek(&self) -> *mut TrieNode<T> {
        self.items[self.length - 1]
    }

    fn peek_ref(&self) -> &'a mut TrieNode<T> {
        let item = self.items[self.length - 1];
        unsafe { &mut *item }
    }

    fn pop_ref(&mut self) -> &'a mut TrieNode<T> {
        self.length -= 1;
        unsafe {
            &mut *self.items[self.length]
        }
    }

    fn is_empty(&self) -> bool {
        self.length == 0
    }

    fn get_ref(&self, idx: usize) -> &'a mut TrieNode<T> {
        assert!(idx < self.length);
        unsafe {
            &mut *self.items[idx]
        }
    }
}

// Implementation of SearchStack creation logic.
// Once a SearchStack has been created the Entry methods are relatively straight-forward.
impl<T> Map<T> {
    /// Gets the given key's corresponding entry in the map for in-place manipulation.
    #[inline]
    pub fn entry(&mut self, key: usize) -> Entry<T> {
        // Create an empty search stack.
        let mut search_stack = SearchStack::new(self, key);

        // Unconditionally add the corresponding node from the first layer.
        let first_node = &mut search_stack.map.root.children[chunk(key, 0)] as *mut _;
        search_stack.push(first_node);

        // While no appropriate slot is found, keep descending down the Trie,
        // adding nodes to the search stack.
        let search_successful: bool;
        loop {
            match unsafe { next_child(search_stack.peek(), key, search_stack.length) } {
                (Some(child), _) => search_stack.push(child),
                (None, success) => {
                    search_successful = success;
                    break;
                }
            }
        }

        if search_successful {
            Occupied(OccupiedEntry { search_stack: search_stack })
        } else {
            Vacant(VacantEntry { search_stack: search_stack })
        }
    }
}

/// Get a mutable pointer to the next child of a node, given a key and an idx.
///
/// The idx is the index of the next child, such that `node` was accessed via
/// parent.children[chunk(key, idx - 1)].
///
/// Returns a tuple with an optional mutable pointer to the next child, and
/// a boolean flag to indicate whether the external key node was found.
///
/// This function is safe only if `node` points to a valid `TrieNode`.
#[inline]
unsafe fn next_child<T>(node: *mut TrieNode<T>, key: usize, idx: usize)
    -> (Option<*mut TrieNode<T>>, bool) {
    match *node {
        // If the node is internal, tell the caller to descend further.
        Internal(ref mut node_internal) => {
            (Some(&mut node_internal.children[chunk(key, idx)] as *mut _), false)
        },
        // If the node is external or empty, the search is complete.
        // If the key doesn't match, node expansion will be done upon
        // insertion. If it does match, we've found our node.
        External(stored_key, _) if stored_key == key => (None, true),
        External(..) | Nothing => (None, false)
    }
}

// NB: All these methods assume a correctly constructed occupied entry (matching the given key).
impl<'a, T> OccupiedEntry<'a, T> {
    /// Gets a reference to the value in the entry.
    #[inline]
    pub fn get(&self) -> &T {
        match *self.search_stack.peek_ref() {
            External(_, ref value) => value,
            // Invalid SearchStack, non-external last node.
            _ => unreachable!()
        }
    }

    /// Gets a mutable reference to the value in the entry.
    #[inline]
    pub fn get_mut(&mut self) -> &mut T {
        match *self.search_stack.peek_ref() {
            External(_, ref mut value) => value,
            // Invalid SearchStack, non-external last node.
            _ => unreachable!()
        }
    }

    /// Converts the OccupiedEntry into a mutable reference to the value in the entry,
    /// with a lifetime bound to the map itself.
    #[inline]
    pub fn into_mut(self) -> &'a mut T {
        match *self.search_stack.peek_ref() {
            External(_, ref mut value) => value,
            // Invalid SearchStack, non-external last node.
            _ => unreachable!()
        }
    }

    /// Sets the value of the entry, and returns the entry's old value.
    #[inline]
    pub fn insert(&mut self, value: T) -> T {
        match *self.search_stack.peek_ref() {
            External(_, ref mut stored_value) => {
                mem::replace(stored_value, value)
            }
            // Invalid SearchStack, non-external last node.
            _ => unreachable!()
        }
    }

    /// Takes the value out of the entry, and returns it.
    #[inline]
    pub fn remove(self) -> T {
        // This function removes the external leaf-node, then unwinds the search-stack
        // deleting now-childless ancestors.
        let mut search_stack = self.search_stack;

        // Extract the value from the leaf-node of interest.
        let leaf_node = mem::replace(search_stack.pop_ref(), Nothing);

        let value = match leaf_node {
            External(_, value) => value,
            // Invalid SearchStack, non-external last node.
            _ => unreachable!()
        };

        // Iterate backwards through the search stack, deleting nodes if they are childless.
        // We compare each ancestor's parent count to 1 because each ancestor reached has just
        // had one of its children deleted.
        while !search_stack.is_empty() {
            let ancestor = search_stack.pop_ref();
            match *ancestor {
                Internal(ref mut internal) => {
                    // If stopping deletion, update the child count and break.
                    if internal.count != 1 {
                        internal.count -= 1;
                        break;
                    }
                }
                // Invalid SearchStack, non-internal ancestor node.
                _ => unreachable!()
            }
            *ancestor = Nothing;
        }

        // Decrement the length of the entire map, for the removed node.
        search_stack.map.length -= 1;

        value
    }
}

impl<'a, T> VacantEntry<'a, T> {
    /// Set the vacant entry to the given value.
    pub fn insert(self, value: T) -> &'a mut T {
        let search_stack = self.search_stack;
        let old_length = search_stack.length;
        let key = search_stack.key;

        // Update the map's length for the new element.
        search_stack.map.length += 1;

        // If there's only 1 node in the search stack, insert a new node below it at idx 1.
        if old_length == 1 {
            // Note: Small hack to appease the borrow checker. Can't mutably borrow root.count
            let mut temp = search_stack.map.root.count;
            let (value_ref, _) = insert(&mut temp, search_stack.get_ref(0), key, value, 1);
            search_stack.map.root.count = temp;
            value_ref
        }
        // Otherwise, find the predecessor of the last stack node, and insert as normal.
        else {
            match *search_stack.get_ref(old_length - 2) {
                Internal(ref mut parent) => {
                    let parent = &mut **parent;
                    let (value_ref, _) = insert(&mut parent.count,
                                                &mut parent.children[chunk(key, old_length - 1)],
                                                key, value, old_length);
                    value_ref
                }
                // Invalid SearchStack, non-internal ancestor node.
                _ => unreachable!()
            }
        }
    }
}

/// A forward iterator over a map.
pub struct Iter<'a, T:'a> {
    stack: [slice::Iter<'a, TrieNode<T>>; MAX_DEPTH],
    length: usize,
    remaining: usize,
}

impl<'a, T> Clone for Iter<'a, T> {
    #[cfg(target_pointer_width="32")]
    fn clone(&self) -> Iter<'a, T> {
        Iter {
            stack: [self.stack[0].clone(), self.stack[1].clone(),
                    self.stack[2].clone(), self.stack[3].clone(),
                    self.stack[4].clone(), self.stack[5].clone(),
                    self.stack[6].clone(), self.stack[7].clone()], ..*self }
    }

    #[cfg(target_pointer_width="64")]
    fn clone(&self) -> Iter<'a, T> {
        Iter {
            stack: [self.stack[0].clone(), self.stack[1].clone(),
                    self.stack[2].clone(), self.stack[3].clone(),
                    self.stack[4].clone(), self.stack[5].clone(),
                    self.stack[6].clone(), self.stack[7].clone(),
                    self.stack[8].clone(), self.stack[9].clone(),
                    self.stack[10].clone(), self.stack[11].clone(),
                    self.stack[12].clone(), self.stack[13].clone(),
                    self.stack[14].clone(), self.stack[15].clone()], ..*self }
    }
}

/// A forward iterator over the key-value pairs of a map, with the
/// values being mutable.
pub struct IterMut<'a, T:'a> {
    stack: [slice::IterMut<'a, TrieNode<T>>; MAX_DEPTH],
    length: usize,
    remaining: usize,
}

/// A forward iterator over the keys of a map.
pub struct Keys<'a, T: 'a>(Iter<'a, T>);

impl<'a, T> Clone for Keys<'a, T> {
    fn clone(&self) -> Keys<'a, T> { Keys(self.0.clone()) }
}

impl<'a, T> Iterator for Keys<'a, T> {
    type Item = usize;
    fn next(&mut self) -> Option<usize> { self.0.next().map(|e| e.0) }
    fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
}

impl<'a, T> ExactSizeIterator for Keys<'a, T> {}

/// A forward iterator over the values of a map.
pub struct Values<'a, T: 'a>(Iter<'a, T>);

impl<'a, T> Clone for Values<'a, T> {
    fn clone(&self) -> Values<'a, T> { Values(self.0.clone()) }
}

impl<'a, T> Iterator for Values<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> { self.0.next().map(|e| e.1) }
    fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
}

impl<'a, T> ExactSizeIterator for Values<'a, T> {}

// FIXME #5846: see `addr!` above.
macro_rules! item { ($i:item) => {$i}}

macro_rules! iterator_impl {
    ($name:ident,
     iter = $iter:ident,
     mutability = $($mut_:tt)*) => {
        impl<'a, T> $name<'a, T> {
            // Create new zero'd iterator. We have a thin gilding of safety by
            // using init rather than uninit, so that the worst that can happen
            // from failing to initialise correctly after calling these is a
            // segfault.
            #[cfg(target_pointer_width="32")]
            unsafe fn new() -> $name<'a, T> {
                $name {
                    remaining: 0,
                    length: 0,
                    // ick :( ... at least the compiler will tell us if we screwed up.
                    stack: [IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),

                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            ]
                }
            }

            #[cfg(target_pointer_width="64")]
            unsafe fn new() -> $name<'a, T> {
                $name {
                    remaining: 0,
                    length: 0,
                    stack: [IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),

                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),

                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),

                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            IntoIterator::into_iter((& $($mut_)*[])),
                            ]
                }
            }
        }

        item!(impl<'a, T> Iterator for $name<'a, T> {
                type Item = (usize, &'a $($mut_)* T);
                // you might wonder why we're not even trying to act within the
                // rules, and are just manipulating raw pointers like there's no
                // such thing as invalid pointers and memory unsafety. The
                // reason is performance, without doing this we can get the
                // (now replaced) bench_iter_large microbenchmark down to about
                // 30000 ns/iter (using .unsafe_get to index self.stack directly, 38000
                // ns/iter with [] checked indexing), but this smashes that down
                // to 13500 ns/iter.
                //
                // Fortunately, it's still safe...
                //
                // We have an invariant that every Internal node
                // corresponds to one push to self.stack, and one pop,
                // nested appropriately. self.stack has enough storage
                // to store the maximum depth of Internal nodes in the
                // trie (8 on 32-bit platforms, 16 on 64-bit).
                fn next(&mut self) -> Option<(usize, &'a $($mut_)* T)> {
                    let start_ptr = self.stack.as_mut_ptr();

                    unsafe {
                        // write_ptr is the next place to write to the stack.
                        // invariant: start_ptr <= write_ptr < end of the
                        // vector.
                        let mut write_ptr = start_ptr.offset(self.length as isize);
                        while write_ptr != start_ptr {
                            // indexing back one is safe, since write_ptr >
                            // start_ptr now.
                            match (*write_ptr.offset(-1)).next() {
                                // exhausted this iterator (i.e. finished this
                                // Internal node), so pop from the stack.
                                //
                                // don't bother clearing the memory, because the
                                // next time we use it we'll've written to it
                                // first.
                                None => write_ptr = write_ptr.offset(-1),
                                Some(child) => {
                                    addr!(match *child {
                                            Internal(ref $($mut_)* node) => {
                                                // going down a level, so push
                                                // to the stack (this is the
                                                // write referenced above)
                                                *write_ptr = node.children.$iter();
                                                write_ptr = write_ptr.offset(1);
                                            }
                                            External(key, ref $($mut_)* value) => {
                                                self.remaining -= 1;
                                                // store the new length of the
                                                // stack, based on our current
                                                // position.
                                                self.length = (write_ptr as usize
                                                               - start_ptr as usize) /
                                                    mem::size_of_val(&*write_ptr);

                                                return Some((key, value));
                                            }
                                            Nothing => {}
                                        })
                                }
                            }
                        }
                    }
                    return None;
                }

                #[inline]
                fn size_hint(&self) -> (usize, Option<usize>) {
                    (self.remaining, Some(self.remaining))
                }
            });

        impl<'a, T> ExactSizeIterator for $name<'a, T> {
            fn len(&self) -> usize { self.remaining }
        }
    }
}

iterator_impl! { Iter, iter = iter, mutability = }
iterator_impl! { IterMut, iter = iter_mut, mutability = mut }

/// A bounded forward iterator over a map.
pub struct Range<'a, T: 'a>(Iter<'a, T>);

impl<'a, T> Clone for Range<'a, T> {
    fn clone(&self) -> Range<'a, T> { Range(self.0.clone()) }
}

impl<'a, T> Iterator for Range<'a, T> {
    type Item = (usize, &'a T);
    fn next(&mut self) -> Option<(usize, &'a T)> { self.0.next() }
    fn size_hint(&self) -> (usize, Option<usize>) { (0, Some(self.0.remaining)) }
}

/// A bounded forward iterator over the key-value pairs of a map, with the
/// values being mutable.
pub struct RangeMut<'a, T: 'a>(IterMut<'a, T>);

impl<'a, T> Iterator for RangeMut<'a, T> {
    type Item = (usize, &'a mut T);
    fn next(&mut self) -> Option<(usize, &'a mut T)> { self.0.next() }
    fn size_hint(&self) -> (usize, Option<usize>) { (0, Some(self.0.remaining)) }
}

impl<'a, T> IntoIterator for &'a Map<T> {
    type Item = (usize, &'a T);
    type IntoIter = Iter<'a, T>;
    fn into_iter(self) -> Iter<'a, T> { self.iter() }
}

impl<'a, T> IntoIterator for &'a mut Map<T> {
    type Item = (usize, &'a mut T);
    type IntoIter = IterMut<'a, T>;
    fn into_iter(self) -> IterMut<'a, T> { self.iter_mut() }
}

#[cfg(test)]
mod test {
    use std::usize;
    use std::hash::{Hash, Hasher};
    use std::collections::hash_map::DefaultHasher;

    use super::{Map, InternalNode};
    use super::Entry::*;
    use super::TrieNode::*;

    fn check_integrity<T>(trie: &InternalNode<T>) {
        assert!(trie.count != 0);

        let mut sum = 0;

        for x in trie.children.iter() {
            match *x {
              Nothing => (),
              Internal(ref y) => {
                  check_integrity(&**y);
                  sum += 1
              }
              External(_, _) => { sum += 1 }
            }
        }

        assert_eq!(sum, trie.count);
    }

    #[test]
    fn test_find_mut() {
        let mut m = Map::new();
        assert!(m.insert(1, 12).is_none());
        assert!(m.insert(2, 8).is_none());
        assert!(m.insert(5, 14).is_none());
        let new = 100;
        match m.get_mut(&5) {
            None => panic!(), Some(x) => *x = new
        }
        assert_eq!(m.get(&5), Some(&new));
    }

    #[test]
    fn test_find_mut_missing() {
        let mut m = Map::new();
        assert!(m.get_mut(&0).is_none());
        assert!(m.insert(1, 12).is_none());
        assert!(m.get_mut(&0).is_none());
        assert!(m.insert(2, 8).is_none());
        assert!(m.get_mut(&0).is_none());
    }

    #[test]
    fn test_step() {
        let mut trie = Map::new();
        let n = 300;

        for x in (1..n).step_by(2) {
            assert!(trie.insert(x, x + 1).is_none());
            assert!(trie.contains_key(&x));
            check_integrity(&trie.root);
        }

        for x in (0..n).step_by(2) {
            assert!(!trie.contains_key(&x));
            assert!(trie.insert(x, x + 1).is_none());
            check_integrity(&trie.root);
        }

        for x in 0..n {
            assert!(trie.contains_key(&x));
            assert!(!trie.insert(x, x + 1).is_none());
            check_integrity(&trie.root);
        }

        for x in (1..n).step_by(2) {
            assert!(trie.remove(&x).is_some());
            assert!(!trie.contains_key(&x));
            check_integrity(&trie.root);
        }

        for x in (0..n).step_by(2) {
            assert!(trie.contains_key(&x));
            assert!(!trie.insert(x, x + 1).is_none());
            check_integrity(&trie.root);
        }
    }

    #[test]
    fn test_each_reverse() {
        let mut m = Map::new();

        assert!(m.insert(3, 6).is_none());
        assert!(m.insert(0, 0).is_none());
        assert!(m.insert(4, 8).is_none());
        assert!(m.insert(2, 4).is_none());
        assert!(m.insert(1, 2).is_none());

        let mut n = 5;
        let mut vec: Vec<&i32> = vec![];
        m.each_reverse(|k, v| {
            n -= 1;
            assert_eq!(*k, n);
            vec.push(v);
            true
        });
        assert_eq!(vec, [&8, &6, &4, &2, &0]);
    }

    #[test]
    fn test_each_reverse_break() {
        let mut m = Map::new();

        for x in (usize::MAX - 10000..usize::MAX).rev() {
            m.insert(x, x / 2);
        }

        let mut n = usize::MAX - 1;
        m.each_reverse(|k, v| {
            if n == usize::MAX - 5000 { false } else {
                assert!(n > usize::MAX - 5000);

                assert_eq!(*k, n);
                assert_eq!(*v, n / 2);
                n -= 1;
                true
            }
        });
    }

    #[test]
    fn test_insert() {
        let mut m = Map::new();
        assert_eq!(m.insert(1, 2), None);
        assert_eq!(m.insert(1, 3), Some(2));
        assert_eq!(m.insert(1, 4), Some(3));
    }

    #[test]
    fn test_remove() {
        let mut m = Map::new();
        m.insert(1, 2);
        assert_eq!(m.remove(&1), Some(2));
        assert_eq!(m.remove(&1), None);
    }

    #[test]
    fn test_from_iter() {
        let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];

        let map: Map<i32> = xs.iter().cloned().collect();

        for &(k, v) in xs.iter() {
            assert_eq!(map.get(&k), Some(&v));
        }
    }

    #[test]
    fn test_keys() {
        let vec = [(1, 'a'), (2, 'b'), (3, 'c')];
        let map: Map<_> = vec.iter().cloned().collect();
        let keys: Vec<_> = map.keys().collect();
        assert_eq!(keys.len(), 3);
        assert!(keys.contains(&1));
        assert!(keys.contains(&2));
        assert!(keys.contains(&3));
    }

    #[test]
    fn test_values() {
        let vec = [(1, 'a'), (2, 'b'), (3, 'c')];
        let map: Map<_> = vec.iter().cloned().collect();
        let values: Vec<_> = map.values().cloned().collect();
        assert_eq!(values.len(), 3);
        assert!(values.contains(&'a'));
        assert!(values.contains(&'b'));
        assert!(values.contains(&'c'));
    }

    #[test]
    fn test_iteration() {
        let empty_map : Map<usize> = Map::new();
        assert_eq!(empty_map.iter().next(), None);

        let first = usize::MAX - 10000;
        let last = usize::MAX;

        let mut map = Map::new();
        for x in (first..last).rev() {
            map.insert(x, x / 2);
        }

        let mut i = 0;
        for (k, &v) in map.iter() {
            assert_eq!(k, first + i);
            assert_eq!(v, k / 2);
            i += 1;
        }
        assert_eq!(i, last - first);
    }

    #[test]
    fn test_mut_iter() {
        let mut empty_map : Map<usize> = Map::new();
        assert!(empty_map.iter_mut().next().is_none());

        let first = usize::MAX - 10000;
        let last = usize::MAX;

        let mut map = Map::new();
        for x in (first..last).rev() {
            map.insert(x, x / 2);
        }

        let mut i = 0;
        for (k, v) in map.iter_mut() {
            assert_eq!(k, first + i);
            *v -= k / 2;
            i += 1;
        }
        assert_eq!(i, last - first);

        assert!(map.iter().all(|(_, &v)| v == 0));
    }

    #[test]
    fn test_bound() {
        let empty_map : Map<usize> = Map::new();
        assert_eq!(empty_map.lower_bound(0).next(), None);
        assert_eq!(empty_map.upper_bound(0).next(), None);

        let last = 999;
        let step = 3;
        let value = 42;

        let mut map : Map<usize> = Map::new();
        for x in (0..last).step_by(step) {
            assert!(x % step == 0);
            map.insert(x, value);
        }

        for i in 0..last - step {
            let mut lb = map.lower_bound(i);
            let mut ub = map.upper_bound(i);
            let next_key = i - i % step + step;
            let next_pair = (next_key, &value);
            if i % step == 0 {
                assert_eq!(lb.next(), Some((i, &value)));
            } else {
                assert_eq!(lb.next(), Some(next_pair));
            }
            assert_eq!(ub.next(), Some(next_pair));
        }

        let mut lb = map.lower_bound(last - step);
        assert_eq!(lb.next(), Some((last - step, &value)));
        let mut ub = map.upper_bound(last - step);
        assert_eq!(ub.next(), None);

        for i in last - step + 1..last {
            let mut lb = map.lower_bound(i);
            assert_eq!(lb.next(), None);
            let mut ub = map.upper_bound(i);
            assert_eq!(ub.next(), None);
        }
    }

    #[test]
    fn test_mut_bound() {
        let empty_map : Map<usize> = Map::new();
        assert_eq!(empty_map.lower_bound(0).next(), None);
        assert_eq!(empty_map.upper_bound(0).next(), None);

        let mut m_lower = Map::new();
        let mut m_upper = Map::new();
        for i in 0..100 {
            m_lower.insert(2 * i, 4 * i);
            m_upper.insert(2 * i, 4 * i);
        }

        for i in 0..199 {
            let mut lb_it = m_lower.lower_bound_mut(i);
            let (k, v) = lb_it.next().unwrap();
            let lb = i + i % 2;
            assert_eq!(lb, k);
            *v -= k;
        }

        for i in 0..198 {
            let mut ub_it = m_upper.upper_bound_mut(i);
            let (k, v) = ub_it.next().unwrap();
            let ub = i + 2 - i % 2;
            assert_eq!(ub, k);
            *v -= k;
        }

        assert!(m_lower.lower_bound_mut(199).next().is_none());
        assert!(m_upper.upper_bound_mut(198).next().is_none());

        assert!(m_lower.iter().all(|(_, &x)| x == 0));
        assert!(m_upper.iter().all(|(_, &x)| x == 0));
    }

    #[test]
    fn test_clone() {
        let mut a = Map::new();

        a.insert(1, 'a');
        a.insert(2, 'b');
        a.insert(3, 'c');

        assert!(a.clone() == a);
    }

    #[test]
    fn test_eq() {
        let mut a = Map::new();
        let mut b = Map::new();

        assert!(a == b);
        assert!(a.insert(0, 5).is_none());
        assert!(a != b);
        assert!(b.insert(0, 4).is_none());
        assert!(a != b);
        assert!(a.insert(5, 19).is_none());
        assert!(a != b);
        assert!(!b.insert(0, 5).is_none());
        assert!(a != b);
        assert!(b.insert(5, 19).is_none());
        assert!(a == b);
    }

    #[test]
    fn test_lt() {
        let mut a = Map::new();
        let mut b = Map::new();

        assert!(!(a < b) && !(b < a));
        assert!(b.insert(2, 5).is_none());
        assert!(a < b);
        assert!(a.insert(2, 7).is_none());
        assert!(!(a < b) && b < a);
        assert!(b.insert(1, 0).is_none());
        assert!(b < a);
        assert!(a.insert(0, 6).is_none());
        assert!(a < b);
        assert!(a.insert(6, 2).is_none());
        assert!(a < b && !(b < a));
    }

    #[test]
    fn test_ord() {
        let mut a = Map::new();
        let mut b = Map::new();

        assert!(a <= b && a >= b);
        assert!(a.insert(1, 1).is_none());
        assert!(a > b && a >= b);
        assert!(b < a && b <= a);
        assert!(b.insert(2, 2).is_none());
        assert!(b > a && b >= a);
        assert!(a < b && a <= b);
    }

    #[test]
    fn test_hash() {
        fn hash<T: Hash>(t: &T) -> u64 {
            let mut s = DefaultHasher::new();
            t.hash(&mut s);
            s.finish()
        }

      let mut x = Map::new();
      let mut y = Map::new();

      assert!(hash(&x) == hash(&y));
      x.insert(1, 'a');
      x.insert(2, 'b');
      x.insert(3, 'c');

      y.insert(3, 'c');
      y.insert(2, 'b');
      y.insert(1, 'a');

      assert!(hash(&x) == hash(&y));
    }

    #[test]
    fn test_debug() {
        let mut map = Map::new();
        let empty: Map<char> = Map::new();

        map.insert(1, 'a');
        map.insert(2, 'b');

        assert_eq!(format!("{:?}", map), "{1: 'a', 2: 'b'}");
        assert_eq!(format!("{:?}", empty), "{}");
    }

    #[test]
    fn test_index() {
        let mut map = Map::new();

        map.insert(1, 2);
        map.insert(2, 1);
        map.insert(3, 4);

        assert_eq!(map[&2], 1);
    }

    #[test]
    #[should_panic]
    fn test_index_nonexistent() {
        let mut map = Map::new();

        map.insert(1, 2);
        map.insert(2, 1);
        map.insert(3, 4);

        map[&4];
    }

    // Number of items to insert into the map during entry tests.
    // The tests rely on it being even.
    const SQUARES_UPPER_LIM: usize = 128;

    /// Make a map storing i^2 for i in [0, 128)
    fn squares_map() -> Map<usize> {
        let mut map = Map::new();
        for i in 0..SQUARES_UPPER_LIM {
            map.insert(i, i * i);
        }
        map
    }

    #[test]
    fn test_entry_get() {
        let mut map = squares_map();

        for i in 0..SQUARES_UPPER_LIM {
            match map.entry(i) {
                Occupied(slot) => assert_eq!(slot.get(), &(i * i)),
                Vacant(_) => panic!("Key not found.")
            }
        }
        check_integrity(&map.root);
    }

    #[test]
    fn test_entry_get_mut() {
        let mut map = squares_map();

        // Change the entries to cubes.
        for i in 0..SQUARES_UPPER_LIM {
            match map.entry(i) {
                Occupied(mut e) => {
                    *e.get_mut() = i * i * i;
                }
                Vacant(_) => panic!("Key not found.")
            }
            assert_eq!(map.get(&i).unwrap(), &(i * i * i));
        }

        check_integrity(&map.root);
    }

    #[test]
    fn test_entry_into_mut() {
        let mut map = Map::new();
        map.insert(3, 6);

        let value_ref = match map.entry(3) {
            Occupied(e) => e.into_mut(),
            Vacant(_) => panic!("Entry not found.")
        };

        assert_eq!(*value_ref, 6);
    }

    #[test]
    fn test_entry_take() {
        let mut map = squares_map();
        assert_eq!(map.len(), SQUARES_UPPER_LIM);

        // Remove every odd key, checking that the correct value is returned.
        for i in (1..SQUARES_UPPER_LIM).step_by(2) {
            match map.entry(i) {
                Occupied(e) => assert_eq!(e.remove(), i * i),
                Vacant(_) => panic!("Key not found.")
            }
        }

        check_integrity(&map.root);

        // Check that the values for even keys remain unmodified.
        for i in (0..SQUARES_UPPER_LIM).step_by(2) {
            assert_eq!(map.get(&i).unwrap(), &(i * i));
        }

        assert_eq!(map.len(), SQUARES_UPPER_LIM / 2);
    }

    #[test]
    fn test_occupied_entry_set() {
        let mut map = squares_map();

        // Change all the entries to cubes.
        for i in 0..SQUARES_UPPER_LIM {
            match map.entry(i) {
                Occupied(mut e) => assert_eq!(e.insert(i * i * i), i * i),
                Vacant(_) => panic!("Key not found.")
            }
            assert_eq!(map.get(&i).unwrap(), &(i * i * i));
        }
        check_integrity(&map.root);
    }

    #[test]
    fn test_vacant_entry_set() {
        let mut map = Map::new();

        for i in 0..SQUARES_UPPER_LIM {
            match map.entry(i) {
                Vacant(e) => {
                    // Insert i^2.
                    let inserted_val = e.insert(i * i);
                    assert_eq!(*inserted_val, i * i);

                    // Update it to i^3 using the returned mutable reference.
                    *inserted_val = i * i * i;
                },
                _ => panic!("Non-existent key found.")
            }
            assert_eq!(map.get(&i).unwrap(), &(i * i * i));
        }

        check_integrity(&map.root);
        assert_eq!(map.len(), SQUARES_UPPER_LIM);
    }

    #[test]
    fn test_single_key() {
        let mut map = Map::new();
        map.insert(1, 2);

        match map.entry(1) {
            Occupied(e) => { e.remove(); },
            _ => ()
        }
    }
}

#[cfg(test)]
mod bench {
    use rand::{weak_rng, Rng};
    use test::{Bencher, black_box};

    use super::{Map, Occupied, Vacant};

    const MAP_SIZE: usize = 1000;

    map_insert_rand_bench!{insert_rand_100,    100,    Map}
    map_insert_rand_bench!{insert_rand_10_000, 10_000, Map}

    map_insert_seq_bench!{insert_seq_100,    100,    Map}
    map_insert_seq_bench!{insert_seq_10_000, 10_000, Map}

    map_find_rand_bench!{find_rand_100,    100,    Map}
    map_find_rand_bench!{find_rand_10_000, 10_000, Map}

    map_find_seq_bench!{find_seq_100,    100,    Map}
    map_find_seq_bench!{find_seq_10_000, 10_000, Map}

    fn random_map(size: usize) -> Map<usize> {
        let mut map = Map::<usize>::new();
        let mut rng = weak_rng();

        for _ in 0..size {
            map.insert(rng.gen(), rng.gen());
        }
        map
    }

    fn bench_iter(b: &mut Bencher, size: usize) {
        let map = random_map(size);
        b.iter(|| {
            for entry in map.iter() {
                black_box(entry);
            }
        });
    }

    #[bench]
    pub fn iter_20(b: &mut Bencher) {
        bench_iter(b, 20);
    }

    #[bench]
    pub fn iter_1000(b: &mut Bencher) {
        bench_iter(b, 1000);
    }

    #[bench]
    pub fn iter_100000(b: &mut Bencher) {
        bench_iter(b, 100000);
    }

    #[bench]
    fn bench_lower_bound(b: &mut Bencher) {
        let mut m = Map::<usize>::new();
        let mut rng = weak_rng();
        for _ in 0..MAP_SIZE {
            m.insert(rng.gen(), rng.gen());
        }

        b.iter(|| {
            for _ in 0..10 {
                m.lower_bound(rng.gen());
            }
        });
    }

    #[bench]
    fn bench_upper_bound(b: &mut Bencher) {
        let mut m = Map::<usize>::new();
        let mut rng = weak_rng();
        for _ in 0..MAP_SIZE {
            m.insert(rng.gen(), rng.gen());
        }

        b.iter(|| {
            for _ in 0..10 {
                m.upper_bound(rng.gen());
            }
        });
    }

    #[bench]
    fn bench_insert_large(b: &mut Bencher) {
        let mut m = Map::<[usize; 10]>::new();
        let mut rng = weak_rng();

        b.iter(|| {
            for _ in 0..MAP_SIZE {
                m.insert(rng.gen(), [1; 10]);
            }
        });
    }

    #[bench]
    fn bench_insert_large_entry(b: &mut Bencher) {
        let mut m = Map::<[usize; 10]>::new();
        let mut rng = weak_rng();

        b.iter(|| {
            for _ in 0..MAP_SIZE {
                match m.entry(rng.gen()) {
                    Occupied(mut e) => { e.insert([1; 10]); },
                    Vacant(e) => { e.insert([1; 10]); }
                }
            }
        });
    }

    #[bench]
    fn bench_insert_large_low_bits(b: &mut Bencher) {
        let mut m = Map::<[usize; 10]>::new();
        let mut rng = weak_rng();

        b.iter(|| {
            for _ in 0..MAP_SIZE {
                // only have the last few bits set.
                m.insert(rng.gen::<usize>() & 0xff_ff, [1; 10]);
            }
        });
    }

    #[bench]
    fn bench_insert_small(b: &mut Bencher) {
        let mut m = Map::<()>::new();
        let mut rng = weak_rng();

        b.iter(|| {
            for _ in 0..MAP_SIZE {
                m.insert(rng.gen(), ());
            }
        });
    }

    #[bench]
    fn bench_insert_small_low_bits(b: &mut Bencher) {
        let mut m = Map::<()>::new();
        let mut rng = weak_rng();

        b.iter(|| {
            for _ in 0..MAP_SIZE {
                // only have the last few bits set.
                m.insert(rng.gen::<usize>() & 0xff_ff, ());
            }
        });
    }

    #[bench]
    fn bench_get(b: &mut Bencher) {
        let map = random_map(MAP_SIZE);
        let keys: Vec<usize> = map.keys().collect();
        b.iter(|| {
            for key in keys.iter() {
                black_box(map.get(key));
            }
        });
    }

    #[bench]
    fn bench_get_entry(b: &mut Bencher) {
        let mut map = random_map(MAP_SIZE);
        let keys: Vec<usize> = map.keys().collect();
        b.iter(|| {
            for key in keys.iter() {
                match map.entry(*key) {
                    Occupied(e) => { black_box(e.get()); },
                    _ => ()
                }
            }
        });
    }

    #[bench]
    fn bench_remove(b: &mut Bencher) {
        b.iter(|| {
            let mut map = random_map(MAP_SIZE);
            let keys: Vec<usize> = map.keys().collect();
            for key in keys.iter() {
                black_box(map.remove(key));
            }
        });
    }

    #[bench]
    fn bench_remove_entry(b: &mut Bencher) {
        b.iter(|| {
            let mut map = random_map(MAP_SIZE);
            let keys: Vec<usize> = map.keys().collect();
            for key in keys.iter() {
                match map.entry(*key) {
                    Occupied(e) => { black_box(e.remove()); },
                    _ => ()
                }
            }
        });
    }
}