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::{Excluded, Included, Unbounded, self};
  13 use std::collections::btree_map::Entry::{Occupied, Vacant};
  14 use std::rc::Rc;
  15
  16 #[test]
  17 fn test_basic_large() {
  18     let mut map = BTreeMap::new();
  19     let size = 10000;
  20     assert_eq!(map.len(), 0);
  21
  22     for i in 0..size {
  23         assert_eq!(map.insert(i, 10*i), None);
  24         assert_eq!(map.len(), i + 1);
  25     }
  26
  27     for i in 0..size {
  28         assert_eq!(map.get(&i).unwrap(), &(i*10));
  29     }
  30
  31     for i in size..size*2 {
  32         assert_eq!(map.get(&i), None);
  33     }
  34
  35     for i in 0..size {
  36         assert_eq!(map.insert(i, 100*i), Some(10*i));
  37         assert_eq!(map.len(), size);
  38     }
  39
  40     for i in 0..size {
  41         assert_eq!(map.get(&i).unwrap(), &(i*100));
  42     }
  43
  44     for i in 0..size/2 {
  45         assert_eq!(map.remove(&(i*2)), Some(i*200));
  46         assert_eq!(map.len(), size - i - 1);
  47     }
  48
  49     for i in 0..size/2 {
  50         assert_eq!(map.get(&(2*i)), None);
  51         assert_eq!(map.get(&(2*i+1)).unwrap(), &(i*200 + 100));
  52     }
  53
  54     for i in 0..size/2 {
  55         assert_eq!(map.remove(&(2*i)), None);
  56         assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100));
  57         assert_eq!(map.len(), size/2 - i - 1);
  58     }
  59 }
  60
  61 #[test]
  62 fn test_basic_small() {
  63     let mut map = BTreeMap::new();
  64     assert_eq!(map.remove(&1), None);
  65     assert_eq!(map.get(&1), None);
  66     assert_eq!(map.insert(1, 1), None);
  67     assert_eq!(map.get(&1), Some(&1));
  68     assert_eq!(map.insert(1, 2), Some(1));
  69     assert_eq!(map.get(&1), Some(&2));
  70     assert_eq!(map.insert(2, 4), None);
  71     assert_eq!(map.get(&2), Some(&4));
  72     assert_eq!(map.remove(&1), Some(2));
  73     assert_eq!(map.remove(&2), Some(4));
  74     assert_eq!(map.remove(&1), None);
  75 }
  76
  77 #[test]
  78 fn test_iter() {
  79     let size = 10000;
  80
  81     // Forwards
  82     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
  83
  84     fn test<T>(size: usize, mut iter: T) where T: Iterator<Item=(usize, usize)> {
  85         for i in 0..size {
  86             assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
  87             assert_eq!(iter.next().unwrap(), (i, i));
  88         }
  89         assert_eq!(iter.size_hint(), (0, Some(0)));
  90         assert_eq!(iter.next(), None);
  91     }
  92     test(size, map.iter().map(|(&k, &v)| (k, v)));
  93     test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
  94     test(size, map.into_iter());
  95 }
  96
  97 #[test]
  98 fn test_iter_rev() {
  99     let size = 10000;
 100
 101     // Forwards
 102     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 103
 104     fn test<T>(size: usize, mut iter: T) where T: Iterator<Item=(usize, usize)> {
 105         for i in 0..size {
 106             assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
 107             assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
 108         }
 109         assert_eq!(iter.size_hint(), (0, Some(0)));
 110         assert_eq!(iter.next(), None);
 111     }
 112     test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
 113     test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
 114     test(size, map.into_iter().rev());
 115 }
 116
 117 #[test]
 118 fn test_values_mut() {
 119     let mut a = BTreeMap::new();
 120     a.insert(1, String::from("hello"));
 121     a.insert(2, String::from("goodbye"));
 122
 123     for value in a.values_mut() {
 124         value.push_str("!");
 125     }
 126
 127     let values: Vec<String> = a.values().cloned().collect();
 128     assert_eq!(values, [String::from("hello!"),
 129                         String::from("goodbye!")]);
 130 }
 131
 132 #[test]
 133 fn test_iter_mixed() {
 134     let size = 10000;
 135
 136     // Forwards
 137     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 138
 139     fn test<T>(size: usize, mut iter: T)
 140             where T: Iterator<Item=(usize, usize)> + DoubleEndedIterator {
 141         for i in 0..size / 4 {
 142             assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
 143             assert_eq!(iter.next().unwrap(), (i, i));
 144             assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
 145         }
 146         for i in size / 4..size * 3 / 4 {
 147             assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
 148             assert_eq!(iter.next().unwrap(), (i, i));
 149         }
 150         assert_eq!(iter.size_hint(), (0, Some(0)));
 151         assert_eq!(iter.next(), None);
 152     }
 153     test(size, map.iter().map(|(&k, &v)| (k, v)));
 154     test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
 155     test(size, map.into_iter());
 156 }
 157
 158 #[test]
 159 fn test_range_small() {
 160     let size = 5;
 161
 162     // Forwards
 163     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 164
 165     let mut j = 0;
 166     for ((&k, &v), i) in map.range(Included(&2), Unbounded).zip(2..size) {
 167         assert_eq!(k, i);
 168         assert_eq!(v, i);
 169         j += 1;
 170     }
 171     assert_eq!(j, size - 2);
 172 }
 173
 174 #[test]
 175 fn test_range_1000() {
 176     let size = 1000;
 177     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 178
 179     fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
 180         let mut kvs = map.range(min, max).map(|(&k, &v)| (k, v));
 181         let mut pairs = (0..size).map(|i| (i, i));
 182
 183         for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 184             assert_eq!(kv, pair);
 185         }
 186         assert_eq!(kvs.next(), None);
 187         assert_eq!(pairs.next(), None);
 188     }
 189     test(&map, size, Included(&0), Excluded(&size));
 190     test(&map, size, Unbounded, Excluded(&size));
 191     test(&map, size, Included(&0), Included(&(size - 1)));
 192     test(&map, size, Unbounded, Included(&(size - 1)));
 193     test(&map, size, Included(&0), Unbounded);
 194     test(&map, size, Unbounded, Unbounded);
 195 }
 196
 197 #[test]
 198 fn test_range() {
 199     let size = 200;
 200     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 201
 202     for i in 0..size {
 203         for j in i..size {
 204             let mut kvs = map.range(Included(&i), Included(&j)).map(|(&k, &v)| (k, v));
 205             let mut pairs = (i..j+1).map(|i| (i, i));
 206
 207             for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 208                 assert_eq!(kv, pair);
 209             }
 210             assert_eq!(kvs.next(), None);
 211             assert_eq!(pairs.next(), None);
 212         }
 213     }
 214 }
 215
 216 #[test]
 217 fn test_borrow() {
 218     // make sure these compile -- using the Borrow trait
 219     {
 220         let mut map = BTreeMap::new();
 221         map.insert("0".to_string(), 1);
 222         assert_eq!(map["0"], 1);
 223     }
 224
 225     {
 226         let mut map = BTreeMap::new();
 227         map.insert(Box::new(0), 1);
 228         assert_eq!(map[&0], 1);
 229     }
 230
 231     {
 232         let mut map = BTreeMap::new();
 233         map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
 234         assert_eq!(map[&[0, 1][..]], 1);
 235     }
 236
 237     {
 238         let mut map = BTreeMap::new();
 239         map.insert(Rc::new(0), 1);
 240         assert_eq!(map[&0], 1);
 241     }
 242 }
 243
 244 #[test]
 245 fn test_entry(){
 246     let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
 247
 248     let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
 249
 250     // Existing key (insert)
 251     match map.entry(1) {
 252         Vacant(_) => unreachable!(),
 253         Occupied(mut view) => {
 254             assert_eq!(view.get(), &10);
 255             assert_eq!(view.insert(100), 10);
 256         }
 257     }
 258     assert_eq!(map.get(&1).unwrap(), &100);
 259     assert_eq!(map.len(), 6);
 260
 261
 262     // Existing key (update)
 263     match map.entry(2) {
 264         Vacant(_) => unreachable!(),
 265         Occupied(mut view) => {
 266             let v = view.get_mut();
 267             *v *= 10;
 268         }
 269     }
 270     assert_eq!(map.get(&2).unwrap(), &200);
 271     assert_eq!(map.len(), 6);
 272
 273     // Existing key (take)
 274     match map.entry(3) {
 275         Vacant(_) => unreachable!(),
 276         Occupied(view) => {
 277             assert_eq!(view.remove(), 30);
 278         }
 279     }
 280     assert_eq!(map.get(&3), None);
 281     assert_eq!(map.len(), 5);
 282
 283
 284     // Inexistent key (insert)
 285     match map.entry(10) {
 286         Occupied(_) => unreachable!(),
 287         Vacant(view) => {
 288             assert_eq!(*view.insert(1000), 1000);
 289         }
 290     }
 291     assert_eq!(map.get(&10).unwrap(), &1000);
 292     assert_eq!(map.len(), 6);
 293 }
 294
 295 #[test]
 296 fn test_extend_ref() {
 297     let mut a = BTreeMap::new();
 298     a.insert(1, "one");
 299     let mut b = BTreeMap::new();
 300     b.insert(2, "two");
 301     b.insert(3, "three");
 302
 303     a.extend(&b);
 304
 305     assert_eq!(a.len(), 3);
 306     assert_eq!(a[&1], "one");
 307     assert_eq!(a[&2], "two");
 308     assert_eq!(a[&3], "three");
 309 }
 310
 311 #[test]
 312 fn test_zst() {
 313     let mut m = BTreeMap::new();
 314     assert_eq!(m.len(), 0);
 315
 316     assert_eq!(m.insert((), ()), None);
 317     assert_eq!(m.len(), 1);
 318
 319     assert_eq!(m.insert((), ()), Some(()));
 320     assert_eq!(m.len(), 1);
 321     assert_eq!(m.iter().count(), 1);
 322
 323     m.clear();
 324     assert_eq!(m.len(), 0);
 325
 326     for _ in 0..100 {
 327         m.insert((), ());
 328     }
 329
 330     assert_eq!(m.len(), 1);
 331     assert_eq!(m.iter().count(), 1);
 332 }
 333
 334 // This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
 335 // do not cause segfaults when used with zero-sized values. All other map behavior is
 336 // undefined.
 337 #[test]
 338 fn test_bad_zst() {
 339     use std::cmp::Ordering;
 340
 341     struct Bad;
 342
 343     impl PartialEq for Bad {
 344         fn eq(&self, _: &Self) -> bool { false }
 345     }
 346
 347     impl Eq for Bad {}
 348
 349     impl PartialOrd for Bad {
 350         fn partial_cmp(&self, _: &Self) -> Option<Ordering> { Some(Ordering::Less) }
 351     }
 352
 353     impl Ord for Bad {
 354         fn cmp(&self, _: &Self) -> Ordering { Ordering::Less }
 355     }
 356
 357     let mut m = BTreeMap::new();
 358
 359     for _ in 0..100 {
 360         m.insert(Bad, Bad);
 361     }
 362 }
 363
 364 #[test]
 365 fn test_clone() {
 366     let mut map = BTreeMap::new();
 367     let size = 100;
 368     assert_eq!(map.len(), 0);
 369
 370     for i in 0..size {
 371         assert_eq!(map.insert(i, 10*i), None);
 372         assert_eq!(map.len(), i + 1);
 373         assert_eq!(map, map.clone());
 374     }
 375
 376     for i in 0..size {
 377         assert_eq!(map.insert(i, 100*i), Some(10*i));
 378         assert_eq!(map.len(), size);
 379         assert_eq!(map, map.clone());
 380     }
 381
 382     for i in 0..size/2 {
 383         assert_eq!(map.remove(&(i*2)), Some(i*200));
 384         assert_eq!(map.len(), size - i - 1);
 385         assert_eq!(map, map.clone());
 386     }
 387
 388     for i in 0..size/2 {
 389         assert_eq!(map.remove(&(2*i)), None);
 390         assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100));
 391         assert_eq!(map.len(), size/2 - i - 1);
 392         assert_eq!(map, map.clone());
 393     }
 394 }
 395
 396 #[test]
 397 #[allow(dead_code)]
 398 fn test_variance() {
 399     use std::collections::btree_map::{Iter, IntoIter, Range, Keys, Values};
 400
 401     fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> { v }
 402     fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> { v }
 403     fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> { v }
 404     fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> { v }
 405     fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> { v }
 406     fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> { v }
 407     fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> { v }
 408     fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> { v }
 409     fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> { v }
 410     fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> { v }
 411 }
 412
 413 #[test]
 414 fn test_occupied_entry_key() {
 415     let mut a = BTreeMap::new();
 416     let key = "hello there";
 417     let value = "value goes here";
 418     assert!(a.is_empty());
 419     a.insert(key.clone(), value.clone());
 420     assert_eq!(a.len(), 1);
 421     assert_eq!(a[key], value);
 422
 423     match a.entry(key.clone()) {
 424         Vacant(_) => panic!(),
 425         Occupied(e) => assert_eq!(key, *e.key()),
 426     }
 427     assert_eq!(a.len(), 1);
 428     assert_eq!(a[key], value);
 429 }
 430
 431 #[test]
 432 fn test_vacant_entry_key() {
 433     let mut a = BTreeMap::new();
 434     let key = "hello there";
 435     let value = "value goes here";
 436
 437     assert!(a.is_empty());
 438     match a.entry(key.clone()) {
 439         Occupied(_) => panic!(),
 440         Vacant(e) => {
 441             assert_eq!(key, *e.key());
 442             e.insert(value.clone());
 443         },
 444     }
 445     assert_eq!(a.len(), 1);
 446     assert_eq!(a[key], value);
 447 }
 448
 449 mod bench {
 450     use std::collections::BTreeMap;
 451     use std::__rand::{Rng, thread_rng};
 452
 453     use test::{Bencher, black_box};
 454
 455     map_insert_rand_bench!{insert_rand_100,    100,    BTreeMap}
 456     map_insert_rand_bench!{insert_rand_10_000, 10_000, BTreeMap}
 457
 458     map_insert_seq_bench!{insert_seq_100,    100,    BTreeMap}
 459     map_insert_seq_bench!{insert_seq_10_000, 10_000, BTreeMap}
 460
 461     map_find_rand_bench!{find_rand_100,    100,    BTreeMap}
 462     map_find_rand_bench!{find_rand_10_000, 10_000, BTreeMap}
 463
 464     map_find_seq_bench!{find_seq_100,    100,    BTreeMap}
 465     map_find_seq_bench!{find_seq_10_000, 10_000, BTreeMap}
 466
 467     fn bench_iter(b: &mut Bencher, size: i32) {
 468         let mut map = BTreeMap::<i32, i32>::new();
 469         let mut rng = thread_rng();
 470
 471         for _ in 0..size {
 472             map.insert(rng.gen(), rng.gen());
 473         }
 474
 475         b.iter(|| {
 476             for entry in &map {
 477                 black_box(entry);
 478             }
 479         });
 480     }
 481
 482     #[bench]
 483     pub fn iter_20(b: &mut Bencher) {
 484         bench_iter(b, 20);
 485     }
 486
 487     #[bench]
 488     pub fn iter_1000(b: &mut Bencher) {
 489         bench_iter(b, 1000);
 490     }
 491
 492     #[bench]
 493     pub fn iter_100000(b: &mut Bencher) {
 494         bench_iter(b, 100000);
 495     }
 496 }