[ACP] RangeBounds::overlaps

[theli-ua]

Proposal

Problem statement

RangeBounds today is a standard trait to represent ranges and provides a single method contains used to determine if a range contains a given element. Another common operation on ranges (like intervals) is to check if 2 overlap. Today there is no method to check for that

Motivating examples or use cases

• 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

Solution sketch

pub trait RangeBounds<T: ?Sized> {

    /// Returns `true` if there exists an element present in both ranges.
    ///
    /// # Examples
    ///
    /// ```
    /// assert!( (3..5).overlaps(&(1..4));
    /// assert!(!(3..5).overlaps(&(5..6));
    /// ```
    ///
    fn overlaps<O, E>(&self, other: &O) -> bool
    where
        T: PartialOrd<E>,
        E: ?Sized + PartialOrd<T>,
        O: RangeBounds<E>,
    {
          todo!()
    }
}

Open questions

There is a question whether to consider (Excluded(1), Excluded(3)) as overlapping with (Excluded(2), Excluded(5)). Since this is only a problem for cases where a discrete step between elements is known we could have a specialized implementation for anything that implements Step that handles these cases.

Alternatives

Alternative would be for developers to implement it on specific types, or an extension trait on top of RangeBounds (which could be a separate crate)

Links and related work

[pitaj]

In most cases, don't people want to perform some sort of operation on the overlapping region? Could the function return a range instead? Then you could use Range::is_empty to just check if there is overlap.

[theli-ua]

@pitaj well, we'd probably need to add is_empty to RangeBounds in that case.

[scottmcm]

Hmm, intersect probably wants different return types depending on the input ranges, not just an impl RangeBounds.

Is it reasonable to mix the types? I guess Range & RangeInclusive doesn't know the type to return, so maybe not?

[theli-ua]

Yeah, given that this is a trait and in case of intersect/overlap we would need to return a concrete type I'd say for the trait specifically it makes sense to have overlaps that returns a boolean and would be similar to currently provided method - contains

[quaternic]

  fn overlaps<O, E>(&self, other: &O) -> bool
  where
      T: PartialOrd<E>,
      E: ?Sized + PartialOrd<T>,
      O: RangeBounds<E>,

Functions like overlaps or intersect should require T: Ord, because if the upper (or lower) bounds of the two sets are not mutually comparable, you can't necessarily compute the intersection as a range. It might not even be representable as a range at all.

Example: Nonnegative integers can be partially ordered by divisibility, so that e.g. D(2)..=D(30) contains D(x) iff x is even and divides 30. Then the intersection of the ranges D(2)..=D(30) and D(3)..=D(12) is D(6)..=D(6), but computing that requires more than what PartialOrd provides.

[theli-ua]

@quaternic that makes sense so it'd be

pub trait RangeBounds<T: ?Sized> {

    /// Returns `true` if there exists an element present in both ranges.
    ///
    /// # Examples
    ///
    /// ```
    /// assert!( (3..5).overlaps(&(1..4));
    /// assert!(!(3..5).overlaps(&(5..6));
    /// ```
    ///
    fn overlaps(&self, other: &T) -> bool
    where
        T: Ord,
    {
          todo!()
    }
}

[pitaj]

Hmm, intersect probably wants different return types depending on the input ranges, not just an impl RangeBounds.

Is it reasonable to mix the types? I guess Range & RangeInclusive doesn't know the type to return, so maybe not?

Yeah, given that this is a trait and in case of intersect/overlap we would need to return a concrete type I'd say for the trait specifically it makes sense to have overlaps that returns a boolean

The function could just return (Bound, Bound) rather than a range type to avoid this issue. It would be good to have is_empty on RangeBounds though.

Should it maybe return Option<(Bound, Bound)> with None for the "no overlap" case, or should it return a specific empty range?

Like what should (2..6).intersect(11..13) return? (Bound::Excluded(11), Bound::Excluded(6))?