src/liballoc/tests/btree/set.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use std::collections::BTreeSet;
  12
  13 use std::iter::FromIterator;
  14 use super::DeterministicRng;
  15
  16 #[test]
  17 fn test_clone_eq() {
  18     let mut m = BTreeSet::new();
  19
  20     m.insert(1);
  21     m.insert(2);
  22
  23     assert!(m.clone() == m);
  24 }
  25
  26 #[test]
  27 fn test_hash() {
  28     let mut x = BTreeSet::new();
  29     let mut y = BTreeSet::new();
  30
  31     x.insert(1);
  32     x.insert(2);
  33     x.insert(3);
  34
  35     y.insert(3);
  36     y.insert(2);
  37     y.insert(1);
  38
  39     assert!(::hash(&x) == ::hash(&y));
  40 }
  41
  42 fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F)
  43     where F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut dyn FnMut(&i32) -> bool) -> bool
  44 {
  45     let mut set_a = BTreeSet::new();
  46     let mut set_b = BTreeSet::new();
  47
  48     for x in a {
  49         assert!(set_a.insert(*x))
  50     }
  51     for y in b {
  52         assert!(set_b.insert(*y))
  53     }
  54
  55     let mut i = 0;
  56     f(&set_a,
  57       &set_b,
  58       &mut |&x| {
  59           assert_eq!(x, expected[i]);
  60           i += 1;
  61           true
  62       });
  63     assert_eq!(i, expected.len());
  64 }
  65
  66 #[test]
  67 fn test_intersection() {
  68     fn check_intersection(a: &[i32], b: &[i32], expected: &[i32]) {
  69         check(a, b, expected, |x, y, f| x.intersection(y).all(f))
  70     }
  71
  72     check_intersection(&[], &[], &[]);
  73     check_intersection(&[1, 2, 3], &[], &[]);
  74     check_intersection(&[], &[1, 2, 3], &[]);
  75     check_intersection(&[2], &[1, 2, 3], &[2]);
  76     check_intersection(&[1, 2, 3], &[2], &[2]);
  77     check_intersection(&[11, 1, 3, 77, 103, 5, -5],
  78                        &[2, 11, 77, -9, -42, 5, 3],
  79                        &[3, 5, 11, 77]);
  80 }
  81
  82 #[test]
  83 fn test_difference() {
  84     fn check_difference(a: &[i32], b: &[i32], expected: &[i32]) {
  85         check(a, b, expected, |x, y, f| x.difference(y).all(f))
  86     }
  87
  88     check_difference(&[], &[], &[]);
  89     check_difference(&[1, 12], &[], &[1, 12]);
  90     check_difference(&[], &[1, 2, 3, 9], &[]);
  91     check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]);
  92     check_difference(&[-5, 11, 22, 33, 40, 42],
  93                      &[-12, -5, 14, 23, 34, 38, 39, 50],
  94                      &[11, 22, 33, 40, 42]);
  95 }
  96
  97 #[test]
  98 fn test_symmetric_difference() {
  99     fn check_symmetric_difference(a: &[i32], b: &[i32], expected: &[i32]) {
 100         check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
 101     }
 102
 103     check_symmetric_difference(&[], &[], &[]);
 104     check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]);
 105     check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]);
 106     check_symmetric_difference(&[1, 3, 5, 9, 11],
 107                                &[-2, 3, 9, 14, 22],
 108                                &[-2, 1, 5, 11, 14, 22]);
 109 }
 110
 111 #[test]
 112 fn test_union() {
 113     fn check_union(a: &[i32], b: &[i32], expected: &[i32]) {
 114         check(a, b, expected, |x, y, f| x.union(y).all(f))
 115     }
 116
 117     check_union(&[], &[], &[]);
 118     check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
 119     check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
 120     check_union(&[1, 3, 5, 9, 11, 16, 19, 24],
 121                 &[-2, 1, 5, 9, 13, 19],
 122                 &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]);
 123 }
 124
 125 #[test]
 126 fn test_zip() {
 127     let mut x = BTreeSet::new();
 128     x.insert(5);
 129     x.insert(12);
 130     x.insert(11);
 131
 132     let mut y = BTreeSet::new();
 133     y.insert("foo");
 134     y.insert("bar");
 135
 136     let x = x;
 137     let y = y;
 138     let mut z = x.iter().zip(&y);
 139
 140     assert_eq!(z.next().unwrap(), (&5, &("bar")));
 141     assert_eq!(z.next().unwrap(), (&11, &("foo")));
 142     assert!(z.next().is_none());
 143 }
 144
 145 #[test]
 146 fn test_from_iter() {
 147     let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
 148
 149     let set: BTreeSet<_> = xs.iter().cloned().collect();
 150
 151     for x in &xs {
 152         assert!(set.contains(x));
 153     }
 154 }
 155
 156 #[test]
 157 fn test_show() {
 158     let mut set = BTreeSet::new();
 159     let empty = BTreeSet::<i32>::new();
 160
 161     set.insert(1);
 162     set.insert(2);
 163
 164     let set_str = format!("{:?}", set);
 165
 166     assert_eq!(set_str, "{1, 2}");
 167     assert_eq!(format!("{:?}", empty), "{}");
 168 }
 169
 170 #[test]
 171 fn test_extend_ref() {
 172     let mut a = BTreeSet::new();
 173     a.insert(1);
 174
 175     a.extend(&[2, 3, 4]);
 176
 177     assert_eq!(a.len(), 4);
 178     assert!(a.contains(&1));
 179     assert!(a.contains(&2));
 180     assert!(a.contains(&3));
 181     assert!(a.contains(&4));
 182
 183     let mut b = BTreeSet::new();
 184     b.insert(5);
 185     b.insert(6);
 186
 187     a.extend(&b);
 188
 189     assert_eq!(a.len(), 6);
 190     assert!(a.contains(&1));
 191     assert!(a.contains(&2));
 192     assert!(a.contains(&3));
 193     assert!(a.contains(&4));
 194     assert!(a.contains(&5));
 195     assert!(a.contains(&6));
 196 }
 197
 198 #[test]
 199 fn test_recovery() {
 200     use std::cmp::Ordering;
 201
 202     #[derive(Debug)]
 203     struct Foo(&'static str, i32);
 204
 205     impl PartialEq for Foo {
 206         fn eq(&self, other: &Self) -> bool {
 207             self.0 == other.0
 208         }
 209     }
 210
 211     impl Eq for Foo {}
 212
 213     impl PartialOrd for Foo {
 214         fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 215             self.0.partial_cmp(&other.0)
 216         }
 217     }
 218
 219     impl Ord for Foo {
 220         fn cmp(&self, other: &Self) -> Ordering {
 221             self.0.cmp(&other.0)
 222         }
 223     }
 224
 225     let mut s = BTreeSet::new();
 226     assert_eq!(s.replace(Foo("a", 1)), None);
 227     assert_eq!(s.len(), 1);
 228     assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
 229     assert_eq!(s.len(), 1);
 230
 231     {
 232         let mut it = s.iter();
 233         assert_eq!(it.next(), Some(&Foo("a", 2)));
 234         assert_eq!(it.next(), None);
 235     }
 236
 237     assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2)));
 238     assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2)));
 239     assert_eq!(s.len(), 0);
 240
 241     assert_eq!(s.get(&Foo("a", 1)), None);
 242     assert_eq!(s.take(&Foo("a", 1)), None);
 243
 244     assert_eq!(s.iter().next(), None);
 245 }
 246
 247 #[test]
 248 #[allow(dead_code)]
 249 fn test_variance() {
 250     use std::collections::btree_set::{IntoIter, Iter, Range};
 251
 252     fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> {
 253         v
 254     }
 255     fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
 256         v
 257     }
 258     fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
 259         v
 260     }
 261     fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> {
 262         v
 263     }
 264 }
 265
 266 #[test]
 267 fn test_append() {
 268     let mut a = BTreeSet::new();
 269     a.insert(1);
 270     a.insert(2);
 271     a.insert(3);
 272
 273     let mut b = BTreeSet::new();
 274     b.insert(3);
 275     b.insert(4);
 276     b.insert(5);
 277
 278     a.append(&mut b);
 279
 280     assert_eq!(a.len(), 5);
 281     assert_eq!(b.len(), 0);
 282
 283     assert_eq!(a.contains(&1), true);
 284     assert_eq!(a.contains(&2), true);
 285     assert_eq!(a.contains(&3), true);
 286     assert_eq!(a.contains(&4), true);
 287     assert_eq!(a.contains(&5), true);
 288 }
 289
 290 fn rand_data(len: usize) -> Vec<u32> {
 291     let mut rng = DeterministicRng::new();
 292     Vec::from_iter((0..len).map(|_| rng.next()))
 293 }
 294
 295 #[test]
 296 fn test_split_off_empty_right() {
 297     let mut data = rand_data(173);
 298
 299     let mut set = BTreeSet::from_iter(data.clone());
 300     let right = set.split_off(&(data.iter().max().unwrap() + 1));
 301
 302     data.sort();
 303     assert!(set.into_iter().eq(data));
 304     assert!(right.into_iter().eq(None));
 305 }
 306
 307 #[test]
 308 fn test_split_off_empty_left() {
 309     let mut data = rand_data(314);
 310
 311     let mut set = BTreeSet::from_iter(data.clone());
 312     let right = set.split_off(data.iter().min().unwrap());
 313
 314     data.sort();
 315     assert!(set.into_iter().eq(None));
 316     assert!(right.into_iter().eq(data));
 317 }
 318
 319 #[test]
 320 fn test_split_off_large_random_sorted() {
 321     let mut data = rand_data(1529);
 322     // special case with maximum height.
 323     data.sort();
 324
 325     let mut set = BTreeSet::from_iter(data.clone());
 326     let key = data[data.len() / 2];
 327     let right = set.split_off(&key);
 328
 329     assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key)));
 330     assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key)));
 331 }