array_bsearch.rb

require_relative 'memoize'

class Object
  def _identity
    self
  end
end

#
# class providing binary search functionality around Array
#
# see https://gist.github.com/mdunsmuir/9924202 for tests and updates
#
class ArrayBSearch

  def initialize(array)
    @array = array.clone
  end

  memoize :get_sorted do |compare|
    @array.sort_by { |x| x.send(compare) }
  end

  def bracketing_bsearch(target, compare = :_identity)
    sorted_array = get_sorted(compare)
    compare_fun  = get_compare_fun(compare)

    key = compare_fun[target]
    first = 0
    last  = sorted_array.size - 1

    while last - first > 0
      mid = first + (last - first) / 2
      if key > compare_fun[sorted_array[mid]]
        first = mid + 1
      else
        last = mid
      end
    end

    neighbors = [sorted_array[first]]

    if key > compare_fun[sorted_array[first]]
      neighbors << sorted_array[first + 1] if sorted_array[first + 1]
    elsif key < compare_fun[sorted_array[first]]
      neighbors << sorted_array[first - 1] if first > 0
    end

    neighbors.sort_by(&compare)
  end

  memoize :check_numeric do |compare|
    compare_fun = get_compare_fun(compare)
    is_numeric = true
    @array.each do |x|
      is_numeric = is_numeric && compare_fun[x].is_a?(Numeric)
    end
    is_numeric ? :true : :false
  end

  def epsilon_bsearch(target, epsilon, compare = :_identity)
    unless check_numeric(compare) == :true
      raise ArgumentError.new("can only epsilon search on Arrays of Numerics!")
    end

    result = bracketing_bsearch(target, compare)
    compare_fun  = get_compare_fun(compare)
    closest = result.map { |x| [x, (compare_fun[target] - compare_fun[x]).abs] }.sort_by(&:last).first

    if closest.last <= epsilon
      closest.first
    else
      nil
    end
  end

  memoize :get_compare_fun do |sym|
    proc { |x| x.send(sym) }
  end

  private :get_compare_fun

end

memoize.rb

class Module

  #
  # enables this syntax for defining memoized instance methods:
  #
  # class Memo
  #
  #   def no_memo(*args)
  #     ...
  #   end
  #
  #   memoize(:with_memo) do |*args|
  #     ...
  #   end
  #
  # end
  #
  # Memo#with_memo is memoized, but Memo#no_memo is not. Memo#with_memo will
  # check its cache to see if it has been called with the same args before,
  # and if so it will return the result of that call (regardless of state
  # changes since the initial call).
  #
  # beware, there is a gem out there called "memoize" that is distinct from
  # these 11 lines of code
  #

  def memoize(method_name, &block)
    define_method(method_name) do |*args|
      @memo_cache ||= Hash.new
      @memo_cache[method_name] ||= Hash.new
      @memo_cache[method_name][args] ||= instance_exec(*args, &block)
    end
  end

end

test_array_bsearch.rb

require_relative 'array_bsearch'
require 'minitest/autorun'

describe ArrayBSearch do

  TEST_ARRAY = [0.169, 0.902, 0.617, 0.353, 0.234, 
                0.64, 0.4, 0.007, 0.621, 0.154, 
                0.87, 0.076, 0.307, 0.786, 0.402, 
                0.848, 0.839, 0.042, 0.784, 0.249, 
                0.259, 0.388, 0.956, 0.319, 0.092]

  describe "basic behavior in numerical search" do

    before do
      @bs = ArrayBSearch.new(TEST_ARRAY)
    end

    it "must correctly locate values in the array" do
      assert_equal([0.307], @bs.bracketing_bsearch(0.307))
    end

    it "must return bracketing values when no exact match is found" do
      assert_equal([0.786, 0.839], @bs.bracketing_bsearch(0.789))
    end

    it "must return the first/last value when the key is below/above the range" do
      assert_equal([0.007], @bs.bracketing_bsearch(0.005))
      assert_equal([0.956], @bs.bracketing_bsearch(0.999))
    end

  end

  it "must work correctly with a custom comparison function" do
    s = Struct.new(:foo, :bar)
    bs = ArrayBSearch.new(TEST_ARRAY.map { |x| s.new(x * 2, x) })
    result = bs.bracketing_bsearch(s.new(9943953534.35245, 0.319), :bar)
    assert_equal([s.new(0.638, 0.319)], result)
  end

  describe "epsilon search" do
    
    before do
      @bs = ArrayBSearch.new(TEST_ARRAY)
    end

    it "must find values within a given epsilon" do
      assert_equal(0.259, @bs.epsilon_bsearch(0.258, 0.005))
      assert_equal(0.007, @bs.epsilon_bsearch(0.005, 0.003))
    end

    it "must return nil if the appropriate value isn't found" do
      assert_nil(@bs.epsilon_bsearch(0.555, 0.002))
    end

    it "must also work with custom comparison functions" do
      s = Struct.new(:foo, :bar)
      bs = ArrayBSearch.new(TEST_ARRAY.map { |x| s.new(x * 2, x) })
      result = bs.epsilon_bsearch(s.new(9943953534.35245, 0.317), 0.005, :bar)
      assert_equal(s.new(0.638, 0.319), result)
      assert_nil(bs.epsilon_bsearch(s.new(5, 0.555), 0.002, :bar))
    end

    it "must reject non-Numeric arrays" do
      bs = ArrayBSearch.new(["foo", "bar", "baz"])
      assert_raises(ArgumentError) do
        bs.epsilon_bsearch("bar", 0.334)
      end
    end

  end

end