+use crate::stable_hasher::{HashStable, StableHasher};
use std::borrow::Borrow;
use std::cmp::Ordering;
use std::iter::FromIterator;
/// 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, Encodable, Decodable)]
-pub struct SortedMap<K: Ord, V> {
+#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Encodable, Decodable)]
+pub struct SortedMap<K, V> {
data: Vec<(K, V)>,
}
-impl<K: Ord, V> SortedMap<K, V> {
+impl<K, V> Default for SortedMap<K, V> {
+ #[inline]
+ fn default() -> SortedMap<K, V> {
+ SortedMap { data: Vec::new() }
+ }
+}
+
+impl<K, V> SortedMap<K, V> {
#[inline]
- pub fn new() -> SortedMap<K, V> {
- SortedMap { data: vec![] }
+ pub const fn new() -> SortedMap<K, V> {
+ SortedMap { data: Vec::new() }
}
+}
+impl<K: Ord, V> SortedMap<K, V> {
/// Construct a `SortedMap` from a presorted set of elements. This is faster
/// than creating an empty map and then inserting the elements individually.
///
R: RangeBounds<K>,
{
let start = match range.start_bound() {
- Bound::Included(k) => match self.lookup_index_for(k) {
+ Bound::Included(ref k) => match self.lookup_index_for(k) {
Ok(index) | Err(index) => index,
},
- Bound::Excluded(k) => match self.lookup_index_for(k) {
+ Bound::Excluded(ref k) => match self.lookup_index_for(k) {
Ok(index) => index + 1,
Err(index) => index,
},
};
let end = match range.end_bound() {
- Bound::Included(k) => match self.lookup_index_for(k) {
+ Bound::Included(ref k) => match self.lookup_index_for(k) {
Ok(index) => index + 1,
Err(index) => index,
},
- Bound::Excluded(k) => match self.lookup_index_for(k) {
+ Bound::Excluded(ref k) => match self.lookup_index_for(k) {
Ok(index) | Err(index) => index,
},
Bound::Unbounded => self.data.len(),
}
}
+impl<K: HashStable<CTX>, V: HashStable<CTX>, CTX> HashStable<CTX> for SortedMap<K, V> {
+ #[inline]
+ fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
+ self.data.hash_stable(ctx, hasher);
+ }
+}
+
#[cfg(test)]
mod tests;