1 use std::borrow::Borrow;
2 use std::cmp::Ordering;
3 use std::iter::FromIterator;
5 use std::ops::{Bound, Index, IndexMut, RangeBounds};
9 pub use index_map::SortedIndexMultiMap;
11 /// `SortedMap` is a data structure with similar characteristics as BTreeMap but
12 /// slightly different trade-offs: lookup, insertion, and removal are O(log(N))
13 /// and elements can be iterated in order cheaply.
15 /// `SortedMap` can be faster than a `BTreeMap` for small sizes (<50) since it
16 /// stores data in a more compact way. It also supports accessing contiguous
17 /// ranges of elements as a slice, and slices of already sorted elements can be
18 /// inserted efficiently.
19 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default, Debug, Encodable, Decodable)]
20 pub struct SortedMap<K: Ord, V> {
24 impl<K: Ord, V> SortedMap<K, V> {
26 pub fn new() -> SortedMap<K, V> {
27 SortedMap { data: vec![] }
30 /// Construct a `SortedMap` from a presorted set of elements. This is faster
31 /// than creating an empty map and then inserting the elements individually.
33 /// It is up to the caller to make sure that the elements are sorted by key
34 /// and that there are no duplicates.
36 pub fn from_presorted_elements(elements: Vec<(K, V)>) -> SortedMap<K, V> {
37 debug_assert!(elements.windows(2).all(|w| w[0].0 < w[1].0));
39 SortedMap { data: elements }
43 pub fn insert(&mut self, key: K, mut value: V) -> Option<V> {
44 match self.lookup_index_for(&key) {
46 let slot = unsafe { self.data.get_unchecked_mut(index) };
47 mem::swap(&mut slot.1, &mut value);
51 self.data.insert(index, (key, value));
58 pub fn remove(&mut self, key: &K) -> Option<V> {
59 match self.lookup_index_for(key) {
60 Ok(index) => Some(self.data.remove(index).1),
66 pub fn get<Q>(&self, key: &Q) -> Option<&V>
71 match self.lookup_index_for(key) {
72 Ok(index) => unsafe { Some(&self.data.get_unchecked(index).1) },
78 pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
83 match self.lookup_index_for(key) {
84 Ok(index) => unsafe { Some(&mut self.data.get_unchecked_mut(index).1) },
90 pub fn clear(&mut self) {
94 /// Iterate over elements, sorted by key
96 pub fn iter(&self) -> ::std::slice::Iter<'_, (K, V)> {
100 /// Iterate over the keys, sorted
102 pub fn keys(&self) -> impl Iterator<Item = &K> + ExactSizeIterator + DoubleEndedIterator {
103 self.data.iter().map(|&(ref k, _)| k)
106 /// Iterate over values, sorted by key
108 pub fn values(&self) -> impl Iterator<Item = &V> + ExactSizeIterator + DoubleEndedIterator {
109 self.data.iter().map(|&(_, ref v)| v)
113 pub fn len(&self) -> usize {
118 pub fn is_empty(&self) -> bool {
123 pub fn range<R>(&self, range: R) -> &[(K, V)]
127 let (start, end) = self.range_slice_indices(range);
128 &self.data[start..end]
132 pub fn remove_range<R>(&mut self, range: R)
136 let (start, end) = self.range_slice_indices(range);
137 self.data.splice(start..end, ::std::iter::empty());
140 /// Mutate all keys with the given function `f`. This mutation must not
141 /// change the sort-order of keys.
143 pub fn offset_keys<F>(&mut self, f: F)
147 self.data.iter_mut().map(|&mut (ref mut k, _)| k).for_each(f);
150 /// Inserts a presorted range of elements into the map. If the range can be
151 /// inserted as a whole in between to existing elements of the map, this
152 /// will be faster than inserting the elements individually.
154 /// It is up to the caller to make sure that the elements are sorted by key
155 /// and that there are no duplicates.
157 pub fn insert_presorted(&mut self, mut elements: Vec<(K, V)>) {
158 if elements.is_empty() {
162 debug_assert!(elements.windows(2).all(|w| w[0].0 < w[1].0));
164 let start_index = self.lookup_index_for(&elements[0].0);
166 let drain = match start_index {
168 let mut drain = elements.drain(..);
169 self.data[index] = drain.next().unwrap();
173 if index == self.data.len() || elements.last().unwrap().0 < self.data[index].0 {
174 // We can copy the whole range without having to mix with
175 // existing elements.
176 self.data.splice(index..index, elements.drain(..));
180 let mut drain = elements.drain(..);
181 self.data.insert(index, drain.next().unwrap());
187 for (k, v) in drain {
192 /// Looks up the key in `self.data` via `slice::binary_search()`.
194 fn lookup_index_for<Q>(&self, key: &Q) -> Result<usize, usize>
199 self.data.binary_search_by(|&(ref x, _)| x.borrow().cmp(key))
203 fn range_slice_indices<R>(&self, range: R) -> (usize, usize)
207 let start = match range.start_bound() {
208 Bound::Included(ref k) => match self.lookup_index_for(k) {
209 Ok(index) | Err(index) => index,
211 Bound::Excluded(ref k) => match self.lookup_index_for(k) {
212 Ok(index) => index + 1,
215 Bound::Unbounded => 0,
218 let end = match range.end_bound() {
219 Bound::Included(ref k) => match self.lookup_index_for(k) {
220 Ok(index) => index + 1,
223 Bound::Excluded(ref k) => match self.lookup_index_for(k) {
224 Ok(index) | Err(index) => index,
226 Bound::Unbounded => self.data.len(),
233 pub fn contains_key<Q>(&self, key: &Q) -> bool
238 self.get(key).is_some()
242 impl<K: Ord, V> IntoIterator for SortedMap<K, V> {
244 type IntoIter = ::std::vec::IntoIter<(K, V)>;
246 fn into_iter(self) -> Self::IntoIter {
247 self.data.into_iter()
251 impl<'a, K, Q, V> Index<&'a Q> for SortedMap<K, V>
258 fn index(&self, key: &Q) -> &Self::Output {
259 self.get(key).expect("no entry found for key")
263 impl<'a, K, Q, V> IndexMut<&'a Q> for SortedMap<K, V>
268 fn index_mut(&mut self, key: &Q) -> &mut Self::Output {
269 self.get_mut(key).expect("no entry found for key")
273 impl<K: Ord, V> FromIterator<(K, V)> for SortedMap<K, V> {
274 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
275 let mut data: Vec<(K, V)> = iter.into_iter().collect();
277 data.sort_unstable_by(|&(ref k1, _), &(ref k2, _)| k1.cmp(k2));
278 data.dedup_by(|&mut (ref k1, _), &mut (ref k2, _)| k1.cmp(k2) == Ordering::Equal);