[ACP] RangeBounds::overlaps (original) (raw)

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)