Feature #19839: Need a method to check if two ranges overlap

• Status: Closed
• Assignee: -
• Target version: -

[shouichi (Shouichi Kamiya)]

It would be convenient to have a method that checks if two ranges overlap. For example,

(0..10).overlap?(5..15) #=> true
(0..10).overlap?(20..30) #=> false

[baweaver (Brandon Weaver)]

I've made several helpers for this exact same problem, as well as a Range#merge in the past. I would very much be in favor of this change.

Example usage from an interview problem, though I have some internal usecases which have done similar:

https://gist.github.com/baweaver/5dbca4296db0651de41267c2c1267c68

The idea for this was to bold targeted segments of a String like:

Emboldener.new(text: "aaabbcc", targets: ["aaa","aab","bc"]).run

...and have intersections merged. Granted this also brings up an interesting follow-up potential of merging ranges and if they happen to be left or right biased:

private def merge_range(a, b)
  return Range.new(a.begin, b.end) if a.cover?(b.begin)
  return Range.new(b.begin, a.end) if b.cover?(a.begin)

  nil
end

In any case the overlap? method would be very handy to me for a number of use-cases.

[nobu (Nobuyoshi Nakada)]

What do you expect when it is called with a non-Range object, TypeError, same as cover? or something else?

[shouichi (Shouichi Kamiya)]

Thank you for your feedback.

I've made several helpers for this exact same problem, as well as a Range#merge in the past.

Yes, Range class can have methods such as Range#merge but I wanted to start small and see what happens.

What do you expect when it is called with a non-Range object, TypeError, same as cover? or something else?

Yes. Raising TypeError seems correct. I'm going to fix the PR.

[Dan0042 (Daniel DeLorme)]

Related to #16757

[hsbt (Hiroshi SHIBATA)]

• Status changed from Open to Feedback

ActiveSupport already have overlaps? method.

• https://api.rubyonrails.org/classes/Range.html#method-i-overlaps-3F
• https://github.com/rails/rails/blob/main/activesupport/lib/active_support/core_ext/range/overlap.rb#L7

Is it enough for your use-case?

[shouichi (Shouichi Kamiya)]

Though ActiveSupport's overlaps? method is enough for our use-case. I think the feature is so fundamental that it should be supported by the standard library.

Slightly off-topic: It might be better to add a method that returns the overlapping range of two ranges. Then users can check if the overlapping range is empty or not. Although there's no method to check if a range is empty.

[hsbt (Hiroshi SHIBATA)]

• Status changed from Feedback to Open

Thanks. Basically, we didn't add new methods from ActiveSupport without performance reason.

Can you describe why we should add overlap? to ruby core?

[shouichi (Shouichi Kamiya)]

Honestly, I can't give a formal reason. But I do believe it's a very basic operation. For example, postgres and boost provide such functionality.

• https://www.postgresql.org/docs/15/functions-range.html
• https://www.boost.org/doc/libs/1_83_0/libs/numeric/interval/doc/interval.htm

[baweaver (Brandon Weaver)]

I believe there are a few reasons for this addition. The core one I see often in justifications is precedence in existing Ruby, such as:

Combinations

These cases have clear precedent for iterable / enumerable types:

• Array#concat - Merging two Arrays
• Hash#merge - Merging two Hashes
• Set#union - Merging two Sets (or Enumerable on other end)

Inclusions

Interestingly not as common are patterns like Enumerable#include?(other_enumerable) versus the very common Enumerable#include?(single_item) so we have a lot of "unnamed" approximations:

• Array - (array_two - array_one).empty? or array_one.intersection(array_two).any?
• Hash - (hash_two.keys - hash_one.keys).empty?

...which are not very performant, and I would bet are common patterns in non-Rails code. It also raises a potential for Hash#intersection and how that might work with same keys with different values.

Overlaps

For these two cases I would also almost consider overlaps?, which is synonymous to intersection(other).any? from Array:

[1, 2, 3].overlaps?([2, 3]) # true
{ a: 1, b: 2 }.overlaps?(a: 3, b: 5) # true? key vs value is complicated here

(1..10).overlaps?(5..15) # true

---

Point being I would argue there is a (minor) performance win potential here for existing code, it feels very much in the spirit of Ruby of creating a name for a common operation.

[matz (Yukihiro Matsumoto)]

Accepted. It must be useful without ActiveSupport.

Matz.

[ko1 (Koichi Sasada)]

I'm not sure what (n...n) means but on AS definition, the following code return true.

p (1..2).overlap?(2...2)  #=> true
p (2..2).overlap?(2...2)  #=> true
p (2...2).overlap?(2...2) #=> true

is it intentional?

[matz (Yukihiro Matsumoto)]

