Range types are essentially abstract sets, defined by a start and end point. A common operation on sets is calculating the intersection, and in practice this applies to ranges as well.
Having a generic way to tell if the result is empty is also useful.
Motivating examples or use casesA custom slice type where indexing always succeeds
use std::ops::{Index, IntoBounds};
pub struct Slice<T>([T]);
impl<T, R: IntoBounds<usize>> Index<R> for Slice<T> {
type Output = [T];
fn index(&self, index: R) -> &[T] {
&self.0[index.clamp(..self.0.len())]
}
}
The examples from #277 are also applicable to this proposal
Solution sketch
- a database implementation using btree index where a parent node would split its total key range in ranges per child. To implement an operation to find keys within a given range it would need to check if child ranges overlap with an input range
- An interval map implementation would need to be able to check for overlaps
- A memory copy/move implementation operation may check for overlaps to decide if it needs to use move or copy
- A database implementation allowing to operate on ranges (eg range deletes, range queries, etc) would need to have an ability to check for range overlaps
pub trait RangeBounds<T: ?Sized> {
// ...
/// Returns `true` if the range contains no items.
/// One-sided ranges (`RangeFrom`, etc) always returns `true`.
///
/// # Examples
///
/// ```
/// use std::ops::RangeBounds;
///
/// assert!(!(3..).is_empty());
/// assert!(!(..2).is_empty());
/// assert!(!RangeBounds::is_empty(&(3..5)));
/// assert!( RangeBounds::is_empty(&(3..3)));
/// assert!( RangeBounds::is_empty(&(3..2)));
/// ```
///
/// The range is empty if either side is incomparable:
///
/// ```
/// use std::ops::RangeBounds;
///
/// assert!(!RangeBounds::is_empty(&(3.0..5.0)));
/// assert!( RangeBounds::is_empty(&(3.0..f32::NAN)));
/// assert!( RangeBounds::is_empty(&(f32::NAN..5.0)));
/// ```
///
/// But never empty is either side is unbounded:
///
/// ```
/// use std::ops::Bound::*;
/// use playground::RangeBounds;
///
/// assert!(!(..0).is_empty());
/// assert!(!(i32::MAX..).is_empty());
/// assert!(!RangeBounds::<u8>::is_empty(&(..)));
/// ```
///
/// `(Excluded(a), Excluded(b))` is only empty if `a >= b`:
///
/// ```
/// use std::ops::Bound::*;
/// use std::ops::RangeBounds;
///
/// assert!(!(Excluded(1), Excluded(3)).is_empty());
/// assert!(!(Excluded(1), Excluded(2)).is_empty());
/// assert!( (Excluded(1), Excluded(1)).is_empty());
/// assert!( (Excluded(2), Excluded(1)).is_empty());
/// assert!( (Excluded(3), Excluded(1)).is_empty());
/// ```
fn is_empty(&self) -> bool
where
T: PartialOrd,
{
!match (self.start_bound(), self.end_bound()) {
(Unbounded, _) | (_, Unbounded) => true,
(Included(start), Excluded(end))
| (Excluded(start), Included(end))
| (Excluded(start), Excluded(end)) => start < end,
(Included(start), Included(end)) => start <= end,
}
}
}
pub trait IntoBounds<T>: RangeBounds<T> {
fn into_bounds(self) -> (Bound<T>, Bound<T>);
/// Clamp `self` within the bounds of `other`.
/// In set terms, this is the _intersection_.
///
/// # Examples
///
/// ```
/// use std::ops::Bound::*;
/// use std::ops::IntoBounds;
///
/// assert_eq!((3..).clamp(..5), (Included(3), Excluded(5)));
/// assert_eq!((-12..387).clamp(0..256), (Included(0), Excluded(256)));
/// assert_eq!((1..5).clamp(..), (Included(1), Excluded(5)));
/// assert_eq!((1..=9).clamp(0..10), (Included(1), Included(9)));
/// assert_eq!((7..=13).clamp(8..13), (Included(8), Excluded(13)));
/// ```
///
/// Combine with `is_empty` to determine if two ranges overlap.
///
/// ```
/// use std::ops::{RangeBounds, IntoBounds};
///
/// assert!(!(3..).clamp(..5).is_empty());
/// assert!(!(-12..387).clamp(0..256).is_empty());
/// assert!((1..5).clamp(6..).is_empty());
/// ```
fn clamp<R>(self, other: R) -> (Bound<T>, Bound<T>)
where
Self: Sized,
T: Ord,
R: Sized + IntoBounds<T>,
{
let (self_start, self_end) = IntoBounds::into_bounds(self);
let (other_start, other_end) = IntoBounds::into_bounds(other);
let start = match (self_start, other_start) {
(Included(a), Included(b)) => Included(Ord::max(a, b)),
(Excluded(a), Excluded(b)) => Excluded(Ord::max(a, b)),
(Unbounded, Unbounded) => Unbounded,
(x, Unbounded) | (Unbounded, x) => x,
(Included(i), Excluded(e))
| (Excluded(e), Included(i)) => if i > e {
Included(i)
} else {
Excluded(e)
}
};
let end = match (self_end, other_end) {
(Included(a), Included(b)) => Included(Ord::min(a, b)),
(Excluded(a), Excluded(b)) => Excluded(Ord::min(a, b)),
(Unbounded, Unbounded) => Unbounded,
(x, Unbounded) | (Unbounded, x) => x,
(Included(i), Excluded(e))
| (Excluded(e), Included(i)) => if i < e {
Included(i)
} else {
Excluded(e)
}
};
(start, end)
}
} Alternatives
Just provide a generic way to tell if two ranges overlap, without actually calculating the overlap, aka #277. RangeBounds::overlap is more flexible, since it can operate without Ord or IntoBounds.
This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.
Possible responsesThe libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):
Second, if there's a concrete solution:
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4