IntoBounds::clamp and RangeBounds::is_empty (original) (raw)

Proposal

Problem statement

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 cases

A custom slice type where indexing always succeeds

use std::ops::{Index, IntoBounds};

pub struct Slice([T]);

impl<T, R: IntoBounds> Index for Slice { 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

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: RangeBounds { fn into_bounds(self) -> (Bound, Bound);

/// 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.

What happens now?

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 responses

The 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: