Ruby: intersection between two ranges

Question

In ruby, given two date ranges, I want the range that represents the intersection of the two date ranges, or nil if no intersection. For example:

(Date.new(2011,1,1)..Date.new(2011,1,15)) & (Date.new(2011,1,10)..Date.new(2011,2,15))
=> Mon, 10 Jan 2011..Sat, 15 Jan 2011

Edit: Should have said that I want it to work for DateTime as well, so interval can be down to mins and secs:

(DateTime.new(2011,1,1,22,45)..Date.new(2011,2,15)) & (Date.new(2011,1,1)..Date.new(2011,2,15))
=> Sat, 01 Jan 2011 22:45:00 +0000..Tue, 15 Feb 2011

steenslag · Accepted Answer · 2011-12-07T15:35:25.157

31

require 'date'

class Range
  def intersection(other)
    return nil if (self.max < other.begin or other.max < self.begin) 
    [self.begin, other.begin].max..[self.max, other.max].min
  end
  alias_method :&, :intersection
end

p (Date.new(2011,1,1)..Date.new(2011,1,15)) & (Date.new(2011,1,10)..Date.new(2011,2,15))
#<Date: 2011-01-10 ((2455572j,0s,0n),+0s,2299161j)>..#<Date: 2011-01-15 ((2455577j,0s,0n),+0s,2299161j)>

edited Dec 07 '11 at 15:35

answered Dec 07 '11 at 12:08

steenslag

79,051
16
138
171

This one is great, but I've had to change range.end to range.max so that the exclusive range notation (...) still works. – jjnevis Dec 07 '11 at 13:37
@jjnevis I didn't do that because I thought range.max would iterate, but it appears I was wrong. Then range.max is definitely better and I 'll edit the answer. – steenslag Dec 07 '11 at 15:34
2

Would it be more consistent to use range.min rather than range.begin if we are using range.max? Anyway - this answer gets my tick! Thanks. – jjnevis Dec 07 '11 at 16:49
2

This answer has a big flaw: it doesn't support Ranges that have their ends excluded. – bert bruynooghe Mar 07 '13 at 13:19
1

also, it does not work with empty ranges (where min/max return nil). while exotic, it sometimes happens sometimes. – sergeych Apr 29 '19 at 18:09
Mathematically it would be more appropriate to return a range that's empty rather than returning a nil, if extrapolating from set theory. – galva Nov 14 '19 at 13:15

Aliaksei Kliuchnikau · Answer 2 · 2011-12-07T11:55:56.880

10

You can try this to get a range representing intersection

range1 = Date.new(2011,12,1)..Date.new(2011,12,10)
range2 = Date.new(2011,12,4)..Date.new(2011,12,12)

inters = range1.to_a & range2.to_a

intersected_range = inters.min..inters.max

Converting your example:

class Range  
  def intersection(other)  
    raise ArgumentError, 'value must be a Range' unless other.kind_of?(Range)  

    inters = self.to_a & other.to_a

    inters.empty? ? nil : inters.min..inters.max 
  end  

  alias_method :&, :intersection  
end

edited Dec 07 '11 at 11:55

answered Dec 07 '11 at 11:41

Aliaksei Kliuchnikau

13,589
4
59
72

3

Keep in mind though that converting large Ranges to arrays can be very inefficient. – Ajedi32 Aug 03 '12 at 20:27
Elegant answer for simple, short, discrete ranges, thanks! – Divide Feb 03 '16 at 05:38

score 3 · Answer 3 · edited Jan 05 '14 at 17:20

I baked this solution for ascending ranges, also taking care of the exclude end situations:

intersect_ranges = ->(r1, r2) do
  new_end = [r1.end, r2.end].min
  new_begin = [r1.begin, r2.begin].max
  exclude_end = (r2.exclude_end? && new_end == r2.end) || (r1.exclude_end? && new_end == r1.end)

  valid = (new_begin <= new_end && !exclude_end) 
  valid ||= (new_begin < new_end && exclude_end))
  valid ? Range.new(new_begin, new_end, exclude_end) : nil
end

I'm also a bit worried by you guys adding it to the Range class itself, since the behavior of intersecting ranges is not uniformly defined. (How about intersecting 1...4 and 4...1? Why nil when there is no intersection; we could also say this is an empty range: 1...1 )

score 3 · Answer 4 · answered Feb 04 '21 at 19:53

You can use overlaps? with Range starting with Rails v3

# For dates, make sure you have the correct format
first_range = first_start.to_date..first_end.to_date
second_range = second_start.to_date..second_end.to_date

intersection = first_range.overlaps?(second_range) # => Boolean

# Example with numbers
(1..7).overlaps?(3..5) # => true

More details in the docs

score 3 · Answer 5 · answered Dec 07 '11 at 11:32

I found this: http://www.postal-code.com/binarycode/2009/06/06/better-range-intersection-in-ruby/ which is a pretty good start, but does not work for dates. I've tweaked a bit into this:

class Range  
  def intersection(other)  
    raise ArgumentError, 'value must be a Range' unless other.kind_of?(Range)  

    new_min = self.cover?(other.min) ? other.min : other.cover?(min) ? min : nil  
    new_max = self.cover?(other.max) ? other.max : other.cover?(max) ? max : nil  

    new_min && new_max ? new_min..new_max : nil  
  end  

  alias_method :&, :intersection  
end

I've omitted the tests, but they are basically the tests from the post above changed for dates. This works for ruby 1.9.2.

Anyone got a better solution?

