Ranges include? or overlap? with Ranges

Update: This has been added to Rails’ active_support.

The past several days I’ve found myself repeatedly writing the following lines to check if two events are conflicting:

window = course.begin_at...course.end_at
window.include?(event.begin_at) || window.include?(event.end_at?)

It finally donned on me that all I’m really doing is checking if two ranges overlap. What I really wanted to be doing is:

(course.begin_at...course.end_at).overlap?(event.begin_at...event.end_at)

While I was at it, I decided that it only made sense that Range#include? should be able to take a range:

class Range

  def overlap?(range)
    self.include?(range.first) || range.include?(self.first)
  end

  def include_with_range?(value)
    if value.is_a?(Range)
      last = value.exclude_end? ? value.last - 1 : value.last
      self.include?(value.first) && self.include?(last)
    else
      include_without_range?(value)
    end
  end
  alias_method_chain :include?, :range

end

update: thanks to Daniel Schierbeck for the better implementation of overlap?

So now, I can do things like:

(1..5).include?(2..3)    #=> true
(1..5).include?(4..8)    #=> false
(1..5).overlap?(4..8)    #=> true
(1...5).overlap?(5..10)  #=> false

I love this language!

range and ruby February 13, 2007

9 Comments

Mike Berrow February 14, 2007

Nice, but what do you think of this ..

class Range
  def overlap?(range)
    (self.to_a &amp; range.to_a).length &gt; 0
  end

  def include_with_range?(value)
    if value.is_a?(Range)
      (self.to_a &amp; value.to_a).length == value.to_a.length
    else
      include_without_range?(value)
    end
  end
  alias_method_chain :include?, :range
end

Brandon February 14, 2007

I like that it’s cleaner, my implementation is really bugging me, but I can’t figure out how to make it better.

The only problem with this is performance and memory usage. It has to instantiate all the objects in the range instead of just checking the end values.

(10.years.ago..10.years.from_now).include?(1.year.ago..1.year.from_now)

This call from IRB brought my machine to its knees because it has to instantiate a Time object for every second in both ranges. I finally killed it after it consumed 750MB of RAM.

Mike Berrow February 14, 2007

Very, very good point.
Now I see why you did it that way.

Brandon February 14, 2007

Looking at the C source code for Range, that’s similar to how it implements include?

Brandon February 14, 2007

Duh, include? can be implemented the same way as overlap?, but with a && instead of ||.

I’ve updated the code in the original post.

Mike Berrow February 15, 2007

Excellent!
I could not resist trying to wind it up tighter.
I needed to bring in Symbol.to_proc for this (incl. in Rails)

class Symbol; def to_proc; Proc.new { |obj, *args| obj.send(self, *args) }; end; end
class Range
  def ends(range)
    endr = range.exclude_end? ? range.last - 1 : range.last
    yield self.include?(range.first), self.include?(endr)
  end
  def overlap?(range)
    self.ends(range,&amp;:'|')
  end
  def include_with_range?(value)
    if value.is_a?(Range)
      self.ends(value,&amp;:'&amp;')
    else
      include_without_range?(value)
    end
  end
  alias_method_chain :include?, :range
end

Daniel Schierbeck February 19, 2007

Wouldn’t this do the trick just fine?

class Range
  def overlaps? other
    include? other.first or other.include? first
  end
end

Range#include? takes care of whether or not the end is excluded, so you don’t need to do it yourself. Furthermore, this implementation will work with all objects, not just integers.

Brandon February 20, 2007

Daniel,

Thanks, that is much better.

Daniel Schierbeck February 20, 2007

Here’s an implementation of #include?, which I’ve called #span? here.

def span? other
  include? other.first and
  other.last &lt;= (other.exclude_end? ? last.succ : last)
end

That seems to work. Cheers!

opensoul.org

Ranges include? or overlap? with Ranges

9 Comments

Popular Posts