use std::{collections::BTreeMap, convert::TryFrom};
use thiserror::Error;
#[derive(Clone, Error, Debug, PartialEq, Eq)]
pub enum RangeSetError {
#[error("Invalid range provided")]
InvalidRange,
#[error("Overlapping ranges")]
RangeOverlap,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct RangeSet<RK: Ord + Copy> {
ranges: BTreeMap<RK, RK>, }
impl<RK: Ord + Copy> RangeSet<RK> {
pub fn new() -> Self {
Self {
ranges: BTreeMap::new(),
}
}
pub fn insert(&mut self, start: RK, end: RK) -> Result<(), RangeSetError> {
if start >= end {
return Err(RangeSetError::InvalidRange);
}
if let Some((&_prev_start, &prev_end)) = self.ranges.range(..=start).next_back() {
if prev_end >= start {
return Err(RangeSetError::RangeOverlap);
}
}
if let Some((&next_start, _)) = self.ranges.range(start..).next() {
if next_start < end {
return Err(RangeSetError::RangeOverlap);
}
}
self.ranges.insert(start, end);
Ok(())
}
pub fn contains(&self, value: RK) -> bool {
if let Some((&_start, &end)) = self.ranges.range(..=value).next_back() {
return value < end;
}
false
}
pub fn remove(&mut self, start: RK, end: RK) -> bool {
if let Some(range_end) = self.ranges.get(&start) {
if *range_end == end {
self.ranges.remove(&start);
return true;
}
}
false
}
pub fn iter(&self) -> impl Iterator<Item = (RK, RK)> + '_ {
self.ranges.iter().map(|(&s, &e)| (s, e))
}
pub fn len(&self) -> usize {
self.ranges.len()
}
pub fn is_empty(&self) -> bool {
self.ranges.is_empty()
}
}
impl<RK: Copy + Ord> Default for RangeSet<RK> {
fn default() -> Self {
RangeSet::new()
}
}
impl<RK: Copy + Ord> TryFrom<Vec<(RK, RK)>> for RangeSet<RK> {
type Error = RangeSetError;
fn try_from(value: Vec<(RK, RK)>) -> Result<Self, Self::Error> {
let mut range_set = RangeSet::new();
for range in value {
range_set.insert(range.0, range.1)?;
}
Ok(range_set)
}
}
#[cfg(test)]
mod tests {
use std::convert::TryInto;
use crate::rangeset::{RangeSet, RangeSetError};
#[test]
fn test_insertions() {
let mut rs = RangeSet::new();
assert_eq!(rs.insert(10, 20), Ok(()));
assert_eq!(rs.insert(30, 40), Ok(()));
assert_eq!(rs.insert(15, 25), Err(RangeSetError::RangeOverlap));
assert!(rs.contains(15));
assert!(!rs.contains(25));
}
#[test]
fn test_removal() {
let mut rs = RangeSet::new();
assert_eq!(rs.insert(10, 20), Ok(()));
assert_eq!(rs.insert(30, 40), Ok(()));
assert!(!rs.remove(10, 11));
assert!(rs.remove(10, 20));
assert!(rs.remove(30, 40));
assert!(!rs.remove(30, 40));
}
#[test]
fn test_try_from_vec() {
let range_set: RangeSet<u32> = vec![(0, 10), (100, 150)].try_into().unwrap();
assert_eq!(range_set.len(), 2);
let invalid_result: Result<RangeSet<u32>, RangeSetError> =
vec![(10, 30), (11, 23)].try_into();
assert_eq!(invalid_result, Err(RangeSetError::RangeOverlap))
}
}