src/liballoc/tests/btree/map.rs

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