use alloc::{vec, vec::Vec};
use core::iter::FromIterator;
use crate::generic_range::GenericRange;
use crate::{Arrangement, Domain};
/// Trait implementation of `Arbitrary` for use in fuzzers.
#[cfg(feature = "arbitrary")]
mod arbitrary;
/// Ranges methods to find out if a value is contained within.
mod contains;
/// Ranges difference.
mod difference;
/// Ranges formatting.
mod format;
/// Ranges insertion.
mod insert;
/// Ranges intersection.
mod intersect;
/// Ranges inversion.
mod invert;
/// Proptest `Arbitrary`.
#[cfg(any(feature = "proptest", test))]
mod proptest;
/// Ranges removal.
mod remove;
/// Ranges symmetric difference.
mod symmetric_difference;
/// Ranges unionization.
mod union;
/// A range set storing `GenericRange`s in the most memory-optimal fashion possible.
///
/// The two guarantees of storing ranges disjoint and sorted allows for the following optimizations:
/// - keeping them ordered, upper and lower bounds for searches can be used to keep the search
/// space as small as possible
/// - storing them disjoint is a by-product of automatically merging newly inserted ranges, which
/// additionally helps to reduce reindexing of the internal vector
///
#[allow(clippy::missing_inline_in_public_items)]
#[derive(Clone, Debug, Default, Hash, PartialEq, Eq)]
pub struct Ranges<T: Domain> {
/// Inner storage - can and probably will be replaced with something more efficient
/// as soon as const generics are available (like an array with a pre-defined size,
/// which makes sense if you know how many discrete singletons you may have, e.g. for integers).
pub(crate) ranges: Vec<GenericRange<T>>,
}
impl<T: Domain> Ranges<T> {
/// Creates a new empty `Ranges` with an initial capacity of 0.
#[must_use]
pub fn new() -> Self {
Self::with_capacity(0)
}
/// Initializes the underlying vector with a given capacity.
#[must_use]
pub fn with_capacity(capacity: usize) -> Self {
Self {
ranges: Vec::with_capacity(capacity),
}
}
/// Initializes the underlying vector with a single full range.
#[must_use]
pub fn full() -> Self {
Self {
ranges: vec![GenericRange::full()],
}
}
/// Returns true if the whole domain is in this range.
#[allow(clippy::indexing_slicing)]
#[must_use]
pub fn is_full(&self) -> bool
where
T: PartialEq,
{
// we could do `*self == Self::full()` but that would require vector allocation at runtime
// however, as soon as Self::full() becomes constant, it should be used instead
self.ranges.len() == 1 && self.ranges[0] == GenericRange::full()
}
/// Returns the amount of saved disjoint ranges.
#[must_use]
pub fn len(&self) -> usize {
self.ranges.len()
}
/// Returns true if there are no ranges and we have an empty set.
#[must_use]
pub fn is_empty(&self) -> bool {
self.ranges.is_empty()
}
/// Find the `GenericRange`s in `self` which at least touch `other`.
///
/// Since `other` is a `GenericRange` (i.e. contiguous),
/// the overlapping ranges must all be consecutive.
/// Therefore, this only returns the indices of the first and last ranges which overlap.
///
/// This returns a (start, end) pair of indices into `self.ranges`.
///
/// # Example
/// ```
/// use ranges::Ranges;
///
/// let ranges = Ranges::from(vec![0..5, 10..20, 25..30, 45..50]);
/// assert_eq!(ranges.find_intersecting_ranges(&(7..47).into()), Some((1, 3)))
/// ```
#[must_use]
pub fn find_intersecting_ranges(&self, other: &GenericRange<T>) -> Option<(usize, usize)> {
let mut seen_overlap = false;
let mut indices = None;
for (i, range) in self.ranges.iter().enumerate() {
#[allow(clippy::wildcard_enum_match_arm)]
let overlap = match other.arrangement(range) {
Arrangement::Disjoint { .. } => false,
Arrangement::Empty { .. } => return None,
_ => true,
};
match (seen_overlap, overlap) {
// we have not seen overlap and there is none... continue
//
// range |----|
// new_range |--------|
(false, false) => {}
// this is the first intersecting range
//
// either starting in the same place:
// range |----|
// new_range |--------|
//
// or starting before with overlap:
// range |------|
// new_range |--------|
(false, true) => {
seen_overlap = true;
indices = Some((i, i));
}
// we're in the middle of ranges that intersect
//
// either completely within the new range:
// range |--|
// new_range |--------|
//
// or extending past:
// range |----|
// new_range |--------|
(true, true) => {
indices = indices.map(|(s, _)| (s, i));
}
// we've reached the end of intersecting ranges
// even if there are more ranges after this,
// they could not possibly overlap.
//
// range |---|
// new_range |--------|
(true, false) => {
break;
}
}
}
indices
}
/// Returns the internal vector of `GenericRange`s as a slice.
#[must_use]
pub fn as_slice(&self) -> &[GenericRange<T>] {
self.ranges.as_slice()
}
}
impl<T: Domain, U> From<U> for Ranges<T>
where
U: Into<GenericRange<T>>,
{
#[must_use]
fn from(r: U) -> Self {
let range = r.into();
let mut ranges = Self::new();
let _ = ranges.insert(range);
ranges
}
}
impl<T: Domain, U> From<Vec<U>> for Ranges<T>
where
U: Into<GenericRange<T>>,
{
#[must_use]
fn from(v: Vec<U>) -> Self {
let mut ranges = Self::with_capacity(v.capacity());
// we can not just transfer the contents, as there might be overlapping entries
for range in v {
let _ = ranges.insert(range.into());
}
ranges
}
}
impl<T: Domain> FromIterator<GenericRange<T>> for Ranges<T> {
#[allow(clippy::shadow_reuse)]
fn from_iter<I: IntoIterator<Item = GenericRange<T>>>(iter: I) -> Self {
let iter = iter.into_iter();
// edge case: n ranges, all being empty, would unnecessarily allocate but is better
// than the alternative: n ranges all being separately allocated.
let (lower_bound, _) = iter.size_hint();
let mut ranges = Self::with_capacity(lower_bound);
for range in iter {
let _ = ranges.insert(range);
}
ranges.ranges.shrink_to_fit();
ranges
}
}
impl<T: Domain> AsRef<Vec<GenericRange<T>>> for Ranges<T> {
fn as_ref(&self) -> &Vec<GenericRange<T>> {
&self.ranges
}
}
#[cfg(test)]
mod tests {
use alloc::vec;
use core::ops::Bound;
use crate::{GenericRange, Ranges};
#[test]
fn from_core_ranges() {
// [x, y) - x..y
assert_eq!(
Ranges::from(1..5),
Ranges {
ranges: vec![GenericRange {
start: Bound::Included(1),
end: Bound::Excluded(5)
}]
}
);
// [x, y] - x..=y
assert_eq!(
Ranges::from(6..=10),
Ranges {
ranges: vec![GenericRange {
start: Bound::Included(6),
end: Bound::Included(10)
}]
}
);
// [x, +inf) - x..
assert_eq!(
Ranges::from(12..),
Ranges {
ranges: vec![GenericRange {
start: Bound::Included(12),
end: Bound::Included(2_147_483_647)
}]
}
);
// (-inf, y) - ..y
assert_eq!(
Ranges::from(..15),
Ranges {
ranges: vec![GenericRange {
start: Bound::Included(-2_147_483_648),
end: Bound::Excluded(15)
}]
}
);
// (-inf, y] - ..=y
assert_eq!(
Ranges::from(..=20),
Ranges {
ranges: vec![GenericRange {
start: Bound::Included(-2_147_483_648),
end: Bound::Included(20)
}]
}
);
// (-inf, +inf) - ..
let ranges: Ranges<usize> = Ranges::from(..);
assert_eq!(
ranges,
Ranges {
ranges: vec![GenericRange {
start: Bound::Included(0),
end: Bound::Included(18_446_744_073_709_551_615)
}]
}
);
// (x, y) - has no Rust equivalent
assert_eq!(
Ranges::from((Bound::Excluded(30), Bound::Excluded(42))),
Ranges {
ranges: vec![GenericRange {
start: Bound::Excluded(30),
end: Bound::Excluded(42)
}]
}
);
// (x, y] - has no Rust equivalent
assert_eq!(
Ranges::from((Bound::Excluded(45), Bound::Included(50))),
Ranges {
ranges: vec![GenericRange {
start: Bound::Excluded(45),
end: Bound::Included(50)
}]
}
);
// (x, +inf) - has no Rust equivalent
assert_eq!(
Ranges::from((Bound::Excluded(55), Bound::Unbounded)),
Ranges {
ranges: vec![GenericRange {
start: Bound::Excluded(55),
end: Bound::Included(2_147_483_647)
}]
}
);
}
}