use core::ops::{Add, AddAssign, RangeBounds};
use crate::{Arrangement, Domain, GenericRange, OperationResult, Ranges};
impl<T: Domain> Ranges<T> {
/// Returns `true` if any element or the internal vector was modified to accommodate `range`.
/// This means `false` is returned if and only if nothing has changed.
///
/// # Examples
/// Empty:
/// ```
/// use ranges::Ranges;
///
/// let mut ranges = Ranges::new();
/// assert!(ranges.insert(0..3));
/// assert_eq!(ranges, (0..3).into())
/// ```
/// Collision with internal expansion of existing entry:
/// ```
/// use ranges::Ranges;
///
/// let mut ranges = Ranges::from(0..3);
/// assert!(ranges.insert(2..5));
/// assert_eq!(ranges, (0..5).into())
/// ```
/// No change in internal vector:
/// ```
/// use ranges::Ranges;
///
/// let mut ranges = Ranges::from(0..10);
/// assert!(!ranges.insert(3..7));
/// assert_eq!(ranges, (0..10).into())
/// ```
pub fn insert<R>(&mut self, range: R) -> bool
where
R: Into<GenericRange<T>>,
{
let new_range = range.into();
if new_range.is_empty() {
return false;
}
if self.ranges.is_empty() {
self.ranges.push(new_range);
return true;
}
if new_range.is_full() {
return if self.is_full() {
false
} else {
// whatever is in `self.ranges` does not matter...
self.ranges.clear();
self.ranges.push(new_range);
true
};
}
let indices = self.find_intersecting_ranges(&new_range);
match indices {
// we only encountered disjoint ranges
None => {
let index = self
.ranges
.binary_search_by(|r| GenericRange::cmp_start_start(r.start_bound(), new_range.start_bound()))
.unwrap_err();
self.ranges.insert(index, new_range);
true
}
// a single range intersected
Some((s, e)) if s == e => {
#[allow(clippy::indexing_slicing)]
match new_range.arrangement(&self.ranges[s]) {
// find_intersecting_ranges() ignores disjoint ranges
Arrangement::Disjoint { .. } => unreachable!(),
Arrangement::Touching { .. } | Arrangement::Overlapping { .. } => {
// for these two cases it does not matter how they're arranged, one can
// never be inside the other
// remove the value at index s and replace it with a temporary full range
#[allow(clippy::indexing_slicing)]
let existing_range = core::mem::replace(&mut self.ranges[s], GenericRange::full());
let new_range = match new_range.union(existing_range) {
OperationResult::Empty | OperationResult::Double(_, _) => unreachable!(),
OperationResult::Single(r) => r,
};
// replace temporary value with the newly calculated one
self.ranges[s] = new_range;
true
}
Arrangement::Containing { self_shorter: false }
| Arrangement::Starting {
self_shorter: false, ..
}
| Arrangement::Ending {
self_shorter: false, ..
} => {
// in this case the inserted range is disjoint from all others except
// self.ranges[s], but is also larger, so we can simply replace it.
self.ranges[s] = new_range;
true
}
Arrangement::Containing { self_shorter: true }
| Arrangement::Starting { self_shorter: true, .. }
| Arrangement::Ending { self_shorter: true, .. }
| Arrangement::Equal => {
// self is shorter or equal and thus no modification is required
false
}
Arrangement::Empty { self_empty: Some(true) } => {
unreachable!("inserted range being empty is caught at the beginning of this method")
}
Arrangement::Empty {
self_empty: Some(false),
} => unreachable!("internal guarantee broken: empty range in set"),
Arrangement::Empty { self_empty: None } => unreachable!("under no circumstances is this reachable"),
}
}
Some((s, e)) => {
// replace first element of affected indices by full range
#[allow(clippy::indexing_slicing)]
let first = core::mem::replace(&mut self.ranges[s], GenericRange::full());
// we can safely unwrap here because we know there are at least two ranges
#[allow(clippy::integer_arithmetic, clippy::expect_used)]
let last = self
.ranges
.drain(s + 1..=e)
.last()
.expect("there are at least two ranges");
// and because the indices were sorted, we can now construct a new one directly
let existing_ranges_combined = GenericRange {
start: first.start,
end: last.end,
};
let new_range = match new_range.union(existing_ranges_combined) {
OperationResult::Empty | OperationResult::Double(_, _) => unreachable!(),
OperationResult::Single(r) => r,
};
// replace temporary value with the newly calculated one
#[allow(clippy::indexing_slicing)]
// using a block to apply the lint allowance, because attributes on expressions are
// experimental
{
self.ranges[s] = new_range;
}
true
}
}
}
}
/// This calls [`self.insert(other)`](#method.insert).
impl<T, I> Add<I> for Ranges<T>
where
I: Into<GenericRange<T>>,
T: Domain,
{
type Output = Self;
#[must_use]
fn add(mut self, rhs: I) -> Self::Output {
let _ = self.insert(rhs.into());
self
}
}
/// This calls [`self.insert(other)`](#method.insert).
impl<T, I> AddAssign<I> for Ranges<T>
where
I: Into<GenericRange<T>>,
T: Domain,
{
fn add_assign(&mut self, rhs: I) {
let _ = self.insert(rhs.into());
}
}
#[cfg(test)]
mod tests {
use alloc::vec;
use core::cmp::Ordering;
use core::ops::RangeBounds;
use proptest::prelude::*;
use crate::{GenericRange, Ranges};
#[test]
fn empty() {
let mut ranges = Ranges::new();
assert!(ranges.insert(0..3));
assert_eq!(ranges.ranges, vec![(0..3).into()])
}
#[test]
fn one_collision() {
let mut ranges = Ranges::from(0..3);
assert!(ranges.insert(2..5));
assert_eq!(ranges.ranges, vec![(0..5).into()])
}
#[test]
fn two_collisions() {
let mut ranges = Ranges::from(0..3);
assert!(ranges.insert(5..10));
assert!(ranges.insert(2..7));
assert_eq!(ranges.ranges, vec![(0..10).into()])
}
#[test]
fn full() {
let mut ranges = Ranges::from(0..3);
assert!(ranges.insert(GenericRange::full()));
assert!(ranges.is_full())
}
#[test]
fn muvlon() {
// checks if inserting an empty range modifies the internal vector
let mut ranges = Ranges::new();
assert!(!ranges.insert(5..5));
assert_eq!(ranges.ranges, vec![]);
}
proptest! {
#[ignore]
#[test]
fn sorted_and_disjoint(mut ranges in any::<Ranges<u8>>(), range in any::<GenericRange<u8>>()) {
let _ = ranges.insert(range);
let sorted_and_disjoint = ranges.as_slice().windows(2).all(|slice| match slice {
[left, right] => {
GenericRange::cmp_start_start(left.start_bound(), right.start_bound()) == Ordering::Less
&& GenericRange::cmp_end_start(left.end_bound(), right.start_bound()) == Ordering::Less
},
_ => false,
});
prop_assert!(sorted_and_disjoint);
}
}
}