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