]>
Commit | Line | Data |
---|---|---|
c34b1796 AL |
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}; | |
d9579d0f | 14 | use std::rc::Rc; |
c34b1796 AL |
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 | ||
54a0048b SL |
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 | ||
c34b1796 AL |
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)); | |
9cc50fc6 | 205 | let mut pairs = (i..j+1).map(|i| (i, i)); |
c34b1796 AL |
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 | ||
d9579d0f AL |
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 | ||
c34b1796 AL |
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 | ||
62682a34 SL |
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 | ||
b039eaaf SL |
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 | ||
9cc50fc6 SL |
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] | |
7453a54e | 397 | #[allow(dead_code)] |
9cc50fc6 SL |
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 | ||
54a0048b SL |
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 | ||
c34b1796 AL |
449 | mod bench { |
450 | use std::collections::BTreeMap; | |
9346a6ac | 451 | use std::__rand::{Rng, thread_rng}; |
c34b1796 AL |
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(); | |
9346a6ac | 469 | let mut rng = thread_rng(); |
c34b1796 AL |
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 | } |