Implement `append` for b-trees.

The algorithm implemented here is linear in the size of the two b-trees. It
firsts creates a `MergeIter` from the two b-trees and then builds a new b-tree
by pushing key-value pairs from the `MergeIter` into nodes at the right heights.

Three functions for stealing have been added to the implementation of `Handle` as
well as a getter for the height of a `NodeRef`.

The docs have been updated with performance information about `BTreeMap::append` and
the remark about B has been removed now that it is the same for all instances of `BTreeMap`.

3 files changed, 77 insertions, 0 deletions

diff --git a/src/libcollectionstest/btree/map.rs b/src/libcollectionstest/btree/map.rs
index 619bc189e6c..1858791776f 100644
--- a/src/libcollectionstest/btree/map.rs
+++ b/src/libcollectionstest/btree/map.rs
@@ -446,6 +446,58 @@ fn test_vacant_entry_key() {
     assert_eq!(a[key], value);
 }
 
+macro_rules! create_append_test {
+    ($name:ident, $len:expr) => {
+        #[test]
+        fn $name() {
+            let mut a = BTreeMap::new();
+            for i in 0..8 {
+                a.insert(i, i);
+            }
+
+            let mut b = BTreeMap::new();
+            for i in 5..$len {
+                b.insert(i, 2*i);
+            }
+
+            a.append(&mut b);
+
+            assert_eq!(a.len(), $len);
+            assert_eq!(b.len(), 0);
+
+            for i in 0..$len {
+                if i < 5 {
+                    assert_eq!(a[&i], i);
+                } else {
+                    assert_eq!(a[&i], 2*i);
+                }
+            }
+
+            assert_eq!(a.remove(&($len-1)), Some(2*($len-1)));
+            assert_eq!(a.insert($len-1, 20), None);
+        }
+    };
+}
+
+// These are mostly for testing the algorithm that "fixes" the right edge after insertion.
+// Single node.
+create_append_test!(test_append_9, 9);
+// Two leafs that don't need fixing.
+create_append_test!(test_append_17, 17);
+// Two leafs where the second one ends up underfull and needs stealing at the end.
+create_append_test!(test_append_14, 14);
+// Two leafs where the second one ends up empty because the insertion finished at the root.
+create_append_test!(test_append_12, 12);
+// Three levels; insertion finished at the root.
+create_append_test!(test_append_144, 144);
+// Three levels; insertion finished at leaf while there is an empty node on the second level.
+create_append_test!(test_append_145, 145);
+// Tests for several randomly chosen sizes.
+create_append_test!(test_append_170, 170);
+create_append_test!(test_append_181, 181);
+create_append_test!(test_append_239, 239);
+create_append_test!(test_append_1700, 1700);
+
 mod bench {
     use std::collections::BTreeMap;
     use std::__rand::{Rng, thread_rng};
diff --git a/src/libcollectionstest/btree/set.rs b/src/libcollectionstest/btree/set.rs
index 3928804a8ed..53ccfd5b4e2 100644
--- a/src/libcollectionstest/btree/set.rs
+++ b/src/libcollectionstest/btree/set.rs
@@ -265,3 +265,27 @@ fn test_variance() {
     fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> { v }
     fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> { v }
 }
+
+#[test]
+fn test_append() {
+    let mut a = BTreeSet::new();
+    a.insert(1);
+    a.insert(2);
+    a.insert(3);
+
+    let mut b = BTreeSet::new();
+    b.insert(3);
+    b.insert(4);
+    b.insert(5);
+
+    a.append(&mut b);
+
+    assert_eq!(a.len(), 5);
+    assert_eq!(b.len(), 0);
+
+    assert_eq!(a.contains(&1), true);
+    assert_eq!(a.contains(&2), true);
+    assert_eq!(a.contains(&3), true);
+    assert_eq!(a.contains(&4), true);
+    assert_eq!(a.contains(&5), true);
+}
diff --git a/src/libcollectionstest/lib.rs b/src/libcollectionstest/lib.rs
index 056ac13585c..e4152b99d2c 100644
--- a/src/libcollectionstest/lib.rs
+++ b/src/libcollectionstest/lib.rs
@@ -13,6 +13,7 @@
 #![feature(binary_heap_extras)]
 #![feature(binary_heap_append)]
 #![feature(box_syntax)]
+#![feature(btree_append)]
 #![feature(btree_range)]
 #![feature(collections)]
 #![feature(collections_bound)]