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::{self, Excluded, Included, Unbounded};
13 use std::collections::btree_map::Entry::{Occupied, Vacant};
16 use std::iter::FromIterator;
17 use super::DeterministicRng;
20 fn test_basic_large() {
21 let mut map = BTreeMap::new();
23 assert_eq!(map.len(), 0);
26 assert_eq!(map.insert(i, 10 * i), None);
27 assert_eq!(map.len(), i + 1);
31 assert_eq!(map.get(&i).unwrap(), &(i * 10));
34 for i in size..size * 2 {
35 assert_eq!(map.get(&i), None);
39 assert_eq!(map.insert(i, 100 * i), Some(10 * i));
40 assert_eq!(map.len(), size);
44 assert_eq!(map.get(&i).unwrap(), &(i * 100));
47 for i in 0..size / 2 {
48 assert_eq!(map.remove(&(i * 2)), Some(i * 200));
49 assert_eq!(map.len(), size - i - 1);
52 for i in 0..size / 2 {
53 assert_eq!(map.get(&(2 * i)), None);
54 assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100));
57 for i in 0..size / 2 {
58 assert_eq!(map.remove(&(2 * i)), None);
59 assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
60 assert_eq!(map.len(), size / 2 - i - 1);
65 fn test_basic_small() {
66 let mut map = BTreeMap::new();
67 assert_eq!(map.remove(&1), None);
68 assert_eq!(map.get(&1), None);
69 assert_eq!(map.insert(1, 1), None);
70 assert_eq!(map.get(&1), Some(&1));
71 assert_eq!(map.insert(1, 2), Some(1));
72 assert_eq!(map.get(&1), Some(&2));
73 assert_eq!(map.insert(2, 4), None);
74 assert_eq!(map.get(&2), Some(&4));
75 assert_eq!(map.remove(&1), Some(2));
76 assert_eq!(map.remove(&2), Some(4));
77 assert_eq!(map.remove(&1), None);
85 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
87 fn test<T>(size: usize, mut iter: T)
88 where T: Iterator<Item = (usize, usize)>
91 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
92 assert_eq!(iter.next().unwrap(), (i, i));
94 assert_eq!(iter.size_hint(), (0, Some(0)));
95 assert_eq!(iter.next(), None);
97 test(size, map.iter().map(|(&k, &v)| (k, v)));
98 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
99 test(size, map.into_iter());
107 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
109 fn test<T>(size: usize, mut iter: T)
110 where T: Iterator<Item = (usize, usize)>
113 assert_eq!(iter.size_hint(), (size - i, Some(size - i)));
114 assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1));
116 assert_eq!(iter.size_hint(), (0, Some(0)));
117 assert_eq!(iter.next(), None);
119 test(size, map.iter().rev().map(|(&k, &v)| (k, v)));
120 test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v)));
121 test(size, map.into_iter().rev());
125 fn test_values_mut() {
126 let mut a = BTreeMap::new();
127 a.insert(1, String::from("hello"));
128 a.insert(2, String::from("goodbye"));
130 for value in a.values_mut() {
134 let values: Vec<String> = a.values().cloned().collect();
135 assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]);
139 fn test_iter_mixed() {
143 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
145 fn test<T>(size: usize, mut iter: T)
146 where T: Iterator<Item = (usize, usize)> + DoubleEndedIterator
148 for i in 0..size / 4 {
149 assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2)));
150 assert_eq!(iter.next().unwrap(), (i, i));
151 assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1));
153 for i in size / 4..size * 3 / 4 {
154 assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i)));
155 assert_eq!(iter.next().unwrap(), (i, i));
157 assert_eq!(iter.size_hint(), (0, Some(0)));
158 assert_eq!(iter.next(), None);
160 test(size, map.iter().map(|(&k, &v)| (k, v)));
161 test(size, map.iter_mut().map(|(&k, &mut v)| (k, v)));
162 test(size, map.into_iter());
166 fn test_range_small() {
170 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
173 for ((&k, &v), i) in map.range(2..).zip(2..size) {
178 assert_eq!(j, size - 2);
182 fn test_range_1000() {
184 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
186 fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) {
187 let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v));
188 let mut pairs = (0..size).map(|i| (i, i));
190 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
191 assert_eq!(kv, pair);
193 assert_eq!(kvs.next(), None);
194 assert_eq!(pairs.next(), None);
196 test(&map, size, Included(&0), Excluded(&size));
197 test(&map, size, Unbounded, Excluded(&size));
198 test(&map, size, Included(&0), Included(&(size - 1)));
199 test(&map, size, Unbounded, Included(&(size - 1)));
200 test(&map, size, Included(&0), Unbounded);
201 test(&map, size, Unbounded, Unbounded);
205 fn test_range_borrowed_key() {
206 let mut map = BTreeMap::new();
207 map.insert("aardvark".to_string(), 1);
208 map.insert("baboon".to_string(), 2);
209 map.insert("coyote".to_string(), 3);
210 map.insert("dingo".to_string(), 4);
211 // NOTE: would like to use simply "b".."d" here...
212 let mut iter = map.range::<str, _>((Included("b"),Excluded("d")));
213 assert_eq!(iter.next(), Some((&"baboon".to_string(), &2)));
214 assert_eq!(iter.next(), Some((&"coyote".to_string(), &3)));
215 assert_eq!(iter.next(), None);
221 let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
225 let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v));
226 let mut pairs = (i..j + 1).map(|i| (i, i));
228 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
229 assert_eq!(kv, pair);
231 assert_eq!(kvs.next(), None);
232 assert_eq!(pairs.next(), None);
238 fn test_range_mut() {
240 let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
244 let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v));
245 let mut pairs = (i..j + 1).map(|i| (i, i));
247 for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) {
248 assert_eq!(kv, pair);
250 assert_eq!(kvs.next(), None);
251 assert_eq!(pairs.next(), None);
258 // make sure these compile -- using the Borrow trait
260 let mut map = BTreeMap::new();
261 map.insert("0".to_string(), 1);
262 assert_eq!(map["0"], 1);
266 let mut map = BTreeMap::new();
267 map.insert(Box::new(0), 1);
268 assert_eq!(map[&0], 1);
272 let mut map = BTreeMap::new();
273 map.insert(Box::new([0, 1]) as Box<[i32]>, 1);
274 assert_eq!(map[&[0, 1][..]], 1);
278 let mut map = BTreeMap::new();
279 map.insert(Rc::new(0), 1);
280 assert_eq!(map[&0], 1);
286 let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
288 let mut map: BTreeMap<_, _> = xs.iter().cloned().collect();
290 // Existing key (insert)
292 Vacant(_) => unreachable!(),
293 Occupied(mut view) => {
294 assert_eq!(view.get(), &10);
295 assert_eq!(view.insert(100), 10);
298 assert_eq!(map.get(&1).unwrap(), &100);
299 assert_eq!(map.len(), 6);
302 // Existing key (update)
304 Vacant(_) => unreachable!(),
305 Occupied(mut view) => {
306 let v = view.get_mut();
310 assert_eq!(map.get(&2).unwrap(), &200);
311 assert_eq!(map.len(), 6);
313 // Existing key (take)
315 Vacant(_) => unreachable!(),
317 assert_eq!(view.remove(), 30);
320 assert_eq!(map.get(&3), None);
321 assert_eq!(map.len(), 5);
324 // Inexistent key (insert)
325 match map.entry(10) {
326 Occupied(_) => unreachable!(),
328 assert_eq!(*view.insert(1000), 1000);
331 assert_eq!(map.get(&10).unwrap(), &1000);
332 assert_eq!(map.len(), 6);
336 fn test_extend_ref() {
337 let mut a = BTreeMap::new();
339 let mut b = BTreeMap::new();
341 b.insert(3, "three");
345 assert_eq!(a.len(), 3);
346 assert_eq!(a[&1], "one");
347 assert_eq!(a[&2], "two");
348 assert_eq!(a[&3], "three");
353 let mut m = BTreeMap::new();
354 assert_eq!(m.len(), 0);
356 assert_eq!(m.insert((), ()), None);
357 assert_eq!(m.len(), 1);
359 assert_eq!(m.insert((), ()), Some(()));
360 assert_eq!(m.len(), 1);
361 assert_eq!(m.iter().count(), 1);
364 assert_eq!(m.len(), 0);
370 assert_eq!(m.len(), 1);
371 assert_eq!(m.iter().count(), 1);
374 // This test's only purpose is to ensure that zero-sized keys with nonsensical orderings
375 // do not cause segfaults when used with zero-sized values. All other map behavior is
379 use std::cmp::Ordering;
383 impl PartialEq for Bad {
384 fn eq(&self, _: &Self) -> bool {
391 impl PartialOrd for Bad {
392 fn partial_cmp(&self, _: &Self) -> Option<Ordering> {
398 fn cmp(&self, _: &Self) -> Ordering {
403 let mut m = BTreeMap::new();
412 let mut map = BTreeMap::new();
414 assert_eq!(map.len(), 0);
417 assert_eq!(map.insert(i, 10 * i), None);
418 assert_eq!(map.len(), i + 1);
419 assert_eq!(map, map.clone());
423 assert_eq!(map.insert(i, 100 * i), Some(10 * i));
424 assert_eq!(map.len(), size);
425 assert_eq!(map, map.clone());
428 for i in 0..size / 2 {
429 assert_eq!(map.remove(&(i * 2)), Some(i * 200));
430 assert_eq!(map.len(), size - i - 1);
431 assert_eq!(map, map.clone());
434 for i in 0..size / 2 {
435 assert_eq!(map.remove(&(2 * i)), None);
436 assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100));
437 assert_eq!(map.len(), size / 2 - i - 1);
438 assert_eq!(map, map.clone());
445 use std::collections::btree_map::{Iter, IntoIter, Range, Keys, Values};
447 fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> {
450 fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> {
453 fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> {
456 fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> {
459 fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> {
462 fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> {
465 fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> {
468 fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> {
471 fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> {
474 fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> {
480 fn test_occupied_entry_key() {
481 let mut a = BTreeMap::new();
482 let key = "hello there";
483 let value = "value goes here";
484 assert!(a.is_empty());
485 a.insert(key.clone(), value.clone());
486 assert_eq!(a.len(), 1);
487 assert_eq!(a[key], value);
489 match a.entry(key.clone()) {
490 Vacant(_) => panic!(),
491 Occupied(e) => assert_eq!(key, *e.key()),
493 assert_eq!(a.len(), 1);
494 assert_eq!(a[key], value);
498 fn test_vacant_entry_key() {
499 let mut a = BTreeMap::new();
500 let key = "hello there";
501 let value = "value goes here";
503 assert!(a.is_empty());
504 match a.entry(key.clone()) {
505 Occupied(_) => panic!(),
507 assert_eq!(key, *e.key());
508 e.insert(value.clone());
511 assert_eq!(a.len(), 1);
512 assert_eq!(a[key], value);
515 macro_rules! create_append_test {
516 ($name:ident, $len:expr) => {
519 let mut a = BTreeMap::new();
524 let mut b = BTreeMap::new();
531 assert_eq!(a.len(), $len);
532 assert_eq!(b.len(), 0);
536 assert_eq!(a[&i], i);
538 assert_eq!(a[&i], 2*i);
542 assert_eq!(a.remove(&($len-1)), Some(2*($len-1)));
543 assert_eq!(a.insert($len-1, 20), None);
548 // These are mostly for testing the algorithm that "fixes" the right edge after insertion.
550 create_append_test!(test_append_9, 9);
551 // Two leafs that don't need fixing.
552 create_append_test!(test_append_17, 17);
553 // Two leafs where the second one ends up underfull and needs stealing at the end.
554 create_append_test!(test_append_14, 14);
555 // Two leafs where the second one ends up empty because the insertion finished at the root.
556 create_append_test!(test_append_12, 12);
557 // Three levels; insertion finished at the root.
558 create_append_test!(test_append_144, 144);
559 // Three levels; insertion finished at leaf while there is an empty node on the second level.
560 create_append_test!(test_append_145, 145);
561 // Tests for several randomly chosen sizes.
562 create_append_test!(test_append_170, 170);
563 create_append_test!(test_append_181, 181);
564 create_append_test!(test_append_239, 239);
565 create_append_test!(test_append_1700, 1700);
567 fn rand_data(len: usize) -> Vec<(u32, u32)> {
568 let mut rng = DeterministicRng::new();
569 Vec::from_iter((0..len).map(|_| (rng.next(), rng.next())))
573 fn test_split_off_empty_right() {
574 let mut data = rand_data(173);
576 let mut map = BTreeMap::from_iter(data.clone());
577 let right = map.split_off(&(data.iter().max().unwrap().0 + 1));
580 assert!(map.into_iter().eq(data));
581 assert!(right.into_iter().eq(None));
585 fn test_split_off_empty_left() {
586 let mut data = rand_data(314);
588 let mut map = BTreeMap::from_iter(data.clone());
589 let right = map.split_off(&data.iter().min().unwrap().0);
592 assert!(map.into_iter().eq(None));
593 assert!(right.into_iter().eq(data));
597 fn test_split_off_large_random_sorted() {
598 let mut data = rand_data(1529);
599 // special case with maximum height.
602 let mut map = BTreeMap::from_iter(data.clone());
603 let key = data[data.len() / 2].0;
604 let right = map.split_off(&key);
606 assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key)));
607 assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key)));