Feature #19839
closedNeed a method to check if two ranges overlap
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
Updated by baweaver (Brandon Weaver) about 1 year 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) about 1 year 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) about 1 year 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 Dan0042 (Daniel DeLorme) about 1 year ago
Related to #16757
Updated by hsbt (Hiroshi SHIBATA) about 1 year ago
- 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?
Updated by shouichi (Shouichi Kamiya) about 1 year 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) about 1 year 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) about 1 year 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) about 1 year 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?
orarray_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) about 1 year ago
Accepted. It must be useful without ActiveSupport.
Matz.
Updated by ko1 (Koichi Sasada) about 1 year 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) about 1 year 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) about 1 year 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) about 1 year ago
I opened a PR about a month ago but should I close it...? https://github.com/ruby/ruby/pull/8242
Updated by shouichi (Shouichi Kamiya) about 1 year 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 mame (Yusuke Endoh) about 1 year ago
@nobu (Nobuyoshi Nakada) is trying to fix the corner cases that @ko1 (Koichi Sasada) pointed: https://github.com/ruby/ruby/pull/8448
Updated by akr (Akira Tanaka) about 1 year 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) about 1 year 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) about 1 year 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, thenoverlap?
can return false when one of the ranges is empty.
It's for nil
, that means begin-less range.
Updated by shouichi (Shouichi Kamiya) about 1 year ago
Because (...-Float::INFINITY)
is semantically empty, shouldn't none?
return true
?
Updated by akr (Akira Tanaka) about 1 year 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) about 1 year ago
shouichi (Shouichi Kamiya) wrote in #note-21:
Because
(...-Float::INFINITY)
is semantically empty, shouldn'tnone?
returntrue
?
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 inEnumerable
which useseach
method which usessucc
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) about 1 year 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 shouichi (Shouichi Kamiya) about 1 year ago
Asked them in their discord channel. https://discord.com/channels/849034466856665118/974005005768069211/1154298190120624138
Updated by rafaelfranca (Rafael França) about 1 year 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) 12 months ago
Just FYI: Documentation has been added at c23b25f75f6180b7428f9650e063b1e50fc161e2 for the corner cases of minimum value.
Updated by mame (Yusuke Endoh) 12 months ago
- Related to Feature #13933: Add Range#empty? added
Updated by hsbt (Hiroshi SHIBATA) 12 months ago
- Related to Feature #15976: Add Array#overlap? for whether the intersection of 2 arrays is non empty? added