On Aug 6, 1:48 pm, Bryan R. [email protected] wrote:
(1…11) (22…29)
Here is a module from our project earlier this year:
# 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 <> [ [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 <
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
