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::iter::range_inclusive;
  15 use std::rc::Rc;
  16
  17 #[test]
  18 fn test_basic_large() {
  19     let mut map = BTreeMap::new();
  20     let size = 10000;
  21     assert_eq!(map.len(), 0);
  22
  23     for i in 0..size {
  24         assert_eq!(map.insert(i, 10*i), None);
  25         assert_eq!(map.len(), i + 1);
  26     }
  27
  28     for i in 0..size {
  29         assert_eq!(map.get(&i).unwrap(), &(i*10));
  30     }
  31
  32     for i in size..size*2 {
  33         assert_eq!(map.get(&i), None);
  34     }
  35
  36     for i in 0..size {
  37         assert_eq!(map.insert(i, 100*i), Some(10*i));
  38         assert_eq!(map.len(), size);
  39     }
  40
  41     for i in 0..size {
  42         assert_eq!(map.get(&i).unwrap(), &(i*100));
  43     }
  44
  45     for i in 0..size/2 {
  46         assert_eq!(map.remove(&(i*2)), Some(i*200));
  47         assert_eq!(map.len(), size - i - 1);
  48     }
  49
  50     for i in 0..size/2 {
  51         assert_eq!(map.get(&(2*i)), None);
  52         assert_eq!(map.get(&(2*i+1)).unwrap(), &(i*200 + 100));
  53     }
  54
  55     for i in 0..size/2 {
  56         assert_eq!(map.remove(&(2*i)), None);
  57         assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100));
  58         assert_eq!(map.len(), size/2 - i - 1);
  59     }
  60 }
  61
  62 #[test]
  63 fn test_basic_small() {
  64     let mut map = BTreeMap::new();
  65     assert_eq!(map.remove(&1), None);
  66     assert_eq!(map.get(&1), None);
  67     assert_eq!(map.insert(1, 1), None);
  68     assert_eq!(map.get(&1), Some(&1));
  69     assert_eq!(map.insert(1, 2), Some(1));
  70     assert_eq!(map.get(&1), Some(&2));
  71     assert_eq!(map.insert(2, 4), None);
  72     assert_eq!(map.get(&2), Some(&4));
  73     assert_eq!(map.remove(&1), Some(2));
  74     assert_eq!(map.remove(&2), Some(4));
  75     assert_eq!(map.remove(&1), None);
  76 }
  77
  78 #[test]
  79 fn test_iter() {
  80     let size = 10000;
  81
  82     // Forwards
  83     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
  84
  85     fn test<T>(size: usize, mut iter: T) where T: Iterator<Item=(usize, usize)> {
  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     let size = 10000;
 101
 102     // Forwards
 103     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 104
 105     fn test<T>(size: usize, mut iter: T) where T: Iterator<Item=(usize, usize)> {
 106         for i in 0..size {
 107             assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
 108             assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
 109         }
 110         assert_eq!(iter.size_hint(), (0, Some(0)));
 111         assert_eq!(iter.next(), None);
 112     }
 113     test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
 114     test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
 115     test(size, map.into_iter().rev());
 116 }
 117
 118 #[test]
 119 fn test_iter_mixed() {
 120     let size = 10000;
 121
 122     // Forwards
 123     let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 124
 125     fn test<T>(size: usize, mut iter: T)
 126             where T: Iterator<Item=(usize, usize)> + DoubleEndedIterator {
 127         for i in 0..size / 4 {
 128             assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
 129             assert_eq!(iter.next().unwrap(), (i, i));
 130             assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
 131         }
 132         for i in size / 4..size * 3 / 4 {
 133             assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
 134             assert_eq!(iter.next().unwrap(), (i, i));
 135         }
 136         assert_eq!(iter.size_hint(), (0, Some(0)));
 137         assert_eq!(iter.next(), None);
 138     }
 139     test(size, map.iter().map(|(&k, &v)| (k, v)));
 140     test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
 141     test(size, map.into_iter());
 142 }
 143
 144 #[test]
 145 fn test_range_small() {
 146     let size = 5;
 147
 148     // Forwards
 149     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 150
 151     let mut j = 0;
 152     for ((&k, &v), i) in map.range(Included(&2), Unbounded).zip(2..size) {
 153         assert_eq!(k, i);
 154         assert_eq!(v, i);
 155         j += 1;
 156     }
 157     assert_eq!(j, size - 2);
 158 }
 159
 160 #[test]
 161 fn test_range_1000() {
 162     let size = 1000;
 163     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 164
 165     fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
 166         let mut kvs = map.range(min, max).map(|(&k, &v)| (k, v));
 167         let mut pairs = (0..size).map(|i| (i, i));
 168
 169         for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 170             assert_eq!(kv, pair);
 171         }
 172         assert_eq!(kvs.next(), None);
 173         assert_eq!(pairs.next(), None);
 174     }
 175     test(&map, size, Included(&0), Excluded(&size));
 176     test(&map, size, Unbounded, Excluded(&size));
 177     test(&map, size, Included(&0), Included(&(size - 1)));
 178     test(&map, size, Unbounded, Included(&(size - 1)));
 179     test(&map, size, Included(&0), Unbounded);
 180     test(&map, size, Unbounded, Unbounded);
 181 }
 182
 183 #[test]
 184 fn test_range() {
 185     let size = 200;
 186     let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
 187
 188     for i in 0..size {
 189         for j in i..size {
 190             let mut kvs = map.range(Included(&i), Included(&j)).map(|(&k, &v)| (k, v));
 191             let mut pairs = range_inclusive(i, j).map(|i| (i, i));
 192
 193             for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
 194                 assert_eq!(kv, pair);
 195             }
 196             assert_eq!(kvs.next(), None);
 197             assert_eq!(pairs.next(), None);
 198         }
 199     }
 200 }
 201
 202 #[test]
 203 fn test_borrow() {
 204     // make sure these compile -- using the Borrow trait
 205     {
 206         let mut map = BTreeMap::new();
 207         map.insert("0".to_string(), 1);
 208         assert_eq!(map["0"], 1);
 209     }
 210
 211     {
 212         let mut map = BTreeMap::new();
 213         map.insert(Box::new(0), 1);
 214         assert_eq!(map[&0], 1);
 215     }
 216
 217     {
 218         let mut map = BTreeMap::new();
 219         map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
 220         assert_eq!(map[&[0, 1][..]], 1);
 221     }
 222
 223     {
 224         let mut map = BTreeMap::new();
 225         map.insert(Rc::new(0), 1);
 226         assert_eq!(map[&0], 1);
 227     }
 228 }
 229
 230 #[test]
 231 fn test_entry(){
 232     let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
 233
 234     let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
 235
 236     // Existing key (insert)
 237     match map.entry(1) {
 238         Vacant(_) => unreachable!(),
 239         Occupied(mut view) => {
 240             assert_eq!(view.get(), &10);
 241             assert_eq!(view.insert(100), 10);
 242         }
 243     }
 244     assert_eq!(map.get(&1).unwrap(), &100);
 245     assert_eq!(map.len(), 6);
 246
 247
 248     // Existing key (update)
 249     match map.entry(2) {
 250         Vacant(_) => unreachable!(),
 251         Occupied(mut view) => {
 252             let v = view.get_mut();
 253             *v *= 10;
 254         }
 255     }
 256     assert_eq!(map.get(&2).unwrap(), &200);
 257     assert_eq!(map.len(), 6);
 258
 259     // Existing key (take)
 260     match map.entry(3) {
 261         Vacant(_) => unreachable!(),
 262         Occupied(view) => {
 263             assert_eq!(view.remove(), 30);
 264         }
 265     }
 266     assert_eq!(map.get(&3), None);
 267     assert_eq!(map.len(), 5);
 268
 269
 270     // Inexistent key (insert)
 271     match map.entry(10) {
 272         Occupied(_) => unreachable!(),
 273         Vacant(view) => {
 274             assert_eq!(*view.insert(1000), 1000);
 275         }
 276     }
 277     assert_eq!(map.get(&10).unwrap(), &1000);
 278     assert_eq!(map.len(), 6);
 279 }
 280
 281 #[test]
 282 fn test_extend_ref() {
 283     let mut a = BTreeMap::new();
 284     a.insert(1, "one");
 285     let mut b = BTreeMap::new();
 286     b.insert(2, "two");
 287     b.insert(3, "three");
 288
 289     a.extend(&b);
 290
 291     assert_eq!(a.len(), 3);
 292     assert_eq!(a[&1], "one");
 293     assert_eq!(a[&2], "two");
 294     assert_eq!(a[&3], "three");
 295 }
 296
 297 mod bench {
 298     use std::collections::BTreeMap;
 299     use std::__rand::{Rng, thread_rng};
 300
 301     use test::{Bencher, black_box};
 302
 303     map_insert_rand_bench!{insert_rand_100,    100,    BTreeMap}
 304     map_insert_rand_bench!{insert_rand_10_000, 10_000, BTreeMap}
 305
 306     map_insert_seq_bench!{insert_seq_100,    100,    BTreeMap}
 307     map_insert_seq_bench!{insert_seq_10_000, 10_000, BTreeMap}
 308
 309     map_find_rand_bench!{find_rand_100,    100,    BTreeMap}
 310     map_find_rand_bench!{find_rand_10_000, 10_000, BTreeMap}
 311
 312     map_find_seq_bench!{find_seq_100,    100,    BTreeMap}
 313     map_find_seq_bench!{find_seq_10_000, 10_000, BTreeMap}
 314
 315     fn bench_iter(b: &mut Bencher, size: i32) {
 316         let mut map = BTreeMap::<i32, i32>::new();
 317         let mut rng = thread_rng();
 318
 319         for _ in 0..size {
 320             map.insert(rng.gen(), rng.gen());
 321         }
 322
 323         b.iter(|| {
 324             for entry in &map {
 325                 black_box(entry);
 326             }
 327         });
 328     }
 329
 330     #[bench]
 331     pub fn iter_20(b: &mut Bencher) {
 332         bench_iter(b, 20);
 333     }
 334
 335     #[bench]
 336     pub fn iter_1000(b: &mut Bencher) {
 337         bench_iter(b, 1000);
 338     }
 339
 340     #[bench]
 341     pub fn iter_100000(b: &mut Bencher) {
 342         bench_iter(b, 100000);
 343     }
 344 }