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}
;
17 fn test_basic_large() {
18 let mut map
= BTreeMap
::new();
20 assert_eq
!(map
.len(), 0);
23 assert_eq
!(map
.insert(i
, 10*i
), None
);
24 assert_eq
!(map
.len(), i
+ 1);
28 assert_eq
!(map
.get(&i
).unwrap(), &(i
*10));
31 for i
in size
..size
*2 {
32 assert_eq
!(map
.get(&i
), None
);
36 assert_eq
!(map
.insert(i
, 100*i
), Some(10*i
));
37 assert_eq
!(map
.len(), size
);
41 assert_eq
!(map
.get(&i
).unwrap(), &(i
*100));
45 assert_eq
!(map
.remove(&(i
*2)), Some(i
*200));
46 assert_eq
!(map
.len(), size
- i
- 1);
50 assert_eq
!(map
.get(&(2*i
)), None
);
51 assert_eq
!(map
.get(&(2*i
+1)).unwrap(), &(i
*200 + 100));
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);
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
);
82 let mut map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
84 fn test
<T
>(size
: usize, mut iter
: T
) where T
: Iterator
<Item
=(usize, usize)> {
86 assert_eq
!(iter
.size_hint(), (size
- i
, Some(size
- i
)));
87 assert_eq
!(iter
.next().unwrap(), (i
, i
));
89 assert_eq
!(iter
.size_hint(), (0, Some(0)));
90 assert_eq
!(iter
.next(), None
);
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());
102 let mut map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
104 fn test
<T
>(size
: usize, mut iter
: T
) where T
: Iterator
<Item
=(usize, usize)> {
106 assert_eq
!(iter
.size_hint(), (size
- i
, Some(size
- i
)));
107 assert_eq
!(iter
.next().unwrap(), (size
- i
- 1, size
- i
- 1));
109 assert_eq
!(iter
.size_hint(), (0, Some(0)));
110 assert_eq
!(iter
.next(), None
);
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());
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"));
123 for value
in a
.values_mut() {
127 let values
: Vec
<String
> = a
.values().cloned().collect();
128 assert_eq
!(values
, [String
::from("hello!"),
129 String
::from("goodbye!")]);
133 fn test_iter_mixed() {
137 let mut map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
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));
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
));
150 assert_eq
!(iter
.size_hint(), (0, Some(0)));
151 assert_eq
!(iter
.next(), None
);
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());
159 fn test_range_small() {
163 let map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
166 for ((&k
, &v
), i
) in map
.range(Included(&2), Unbounded
).zip(2..size
) {
171 assert_eq
!(j
, size
- 2);
175 fn test_range_1000() {
177 let map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
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
));
183 for (kv
, pair
) in kvs
.by_ref().zip(pairs
.by_ref()) {
184 assert_eq
!(kv
, pair
);
186 assert_eq
!(kvs
.next(), None
);
187 assert_eq
!(pairs
.next(), None
);
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
);
200 let map
: BTreeMap
<_
, _
> = (0..size
).map(|i
| (i
, i
)).collect();
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
));
207 for (kv
, pair
) in kvs
.by_ref().zip(pairs
.by_ref()) {
208 assert_eq
!(kv
, pair
);
210 assert_eq
!(kvs
.next(), None
);
211 assert_eq
!(pairs
.next(), None
);
218 // make sure these compile -- using the Borrow trait
220 let mut map
= BTreeMap
::new();
221 map
.insert("0".to_string(), 1);
222 assert_eq
!(map
["0"], 1);
226 let mut map
= BTreeMap
::new();
227 map
.insert(Box
::new(0), 1);
228 assert_eq
!(map
[&0], 1);
232 let mut map
= BTreeMap
::new();
233 map
.insert(Box
::new([0, 1]) as Box
<[i32]>, 1);
234 assert_eq
!(map
[&[0, 1][..]], 1);
238 let mut map
= BTreeMap
::new();
239 map
.insert(Rc
::new(0), 1);
240 assert_eq
!(map
[&0], 1);
246 let xs
= [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
248 let mut map
: BTreeMap
<_
, _
> = xs
.iter().cloned().collect();
250 // Existing key (insert)
252 Vacant(_
) => unreachable
!(),
253 Occupied(mut view
) => {
254 assert_eq
!(view
.get(), &10);
255 assert_eq
!(view
.insert(100), 10);
258 assert_eq
!(map
.get(&1).unwrap(), &100);
259 assert_eq
!(map
.len(), 6);
262 // Existing key (update)
264 Vacant(_
) => unreachable
!(),
265 Occupied(mut view
) => {
266 let v
= view
.get_mut();
270 assert_eq
!(map
.get(&2).unwrap(), &200);
271 assert_eq
!(map
.len(), 6);
273 // Existing key (take)
275 Vacant(_
) => unreachable
!(),
277 assert_eq
!(view
.remove(), 30);
280 assert_eq
!(map
.get(&3), None
);
281 assert_eq
!(map
.len(), 5);
284 // Inexistent key (insert)
285 match map
.entry(10) {
286 Occupied(_
) => unreachable
!(),
288 assert_eq
!(*view
.insert(1000), 1000);
291 assert_eq
!(map
.get(&10).unwrap(), &1000);
292 assert_eq
!(map
.len(), 6);
296 fn test_extend_ref() {
297 let mut a
= BTreeMap
::new();
299 let mut b
= BTreeMap
::new();
301 b
.insert(3, "three");
305 assert_eq
!(a
.len(), 3);
306 assert_eq
!(a
[&1], "one");
307 assert_eq
!(a
[&2], "two");
308 assert_eq
!(a
[&3], "three");
313 let mut m
= BTreeMap
::new();
314 assert_eq
!(m
.len(), 0);
316 assert_eq
!(m
.insert((), ()), None
);
317 assert_eq
!(m
.len(), 1);
319 assert_eq
!(m
.insert((), ()), Some(()));
320 assert_eq
!(m
.len(), 1);
321 assert_eq
!(m
.iter().count(), 1);
324 assert_eq
!(m
.len(), 0);
330 assert_eq
!(m
.len(), 1);
331 assert_eq
!(m
.iter().count(), 1);
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
339 use std
::cmp
::Ordering
;
343 impl PartialEq
for Bad
{
344 fn eq(&self, _
: &Self) -> bool { false }
349 impl PartialOrd
for Bad
{
350 fn partial_cmp(&self, _
: &Self) -> Option
<Ordering
> { Some(Ordering::Less) }
354 fn cmp(&self, _
: &Self) -> Ordering { Ordering::Less }
357 let mut m
= BTreeMap
::new();
366 let mut map
= BTreeMap
::new();
368 assert_eq
!(map
.len(), 0);
371 assert_eq
!(map
.insert(i
, 10*i
), None
);
372 assert_eq
!(map
.len(), i
+ 1);
373 assert_eq
!(map
, map
.clone());
377 assert_eq
!(map
.insert(i
, 100*i
), Some(10*i
));
378 assert_eq
!(map
.len(), size
);
379 assert_eq
!(map
, map
.clone());
383 assert_eq
!(map
.remove(&(i
*2)), Some(i
*200));
384 assert_eq
!(map
.len(), size
- i
- 1);
385 assert_eq
!(map
, map
.clone());
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());
399 use std
::collections
::btree_map
::{Iter, IntoIter, Range, Keys, Values}
;
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 }
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
);
423 match a
.entry(key
.clone()) {
424 Vacant(_
) => panic
!(),
425 Occupied(e
) => assert_eq
!(key
, *e
.key()),
427 assert_eq
!(a
.len(), 1);
428 assert_eq
!(a
[key
], value
);
432 fn test_vacant_entry_key() {
433 let mut a
= BTreeMap
::new();
434 let key
= "hello there";
435 let value
= "value goes here";
437 assert
!(a
.is_empty());
438 match a
.entry(key
.clone()) {
439 Occupied(_
) => panic
!(),
441 assert_eq
!(key
, *e
.key());
442 e
.insert(value
.clone());
445 assert_eq
!(a
.len(), 1);
446 assert_eq
!(a
[key
], value
);
450 use std
::collections
::BTreeMap
;
451 use std
::__rand
::{Rng, thread_rng}
;
453 use test
::{Bencher, black_box}
;
455 map_insert_rand_bench
!{insert_rand_100, 100, BTreeMap}
456 map_insert_rand_bench
!{insert_rand_10_000, 10_000, BTreeMap}
458 map_insert_seq_bench
!{insert_seq_100, 100, BTreeMap}
459 map_insert_seq_bench
!{insert_seq_10_000, 10_000, BTreeMap}
461 map_find_rand_bench
!{find_rand_100, 100, BTreeMap}
462 map_find_rand_bench
!{find_rand_10_000, 10_000, BTreeMap}
464 map_find_seq_bench
!{find_seq_100, 100, BTreeMap}
465 map_find_seq_bench
!{find_seq_10_000, 10_000, BTreeMap}
467 fn bench_iter(b
: &mut Bencher
, size
: i32) {
468 let mut map
= BTreeMap
::<i32, i32>::new();
469 let mut rng
= thread_rng();
472 map
.insert(rng
.gen(), rng
.gen());
483 pub fn iter_20(b
: &mut Bencher
) {
488 pub fn iter_1000(b
: &mut Bencher
) {
493 pub fn iter_100000(b
: &mut Bencher
) {
494 bench_iter(b
, 100000);