finds boundaries of a range of special items in a sequence

finder.rb

class Finder

  attr_reader :right, :left

  def initialize attrs
    @fetch = attrs[:fetch]
    @test  = attrs[:inside_test]
    @index = attrs[:inside_index]
    @step  = attrs[:step]

    find_left_border  nil, step_left(@index),  @index
    find_right_border step_right(@index), @index, nil
  end

  def find_left_border left, index, right
    puts "#{left} #{index} #{right}"
    puts "search range #{ right - left }" if left
    if inside? index
      find_left_border( left, step_left(index, left), index )
    elsif !next_to? index, right
      find_left_border( index, middle(index, right),   right )
    else
      @left = index
    end
  end

  def find_right_border left, index, right
    puts "#{left} #{index} #{right}"
    puts "search range #{ right - left }" if right
    if inside? index
      find_right_border( index, step_right(index, right), right )
    elsif !next_to? left, index
      find_right_border( left,  middle(left, index),      index )
    else
      @right = index
    end
  end

  def next_to? a,b
    a.succ == b
  end

  def inside? index
    element = @fetch.call(index)    
    element && @test.call(element)
  end

  def step_left from, boundary = nil
    return middle(boundary, from) if boundary
    max(0, from - @step)
  end

  def step_right from, boundary = nil
    return middle(from, boundary) + 1 if boundary
    from + @step
  end

  def middle left, right
    left + (( right - left ) / 2)
  end

  def max left, right
    ( left > right ) ? left : right
  end

end

finder_spec.rb

require_relative 'finder.rb'


describe Finder do

  [
    { left:   4, right: 10, index:  7, size:  15 },
    { left:   4, right: 10, index:  8, size:  15 },
    { left:   4, right: 10, index:  9, size:  15 },
    { left:   3, right: 10, index:  9, size:  25 },
    { left:   3, right: 100, index:  9, size:  250 },
  ].each do |attrs|

    left, right, index, size = attrs[:left], attrs[:right], attrs[:index], attrs[:size]

    elements = []
    (left+1).times { elements << 0 }
    (right-(left+1)).times { elements << 1 }
    (size-right).times { elements << 0 }

    context "with index inside of #{index} for list #{elements.inspect}" do
      before do
        @finder = Finder.new fetch:        lambda { |id| elements[id] },
                             inside_test:  lambda { |element| element == 1 },
                             step:         5,
                             inside_index: index
      end

      it "should find the left border #{left}" do
        @finder.left.should == left
      end

      it "should find the right border #{right}" do
        @finder.right.should == right
      end

    end

  end

end