Better Range Intersection in Ruby

A little while ago I posted a solution for finding intersections between timespans (“Detecting DateTime Timespan Overlap In Ruby”). It works but, as Dan Kubb pointed out to me, it doesn’t use the most graceful means of determining intersections between Range instances, particularly for very large ranges.

Not content to leave it at that, Dan of course provides a better solution, complete with tests (but wait! see below for even better code):

#!/usr/bin/env ruby

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

    min, max = first, exclude_end? ? max : last
    other_min, other_max = other.first, other.exclude_end? ? other.max : other.last

    new_min = self === other_min ? other_min : other === min ? min : nil
    new_max = self === other_max ? other_max : other === max ? max : nil

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

  alias_method :&, :intersection
end

if __FILE__ == $0
  range = 5..10

  tests = {
    1..4   => nil,     # before
    11..15 => nil,     # after
    1..6   => 5..6,    # overlap_begin
    9..15  => 9..10,   # overlap_end
    1..5   => 5..5,    # overlap_begin_edge
    10..15 => 10..10,  # overlap_end_edge
    5..10  => 5..10,   # overlap_all
    6..9   => 6..9,    # overlap_inner

    1...5  => nil,     # before       (exclusive range)
    1...7  => 5..6,    # overlap_begin      (exclusive range)
    1...6  => 5..5,    # overlap_begin_edge (exclusive range)
    5...11 => 5..10,   # overlap_all  (exclusive range)
    6...10 => 6..9,    # overlap_inner      (exclusive range)
  }

  tests.each do |other, expected|
    result = range.intersection(other)
    result_status = ( result == expected ) ? "passed" : "failed"
    puts "#{range.inspect} #{other.inspect} result #{result_status}: #{result.inspect} (#{expected.inspect})"
  end
end

I like it.

Update: On June 30, 2011 Montgomery Kosma found a bug in the implementation above. Wrote Montgomery:

Turns out that the function fails where the first argument is a range with an excluded endpoint. E.g.,

a = 1…10
b = 5..15

a & b yields nil, instead of the expected answer (5..9).

This is due to a cool little name collision, undetectable in most instances. Except when exclude_end? is true, the method max evaluates to the same thing as what you’d expect had been stored in the variable max.

Changing min and max to my_min and my_max solves the problem. And makes the method just a bit more efficient at the same time.

Ruby is great, like lisp and smalltalk in its beauty, but like many beautiful things it has a dangerous side, as one can see from this otherwise elegant piece of code. This is also a good example of a test suite that really needed bookends (testing 1…10 as well as 1..10).

A new version with his improvements and a test to cover them:

#!/usr/bin/env ruby

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

    my_min, my_max = first, exclude_end? ? max : last
    other_min, other_max = other.first, other.exclude_end? ? other.max : other.last

    new_min = self === other_min ? other_min : other === my_min ? my_min : nil
    new_max = self === other_max ? other_max : other === my_max ? my_max : nil

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

  alias_method :&, :intersection
end

if __FILE__ == $0
  def do_test( range, other, expected )
    result = range.intersection(other)
    result_status = ( result == expected ) ? "passed" : "failed"
    puts "#{range.inspect} #{other.inspect} result #{result_status}: #{result.inspect} (#{expected.inspect})"
  end

  # Test an inclusive range
  range = 5..10

  tests = {
    1..4   => nil,     # before
    11..15 => nil,     # after
    1..6   => 5..6,    # overlap_begin
    9..15  => 9..10,   # overlap_end
    1..5   => 5..5,    # overlap_begin_edge
    10..15 => 10..10,  # overlap_end_edge
    5..10  => 5..10,   # overlap_all
    6..9   => 6..9,    # overlap_inner

    1...5  => nil,     # before             (exclusive range)
    1...7  => 5..6,    # overlap_begin      (exclusive range)
    1...6  => 5..5,    # overlap_begin_edge (exclusive range)
    5...11 => 5..10,   # overlap_all        (exclusive range)
    6...10 => 6..9,    # overlap_inner      (exclusive range)
  }

  tests.each do |other, expected|
    do_test( range, other, expected )
  end

  # Test an exclusive range
  # This covers a bug found by Montgomery Kosma in the original code
  range = 1...10

  tests = {
    5..15 => 5..9       #overlap_end
  }

  tests.each do |other, expected|
    do_test( range, other, expected )
  end
end

It just gets better and better!