Merge crate `collections` into `alloc`

3 files changed, 1060 insertions, 0 deletions

diff --git a/src/liballoc/tests/btree/map.rs b/src/liballoc/tests/btree/map.rs
new file mode 100644
index 00000000000..2c899d96940
--- /dev/null
+++ b/src/liballoc/tests/btree/map.rs
@@ -0,0 +1,687 @@
+// Copyright 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.
+
+use std::collections::BTreeMap;
+use std::collections::Bound::{self, Excluded, Included, Unbounded};
+use std::collections::btree_map::Entry::{Occupied, Vacant};
+use std::rc::Rc;
+
+use std::iter::FromIterator;
+use super::DeterministicRng;
+
+#[test]
+fn test_basic_large() {
+    let mut map = BTreeMap::new();
+    let size = 10000;
+    assert_eq!(map.len(), 0);
+
+    for i in 0..size {
+        assert_eq!(map.insert(i, 10 * i), None);
+        assert_eq!(map.len(), i + 1);
+    }
+
+    for i in 0..size {
+        assert_eq!(map.get(&i).unwrap(), &(i * 10));
+    }
+
+    for i in size..size * 2 {
+        assert_eq!(map.get(&i), None);
+    }
+
+    for i in 0..size {
+        assert_eq!(map.insert(i, 100 * i), Some(10 * i));
+        assert_eq!(map.len(), size);
+    }
+
+    for i in 0..size {
+        assert_eq!(map.get(&i).unwrap(), &(i * 100));
+    }
+
+    for i in 0..size / 2 {
+        assert_eq!(map.remove(&(i * 2)), Some(i * 200));
+        assert_eq!(map.len(), size - i - 1);
+    }
+
+    for i in 0..size / 2 {
+        assert_eq!(map.get(&(2 * i)), None);
+        assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
+    }
+
+    for i in 0..size / 2 {
+        assert_eq!(map.remove(&(2 * i)), None);
+        assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
+        assert_eq!(map.len(), size / 2 - i - 1);
+    }
+}
+
+#[test]
+fn test_basic_small() {
+    let mut map = BTreeMap::new();
+    assert_eq!(map.remove(&1), None);
+    assert_eq!(map.get(&1), None);
+    assert_eq!(map.insert(1, 1), None);
+    assert_eq!(map.get(&1), Some(&1));
+    assert_eq!(map.insert(1, 2), Some(1));
+    assert_eq!(map.get(&1), Some(&2));
+    assert_eq!(map.insert(2, 4), None);
+    assert_eq!(map.get(&2), Some(&4));
+    assert_eq!(map.remove(&1), Some(2));
+    assert_eq!(map.remove(&2), Some(4));
+    assert_eq!(map.remove(&1), None);
+}
+
+#[test]
+fn test_iter() {
+    let size = 10000;
+
+    // Forwards
+    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    fn test<T>(size: usize, mut iter: T)
+        where T: Iterator<Item = (usize, usize)>
+    {
+        for i in 0..size {
+            assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
+            assert_eq!(iter.next().unwrap(), (i, i));
+        }
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+    }
+    test(size, map.iter().map(|(&k, &v)| (k, v)));
+    test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
+    test(size, map.into_iter());
+}
+
+#[test]
+fn test_iter_rev() {
+    let size = 10000;
+
+    // Forwards
+    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    fn test<T>(size: usize, mut iter: T)
+        where T: Iterator<Item = (usize, usize)>
+    {
+        for i in 0..size {
+            assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
+            assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
+        }
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+    }
+    test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
+    test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
+    test(size, map.into_iter().rev());
+}
+
+#[test]
+fn test_values_mut() {
+    let mut a = BTreeMap::new();
+    a.insert(1, String::from("hello"));
+    a.insert(2, String::from("goodbye"));
+
+    for value in a.values_mut() {
+        value.push_str("!");
+    }
+
+    let values: Vec<String> = a.values().cloned().collect();
+    assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
+}
+
+#[test]
+fn test_iter_mixed() {
+    let size = 10000;
+
+    // Forwards
+    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    fn test<T>(size: usize, mut iter: T)
+        where T: Iterator<Item = (usize, usize)> + DoubleEndedIterator
+    {
+        for i in 0..size / 4 {
+            assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
+            assert_eq!(iter.next().unwrap(), (i, i));
+            assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
+        }
+        for i in size / 4..size * 3 / 4 {
+            assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
+            assert_eq!(iter.next().unwrap(), (i, i));
+        }
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+    }
+    test(size, map.iter().map(|(&k, &v)| (k, v)));
+    test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
+    test(size, map.into_iter());
+}
+
+#[test]
+fn test_range_small() {
+    let size = 5;
+
+    // Forwards
+    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    let mut j = 0;
+    for ((&k, &v), i) in map.range(2..).zip(2..size) {
+        assert_eq!(k, i);
+        assert_eq!(v, i);
+        j += 1;
+    }
+    assert_eq!(j, size - 2);
+}
+
+#[test]
+fn test_range_inclusive() {
+    let size = 500;
+
+    let map: BTreeMap<_, _> = (0...size).map(|i| (i, i)).collect();
+
+    fn check<'a, L, R>(lhs: L, rhs: R)
+        where L: IntoIterator<Item=(&'a i32, &'a i32)>,
+              R: IntoIterator<Item=(&'a i32, &'a i32)>,
+    {
+        let lhs: Vec<_> = lhs.into_iter().collect();
+        let rhs: Vec<_> = rhs.into_iter().collect();
+        assert_eq!(lhs, rhs);
+    }
+
+    check(map.range(size + 1...size + 1), vec![]);
+    check(map.range(size...size), vec![(&size, &size)]);
+    check(map.range(size...size + 1), vec![(&size, &size)]);
+    check(map.range(0...0), vec![(&0, &0)]);
+    check(map.range(0...size - 1), map.range(..size));
+    check(map.range(-1...-1), vec![]);
+    check(map.range(-1...size), map.range(..));
+    check(map.range(...size), map.range(..));
+    check(map.range(...200), map.range(..201));
+    check(map.range(5...8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]);
+    check(map.range(-1...0), vec![(&0, &0)]);
+    check(map.range(-1...2), vec![(&0, &0), (&1, &1), (&2, &2)]);
+}
+
+#[test]
+fn test_range_inclusive_max_value() {
+    let max = ::std::usize::MAX;
+    let map: BTreeMap<_, _> = vec![(max, 0)].into_iter().collect();
+
+    assert_eq!(map.range(max...max).collect::<Vec<_>>(), &[(&max, &0)]);
+}
+
+#[test]
+fn test_range_equal_empty_cases() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    assert_eq!(map.range((Included(2), Excluded(2))).next(), None);
+    assert_eq!(map.range((Excluded(2), Included(2))).next(), None);
+}
+
+#[test]
+#[should_panic]
+fn test_range_equal_excluded() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    map.range((Excluded(2), Excluded(2)));
+}
+
+#[test]
+#[should_panic]
+fn test_range_backwards_1() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    map.range((Included(3), Included(2)));
+}
+
+#[test]
+#[should_panic]
+fn test_range_backwards_2() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    map.range((Included(3), Excluded(2)));
+}
+
+#[test]
+#[should_panic]
+fn test_range_backwards_3() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    map.range((Excluded(3), Included(2)));
+}
+
+#[test]
+#[should_panic]
+fn test_range_backwards_4() {
+    let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
+    map.range((Excluded(3), Excluded(2)));
+}
+
+#[test]
+fn test_range_1000() {
+    let size = 1000;
+    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
+        let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v));
+        let mut pairs = (0..size).map(|i| (i, i));
+
+        for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
+            assert_eq!(kv, pair);
+        }
+        assert_eq!(kvs.next(), None);
+        assert_eq!(pairs.next(), None);
+    }
+    test(&map, size, Included(&0), Excluded(&size));
+    test(&map, size, Unbounded, Excluded(&size));
+    test(&map, size, Included(&0), Included(&(size - 1)));
+    test(&map, size, Unbounded, Included(&(size - 1)));
+    test(&map, size, Included(&0), Unbounded);
+    test(&map, size, Unbounded, Unbounded);
+}
+
+#[test]
+fn test_range_borrowed_key() {
+    let mut map = BTreeMap::new();
+    map.insert("aardvark".to_string(), 1);
+    map.insert("baboon".to_string(), 2);
+    map.insert("coyote".to_string(), 3);
+    map.insert("dingo".to_string(), 4);
+    // NOTE: would like to use simply "b".."d" here...
+    let mut iter = map.range::<str, _>((Included("b"),Excluded("d")));
+    assert_eq!(iter.next(), Some((&"baboon".to_string(), &2)));
+    assert_eq!(iter.next(), Some((&"coyote".to_string(), &3)));
+    assert_eq!(iter.next(), None);
+}
+
+#[test]
+fn test_range() {
+    let size = 200;
+    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    for i in 0..size {
+        for j in i..size {
+            let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
+            let mut pairs = (i..j + 1).map(|i| (i, i));
+
+            for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
+                assert_eq!(kv, pair);
+            }
+            assert_eq!(kvs.next(), None);
+            assert_eq!(pairs.next(), None);
+        }
+    }
+}
+
+#[test]
+fn test_range_mut() {
+    let size = 200;
+    let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
+
+    for i in 0..size {
+        for j in i..size {
+            let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
+            let mut pairs = (i..j + 1).map(|i| (i, i));
+
+            for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
+                assert_eq!(kv, pair);
+            }
+            assert_eq!(kvs.next(), None);
+            assert_eq!(pairs.next(), None);
+        }
+    }
+}
+
+#[test]
+fn test_borrow() {
+    // make sure these compile -- using the Borrow trait
+    {
+        let mut map = BTreeMap::new();
+        map.insert("0".to_string(), 1);
+        assert_eq!(map["0"], 1);
+    }
+
+    {
+        let mut map = BTreeMap::new();
+        map.insert(Box::new(0), 1);
+        assert_eq!(map[&0], 1);
+    }
+
+    {
+        let mut map = BTreeMap::new();
+        map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
+        assert_eq!(map[&[0, 1][..]], 1);
+    }
+
+    {
+        let mut map = BTreeMap::new();
+        map.insert(Rc::new(0), 1);
+        assert_eq!(map[&0], 1);
+    }
+}
+
+#[test]
+fn test_entry() {
+    let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
+
+    let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
+
+    // Existing key (insert)
+    match map.entry(1) {
+        Vacant(_) => unreachable!(),
+        Occupied(mut view) => {
+            assert_eq!(view.get(), &10);
+            assert_eq!(view.insert(100), 10);
+        }
+    }
+    assert_eq!(map.get(&1).unwrap(), &100);
+    assert_eq!(map.len(), 6);
+
+
+    // Existing key (update)
+    match map.entry(2) {
+        Vacant(_) => unreachable!(),
+        Occupied(mut view) => {
+            let v = view.get_mut();
+            *v *= 10;
+        }
+    }
+    assert_eq!(map.get(&2).unwrap(), &200);
+    assert_eq!(map.len(), 6);
+
+    // Existing key (take)
+    match map.entry(3) {
+        Vacant(_) => unreachable!(),
+        Occupied(view) => {
+            assert_eq!(view.remove(), 30);
+        }
+    }
+    assert_eq!(map.get(&3), None);
+    assert_eq!(map.len(), 5);
+
+
+    // Inexistent key (insert)
+    match map.entry(10) {
+        Occupied(_) => unreachable!(),
+        Vacant(view) => {
+            assert_eq!(*view.insert(1000), 1000);
+        }
+    }
+    assert_eq!(map.get(&10).unwrap(), &1000);
+    assert_eq!(map.len(), 6);
+}
+
+#[test]
+fn test_extend_ref() {
+    let mut a = BTreeMap::new();
+    a.insert(1, "one");
+    let mut b = BTreeMap::new();
+    b.insert(2, "two");
+    b.insert(3, "three");
+
+    a.extend(&b);
+
+    assert_eq!(a.len(), 3);
+    assert_eq!(a[&1], "one");
+    assert_eq!(a[&2], "two");
+    assert_eq!(a[&3], "three");
+}
+
+#[test]
+fn test_zst() {
+    let mut m = BTreeMap::new();
+    assert_eq!(m.len(), 0);
+
+    assert_eq!(m.insert((), ()), None);
+    assert_eq!(m.len(), 1);
+
+    assert_eq!(m.insert((), ()), Some(()));
+    assert_eq!(m.len(), 1);
+    assert_eq!(m.iter().count(), 1);
+
+    m.clear();
+    assert_eq!(m.len(), 0);
+
+    for _ in 0..100 {
+        m.insert((), ());
+    }
+
+    assert_eq!(m.len(), 1);
+    assert_eq!(m.iter().count(), 1);
+}
+
+// This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
+// do not cause segfaults when used with zero-sized values. All other map behavior is
+// undefined.
+#[test]
+fn test_bad_zst() {
+    use std::cmp::Ordering;
+
+    struct Bad;
+
+    impl PartialEq for Bad {
+        fn eq(&self, _: &Self) -> bool {
+            false
+        }
+    }
+
+    impl Eq for Bad {}
+
+    impl PartialOrd for Bad {
+        fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
+            Some(Ordering::Less)
+        }
+    }
+
+    impl Ord for Bad {
+        fn cmp(&self, _: &Self) -> Ordering {
+            Ordering::Less
+        }
+    }
+
+    let mut m = BTreeMap::new();
+
+    for _ in 0..100 {
+        m.insert(Bad, Bad);
+    }
+}
+
+#[test]
+fn test_clone() {
+    let mut map = BTreeMap::new();
+    let size = 100;
+    assert_eq!(map.len(), 0);
+
+    for i in 0..size {
+        assert_eq!(map.insert(i, 10 * i), None);
+        assert_eq!(map.len(), i + 1);
+        assert_eq!(map, map.clone());
+    }
+
+    for i in 0..size {
+        assert_eq!(map.insert(i, 100 * i), Some(10 * i));
+        assert_eq!(map.len(), size);
+        assert_eq!(map, map.clone());
+    }
+
+    for i in 0..size / 2 {
+        assert_eq!(map.remove(&(i * 2)), Some(i * 200));
+        assert_eq!(map.len(), size - i - 1);
+        assert_eq!(map, map.clone());
+    }
+
+    for i in 0..size / 2 {
+        assert_eq!(map.remove(&(2 * i)), None);
+        assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
+        assert_eq!(map.len(), size / 2 - i - 1);
+        assert_eq!(map, map.clone());
+    }
+}
+
+#[test]
+#[allow(dead_code)]
+fn test_variance() {
+    use std::collections::btree_map::{Iter, IntoIter, Range, Keys, Values};
+
+    fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> {
+        v
+    }
+    fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> {
+        v
+    }
+    fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> {
+        v
+    }
+    fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> {
+        v
+    }
+    fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> {
+        v
+    }
+    fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> {
+        v
+    }
+    fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> {
+        v
+    }
+    fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> {
+        v
+    }
+    fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> {
+        v
+    }
+    fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> {
+        v
+    }
+}
+
+#[test]
+fn test_occupied_entry_key() {
+    let mut a = BTreeMap::new();
+    let key = "hello there";
+    let value = "value goes here";
+    assert!(a.is_empty());
+    a.insert(key.clone(), value.clone());
+    assert_eq!(a.len(), 1);
+    assert_eq!(a[key], value);
+
+    match a.entry(key.clone()) {
+        Vacant(_) => panic!(),
+        Occupied(e) => assert_eq!(key, *e.key()),
+    }
+    assert_eq!(a.len(), 1);
+    assert_eq!(a[key], value);
+}
+
+#[test]
+fn test_vacant_entry_key() {
+    let mut a = BTreeMap::new();
+    let key = "hello there";
+    let value = "value goes here";
+
+    assert!(a.is_empty());
+    match a.entry(key.clone()) {
+        Occupied(_) => panic!(),
+        Vacant(e) => {
+            assert_eq!(key, *e.key());
+            e.insert(value.clone());
+        }
+    }
+    assert_eq!(a.len(), 1);
+    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);
+
+fn rand_data(len: usize) -> Vec<(u32, u32)> {
+    let mut rng = DeterministicRng::new();
+    Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
+}
+
+#[test]
+fn test_split_off_empty_right() {
+    let mut data = rand_data(173);
+
+    let mut map = BTreeMap::from_iter(data.clone());
+    let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
+
+    data.sort();
+    assert!(map.into_iter().eq(data));
+    assert!(right.into_iter().eq(None));
+}
+
+#[test]
+fn test_split_off_empty_left() {
+    let mut data = rand_data(314);
+
+    let mut map = BTreeMap::from_iter(data.clone());
+    let right = map.split_off(&data.iter().min().unwrap().0);
+
+    data.sort();
+    assert!(map.into_iter().eq(None));
+    assert!(right.into_iter().eq(data));
+}
+
+#[test]
+fn test_split_off_large_random_sorted() {
+    let mut data = rand_data(1529);
+    // special case with maximum height.
+    data.sort();
+
+    let mut map = BTreeMap::from_iter(data.clone());
+    let key = data[data.len() / 2].0;
+    let right = map.split_off(&key);
+
+    assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
+    assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
+}
diff --git a/src/liballoc/tests/btree/mod.rs b/src/liballoc/tests/btree/mod.rs
new file mode 100644
index 00000000000..ae8b18d0c9f
--- /dev/null
+++ b/src/liballoc/tests/btree/mod.rs
@@ -0,0 +1,42 @@
+// Copyright 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.
+
+mod map;
+mod set;
+
+/// XorShiftRng
+struct DeterministicRng {
+    x: u32,
+    y: u32,
+    z: u32,
+    w: u32,
+}
+
+impl DeterministicRng {
+    fn new() -> Self {
+        DeterministicRng {
+            x: 0x193a6754,
+            y: 0xa8a7d469,
+            z: 0x97830e05,
+            w: 0x113ba7bb,
+        }
+    }
+
+    fn next(&mut self) -> u32 {
+        let x = self.x;
+        let t = x ^ (x << 11);
+        self.x = self.y;
+        self.y = self.z;
+        self.z = self.w;
+        let w_ = self.w;
+        self.w = w_ ^ (w_ >> 19) ^ (t ^ (t >> 8));
+        self.w
+    }
+}
diff --git a/src/liballoc/tests/btree/set.rs b/src/liballoc/tests/btree/set.rs
new file mode 100644
index 00000000000..6171b8ba624
--- /dev/null
+++ b/src/liballoc/tests/btree/set.rs
@@ -0,0 +1,331 @@
+// Copyright 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.
+
+use std::collections::BTreeSet;
+
+use std::iter::FromIterator;
+use super::DeterministicRng;
+
+#[test]
+fn test_clone_eq() {
+    let mut m = BTreeSet::new();
+
+    m.insert(1);
+    m.insert(2);
+
+    assert!(m.clone() == m);
+}
+
+#[test]
+fn test_hash() {
+    let mut x = BTreeSet::new();
+    let mut y = BTreeSet::new();
+
+    x.insert(1);
+    x.insert(2);
+    x.insert(3);
+
+    y.insert(3);
+    y.insert(2);
+    y.insert(1);
+
+    assert!(::hash(&x) == ::hash(&y));
+}
+
+fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F)
+    where F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut FnMut(&i32) -> bool) -> bool
+{
+    let mut set_a = BTreeSet::new();
+    let mut set_b = BTreeSet::new();
+
+    for x in a {
+        assert!(set_a.insert(*x))
+    }
+    for y in b {
+        assert!(set_b.insert(*y))
+    }
+
+    let mut i = 0;
+    f(&set_a,
+      &set_b,
+      &mut |&x| {
+          assert_eq!(x, expected[i]);
+          i += 1;
+          true
+      });
+    assert_eq!(i, expected.len());
+}
+
+#[test]
+fn test_intersection() {
+    fn check_intersection(a: &[i32], b: &[i32], expected: &[i32]) {
+        check(a, b, expected, |x, y, f| x.intersection(y).all(f))
+    }
+
+    check_intersection(&[], &[], &[]);
+    check_intersection(&[1, 2, 3], &[], &[]);
+    check_intersection(&[], &[1, 2, 3], &[]);
+    check_intersection(&[2], &[1, 2, 3], &[2]);
+    check_intersection(&[1, 2, 3], &[2], &[2]);
+    check_intersection(&[11, 1, 3, 77, 103, 5, -5],
+                       &[2, 11, 77, -9, -42, 5, 3],
+                       &[3, 5, 11, 77]);
+}
+
+#[test]
+fn test_difference() {
+    fn check_difference(a: &[i32], b: &[i32], expected: &[i32]) {
+        check(a, b, expected, |x, y, f| x.difference(y).all(f))
+    }
+
+    check_difference(&[], &[], &[]);
+    check_difference(&[1, 12], &[], &[1, 12]);
+    check_difference(&[], &[1, 2, 3, 9], &[]);
+    check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]);
+    check_difference(&[-5, 11, 22, 33, 40, 42],
+                     &[-12, -5, 14, 23, 34, 38, 39, 50],
+                     &[11, 22, 33, 40, 42]);
+}
+
+#[test]
+fn test_symmetric_difference() {
+    fn check_symmetric_difference(a: &[i32], b: &[i32], expected: &[i32]) {
+        check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
+    }
+
+    check_symmetric_difference(&[], &[], &[]);
+    check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]);
+    check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]);
+    check_symmetric_difference(&[1, 3, 5, 9, 11],
+                               &[-2, 3, 9, 14, 22],
+                               &[-2, 1, 5, 11, 14, 22]);
+}
+
+#[test]
+fn test_union() {
+    fn check_union(a: &[i32], b: &[i32], expected: &[i32]) {
+        check(a, b, expected, |x, y, f| x.union(y).all(f))
+    }
+
+    check_union(&[], &[], &[]);
+    check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
+    check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
+    check_union(&[1, 3, 5, 9, 11, 16, 19, 24],
+                &[-2, 1, 5, 9, 13, 19],
+                &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]);
+}
+
+#[test]
+fn test_zip() {
+    let mut x = BTreeSet::new();
+    x.insert(5);
+    x.insert(12);
+    x.insert(11);
+
+    let mut y = BTreeSet::new();
+    y.insert("foo");
+    y.insert("bar");
+
+    let x = x;
+    let y = y;
+    let mut z = x.iter().zip(&y);
+
+    assert_eq!(z.next().unwrap(), (&5, &("bar")));
+    assert_eq!(z.next().unwrap(), (&11, &("foo")));
+    assert!(z.next().is_none());
+}
+
+#[test]
+fn test_from_iter() {
+    let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
+
+    let set: BTreeSet<_> = xs.iter().cloned().collect();
+
+    for x in &xs {
+        assert!(set.contains(x));
+    }
+}
+
+#[test]
+fn test_show() {
+    let mut set = BTreeSet::new();
+    let empty = BTreeSet::<i32>::new();
+
+    set.insert(1);
+    set.insert(2);
+
+    let set_str = format!("{:?}", set);
+
+    assert_eq!(set_str, "{1, 2}");
+    assert_eq!(format!("{:?}", empty), "{}");
+}
+
+#[test]
+fn test_extend_ref() {
+    let mut a = BTreeSet::new();
+    a.insert(1);
+
+    a.extend(&[2, 3, 4]);
+
+    assert_eq!(a.len(), 4);
+    assert!(a.contains(&1));
+    assert!(a.contains(&2));
+    assert!(a.contains(&3));
+    assert!(a.contains(&4));
+
+    let mut b = BTreeSet::new();
+    b.insert(5);
+    b.insert(6);
+
+    a.extend(&b);
+
+    assert_eq!(a.len(), 6);
+    assert!(a.contains(&1));
+    assert!(a.contains(&2));
+    assert!(a.contains(&3));
+    assert!(a.contains(&4));
+    assert!(a.contains(&5));
+    assert!(a.contains(&6));
+}
+
+#[test]
+fn test_recovery() {
+    use std::cmp::Ordering;
+
+    #[derive(Debug)]
+    struct Foo(&'static str, i32);
+
+    impl PartialEq for Foo {
+        fn eq(&self, other: &Self) -> bool {
+            self.0 == other.0
+        }
+    }
+
+    impl Eq for Foo {}
+
+    impl PartialOrd for Foo {
+        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+            self.0.partial_cmp(&other.0)
+        }
+    }
+
+    impl Ord for Foo {
+        fn cmp(&self, other: &Self) -> Ordering {
+            self.0.cmp(&other.0)
+        }
+    }
+
+    let mut s = BTreeSet::new();
+    assert_eq!(s.replace(Foo("a", 1)), None);
+    assert_eq!(s.len(), 1);
+    assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
+    assert_eq!(s.len(), 1);
+
+    {
+        let mut it = s.iter();
+        assert_eq!(it.next(), Some(&Foo("a", 2)));
+        assert_eq!(it.next(), None);
+    }
+
+    assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2)));
+    assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2)));
+    assert_eq!(s.len(), 0);
+
+    assert_eq!(s.get(&Foo("a", 1)), None);
+    assert_eq!(s.take(&Foo("a", 1)), None);
+
+    assert_eq!(s.iter().next(), None);
+}
+
+#[test]
+#[allow(dead_code)]
+fn test_variance() {
+    use std::collections::btree_set::{IntoIter, Iter, Range};
+
+    fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> {
+        v
+    }
+    fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
+        v
+    }
+    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);
+}
+
+fn rand_data(len: usize) -> Vec<u32> {
+    let mut rng = DeterministicRng::new();
+    Vec::from_iter((0..len).map(|_| rng.next()))
+}
+
+#[test]
+fn test_split_off_empty_right() {
+    let mut data = rand_data(173);
+
+    let mut set = BTreeSet::from_iter(data.clone());
+    let right = set.split_off(&(data.iter().max().unwrap() + 1));
+
+    data.sort();
+    assert!(set.into_iter().eq(data));
+    assert!(right.into_iter().eq(None));
+}
+
+#[test]
+fn test_split_off_empty_left() {
+    let mut data = rand_data(314);
+
+    let mut set = BTreeSet::from_iter(data.clone());
+    let right = set.split_off(data.iter().min().unwrap());
+
+    data.sort();
+    assert!(set.into_iter().eq(None));
+    assert!(right.into_iter().eq(data));
+}
+
+#[test]
+fn test_split_off_large_random_sorted() {
+    let mut data = rand_data(1529);
+    // special case with maximum height.
+    data.sort();
+
+    let mut set = BTreeSet::from_iter(data.clone());
+    let key = data[data.len() / 2];
+    let right = set.split_off(&key);
+
+    assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key)));
+    assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key)));
+}