use core::cmp::Ordering;
use core::fmt::{self, Debug};
use core::iter::FromIterator;
use core::ops::RangeInclusive;
#[cfg(feature = "serde1")]
use core::marker::PhantomData;
#[cfg(feature = "serde1")]
use serde::{
de::{Deserialize, Deserializer, SeqAccess, Visitor},
ser::{Serialize, Serializer},
};
use crate::std_ext::*;
use crate::RangeInclusiveMap;
#[derive(Clone)]
pub struct RangeInclusiveSet<T, StepFnsT = T> {
rm: RangeInclusiveMap<T, (), StepFnsT>,
}
impl<T> Default for RangeInclusiveSet<T, T>
where
T: Ord + Clone + StepLite,
{
fn default() -> Self {
Self::new()
}
}
impl<T> PartialEq for RangeInclusiveSet<T, T>
where
T: PartialEq,
{
fn eq(&self, other: &RangeInclusiveSet<T, T>) -> bool {
self.rm == other.rm
}
}
impl<T> Eq for RangeInclusiveSet<T, T> where T: Eq {}
impl<T> PartialOrd for RangeInclusiveSet<T, T>
where
T: PartialOrd,
{
#[inline]
fn partial_cmp(&self, other: &RangeInclusiveSet<T, T>) -> Option<Ordering> {
self.rm.partial_cmp(&other.rm)
}
}
impl<T> Ord for RangeInclusiveSet<T, T>
where
T: Ord,
{
#[inline]
fn cmp(&self, other: &RangeInclusiveSet<T, T>) -> Ordering {
self.rm.cmp(&other.rm)
}
}
impl<T> RangeInclusiveSet<T, T>
where
T: Ord + Clone + StepLite,
{
#[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<T, StepFnsT> RangeInclusiveSet<T, StepFnsT>
where
T: Ord + Clone,
StepFnsT: StepFns<T>,
{
#[cfg(not(feature = "const_fn"))]
pub fn new_with_step_fns() -> Self {
Self {
rm: RangeInclusiveMap::new_with_step_fns(),
}
}
#[cfg(feature = "const_fn")]
pub const fn new_with_step_fns() -> Self {
Self {
rm: RangeInclusiveMap::new_with_step_fns(),
}
}
pub fn get(&self, value: &T) -> Option<&RangeInclusive<T>> {
self.rm.get_key_value(value).map(|(range, _)| range)
}
pub fn contains(&self, value: &T) -> bool {
self.rm.contains_key(value)
}
pub fn iter(&self) -> Iter<'_, T> {
Iter {
inner: self.rm.iter(),
}
}
pub fn clear(&mut self) {
self.rm.clear();
}
pub fn len(&self) -> usize {
self.rm.len()
}
pub fn is_empty(&self) -> bool {
self.rm.is_empty()
}
pub fn insert(&mut self, range: RangeInclusive<T>) {
self.rm.insert(range, ());
}
pub fn remove(&mut self, range: RangeInclusive<T>) {
self.rm.remove(range);
}
pub fn gaps<'a>(&'a self, outer_range: &'a RangeInclusive<T>) -> Gaps<'a, T, StepFnsT> {
Gaps {
inner: self.rm.gaps(outer_range),
}
}
pub fn overlapping<'a>(&'a self, range: &'a RangeInclusive<T>) -> Overlapping<T> {
Overlapping {
inner: self.rm.overlapping(range),
}
}
pub fn overlaps(&self, range: &RangeInclusive<T>) -> bool {
self.overlapping(range).next().is_some()
}
}
pub struct Iter<'a, T> {
inner: super::inclusive_map::Iter<'a, T, ()>,
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a RangeInclusive<T>;
fn next(&mut self) -> Option<&'a RangeInclusive<T>> {
self.inner.next().map(|(range, _)| range)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
pub struct IntoIter<T> {
inner: super::inclusive_map::IntoIter<T, ()>,
}
impl<T> IntoIterator for RangeInclusiveSet<T> {
type Item = RangeInclusive<T>;
type IntoIter = IntoIter<T>;
fn into_iter(self) -> Self::IntoIter {
IntoIter {
inner: self.rm.into_iter(),
}
}
}
impl<T> Iterator for IntoIter<T> {
type Item = RangeInclusive<T>;
fn next(&mut self) -> Option<RangeInclusive<T>> {
self.inner.next().map(|(range, _)| range)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl<T: Debug> Debug for RangeInclusiveSet<T>
where
T: Ord + Clone + StepLite,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_set().entries(self.iter()).finish()
}
}
impl<T> FromIterator<RangeInclusive<T>> for RangeInclusiveSet<T>
where
T: Ord + Clone + StepLite,
{
fn from_iter<I: IntoIterator<Item = RangeInclusive<T>>>(iter: I) -> Self {
let mut range_set = RangeInclusiveSet::new();
range_set.extend(iter);
range_set
}
}
impl<T> Extend<RangeInclusive<T>> for RangeInclusiveSet<T>
where
T: Ord + Clone + StepLite,
{
fn extend<I: IntoIterator<Item = RangeInclusive<T>>>(&mut self, iter: I) {
iter.into_iter().for_each(move |range| {
self.insert(range);
})
}
}
#[cfg(feature = "serde1")]
impl<T> Serialize for RangeInclusiveSet<T>
where
T: Ord + Clone + StepLite + 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.rm.btm.len()))?;
for range in self.iter() {
seq.serialize_element(&(&range.start(), &range.end()))?;
}
seq.end()
}
}
#[cfg(feature = "serde1")]
impl<'de, T> Deserialize<'de> for RangeInclusiveSet<T>
where
T: Ord + Clone + StepLite + Deserialize<'de>,
{
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
deserializer.deserialize_seq(RangeInclusiveSetVisitor::new())
}
}
#[cfg(feature = "serde1")]
struct RangeInclusiveSetVisitor<T> {
marker: PhantomData<fn() -> RangeInclusiveSet<T>>,
}
#[cfg(feature = "serde1")]
impl<T> RangeInclusiveSetVisitor<T> {
fn new() -> Self {
RangeInclusiveSetVisitor {
marker: PhantomData,
}
}
}
#[cfg(feature = "serde1")]
impl<'de, T> Visitor<'de> for RangeInclusiveSetVisitor<T>
where
T: Ord + Clone + StepLite + Deserialize<'de>,
{
type Value = RangeInclusiveSet<T>;
fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
formatter.write_str("RangeInclusiveSet")
}
fn visit_seq<A>(self, mut access: A) -> Result<Self::Value, A::Error>
where
A: SeqAccess<'de>,
{
let mut range_inclusive_set = RangeInclusiveSet::new();
while let Some((start, end)) = access.next_element()? {
range_inclusive_set.insert(start..=end);
}
Ok(range_inclusive_set)
}
}
pub struct Gaps<'a, T, StepFnsT> {
inner: crate::inclusive_map::Gaps<'a, T, (), StepFnsT>,
}
impl<'a, T, StepFnsT> core::iter::FusedIterator for Gaps<'a, T, StepFnsT>
where
T: Ord + Clone,
StepFnsT: StepFns<T>,
{
}
impl<'a, T, StepFnsT> Iterator for Gaps<'a, T, StepFnsT>
where
T: Ord + Clone,
StepFnsT: StepFns<T>,
{
type Item = RangeInclusive<T>;
fn next(&mut self) -> Option<Self::Item> {
self.inner.next()
}
}
pub struct Overlapping<'a, T> {
inner: crate::inclusive_map::Overlapping<'a, T, ()>,
}
impl<'a, T> core::iter::FusedIterator for Overlapping<'a, T> where T: Ord + Clone {}
impl<'a, T> Iterator for Overlapping<'a, T>
where
T: Ord + Clone,
{
type Item = &'a RangeInclusive<T>;
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|(k, _v)| k)
}
}
#[cfg(test)]
mod tests {
use super::*;
use alloc::{format, vec, vec::Vec};
trait RangeInclusiveSetExt<T> {
fn to_vec(&self) -> Vec<RangeInclusive<T>>;
}
impl<T> RangeInclusiveSetExt<T> for RangeInclusiveSet<T>
where
T: Ord + Clone + StepLite,
{
fn to_vec(&self) -> Vec<RangeInclusive<T>> {
self.iter().cloned().collect()
}
}
#[test]
fn empty_set_is_empty() {
let range_set: RangeInclusiveSet<u32> = RangeInclusiveSet::new();
assert_eq!(range_set.to_vec(), vec![]);
}
#[test]
fn insert_into_empty_map() {
let mut range_set: RangeInclusiveSet<u32> = RangeInclusiveSet::new();
range_set.insert(0..=50);
assert_eq!(range_set.to_vec(), vec![0..=50]);
}
#[test]
fn remove_partially_overlapping() {
let mut range_set: RangeInclusiveSet<u32> = RangeInclusiveSet::new();
range_set.insert(0..=50);
range_set.remove(25..=75);
assert_eq!(range_set.to_vec(), vec![0..=24]);
}
#[test]
fn gaps_between_items_floating_inside_outer_range() {
let mut range_set: RangeInclusiveSet<u32> = RangeInclusiveSet::new();
range_set.insert(5..=6);
range_set.insert(2..=3);
let outer_range = 1..=8;
let mut gaps = range_set.gaps(&outer_range);
assert_eq!(gaps.next(), Some(1..=1));
assert_eq!(gaps.next(), Some(4..=4));
assert_eq!(gaps.next(), Some(7..=8));
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
assert_eq!(gaps.next(), None);
}
#[test]
fn overlapping_partial_edges_complete_middle() {
let mut range_set: RangeInclusiveSet<u32> = RangeInclusiveSet::new();
range_set.insert(0..=1);
range_set.insert(3..=4);
range_set.insert(6..=7);
let query_range = 1..=6;
let mut overlapping = range_set.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 set_debug_repr_looks_right() {
let mut set: RangeInclusiveSet<u32> = RangeInclusiveSet::new();
assert_eq!(format!("{:?}", set), "{}");
set.insert(2..=5);
assert_eq!(format!("{:?}", set), "{2..=5}");
set.insert(7..=8);
set.insert(10..=11);
assert_eq!(format!("{:?}", set), "{2..=5, 7..=8, 10..=11}");
}
#[cfg(feature = "serde1")]
#[test]
fn serialization() {
let mut range_set: RangeInclusiveSet<u32> = RangeInclusiveSet::new();
range_set.insert(1..=3);
range_set.insert(5..=7);
let output = serde_json::to_string(&range_set).expect("Failed to serialize");
assert_eq!(output, "[[1,3],[5,7]]");
}
#[cfg(feature = "serde1")]
#[test]
fn deserialization() {
let input = "[[1,3],[5,7]]";
let range_set: RangeInclusiveSet<u32> =
serde_json::from_str(input).expect("Failed to deserialize");
let reserialized = serde_json::to_string(&range_set).expect("Failed to re-serialize");
assert_eq!(reserialized, input);
}
#[cfg(feature = "const_fn")]
const _SET: RangeInclusiveSet<u32> = RangeInclusiveSet::new();
#[cfg(feature = "const_fn")]
const _SET2: RangeInclusiveSet<u32> = RangeInclusiveSet::new_with_step_fns();
}