From: "ara.t.howard" <ara.t.howard@...>
Date: 2008-08-07T05:42:29+09:00
Subject: Re: Need help detecting overlapping ranges


On Aug 6, 2008, at 12:48 PM, Bryan Richardson 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 the code I've come up with so far (ranges is an array of  
> ranges
> similar to what I described above in my example):
>
>  ranges = @failed.outages
>  changes = true
>  while changes
>    changes = false
>    outages = ranges.collect { |range| range.to_a }
>    ranges.clear
>    while !outages.empty?
>      outage = outages.shift
>      outages.each do |n|
>        unless (outage & n).empty?
>          outage = (outage + n).uniq.sort
>          outages.delete(n)
>          changes = true
>        end
>      end
>      ranges << (outage.first..outage.last)
>    end
>  end
>  return ranges.sort { |a,b| a.first <=> b.first }
>
> This code works, but it is *EXTREMELY* slow (my current array of  
> ranges
> is averaging out to ~24000 range elements).  Anyone have an idea of  
> how
> to speed it up?
>
> --
> Thanks!
> Bryan
> -- 
> Posted via http://www.ruby-forum.com/.
>

this should be quite fast with a few constraints.  the main thing is  
that you do not have to convert ranges to detect the overlap nor to do  
the merge.




cfp:~ > cat a.rb
def collapse_inclusive_integer *ranges
   ranges.flatten!
   ranges.compact!

   ranges.each do |r|
     raise ArgumentError, "exclusive range #{ range.inspect }" if
       r.exclude_end?
     raise ArgumentError, "non-integer range #{ range.inspect }" unless
       Integer === r.begin and Integer === r.end
   end

   overlaps = lambda do |i,j|
     a, b = ranges[i], ranges[j]
     a.begin <= b.end and b.begin <= a.end
   end

   merge = lambda do |i,j|
     a, b = ranges[i], ranges[j]
     values = a.begin, a.end, b.begin, b.end
     min, max = values.min, values.max
     range = min .. max
     src, dst = i < j ? [i,j] : [j,i]
     ranges[src] = range
     ranges.delete_at dst
     range
   end

   loop {
     catch('start over'){
       size = ranges.size
       size.times do |i|
         size.times do |j|
           next if i == j
           if overlaps[i,j]
             merge[i,j]
             throw 'start over'
           end
         end
       end
       return ranges
     }
   }
end

ranges = 1..5, 7..11, 22..29, 5..8

p ranges
p collapse_inclusive_integer(ranges)





cfp:~ > ruby a.rb
[1..5, 7..11, 22..29, 5..8]
[1..11, 22..29]


a @ http://codeforpeople.com/
--
we can deny everything, except that we have the possibility of being  
better. simply reflect on that.
h.h. the 14th dalai lama