src/liballoc/tests/btree/map.rs

   1 use std::collections::BTreeMap;
   2 use std::collections::btree_map::Entry::{Occupied, Vacant};
   3 use std::ops::Bound::{self, Excluded, Included, Unbounded};
   4 use std::rc::Rc;
   5 use std::iter::FromIterator;
   6
   7 use super::DeterministicRng;
   8
   9 #[test]
  10 fn test_basic_large() {
  11     let mut map = BTreeMap::new();
  12     #[cfg(not(miri))] // Miri is too slow
  13     let size = 10000;
  14     #[cfg(miri)]
  15     let size = 200;
  16     assert_eq!(map.len(), 0);
  17
  18     for i in 0..size {
  19         assert_eq!(map.insert(i, 10 * i), None);
  20         assert_eq!(map.len(), i + 1);
  21     }
  22
  23     for i in 0..size {
  24         assert_eq!(map.get(&i).unwrap(), &(i * 10));
  25     }
  26
  27     for i in size..size * 2 {
  28         assert_eq!(map.get(&i), None);
  29     }
  30
  31     for i in 0..size {
  32         assert_eq!(map.insert(i, 100 * i), Some(10 * i));
  33         assert_eq!(map.len(), size);
  34     }
  35
  36     for i in 0..size {
  37         assert_eq!(map.get(&i).unwrap(), &(i * 100));
  38     }
  39
  40     for i in 0..size / 2 {
  41         assert_eq!(map.remove(&(i * 2)), Some(i * 200));
  42         assert_eq!(map.len(), size - i - 1);
  43     }
  44
  45     for i in 0..size / 2 {
  46         assert_eq!(map.get(&(2 * i)), None);
  47         assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
  48     }
  49
  50     for i in 0..size / 2 {
  51         assert_eq!(map.remove(&(2 * i)), None);
  52         assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
  53         assert_eq!(map.len(), size / 2 - i - 1);
  54     }
  55 }
  56
  57 #[test]
  58 fn test_basic_small() {
  59     let mut map = BTreeMap::new();
  60     assert_eq!(map.remove(&1), None);
  61     assert_eq!(map.get(&1), None);
  62     assert_eq!(map.insert(1, 1), None);
  63     assert_eq!(map.get(&1), Some(&1));
  64     assert_eq!(map.insert(1, 2), Some(1));
  65     assert_eq!(map.get(&1), Some(&2));
  66     assert_eq!(map.insert(2, 4), None);
  67     assert_eq!(map.get(&2), Some(&4));
  68     assert_eq!(map.remove(&1), Some(2));
  69     assert_eq!(map.remove(&2), Some(4));
  70     assert_eq!(map.remove(&1), None);
  71 }
  72
  73 #[test]
  74 fn test_iter() {
  75     #[cfg(not(miri))] // Miri is too slow
  76     let size = 10000;
  77     #[cfg(miri)]
  78     let size = 200;
  79
  80     // Forwards
  81     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
  82
  83     fn test<T>(size: usize, mut iter: T)
  84         where T: Iterator<Item = (usize, usize)>
  85     {
  86         for i in 0..size {
  87             assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
  88             assert_eq!(iter.next().unwrap(), (i, i));
  89         }
  90         assert_eq!(iter.size_hint(), (0, Some(0)));
  91         assert_eq!(iter.next(), None);
  92     }
  93     test(size, map.iter().map(|(&k, &v)| (k, v)));
  94     test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
  95     test(size, map.into_iter());
  96 }
  97
  98 #[test]
  99 fn test_iter_rev() {
 100     #[cfg(not(miri))] // Miri is too slow
 101     let size = 10000;
 102     #[cfg(miri)]
 103     let size = 200;
 104
 105     // Forwards
 106     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 107
 108     fn test<T>(size: usize, mut iter: T)
 109         where T: Iterator<Item = (usize, usize)>
 110     {
 111         for i in 0..size {
 112             assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
 113             assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
 114         }
 115         assert_eq!(iter.size_hint(), (0, Some(0)));
 116         assert_eq!(iter.next(), None);
 117     }
 118     test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
 119     test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
 120     test(size, map.into_iter().rev());
 121 }
 122
 123 #[test]
 124 fn test_values_mut() {
 125     let mut a = BTreeMap::new();
 126     a.insert(1, String::from("hello"));
 127     a.insert(2, String::from("goodbye"));
 128
 129     for value in a.values_mut() {
 130         value.push_str("!");
 131     }
 132
 133     let values: Vec<String> = a.values().cloned().collect();
 134     assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
 135 }
 136
 137 #[test]
 138 fn test_iter_mixed() {
 139     #[cfg(not(miri))] // Miri is too slow
 140     let size = 10000;
 141     #[cfg(miri)]
 142     let size = 200;
 143
 144     // Forwards
 145     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 146
 147     fn test<T>(size: usize, mut iter: T)
 148         where T: Iterator<Item = (usize, usize)> + DoubleEndedIterator
 149     {
 150         for i in 0..size / 4 {
 151             assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
 152             assert_eq!(iter.next().unwrap(), (i, i));
 153             assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
 154         }
 155         for i in size / 4..size * 3 / 4 {
 156             assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
 157             assert_eq!(iter.next().unwrap(), (i, i));
 158         }
 159         assert_eq!(iter.size_hint(), (0, Some(0)));
 160         assert_eq!(iter.next(), None);
 161     }
 162     test(size, map.iter().map(|(&k, &v)| (k, v)));
 163     test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
 164     test(size, map.into_iter());
 165 }
 166
 167 #[test]
 168 fn test_range_small() {
 169     let size = 5;
 170
 171     // Forwards
 172     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 173
 174     let mut j = 0;
 175     for ((&k, &v), i) in map.range(2..).zip(2..size) {
 176         assert_eq!(k, i);
 177         assert_eq!(v, i);
 178         j += 1;
 179     }
 180     assert_eq!(j, size - 2);
 181 }
 182
 183 #[test]
 184 fn test_range_inclusive() {
 185     let size = 500;
 186
 187     let map: BTreeMap<_, _> = (0..=size).map(|i| (i, i)).collect();
 188
 189     fn check<'a, L, R>(lhs: L, rhs: R)
 190         where L: IntoIterator<Item=(&'a i32, &'a i32)>,
 191               R: IntoIterator<Item=(&'a i32, &'a i32)>,
 192     {
 193         let lhs: Vec<_> = lhs.into_iter().collect();
 194         let rhs: Vec<_> = rhs.into_iter().collect();
 195         assert_eq!(lhs, rhs);
 196     }
 197
 198     check(map.range(size + 1..=size + 1), vec![]);
 199     check(map.range(size..=size), vec![(&size, &size)]);
 200     check(map.range(size..=size + 1), vec![(&size, &size)]);
 201     check(map.range(0..=0), vec![(&0, &0)]);
 202     check(map.range(0..=size - 1), map.range(..size));
 203     check(map.range(-1..=-1), vec![]);
 204     check(map.range(-1..=size), map.range(..));
 205     check(map.range(..=size), map.range(..));
 206     check(map.range(..=200), map.range(..201));
 207     check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]);
 208     check(map.range(-1..=0), vec![(&0, &0)]);
 209     check(map.range(-1..=2), vec![(&0, &0), (&1, &1), (&2, &2)]);
 210 }
 211
 212 #[test]
 213 fn test_range_inclusive_max_value() {
 214     let max = std::usize::MAX;
 215     let map: BTreeMap<_, _> = vec![(max, 0)].into_iter().collect();
 216
 217     assert_eq!(map.range(max..=max).collect::<Vec<_>>(), &[(&max, &0)]);
 218 }
 219
 220 #[test]
 221 fn test_range_equal_empty_cases() {
 222     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 223     assert_eq!(map.range((Included(2), Excluded(2))).next(), None);
 224     assert_eq!(map.range((Excluded(2), Included(2))).next(), None);
 225 }
 226
 227 #[test]
 228 #[should_panic]
 229 #[cfg(not(miri))] // Miri does not support panics
 230 fn test_range_equal_excluded() {
 231     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 232     map.range((Excluded(2), Excluded(2)));
 233 }
 234
 235 #[test]
 236 #[should_panic]
 237 #[cfg(not(miri))] // Miri does not support panics
 238 fn test_range_backwards_1() {
 239     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 240     map.range((Included(3), Included(2)));
 241 }
 242
 243 #[test]
 244 #[should_panic]
 245 #[cfg(not(miri))] // Miri does not support panics
 246 fn test_range_backwards_2() {
 247     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 248     map.range((Included(3), Excluded(2)));
 249 }
 250
 251 #[test]
 252 #[should_panic]
 253 #[cfg(not(miri))] // Miri does not support panics
 254 fn test_range_backwards_3() {
 255     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 256     map.range((Excluded(3), Included(2)));
 257 }
 258
 259 #[test]
 260 #[should_panic]
 261 #[cfg(not(miri))] // Miri does not support panics
 262 fn test_range_backwards_4() {
 263     let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect();
 264     map.range((Excluded(3), Excluded(2)));
 265 }
 266
 267 #[test]
 268 fn test_range_1000() {
 269     #[cfg(not(miri))] // Miri is too slow
 270     let size = 1000;
 271     #[cfg(miri)]
 272     let size = 200;
 273     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 274
 275     fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
 276         let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v));
 277         let mut pairs = (0..size).map(|i| (i, i));
 278
 279         for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 280             assert_eq!(kv, pair);
 281         }
 282         assert_eq!(kvs.next(), None);
 283         assert_eq!(pairs.next(), None);
 284     }
 285     test(&map, size, Included(&0), Excluded(&size));
 286     test(&map, size, Unbounded, Excluded(&size));
 287     test(&map, size, Included(&0), Included(&(size - 1)));
 288     test(&map, size, Unbounded, Included(&(size - 1)));
 289     test(&map, size, Included(&0), Unbounded);
 290     test(&map, size, Unbounded, Unbounded);
 291 }
 292
 293 #[test]
 294 fn test_range_borrowed_key() {
 295     let mut map = BTreeMap::new();
 296     map.insert("aardvark".to_string(), 1);
 297     map.insert("baboon".to_string(), 2);
 298     map.insert("coyote".to_string(), 3);
 299     map.insert("dingo".to_string(), 4);
 300     // NOTE: would like to use simply "b".."d" here...
 301     let mut iter = map.range::<str, _>((Included("b"),Excluded("d")));
 302     assert_eq!(iter.next(), Some((&"baboon".to_string(), &2)));
 303     assert_eq!(iter.next(), Some((&"coyote".to_string(), &3)));
 304     assert_eq!(iter.next(), None);
 305 }
 306
 307 #[test]
 308 fn test_range() {
 309     #[cfg(not(miri))] // Miri is too slow
 310     let size = 200;
 311     #[cfg(miri)]
 312     let size = 30;
 313     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 314
 315     for i in 0..size {
 316         for j in i..size {
 317             let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
 318             let mut pairs = (i..=j).map(|i| (i, i));
 319
 320             for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 321                 assert_eq!(kv, pair);
 322             }
 323             assert_eq!(kvs.next(), None);
 324             assert_eq!(pairs.next(), None);
 325         }
 326     }
 327 }
 328
 329 #[test]
 330 fn test_range_mut() {
 331     #[cfg(not(miri))] // Miri is too slow
 332     let size = 200;
 333     #[cfg(miri)]
 334     let size = 30;
 335     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 336
 337     for i in 0..size {
 338         for j in i..size {
 339             let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
 340             let mut pairs = (i..=j).map(|i| (i, i));
 341
 342             for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 343                 assert_eq!(kv, pair);
 344             }
 345             assert_eq!(kvs.next(), None);
 346             assert_eq!(pairs.next(), None);
 347         }
 348     }
 349 }
 350
 351 #[test]
 352 fn test_borrow() {
 353     // make sure these compile -- using the Borrow trait
 354     {
 355         let mut map = BTreeMap::new();
 356         map.insert("0".to_string(), 1);
 357         assert_eq!(map["0"], 1);
 358     }
 359
 360     {
 361         let mut map = BTreeMap::new();
 362         map.insert(Box::new(0), 1);
 363         assert_eq!(map[&0], 1);
 364     }
 365
 366     {
 367         let mut map = BTreeMap::new();
 368         map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
 369         assert_eq!(map[&[0, 1][..]], 1);
 370     }
 371
 372     {
 373         let mut map = BTreeMap::new();
 374         map.insert(Rc::new(0), 1);
 375         assert_eq!(map[&0], 1);
 376     }
 377 }
 378
 379 #[test]
 380 fn test_entry() {
 381     let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
 382
 383     let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
 384
 385     // Existing key (insert)
 386     match map.entry(1) {
 387         Vacant(_) => unreachable!(),
 388         Occupied(mut view) => {
 389             assert_eq!(view.get(), &10);
 390             assert_eq!(view.insert(100), 10);
 391         }
 392     }
 393     assert_eq!(map.get(&1).unwrap(), &100);
 394     assert_eq!(map.len(), 6);
 395
 396
 397     // Existing key (update)
 398     match map.entry(2) {
 399         Vacant(_) => unreachable!(),
 400         Occupied(mut view) => {
 401             let v = view.get_mut();
 402             *v *= 10;
 403         }
 404     }
 405     assert_eq!(map.get(&2).unwrap(), &200);
 406     assert_eq!(map.len(), 6);
 407
 408     // Existing key (take)
 409     match map.entry(3) {
 410         Vacant(_) => unreachable!(),
 411         Occupied(view) => {
 412             assert_eq!(view.remove(), 30);
 413         }
 414     }
 415     assert_eq!(map.get(&3), None);
 416     assert_eq!(map.len(), 5);
 417
 418
 419     // Inexistent key (insert)
 420     match map.entry(10) {
 421         Occupied(_) => unreachable!(),
 422         Vacant(view) => {
 423             assert_eq!(*view.insert(1000), 1000);
 424         }
 425     }
 426     assert_eq!(map.get(&10).unwrap(), &1000);
 427     assert_eq!(map.len(), 6);
 428 }
 429
 430 #[test]
 431 fn test_extend_ref() {
 432     let mut a = BTreeMap::new();
 433     a.insert(1, "one");
 434     let mut b = BTreeMap::new();
 435     b.insert(2, "two");
 436     b.insert(3, "three");
 437
 438     a.extend(&b);
 439
 440     assert_eq!(a.len(), 3);
 441     assert_eq!(a[&1], "one");
 442     assert_eq!(a[&2], "two");
 443     assert_eq!(a[&3], "three");
 444 }
 445
 446 #[test]
 447 fn test_zst() {
 448     let mut m = BTreeMap::new();
 449     assert_eq!(m.len(), 0);
 450
 451     assert_eq!(m.insert((), ()), None);
 452     assert_eq!(m.len(), 1);
 453
 454     assert_eq!(m.insert((), ()), Some(()));
 455     assert_eq!(m.len(), 1);
 456     assert_eq!(m.iter().count(), 1);
 457
 458     m.clear();
 459     assert_eq!(m.len(), 0);
 460
 461     for _ in 0..100 {
 462         m.insert((), ());
 463     }
 464
 465     assert_eq!(m.len(), 1);
 466     assert_eq!(m.iter().count(), 1);
 467 }
 468
 469 // This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
 470 // do not cause segfaults when used with zero-sized values. All other map behavior is
 471 // undefined.
 472 #[test]
 473 fn test_bad_zst() {
 474     use std::cmp::Ordering;
 475
 476     struct Bad;
 477
 478     impl PartialEq for Bad {
 479         fn eq(&self, _: &Self) -> bool {
 480             false
 481         }
 482     }
 483
 484     impl Eq for Bad {}
 485
 486     impl PartialOrd for Bad {
 487         fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
 488             Some(Ordering::Less)
 489         }
 490     }
 491
 492     impl Ord for Bad {
 493         fn cmp(&self, _: &Self) -> Ordering {
 494             Ordering::Less
 495         }
 496     }
 497
 498     let mut m = BTreeMap::new();
 499
 500     for _ in 0..100 {
 501         m.insert(Bad, Bad);
 502     }
 503 }
 504
 505 #[test]
 506 fn test_clone() {
 507     let mut map = BTreeMap::new();
 508     #[cfg(not(miri))] // Miri is too slow
 509     let size = 100;
 510     #[cfg(miri)]
 511     let size = 30;
 512     assert_eq!(map.len(), 0);
 513
 514     for i in 0..size {
 515         assert_eq!(map.insert(i, 10 * i), None);
 516         assert_eq!(map.len(), i + 1);
 517         assert_eq!(map, map.clone());
 518     }
 519
 520     for i in 0..size {
 521         assert_eq!(map.insert(i, 100 * i), Some(10 * i));
 522         assert_eq!(map.len(), size);
 523         assert_eq!(map, map.clone());
 524     }
 525
 526     for i in 0..size / 2 {
 527         assert_eq!(map.remove(&(i * 2)), Some(i * 200));
 528         assert_eq!(map.len(), size - i - 1);
 529         assert_eq!(map, map.clone());
 530     }
 531
 532     for i in 0..size / 2 {
 533         assert_eq!(map.remove(&(2 * i)), None);
 534         assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
 535         assert_eq!(map.len(), size / 2 - i - 1);
 536         assert_eq!(map, map.clone());
 537     }
 538 }
 539
 540 #[test]
 541 #[allow(dead_code)]
 542 fn test_variance() {
 543     use std::collections::btree_map::{Iter, IntoIter, Range, Keys, Values};
 544
 545     fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> {
 546         v
 547     }
 548     fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> {
 549         v
 550     }
 551     fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> {
 552         v
 553     }
 554     fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> {
 555         v
 556     }
 557     fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> {
 558         v
 559     }
 560     fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> {
 561         v
 562     }
 563     fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> {
 564         v
 565     }
 566     fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> {
 567         v
 568     }
 569     fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> {
 570         v
 571     }
 572     fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> {
 573         v
 574     }
 575 }
 576
 577 #[test]
 578 fn test_occupied_entry_key() {
 579     let mut a = BTreeMap::new();
 580     let key = "hello there";
 581     let value = "value goes here";
 582     assert!(a.is_empty());
 583     a.insert(key.clone(), value.clone());
 584     assert_eq!(a.len(), 1);
 585     assert_eq!(a[key], value);
 586
 587     match a.entry(key.clone()) {
 588         Vacant(_) => panic!(),
 589         Occupied(e) => assert_eq!(key, *e.key()),
 590     }
 591     assert_eq!(a.len(), 1);
 592     assert_eq!(a[key], value);
 593 }
 594
 595 #[test]
 596 fn test_vacant_entry_key() {
 597     let mut a = BTreeMap::new();
 598     let key = "hello there";
 599     let value = "value goes here";
 600
 601     assert!(a.is_empty());
 602     match a.entry(key.clone()) {
 603         Occupied(_) => panic!(),
 604         Vacant(e) => {
 605             assert_eq!(key, *e.key());
 606             e.insert(value.clone());
 607         }
 608     }
 609     assert_eq!(a.len(), 1);
 610     assert_eq!(a[key], value);
 611 }
 612
 613 macro_rules! create_append_test {
 614     ($name:ident, $len:expr) => {
 615         #[test]
 616         fn $name() {
 617             let mut a = BTreeMap::new();
 618             for i in 0..8 {
 619                 a.insert(i, i);
 620             }
 621
 622             let mut b = BTreeMap::new();
 623             for i in 5..$len {
 624                 b.insert(i, 2*i);
 625             }
 626
 627             a.append(&mut b);
 628
 629             assert_eq!(a.len(), $len);
 630             assert_eq!(b.len(), 0);
 631
 632             for i in 0..$len {
 633                 if i < 5 {
 634                     assert_eq!(a[&i], i);
 635                 } else {
 636                     assert_eq!(a[&i], 2*i);
 637                 }
 638             }
 639
 640             assert_eq!(a.remove(&($len-1)), Some(2*($len-1)));
 641             assert_eq!(a.insert($len-1, 20), None);
 642         }
 643     };
 644 }
 645
 646 // These are mostly for testing the algorithm that "fixes" the right edge after insertion.
 647 // Single node.
 648 create_append_test!(test_append_9, 9);
 649 // Two leafs that don't need fixing.
 650 create_append_test!(test_append_17, 17);
 651 // Two leafs where the second one ends up underfull and needs stealing at the end.
 652 create_append_test!(test_append_14, 14);
 653 // Two leafs where the second one ends up empty because the insertion finished at the root.
 654 create_append_test!(test_append_12, 12);
 655 // Three levels; insertion finished at the root.
 656 create_append_test!(test_append_144, 144);
 657 // Three levels; insertion finished at leaf while there is an empty node on the second level.
 658 create_append_test!(test_append_145, 145);
 659 // Tests for several randomly chosen sizes.
 660 create_append_test!(test_append_170, 170);
 661 create_append_test!(test_append_181, 181);
 662 create_append_test!(test_append_239, 239);
 663 #[cfg(not(miri))] // Miri is too slow
 664 create_append_test!(test_append_1700, 1700);
 665
 666 fn rand_data(len: usize) -> Vec<(u32, u32)> {
 667     let mut rng = DeterministicRng::new();
 668     Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
 669 }
 670
 671 #[test]
 672 fn test_split_off_empty_right() {
 673     let mut data = rand_data(173);
 674
 675     let mut map = BTreeMap::from_iter(data.clone());
 676     let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
 677
 678     data.sort();
 679     assert!(map.into_iter().eq(data));
 680     assert!(right.into_iter().eq(None));
 681 }
 682
 683 #[test]
 684 fn test_split_off_empty_left() {
 685     let mut data = rand_data(314);
 686
 687     let mut map = BTreeMap::from_iter(data.clone());
 688     let right = map.split_off(&data.iter().min().unwrap().0);
 689
 690     data.sort();
 691     assert!(map.into_iter().eq(None));
 692     assert!(right.into_iter().eq(data));
 693 }
 694
 695 #[test]
 696 fn test_split_off_large_random_sorted() {
 697     let mut data = rand_data(1529);
 698     // special case with maximum height.
 699     data.sort();
 700
 701     let mut map = BTreeMap::from_iter(data.clone());
 702     let key = data[data.len() / 2].0;
 703     let right = map.split_off(&key);
 704
 705     assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
 706     assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));
 707 }