src/librustc_data_structures/sorted_map.rs - third_party/rust - Git at Google

 // Copyright 2018 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.

 use std::borrow::Borrow;
 use std::cmp::Ordering;
 use std::iter::FromIterator;
 use std::mem;
 use std::ops::{RangeBounds, Bound, Index, IndexMut};

 /// `SortedMap` is a data structure with similar characteristics as BTreeMap but
 /// slightly different trade-offs: lookup, insertion, and removal are O(log(N))
 /// and elements can be iterated in order cheaply.
 ///
 /// `SortedMap` can be faster than a `BTreeMap` for small sizes (<50) since it
 /// stores data in a more compact way. It also supports accessing contiguous
 /// ranges of elements as a slice, and slices of already sorted elements can be
 /// inserted efficiently.
 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default, Debug, RustcEncodable,
          RustcDecodable)]
 pub struct SortedMap<K: Ord, V> {
     data: Vec<(K, V)>
 }

 impl<K: Ord, V> SortedMap<K, V> {
     #[inline]
     pub fn new() -> SortedMap<K, V> {
         SortedMap {
             data: vec![]
         }
     }

     /// Construct a `SortedMap` from a presorted set of elements. This is faster
     /// than creating an empty map and then inserting the elements individually.
     ///
     /// It is up to the caller to make sure that the elements are sorted by key
     /// and that there are no duplicates.
     #[inline]
     pub fn from_presorted_elements(elements: Vec<(K, V)>) -> SortedMap<K, V>
     {
         debug_assert!(elements.windows(2).all(|w| w[0].0 < w[1].0));

         SortedMap {
             data: elements
         }
     }

     #[inline]
     pub fn insert(&mut self, key: K, mut value: V) -> Option<V> {
         match self.lookup_index_for(&key) {
             Ok(index) => {
                 let slot = unsafe {
                     self.data.get_unchecked_mut(index)
                 };
                 mem::swap(&mut slot.1, &mut value);
                 Some(value)
             }
             Err(index) => {
                 self.data.insert(index, (key, value));
                 None
             }
         }
     }

     #[inline]
     pub fn remove(&mut self, key: &K) -> Option<V> {
         match self.lookup_index_for(key) {
             Ok(index) => {
                 Some(self.data.remove(index).1)
             }
             Err(_) => {
                 None
             }
         }
     }

     #[inline]
     pub fn get<Q>(&self, key: &Q) -> Option<&V>
         where K: Borrow<Q>,
               Q: Ord + ?Sized
     {
         match self.lookup_index_for(key) {
             Ok(index) => {
                 unsafe {
                     Some(&self.data.get_unchecked(index).1)
                 }
             }
             Err(_) => {
                 None
             }
         }
     }

     #[inline]
     pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
         where K: Borrow<Q>,
               Q: Ord + ?Sized
     {
         match self.lookup_index_for(key) {
             Ok(index) => {
                 unsafe {
                     Some(&mut self.data.get_unchecked_mut(index).1)
                 }
             }
             Err(_) => {
                 None
             }
         }
     }

     #[inline]
     pub fn clear(&mut self) {
         self.data.clear();
     }

     /// Iterate over elements, sorted by key
     #[inline]
     pub fn iter(&self) -> ::std::slice::Iter<(K, V)> {
         self.data.iter()
     }

     /// Iterate over the keys, sorted
     #[inline]
     pub fn keys(&self) -> impl Iterator<Item = &K> + ExactSizeIterator {
         self.data.iter().map(|&(ref k, _)| k)
     }

     /// Iterate over values, sorted by key
     #[inline]
     pub fn values(&self) -> impl Iterator<Item = &V> + ExactSizeIterator {
         self.data.iter().map(|&(_, ref v)| v)
     }

     #[inline]
     pub fn len(&self) -> usize {
         self.data.len()
     }

     #[inline]
     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }

     #[inline]
     pub fn range<R>(&self, range: R) -> &[(K, V)]
         where R: RangeBounds<K>
     {
         let (start, end) = self.range_slice_indices(range);
         (&self.data[start .. end])
     }

     #[inline]
     pub fn remove_range<R>(&mut self, range: R)
         where R: RangeBounds<K>
     {
         let (start, end) = self.range_slice_indices(range);
         self.data.splice(start .. end, ::std::iter::empty());
     }

     /// Mutate all keys with the given function `f`. This mutation must not
     /// change the sort-order of keys.
     #[inline]
     pub fn offset_keys<F>(&mut self, f: F)
         where F: Fn(&mut K)
     {
         self.data.iter_mut().map(|&mut (ref mut k, _)| k).for_each(f);
     }

     /// Inserts a presorted range of elements into the map. If the range can be
     /// inserted as a whole in between to existing elements of the map, this
     /// will be faster than inserting the elements individually.
     ///
     /// It is up to the caller to make sure that the elements are sorted by key
     /// and that there are no duplicates.
     #[inline]
     pub fn insert_presorted(&mut self, mut elements: Vec<(K, V)>) {
         if elements.is_empty() {
             return
         }

         debug_assert!(elements.windows(2).all(|w| w[0].0 < w[1].0));

         let start_index = self.lookup_index_for(&elements[0].0);

         let drain = match start_index {
             Ok(index) => {
                 let mut drain = elements.drain(..);
                 self.data[index] = drain.next().unwrap();
                 drain
             }
             Err(index) => {
                 if index == self.data.len() ||
                    elements.last().unwrap().0 < self.data[index].0 {
                     // We can copy the whole range without having to mix with
                     // existing elements.
                     self.data.splice(index .. index, elements.drain(..));
                     return
                 }

                 let mut drain = elements.drain(..);
                 self.data.insert(index, drain.next().unwrap());
                 drain
             }
         };

         // Insert the rest
         for (k, v) in drain {
             self.insert(k, v);
         }
     }

     /// Looks up the key in `self.data` via `slice::binary_search()`.
     #[inline(always)]
     fn lookup_index_for<Q>(&self, key: &Q) -> Result<usize, usize>
         where K: Borrow<Q>,
               Q: Ord + ?Sized
     {
         self.data.binary_search_by(|&(ref x, _)| x.borrow().cmp(key))
     }

     #[inline]
     fn range_slice_indices<R>(&self, range: R) -> (usize, usize)
         where R: RangeBounds<K>
     {
         let start = match range.start_bound() {
             Bound::Included(ref k) => {
                 match self.lookup_index_for(k) {
                     Ok(index) | Err(index) => index
                 }
             }
             Bound::Excluded(ref k) => {
                 match self.lookup_index_for(k) {
                     Ok(index) => index + 1,
                     Err(index) => index,
                 }
             }
             Bound::Unbounded => 0,
         };

         let end = match range.end_bound() {
             Bound::Included(ref k) => {
                 match self.lookup_index_for(k) {
                     Ok(index) => index + 1,
                     Err(index) => index,
                 }
             }
             Bound::Excluded(ref k) => {
                 match self.lookup_index_for(k) {
                     Ok(index) | Err(index) => index,
                 }
             }
             Bound::Unbounded => self.data.len(),
         };

         (start, end)
     }

     #[inline]
     pub fn contains_key<Q>(&self, key: &Q) -> bool
         where K: Borrow<Q>,
               Q: Ord + ?Sized
     {
         self.get(key).is_some()
     }
 }

 impl<K: Ord, V> IntoIterator for SortedMap<K, V> {
     type Item = (K, V);
     type IntoIter = ::std::vec::IntoIter<(K, V)>;

     fn into_iter(self) -> Self::IntoIter {
         self.data.into_iter()
     }
 }

 impl<'a, K, Q, V> Index<&'a Q> for SortedMap<K, V>
     where K: Ord + Borrow<Q>,
           Q: Ord + ?Sized
 {
     type Output = V;

     fn index(&self, key: &Q) -> &Self::Output {
         self.get(key).expect("no entry found for key")
     }
 }

 impl<'a, K, Q, V> IndexMut<&'a Q> for SortedMap<K, V>
     where K: Ord + Borrow<Q>,
           Q: Ord + ?Sized
 {
     fn index_mut(&mut self, key: &Q) -> &mut Self::Output {
         self.get_mut(key).expect("no entry found for key")
     }
 }

 impl<K: Ord, V> FromIterator<(K, V)> for SortedMap<K, V> {
     fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
         let mut data: Vec<(K, V)> = iter.into_iter().collect();

         data.sort_unstable_by(|&(ref k1, _), &(ref k2, _)| k1.cmp(k2));
         data.dedup_by(|&mut (ref k1, _), &mut (ref k2, _)| {
             k1.cmp(k2) == Ordering::Equal
         });

         SortedMap {
             data
         }
     }
 }

 #[cfg(test)]
 mod tests {
     use super::SortedMap;

     #[test]
     fn test_insert_and_iter() {
         let mut map = SortedMap::new();
         let mut expected = Vec::new();

         for x in 0 .. 100 {
             assert_eq!(map.iter().cloned().collect::<Vec<_>>(), expected);

             let x = 1000 - x * 2;
             map.insert(x, x);
             expected.insert(0, (x, x));
         }
     }

     #[test]
     fn test_get_and_index() {
         let mut map = SortedMap::new();
         let mut expected = Vec::new();

         for x in 0 .. 100 {
             let x = 1000 - x;
             if x & 1 == 0 {
                 map.insert(x, x);
             }
             expected.push(x);
         }

         for mut x in expected {
             if x & 1 == 0 {
                 assert_eq!(map.get(&x), Some(&x));
                 assert_eq!(map.get_mut(&x), Some(&mut x));
                 assert_eq!(map[&x], x);
                 assert_eq!(&mut map[&x], &mut x);
             } else {
                 assert_eq!(map.get(&x), None);
                 assert_eq!(map.get_mut(&x), None);
             }
         }
     }

     #[test]
     fn test_range() {
         let mut map = SortedMap::new();
         map.insert(1, 1);
         map.insert(3, 3);
         map.insert(6, 6);
         map.insert(9, 9);

         let keys = |s: &[(_, _)]| {
             s.into_iter().map(|e| e.0).collect::<Vec<u32>>()
         };

         for start in 0 .. 11 {
             for end in 0 .. 11 {
                 if end < start {
                     continue
                 }

                 let mut expected = vec![1, 3, 6, 9];
                 expected.retain(|&x| x >= start && x < end);

                 assert_eq!(keys(map.range(start..end)), expected, "range = {}..{}", start, end);
             }
         }
     }


     #[test]
     fn test_offset_keys() {
         let mut map = SortedMap::new();
         map.insert(1, 1);
         map.insert(3, 3);
         map.insert(6, 6);

         map.offset_keys(|k| *k += 1);

         let mut expected = SortedMap::new();
         expected.insert(2, 1);
         expected.insert(4, 3);
         expected.insert(7, 6);

         assert_eq!(map, expected);
     }

     fn keys(s: SortedMap<u32, u32>) -> Vec<u32> {
         s.into_iter().map(|(k, _)| k).collect::<Vec<u32>>()
     }

     fn elements(s: SortedMap<u32, u32>) -> Vec<(u32, u32)> {
         s.into_iter().collect::<Vec<(u32, u32)>>()
     }

     #[test]
     fn test_remove_range() {
         let mut map = SortedMap::new();
         map.insert(1, 1);
         map.insert(3, 3);
         map.insert(6, 6);
         map.insert(9, 9);

         for start in 0 .. 11 {
             for end in 0 .. 11 {
                 if end < start {
                     continue
                 }

                 let mut expected = vec![1, 3, 6, 9];
                 expected.retain(|&x| x < start || x >= end);

                 let mut map = map.clone();
                 map.remove_range(start .. end);

                 assert_eq!(keys(map), expected, "range = {}..{}", start, end);
             }
         }
     }

     #[test]
     fn test_remove() {
         let mut map = SortedMap::new();
         let mut expected = Vec::new();

         for x in 0..10 {
             map.insert(x, x);
             expected.push((x, x));
         }

         for x in 0 .. 10 {
             let mut map = map.clone();
             let mut expected = expected.clone();

             assert_eq!(map.remove(&x), Some(x));
             expected.remove(x as usize);

             assert_eq!(map.iter().cloned().collect::<Vec<_>>(), expected);
         }
     }

     #[test]
     fn test_insert_presorted_non_overlapping() {
         let mut map = SortedMap::new();
         map.insert(2, 0);
         map.insert(8, 0);

         map.insert_presorted(vec![(3, 0), (7, 0)]);

         let expected = vec![2, 3, 7, 8];
         assert_eq!(keys(map), expected);
     }

     #[test]
     fn test_insert_presorted_first_elem_equal() {
         let mut map = SortedMap::new();
         map.insert(2, 2);
         map.insert(8, 8);

         map.insert_presorted(vec![(2, 0), (7, 7)]);

         let expected = vec![(2, 0), (7, 7), (8, 8)];
         assert_eq!(elements(map), expected);
     }

     #[test]
     fn test_insert_presorted_last_elem_equal() {
         let mut map = SortedMap::new();
         map.insert(2, 2);
         map.insert(8, 8);

         map.insert_presorted(vec![(3, 3), (8, 0)]);

         let expected = vec![(2, 2), (3, 3), (8, 0)];
         assert_eq!(elements(map), expected);
     }

     #[test]
     fn test_insert_presorted_shuffle() {
         let mut map = SortedMap::new();
         map.insert(2, 2);
         map.insert(7, 7);

         map.insert_presorted(vec![(1, 1), (3, 3), (8, 8)]);

         let expected = vec![(1, 1), (2, 2), (3, 3), (7, 7), (8, 8)];
         assert_eq!(elements(map), expected);
     }

     #[test]
     fn test_insert_presorted_at_end() {
         let mut map = SortedMap::new();
         map.insert(1, 1);
         map.insert(2, 2);

         map.insert_presorted(vec![(3, 3), (8, 8)]);

         let expected = vec![(1, 1), (2, 2), (3, 3), (8, 8)];
         assert_eq!(elements(map), expected);
     }
 }
	// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
	// file at the top-level directory of this distribution and at
	// http://rust-lang.org/COPYRIGHT.
	//
	// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
	// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
	// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
	// option. This file may not be copied, modified, or distributed
	// except according to those terms.

	use std::borrow::Borrow;
	use std::cmp::Ordering;
	use std::iter::FromIterator;
	use std::mem;
	use std::ops::{RangeBounds, Bound, Index, IndexMut};

	/// `SortedMap` is a data structure with similar characteristics as BTreeMap but
	/// slightly different trade-offs: lookup, insertion, and removal are O(log(N))
	/// and elements can be iterated in order cheaply.
	///
	/// `SortedMap` can be faster than a `BTreeMap` for small sizes (<50) since it
	/// stores data in a more compact way. It also supports accessing contiguous
	/// ranges of elements as a slice, and slices of already sorted elements can be
	/// inserted efficiently.
	#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default, Debug, RustcEncodable,
	RustcDecodable)]
	pub struct SortedMap<K: Ord, V> {
	data: Vec<(K, V)>
	}

	impl<K: Ord, V> SortedMap<K, V> {
	#[inline]
	pub fn new() -> SortedMap<K, V> {
	SortedMap {
	data: vec![]
	}
	}

	/// Construct a `SortedMap` from a presorted set of elements. This is faster
	/// than creating an empty map and then inserting the elements individually.
	///
	/// It is up to the caller to make sure that the elements are sorted by key
	/// and that there are no duplicates.
	#[inline]
	pub fn from_presorted_elements(elements: Vec<(K, V)>) -> SortedMap<K, V>
	{
	debug_assert!(elements.windows(2).all(\|w\| w[0].0 < w[1].0));

	SortedMap {
	data: elements
	}
	}

	#[inline]
	pub fn insert(&mut self, key: K, mut value: V) -> Option<V> {
	match self.lookup_index_for(&key) {
	Ok(index) => {
	let slot = unsafe {
	self.data.get_unchecked_mut(index)
	};
	mem::swap(&mut slot.1, &mut value);
	Some(value)
	}
	Err(index) => {
	self.data.insert(index, (key, value));
	None
	}
	}
	}

	#[inline]
	pub fn remove(&mut self, key: &K) -> Option<V> {
	match self.lookup_index_for(key) {
	Ok(index) => {
	Some(self.data.remove(index).1)
	}
	Err(_) => {
	None
	}
	}
	}

	#[inline]
	pub fn get<Q>(&self, key: &Q) -> Option<&V>
	where K: Borrow<Q>,
	Q: Ord + ?Sized
	{
	match self.lookup_index_for(key) {
	Ok(index) => {
	unsafe {
	Some(&self.data.get_unchecked(index).1)
	}
	}
	Err(_) => {
	None
	}
	}
	}

	#[inline]
	pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
	where K: Borrow<Q>,
	Q: Ord + ?Sized
	{
	match self.lookup_index_for(key) {
	Ok(index) => {
	unsafe {
	Some(&mut self.data.get_unchecked_mut(index).1)
	}
	}
	Err(_) => {
	None
	}
	}
	}

	#[inline]
	pub fn clear(&mut self) {
	self.data.clear();
	}

	/// Iterate over elements, sorted by key
	#[inline]
	pub fn iter(&self) -> ::std::slice::Iter<(K, V)> {
	self.data.iter()
	}

	/// Iterate over the keys, sorted
	#[inline]
	pub fn keys(&self) -> impl Iterator<Item = &K> + ExactSizeIterator {
	self.data.iter().map(\|&(ref k, _)\| k)
	}

	/// Iterate over values, sorted by key
	#[inline]
	pub fn values(&self) -> impl Iterator<Item = &V> + ExactSizeIterator {
	self.data.iter().map(\|&(_, ref v)\| v)
	}

	#[inline]
	pub fn len(&self) -> usize {
	self.data.len()
	}

	#[inline]
	pub fn is_empty(&self) -> bool {
	self.len() == 0
	}

	#[inline]
	pub fn range<R>(&self, range: R) -> &[(K, V)]
	where R: RangeBounds<K>
	{
	let (start, end) = self.range_slice_indices(range);
	(&self.data[start .. end])
	}

	#[inline]
	pub fn remove_range<R>(&mut self, range: R)
	where R: RangeBounds<K>
	{
	let (start, end) = self.range_slice_indices(range);
	self.data.splice(start .. end, ::std::iter::empty());
	}

	/// Mutate all keys with the given function `f`. This mutation must not
	/// change the sort-order of keys.
	#[inline]
	pub fn offset_keys<F>(&mut self, f: F)
	where F: Fn(&mut K)
	{
	self.data.iter_mut().map(\|&mut (ref mut k, _)\| k).for_each(f);
	}

	/// Inserts a presorted range of elements into the map. If the range can be
	/// inserted as a whole in between to existing elements of the map, this
	/// will be faster than inserting the elements individually.
	///
	/// It is up to the caller to make sure that the elements are sorted by key
	/// and that there are no duplicates.
	#[inline]
	pub fn insert_presorted(&mut self, mut elements: Vec<(K, V)>) {
	if elements.is_empty() {
	return
	}

	debug_assert!(elements.windows(2).all(\|w\| w[0].0 < w[1].0));

	let start_index = self.lookup_index_for(&elements[0].0);

	let drain = match start_index {
	Ok(index) => {
	let mut drain = elements.drain(..);
	self.data[index] = drain.next().unwrap();
	drain
	}
	Err(index) => {
	if index == self.data.len() \|\|
	elements.last().unwrap().0 < self.data[index].0 {
	// We can copy the whole range without having to mix with
	// existing elements.
	self.data.splice(index .. index, elements.drain(..));
	return
	}

	let mut drain = elements.drain(..);
	self.data.insert(index, drain.next().unwrap());
	drain
	}
	};

	// Insert the rest
	for (k, v) in drain {
	self.insert(k, v);
	}
	}

	/// Looks up the key in `self.data` via `slice::binary_search()`.
	#[inline(always)]
	fn lookup_index_for<Q>(&self, key: &Q) -> Result<usize, usize>
	where K: Borrow<Q>,
	Q: Ord + ?Sized
	{
	self.data.binary_search_by(\|&(ref x, _)\| x.borrow().cmp(key))
	}

	#[inline]
	fn range_slice_indices<R>(&self, range: R) -> (usize, usize)
	where R: RangeBounds<K>
	{
	let start = match range.start_bound() {
	Bound::Included(ref k) => {
	match self.lookup_index_for(k) {
	Ok(index) \| Err(index) => index
	}
	}
	Bound::Excluded(ref k) => {
	match self.lookup_index_for(k) {
	Ok(index) => index + 1,
	Err(index) => index,
	}
	}
	Bound::Unbounded => 0,
	};

	let end = match range.end_bound() {
	Bound::Included(ref k) => {
	match self.lookup_index_for(k) {
	Ok(index) => index + 1,
	Err(index) => index,
	}
	}
	Bound::Excluded(ref k) => {
	match self.lookup_index_for(k) {
	Ok(index) \| Err(index) => index,
	}
	}
	Bound::Unbounded => self.data.len(),
	};

	(start, end)
	}

	#[inline]
	pub fn contains_key<Q>(&self, key: &Q) -> bool
	where K: Borrow<Q>,
	Q: Ord + ?Sized
	{
	self.get(key).is_some()
	}
	}

	impl<K: Ord, V> IntoIterator for SortedMap<K, V> {
	type Item = (K, V);
	type IntoIter = ::std::vec::IntoIter<(K, V)>;

	fn into_iter(self) -> Self::IntoIter {
	self.data.into_iter()
	}
	}

	impl<'a, K, Q, V> Index<&'a Q> for SortedMap<K, V>
	where K: Ord + Borrow<Q>,
	Q: Ord + ?Sized
	{
	type Output = V;

	fn index(&self, key: &Q) -> &Self::Output {
	self.get(key).expect("no entry found for key")
	}
	}

	impl<'a, K, Q, V> IndexMut<&'a Q> for SortedMap<K, V>
	where K: Ord + Borrow<Q>,
	Q: Ord + ?Sized
	{
	fn index_mut(&mut self, key: &Q) -> &mut Self::Output {
	self.get_mut(key).expect("no entry found for key")
	}
	}

	impl<K: Ord, V> FromIterator<(K, V)> for SortedMap<K, V> {
	fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
	let mut data: Vec<(K, V)> = iter.into_iter().collect();

	data.sort_unstable_by(\|&(ref k1, _), &(ref k2, _)\| k1.cmp(k2));
	data.dedup_by(\|&mut (ref k1, _), &mut (ref k2, _)\| {
	k1.cmp(k2) == Ordering::Equal
	});

	SortedMap {
	data
	}
	}
	}

	#[cfg(test)]
	mod tests {
	use super::SortedMap;

	#[test]
	fn test_insert_and_iter() {
	let mut map = SortedMap::new();
	let mut expected = Vec::new();

	for x in 0 .. 100 {
	assert_eq!(map.iter().cloned().collect::<Vec<_>>(), expected);

	let x = 1000 - x * 2;
	map.insert(x, x);
	expected.insert(0, (x, x));
	}
	}

	#[test]
	fn test_get_and_index() {
	let mut map = SortedMap::new();
	let mut expected = Vec::new();

	for x in 0 .. 100 {
	let x = 1000 - x;
	if x & 1 == 0 {
	map.insert(x, x);
	}
	expected.push(x);
	}

	for mut x in expected {
	if x & 1 == 0 {
	assert_eq!(map.get(&x), Some(&x));
	assert_eq!(map.get_mut(&x), Some(&mut x));
	assert_eq!(map[&x], x);
	assert_eq!(&mut map[&x], &mut x);
	} else {
	assert_eq!(map.get(&x), None);
	assert_eq!(map.get_mut(&x), None);
	}
	}
	}

	#[test]
	fn test_range() {
	let mut map = SortedMap::new();
	map.insert(1, 1);
	map.insert(3, 3);
	map.insert(6, 6);
	map.insert(9, 9);

	let keys = \|s: &[(_, _)]\| {
	s.into_iter().map(\|e\| e.0).collect::<Vec<u32>>()
	};

	for start in 0 .. 11 {
	for end in 0 .. 11 {
	if end < start {
	continue
	}

	let mut expected = vec![1, 3, 6, 9];
	expected.retain(\|&x\| x >= start && x < end);

	assert_eq!(keys(map.range(start..end)), expected, "range = {}..{}", start, end);
	}
	}
	}


	#[test]
	fn test_offset_keys() {
	let mut map = SortedMap::new();
	map.insert(1, 1);
	map.insert(3, 3);
	map.insert(6, 6);

	map.offset_keys(\|k\| *k += 1);

	let mut expected = SortedMap::new();
	expected.insert(2, 1);
	expected.insert(4, 3);
	expected.insert(7, 6);

	assert_eq!(map, expected);
	}

	fn keys(s: SortedMap<u32, u32>) -> Vec<u32> {
	s.into_iter().map(\|(k, _)\| k).collect::<Vec<u32>>()
	}

	fn elements(s: SortedMap<u32, u32>) -> Vec<(u32, u32)> {
	s.into_iter().collect::<Vec<(u32, u32)>>()
	}

	#[test]
	fn test_remove_range() {
	let mut map = SortedMap::new();
	map.insert(1, 1);
	map.insert(3, 3);
	map.insert(6, 6);
	map.insert(9, 9);

	for start in 0 .. 11 {
	for end in 0 .. 11 {
	if end < start {
	continue
	}

	let mut expected = vec![1, 3, 6, 9];
	expected.retain(\|&x\| x < start \|\| x >= end);

	let mut map = map.clone();
	map.remove_range(start .. end);

	assert_eq!(keys(map), expected, "range = {}..{}", start, end);
	}
	}
	}

	#[test]
	fn test_remove() {
	let mut map = SortedMap::new();
	let mut expected = Vec::new();

	for x in 0..10 {
	map.insert(x, x);
	expected.push((x, x));
	}

	for x in 0 .. 10 {
	let mut map = map.clone();
	let mut expected = expected.clone();

	assert_eq!(map.remove(&x), Some(x));
	expected.remove(x as usize);

	assert_eq!(map.iter().cloned().collect::<Vec<_>>(), expected);
	}
	}

	#[test]
	fn test_insert_presorted_non_overlapping() {
	let mut map = SortedMap::new();
	map.insert(2, 0);
	map.insert(8, 0);

	map.insert_presorted(vec![(3, 0), (7, 0)]);

	let expected = vec![2, 3, 7, 8];
	assert_eq!(keys(map), expected);
	}

	#[test]
	fn test_insert_presorted_first_elem_equal() {
	let mut map = SortedMap::new();
	map.insert(2, 2);
	map.insert(8, 8);

	map.insert_presorted(vec![(2, 0), (7, 7)]);

	let expected = vec![(2, 0), (7, 7), (8, 8)];
	assert_eq!(elements(map), expected);
	}

	#[test]
	fn test_insert_presorted_last_elem_equal() {
	let mut map = SortedMap::new();
	map.insert(2, 2);
	map.insert(8, 8);

	map.insert_presorted(vec![(3, 3), (8, 0)]);

	let expected = vec![(2, 2), (3, 3), (8, 0)];
	assert_eq!(elements(map), expected);
	}

	#[test]
	fn test_insert_presorted_shuffle() {
	let mut map = SortedMap::new();
	map.insert(2, 2);
	map.insert(7, 7);

	map.insert_presorted(vec![(1, 1), (3, 3), (8, 8)]);

	let expected = vec![(1, 1), (2, 2), (3, 3), (7, 7), (8, 8)];
	assert_eq!(elements(map), expected);
	}

	#[test]
	fn test_insert_presorted_at_end() {
	let mut map = SortedMap::new();
	map.insert(1, 1);
	map.insert(2, 2);

	map.insert_presorted(vec![(3, 3), (8, 8)]);

	let expected = vec![(1, 1), (2, 2), (3, 3), (8, 8)];
	assert_eq!(elements(map), expected);
	}
	}