run rustfmt on map.rs in libcollections/btree folder

1 files changed, 274 insertions, 220 deletions

diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs
index 29f3e4b1b61..248240a7de8 100644
--- a/src/libcollections/btree/map.rs
+++ b/src/libcollections/btree/map.rs
@@ -17,9 +17,9 @@ use core::ops::Index;
 use core::{fmt, intrinsics, mem, ptr};
 
 use borrow::Borrow;
-use Bound::{self, Included, Excluded, Unbounded};
+use Bound::{self, Excluded, Included, Unbounded};
 
-use super::node::{self, NodeRef, Handle, marker};
+use super::node::{self, Handle, NodeRef, marker};
 use super::search;
 
 use super::node::InsertResult::*;
@@ -129,35 +129,38 @@ use self::Entry::*;
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct BTreeMap<K, V> {
     root: node::Root<K, V>,
-    length: usize
+    length: usize,
 }
 
 impl<K, V> Drop for BTreeMap<K, V> {
     #[unsafe_destructor_blind_to_params]
     fn drop(&mut self) {
         unsafe {
-            for _ in ptr::read(self).into_iter() { }
+            for _ in ptr::read(self).into_iter() {
+            }
         }
     }
 }
 
 impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
     fn clone(&self) -> BTreeMap<K, V> {
-        fn clone_subtree<K: Clone, V: Clone>(
-                node: node::NodeRef<marker::Immut, K, V, marker::LeafOrInternal>)
-                -> BTreeMap<K, V> {
+        fn clone_subtree<K: Clone, V: Clone>(node: node::NodeRef<marker::Immut,
+                                                                 K,
+                                                                 V,
+                                                                 marker::LeafOrInternal>)
+                                             -> BTreeMap<K, V> {
 
             match node.force() {
                 Leaf(leaf) => {
                     let mut out_tree = BTreeMap {
                         root: node::Root::new_leaf(),
-                        length: 0
+                        length: 0,
                     };
 
                     {
                         let mut out_node = match out_tree.root.as_mut().force() {
                             Leaf(leaf) => leaf,
-                            Internal(_) => unreachable!()
+                            Internal(_) => unreachable!(),
                         };
 
                         let mut in_edge = leaf.first_edge();
@@ -171,7 +174,7 @@ impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
                     }
 
                     out_tree
-                },
+                }
                 Internal(internal) => {
                     let mut out_tree = clone_subtree(internal.first_edge().descend());
 
@@ -218,7 +221,7 @@ impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
     fn get(&self, key: &Q) -> Option<&K> {
         match search::search_tree(self.root.as_ref(), key) {
             Found(handle) => Some(handle.into_kv().0),
-            GoDown(_) => None
+            GoDown(_) => None,
         }
     }
 
@@ -226,12 +229,14 @@ impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
         match search::search_tree(self.root.as_mut(), key) {
             Found(handle) => {
                 Some(OccupiedEntry {
-                    handle: handle,
-                    length: &mut self.length,
-                    _marker: PhantomData,
-                }.remove_kv().0)
-            },
-            GoDown(_) => None
+                         handle: handle,
+                         length: &mut self.length,
+                         _marker: PhantomData,
+                     }
+                     .remove_kv()
+                     .0)
+            }
+            GoDown(_) => None,
         }
     }
 
@@ -244,7 +249,8 @@ impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
                     handle: handle,
                     length: &mut self.length,
                     _marker: PhantomData,
-                }.insert(());
+                }
+                .insert(());
                 None
             }
         }
@@ -255,14 +261,14 @@ impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Iter<'a, K: 'a, V: 'a> {
     range: Range<'a, K, V>,
-    length: usize
+    length: usize,
 }
 
 /// A mutable iterator over a BTreeMap's entries.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IterMut<'a, K: 'a, V: 'a> {
     range: RangeMut<'a, K, V>,
-    length: usize
+    length: usize,
 }
 
 /// An owning iterator over a BTreeMap's entries.
