# binary search through a sorted array

require 'test/unit'

TEST_ARRAY_LENGTH = 37; 
BIGGEST_INT = 1000; 

# the problem: 
# Determine whether a presorted array of numbers x[0..n-1] contains
# a target element t. If the array contains t, the program returns 
# its position in the array; otherwise, it returns -1
# (see Beautiful Code, p87. ) 

class TestSearcher < Test::Unit::TestCase
  def test_problem_setup
    # Make sure we have an array of n elements
    a = Array.new( TEST_ARRAY_LENGTH, 0 )
    assert_equal( a.length, TEST_ARRAY_LENGTH ); 

    # Make sure that there's stuff in the array 
    a = Helper.build_random_array( TEST_ARRAY_LENGTH, BIGGEST_INT )
    for i in 0..(TEST_ARRAY_LENGTH-1) do
      # puts "#{a[i]} "
      assert_not_equal( a[i], 0 , "shouldn't have any zeros" )
      assert( a[i] > 0, "should be positive")
      assert( a[i] <= BIGGEST_INT )
    end

    assert( ! is_sorted( a ) ) 
    sorted_a = a.sort
    assert( is_sorted( sorted_a ) ) 
  end
  
  def test_inclusion
    # put a target t into the array
    # look for it in the array
    # is it there? 
    # (test this in our own special Finder class, because that's what we really want to be testing)
    a = Helper.build_random_array( TEST_ARRAY_LENGTH, BIGGEST_INT )
    finder = Finder.new( a )
    
    for divisor in 2...7 do      # for a few places in the array... 
      i = (TEST_ARRAY_LENGTH / divisor ).floor 
      t = a[ i ]
      # puts "sample target t is #{t}"
      found_index = finder.find_index_of_linear( t )
      assert_equal( a[found_index], t );
    end 
    
  end
  
  def test_not_present 
    # make an array without the target t
    a = Helper.build_random_array( TEST_ARRAY_LENGTH, 20 )    # biggest number we're letting in is 20
    finder = Finder.new( a) 

    # look for t in the array?    
    found_index = finder.find_index_of_linear( 77 );
    # it shouldn't be there 
    assert_nil( found_index ); 
    
    found_index = finder.find_index_of_linear( 12.33 );
    # it shouldn't be there 
    assert_nil( found_index ); 

    found_index = finder.find_index_of_linear( "ketchup" );
    # it shouldn't be there 
    assert_nil( found_index );     
  end
  
  def test_known_random_finds
    # we know where 20 should be in each of these 
    a = Helper.build_standard_array( 30, 1)  
    fa = Finder.new( a ); 
    assert_equal( 20, fa.find_index_of_linear( 20 ) )
    
    b = Helper.build_standard_array( 30, 2)
    fb = Finder.new( b ); 
    assert_equal( 10, fb.find_index_of_linear( 20 ) )
    
    c = Helper.build_standard_array( 30, 3)
    fc = Finder.new( c ); 
    assert_equal( 7, fc.find_index_of_linear( 21 ) )
    
    d = [10, 20, 30, 40, 50, 60, 70, 80]
    fd = Finder.new( d )
    assert_equal( nil, fd.find_index_of_linear( 22 ) )
    assert_equal( 2, fd.find_index_of_linear( 30 ) )
    
    e = [18, 22, 3, 5, 29, 1, 12, 20, 18, 38, 57]
    fe = Finder.new( e ) 
    assert_equal( nil, fe.find_index_of_linear( 1117 ) )
    assert_equal( 3, fe.find_index_of_linear( 5) )    
  end
  
  def test_known_position
    num_successful_tests = 0 
    5.upto( 10 ) { | len | 
      len = len * 3
      1000.upto( 1010 ) { | max |
        max = 10 + rand( BIGGEST_INT )
        a = Helper.build_sorted_even_array( len, max )
        assert( is_sorted( a ) ) 
        assert( a.find_all { | x | x % 2 == 0 }.size == a.size, "max was #{max}" )

        pos = rand( len - 1 )
        assert( pos >= 0 ) 
        assert( pos < len -1 )
        assert( is_sorted( a, true ), "array isn't sorted anymore" )  # it's still sorted        
        target = a[pos]

        # find the number we just inserted
        f  = Finder.new( a )
        linear_result =  f.find_index_of_linear( target )
        assert_equal( target, a[linear_result], "linear answer is wrong" )
        binary_result = f.find_index_of_binary( target )
        assert_equal( target, a[binary_result], "binary search found wrong index for #{a[pos]} after #{num_successful_tests} successful tests" )
        num_successful_tests += 1
      }
    }
    puts "#{num_successful_tests} tests completed successfully"
  end
  
  def test_many_ways 
    num_successful_tests = 0 
    10.upto( 300 ) do | len | 
      1.upto( len - 1 ) do | pos |
        random_situation( len, BIGGEST_INT, pos )
        num_successful_tests += 1 
        if (num_successful_tests % 10000 == 0) then
           puts "finished #{num_successful_tests} okay"  
         end 
      end      
    end 
  end
  
  def random_situation( length, maximum_integer, pos ) 
    # puts "testing with random array of length #{length}, max #{maximum_integer}, at pos #{pos}"
    a = Helper.build_random_array( length, maximum_integer )
    a.sort!
    # assert( is_sorted( a ) )
    assert( pos >= 0 )
    assert( pos <= length - 1, "pos #{pos} is greater than #{length-1}" )
    target = a[pos]
    f = Finder.new( a )
    binary_result = f.find_index_of_binary( target )
    assert_equal( target, a[binary_result], "binary search found wrong index for #{a[pos]}" )    
    Finder.analyze
  end 
  
  def is_sorted( arr, verbose=false ) 
    # Make sure that array is sorted
    for i in 0..(arr.length-2) do      
      if ( arr[i] > arr[i+1] ) then 
        puts "not sorted at index #{i}, arr[i] (#{arr[i]}) is not less than arr[i+1] (#{arr[i+1]})" if verbose
        return false
      end
    end 
    true
  end 