Although I said “accepted”, we found some corner cases which are not clear (e.g. #note-11). We have to make these cases clear before merging it to the core.

Matz.

[sawa (Tsuyoshi Sawada)]

I think the analogue for range1.overlap?(range2) in mathematics is interval1 ∩ interval2 ≠ ∅, which does not hold when either interval1 or interval2 is an empty interval.

Hence, I think that, when either range1 or range2 is an empty range (e.g., 2...2, 2..1), range1.overlap?(range2) should return false.

Instead of adopting the AS #note-5 definition,

def overlap?(other)
  other.begin == self.begin || cover?(other.begin) || other.cover?(self.begin)
end

I propose to define it as equivalent to:

def overlap?(other)
  return false if none? or other.none?
  other.begin == self.begin || cover?(other.begin) || other.cover?(self.begin)
end

[nobu (Nobuyoshi Nakada)]

https://github.com/nobu/ruby/tree/Range%23overlap_p

[shouichi (Shouichi Kamiya)]

I opened a PR about a month ago but should I close it...? https://github.com/ruby/ruby/pull/8242

[shouichi (Shouichi Kamiya)]

• Status changed from Open to Closed

Applied in changeset git|e9b503f1bb9692eda1d1f55f62c19d861b88a0d5.

---

[Feature #19839] Add Range#overlap?

Add a method that returns true if two range overlap, otherwise false.

(0..10).overlap?(5..15) #=> true
(0..10).overlap?(20..30) #=> false

[mame (Yusuke Endoh)]

@nobu (Nobuyoshi Nakada) is trying to fix the corner cases that @ko1 (Koichi Sasada) pointed: https://github.com/ruby/ruby/pull/8448

[akr (Akira Tanaka)]

I found another corner case.

% ./ruby -e 'r = (...-Float::INFINITY); p r.overlap?(r)' 
true
% ./ruby -e 'r = (...[]); p r.overlap?(r)'
true
% ./ruby -e 'r = (...""); p r.overlap?(r)' 
true
% ./ruby -e 'r = (...true); p r.overlap?(r)'
true
% ./ruby -e 'r = (...false); p r.overlap?(r)'
true
% ./ruby -e 'r = (...Object.new); p r.overlap?(r)'
true
% ./ruby -v
ruby 3.3.0dev (2023-09-16T22:27:04Z master cd67c0d204) [x86_64-linux]

They are (...MINIMUM) where MINIMUM is a value that there is no value less than that.

(...MINIMUM) is empty because
(1) it doesn't contain MINIMUM itself because ... is used (exclude_end is true) and
(2) it doesn't contain other values because there is no value less than MINIMUM.

But (...MINIMUM).overlap?(...MINIMUM) returns true as shown above.
It means Ruby says there is a value contained in (...MINIMUM).
It is invalid.

Note that true, false, and Object.new has <=> method defined by Kernel.
It determines self is equal to itself and other objects are not comparable.
Thus, they can be considered as minimum values (and maximum values).

I think this problem is difficult to solve.
We have no clean way to detect minimum values.

Some options:
(1) introduce some protocol to detect minimum values such as minimum? method.
(2) hard code minimum values of builtin classes in Range#overlap? and use minimum? for user-defined classes.
(3) document this limitation.

[shouichi (Shouichi Kamiya)]

Shouldn't none? handle empty ranges? Currently, it raises an error.

> (...-Float::INFINITY).none?
(irb):1:in `each': can't iterate from NilClass (TypeError)

If none? handles empty ranges, then overlap? can return false when one of the ranges is empty.

[nobu (Nobuyoshi Nakada)]

shouichi (Shouichi Kamiya) wrote in #note-19:

Shouldn't none? handle empty ranges? Currently, it raises an error.

> (...-Float::INFINITY).none?
(irb):1:in `each': can't iterate from NilClass (TypeError)

If none? handles empty ranges, then overlap? can return false when one of the ranges is empty.

It's for nil, that means begin-less range.

[shouichi (Shouichi Kamiya)]

Because (...-Float::INFINITY) is semantically empty, shouldn't none? return true?

[akr (Akira Tanaka)]

Range has two semantics: succ-based and cover-based.

none? is succ-based because it is implemented in Enumerable which uses each method which uses succ in Range.

overlap? is cover-based.
It uses comparison (<=>).

The two semantics sometimes cause inconsistent behavior.
It is difficult to make them consistent completely.

[Dan0042 (Daniel DeLorme)]

shouichi (Shouichi Kamiya) wrote in #note-21:

Because (...-Float::INFINITY) is semantically empty, shouldn't none? return true?

I agree it should be semantically empty, but (...-Float::INFINITY).size == Infinity

akr (Akira Tanaka) wrote in #note-22:

Range has two semantics: succ-based and cover-based.
none? is succ-based because it is implemented in Enumerable which uses each method which uses succ in Range.

In that case it seems like Range should have cover-based #empty? method. It has been proposed before (#13933) but strangely it was never added?

[mame (Yusuke Endoh)]

This method is going to have an incompatibility with Range#overlap? that ActiveSupport has been provided. Is it OK? I'd like to confirm with the Rails developers just to be sure.

[shouichi (Shouichi Kamiya)]

Asked them in their discord channel. https://discord.com/channels/849034466856665118/974005005768069211/1154298190120624138

[rafaelfranca (Rafael França)]

Thank you for checking with us. I believe the difference when the ranges are empty is acceptable. I don't think it was intentional in the Active Support implementation.

[mame (Yusuke Endoh)]

Just FYI: Documentation has been added at c23b25f75f6180b7428f9650e063b1e50fc161e2 for the corner cases of minimum value.

[mame (Yusuke Endoh)]

• Related to Feature #13933: Add Range#empty? added

[hsbt (Hiroshi SHIBATA)]

• Related to Feature #15976: Add Array#overlap? for whether the intersection of 2 arrays is non empty? added