@@ -270,7 +276,7 @@ pub struct IterMut<'a, K: 'a, V: 'a> {
 pub struct IntoIter<K, V> {
     front: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
     back: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
-    length: usize
+    length: usize,
 }
 
 /// An iterator over a BTreeMap's keys.
@@ -294,7 +300,7 @@ pub struct ValuesMut<'a, K: 'a, V: 'a> {
 /// An iterator over a sub-range of BTreeMap's entries.
 pub struct Range<'a, K: 'a, V: 'a> {
     front: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
-    back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>
+    back: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
 }
 
 /// A mutable iterator over a sub-range of BTreeMap's entries.
@@ -311,15 +317,13 @@ pub struct RangeMut<'a, K: 'a, V: 'a> {
 pub enum Entry<'a, K: 'a, V: 'a> {
     /// A vacant Entry
     #[stable(feature = "rust1", since = "1.0.0")]
-    Vacant(
-        #[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>
-    ),
+    Vacant(#[stable(feature = "rust1", since = "1.0.0")]
+           VacantEntry<'a, K, V>),
 
     /// An occupied Entry
     #[stable(feature = "rust1", since = "1.0.0")]
-    Occupied(
-        #[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>
-    ),
+    Occupied(#[stable(feature = "rust1", since = "1.0.0")]
+             OccupiedEntry<'a, K, V>),
 }
 
 /// A vacant Entry.
@@ -336,11 +340,7 @@ pub struct VacantEntry<'a, K: 'a, V: 'a> {
 /// An occupied Entry.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
-    handle: Handle<NodeRef<
-        marker::Mut<'a>,
-        K, V,
-        marker::LeafOrInternal
-    >, marker::KV>,
+    handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>,
 
     length: &'a mut usize,
 
@@ -349,7 +349,7 @@ pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
 }
 
 // An iterator for merging two sorted sequences into one
-struct MergeIter<K, V, I: Iterator<Item=(K, V)>> {
+struct MergeIter<K, V, I: Iterator<Item = (K, V)>> {
     left: Peekable<I>,
     right: Peekable<I>,
 }
@@ -373,7 +373,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
     pub fn new() -> BTreeMap<K, V> {
         BTreeMap {
             root: node::Root::new_leaf(),
-            length: 0
+            length: 0,
         }
     }
 
@@ -415,10 +415,13 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// assert_eq!(map.get(&2), None);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord {
+    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
+        where K: Borrow<Q>,
+              Q: Ord
+    {
         match search::search_tree(self.root.as_ref(), key) {
             Found(handle) => Some(handle.into_kv().1),
-            GoDown(_) => None
+            GoDown(_) => None,
         }
     }
 
@@ -440,7 +443,10 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// assert_eq!(map.contains_key(&2), false);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord {
+    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
+        where K: Borrow<Q>,
+              Q: Ord
+    {
         self.get(key).is_some()
     }
 
@@ -465,10 +471,13 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// ```
     // See `get` for implementation notes, this is basically a copy-paste with mut's added
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord {
+    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
+        where K: Borrow<Q>,
+              Q: Ord
+    {
         match search::search_tree(self.root.as_mut(), key) {
             Found(handle) => Some(handle.into_kv_mut().1),
-            GoDown(_) => None
+            GoDown(_) => None,
         }
     }
 
@@ -528,16 +537,20 @@ impl<K: Ord, V> BTreeMap<K, V> {
     /// assert_eq!(map.remove(&1), None);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord {
+    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
+        where K: Borrow<Q>,
+              Q: Ord
+    {
         match search::search_tree(self.root.as_mut(), key) {
             Found(handle) => {
                 Some(OccupiedEntry {
-                    handle: handle,
-                    length: &mut self.length,
-                    _marker: PhantomData,
-                }.remove())
-            },
-            GoDown(_) => None
+                         handle: handle,
+                         length: &mut self.length,
+                         _marker: PhantomData,
+                     }
+                     .remove())
+            }
+            GoDown(_) => None,
         }
     }
 
@@ -628,47 +641,63 @@ impl<K: Ord, V> BTreeMap<K, V> {
                                                        min: Bound<&Min>,
                                                        max: Bound<&Max>)
                                                        -> Range<K, V>
