use super::range_wrapper::RangeStartWrapper;
use crate::range_wrapper::RangeEndWrapper;
use crate::std_ext::*;
use alloc::collections::BTreeMap;
use core::cmp::Ordering;
use core::fmt::{self, Debug};
use core::iter::FromIterator;
use core::ops::{Bound, Range};
use core::prelude::v1::*;
#[cfg(feature = "serde1")]
use core::marker::PhantomData;
#[cfg(feature = "serde1")]
use serde::{
de::{Deserialize, Deserializer, SeqAccess, Visitor},
ser::{Serialize, Serializer},
};
#[derive(Clone)]
pub struct RangeMap<K, V> {
pub(crate) btm: BTreeMap<RangeStartWrapper<K>, V>,
}
impl<K, V> Default for RangeMap<K, V>
where
K: Ord + Clone,
V: Eq + Clone,
{
fn default() -> Self {
Self::new()
}
}
impl<K, V> PartialEq for RangeMap<K, V>
where
K: PartialEq,
V: PartialEq,
{
fn eq(&self, other: &RangeMap<K, V>) -> bool {
self.btm == other.btm
}
}
impl<K, V> PartialOrd for RangeMap<K, V>
where
K: PartialOrd,
V: PartialOrd,
{
#[inline]
fn partial_cmp(&self, other: &RangeMap<K, V>) -> Option<Ordering> {
self.btm.partial_cmp(&other.btm)
}
}
impl<K, V> Ord for RangeMap<K, V>
where
K: Ord,
V: Ord,
{
#[inline]
fn cmp(&self, other: &RangeMap<K, V>) -> Ordering {
self.btm.cmp(&other.btm)
}
}
impl<K, V> Eq for RangeMap<K, V>
where
K: Eq,
V: Eq,
{
}
impl<K, V> RangeMap<K, V>
where
K: Ord + Clone,
V: Eq + Clone,
{
#[cfg(feature = "const_fn")]
pub const fn new() -> Self {
RangeMap {
btm: BTreeMap::new(),
}
}
#[cfg(not(feature = "const_fn"))]
pub fn new() -> Self {
RangeMap {
btm: BTreeMap::new(),
}
}
pub fn get(&self, key: &K) -> Option<&V> {
self.get_key_value(key).map(|(_range, value)| value)
}
pub fn get_key_value(&self, key: &K) -> Option<(&Range<K>, &V)> {
let key_as_start = RangeStartWrapper::new(key.clone()..key.clone());
self.btm
.range((Bound::Unbounded, Bound::Included(key_as_start)))
.next_back()
.filter(|(start_wrapper, _value)| {
start_wrapper.end_wrapper.range.contains(key)
})
.map(|(start_wrapper, value)| (&start_wrapper.end_wrapper.range, value))
}
pub fn contains_key(&self, key: &K) -> bool {
self.get(key).is_some()
}
pub fn iter(&self) -> Iter<'_, K, V> {
Iter {
inner: self.btm.iter(),
}
}
pub fn clear(&mut self) {
self.btm.clear();
}
pub fn len(&self) -> usize {
self.btm.len()
}
pub fn is_empty(&self) -> bool {
self.btm.is_empty()
}
pub fn insert(&mut self, range: Range<K>, value: V) {
assert!(range.start < range.end);
let mut new_start_wrapper: RangeStartWrapper<K> = RangeStartWrapper::new(range);
let new_value = value;
let mut candidates = self
.btm
.range::<RangeStartWrapper<K>, (Bound<&RangeStartWrapper<K>>, Bound<&RangeStartWrapper<K>>)>((
Bound::Unbounded,
Bound::Included(&new_start_wrapper),
))
.rev()
.take(2)
.filter(|(stored_start_wrapper, _stored_value)| {
stored_start_wrapper
.end_wrapper
.range
.touches(&new_start_wrapper.end_wrapper.range)
});
if let Some(mut candidate) = candidates.next() {
if let Some(another_candidate) = candidates.next() {
candidate = another_candidate;
}
let (stored_start_wrapper, stored_value) = (candidate.0.clone(), candidate.1.clone());
self.adjust_touching_ranges_for_insert(
stored_start_wrapper,
stored_value,
&mut new_start_wrapper.end_wrapper.range,
&new_value,
);
}
let new_range_end_as_start = RangeStartWrapper::new(
new_start_wrapper.end_wrapper.range.end.clone()
..new_start_wrapper.end_wrapper.range.end.clone(),
);
while let Some((stored_start_wrapper, stored_value)) = self
.btm
.range::<RangeStartWrapper<K>, (Bound<&RangeStartWrapper<K>>, Bound<&RangeStartWrapper<K>>)>((
Bound::Included(&new_start_wrapper),
Bound::Included(&new_range_end_as_start),
))
.next()
{
#[allow(clippy::suspicious_operation_groupings)]
if stored_start_wrapper.end_wrapper.range.start
== new_start_wrapper.end_wrapper.range.end
&& *stored_value != new_value
{
break;
}
let stored_start_wrapper = stored_start_wrapper.clone();
let stored_value = stored_value.clone();
self.adjust_touching_ranges_for_insert(
stored_start_wrapper,
stored_value,
&mut new_start_wrapper.end_wrapper.range,
&new_value,
);
}
self.btm.insert(new_start_wrapper, new_value);
}
pub fn remove(&mut self, range: Range<K>) {
assert!(range.start < range.end);
let start_wrapper: RangeStartWrapper<K> = RangeStartWrapper::new(range);
let range = &start_wrapper.end_wrapper.range;
if let Some((stored_start_wrapper, stored_value)) = self
.btm
.range::<RangeStartWrapper<K>, (Bound<&RangeStartWrapper<K>>, Bound<&RangeStartWrapper<K>>)>((Bound::Unbounded, Bound::Included(&start_wrapper)))
.next_back()
.filter(|(stored_start_wrapper, _stored_value)| {
stored_start_wrapper
.end_wrapper
.range
.overlaps(range)
})
.map(|(stored_start_wrapper, stored_value)| {
(stored_start_wrapper.clone(), stored_value.clone())
})
{
self.adjust_overlapping_ranges_for_remove(
stored_start_wrapper,
stored_value,
range,
);
}
let new_range_end_as_start = RangeStartWrapper::new(range.end.clone()..range.end.clone());
while let Some((stored_start_wrapper, stored_value)) = self
.btm
.range::<RangeStartWrapper<K>, (Bound<&RangeStartWrapper<K>>, Bound<&RangeStartWrapper<K>>)>((
Bound::Excluded(&start_wrapper),
Bound::Excluded(&new_range_end_as_start),
))
.next()
.map(|(stored_start_wrapper, stored_value)| {
(stored_start_wrapper.clone(), stored_value.clone())
})
{
self.adjust_overlapping_ranges_for_remove(
stored_start_wrapper,
stored_value,
range,
);
}
}
fn adjust_touching_ranges_for_insert(
&mut self,
stored_start_wrapper: RangeStartWrapper<K>,
stored_value: V,
new_range: &mut Range<K>,
new_value: &V,
) {
use core::cmp::{max, min};
if stored_value == *new_value {
new_range.start = min(&new_range.start, &stored_start_wrapper.start).clone();
new_range.end = max(&new_range.end, &stored_start_wrapper.end).clone();
self.btm.remove(&stored_start_wrapper);
} else {
if new_range.overlaps(&stored_start_wrapper.range) {
self.btm.remove(&stored_start_wrapper);
if stored_start_wrapper.start < new_range.start {
self.btm.insert(
RangeStartWrapper::new(
stored_start_wrapper.end_wrapper.range.start..new_range.start.clone(),
),
stored_value.clone(),
);
}
if stored_start_wrapper.end_wrapper.range.end > new_range.end {
self.btm.insert(
RangeStartWrapper::new(
new_range.end.clone()..stored_start_wrapper.end_wrapper.range.end,
),
stored_value,
);
}
} else {
}
}
}
fn adjust_overlapping_ranges_for_remove(
&mut self,
stored: RangeStartWrapper<K>,
stored_value: V,
range_to_remove: &Range<K>,
) {
self.btm.remove(&stored);
let stored_range = stored.end_wrapper;
if stored_range.start < range_to_remove.start {
self.btm.insert(
RangeStartWrapper::new(stored_range.range.start..range_to_remove.start.clone()),
stored_value.clone(),
);
}
if stored_range.range.end > range_to_remove.end {
self.btm.insert(
RangeStartWrapper::new(range_to_remove.end.clone()..stored_range.range.end),
stored_value,
);
}
}
pub fn gaps<'a>(&'a self, outer_range: &'a Range<K>) -> Gaps<'a, K, V> {
Gaps {
outer_range,
keys: self.btm.keys(),
candidate_start: &outer_range.start,
}
}
pub fn overlapping<'a>(&'a self, range: &'a Range<K>) -> Overlapping<K, V> {
let start_sliver = RangeEndWrapper::new(range.start.clone()..range.start.clone());
let btm_range_iter = self
.btm
.range::<RangeEndWrapper<K>, (Bound<&RangeEndWrapper<K>>, Bound<_>)>((
Bound::Excluded(&start_sliver),
Bound::Unbounded,
));
Overlapping {
query_range: range,
btm_range_iter,
}
}
pub fn overlaps(&self, range: &Range<K>) -> bool {
self.overlapping(range).next().is_some()
}
}
pub struct Iter<'a, K, V> {
inner: alloc::collections::btree_map::Iter<'a, RangeStartWrapper<K>, V>,
}
impl<'a, K, V> Iterator for Iter<'a, K, V>
where
K: 'a,
V: 'a,
{
type Item = (&'a Range<K>, &'a V);
fn next(&mut self) -> Option<(&'a Range<K>, &'a V)> {
self.inner
.next()
.map(|(by_start, v)| (&by_start.end_wrapper.range, v))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
pub struct IntoIter<K, V> {
inner: alloc::collections::btree_map::IntoIter<RangeStartWrapper<K>, V>,
}
impl<K, V> IntoIterator for RangeMap<K, V> {
type Item = (Range<K>, V);
type IntoIter = IntoIter<K, V>;
fn into_iter(self) -> Self::IntoIter {
IntoIter {
inner: self.btm.into_iter(),
}
}
}
impl<K, V> Iterator for IntoIter<K, V> {
type Item = (Range<K>, V);
fn next(&mut self) -> Option<(Range<K>, V)> {
self.inner
.next()
.map(|(by_start, v)| (by_start.end_wrapper.range, v))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl<K: Debug, V: Debug> Debug for RangeMap<K, V>
where
K: Ord + Clone,
V: Eq + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
impl<K, V> FromIterator<(Range<K>, V)> for RangeMap<K, V>
where
K: Ord + Clone,
V: Eq + Clone,
{
fn from_iter<T: IntoIterator<Item = (Range<K>, V)>>(iter: T) -> Self {
let mut range_map = RangeMap::new();
range_map.extend(iter);
range_map
}
}
impl<K, V> Extend<(Range<K>, V)> for RangeMap<K, V>
where
K: Ord + Clone,
V: Eq + Clone,
{
fn extend<T: IntoIterator<Item = (Range<K>, V)>>(&mut self, iter: T) {
iter.into_iter().for_each(move |(k, v)| {
self.insert(k, v);
})
}
}
#[cfg(feature = "serde1")]
impl<K, V> Serialize for RangeMap<K, V>
where
K: Ord + Clone + Serialize,
V: Eq + Clone + Serialize,
{
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
use serde::ser::SerializeSeq;
let mut seq = serializer.serialize_seq(Some(self.btm.len()))?;
for (k, v) in self.iter() {
seq.serialize_element(&((&k.start, &k.end), &v))?;
}
seq.end()
}
}
#[cfg(feature = "serde1")]
impl<'de, K, V> Deserialize<'de> for RangeMap<K, V>
where
K: Ord + Clone + Deserialize<'de>,
V: Eq + Clone + Deserialize<'de>,
{
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
deserializer.deserialize_seq(RangeMapVisitor::new())
}
}
#[cfg(feature = "serde1")]
struct RangeMapVisitor<K, V> {
marker: PhantomData<fn() -> RangeMap<K, V>>,
}
#[cfg(feature = "serde1")]
impl<K, V> RangeMapVisitor<K, V> {
fn new() -> Self {
RangeMapVisitor {
marker: PhantomData,
}
}
}
#[cfg(feature = "serde1")]
impl<'de, K, V> Visitor<'de> for RangeMapVisitor<K, V>
where
K: Ord + Clone + Deserialize<'de>,
V: Eq + Clone + Deserialize<'de>,
{
type Value = RangeMap<K, V>;
fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
formatter.write_str("RangeMap")
}
fn visit_seq<A>(self, mut access: A) -> Result<Self::Value, A::Error>
where
A: SeqAccess<'de>,
{
let mut range_map = RangeMap::new();
while let Some(((start, end), value)) = access.next_element()? {
range_map.insert(start..end, value);
}
Ok(range_map)
}
}
pub struct Gaps<'a, K, V> {
outer_range: &'a Range<K>,
keys: alloc::collections::btree_map::Keys<'a, RangeStartWrapper<K>, V>,
candidate_start: &'a K,
}
impl<'a, K, V> core::iter::FusedIterator for Gaps<'a, K, V> where K: Ord + Clone {}
impl<'a, K, V> Iterator for Gaps<'a, K, V>
where
K: Ord + Clone,
{
type Item = Range<K>;
fn next(&mut self) -> Option<Self::Item> {
for item in &mut self.keys {
let range = &item.range;
if range.end <= *self.candidate_start {
} else if range.start <= *self.candidate_start {
self.candidate_start = &range.end;
} else if range.start < self.outer_range.end {
let gap = self.candidate_start.clone()..range.start.clone();
self.candidate_start = &range.end;
return Some(gap);
}
}
if *self.candidate_start < self.outer_range.end {
let gap = self.candidate_start.clone()..self.outer_range.end.clone();
self.candidate_start = &self.outer_range.end;
Some(gap)
} else {
None
}
}
}
pub struct Overlapping<'a, K, V> {
query_range: &'a Range<K>,
btm_range_iter: alloc::collections::btree_map::Range<'a, RangeStartWrapper<K>, V>,
}
impl<'a, K, V> core::iter::FusedIterator for Overlapping<'a, K, V> where K: Ord + Clone {}
impl<'a, K, V> Iterator for Overlapping<'a, K, V>
where
K: Ord + Clone,
{
type Item = (&'a Range<K>, &'a V);
fn next(&mut self) -> Option<Self::Item> {
if let Some((k, v)) = self.btm_range_iter.next() {
if k.start < self.query_range.end {
Some((&k.range, v))
} else {
None
}
} else {
None
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use alloc::{format, vec, vec::Vec};
trait RangeMapExt<K, V> {
fn to_vec(&self) -> Vec<(Range<K>, V)>;
}
impl<K, V> RangeMapExt<K, V> for RangeMap<K, V>
where
K: Ord + Clone,
V: Eq + Clone,
{
fn to_vec(&self) -> Vec<(Range<K>, V)> {
self.iter().map(|(kr, v)| (kr.clone(), v.clone())).collect()
}
}
#[test]
fn empty_map_is_empty() {
let range_map: RangeMap<u32, bool> = RangeMap::new();
assert_eq!(range_map.to_vec(), vec![]);
}
#[test]
fn insert_into_empty_map() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(0..50, false);
assert_eq!(range_map.to_vec(), vec![(0..50, false)]);
}
#[test]
fn new_same_value_immediately_following_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(1..3, false);
range_map.insert(3..5, false);
assert_eq!(range_map.to_vec(), vec![(1..5, false)]);
}
#[test]
fn new_different_value_immediately_following_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(1..3, false);
range_map.insert(3..5, true);
assert_eq!(range_map.to_vec(), vec![(1..3, false), (3..5, true)]);
}
#[test]
fn new_same_value_overlapping_end_of_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(1..4, false);
range_map.insert(3..5, false);
assert_eq!(range_map.to_vec(), vec![(1..5, false)]);
}
#[test]
fn new_different_value_overlapping_end_of_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(1..4, false);
range_map.insert(3..5, true);
assert_eq!(range_map.to_vec(), vec![(1..3, false), (3..5, true)]);
}
#[test]
fn new_same_value_immediately_preceding_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(3..5, false);
range_map.insert(1..3, false);
assert_eq!(range_map.to_vec(), vec![(1..5, false)]);
}
#[test]
fn new_different_value_immediately_preceding_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(3..5, true);
range_map.insert(1..3, false);
assert_eq!(range_map.to_vec(), vec![(1..3, false), (3..5, true)]);
}
#[test]
fn new_same_value_wholly_inside_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(1..5, false);
range_map.insert(2..4, false);
assert_eq!(range_map.to_vec(), vec![(1..5, false)]);
}
#[test]
fn new_different_value_wholly_inside_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(1..5, true);
range_map.insert(2..4, false);
assert_eq!(
range_map.to_vec(),
vec![(1..2, true), (2..4, false), (4..5, true)]
);
}
#[test]
fn replace_at_end_of_existing_range_should_coalesce() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(1..3, false);
range_map.insert(3..5, true);
range_map.insert(3..5, false);
assert_eq!(range_map.to_vec(), vec![(1..5, false)]);
}
#[test]
fn lots_of_interesting_ranges() {
use crate::dense::DenseU32RangeMap;
use permutator::Permutation;
let mut ranges_with_values = [
(2..3, false),
(2..3, false),
(2..3, true),
(3..5, true),
(4..6, true),
(5..7, true),
(2..6, true),
];
ranges_with_values.permutation().for_each(|permutation| {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
let mut dense: DenseU32RangeMap<bool> = DenseU32RangeMap::new();
for (k, v) in permutation {
range_map.insert(k.clone(), v);
#[allow(clippy::range_minus_one)]
dense.insert(k.start..=(k.end - 1), v);
let sparse = range_map.to_vec();
let dense = dense.to_end_exclusive_vec();
assert_eq!(sparse, dense);
}
});
}
#[test]
fn get() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(0..50, false);
assert_eq!(range_map.get(&49), Some(&false));
assert_eq!(range_map.get(&50), None);
}
#[test]
fn get_key_value() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(0..50, false);
assert_eq!(range_map.get_key_value(&49), Some((&(0..50), &false)));
assert_eq!(range_map.get_key_value(&50), None);
}
#[test]
fn remove_from_empty_map() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.remove(0..50);
assert_eq!(range_map.to_vec(), vec![]);
}
#[test]
fn remove_non_covered_range_before_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(25..75, false);
range_map.remove(0..25);
assert_eq!(range_map.to_vec(), vec![(25..75, false)]);
}
#[test]
fn remove_non_covered_range_after_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(25..75, false);
range_map.remove(75..100);
assert_eq!(range_map.to_vec(), vec![(25..75, false)]);
}
#[test]
fn remove_overlapping_start_of_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(25..75, false);
range_map.remove(0..30);
assert_eq!(range_map.to_vec(), vec![(30..75, false)]);
}
#[test]
fn remove_middle_of_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(25..75, false);
range_map.remove(30..70);
assert_eq!(range_map.to_vec(), vec![(25..30, false), (70..75, false)]);
}
#[test]
fn remove_overlapping_end_of_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(25..75, false);
range_map.remove(70..100);
assert_eq!(range_map.to_vec(), vec![(25..70, false)]);
}
#[test]
fn remove_exactly_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(25..75, false);
range_map.remove(25..75);
assert_eq!(range_map.to_vec(), vec![]);
}
#[test]
fn remove_superset_of_stored() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(25..75, false);
range_map.remove(0..100);
assert_eq!(range_map.to_vec(), vec![]);
}
#[test]
fn whole_range_is_a_gap() {
let range_map: RangeMap<u32, ()> = RangeMap::new();
let outer_range = 1..8;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(1..8));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn whole_range_is_covered_exactly() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(1..6, ());
let outer_range = 1..6;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn item_before_outer_range() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(1..3, ());
let outer_range = 5..8;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(5..8));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn item_touching_start_of_outer_range() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(1..5, ());
let outer_range = 5..8;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(5..8));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn item_overlapping_start_of_outer_range() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(1..6, ());
let outer_range = 5..8;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(6..8));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn item_starting_at_start_of_outer_range() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(5..6, ());
let outer_range = 5..8;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(6..8));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn items_floating_inside_outer_range() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(5..6, ());
range_map.insert(3..4, ());
let outer_range = 1..8;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(1..3));
assert_eq!(gaps.next(), Some(4..5));
assert_eq!(gaps.next(), Some(6..8));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn item_ending_at_end_of_outer_range() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(7..8, ());
let outer_range = 5..8;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(5..7));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn item_overlapping_end_of_outer_range() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(4..6, ());
let outer_range = 2..5;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(2..4));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn item_touching_end_of_outer_range() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(4..8, ());
let outer_range = 1..4;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(1..4));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn item_after_outer_range() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(6..7, ());
let outer_range = 1..4;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(1..4));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn empty_outer_range_with_items_away_from_both_sides() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(1..3, ());
range_map.insert(5..7, ());
let outer_range = 4..4;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn empty_outer_range_with_items_touching_both_sides() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(2..4, ());
range_map.insert(4..6, ());
let outer_range = 4..4;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn empty_outer_range_with_item_straddling() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(2..5, ());
let outer_range = 4..4;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn no_empty_gaps() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(4..5, true);
range_map.insert(3..4, false);
let outer_range = 1..8;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(1..3));
assert_eq!(gaps.next(), Some(5..8));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn adjacent_small_items() {
let mut range_map: RangeMap<u8, bool> = RangeMap::new();
range_map.insert(0..1, false);
range_map.insert(1..2, true);
range_map.insert(253..254, false);
range_map.insert(254..255, true);
let outer_range = 0..255;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(2..253));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn outer_range_lies_within_first_of_two_stored_ranges() {
let mut range_map: RangeMap<u64, ()> = RangeMap::new();
range_map.insert(0..5, ());
range_map.insert(6..8, ());
let outer_range: Range<u64> = 1..3;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), None);
}
#[test]
fn overlapping_with_empty_map() {
let range_map: RangeMap<u32, ()> = RangeMap::new();
let query_range = 1..8;
let mut overlapping = range_map.overlapping(&query_range);
assert_eq!(overlapping.next(), None);
assert_eq!(overlapping.next(), None);
}
#[test]
fn overlapping_partial_edges_complete_middle() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(0..2, ());
range_map.insert(3..4, ());
range_map.insert(5..7, ());
let query_range = 1..6;
let mut overlapping = range_map.overlapping(&query_range);
assert_eq!(overlapping.next(), Some((&(0..2), &())));
assert_eq!(overlapping.next(), Some((&(3..4), &())));
assert_eq!(overlapping.next(), Some((&(5..7), &())));
assert_eq!(overlapping.next(), None);
assert_eq!(overlapping.next(), None);
}
#[test]
fn overlapping_non_overlapping_edges_complete_middle() {
let mut range_map: RangeMap<u32, ()> = RangeMap::new();
range_map.insert(0..2, ());
range_map.insert(3..4, ());
range_map.insert(5..7, ());
let query_range = 2..5;
let mut overlapping = range_map.overlapping(&query_range);
assert_eq!(overlapping.next(), Some((&(3..4), &())));
assert_eq!(overlapping.next(), None);
assert_eq!(overlapping.next(), None);
}
#[test]
fn map_debug_repr_looks_right() {
let mut map: RangeMap<u32, ()> = RangeMap::new();
assert_eq!(format!("{:?}", map), "{}");
map.insert(2..5, ());
assert_eq!(format!("{:?}", map), "{2..5: ()}");
map.insert(6..7, ());
map.insert(8..9, ());
assert_eq!(format!("{:?}", map), "{2..5: (), 6..7: (), 8..9: ()}");
}
#[test]
fn into_iter_matches_iter() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(1..3, false);
range_map.insert(3..5, true);
let cloned = range_map.to_vec();
let consumed = range_map.into_iter().collect::<Vec<_>>();
assert_eq!(cloned, vec![(1..3, false), (3..5, true)]);
assert_eq!(cloned, consumed);
}
#[cfg(feature = "serde1")]
#[test]
fn serialization() {
let mut range_map: RangeMap<u32, bool> = RangeMap::new();
range_map.insert(1..3, false);
range_map.insert(5..7, true);
let output = serde_json::to_string(&range_map).expect("Failed to serialize");
assert_eq!(output, "[[[1,3],false],[[5,7],true]]");
}
#[cfg(feature = "serde1")]
#[test]
fn deserialization() {
let input = "[[[1,3],false],[[5,7],true]]";
let range_map: RangeMap<u32, bool> =
serde_json::from_str(input).expect("Failed to deserialize");
let reserialized = serde_json::to_string(&range_map).expect("Failed to re-serialize");
assert_eq!(reserialized, input);
}
#[cfg(feature = "const_fn")]
const _MAP: RangeMap<u32, bool> = RangeMap::new();
}