Project

General

Profile

Actions

Feature #19839

closed

Need a method to check if two ranges overlap

Added by shouichi (Shouichi Kamiya) 6 months ago. Updated 4 months ago.

Status:
Closed
Assignee:
-
Target version:
-
[ruby-core:114399]

Description

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

Related issues 2 (0 open2 closed)

Related to Ruby master - Feature #13933: Add Range#empty?RejectedActions
Related to Ruby master - Feature #15976: Add Array#overlap? for whether the intersection of 2 arrays is non empty?ClosedActions

Updated by baweaver (Brandon Weaver) 6 months ago

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.

Updated by nobu (Nobuyoshi Nakada) 6 months ago

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

Updated by shouichi (Shouichi Kamiya) 6 months ago

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.

Updated by shouichi (Shouichi Kamiya) 6 months ago

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.

Updated by hsbt (Hiroshi SHIBATA) 6 months ago

  • 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?

Updated by shouichi (Shouichi Kamiya) 5 months ago

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.

Updated by baweaver (Brandon Weaver) 5 months ago

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.

Updated by matz (Yukihiro Matsumoto) 5 months ago

Accepted. It must be useful without ActiveSupport.

Matz.

Updated by ko1 (Koichi Sasada) 5 months ago

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?

Updated by matz (Yukihiro Matsumoto) 5 months ago

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.

Updated by sawa (Tsuyoshi Sawada) 5 months ago

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

Updated by shouichi (Shouichi Kamiya) 5 months ago

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

Actions #16

Updated by shouichi (Shouichi Kamiya) 5 months ago

  • 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

Updated by akr (Akira Tanaka) 5 months ago

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.

Updated by shouichi (Shouichi Kamiya) 5 months ago

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.

Updated by nobu (Nobuyoshi Nakada) 5 months ago

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.

Updated by shouichi (Shouichi Kamiya) 5 months ago

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

Updated by akr (Akira Tanaka) 5 months ago

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.

Updated by Dan0042 (Daniel DeLorme) 5 months ago

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?

Updated by mame (Yusuke Endoh) 5 months ago

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.

Updated by rafaelfranca (Rafael França) 5 months ago

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.

Updated by mame (Yusuke Endoh) 4 months ago

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

Actions #28

Updated by mame (Yusuke Endoh) 4 months ago

Actions #29

Updated by hsbt (Hiroshi SHIBATA) 4 months ago

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

Also available in: Atom PDF

Like1
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like1Like0Like0Like1Like0Like0Like0Like1Like0Like0Like0Like2Like0Like0Like0Like0Like0Like0Like0