-        where K: Borrow<Min> + Borrow<Max>,
+        where K: Borrow<Min> + Borrow<Max>
     {
         let front = match min {
-            Included(key) => match search::search_tree(self.root.as_ref(), key) {
-                Found(kv_handle) => match kv_handle.left_edge().force() {
-                    Leaf(bottom) => bottom,
-                    Internal(internal) => last_leaf_edge(internal.descend())
-                },
-                GoDown(bottom) => bottom
-            },
-            Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
-                Found(kv_handle) => match kv_handle.right_edge().force() {
-                    Leaf(bottom) => bottom,
-                    Internal(internal) => first_leaf_edge(internal.descend())
-                },
-                GoDown(bottom) => bottom
-            },
-            Unbounded => first_leaf_edge(self.root.as_ref())
+            Included(key) => {
+                match search::search_tree(self.root.as_ref(), key) {
+                    Found(kv_handle) => {
+                        match kv_handle.left_edge().force() {
+                            Leaf(bottom) => bottom,
+                            Internal(internal) => last_leaf_edge(internal.descend()),
+                        }
+                    }
+                    GoDown(bottom) => bottom,
+                }
+            }
+            Excluded(key) => {
+                match search::search_tree(self.root.as_ref(), key) {
+                    Found(kv_handle) => {
+                        match kv_handle.right_edge().force() {
+                            Leaf(bottom) => bottom,
+                            Internal(internal) => first_leaf_edge(internal.descend()),
+                        }
+                    }
+                    GoDown(bottom) => bottom,
+                }
+            }
+            Unbounded => first_leaf_edge(self.root.as_ref()),
         };
 
         let back = match max {
-            Included(key) => match search::search_tree(self.root.as_ref(), key) {
-                Found(kv_handle) => match kv_handle.right_edge().force() {
-                    Leaf(bottom) => bottom,
-                    Internal(internal) => first_leaf_edge(internal.descend())
-                },
-                GoDown(bottom) => bottom
-            },
-            Excluded(key) => match search::search_tree(self.root.as_ref(), key) {
-                Found(kv_handle) => match kv_handle.left_edge().force() {
-                    Leaf(bottom) => bottom,
-                    Internal(internal) => last_leaf_edge(internal.descend())
-                },
-                GoDown(bottom) => bottom
-            },
-            Unbounded => last_leaf_edge(self.root.as_ref())
+            Included(key) => {
+                match search::search_tree(self.root.as_ref(), key) {
+                    Found(kv_handle) => {
+                        match kv_handle.right_edge().force() {
+                            Leaf(bottom) => bottom,
+                            Internal(internal) => first_leaf_edge(internal.descend()),
+                        }
+                    }
+                    GoDown(bottom) => bottom,
+                }
+            }
+            Excluded(key) => {
+                match search::search_tree(self.root.as_ref(), key) {
+                    Found(kv_handle) => {
+                        match kv_handle.left_edge().force() {
+                            Leaf(bottom) => bottom,
+                            Internal(internal) => last_leaf_edge(internal.descend()),
+                        }
+                    }
+                    GoDown(bottom) => bottom,
+                }
+            }
+            Unbounded => last_leaf_edge(self.root.as_ref()),
         };
 
         Range {
             front: front,
-            back: back
+            back: back,
         }
     }
 
@@ -704,51 +733,67 @@ impl<K: Ord, V> BTreeMap<K, V> {
                                                            min: Bound<&Min>,
                                                            max: Bound<&Max>)
                                                            -> RangeMut<K, V>
