From: vld <vdidenko@...>
Date: 2008-08-07T23:15:35+09:00
Subject: Re: Need help detecting overlapping ranges

On Aug 6, 1:48 pm, Bryan Richardson <btrichard...@gmail.com> wrote:
> Hello all,
>
> I am writing some code where I create a bunch of ranges, then at the end
> I want to create new ranges out of any ranges that overlap one another.
> For example, say I have the following ranges:
>
> (1..5) (7..11) (22..29) (5..8)
>
> Given the ranges above, I want to end up with the following ranges:
>
> (1..11) (22..29)

Here is a module from our project earlier this year:

<pre>
# Module Spans and the associated Array "span" method implements an
array of numeric
# intervals with "merge", "complement", "fit", and other convenience
methods
# Copyright (C) 2008  GETCO LLC
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# The full text of the license as of August 06, 2008, is available at
#    http://www.gnu.org/licenses/gpl-3.0.txt
#
class Array

  #  Module +Spans+ and the associated Array span method implements an
array numeric intervals - aka +spans+
  module Spans

    # Reduces the set of spans by combining the overlapping intervals
together to form larger intervals. Adjacent spans are not merged.
    # *IMPORTANT:* The return set is a set of *copies* of objects,
*not the references* to the original objects. The new object have some
of their boundaries changed, but it is random, which objects are
deleted, and which have new boundaries.
    #
    #  >> [ [5,5], [10,20], [3,4], [5,6], [15,25], [3,7] ].spans.merge
    #  => [[3, 7], [10, 25]]
    def merge
      result = deep_clone.position_sort!
      result.each_index do |idx|

        break if idx >= result.size - 1
        curr = result[ idx ]
        succ = result[ idx + 1 ]

        if overlap?( curr, succ )
          curr.send("#{@span_left}=",  [curr.send(@span_left),
succ.send(@span_left) ].min )
          curr.send("#{@span_right}=", [curr.send(@span_right),
succ.send(@span_right)].max )
          result.delete_at( idx + 1)
          redo
        end
      end
      return result.spans( @span_left, @span_right )
    end

    # Provides the spans' complement to fill the specified interval.
The complement spans is a simple array of new arrays, responding to
the +first+ and +last+ methods.
    #
    #  >> [ [5,5], [10,20], [3,4], [5,6], [15,25],
[3,7] ].spans.complement(-1,28)
    #  => [[-1, 3], [7, 10], [25, 28]]
    def complement( left, right )
      complemented = []
      merge.clean!.each do |span|
        break if right <= span.send(@span_left)
        next  if span.send(@span_right)  <  left
        complemented << [ left, span.send(@span_left) ] if left <
span.send(@span_left)
        left = span.send(@span_right)
      end
      complemented << [ left, right ] if left < right
      complemented.spans
    end

    # Finds a first arbitrary span to fit the specified size. Returns
one of the original objects in the provided spans array.
    #
    #  >> [ [5,5], [2,4], [3,7] ].spans.fit( 2 )
    #  => [2, 4]
    def fit( requested_size )
      # see in-code comment to fit_all
      find do |a|
        delta = a.send(@span_right) - a.send(@span_left)
        (delta = requested_size) or (delta > requested_size)
      end
    end

    # Finds all spans to fit the specified size. Returns a new, but
filtered, array of the original objects. The array alreasy has +Spans+
mixed in with the original boundary names.
    #
    #  >> [ [5,5], [2,4], [3,7] ].spans.fit_all( 2 )
    #  => [[2, 4], [3, 7]]
    def fit_all( requested_size )
      self.select do |a|
        ( requested_size <= (a.send(@span_right) -
a.send(@span_left)) )
      end.spans( @span_left, @span_right )
    end

    # Removes all empty and invalid spans from the the calling
instance
    def clean!() delete_if{ |s| s.send(@span_left) >=
s.send(@span_right) } end

    protected

    def position_sort()  sort  { |a,b| position( a, b ) } end
    def position_sort!() sort! { |a,b| position( a, b ) } end

    def position( a, b )
      if a.send(@span_left) < b.send(@span_left)
        a.send(@span_right) > b.send(@span_left)  ? 0 : -1 # -1 is
when "a" is at left of "b"
      else
         a.send(@span_left) < b.send(@span_right) ? 0 :  1 # 1 is when
"a" is at right of "b"
      end
    end

    def overlap?( a, b )
      position( a, b ) == 0
    end

    def deep_clone
        klone = self.clone
        klone.clear
        each { |v| klone << v.clone }
        klone
    end
  end

  # The setter method for an array's first element
  def first=( value) self[0] =value end

  # The setter method for an array's last element
  def last=(  value) self[-1]=value end

  # Sets up the calling +Array+ instance to be processed as +Spans+ -
a collection of intervals. If arguments provided those should be names
of getter/setter methods for left and right sides on intervals
accordingly.
  def spans( left_name = nil, right_name = nil )
    # Validates, that all spans in the array have properly ordered
ends (beginning before or at the end)
    def valid?
      each { |span| return false if span.send(@span_left) >
span.send(@span_right) }
      return true
    end

    @span_left  = (  left_name || "first" )
    @span_right = ( right_name || "last"  )
    unless valid?
      remove_instance_variable(:@span_left)
      remove_instance_variable(:@span_right)
      raise ArgumentError, "Can not consider this array for spans -
invalid intervals."
    end
    self.extend Spans
  end
end
</pre>