use super::range_wrapper::RangeInclusiveStartWrapper;
use crate::range_wrapper::RangeInclusiveEndWrapper;
use crate::std_ext::*;
use alloc::collections::BTreeMap;
use core::cmp::Ordering;
use core::fmt::{self, Debug};
use core::iter::FromIterator;
use core::marker::PhantomData;
use core::ops::{RangeFrom, RangeInclusive};
use core::prelude::v1::*;
#[cfg(feature = "serde1")]
use serde::{
de::{Deserialize, Deserializer, SeqAccess, Visitor},
ser::{Serialize, Serializer},
};
#[derive(Clone)]
pub struct RangeInclusiveMap<K, V, StepFnsT = K> {
pub(crate) btm: BTreeMap<RangeInclusiveStartWrapper<K>, V>,
_phantom: PhantomData<StepFnsT>,
}
impl<K, V> Default for RangeInclusiveMap<K, V, K>
where
K: Ord + Clone + StepLite,
V: Eq + Clone,
{
fn default() -> Self {
Self::new()
}
}
impl<K, V, StepFnsT> PartialEq for RangeInclusiveMap<K, V, StepFnsT>
where
K: PartialEq,
V: PartialEq,
{
fn eq(&self, other: &RangeInclusiveMap<K, V, StepFnsT>) -> bool {
self.btm == other.btm
}
}
impl<K, V, StepFnsT> Eq for RangeInclusiveMap<K, V, StepFnsT>
where
K: Eq,
V: Eq,
{
}
impl<K, V, StepFnsT> PartialOrd for RangeInclusiveMap<K, V, StepFnsT>
where
K: PartialOrd,
V: PartialOrd,
{
#[inline]
fn partial_cmp(&self, other: &RangeInclusiveMap<K, V, StepFnsT>) -> Option<Ordering> {
self.btm.partial_cmp(&other.btm)
}
}
impl<K, V, StepFnsT> Ord for RangeInclusiveMap<K, V, StepFnsT>
where
K: Ord,
V: Ord,
{
#[inline]
fn cmp(&self, other: &RangeInclusiveMap<K, V, StepFnsT>) -> Ordering {
self.btm.cmp(&other.btm)
}
}
impl<K, V> RangeInclusiveMap<K, V, K>
where
K: Ord + Clone + StepLite,
V: Eq + Clone,
{
#[cfg(feature = "const_fn")]
pub const fn new() -> Self {
Self::new_with_step_fns()
}
#[cfg(not(feature = "const_fn"))]
pub fn new() -> Self {
Self::new_with_step_fns()
}
}
impl<K, V, StepFnsT> RangeInclusiveMap<K, V, StepFnsT>
where
K: Ord + Clone,
V: Eq + Clone,
StepFnsT: StepFns<K>,
{
#[cfg(not(feature = "const_fn"))]
pub fn new_with_step_fns() -> Self {
Self {
btm: BTreeMap::new(),
_phantom: PhantomData,
}
}
#[cfg(feature = "const_fn")]
pub const fn new_with_step_fns() -> Self {
Self {
btm: BTreeMap::new(),
_phantom: PhantomData,
}
}
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<(&RangeInclusive<K>, &V)> {
use core::ops::Bound;
let key_as_start = RangeInclusiveStartWrapper::new(key.clone()..=key.clone());
self.btm
.range((Bound::Unbounded, Bound::Included(key_as_start)))
.next_back()
.filter(|(range_start_wrapper, _value)| {
range_start_wrapper.contains(key)
})
.map(|(range_start_wrapper, value)| (&range_start_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: RangeInclusive<K>, value: V) {
use core::ops::Bound;
assert!(
range.start() <= range.end(),
"Range start can not be after range end"
);
let mut new_range_start_wrapper: RangeInclusiveStartWrapper<K> =
RangeInclusiveStartWrapper::new(range);
let new_value = value;
let mut candidates = self
.btm
.range::<RangeInclusiveStartWrapper<K>, (
Bound<&RangeInclusiveStartWrapper<K>>,
Bound<&RangeInclusiveStartWrapper<K>>,
)>((Bound::Unbounded, Bound::Included(&new_range_start_wrapper)))
.rev()
.take(2)
.filter(|(stored_range_start_wrapper, _stored_value)| {
stored_range_start_wrapper
.touches::<StepFnsT>(&new_range_start_wrapper.end_wrapper.range)
});
if let Some(mut candidate) = candidates.next() {
if let Some(another_candidate) = candidates.next() {
candidate = another_candidate;
}
let (stored_range_start_wrapper, stored_value) =
(candidate.0.clone(), candidate.1.clone());
self.adjust_touching_ranges_for_insert(
stored_range_start_wrapper,
stored_value,
&mut new_range_start_wrapper.end_wrapper.range,
&new_value,
);
}
let second_last_possible_start = new_range_start_wrapper.end().clone();
let second_last_possible_start = RangeInclusiveStartWrapper::new(
second_last_possible_start.clone()..=second_last_possible_start,
);
while let Some((stored_range_start_wrapper, stored_value)) = self
.btm
.range::<RangeInclusiveStartWrapper<K>, (
Bound<&RangeInclusiveStartWrapper<K>>,
Bound<&RangeInclusiveStartWrapper<K>>,
)>((
Bound::Included(&new_range_start_wrapper),
Bound::Unbounded,
))
.next()
{
let stored_start = stored_range_start_wrapper.start();
if *stored_start > *second_last_possible_start.start() {
let latest_possible_start = StepFnsT::add_one(second_last_possible_start.start());
if *stored_start > latest_possible_start {
break;
}
if *stored_start == latest_possible_start && *stored_value != new_value {
break;
}
}
let stored_range_start_wrapper = stored_range_start_wrapper.clone();
let stored_value = stored_value.clone();
self.adjust_touching_ranges_for_insert(
stored_range_start_wrapper,
stored_value,
&mut new_range_start_wrapper.end_wrapper.range,
&new_value,
);
}
self.btm.insert(new_range_start_wrapper, new_value);
}
pub fn remove(&mut self, range: RangeInclusive<K>) {
use core::ops::Bound;
assert!(
range.start() <= range.end(),
"Range start can not be after range end"
);
let range_start_wrapper: RangeInclusiveStartWrapper<K> =
RangeInclusiveStartWrapper::new(range);
let range = &range_start_wrapper.range;
if let Some((stored_range_start_wrapper, stored_value)) = self
.btm
.range::<RangeInclusiveStartWrapper<K>, (
Bound<&RangeInclusiveStartWrapper<K>>,
Bound<&RangeInclusiveStartWrapper<K>>,
)>((Bound::Unbounded, Bound::Included(&range_start_wrapper)))
.next_back()
.filter(|(stored_range_start_wrapper, _stored_value)| {
stored_range_start_wrapper.overlaps(range)
})
.map(|(stored_range_start_wrapper, stored_value)| {
(stored_range_start_wrapper.clone(), stored_value.clone())
})
{
self.adjust_overlapping_ranges_for_remove(
stored_range_start_wrapper,
stored_value,
range,
);
}
let new_range_end_as_start =
RangeInclusiveStartWrapper::new(range.end().clone()..=range.end().clone());
while let Some((stored_range_start_wrapper, stored_value)) = self
.btm
.range::<RangeInclusiveStartWrapper<K>, (
Bound<&RangeInclusiveStartWrapper<K>>,
Bound<&RangeInclusiveStartWrapper<K>>,
)>((
Bound::Excluded(&range_start_wrapper),
Bound::Included(&new_range_end_as_start),
))
.next()
.map(|(stored_range_start_wrapper, stored_value)| {
(stored_range_start_wrapper.clone(), stored_value.clone())
})
{
self.adjust_overlapping_ranges_for_remove(
stored_range_start_wrapper,
stored_value,
range,
);
}
}
fn adjust_touching_ranges_for_insert(
&mut self,
stored_range_start_wrapper: RangeInclusiveStartWrapper<K>,
stored_value: V,
new_range: &mut RangeInclusive<K>,
new_value: &V,
) {
use core::cmp::{max, min};
if stored_value == *new_value {
let new_start = min(new_range.start(), stored_range_start_wrapper.start()).clone();
let new_end = max(new_range.end(), stored_range_start_wrapper.end()).clone();
*new_range = new_start..=new_end;
self.btm.remove(&stored_range_start_wrapper);
} else {
if new_range.overlaps(&stored_range_start_wrapper.range) {
self.btm.remove(&stored_range_start_wrapper);
if stored_range_start_wrapper.start() < new_range.start() {
self.btm.insert(
RangeInclusiveStartWrapper::new(
stored_range_start_wrapper.start().clone()
..=StepFnsT::sub_one(new_range.start()),
),
stored_value.clone(),
);
}
if stored_range_start_wrapper.end() > new_range.end() {
self.btm.insert(
RangeInclusiveStartWrapper::new(
StepFnsT::add_one(new_range.end())
..=stored_range_start_wrapper.end().clone(),
),
stored_value,
);
}
} else {
}
}
}
fn adjust_overlapping_ranges_for_remove(
&mut self,
stored_range_start_wrapper: RangeInclusiveStartWrapper<K>,
stored_value: V,
range_to_remove: &RangeInclusive<K>,
) {
self.btm.remove(&stored_range_start_wrapper);
let stored_range = stored_range_start_wrapper.end_wrapper.range;
if stored_range.start() < range_to_remove.start() {
self.btm.insert(
RangeInclusiveStartWrapper::new(
stored_range.start().clone()..=StepFnsT::sub_one(range_to_remove.start()),
),
stored_value.clone(),
);
}
if stored_range.end() > range_to_remove.end() {
self.btm.insert(
RangeInclusiveStartWrapper::new(
StepFnsT::add_one(range_to_remove.end())..=stored_range.end().clone(),
),
stored_value,
);
}
}
pub fn gaps<'a>(&'a self, outer_range: &'a RangeInclusive<K>) -> Gaps<'a, K, V, StepFnsT> {
Gaps {
done: false,
outer_range,
keys: self.btm.keys(),
candidate_start: outer_range.start().clone(),
_phantom: PhantomData,
}
}
pub fn overlapping<'a>(&'a self, range: &'a RangeInclusive<K>) -> Overlapping<K, V> {
let start_sliver =
RangeInclusiveEndWrapper::new(range.start().clone()..=range.start().clone());
let btm_range_iter = self
.btm
.range::<RangeInclusiveEndWrapper<K>, RangeFrom<&RangeInclusiveEndWrapper<K>>>(
&start_sliver..,
);
Overlapping {
query_range: range,
btm_range_iter,
}
}
pub fn overlaps(&self, range: &RangeInclusive<K>) -> bool {
self.overlapping(range).next().is_some()
}
}
pub struct Iter<'a, K, V> {
inner: alloc::collections::btree_map::Iter<'a, RangeInclusiveStartWrapper<K>, V>,
}
impl<'a, K, V> Iterator for Iter<'a, K, V>
where
K: 'a,
V: 'a,
{
type Item = (&'a RangeInclusive<K>, &'a V);
fn next(&mut self) -> Option<(&'a RangeInclusive<K>, &'a V)> {
self.inner.next().map(|(by_start, v)| (&by_start.range, v))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
pub struct IntoIter<K, V> {
inner: alloc::collections::btree_map::IntoIter<RangeInclusiveStartWrapper<K>, V>,
}
impl<K, V> IntoIterator for RangeInclusiveMap<K, V> {
type Item = (RangeInclusive<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 = (RangeInclusive<K>, V);
fn next(&mut self) -> Option<(RangeInclusive<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 RangeInclusiveMap<K, V>
where
K: Ord + Clone + StepLite,
V: Eq + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
impl<K, V> FromIterator<(RangeInclusive<K>, V)> for RangeInclusiveMap<K, V>
where
K: Ord + Clone + StepLite,
V: Eq + Clone,
{
fn from_iter<T: IntoIterator<Item = (RangeInclusive<K>, V)>>(iter: T) -> Self {
let mut range_map = RangeInclusiveMap::new();
range_map.extend(iter);
range_map
}
}
impl<K, V> Extend<(RangeInclusive<K>, V)> for RangeInclusiveMap<K, V>
where
K: Ord + Clone + StepLite,
V: Eq + Clone,
{
fn extend<T: IntoIterator<Item = (RangeInclusive<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 RangeInclusiveMap<K, V>
where
K: Ord + Clone + StepLite + 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 RangeInclusiveMap<K, V>
where
K: Ord + Clone + StepLite + Deserialize<'de>,
V: Eq + Clone + Deserialize<'de>,
{
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
deserializer.deserialize_seq(RangeInclusiveMapVisitor::new())
}
}
#[cfg(feature = "serde1")]
struct RangeInclusiveMapVisitor<K, V> {
marker: PhantomData<fn() -> RangeInclusiveMap<K, V>>,
}
#[cfg(feature = "serde1")]
impl<K, V> RangeInclusiveMapVisitor<K, V> {
fn new() -> Self {
RangeInclusiveMapVisitor {
marker: PhantomData,
}
}
}
#[cfg(feature = "serde1")]
impl<'de, K, V> Visitor<'de> for RangeInclusiveMapVisitor<K, V>
where
K: Ord + Clone + StepLite + Deserialize<'de>,
V: Eq + Clone + Deserialize<'de>,
{
type Value = RangeInclusiveMap<K, V>;
fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
formatter.write_str("RangeInclusiveMap")
}
fn visit_seq<A>(self, mut access: A) -> Result<Self::Value, A::Error>
where
A: SeqAccess<'de>,
{
let mut range_inclusive_map = RangeInclusiveMap::new();
while let Some(((start, end), value)) = access.next_element()? {
range_inclusive_map.insert(start..=end, value);
}
Ok(range_inclusive_map)
}
}
pub struct Gaps<'a, K, V, StepFnsT> {
done: bool,
outer_range: &'a RangeInclusive<K>,
keys: alloc::collections::btree_map::Keys<'a, RangeInclusiveStartWrapper<K>, V>,
candidate_start: K,
_phantom: PhantomData<StepFnsT>,
}
impl<'a, K, V, StepFnsT> core::iter::FusedIterator for Gaps<'a, K, V, StepFnsT>
where
K: Ord + Clone,
StepFnsT: StepFns<K>,
{
}
impl<'a, K, V, StepFnsT> Iterator for Gaps<'a, K, V, StepFnsT>
where
K: Ord + Clone,
StepFnsT: StepFns<K>,
{
type Item = RangeInclusive<K>;
fn next(&mut self) -> Option<Self::Item> {
if self.done {
return None;
}
for item in &mut self.keys {
let range = &item.range;
if *range.end() < self.candidate_start {
} else if *range.start() <= self.candidate_start {
if *range.end() >= *self.outer_range.end() {
self.done = true;
return None;
}
self.candidate_start = StepFnsT::add_one(range.end());
} else if *range.start() <= *self.outer_range.end() {
let gap = self.candidate_start.clone()..=StepFnsT::sub_one(range.start());
if *range.end() >= *self.outer_range.end() {
self.done = true;
} else {
self.candidate_start = StepFnsT::add_one(range.end());
}
return Some(gap);
}
}
self.done = true;
if self.candidate_start <= *self.outer_range.end() {
Some(self.candidate_start.clone()..=self.outer_range.end().clone())
} else {
None
}
}
}
pub struct Overlapping<'a, K, V> {
query_range: &'a RangeInclusive<K>,
btm_range_iter: alloc::collections::btree_map::Range<'a, RangeInclusiveStartWrapper<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 RangeInclusive<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 RangeInclusiveMapExt<K, V> {
fn to_vec(&self) -> Vec<(RangeInclusive<K>, V)>;
}
impl<K, V> RangeInclusiveMapExt<K, V> for RangeInclusiveMap<K, V, K>
where
K: Ord + Clone + StepLite,
V: Eq + Clone,
{
fn to_vec(&self) -> Vec<(RangeInclusive<K>, V)> {
self.iter().map(|(kr, v)| (kr.clone(), v.clone())).collect()
}
}
#[test]
fn empty_map_is_empty() {
let range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
assert_eq!(range_map.to_vec(), vec![]);
}
#[test]
fn insert_into_empty_map() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::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: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(1..=3, false);
range_map.insert(4..=6, false);
assert_eq!(range_map.to_vec(), vec![(1..=6, false)]);
}
#[test]
fn new_different_value_immediately_following_stored() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(1..=3, false);
range_map.insert(4..=6, true);
assert_eq!(range_map.to_vec(), vec![(1..=3, false), (4..=6, true)]);
}
#[test]
fn new_same_value_overlapping_end_of_stored() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(1..=4, false);
range_map.insert(4..=6, false);
assert_eq!(range_map.to_vec(), vec![(1..=6, false)]);
}
#[test]
fn new_different_value_overlapping_end_of_stored() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(1..=3, false);
range_map.insert(3..=5, true);
assert_eq!(range_map.to_vec(), vec![(1..=2, false), (3..=5, true)]);
}
#[test]
fn new_same_value_immediately_preceding_stored() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(3..=5, false);
range_map.insert(1..=2, false);
assert_eq!(range_map.to_vec(), vec![(1..=5, false)]);
}
#[test]
fn new_different_value_immediately_preceding_stored() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(3..=5, true);
range_map.insert(1..=2, false);
assert_eq!(range_map.to_vec(), vec![(1..=2, false), (3..=5, true)]);
}
#[test]
fn new_same_value_wholly_inside_stored() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::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: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(1..=5, true);
range_map.insert(2..=4, false);
assert_eq!(
range_map.to_vec(),
vec![(1..=1, true), (2..=4, false), (5..=5, true)]
);
}
#[test]
fn replace_at_end_of_existing_range_should_coalesce() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(1..=3, false);
range_map.insert(4..=6, true);
range_map.insert(4..=6, false);
assert_eq!(range_map.to_vec(), vec![(1..=6, 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),
(6..=7, true),
(2..=6, true),
];
ranges_with_values.permutation().for_each(|permutation| {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
let mut dense: DenseU32RangeMap<bool> = DenseU32RangeMap::new();
for (k, v) in permutation {
range_map.insert(k.clone(), v);
dense.insert(k, v);
let sparse = range_map.to_vec();
let dense = dense.to_vec();
assert_eq!(sparse, dense);
}
});
}
#[test]
fn get() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(0..=50, false);
assert_eq!(range_map.get(&50), Some(&false));
assert_eq!(range_map.get(&51), None);
}
#[test]
fn get_key_value() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(0..=50, false);
assert_eq!(range_map.get_key_value(&50), Some((&(0..=50), &false)));
assert_eq!(range_map.get_key_value(&51), None);
}
#[test]
fn remove_from_empty_map() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::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: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(25..=75, false);
range_map.remove(0..=24);
assert_eq!(range_map.to_vec(), vec![(25..=75, false)]);
}
#[test]
fn remove_non_covered_range_after_stored() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(25..=75, false);
range_map.remove(76..=100);
assert_eq!(range_map.to_vec(), vec![(25..=75, false)]);
}
#[test]
fn remove_overlapping_start_of_stored() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(25..=75, false);
range_map.remove(0..=25);
assert_eq!(range_map.to_vec(), vec![(26..=75, false)]);
}
#[test]
fn remove_middle_of_stored() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(25..=75, false);
range_map.remove(30..=70);
assert_eq!(range_map.to_vec(), vec![(25..=29, false), (71..=75, false)]);
}
#[test]
fn remove_overlapping_end_of_stored() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(25..=75, false);
range_map.remove(75..=100);
assert_eq!(range_map.to_vec(), vec![(25..=74, false)]);
}
#[test]
fn remove_exactly_stored() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::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: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(25..=75, false);
range_map.remove(0..=100);
assert_eq!(range_map.to_vec(), vec![]);
}
#[test]
fn no_overflow_at_key_domain_extremes() {
let mut range_map: RangeInclusiveMap<u8, bool> = RangeInclusiveMap::new();
range_map.insert(0..=255, false);
range_map.insert(0..=10, true);
range_map.insert(245..=255, true);
range_map.remove(0..=5);
range_map.remove(0..=5);
range_map.remove(250..=255);
range_map.remove(250..=255);
range_map.insert(0..=255, true);
range_map.remove(1..=254);
range_map.insert(254..=254, true);
range_map.insert(255..=255, true);
range_map.insert(255..=255, false);
range_map.insert(0..=0, false);
range_map.insert(1..=1, true);
range_map.insert(0..=0, true);
}
#[test]
fn whole_range_is_a_gap() {
let range_map: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::new();
range_map.insert(1..=4, ());
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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::new();
range_map.insert(1..=5, ());
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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::new();
range_map.insert(5..=6, ());
let outer_range = 5..=8;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(7..=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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::new();
range_map.insert(6..=7, ());
range_map.insert(3..=4, ());
let outer_range = 1..=8;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(1..=2));
assert_eq!(gaps.next(), Some(5..=5));
assert_eq!(gaps.next(), Some(8..=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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::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..=6));
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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::new();
range_map.insert(5..=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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::new();
range_map.insert(5..=9, ());
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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::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 zero_width_outer_range_with_items_away_from_both_sides() {
let mut range_map: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::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(), Some(4..=4));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn zero_width_outer_range_with_items_touching_both_sides() {
let mut range_map: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::new();
range_map.insert(2..=3, ());
range_map.insert(5..=6, ());
let outer_range = 4..=4;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(4..=4));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn empty_outer_range_with_item_straddling() {
let mut range_map: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::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: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
range_map.insert(4..=5, true);
range_map.insert(2..=3, false);
let outer_range = 1..=8;
let mut gaps = range_map.gaps(&outer_range);
assert_eq!(gaps.next(), Some(1..=1));
assert_eq!(gaps.next(), Some(6..=8));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn no_overflow_finding_gaps_at_key_domain_extremes() {
let mut range_map: RangeInclusiveMap<u8, bool> = RangeInclusiveMap::new();
range_map.insert(0..=255, false);
range_map.gaps(&(0..=255));
let mut range_map: RangeInclusiveMap<u8, bool> = RangeInclusiveMap::new();
range_map.insert(0..=255, false);
range_map.gaps(&(0..=5));
range_map.gaps(&(250..=255));
let mut range_map: RangeInclusiveMap<u8, bool> = RangeInclusiveMap::new();
range_map.insert(0..=255, false);
range_map.gaps(&(1..=5));
range_map.gaps(&(250..=254));
let mut range_map: RangeInclusiveMap<u8, bool> = RangeInclusiveMap::new();
range_map.insert(1..=254, false);
range_map.gaps(&(0..=5));
range_map.gaps(&(250..=255));
}
#[test]
fn adjacent_unit_width_items() {
let mut range_map: RangeInclusiveMap<u8, bool> = RangeInclusiveMap::new();
range_map.insert(0..=0, false);
range_map.insert(1..=1, true);
range_map.insert(254..=254, false);
range_map.insert(255..=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 overlapping_with_empty_map() {
let range_map: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::new();
range_map.insert(0..=1, ());
range_map.insert(3..=4, ());
range_map.insert(6..=7, ());
let query_range = 1..=6;
let mut overlapping = range_map.overlapping(&query_range);
assert_eq!(overlapping.next(), Some((&(0..=1), &())));
assert_eq!(overlapping.next(), Some((&(3..=4), &())));
assert_eq!(overlapping.next(), Some((&(6..=7), &())));
assert_eq!(overlapping.next(), None);
assert_eq!(overlapping.next(), None);
}
#[test]
fn overlapping_non_overlapping_edges_complete_middle() {
let mut range_map: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::new();
range_map.insert(0..=1, ());
range_map.insert(3..=4, ());
range_map.insert(6..=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: RangeInclusiveMap<u32, ()> = RangeInclusiveMap::new();
assert_eq!(format!("{:?}", map), "{}");
map.insert(2..=5, ());
assert_eq!(format!("{:?}", map), "{2..=5: ()}");
map.insert(7..=8, ());
map.insert(10..=11, ());
assert_eq!(format!("{:?}", map), "{2..=5: (), 7..=8: (), 10..=11: ()}");
}
#[cfg(feature = "serde1")]
#[test]
fn serialization() {
let mut range_map: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::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: RangeInclusiveMap<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: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new();
#[cfg(feature = "const_fn")]
const _MAP2: RangeInclusiveMap<u32, bool> = RangeInclusiveMap::new_with_step_fns();
}