-        where K: Borrow<Min> + Borrow<Max>,
+        where K: Borrow<Min> + Borrow<Max>
     {
         let root1 = self.root.as_mut();
         let root2 = unsafe { ptr::read(&root1) };
 
         let front = match min {
-            Included(key) => match search::search_tree(root1, key) {
-                Found(kv_handle) => match kv_handle.left_edge().force() {
-                    Leaf(bottom) => bottom,
-                    Internal(internal) => last_leaf_edge(internal.descend())
-                },
-                GoDown(bottom) => bottom
-            },
-            Excluded(key) => match search::search_tree(root1, key) {
-                Found(kv_handle) => match kv_handle.right_edge().force() {
-                    Leaf(bottom) => bottom,
-                    Internal(internal) => first_leaf_edge(internal.descend())
-                },
-                GoDown(bottom) => bottom
-            },
-            Unbounded => first_leaf_edge(root1)
+            Included(key) => {
+                match search::search_tree(root1, key) {
+                    Found(kv_handle) => {
+                        match kv_handle.left_edge().force() {
+                            Leaf(bottom) => bottom,
+                            Internal(internal) => last_leaf_edge(internal.descend()),
+                        }
+                    }
+                    GoDown(bottom) => bottom,
+                }
+            }
+            Excluded(key) => {
+                match search::search_tree(root1, key) {
+                    Found(kv_handle) => {
+                        match kv_handle.right_edge().force() {
+                            Leaf(bottom) => bottom,
+                            Internal(internal) => first_leaf_edge(internal.descend()),
+                        }
+                    }
+                    GoDown(bottom) => bottom,
+                }
+            }
+            Unbounded => first_leaf_edge(root1),
         };
 
         let back = match max {
-            Included(key) => match search::search_tree(root2, key) {
-                Found(kv_handle) => match kv_handle.right_edge().force() {
-                    Leaf(bottom) => bottom,
-                    Internal(internal) => first_leaf_edge(internal.descend())
-                },
-                GoDown(bottom) => bottom
-            },
-            Excluded(key) => match search::search_tree(root2, key) {
-                Found(kv_handle) => match kv_handle.left_edge().force() {
-                    Leaf(bottom) => bottom,
-                    Internal(internal) => last_leaf_edge(internal.descend())
-                },
-                GoDown(bottom) => bottom
-            },
-            Unbounded => last_leaf_edge(root2)
+            Included(key) => {
+                match search::search_tree(root2, key) {
+                    Found(kv_handle) => {
+                        match kv_handle.right_edge().force() {
+                            Leaf(bottom) => bottom,
+                            Internal(internal) => first_leaf_edge(internal.descend()),
+                        }
+                    }
+                    GoDown(bottom) => bottom,
+                }
+            }
+            Excluded(key) => {
+                match search::search_tree(root2, key) {
+                    Found(kv_handle) => {
+                        match kv_handle.left_edge().force() {
+                            Leaf(bottom) => bottom,
+                            Internal(internal) => last_leaf_edge(internal.descend()),
+                        }
+                    }
+                    GoDown(bottom) => bottom,
+                }
+            }
+            Unbounded => last_leaf_edge(root2),
         };
 
         RangeMut {
             front: front,
             back: back,
-            _marker: PhantomData
+            _marker: PhantomData,
         }
     }
 
@@ -773,21 +818,25 @@ impl<K: Ord, V> BTreeMap<K, V> {
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn entry(&mut self, key: K) -> Entry<K, V> {
         match search::search_tree(self.root.as_mut(), &key) {
-            Found(handle) => Occupied(OccupiedEntry {
-                handle: handle,
-                length: &mut self.length,
-                _marker: PhantomData,
-            }),
-            GoDown(handle) => Vacant(VacantEntry {
-                key: key,
-                handle: handle,
-                length: &mut self.length,
-                _marker: PhantomData,
-            })
+            Found(handle) => {
+                Occupied(OccupiedEntry {
+                    handle: handle,
+                    length: &mut self.length,
+                    _marker: PhantomData,
+                })
+            }
+            GoDown(handle) => {
+                Vacant(VacantEntry {
+                    key: key,
+                    handle: handle,
+                    length: &mut self.length,
+                    _marker: PhantomData,
+                })
+            }
         }
     }
 
-    fn from_sorted_iter<I: Iterator<Item=(K, V)>>(&mut self, iter: I) {
+    fn from_sorted_iter<I: Iterator<Item = (K, V)>>(&mut self, iter: I) {
         let mut cur_node = last_leaf_edge(self.root.as_mut()).into_node();
         // Iterate through all key-value pairs, pushing them into nodes at the right level.
         for (key, value) in iter {
@@ -810,12 +859,12 @@ impl<K: Ord, V> BTreeMap<K, V> {
                                 // Go up again.
                                 test_node = parent.forget_type();
                             }
-                        },
+                        }
                         Err(node) => {
                             // We are at the top, create a new root node and push there.
                             open_node = node.into_root_mut().push_level();
                             break;
-                        },
+                        }
                     }
                 }
 
