Crate range_overlap

Determine how two ranges overlap, given their end points.

There are two pairs of terms used throughout this crate: exclusive vs. inclusive and closed vs. open.

• exclusive vs. inclusive refers to whether the end of the range is considered part of it. This is the distinction between 1..3 and 1..=3 in Rust’s range notation: the former will only represent the sequence [1, 2] and thus is exclusive, while the latter represents [1, 2, 3] and so is inclusive.

• closed vs. open refers to whether the range has finite end points. You could have a range that starts at 1 and goes one forever, ends at 10 but has infinitely many values less than that, or that has no end points whatsoever. These are all open ranges. Conversely, a range that starts at 1 and ends at 5 is closed. When this crate needs to represent ranges that may be closed, half-open, or fully open, it uses Option<T> values, where Some(T) represents a closed side and None an open side. For example, (Some(1), None) represent the range starting at 1 and going on forever.

The RangeOverlap enum of this crate specifies 6 possible ways in which two ranges may overlap. In the following schematics, | indicates an end point included in the range, - indicates an internal part of the range, and o indicates an exclusive end point. For simplicity, we’ll only cover fully closed ranges first.

The simplest is no overlap, represented by RangeOverlap::None:

// B is wholly after A
A: |----|
B:         |----|
 
// A is wholly after B
A:         |--|
B: |---|
 
// B starts on A's excluded end point:
A: |----o
B:      |----o

The next simplest is RangeOverlap::AEqualsB, when A and B represent the same range:

// This holds true for inclusive...
A: |----|
B: |----|
 
// ...and exclusive ranges:
A: |----o
B: |----o

The next two variants indicate when one range is entirely within another. RangeOverlap::AContainsB means that the first range specified (A) contains all the points in B, while RangeOverlap::AInsideB indicates the reverse:

// AContainsB:
A: |------|
B:   |--|
 
// These are also AContainsB, because no point in B is outside A, even though
// the ends line up:
A: |------|
B: |----|
 
A: |------|
B:   |----|
 
A: |------o
B:   |----o
 
And vice versa, these are AInsideB:
A:   |---|
B: |-------|
 
A:   |---o
B: |-----o
 
A: |---|
B: |-----|

Finally, RangeOverlap::AEndsInB and RangeOverlap::AStartsInB indicate cases where only one end of A falls within the limits of B:

// AEndsInB:
 
A: |------|
B:    |-------|
 
// This is AEndsInB because the end of A is included. If it were
// exclusive this would be None:
A: |------|
B:        |-----|
 
// AStartsInB:
A:    |------|
B: |----|
 
A:    |------|
B: |--|

The main function that can classify any type of range is classify_any. This can handle closed, half-open, or fully open ranges and interpret the end points as inclusive or exclusive. If you know your ranges will be closed, you can use excl_classify or incl_classify to determine the RangeOverlap without needing to wrap the range ends in Some().

One assumption this crate makes is that an end being open means the same thing for both ranges. For example:

 
let overlap = classify_any(None, Some(5), None, Some(10), false);
assert_eq!(overlap, RangeOverlap::AInsideB);

Here, None is assumed to mean the same thing for both ranges, essentially negative infinity. Since this means there can be no point in A not also in B, the result is AInsideB. Another interesting case is when both ranges are fully open:

 
// With literal `None`s we had to give the type T as i32, since there was nothing
// for Rust to infer T from. You will almost never need to do this in practice.
let overlap = classify_any::<i32>(None, None, None, None, false);
assert_eq!(overlap, RangeOverlap::AEqualsB);

Again, since None is taken to mean the same thing for both A and B, all points in one must be in the other, so these two are equal ranges.

If you only need to determine if two ranges overlap, but not how, you can either use the RangeOverlap::has_overlap method, or call one of the convenience methods:

• has_excl_overlap
• has_incl_overlap
• has_open_excl_overlap
• has_open_incl_overlap

Finally, note that all of these method are defined for any type that implements PartialOrd. This means you can use them for integers, floats, chrono times, and many other types. This includes types such as std::string::String, which may not produce intuitive behavior unless you are very clear on how they are ordered.

Enums

• RangeOverlap
  An enum describing the kind of overlap between two ranges.

Functions

• classify_any
  Classify the kind of overlap between two ranges that can be closed, half-open, or fully open. Specifying a_start, a_end, b_start, or b_end as None indicates that that side of the range is open. The final parameter, inclusive, can be true to indicate that a_end and b_end are part of their ranges, or false if they are not.
• excl_classify
  Classify the kind of overlap between two fully closed ranges with the ends considered exclusive.
• has_excl_overlap
  A convenience function that directly returns true if the two closed ranges given have overlap, with a_end and b_end not included in the range.
• has_incl_overlap
  A convenience function that directly returns true if the two closed ranges given have overlap, with a_end and b_end included in the range.
• has_open_excl_overlap
  A convenience function that directly returns true if the two ranges given (which may be closed, half-open, or fully open) have overlap, with a_end and b_end not included in the range.
• has_open_incl_overlap
  A convenience function that directly returns true if the two ranges given (which may be closed, half-open, or fully open) have overlap, with a_end and b_end included in the range.
• incl_classify
  Classify the kind of overlap between two fully closed ranges with the ends considered inclusive.