From: ara.t.howard@...
Date: 2006-05-06T03:50:56+09:00
Subject: Re: Finding an interval in a sorted array?

On Sat, 6 May 2006, Bil Kleb wrote:

> Hello,
>
> Surely there is a way to find an interval in a sorted array
> without resorting to indices?  (I'm drawing a blank.)
>
> require 'test/unit'
>
> class Array
>   def interval_containing( x )
>     # elegant code goes here
>   end
> end
>
> class TestIntervalFinder < Test::Unit::TestCase
>   def test_finds_intervals
>     data = [ 0, 1, 2 ].sort
>     assert_equal [0],   data.interval_containing(-0.2)
>     assert_equal [0],   data.interval_containing( 0.0)
>     assert_equal [0,1], data.interval_containing( 0.5)
>     assert_equal [1],   data.interval_containing( 1.0)
>     assert_equal [1,2], data.interval_containing( 1.6)
>     assert_equal [2],   data.interval_containing( 2.0)
>     assert_equal [2],   data.interval_containing( 5.0)
>   end
> end
>
> Thanks,
> -- 
> Bil
> http://fun3d.larc.nasa.gov
>

this ought to get you going


   class Array
     #
     # extract any sequences in a sorted list
     #
     #   [0, 1, 2, 4, 5].sequences        #=> [0..2, 4..5]
     #   [-5, -4, -4, -3, 0, 1].sequences #=> [-5..-4, -4..-3, 0..1]
     #
     def sequences list = self.sort
       distance = lambda do |a,b|
         (b - a).abs
       end
       continuous = lambda do |range, list|
         first, last = range.first, range.last
         a, b = list[first], list[last]
         ((list.empty? or (distance[a,b] == distance[first,last])) ? (a .. b) : nil)
       end
       discrete = lambda do |range, list|
         first, last = range.first, range.last
         edge = last + 1
         (edge >= list.length or distance[list[last], list[edge]] != 1)
       end
       sequence = lambda do |range, list|
         first, last = range.first, range.last
         (list[first] .. list[last])
       end

       last = list.length - 1
       a, b = 0, last

       accum = []
       while a <= b and a < list.length and b < list.length
         range = a .. b

         if continuous[ range, list ]
           if discrete[ range, list ]
             accum << sequence[ range, list ]
             a, b = b + 1, last # move a and b up
           else
             b = b + (distance[b, last] / 2) # move b up
           end
         else
           b = a + (distance[a, b] / 2) # move b down
         end
       end
       accum
     end
   end


i think you need to re-write your test since an array could have the same
interval twice - eg test must be on a list of intervals

regards.



-a
-- 
be kind whenever possible... it is always possible.
- h.h. the 14th dali lama