@@ -890,7 +939,9 @@ impl<K: Ord, V> BTreeMap<K, V> {
     #[unstable(feature = "btree_split_off",
                reason = "recently added as part of collections reform 2",
                issue = "19986")]
-    pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self where K: Borrow<Q> {
+    pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
+        where K: Borrow<Q>
+    {
         if self.is_empty() {
             return Self::new();
         }
@@ -910,7 +961,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
                 let mut split_edge = match search::search_node(left_node, key) {
                     // key is going to the right tree
                     Found(handle) => handle.left_edge(),
-                    GoDown(handle) => handle
+                    GoDown(handle) => handle,
                 };
 
                 split_edge.move_suffix(&mut right_node);
@@ -920,8 +971,12 @@ impl<K: Ord, V> BTreeMap<K, V> {
                         left_node = edge.descend();
                         right_node = node.first_edge().descend();
                     }
-                    (Leaf(_), Leaf(_)) => { break; },
-                    _ => { unreachable!(); }
+                    (Leaf(_), Leaf(_)) => {
+                        break;
+                    }
+                    _ => {
+                        unreachable!();
+                    }
                 }
             }
         }
@@ -950,8 +1005,12 @@ impl<K: Ord, V> BTreeMap<K, V> {
                 loop {
                     res += dfs(edge.reborrow().descend());
                     match edge.right_kv() {
-                        Ok(right_kv) => { edge = right_kv.right_edge(); },
-                        Err(_) => { break; }
+                        Ok(right_kv) => {
+                            edge = right_kv.right_edge();
+                        }
+                        Err(_) => {
+                            break;
+                        }
                     }
                 }
             }
@@ -1064,14 +1123,16 @@ impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
 }
 
 impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> {
-    fn len(&self) -> usize { self.length }
+    fn len(&self) -> usize {
+        self.length
+    }
 }
 
 impl<'a, K, V> Clone for Iter<'a, K, V> {
     fn clone(&self) -> Iter<'a, K, V> {
         Iter {
             range: self.range.clone(),
-            length: self.length
+            length: self.length,
         }
     }
 }
@@ -1114,7 +1175,9 @@ impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
 }
 
 impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> {
-    fn len(&self) -> usize { self.length }
+    fn len(&self) -> usize {
+        self.length
+    }
 }
 
 impl<K, V> IntoIterator for BTreeMap<K, V> {
@@ -1130,14 +1193,15 @@ impl<K, V> IntoIterator for BTreeMap<K, V> {
         IntoIter {
             front: first_leaf_edge(root1),
             back: last_leaf_edge(root2),
-            length: len
+            length: len,
         }
     }
 }
 
 impl<K, V> Drop for IntoIter<K, V> {
     fn drop(&mut self) {
-        for _ in &mut *self { }
+        for _ in &mut *self {
+        }
         unsafe {
             let leaf_node = ptr::read(&self.front).into_node();
             if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
@@ -1168,10 +1232,10 @@ impl<K, V> Iterator for IntoIter<K, V> {
                 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
                 self.front = kv.right_edge();
                 return Some((k, v));
-            },
+            }
             Err(last_edge) => unsafe {
                 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
-            }
+            },
         };
 
         loop {
@@ -1181,10 +1245,10 @@ impl<K, V> Iterator for IntoIter<K, V> {
                     let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
                     self.front = first_leaf_edge(kv.right_edge().descend());
                     return Some((k, v));
-                },
+                }
                 Err(last_edge) => unsafe {
                     cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
-                }
+                },
             }
         }
     }
@@ -1210,10 +1274,10 @@ impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
                 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
                 self.back = kv.left_edge();
                 return Some((k, v));