score 0 · Answer 6 · answered Nov 23 '16 at 17:31

I have times as [[start, end], ...] and I want to remove the some time ranges from a each initial time range, here is what I did:

def exclude_intersecting_time_ranges(initial_times, other_times)
  initial_times.map { |initial_time|
    other_times.each do |other_time|
      next unless initial_time
      # Other started after initial ended
      next if other_time.first >= initial_time.last
      # Other ended before initial started
      next if other_time.last <= initial_time.first

      # if other time started before and ended after after, no hour is counted
      if other_time.first <= initial_time.first && other_time.last >= initial_time.last
        initial_time = nil
      # if other time range is inside initial time range, split in two time ranges
      elsif initial_time.first < other_time.first && initial_time.last > other_time.last
        initial_times.push([other_time.last, initial_time.last])
        initial_time = [initial_time.first, other_time.first]
      # if start time of other time range is before initial time range
      elsif other_time.first <= initial_time.first
        initial_time = [other_time.last, initial_time.last]
      # if end time of other time range if after initial time range
      elsif other_time.last >= initial_time.last
        initial_time = [initial_time.first, other_time.first]
      end
    end

    initial_time
  }.compact
end

score 0 · Answer 7 · answered Mar 24 '18 at 22:15

0

Since this question is related to How to combine overlapping time ranges (time ranges union), I also wanted to post my finding of the gem range_operators here, because if helped me in the same situation.

answered Mar 24 '18 at 22:15

nlsrchtr

770
5
7

The [implementation of intersect](https://github.com/monocle/range_operators/blob/master/lib/range_operators/array_operator_definitions.rb#L42) is (potentially) not very good since it iterates over the whole range. It would be slow and memory intensive for large ranges. It's fine for small ranges. – James H Apr 20 '22 at 20:29

Zack Xu · Answer 8 · 2023-03-10T14:36:27.203

0

You can also use Set to achieve this goal, which results in code that is more elegant.

require 'date'

class Range
  def intersection(other)
    intersecting_set = to_set & other.to_set
    intersecting_set.first && (intersecting_set.min..intersecting_set.max)
  end
  alias_method :&, :intersection
end

pry(main)> p (Date.new(2011,1,1)..Date.new(2011,1,15)) & (Date.new(2011,1,10)..Date.new(2011,2,15))
Mon, 10 Jan 2011..Sat, 15 Jan 2011
=> Mon, 10 Jan 2011..Sat, 15 Jan 2011

Also, you should use refinement, not monkey patch Range everywhere in your codebase.

edited Mar 10 '23 at 14:36

answered Mar 03 '23 at 17:43

Zack Xu

11,505
9
70
78

Can you explain "use refinement, not monkey patch Range everything"? – Joshua Pinter Jun 21 '23 at 19:58
This is great first attempt at the solution. But it doesn't work with `DateTime` objects. And it doesn't handle endless or beginningless ranges very well. – Joshua Pinter Jun 22 '23 at 17:38

score 0 · Answer 9 · answered Jun 22 '23 at 17:46

`Range#intersection` that handles `DateTime` objects as well.

Initializer

  # Determines the overlap of two ranges.
  #
  # Returns: Range
  #
  def intersection( second_range )
    raise ArgumentError, "must be another Range" unless second_range.is_a?( Range )

    return nil unless self.overlaps?( second_range )

    intersection_start_at = [ self.first, second_range.first ].compact.max
    intersection_end_at   = [ self.end, second_range.end ].compact.min

    ( intersection_start_at..intersection_end_at )
  end
  alias_method :&, :intersection

Usage

(12.hours.ago..6.hours.ago).intersection(10.hours.ago..8.hours.ago)
#=> Thu, 22 Jun 2023 01:45:33.072270000 MDT -06:00..Thu, 22 Jun 2023 03:45:33.072282000 MDT -06:00

And with OP's specific example:

(DateTime.new(2011,1,1,22,45)..Date.new(2011,2,15)) & (Date.new(2011,1,1)..Date.new(201
1,2,15))
#=> Sat, 01 Jan 2011 22:45:00 +0000..Tue, 15 Feb 2011

score 0 · Answer 10 · answered Dec 07 '11 at 11:34

Try something like this

require 'date'
sample = Date.parse('2011-01-01')
sample1 = Date.parse('2011-01-15')
sample2 = Date.parse('2010-12-19')
sample3 = Date.parse('2011-01-11')

puts (sample..sample1).to_a & (sample2..sample3).to_a

What this will give you is a array of intersection dates!!

score -1 · Answer 11 · answered Dec 07 '11 at 11:33

-1

I'd transfer them into an array, since arrays know the intersection-operation:

(Date.new(2011,1,1)..Date.new(2011,1,15)).to_a & (Date.new(2011,1,10)..Date.new(2011,2,15)).to_a

Of course this returns an Array. So if you want an Enumerator (Range doesn't seem to be possible since these are not consecutive values anymore) just throw to_enum at the end.

answered Dec 07 '11 at 11:33

robustus

3,626
1
26
24

Sorry - should have said that I want it to work for DateTime too, so the interval could be down to mins and secs. I also want a range returned. – jjnevis Dec 07 '11 at 11:40

Ruby: intersection between two ranges

11 Answers11

`Range#intersection` that handles `DateTime` objects as well.

Initializer

Usage

Linked

Ruby: intersection between two ranges

11 Answers11

Range#intersection that handles DateTime objects as well.

Initializer

Usage

Linked

`Range#intersection` that handles `DateTime` objects as well.