########## アルゴリズムの実装

class Array                       ## 配列、Ruby の中心的な組み込みクラス
                                  ## Ruby でクラスの再開、メソッドの追加が可能
                                  # 検索アルゴリズムを Array に追加すること
  #                               #  により、使用が簡単になる:
  # Linear Search Algorithm       #  linear_search(array, value) のではなく、
  #                               #  array.linear_search(value)
  def linear_search (value)       ## def はメソッドの定義 (end まで)
    i = 0
    while i < length              ## length は Array のメソッド、要素数を返す
      if value == self[i]         ## self は現在のオブジェクト (ここは配列) を指す。
        return i
      end
      i += 1                      ## Ruby に ++/-- は存在しない
    end
    nil                           ## nil は「値無し」の意味。ここで「見つかってない」の印。
  end                             ## メソッドの終わりに return が不要 (最後の値は戻り値)

  #
  # Binary Search Algorithm
  #
  def binary_search (value)       # 配列が整列されていることが前提
    low = 0                       # 最初の候補の番号
    high = length - 1             # 最後の候補の番号
    while low <= high
      middle = (low + high) / 2   # 分岐点の計算
      at_middle = self[middle]
      if at_middle > value
        high = middle - 1
      elsif at_middle < value
        low = middle + 1
      else                        # value == at_middle
        return middle
      end
    end
    nil
  end
end                               # クラス Array へのメソッド追加終了


########## 参考のため: メゾッドのではなく、関数での実装

# Array のメソッドのではなく、関数での実装の例:
def linear_search (array, value)
  i = 0
  l = array.length
  while i < l
    if value == array[i]
      return i
    end
    i += 1
  end
  nil
end

# Array のメソッドのではなく、関数での実装の例: (メソッドでも同様に可能)
def linear_search (array, value)
  array.each_with_index do |v, i| ## each_with_index は配列の要素とその指数を辿る
    return i  if v == value       ## 後置 if で end 無しに簡単な if 文が記述可能
  end
  nil
end


########## 実験のためのプログラム
                                  ## require でライブラリをインクルード
require 'profiler'                ## profiler ライブラリは各メソッドの実行回数を記録
require 'benchmark'               ## benchmark ライブラリは実行時間を比較

class Fixnum
  alias :plus :'+'
  def + (other)  self.plus other  end
  alias :minus :'-'
  def - (other)  self.minus other  end
  alias :divide :'/'
  def / (other)  self.divide other  end
end

def profile
  Profiler__::start_profile       ## 実行回数の記録の開始
  yield                           ## メソッドに渡されたブロックの実行
  Profiler__::stop_profile        ## 実行回数の記録の修了
  Profiler__::print_profile(STDOUT) ## 実行回数の出力
end


                                  ## 大文字から始まる識別子は定数 (クラス名も含む)
COUNT = 10000                     # 配列の要素の数 (宿題 1 のために変更)
RANGE_TOP = 1000000               # 要素の値 (整数) の上限

TEST_ARRAY = Array.new(COUNT) do  # TEST_ARRAY に乱数で作った要素を収集
  rand RANGE_TOP                  # 0 <= x < RANGE_TOP の整数の乱数
end
                                  ## ビックリマークのついたメソッドは「要注意」
                                  ## 多くの場合「その場で、データを破壊的に上書き」の意味
TEST_ARRAY.sort!.uniq!            # 2分探索のため、整列 (sort) と同一値の排除 (uniq) が必要

#p TEST_ARRAY                     # テスト用データの確認

# 実行用に便利なメソッド
def test_linear
  TEST_ARRAY.linear_search(rand RANGE_TOP)
end

def test_binary
  TEST_ARRAY.binary_search(rand RANGE_TOP)
end

# profiling function call count
puts "PROFILING LINEAR and BINARY SEARCH" ## 文字列の出力

profile { test_linear }           ## 線形探索のメソッドの実行回数の記録

puts                              ## 空行の出力

profile { test_binary }           ## 2分探索のメソッドの実行回数の記録

puts                               

# performance testing program
puts "BENCHMARKING LINEAR and BINARY SEARCH"
Benchmark::bm do |bm|             # 実行時間の比較
  bm.report('linear search') { 1000.times { test_linear } }
  bm.report('binary search') { 10000.times { test_binary } }
end                ## times は一定回数の繰り返し (do .. end または { .. } の間)