-            },
+            }
             Err(last_edge) => unsafe {
                 unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
-            }
+            },
         };
 
         loop {
@@ -1223,17 +1287,19 @@ impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
                     let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
                     self.back = last_leaf_edge(kv.left_edge().descend());
                     return Some((k, v));
-                },
+                }
                 Err(last_edge) => unsafe {
                     cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
-                }
+                },
             }
         }
     }
 }
 
 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
-    fn len(&self) -> usize { self.length }
+    fn len(&self) -> usize {
+        self.length
+    }
 }
 
 impl<'a, K, V> Iterator for Keys<'a, K, V> {
@@ -1262,9 +1328,7 @@ impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
 
 impl<'a, K, V> Clone for Keys<'a, K, V> {
     fn clone(&self) -> Keys<'a, K, V> {
-        Keys {
-            inner: self.inner.clone()
-        }
+        Keys { inner: self.inner.clone() }
     }
 }
 
@@ -1294,9 +1358,7 @@ impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
 
 impl<'a, K, V> Clone for Values<'a, K, V> {
     fn clone(&self) -> Values<'a, K, V> {
-        Values {
-            inner: self.inner.clone()
-        }
+        Values { inner: self.inner.clone() }
     }
 }
 
@@ -1348,7 +1410,7 @@ impl<'a, K, V> Range<'a, K, V> {
                 let ret = kv.into_kv();
                 self.front = kv.right_edge();
                 return ret;
-            },
+            }
             Err(last_edge) => {
                 let next_level = last_edge.into_node().ascend().ok();
                 unwrap_unchecked(next_level)
@@ -1361,7 +1423,7 @@ impl<'a, K, V> Range<'a, K, V> {
                     let ret = kv.into_kv();
                     self.front = first_leaf_edge(kv.right_edge().descend());
                     return ret;
-                },
+                }
                 Err(last_edge) => {
                     let next_level = last_edge.into_node().ascend().ok();
                     cur_handle = unwrap_unchecked(next_level);
@@ -1390,7 +1452,7 @@ impl<'a, K, V> Range<'a, K, V> {
                 let ret = kv.into_kv();
                 self.back = kv.left_edge();
                 return ret;
-            },
+            }
             Err(last_edge) => {
                 let next_level = last_edge.into_node().ascend().ok();
                 unwrap_unchecked(next_level)
@@ -1403,7 +1465,7 @@ impl<'a, K, V> Range<'a, K, V> {
                     let ret = kv.into_kv();
                     self.back = last_leaf_edge(kv.left_edge().descend());
                     return ret;
-                },
+                }
                 Err(last_edge) => {
                     let next_level = last_edge.into_node().ascend().ok();
                     cur_handle = unwrap_unchecked(next_level);
@@ -1417,7 +1479,7 @@ impl<'a, K, V> Clone for Range<'a, K, V> {
     fn clone(&self) -> Range<'a, K, V> {
         Range {
             front: self.front,
-            back: self.back
+            back: self.back,
         }
     }
 }
@@ -1429,7 +1491,7 @@ impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
         if self.front == self.back {
             None
         } else {
-            unsafe { Some (self.next_unchecked()) }
+            unsafe { Some(self.next_unchecked()) }
         }
     }
 }
