diff options
Diffstat (limited to 'library/alloc/tests/btree')
| -rw-r--r-- | library/alloc/tests/btree/map.rs | 1463 | ||||
| -rw-r--r-- | library/alloc/tests/btree/mod.rs | 27 | ||||
| -rw-r--r-- | library/alloc/tests/btree/set.rs | 666 |
3 files changed, 2156 insertions, 0 deletions
diff --git a/library/alloc/tests/btree/map.rs b/library/alloc/tests/btree/map.rs new file mode 100644 index 00000000000..f9f81716e35 --- /dev/null +++ b/library/alloc/tests/btree/map.rs @@ -0,0 +1,1463 @@ +use std::collections::btree_map::Entry::{Occupied, Vacant}; +use std::collections::BTreeMap; +use std::convert::TryFrom; +use std::fmt::Debug; +use std::iter::FromIterator; +use std::mem; +use std::ops::Bound::{self, Excluded, Included, Unbounded}; +use std::ops::RangeBounds; +use std::panic::{catch_unwind, AssertUnwindSafe}; +use std::rc::Rc; +use std::sync::atomic::{AtomicUsize, Ordering}; + +use super::DeterministicRng; + +// Value of node::CAPACITY, thus capacity of a tree with a single level, +// i.e. a tree who's root is a leaf node at height 0. +const NODE_CAPACITY: usize = 11; + +// Minimum number of elements to insert in order to guarantee a tree with 2 levels, +// i.e. a tree who's root is an internal node at height 1, with edges to leaf nodes. +// It's not the minimum size: removing an element from such a tree does not always reduce height. +const MIN_INSERTS_HEIGHT_1: usize = NODE_CAPACITY + 1; + +// Minimum number of elements to insert in order to guarantee a tree with 3 levels, +// i.e. a tree who's root is an internal node at height 2, with edges to more internal nodes. +// It's not the minimum size: removing an element from such a tree does not always reduce height. +const MIN_INSERTS_HEIGHT_2: usize = NODE_CAPACITY + (NODE_CAPACITY + 1) * NODE_CAPACITY + 1; + +// Gather all references from a mutable iterator and make sure Miri notices if +// using them is dangerous. +fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) { + // Gather all those references. + let mut refs: Vec<&mut T> = iter.collect(); + // Use them all. Twice, to be sure we got all interleavings. + for r in refs.iter_mut() { + mem::swap(dummy, r); + } + for r in refs { + mem::swap(dummy, r); + } +} + +#[test] +fn test_basic_large() { + let mut map = BTreeMap::new(); + // Miri is too slow + let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 } else { 10000 }; + assert_eq!(map.len(), 0); + + for i in 0..size { + assert_eq!(map.insert(i, 10 * i), None); + assert_eq!(map.len(), i + 1); + } + + assert_eq!(map.first_key_value(), Some((&0, &0))); + assert_eq!(map.last_key_value(), Some((&(size - 1), &(10 * (size - 1))))); + assert_eq!(map.first_entry().unwrap().key(), &0); + assert_eq!(map.last_entry().unwrap().key(), &(size - 1)); + + for i in 0..size { + assert_eq!(map.get(&i).unwrap(), &(i * 10)); + } + + for i in size..size * 2 { + assert_eq!(map.get(&i), None); + } + + for i in 0..size { + assert_eq!(map.insert(i, 100 * i), Some(10 * i)); + assert_eq!(map.len(), size); + } + + for i in 0..size { + assert_eq!(map.get(&i).unwrap(), &(i * 100)); + } + + for i in 0..size / 2 { + assert_eq!(map.remove(&(i * 2)), Some(i * 200)); + assert_eq!(map.len(), size - i - 1); + } + + for i in 0..size / 2 { + assert_eq!(map.get(&(2 * i)), None); + assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100)); + } + + for i in 0..size / 2 { + assert_eq!(map.remove(&(2 * i)), None); + assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100)); + assert_eq!(map.len(), size / 2 - i - 1); + } +} + +#[test] +fn test_basic_small() { + let mut map = BTreeMap::new(); + // Empty, root is absent (None): + assert_eq!(map.remove(&1), None); + assert_eq!(map.len(), 0); + assert_eq!(map.get(&1), None); + assert_eq!(map.get_mut(&1), None); + assert_eq!(map.first_key_value(), None); + assert_eq!(map.last_key_value(), None); + assert_eq!(map.keys().count(), 0); + assert_eq!(map.values().count(), 0); + assert_eq!(map.range(..).next(), None); + assert_eq!(map.range(..1).next(), None); + assert_eq!(map.range(1..).next(), None); + assert_eq!(map.range(1..=1).next(), None); + assert_eq!(map.range(1..2).next(), None); + assert_eq!(map.insert(1, 1), None); + + // 1 key-value pair: + assert_eq!(map.len(), 1); + assert_eq!(map.get(&1), Some(&1)); + assert_eq!(map.get_mut(&1), Some(&mut 1)); + assert_eq!(map.first_key_value(), Some((&1, &1))); + assert_eq!(map.last_key_value(), Some((&1, &1))); + assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]); + assert_eq!(map.values().collect::<Vec<_>>(), vec![&1]); + assert_eq!(map.insert(1, 2), Some(1)); + assert_eq!(map.len(), 1); + assert_eq!(map.get(&1), Some(&2)); + assert_eq!(map.get_mut(&1), Some(&mut 2)); + assert_eq!(map.first_key_value(), Some((&1, &2))); + assert_eq!(map.last_key_value(), Some((&1, &2))); + assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]); + assert_eq!(map.values().collect::<Vec<_>>(), vec![&2]); + assert_eq!(map.insert(2, 4), None); + + // 2 key-value pairs: + assert_eq!(map.len(), 2); + assert_eq!(map.get(&2), Some(&4)); + assert_eq!(map.get_mut(&2), Some(&mut 4)); + assert_eq!(map.first_key_value(), Some((&1, &2))); + assert_eq!(map.last_key_value(), Some((&2, &4))); + assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1, &2]); + assert_eq!(map.values().collect::<Vec<_>>(), vec![&2, &4]); + assert_eq!(map.remove(&1), Some(2)); + + // 1 key-value pair: + assert_eq!(map.len(), 1); + assert_eq!(map.get(&1), None); + assert_eq!(map.get_mut(&1), None); + assert_eq!(map.get(&2), Some(&4)); + assert_eq!(map.get_mut(&2), Some(&mut 4)); + assert_eq!(map.first_key_value(), Some((&2, &4))); + assert_eq!(map.last_key_value(), Some((&2, &4))); + assert_eq!(map.keys().collect::<Vec<_>>(), vec![&2]); + assert_eq!(map.values().collect::<Vec<_>>(), vec![&4]); + assert_eq!(map.remove(&2), Some(4)); + + // Empty but root is owned (Some(...)): + assert_eq!(map.len(), 0); + assert_eq!(map.get(&1), None); + assert_eq!(map.get_mut(&1), None); + assert_eq!(map.first_key_value(), None); + assert_eq!(map.last_key_value(), None); + assert_eq!(map.keys().count(), 0); + assert_eq!(map.values().count(), 0); + assert_eq!(map.range(..).next(), None); + assert_eq!(map.range(..1).next(), None); + assert_eq!(map.range(1..).next(), None); + assert_eq!(map.range(1..=1).next(), None); + assert_eq!(map.range(1..2).next(), None); + assert_eq!(map.remove(&1), None); +} + +#[test] +fn test_iter() { + // Miri is too slow + let size = if cfg!(miri) { 200 } else { 10000 }; + + let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + fn test<T>(size: usize, mut iter: T) + where + T: Iterator<Item = (usize, usize)>, + { + for i in 0..size { + assert_eq!(iter.size_hint(), (size - i, Some(size - i))); + assert_eq!(iter.next().unwrap(), (i, i)); + } + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + } + test(size, map.iter().map(|(&k, &v)| (k, v))); + test(size, map.iter_mut().map(|(&k, &mut v)| (k, v))); + test(size, map.into_iter()); +} + +#[test] +fn test_iter_rev() { + // Miri is too slow + let size = if cfg!(miri) { 200 } else { 10000 }; + + let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + fn test<T>(size: usize, mut iter: T) + where + T: Iterator<Item = (usize, usize)>, + { + for i in 0..size { + assert_eq!(iter.size_hint(), (size - i, Some(size - i))); + assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1)); + } + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + } + test(size, map.iter().rev().map(|(&k, &v)| (k, v))); + test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v))); + test(size, map.into_iter().rev()); +} + +/// Specifically tests iter_mut's ability to mutate the value of pairs in-line +fn do_test_iter_mut_mutation<T>(size: usize) +where + T: Copy + Debug + Ord + TryFrom<usize>, + <T as std::convert::TryFrom<usize>>::Error: std::fmt::Debug, +{ + let zero = T::try_from(0).unwrap(); + let mut map: BTreeMap<T, T> = (0..size).map(|i| (T::try_from(i).unwrap(), zero)).collect(); + + // Forward and backward iteration sees enough pairs (also tested elsewhere) + assert_eq!(map.iter_mut().count(), size); + assert_eq!(map.iter_mut().rev().count(), size); + + // Iterate forwards, trying to mutate to unique values + for (i, (k, v)) in map.iter_mut().enumerate() { + assert_eq!(*k, T::try_from(i).unwrap()); + assert_eq!(*v, zero); + *v = T::try_from(i + 1).unwrap(); + } + + // Iterate backwards, checking that mutations succeeded and trying to mutate again + for (i, (k, v)) in map.iter_mut().rev().enumerate() { + assert_eq!(*k, T::try_from(size - i - 1).unwrap()); + assert_eq!(*v, T::try_from(size - i).unwrap()); + *v = T::try_from(2 * size - i).unwrap(); + } + + // Check that backward mutations succeeded + for (i, (k, v)) in map.iter_mut().enumerate() { + assert_eq!(*k, T::try_from(i).unwrap()); + assert_eq!(*v, T::try_from(size + i + 1).unwrap()); + } +} + +#[derive(Clone, Copy, Debug, Eq, PartialEq, PartialOrd, Ord)] +#[repr(align(32))] +struct Align32(usize); + +impl TryFrom<usize> for Align32 { + type Error = (); + + fn try_from(s: usize) -> Result<Align32, ()> { + Ok(Align32(s)) + } +} + +#[test] +fn test_iter_mut_mutation() { + // Check many alignments and trees with roots at various heights. + do_test_iter_mut_mutation::<u8>(0); + do_test_iter_mut_mutation::<u8>(1); + do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<u8>(127); // not enough unique values to test MIN_INSERTS_HEIGHT_2 + do_test_iter_mut_mutation::<u16>(1); + do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_2); + do_test_iter_mut_mutation::<u32>(1); + do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_2); + do_test_iter_mut_mutation::<u64>(1); + do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_2); + do_test_iter_mut_mutation::<u128>(1); + do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_2); + do_test_iter_mut_mutation::<Align32>(1); + do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_1); + do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_2); +} + +#[test] +#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915> +fn test_values_mut() { + let mut a: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect(); + test_all_refs(&mut 13, a.values_mut()); +} + +#[test] +fn test_values_mut_mutation() { + let mut a = BTreeMap::new(); + a.insert(1, String::from("hello")); + a.insert(2, String::from("goodbye")); + + for value in a.values_mut() { + value.push_str("!"); + } + + let values: Vec<String> = a.values().cloned().collect(); + assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]); +} + +#[test] +#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915> +fn test_iter_entering_root_twice() { + let mut map: BTreeMap<_, _> = (0..2).map(|i| (i, i)).collect(); + let mut it = map.iter_mut(); + let front = it.next().unwrap(); + let back = it.next_back().unwrap(); + assert_eq!(front, (&0, &mut 0)); + assert_eq!(back, (&1, &mut 1)); + *front.1 = 24; + *back.1 = 42; + assert_eq!(front, (&0, &mut 24)); + assert_eq!(back, (&1, &mut 42)); +} + +#[test] +#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915> +fn test_iter_descending_to_same_node_twice() { + let mut map: BTreeMap<_, _> = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)).collect(); + let mut it = map.iter_mut(); + // Descend into first child. + let front = it.next().unwrap(); + // Descend into first child again, after running through second child. + while it.next_back().is_some() {} + // Check immutable access. + assert_eq!(front, (&0, &mut 0)); + // Perform mutable access. + *front.1 = 42; +} + +#[test] +fn test_iter_mixed() { + // Miri is too slow + let size = if cfg!(miri) { 200 } else { 10000 }; + + let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + fn test<T>(size: usize, mut iter: T) + where + T: Iterator<Item = (usize, usize)> + DoubleEndedIterator, + { + for i in 0..size / 4 { + assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2))); + assert_eq!(iter.next().unwrap(), (i, i)); + assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1)); + } + for i in size / 4..size * 3 / 4 { + assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i))); + assert_eq!(iter.next().unwrap(), (i, i)); + } + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + } + test(size, map.iter().map(|(&k, &v)| (k, v))); + test(size, map.iter_mut().map(|(&k, &mut v)| (k, v))); + test(size, map.into_iter()); +} + +#[test] +#[cfg_attr(miri, ignore)] // FIXME: fails in Miri <https://github.com/rust-lang/rust/issues/73915> +fn test_iter_min_max() { + let mut a = BTreeMap::new(); + assert_eq!(a.iter().min(), None); + assert_eq!(a.iter().max(), None); + assert_eq!(a.iter_mut().min(), None); + assert_eq!(a.iter_mut().max(), None); + assert_eq!(a.range(..).min(), None); + assert_eq!(a.range(..).max(), None); + assert_eq!(a.range_mut(..).min(), None); + assert_eq!(a.range_mut(..).max(), None); + assert_eq!(a.keys().min(), None); + assert_eq!(a.keys().max(), None); + assert_eq!(a.values().min(), None); + assert_eq!(a.values().max(), None); + assert_eq!(a.values_mut().min(), None); + assert_eq!(a.values_mut().max(), None); + a.insert(1, 42); + a.insert(2, 24); + assert_eq!(a.iter().min(), Some((&1, &42))); + assert_eq!(a.iter().max(), Some((&2, &24))); + assert_eq!(a.iter_mut().min(), Some((&1, &mut 42))); + assert_eq!(a.iter_mut().max(), Some((&2, &mut 24))); + assert_eq!(a.range(..).min(), Some((&1, &42))); + assert_eq!(a.range(..).max(), Some((&2, &24))); + assert_eq!(a.range_mut(..).min(), Some((&1, &mut 42))); + assert_eq!(a.range_mut(..).max(), Some((&2, &mut 24))); + assert_eq!(a.keys().min(), Some(&1)); + assert_eq!(a.keys().max(), Some(&2)); + assert_eq!(a.values().min(), Some(&24)); + assert_eq!(a.values().max(), Some(&42)); + assert_eq!(a.values_mut().min(), Some(&mut 24)); + assert_eq!(a.values_mut().max(), Some(&mut 42)); +} + +fn range_keys(map: &BTreeMap<i32, i32>, range: impl RangeBounds<i32>) -> Vec<i32> { + map.range(range) + .map(|(&k, &v)| { + assert_eq!(k, v); + k + }) + .collect() +} + +#[test] +fn test_range_small() { + let size = 4; + + let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect(); + let all: Vec<_> = (1..=size).collect(); + let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]); + + assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all); + assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all); + assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Included(0), Included(size))), all); + assert_eq!(range_keys(&map, (Included(0), Unbounded)), all); + assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Included(1), Included(size))), all); + assert_eq!(range_keys(&map, (Included(1), Unbounded)), all); + assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all); + assert_eq!(range_keys(&map, (Unbounded, Included(size))), all); + assert_eq!(range_keys(&map, ..), all); + + assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]); + assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]); + assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]); + assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first); + assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first); + assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first); + assert_eq!(range_keys(&map, (Included(0), Included(1))), first); + assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first); + assert_eq!(range_keys(&map, (Included(1), Included(1))), first); + assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first); + assert_eq!(range_keys(&map, (Unbounded, Included(1))), first); + assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last); + assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last); + assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last); + assert_eq!(range_keys(&map, (Included(size), Included(size))), last); + assert_eq!(range_keys(&map, (Included(size), Unbounded)), last); + assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]); + assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]); + + assert_eq!(range_keys(&map, ..3), vec![1, 2]); + assert_eq!(range_keys(&map, 3..), vec![3, 4]); + assert_eq!(range_keys(&map, 2..=3), vec![2, 3]); +} + +#[test] +fn test_range_height_1() { + // Tests tree with a root and 2 leaves. Depending on details we don't want or need + // to rely upon, the single key at the root will be 6 or 7. + + let map: BTreeMap<_, _> = (1..=MIN_INSERTS_HEIGHT_1 as i32).map(|i| (i, i)).collect(); + for &root in &[6, 7] { + assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]); + assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]); + assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]); + assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]); + + assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]); + assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]); + assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]); + assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]); + } +} + +#[test] +fn test_range_large() { + let size = 200; + + let map: BTreeMap<_, _> = (1..=size).map(|i| (i, i)).collect(); + let all: Vec<_> = (1..=size).collect(); + let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]); + + assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all); + assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all); + assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Included(0), Included(size))), all); + assert_eq!(range_keys(&map, (Included(0), Unbounded)), all); + assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all); + assert_eq!(range_keys(&map, (Included(1), Included(size))), all); + assert_eq!(range_keys(&map, (Included(1), Unbounded)), all); + assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all); + assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all); + assert_eq!(range_keys(&map, (Unbounded, Included(size))), all); + assert_eq!(range_keys(&map, ..), all); + + assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]); + assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]); + assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]); + assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]); + assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first); + assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first); + assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first); + assert_eq!(range_keys(&map, (Included(0), Included(1))), first); + assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first); + assert_eq!(range_keys(&map, (Included(1), Included(1))), first); + assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first); + assert_eq!(range_keys(&map, (Unbounded, Included(1))), first); + assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last); + assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last); + assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last); + assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last); + assert_eq!(range_keys(&map, (Included(size), Included(size))), last); + assert_eq!(range_keys(&map, (Included(size), Unbounded)), last); + assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]); + assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]); + assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]); + + fn check<'a, L, R>(lhs: L, rhs: R) + where + L: IntoIterator<Item = (&'a i32, &'a i32)>, + R: IntoIterator<Item = (&'a i32, &'a i32)>, + { + let lhs: Vec<_> = lhs.into_iter().collect(); + let rhs: Vec<_> = rhs.into_iter().collect(); + assert_eq!(lhs, rhs); + } + + check(map.range(..=100), map.range(..101)); + check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]); + check(map.range(-1..=2), vec![(&1, &1), (&2, &2)]); +} + +#[test] +fn test_range_inclusive_max_value() { + let max = usize::MAX; + let map: BTreeMap<_, _> = vec![(max, 0)].into_iter().collect(); + + assert_eq!(map.range(max..=max).collect::<Vec<_>>(), &[(&max, &0)]); +} + +#[test] +fn test_range_equal_empty_cases() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + assert_eq!(map.range((Included(2), Excluded(2))).next(), None); + assert_eq!(map.range((Excluded(2), Included(2))).next(), None); +} + +#[test] +#[should_panic] +fn test_range_equal_excluded() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + map.range((Excluded(2), Excluded(2))); +} + +#[test] +#[should_panic] +fn test_range_backwards_1() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + map.range((Included(3), Included(2))); +} + +#[test] +#[should_panic] +fn test_range_backwards_2() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + map.range((Included(3), Excluded(2))); +} + +#[test] +#[should_panic] +fn test_range_backwards_3() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + map.range((Excluded(3), Included(2))); +} + +#[test] +#[should_panic] +fn test_range_backwards_4() { + let map: BTreeMap<_, _> = (0..5).map(|i| (i, i)).collect(); + map.range((Excluded(3), Excluded(2))); +} + +#[test] +fn test_range_1000() { + // Miri is too slow + let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 as u32 } else { 1000 }; + let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) { + let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v)); + let mut pairs = (0..size).map(|i| (i, i)); + + for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) { + assert_eq!(kv, pair); + } + assert_eq!(kvs.next(), None); + assert_eq!(pairs.next(), None); + } + test(&map, size, Included(&0), Excluded(&size)); + test(&map, size, Unbounded, Excluded(&size)); + test(&map, size, Included(&0), Included(&(size - 1))); + test(&map, size, Unbounded, Included(&(size - 1))); + test(&map, size, Included(&0), Unbounded); + test(&map, size, Unbounded, Unbounded); +} + +#[test] +fn test_range_borrowed_key() { + let mut map = BTreeMap::new(); + map.insert("aardvark".to_string(), 1); + map.insert("baboon".to_string(), 2); + map.insert("coyote".to_string(), 3); + map.insert("dingo".to_string(), 4); + // NOTE: would like to use simply "b".."d" here... + let mut iter = map.range::<str, _>((Included("b"), Excluded("d"))); + assert_eq!(iter.next(), Some((&"baboon".to_string(), &2))); + assert_eq!(iter.next(), Some((&"coyote".to_string(), &3))); + assert_eq!(iter.next(), None); +} + +#[test] +fn test_range() { + let size = 200; + // Miri is too slow + let step = if cfg!(miri) { 66 } else { 1 }; + let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + for i in (0..size).step_by(step) { + for j in (i..size).step_by(step) { + let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v)); + let mut pairs = (i..=j).map(|i| (i, i)); + + for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) { + assert_eq!(kv, pair); + } + assert_eq!(kvs.next(), None); + assert_eq!(pairs.next(), None); + } + } +} + +#[test] +fn test_range_mut() { + let size = 200; + // Miri is too slow + let step = if cfg!(miri) { 66 } else { 1 }; + let mut map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect(); + + for i in (0..size).step_by(step) { + for j in (i..size).step_by(step) { + let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v)); + let mut pairs = (i..=j).map(|i| (i, i)); + + for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) { + assert_eq!(kv, pair); + } + assert_eq!(kvs.next(), None); + assert_eq!(pairs.next(), None); + } + } +} + +mod test_drain_filter { + use super::*; + + #[test] + fn empty() { + let mut map: BTreeMap<i32, i32> = BTreeMap::new(); + map.drain_filter(|_, _| unreachable!("there's nothing to decide on")); + assert!(map.is_empty()); + } + + #[test] + fn consuming_nothing() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + assert!(map.drain_filter(|_, _| false).eq(std::iter::empty())); + } + + #[test] + fn consuming_all() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + assert!(map.drain_filter(|_, _| true).eq(pairs)); + } + + #[test] + fn mutating_and_keeping() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + assert!( + map.drain_filter(|_, v| { + *v += 6; + false + }) + .eq(std::iter::empty()) + ); + assert!(map.keys().copied().eq(0..3)); + assert!(map.values().copied().eq(6..9)); + } + + #[test] + fn mutating_and_removing() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + assert!( + map.drain_filter(|_, v| { + *v += 6; + true + }) + .eq((0..3).map(|i| (i, i + 6))) + ); + assert!(map.is_empty()); + } + + #[test] + fn underfull_keeping_all() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| false); + assert!(map.keys().copied().eq(0..3)); + } + + #[test] + fn underfull_removing_one() { + let pairs = (0..3).map(|i| (i, i)); + for doomed in 0..3 { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i == doomed); + assert_eq!(map.len(), 2); + } + } + + #[test] + fn underfull_keeping_one() { + let pairs = (0..3).map(|i| (i, i)); + for sacred in 0..3 { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i != sacred); + assert!(map.keys().copied().eq(sacred..=sacred)); + } + } + + #[test] + fn underfull_removing_all() { + let pairs = (0..3).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| true); + assert!(map.is_empty()); + } + + #[test] + fn height_0_keeping_all() { + let pairs = (0..NODE_CAPACITY).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| false); + assert!(map.keys().copied().eq(0..NODE_CAPACITY)); + } + + #[test] + fn height_0_removing_one() { + let pairs = (0..NODE_CAPACITY).map(|i| (i, i)); + for doomed in 0..NODE_CAPACITY { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i == doomed); + assert_eq!(map.len(), NODE_CAPACITY - 1); + } + } + + #[test] + fn height_0_keeping_one() { + let pairs = (0..NODE_CAPACITY).map(|i| (i, i)); + for sacred in 0..NODE_CAPACITY { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i != sacred); + assert!(map.keys().copied().eq(sacred..=sacred)); + } + } + + #[test] + fn height_0_removing_all() { + let pairs = (0..NODE_CAPACITY).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| true); + assert!(map.is_empty()); + } + + #[test] + fn height_0_keeping_half() { + let mut map: BTreeMap<_, _> = (0..16).map(|i| (i, i)).collect(); + assert_eq!(map.drain_filter(|i, _| *i % 2 == 0).count(), 8); + assert_eq!(map.len(), 8); + } + + #[test] + fn height_1_removing_all() { + let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| true); + assert!(map.is_empty()); + } + + #[test] + fn height_1_removing_one() { + let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); + for doomed in 0..MIN_INSERTS_HEIGHT_1 { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i == doomed); + assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1 - 1); + } + } + + #[test] + fn height_1_keeping_one() { + let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); + for sacred in 0..MIN_INSERTS_HEIGHT_1 { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i != sacred); + assert!(map.keys().copied().eq(sacred..=sacred)); + } + } + + #[cfg(not(miri))] // Miri is too slow + #[test] + fn height_2_removing_one() { + let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); + for doomed in (0..MIN_INSERTS_HEIGHT_2).step_by(12) { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i == doomed); + assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1); + } + } + + #[cfg(not(miri))] // Miri is too slow + #[test] + fn height_2_keeping_one() { + let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); + for sacred in (0..MIN_INSERTS_HEIGHT_2).step_by(12) { + let mut map: BTreeMap<_, _> = pairs.clone().collect(); + map.drain_filter(|i, _| *i != sacred); + assert!(map.keys().copied().eq(sacred..=sacred)); + } + } + + #[test] + fn height_2_removing_all() { + let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); + let mut map: BTreeMap<_, _> = pairs.collect(); + map.drain_filter(|_, _| true); + assert!(map.is_empty()); + } + + #[test] + fn drop_panic_leak() { + static PREDS: AtomicUsize = AtomicUsize::new(0); + static DROPS: AtomicUsize = AtomicUsize::new(0); + + struct D; + impl Drop for D { + fn drop(&mut self) { + if DROPS.fetch_add(1, Ordering::SeqCst) == 1 { + panic!("panic in `drop`"); + } + } + } + + // Keys are multiples of 4, so that each key is counted by a hexadecimal digit. + let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>(); + + catch_unwind(move || { + drop(map.drain_filter(|i, _| { + PREDS.fetch_add(1usize << i, Ordering::SeqCst); + true + })) + }) + .unwrap_err(); + + assert_eq!(PREDS.load(Ordering::SeqCst), 0x011); + assert_eq!(DROPS.load(Ordering::SeqCst), 3); + } + + #[test] + fn pred_panic_leak() { + static PREDS: AtomicUsize = AtomicUsize::new(0); + static DROPS: AtomicUsize = AtomicUsize::new(0); + + struct D; + impl Drop for D { + fn drop(&mut self) { + DROPS.fetch_add(1, Ordering::SeqCst); + } + } + + // Keys are multiples of 4, so that each key is counted by a hexadecimal digit. + let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>(); + + catch_unwind(AssertUnwindSafe(|| { + drop(map.drain_filter(|i, _| { + PREDS.fetch_add(1usize << i, Ordering::SeqCst); + match i { + 0 => true, + _ => panic!(), + } + })) + })) + .unwrap_err(); + + assert_eq!(PREDS.load(Ordering::SeqCst), 0x011); + assert_eq!(DROPS.load(Ordering::SeqCst), 1); + assert_eq!(map.len(), 2); + assert_eq!(map.first_entry().unwrap().key(), &4); + assert_eq!(map.last_entry().unwrap().key(), &8); + } + + // Same as above, but attempt to use the iterator again after the panic in the predicate + #[test] + fn pred_panic_reuse() { + static PREDS: AtomicUsize = AtomicUsize::new(0); + static DROPS: AtomicUsize = AtomicUsize::new(0); + + struct D; + impl Drop for D { + fn drop(&mut self) { + DROPS.fetch_add(1, Ordering::SeqCst); + } + } + + // Keys are multiples of 4, so that each key is counted by a hexadecimal digit. + let mut map = (0..3).map(|i| (i * 4, D)).collect::<BTreeMap<_, _>>(); + + { + let mut it = map.drain_filter(|i, _| { + PREDS.fetch_add(1usize << i, Ordering::SeqCst); + match i { + 0 => true, + _ => panic!(), + } + }); + catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err(); + // Iterator behaviour after a panic is explicitly unspecified, + // so this is just the current implementation: + let result = catch_unwind(AssertUnwindSafe(|| it.next())); + assert!(matches!(result, Ok(None))); + } + + assert_eq!(PREDS.load(Ordering::SeqCst), 0x011); + assert_eq!(DROPS.load(Ordering::SeqCst), 1); + assert_eq!(map.len(), 2); + assert_eq!(map.first_entry().unwrap().key(), &4); + assert_eq!(map.last_entry().unwrap().key(), &8); + } +} + +#[test] +fn test_borrow() { + // make sure these compile -- using the Borrow trait + { + let mut map = BTreeMap::new(); + map.insert("0".to_string(), 1); + assert_eq!(map["0"], 1); + } + + { + let mut map = BTreeMap::new(); + map.insert(Box::new(0), 1); + assert_eq!(map[&0], 1); + } + + { + let mut map = BTreeMap::new(); + map.insert(Box::new([0, 1]) as Box<[i32]>, 1); + assert_eq!(map[&[0, 1][..]], 1); + } + + { + let mut map = BTreeMap::new(); + map.insert(Rc::new(0), 1); + assert_eq!(map[&0], 1); + } +} + +#[test] +fn test_entry() { + let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)]; + + let mut map: BTreeMap<_, _> = xs.iter().cloned().collect(); + + // Existing key (insert) + match map.entry(1) { + Vacant(_) => unreachable!(), + Occupied(mut view) => { + assert_eq!(view.get(), &10); + assert_eq!(view.insert(100), 10); + } + } + assert_eq!(map.get(&1).unwrap(), &100); + assert_eq!(map.len(), 6); + + // Existing key (update) + match map.entry(2) { + Vacant(_) => unreachable!(), + Occupied(mut view) => { + let v = view.get_mut(); + *v *= 10; + } + } + assert_eq!(map.get(&2).unwrap(), &200); + assert_eq!(map.len(), 6); + + // Existing key (take) + match map.entry(3) { + Vacant(_) => unreachable!(), + Occupied(view) => { + assert_eq!(view.remove(), 30); + } + } + assert_eq!(map.get(&3), None); + assert_eq!(map.len(), 5); + + // Inexistent key (insert) + match map.entry(10) { + Occupied(_) => unreachable!(), + Vacant(view) => { + assert_eq!(*view.insert(1000), 1000); + } + } + assert_eq!(map.get(&10).unwrap(), &1000); + assert_eq!(map.len(), 6); +} + +#[test] +fn test_extend_ref() { + let mut a = BTreeMap::new(); + a.insert(1, "one"); + let mut b = BTreeMap::new(); + b.insert(2, "two"); + b.insert(3, "three"); + + a.extend(&b); + + assert_eq!(a.len(), 3); + assert_eq!(a[&1], "one"); + assert_eq!(a[&2], "two"); + assert_eq!(a[&3], "three"); +} + +#[test] +fn test_zst() { + let mut m = BTreeMap::new(); + assert_eq!(m.len(), 0); + + assert_eq!(m.insert((), ()), None); + assert_eq!(m.len(), 1); + + assert_eq!(m.insert((), ()), Some(())); + assert_eq!(m.len(), 1); + assert_eq!(m.iter().count(), 1); + + m.clear(); + assert_eq!(m.len(), 0); + + for _ in 0..100 { + m.insert((), ()); + } + + assert_eq!(m.len(), 1); + assert_eq!(m.iter().count(), 1); +} + +// This test's only purpose is to ensure that zero-sized keys with nonsensical orderings +// do not cause segfaults when used with zero-sized values. All other map behavior is +// undefined. +#[test] +fn test_bad_zst() { + use std::cmp::Ordering; + + struct Bad; + + impl PartialEq for Bad { + fn eq(&self, _: &Self) -> bool { + false + } + } + + impl Eq for Bad {} + + impl PartialOrd for Bad { + fn partial_cmp(&self, _: &Self) -> Option<Ordering> { + Some(Ordering::Less) + } + } + + impl Ord for Bad { + fn cmp(&self, _: &Self) -> Ordering { + Ordering::Less + } + } + + let mut m = BTreeMap::new(); + + for _ in 0..100 { + m.insert(Bad, Bad); + } +} + +#[test] +fn test_clone() { + let mut map = BTreeMap::new(); + let size = MIN_INSERTS_HEIGHT_1; + assert_eq!(map.len(), 0); + + for i in 0..size { + assert_eq!(map.insert(i, 10 * i), None); + assert_eq!(map.len(), i + 1); + assert_eq!(map, map.clone()); + } + + for i in 0..size { + assert_eq!(map.insert(i, 100 * i), Some(10 * i)); + assert_eq!(map.len(), size); + assert_eq!(map, map.clone()); + } + + for i in 0..size / 2 { + assert_eq!(map.remove(&(i * 2)), Some(i * 200)); + assert_eq!(map.len(), size - i - 1); + assert_eq!(map, map.clone()); + } + + for i in 0..size / 2 { + assert_eq!(map.remove(&(2 * i)), None); + assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100)); + assert_eq!(map.len(), size / 2 - i - 1); + assert_eq!(map, map.clone()); + } + + // Test a tree with 2 chock-full levels and a tree with 3 levels. + map = (1..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)).collect(); + assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1); + assert_eq!(map, map.clone()); + map.insert(0, 0); + assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2); + assert_eq!(map, map.clone()); +} + +#[test] +fn test_clone_from() { + let mut map1 = BTreeMap::new(); + let max_size = MIN_INSERTS_HEIGHT_1; + + // Range to max_size inclusive, because i is the size of map1 being tested. + for i in 0..=max_size { + let mut map2 = BTreeMap::new(); + for j in 0..i { + let mut map1_copy = map2.clone(); + map1_copy.clone_from(&map1); // small cloned from large + assert_eq!(map1_copy, map1); + let mut map2_copy = map1.clone(); + map2_copy.clone_from(&map2); // large cloned from small + assert_eq!(map2_copy, map2); + map2.insert(100 * j + 1, 2 * j + 1); + } + map2.clone_from(&map1); // same length + assert_eq!(map2, map1); + map1.insert(i, 10 * i); + } +} + +#[test] +#[allow(dead_code)] +fn test_variance() { + use std::collections::btree_map::{IntoIter, Iter, Keys, Range, Values}; + + fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> { + v + } + fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> { + v + } + fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> { + v + } + fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> { + v + } + fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> { + v + } + fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> { + v + } + fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> { + v + } + fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> { + v + } + fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> { + v + } + fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> { + v + } +} + +#[test] +fn test_occupied_entry_key() { + let mut a = BTreeMap::new(); + let key = "hello there"; + let value = "value goes here"; + assert!(a.is_empty()); + a.insert(key.clone(), value.clone()); + assert_eq!(a.len(), 1); + assert_eq!(a[key], value); + + match a.entry(key.clone()) { + Vacant(_) => panic!(), + Occupied(e) => assert_eq!(key, *e.key()), + } + assert_eq!(a.len(), 1); + assert_eq!(a[key], value); +} + +#[test] +fn test_vacant_entry_key() { + let mut a = BTreeMap::new(); + let key = "hello there"; + let value = "value goes here"; + + assert!(a.is_empty()); + match a.entry(key.clone()) { + Occupied(_) => panic!(), + Vacant(e) => { + assert_eq!(key, *e.key()); + e.insert(value.clone()); + } + } + assert_eq!(a.len(), 1); + assert_eq!(a[key], value); +} + +#[test] +fn test_first_last_entry() { + let mut a = BTreeMap::new(); + assert!(a.first_entry().is_none()); + assert!(a.last_entry().is_none()); + a.insert(1, 42); + assert_eq!(a.first_entry().unwrap().key(), &1); + assert_eq!(a.last_entry().unwrap().key(), &1); + a.insert(2, 24); + assert_eq!(a.first_entry().unwrap().key(), &1); + assert_eq!(a.last_entry().unwrap().key(), &2); + a.insert(0, 6); + assert_eq!(a.first_entry().unwrap().key(), &0); + assert_eq!(a.last_entry().unwrap().key(), &2); + let (k1, v1) = a.first_entry().unwrap().remove_entry(); + assert_eq!(k1, 0); + assert_eq!(v1, 6); + let (k2, v2) = a.last_entry().unwrap().remove_entry(); + assert_eq!(k2, 2); + assert_eq!(v2, 24); + assert_eq!(a.first_entry().unwrap().key(), &1); + assert_eq!(a.last_entry().unwrap().key(), &1); +} + +macro_rules! create_append_test { + ($name:ident, $len:expr) => { + #[test] + fn $name() { + let mut a = BTreeMap::new(); + for i in 0..8 { + a.insert(i, i); + } + + let mut b = BTreeMap::new(); + for i in 5..$len { + b.insert(i, 2 * i); + } + + a.append(&mut b); + + assert_eq!(a.len(), $len); + assert_eq!(b.len(), 0); + + for i in 0..$len { + if i < 5 { + assert_eq!(a[&i], i); + } else { + assert_eq!(a[&i], 2 * i); + } + } + + assert_eq!(a.remove(&($len - 1)), Some(2 * ($len - 1))); + assert_eq!(a.insert($len - 1, 20), None); + } + }; +} + +// These are mostly for testing the algorithm that "fixes" the right edge after insertion. +// Single node. +create_append_test!(test_append_9, 9); +// Two leafs that don't need fixing. +create_append_test!(test_append_17, 17); +// Two leafs where the second one ends up underfull and needs stealing at the end. +create_append_test!(test_append_14, 14); +// Two leafs where the second one ends up empty because the insertion finished at the root. +create_append_test!(test_append_12, 12); +// Three levels; insertion finished at the root. +create_append_test!(test_append_144, 144); +// Three levels; insertion finished at leaf while there is an empty node on the second level. +create_append_test!(test_append_145, 145); +// Tests for several randomly chosen sizes. +create_append_test!(test_append_170, 170); +create_append_test!(test_append_181, 181); +#[cfg(not(miri))] // Miri is too slow +create_append_test!(test_append_239, 239); +#[cfg(not(miri))] // Miri is too slow +create_append_test!(test_append_1700, 1700); + +fn rand_data(len: usize) -> Vec<(u32, u32)> { + let mut rng = DeterministicRng::new(); + Vec::from_iter((0..len).map(|_| (rng.next(), rng.next()))) +} + +#[test] +fn test_split_off_empty_right() { + let mut data = rand_data(173); + + let mut map = BTreeMap::from_iter(data.clone()); + let right = map.split_off(&(data.iter().max().unwrap().0 + 1)); + + data.sort(); + assert!(map.into_iter().eq(data)); + assert!(right.into_iter().eq(None)); +} + +#[test] +fn test_split_off_empty_left() { + let mut data = rand_data(314); + + let mut map = BTreeMap::from_iter(data.clone()); + let right = map.split_off(&data.iter().min().unwrap().0); + + data.sort(); + assert!(map.into_iter().eq(None)); + assert!(right.into_iter().eq(data)); +} + +// In a tree with 3 levels, if all but a part of the first leaf node is split off, +// make sure fix_top eliminates both top levels. +#[test] +fn test_split_off_tiny_left_height_2() { + let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); + let mut left: BTreeMap<_, _> = pairs.clone().collect(); + let right = left.split_off(&1); + assert_eq!(left.len(), 1); + assert_eq!(right.len(), MIN_INSERTS_HEIGHT_2 - 1); + assert_eq!(*left.first_key_value().unwrap().0, 0); + assert_eq!(*right.first_key_value().unwrap().0, 1); +} + +// In a tree with 3 levels, if only part of the last leaf node is split off, +// make sure fix_top eliminates both top levels. +#[test] +fn test_split_off_tiny_right_height_2() { + let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); + let last = MIN_INSERTS_HEIGHT_2 - 1; + let mut left: BTreeMap<_, _> = pairs.clone().collect(); + assert_eq!(*left.last_key_value().unwrap().0, last); + let right = left.split_off(&last); + assert_eq!(left.len(), MIN_INSERTS_HEIGHT_2 - 1); + assert_eq!(right.len(), 1); + assert_eq!(*left.last_key_value().unwrap().0, last - 1); + assert_eq!(*right.last_key_value().unwrap().0, last); +} + +#[test] +fn test_split_off_large_random_sorted() { + // Miri is too slow + let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) }; + // special case with maximum height. + data.sort(); + + let mut map = BTreeMap::from_iter(data.clone()); + let key = data[data.len() / 2].0; + let right = map.split_off(&key); + + assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key))); + assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key))); +} + +#[test] +fn test_into_iter_drop_leak_height_0() { + static DROPS: AtomicUsize = AtomicUsize::new(0); + + struct D; + + impl Drop for D { + fn drop(&mut self) { + if DROPS.fetch_add(1, Ordering::SeqCst) == 3 { + panic!("panic in `drop`"); + } + } + } + + let mut map = BTreeMap::new(); + map.insert("a", D); + map.insert("b", D); + map.insert("c", D); + map.insert("d", D); + map.insert("e", D); + + catch_unwind(move || drop(map.into_iter())).unwrap_err(); + + assert_eq!(DROPS.load(Ordering::SeqCst), 5); +} + +#[test] +fn test_into_iter_drop_leak_height_1() { + let size = MIN_INSERTS_HEIGHT_1; + static DROPS: AtomicUsize = AtomicUsize::new(0); + static PANIC_POINT: AtomicUsize = AtomicUsize::new(0); + + struct D; + impl Drop for D { + fn drop(&mut self) { + if DROPS.fetch_add(1, Ordering::SeqCst) == PANIC_POINT.load(Ordering::SeqCst) { + panic!("panic in `drop`"); + } + } + } + + for panic_point in vec![0, 1, size - 2, size - 1] { + DROPS.store(0, Ordering::SeqCst); + PANIC_POINT.store(panic_point, Ordering::SeqCst); + let map: BTreeMap<_, _> = (0..size).map(|i| (i, D)).collect(); + catch_unwind(move || drop(map.into_iter())).unwrap_err(); + assert_eq!(DROPS.load(Ordering::SeqCst), size); + } +} diff --git a/library/alloc/tests/btree/mod.rs b/library/alloc/tests/btree/mod.rs new file mode 100644 index 00000000000..1d08ae13e05 --- /dev/null +++ b/library/alloc/tests/btree/mod.rs @@ -0,0 +1,27 @@ +mod map; +mod set; + +/// XorShiftRng +struct DeterministicRng { + x: u32, + y: u32, + z: u32, + w: u32, +} + +impl DeterministicRng { + fn new() -> Self { + DeterministicRng { x: 0x193a6754, y: 0xa8a7d469, z: 0x97830e05, w: 0x113ba7bb } + } + + fn next(&mut self) -> u32 { + let x = self.x; + let t = x ^ (x << 11); + self.x = self.y; + self.y = self.z; + self.z = self.w; + let w_ = self.w; + self.w = w_ ^ (w_ >> 19) ^ (t ^ (t >> 8)); + self.w + } +} diff --git a/library/alloc/tests/btree/set.rs b/library/alloc/tests/btree/set.rs new file mode 100644 index 00000000000..b6c34b7c6c3 --- /dev/null +++ b/library/alloc/tests/btree/set.rs @@ -0,0 +1,666 @@ +use std::collections::BTreeSet; +use std::iter::FromIterator; +use std::panic::{catch_unwind, AssertUnwindSafe}; +use std::sync::atomic::{AtomicU32, Ordering}; + +use super::DeterministicRng; + +#[test] +fn test_clone_eq() { + let mut m = BTreeSet::new(); + + m.insert(1); + m.insert(2); + + assert_eq!(m.clone(), m); +} + +#[test] +fn test_hash() { + use crate::hash; + + let mut x = BTreeSet::new(); + let mut y = BTreeSet::new(); + + x.insert(1); + x.insert(2); + x.insert(3); + + y.insert(3); + y.insert(2); + y.insert(1); + + assert_eq!(hash(&x), hash(&y)); +} + +#[test] +fn test_iter_min_max() { + let mut a = BTreeSet::new(); + assert_eq!(a.iter().min(), None); + assert_eq!(a.iter().max(), None); + assert_eq!(a.range(..).min(), None); + assert_eq!(a.range(..).max(), None); + assert_eq!(a.difference(&BTreeSet::new()).min(), None); + assert_eq!(a.difference(&BTreeSet::new()).max(), None); + assert_eq!(a.intersection(&a).min(), None); + assert_eq!(a.intersection(&a).max(), None); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), None); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), None); + assert_eq!(a.union(&a).min(), None); + assert_eq!(a.union(&a).max(), None); + a.insert(1); + a.insert(2); + assert_eq!(a.iter().min(), Some(&1)); + assert_eq!(a.iter().max(), Some(&2)); + assert_eq!(a.range(..).min(), Some(&1)); + assert_eq!(a.range(..).max(), Some(&2)); + assert_eq!(a.difference(&BTreeSet::new()).min(), Some(&1)); + assert_eq!(a.difference(&BTreeSet::new()).max(), Some(&2)); + assert_eq!(a.intersection(&a).min(), Some(&1)); + assert_eq!(a.intersection(&a).max(), Some(&2)); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), Some(&1)); + assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), Some(&2)); + assert_eq!(a.union(&a).min(), Some(&1)); + assert_eq!(a.union(&a).max(), Some(&2)); +} + +fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F) +where + F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut dyn FnMut(&i32) -> bool) -> bool, +{ + let mut set_a = BTreeSet::new(); + let mut set_b = BTreeSet::new(); + + for x in a { + assert!(set_a.insert(*x)) + } + for y in b { + assert!(set_b.insert(*y)) + } + + let mut i = 0; + f(&set_a, &set_b, &mut |&x| { + if i < expected.len() { + assert_eq!(x, expected[i]); + } + i += 1; + true + }); + assert_eq!(i, expected.len()); +} + +#[test] +fn test_intersection() { + fn check_intersection(a: &[i32], b: &[i32], expected: &[i32]) { + check(a, b, expected, |x, y, f| x.intersection(y).all(f)) + } + + check_intersection(&[], &[], &[]); + check_intersection(&[1, 2, 3], &[], &[]); + check_intersection(&[], &[1, 2, 3], &[]); + check_intersection(&[2], &[1, 2, 3], &[2]); + check_intersection(&[1, 2, 3], &[2], &[2]); + check_intersection(&[11, 1, 3, 77, 103, 5, -5], &[2, 11, 77, -9, -42, 5, 3], &[3, 5, 11, 77]); + + if cfg!(miri) { + // Miri is too slow + return; + } + + let large = (0..100).collect::<Vec<_>>(); + check_intersection(&[], &large, &[]); + check_intersection(&large, &[], &[]); + check_intersection(&[-1], &large, &[]); + check_intersection(&large, &[-1], &[]); + check_intersection(&[0], &large, &[0]); + check_intersection(&large, &[0], &[0]); + check_intersection(&[99], &large, &[99]); + check_intersection(&large, &[99], &[99]); + check_intersection(&[100], &large, &[]); + check_intersection(&large, &[100], &[]); + check_intersection(&[11, 5000, 1, 3, 77, 8924], &large, &[1, 3, 11, 77]); +} + +#[test] +fn test_intersection_size_hint() { + let x: BTreeSet<i32> = [3, 4].iter().copied().collect(); + let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect(); + let mut iter = x.intersection(&y); + assert_eq!(iter.size_hint(), (1, Some(1))); + assert_eq!(iter.next(), Some(&3)); + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + + iter = y.intersection(&y); + assert_eq!(iter.size_hint(), (0, Some(3))); + assert_eq!(iter.next(), Some(&1)); + assert_eq!(iter.size_hint(), (0, Some(2))); +} + +#[test] +fn test_difference() { + fn check_difference(a: &[i32], b: &[i32], expected: &[i32]) { + check(a, b, expected, |x, y, f| x.difference(y).all(f)) + } + + check_difference(&[], &[], &[]); + check_difference(&[1, 12], &[], &[1, 12]); + check_difference(&[], &[1, 2, 3, 9], &[]); + check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]); + check_difference(&[1, 3, 5, 9, 11], &[3, 6, 9], &[1, 5, 11]); + check_difference(&[1, 3, 5, 9, 11], &[0, 1], &[3, 5, 9, 11]); + check_difference(&[1, 3, 5, 9, 11], &[11, 12], &[1, 3, 5, 9]); + check_difference( + &[-5, 11, 22, 33, 40, 42], + &[-12, -5, 14, 23, 34, 38, 39, 50], + &[11, 22, 33, 40, 42], + ); + + if cfg!(miri) { + // Miri is too slow + return; + } + + let large = (0..100).collect::<Vec<_>>(); + check_difference(&[], &large, &[]); + check_difference(&[-1], &large, &[-1]); + check_difference(&[0], &large, &[]); + check_difference(&[99], &large, &[]); + check_difference(&[100], &large, &[100]); + check_difference(&[11, 5000, 1, 3, 77, 8924], &large, &[5000, 8924]); + check_difference(&large, &[], &large); + check_difference(&large, &[-1], &large); + check_difference(&large, &[100], &large); +} + +#[test] +fn test_difference_size_hint() { + let s246: BTreeSet<i32> = [2, 4, 6].iter().copied().collect(); + let s23456: BTreeSet<i32> = (2..=6).collect(); + let mut iter = s246.difference(&s23456); + assert_eq!(iter.size_hint(), (0, Some(3))); + assert_eq!(iter.next(), None); + + let s12345: BTreeSet<i32> = (1..=5).collect(); + iter = s246.difference(&s12345); + assert_eq!(iter.size_hint(), (0, Some(3))); + assert_eq!(iter.next(), Some(&6)); + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + + let s34567: BTreeSet<i32> = (3..=7).collect(); + iter = s246.difference(&s34567); + assert_eq!(iter.size_hint(), (0, Some(3))); + assert_eq!(iter.next(), Some(&2)); + assert_eq!(iter.size_hint(), (0, Some(2))); + assert_eq!(iter.next(), None); + + let s1: BTreeSet<i32> = (-9..=1).collect(); + iter = s246.difference(&s1); + assert_eq!(iter.size_hint(), (3, Some(3))); + + let s2: BTreeSet<i32> = (-9..=2).collect(); + iter = s246.difference(&s2); + assert_eq!(iter.size_hint(), (2, Some(2))); + assert_eq!(iter.next(), Some(&4)); + assert_eq!(iter.size_hint(), (1, Some(1))); + + let s23: BTreeSet<i32> = (2..=3).collect(); + iter = s246.difference(&s23); + assert_eq!(iter.size_hint(), (1, Some(3))); + assert_eq!(iter.next(), Some(&4)); + assert_eq!(iter.size_hint(), (1, Some(1))); + + let s4: BTreeSet<i32> = (4..=4).collect(); + iter = s246.difference(&s4); + assert_eq!(iter.size_hint(), (2, Some(3))); + assert_eq!(iter.next(), Some(&2)); + assert_eq!(iter.size_hint(), (1, Some(2))); + assert_eq!(iter.next(), Some(&6)); + assert_eq!(iter.size_hint(), (0, Some(0))); + assert_eq!(iter.next(), None); + + let s56: BTreeSet<i32> = (5..=6).collect(); + iter = s246.difference(&s56); + assert_eq!(iter.size_hint(), (1, Some(3))); + assert_eq!(iter.next(), Some(&2)); + assert_eq!(iter.size_hint(), (0, Some(2))); + + let s6: BTreeSet<i32> = (6..=19).collect(); + iter = s246.difference(&s6); + assert_eq!(iter.size_hint(), (2, Some(2))); + assert_eq!(iter.next(), Some(&2)); + assert_eq!(iter.size_hint(), (1, Some(1))); + + let s7: BTreeSet<i32> = (7..=19).collect(); + iter = s246.difference(&s7); + assert_eq!(iter.size_hint(), (3, Some(3))); +} + +#[test] +fn test_symmetric_difference() { + fn check_symmetric_difference(a: &[i32], b: &[i32], expected: &[i32]) { + check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f)) + } + + check_symmetric_difference(&[], &[], &[]); + check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]); + check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]); + check_symmetric_difference(&[1, 3, 5, 9, 11], &[-2, 3, 9, 14, 22], &[-2, 1, 5, 11, 14, 22]); +} + +#[test] +fn test_symmetric_difference_size_hint() { + let x: BTreeSet<i32> = [2, 4].iter().copied().collect(); + let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect(); + let mut iter = x.symmetric_difference(&y); + assert_eq!(iter.size_hint(), (0, Some(5))); + assert_eq!(iter.next(), Some(&1)); + assert_eq!(iter.size_hint(), (0, Some(4))); + assert_eq!(iter.next(), Some(&3)); + assert_eq!(iter.size_hint(), (0, Some(1))); +} + +#[test] +fn test_union() { + fn check_union(a: &[i32], b: &[i32], expected: &[i32]) { + check(a, b, expected, |x, y, f| x.union(y).all(f)) + } + + check_union(&[], &[], &[]); + check_union(&[1, 2, 3], &[2], &[1, 2, 3]); + check_union(&[2], &[1, 2, 3], &[1, 2, 3]); + check_union( + &[1, 3, 5, 9, 11, 16, 19, 24], + &[-2, 1, 5, 9, 13, 19], + &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24], + ); +} + +#[test] +fn test_union_size_hint() { + let x: BTreeSet<i32> = [2, 4].iter().copied().collect(); + let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect(); + let mut iter = x.union(&y); + assert_eq!(iter.size_hint(), (3, Some(5))); + assert_eq!(iter.next(), Some(&1)); + assert_eq!(iter.size_hint(), (2, Some(4))); + assert_eq!(iter.next(), Some(&2)); + assert_eq!(iter.size_hint(), (1, Some(2))); +} + +#[test] +// Only tests the simple function definition with respect to intersection +fn test_is_disjoint() { + let one = [1].iter().collect::<BTreeSet<_>>(); + let two = [2].iter().collect::<BTreeSet<_>>(); + assert!(one.is_disjoint(&two)); +} + +#[test] +// Also implicitly tests the trivial function definition of is_superset +fn test_is_subset() { + fn is_subset(a: &[i32], b: &[i32]) -> bool { + let set_a = a.iter().collect::<BTreeSet<_>>(); + let set_b = b.iter().collect::<BTreeSet<_>>(); + set_a.is_subset(&set_b) + } + + assert_eq!(is_subset(&[], &[]), true); + assert_eq!(is_subset(&[], &[1, 2]), true); + assert_eq!(is_subset(&[0], &[1, 2]), false); + assert_eq!(is_subset(&[1], &[1, 2]), true); + assert_eq!(is_subset(&[2], &[1, 2]), true); + assert_eq!(is_subset(&[3], &[1, 2]), false); + assert_eq!(is_subset(&[1, 2], &[1]), false); + assert_eq!(is_subset(&[1, 2], &[1, 2]), true); + assert_eq!(is_subset(&[1, 2], &[2, 3]), false); + assert_eq!( + is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 33, 34, 38, 39, 40, 42]), + true + ); + assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 34, 38]), false); + + if cfg!(miri) { + // Miri is too slow + return; + } + + let large = (0..100).collect::<Vec<_>>(); + assert_eq!(is_subset(&[], &large), true); + assert_eq!(is_subset(&large, &[]), false); + assert_eq!(is_subset(&[-1], &large), false); + assert_eq!(is_subset(&[0], &large), true); + assert_eq!(is_subset(&[1, 2], &large), true); + assert_eq!(is_subset(&[99, 100], &large), false); +} + +#[test] +fn test_drain_filter() { + let mut x: BTreeSet<_> = [1].iter().copied().collect(); + let mut y: BTreeSet<_> = [1].iter().copied().collect(); + + x.drain_filter(|_| true); + y.drain_filter(|_| false); + assert_eq!(x.len(), 0); + assert_eq!(y.len(), 1); +} + +#[test] +fn test_drain_filter_drop_panic_leak() { + static PREDS: AtomicU32 = AtomicU32::new(0); + static DROPS: AtomicU32 = AtomicU32::new(0); + + #[derive(PartialEq, Eq, PartialOrd, Ord)] + struct D(i32); + impl Drop for D { + fn drop(&mut self) { + if DROPS.fetch_add(1, Ordering::SeqCst) == 1 { + panic!("panic in `drop`"); + } + } + } + + let mut set = BTreeSet::new(); + set.insert(D(0)); + set.insert(D(4)); + set.insert(D(8)); + + catch_unwind(move || { + drop(set.drain_filter(|d| { + PREDS.fetch_add(1u32 << d.0, Ordering::SeqCst); + true + })) + }) + .ok(); + + assert_eq!(PREDS.load(Ordering::SeqCst), 0x011); + assert_eq!(DROPS.load(Ordering::SeqCst), 3); +} + +#[test] +fn test_drain_filter_pred_panic_leak() { + static PREDS: AtomicU32 = AtomicU32::new(0); + static DROPS: AtomicU32 = AtomicU32::new(0); + + #[derive(PartialEq, Eq, PartialOrd, Ord)] + struct D(i32); + impl Drop for D { + fn drop(&mut self) { + DROPS.fetch_add(1, Ordering::SeqCst); + } + } + + let mut set = BTreeSet::new(); + set.insert(D(0)); + set.insert(D(4)); + set.insert(D(8)); + + catch_unwind(AssertUnwindSafe(|| { + drop(set.drain_filter(|d| { + PREDS.fetch_add(1u32 << d.0, Ordering::SeqCst); + match d.0 { + 0 => true, + _ => panic!(), + } + })) + })) + .ok(); + + assert_eq!(PREDS.load(Ordering::SeqCst), 0x011); + assert_eq!(DROPS.load(Ordering::SeqCst), 1); + assert_eq!(set.len(), 2); + assert_eq!(set.first().unwrap().0, 4); + assert_eq!(set.last().unwrap().0, 8); +} + +#[test] +fn test_clear() { + let mut x = BTreeSet::new(); + x.insert(1); + + x.clear(); + assert!(x.is_empty()); +} + +#[test] +fn test_zip() { + let mut x = BTreeSet::new(); + x.insert(5); + x.insert(12); + x.insert(11); + + let mut y = BTreeSet::new(); + y.insert("foo"); + y.insert("bar"); + + let x = x; + let y = y; + let mut z = x.iter().zip(&y); + + assert_eq!(z.next().unwrap(), (&5, &("bar"))); + assert_eq!(z.next().unwrap(), (&11, &("foo"))); + assert!(z.next().is_none()); +} + +#[test] +fn test_from_iter() { + let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9]; + + let set: BTreeSet<_> = xs.iter().cloned().collect(); + + for x in &xs { + assert!(set.contains(x)); + } +} + +#[test] +fn test_show() { + let mut set = BTreeSet::new(); + let empty = BTreeSet::<i32>::new(); + + set.insert(1); + set.insert(2); + + let set_str = format!("{:?}", set); + + assert_eq!(set_str, "{1, 2}"); + assert_eq!(format!("{:?}", empty), "{}"); +} + +#[test] +fn test_extend_ref() { + let mut a = BTreeSet::new(); + a.insert(1); + + a.extend(&[2, 3, 4]); + + assert_eq!(a.len(), 4); + assert!(a.contains(&1)); + assert!(a.contains(&2)); + assert!(a.contains(&3)); + assert!(a.contains(&4)); + + let mut b = BTreeSet::new(); + b.insert(5); + b.insert(6); + + a.extend(&b); + + assert_eq!(a.len(), 6); + assert!(a.contains(&1)); + assert!(a.contains(&2)); + assert!(a.contains(&3)); + assert!(a.contains(&4)); + assert!(a.contains(&5)); + assert!(a.contains(&6)); +} + +#[test] +fn test_recovery() { + use std::cmp::Ordering; + + #[derive(Debug)] + struct Foo(&'static str, i32); + + impl PartialEq for Foo { + fn eq(&self, other: &Self) -> bool { + self.0 == other.0 + } + } + + impl Eq for Foo {} + + impl PartialOrd for Foo { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + self.0.partial_cmp(&other.0) + } + } + + impl Ord for Foo { + fn cmp(&self, other: &Self) -> Ordering { + self.0.cmp(&other.0) + } + } + + let mut s = BTreeSet::new(); + assert_eq!(s.replace(Foo("a", 1)), None); + assert_eq!(s.len(), 1); + assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1))); + assert_eq!(s.len(), 1); + + { + let mut it = s.iter(); + assert_eq!(it.next(), Some(&Foo("a", 2))); + assert_eq!(it.next(), None); + } + + assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2))); + assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2))); + assert_eq!(s.len(), 0); + + assert_eq!(s.get(&Foo("a", 1)), None); + assert_eq!(s.take(&Foo("a", 1)), None); + + assert_eq!(s.iter().next(), None); +} + +#[test] +#[allow(dead_code)] +fn test_variance() { + use std::collections::btree_set::{IntoIter, Iter, Range}; + + fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> { + v + } + fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> { + v + } + fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> { + v + } + fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> { + v + } +} + +#[test] +fn test_append() { + let mut a = BTreeSet::new(); + a.insert(1); + a.insert(2); + a.insert(3); + + let mut b = BTreeSet::new(); + b.insert(3); + b.insert(4); + b.insert(5); + + a.append(&mut b); + + assert_eq!(a.len(), 5); + assert_eq!(b.len(), 0); + + assert_eq!(a.contains(&1), true); + assert_eq!(a.contains(&2), true); + assert_eq!(a.contains(&3), true); + assert_eq!(a.contains(&4), true); + assert_eq!(a.contains(&5), true); +} + +#[test] +fn test_first_last() { + let mut a = BTreeSet::new(); + assert_eq!(a.first(), None); + assert_eq!(a.last(), None); + a.insert(1); + assert_eq!(a.first(), Some(&1)); + assert_eq!(a.last(), Some(&1)); + a.insert(2); + assert_eq!(a.first(), Some(&1)); + assert_eq!(a.last(), Some(&2)); + for i in 3..=12 { + a.insert(i); + } + assert_eq!(a.first(), Some(&1)); + assert_eq!(a.last(), Some(&12)); + assert_eq!(a.pop_first(), Some(1)); + assert_eq!(a.pop_last(), Some(12)); + assert_eq!(a.pop_first(), Some(2)); + assert_eq!(a.pop_last(), Some(11)); + assert_eq!(a.pop_first(), Some(3)); + assert_eq!(a.pop_last(), Some(10)); + assert_eq!(a.pop_first(), Some(4)); + assert_eq!(a.pop_first(), Some(5)); + assert_eq!(a.pop_first(), Some(6)); + assert_eq!(a.pop_first(), Some(7)); + assert_eq!(a.pop_first(), Some(8)); + assert_eq!(a.clone().pop_last(), Some(9)); + assert_eq!(a.pop_first(), Some(9)); + assert_eq!(a.pop_first(), None); + assert_eq!(a.pop_last(), None); +} + +fn rand_data(len: usize) -> Vec<u32> { + let mut rng = DeterministicRng::new(); + Vec::from_iter((0..len).map(|_| rng.next())) +} + +#[test] +fn test_split_off_empty_right() { + let mut data = rand_data(173); + + let mut set = BTreeSet::from_iter(data.clone()); + let right = set.split_off(&(data.iter().max().unwrap() + 1)); + + data.sort(); + assert!(set.into_iter().eq(data)); + assert!(right.into_iter().eq(None)); +} + +#[test] +fn test_split_off_empty_left() { + let mut data = rand_data(314); + + let mut set = BTreeSet::from_iter(data.clone()); + let right = set.split_off(data.iter().min().unwrap()); + + data.sort(); + assert!(set.into_iter().eq(None)); + assert!(right.into_iter().eq(data)); +} + +#[test] +fn test_split_off_large_random_sorted() { + // Miri is too slow + let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) }; + // special case with maximum height. + data.sort(); + + let mut set = BTreeSet::from_iter(data.clone()); + let key = data[data.len() / 2]; + let right = set.split_off(&key); + + assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key))); + assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key))); +} |