end

# Help analyze arrays 
class Helper 

  # Create an array of len elements with values 1 to max 
  def Helper.build_random_array( len, max )
    a = Array.new( len )
    for i in 0..(len-1)
      a[i] = 1 + rand( max-1 )
    end
    a
  end 
  
  def Helper.build_sorted_even_array( len, max ) 
    a = build_random_array( len, (max / 2).floor )
    a.map { | n | n * 2 }.sort
  end 

  def Helper.build_standard_array( len, factor )
    a = Array.new( len )
    for i in 0..(len-1)
      a[i] = factor * i 
    end
    a
  end 
  
  
  
end

class Finder
    @@frames = Array.new   
    @@num_searches = 0 
  
  def initialize( arr )
    # arr should be sorted
    @arr = arr;  
  end
  
  def find_index_of_linear( t )
    for i in 0..@arr.length do
      if (@arr[i] == t) then 
        return i
      end
    end
    return nil
  end 
  
  def find_index_of_binary( t ) 
    @@num_searches = @@num_searches + 1 
    binary_search( t, 0, @arr.length-1, 0 )     
  end
  
  
  # recursive implementation of binary search
  def binary_search( t, low, high, depth ) 
    if ( high < low ) 
      return nil
    end
    mid = low + ( (high-low) / 2 ).floor
    if @arr[mid] == t 
      @@frames.push( depth ) 
      return mid
    end
    
    if @arr[mid] > t 
      return binary_search( t, low, mid - 1, depth + 1 ) 
    else 
      return binary_search( t, mid + 1, high, depth + 1) 
    end    
  end
    
  # the binary_search method above uses tail recursion,
  # so we can unwind it into an iterative form
  def binary_search_iterative( t, low, high ) 
    
  end 

  def Finder.analyze
    if @@num_searches % 10000 == 0 
      puts "analyze: got #{@@num_searches} searches" 
      total_frames = @@frames.inject {|sum, n| sum + n } 
      puts "total frames is #{total_frames}"
    end
  end 
  
end