@@ -1443,7 +1505,7 @@ impl<'a, K, V> RangeMut<'a, K, V> {
                 let (k, v) = ptr::read(&kv).into_kv_mut();
                 self.front = kv.right_edge();
                 return (k, v);
-            },
+            }
             Err(last_edge) => {
                 let next_level = last_edge.into_node().ascend().ok();
                 unwrap_unchecked(next_level)
@@ -1456,7 +1518,7 @@ impl<'a, K, V> RangeMut<'a, K, V> {
                     let (k, v) = ptr::read(&kv).into_kv_mut();
                     self.front = first_leaf_edge(kv.right_edge().descend());
                     return (k, v);
-                },
+                }
                 Err(last_edge) => {
                     let next_level = last_edge.into_node().ascend().ok();
                     cur_handle = unwrap_unchecked(next_level);
@@ -1485,7 +1547,7 @@ impl<'a, K, V> RangeMut<'a, K, V> {
                 let (k, v) = ptr::read(&kv).into_kv_mut();
                 self.back = kv.left_edge();
                 return (k, v);
-            },
+            }
             Err(last_edge) => {
                 let next_level = last_edge.into_node().ascend().ok();
                 unwrap_unchecked(next_level)
@@ -1498,7 +1560,7 @@ impl<'a, K, V> RangeMut<'a, K, V> {
                     let (k, v) = ptr::read(&kv).into_kv_mut();
                     self.back = last_leaf_edge(kv.left_edge().descend());
                     return (k, v);
-                },
+                }
                 Err(last_edge) => {
                     let next_level = last_edge.into_node().ascend().ok();
                     cur_handle = unwrap_unchecked(next_level);
@@ -1509,7 +1571,7 @@ impl<'a, K, V> RangeMut<'a, K, V> {
 }
 
 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
-    fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
+    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> {
         let mut map = BTreeMap::new();
         map.extend(iter);
         map
@@ -1518,7 +1580,7 @@ impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
 
 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
     #[inline]
-    fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
+    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
         for (k, v) in iter {
             self.insert(k, v);
         }
@@ -1526,7 +1588,7 @@ impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
 }
 
 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
-    fn extend<I: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: I) {
+    fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
         self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
     }
 }
@@ -1547,8 +1609,7 @@ impl<K: Ord, V> Default for BTreeMap<K, V> {
 
 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
     fn eq(&self, other: &BTreeMap<K, V>) -> bool {
-        self.len() == other.len() &&
-            self.iter().zip(other).all(|(a, b)| a == b)
+        self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
     }
 }
 
@@ -1575,7 +1636,8 @@ impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
 }
 
 impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
-    where K: Borrow<Q>, Q: Ord
+    where K: Borrow<Q>,
+          Q: Ord
 {
     type Output = V;
 
@@ -1585,11 +1647,9 @@ impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
     }
 }
 
