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>
