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.
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.
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
;
18 fn test_basic_large() {
19 let mut map
= BTreeMap
::new();
21 assert_eq
!(map
.len(), 0);
24 assert_eq
!(map
.insert(i
, 10*i
), None
);
25 assert_eq
!(map
.len(), i
+ 1);
29 assert_eq
!(map
.get(&i
).unwrap(), &(i
*10));
32 for i
in size
..size
*2 {
33 assert_eq
!(map
.get(&i
), None
);
37 assert_eq
!(map
.insert(i
, 100*i
), Some(10*i
));
38 assert_eq
!(map
.len(), size
);
42 assert_eq
!(map
.get(&i
).unwrap(), &(i
*100));
46 assert_eq
!(map
.remove(&(i
*2)), Some(i
*200));
47 assert_eq
!(map
.len(), size
- i
- 1);
51 assert_eq
!(map
.get(&(2*i
)), None
);
52 assert_eq
!(map
.get(&(2*i
+1)).unwrap(), &(i
*200 + 100));
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);
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
);
83 let mut map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
85 fn test
<T
>(size
: usize, mut iter
: T
) where T
: Iterator
<Item
=(usize, usize)> {
87 assert_eq
!(iter
.size_hint(), (size
- i
, Some(size
- i
)));
88 assert_eq
!(iter
.next().unwrap(), (i
, i
));
90 assert_eq
!(iter
.size_hint(), (0, Some(0)));
91 assert_eq
!(iter
.next(), None
);
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());
103 let mut map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
105 fn test
<T
>(size
: usize, mut iter
: T
) where T
: Iterator
<Item
=(usize, usize)> {
107 assert_eq
!(iter
.size_hint(), (size
- i
, Some(size
- i
)));
108 assert_eq
!(iter
.next().unwrap(), (size
- i
- 1, size
- i
- 1));
110 assert_eq
!(iter
.size_hint(), (0, Some(0)));
111 assert_eq
!(iter
.next(), None
);
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());
119 fn test_iter_mixed() {
123 let mut map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
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));
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
));
136 assert_eq
!(iter
.size_hint(), (0, Some(0)));
137 assert_eq
!(iter
.next(), None
);
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());
145 fn test_range_small() {
149 let map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
152 for ((&k
, &v
), i
) in map
.range(Included(&2), Unbounded
).zip(2..size
) {
157 assert_eq
!(j
, size
- 2);
161 fn test_range_1000() {
163 let map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
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
));
169 for (kv
, pair
) in kvs
.by_ref().zip(pairs
.by_ref()) {
170 assert_eq
!(kv
, pair
);
172 assert_eq
!(kvs
.next(), None
);
173 assert_eq
!(pairs
.next(), None
);
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
);
186 let map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
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
));
193 for (kv
, pair
) in kvs
.by_ref().zip(pairs
.by_ref()) {
194 assert_eq
!(kv
, pair
);
196 assert_eq
!(kvs
.next(), None
);
197 assert_eq
!(pairs
.next(), None
);
204 // make sure these compile -- using the Borrow trait
206 let mut map
= BTreeMap
::new();
207 map
.insert("0".to_string(), 1);
208 assert_eq
!(map
["0"], 1);
212 let mut map
= BTreeMap
::new();
213 map
.insert(Box
::new(0), 1);
214 assert_eq
!(map
[&0], 1);
218 let mut map
= BTreeMap
::new();
219 map
.insert(Box
::new([0, 1]) as Box
<[i32]>, 1);
220 assert_eq
!(map
[&[0, 1][..]], 1);
224 let mut map
= BTreeMap
::new();
225 map
.insert(Rc
::new(0), 1);
226 assert_eq
!(map
[&0], 1);
232 let xs
= [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
234 let mut map
: BTreeMap
<_
, _
> = xs
.iter().cloned().collect();
236 // Existing key (insert)
238 Vacant(_
) => unreachable
!(),
239 Occupied(mut view
) => {
240 assert_eq
!(view
.get(), &10);
241 assert_eq
!(view
.insert(100), 10);
244 assert_eq
!(map
.get(&1).unwrap(), &100);
245 assert_eq
!(map
.len(), 6);
248 // Existing key (update)
250 Vacant(_
) => unreachable
!(),
251 Occupied(mut view
) => {
252 let v
= view
.get_mut();
256 assert_eq
!(map
.get(&2).unwrap(), &200);
257 assert_eq
!(map
.len(), 6);
259 // Existing key (take)
261 Vacant(_
) => unreachable
!(),
263 assert_eq
!(view
.remove(), 30);
266 assert_eq
!(map
.get(&3), None
);
267 assert_eq
!(map
.len(), 5);
270 // Inexistent key (insert)
271 match map
.entry(10) {
272 Occupied(_
) => unreachable
!(),
274 assert_eq
!(*view
.insert(1000), 1000);
277 assert_eq
!(map
.get(&10).unwrap(), &1000);
278 assert_eq
!(map
.len(), 6);
282 fn test_extend_ref() {
283 let mut a
= BTreeMap
::new();
285 let mut b
= BTreeMap
::new();
287 b
.insert(3, "three");
291 assert_eq
!(a
.len(), 3);
292 assert_eq
!(a
[&1], "one");
293 assert_eq
!(a
[&2], "two");
294 assert_eq
!(a
[&3], "three");
298 use std
::collections
::BTreeMap
;
299 use std
::__rand
::{Rng, thread_rng}
;
301 use test
::{Bencher, black_box}
;
303 map_insert_rand_bench
!{insert_rand_100, 100, BTreeMap}
304 map_insert_rand_bench
!{insert_rand_10_000, 10_000, BTreeMap}
306 map_insert_seq_bench
!{insert_seq_100, 100, BTreeMap}
307 map_insert_seq_bench
!{insert_seq_10_000, 10_000, BTreeMap}
309 map_find_rand_bench
!{find_rand_100, 100, BTreeMap}
310 map_find_rand_bench
!{find_rand_10_000, 10_000, BTreeMap}
312 map_find_seq_bench
!{find_seq_100, 100, BTreeMap}
313 map_find_seq_bench
!{find_seq_10_000, 10_000, BTreeMap}
315 fn bench_iter(b
: &mut Bencher
, size
: i32) {
316 let mut map
= BTreeMap
::<i32, i32>::new();
317 let mut rng
= thread_rng();
320 map
.insert(rng
.gen(), rng
.gen());
331 pub fn iter_20(b
: &mut Bencher
) {
336 pub fn iter_1000(b
: &mut Bencher
) {
341 pub fn iter_100000(b
: &mut Bencher
) {
342 bench_iter(b
, 100000);