-fn first_leaf_edge<BorrowType, K, V>(
-        mut node: NodeRef<BorrowType,
-                          K, V,
-                          marker::LeafOrInternal>
-        ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+fn first_leaf_edge<BorrowType, K, V>
+    (mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>)
+     -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
     loop {
         match node.force() {
             Leaf(leaf) => return leaf.first_edge(),
@@ -1600,11 +1660,9 @@ fn first_leaf_edge<BorrowType, K, V>(
     }
 }
 
-fn last_leaf_edge<BorrowType, K, V>(
-        mut node: NodeRef<BorrowType,
-                          K, V,
-                          marker::LeafOrInternal>
-        ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+fn last_leaf_edge<BorrowType, K, V>
+    (mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>)
+     -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
     loop {
         match node.force() {
             Leaf(leaf) => return leaf.last_edge(),
@@ -1653,9 +1711,9 @@ impl<K, V> BTreeMap<K, V> {
         Iter {
             range: Range {
                 front: first_leaf_edge(self.root.as_ref()),
-                back: last_leaf_edge(self.root.as_ref())
+                back: last_leaf_edge(self.root.as_ref()),
             },
-            length: self.length
+            length: self.length,
         }
     }
 
@@ -1690,7 +1748,7 @@ impl<K, V> BTreeMap<K, V> {
                 back: last_leaf_edge(root2),
                 _marker: PhantomData,
             },
-            length: self.length
+            length: self.length,
         }
     }
 
@@ -1865,15 +1923,17 @@ impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
 
         loop {
             match cur_parent {
-                Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) {
-                    Fit(_) => return unsafe { &mut *out_ptr },
-                    Split(left, k, v, right) => {
-                        ins_k = k;
-                        ins_v = v;
-                        ins_edge = right;
-                        cur_parent = left.ascend().map_err(|n| n.into_root_mut());
+                Ok(parent) => {
+                    match parent.insert(ins_k, ins_v, ins_edge) {
+                        Fit(_) => return unsafe { &mut *out_ptr },
+                        Split(left, k, v, right) => {
+                            ins_k = k;
+                            ins_v = v;
+                            ins_edge = right;
+                            cur_parent = left.ascend().map_err(|n| n.into_root_mut());
+                        }
                     }
-                },
+                }
                 Err(root) => {
                     root.push_level().push(ins_k, ins_v, ins_edge);
                     return unsafe { &mut *out_ptr };
@@ -1928,7 +1988,7 @@ impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
             Leaf(leaf) => {
                 let (hole, old_key, old_val) = leaf.remove();
                 (hole.into_node(), old_key, old_val)
-            },
+            }
             Internal(mut internal) => {
                 let key_loc = internal.kv_mut().0 as *mut K;
                 let val_loc = internal.kv_mut().1 as *mut V;
@@ -1938,12 +1998,8 @@ impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
 
                 let (hole, key, val) = to_remove.remove();
 
-                let old_key = unsafe {
-                    mem::replace(&mut *key_loc, key)
-                };
-                let old_val = unsafe {
-                    mem::replace(&mut *val_loc, val)
-                };
+                let old_key = unsafe { mem::replace(&mut *key_loc, key) };
+                let old_val = unsafe { mem::replace(&mut *val_loc, val) };
 
                 (hole.into_node(), old_key, old_val)
             }
@@ -1955,14 +2011,16 @@ impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
             match handle_underfull_node(cur_node) {
                 AtRoot => break,
                 EmptyParent(_) => unreachable!(),
-                Merged(parent) => if parent.len() == 0 {
-                    // We must be at the root
-                    parent.into_root_mut().pop_level();
-                    break;
-                } else {
-                    cur_node = parent.forget_type();
-                },
-                Stole(_) => break
+                Merged(parent) => {
+                    if parent.len() == 0 {
+                        // We must be at the root
+                        parent.into_root_mut().pop_level();
+                        break;
+                    } else {
+                        cur_node = parent.forget_type();
+                    }
+                }
+                Stole(_) => break,
             }
         }
 
@@ -1974,13 +2032,11 @@ enum UnderflowResult<'a, K, V> {
     AtRoot,
     EmptyParent(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
     Merged(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
-    Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>)
+    Stole(NodeRef<marker::Mut<'a>, K, V, marker::Internal>),
 }
 
-fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
-                                                 K, V,
-                                                 marker::LeafOrInternal>)
-                                                 -> UnderflowResult<'a, K, V> {
+fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>)
+                                   -> UnderflowResult<'a, K, V> {
     let parent = if let Ok(parent) = node.ascend() {
         parent
     } else {
@@ -1989,10 +2045,12 @@ fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
 
     let (is_left, mut handle) = match parent.left_kv() {
         Ok(left) => (true, left),
-        Err(parent) => match parent.right_kv() {
-            Ok(right) => (false, right),
-            Err(parent) => {
-                return EmptyParent(parent.into_node());
+        Err(parent) => {
+            match parent.right_kv() {
+                Ok(right) => (false, right),
+                Err(parent) => {
+                    return EmptyParent(parent.into_node());
+                }
             }
         }
     };
@@ -2009,7 +2067,7 @@ fn handle_underfull_node<'a, K, V>(node: NodeRef<marker::Mut<'a>,
     }
 }
 
-impl<K: Ord, V, I: Iterator<Item=(K, V)>> Iterator for MergeIter<K, V, I> {
+impl<K: Ord, V, I: Iterator<Item = (K, V)>> Iterator for MergeIter<K, V, I> {
     type Item = (K, V);
 
     fn next(&mut self) -> Option<(K, V)> {
@@ -2023,16 +2081,12 @@ impl<K: Ord, V, I: Iterator<Item=(K, V)>> Iterator for MergeIter<K, V, I> {
         // Check which elements comes first and only advance the corresponding iterator.
         // If two keys are equal, take the value from `right`.
         match res {
-            Ordering::Less => {
-                self.left.next()
-            },
-            Ordering::Greater => {
-                self.right.next()
-            },
+            Ordering::Less => self.left.next(),
+            Ordering::Greater => self.right.next(),
             Ordering::Equal => {
                 self.left.next();
                 self.right.next()
-            },
+            }
         }
     }
 }