[ruby-dev:14478] Re: Ruby/Bsearch

At Thu, 16 Aug 2001 00:15:05 +0900,
Satoru Takabayashi wrote:
> 作者です。
> 
> APIは、こんな感じでいいでしょうか。
> <http://namazu.org/~satoru/ruby-bsearch/>
> まずいようであれば修正します。

　rough/ 以下のモジュールは標準採用への登竜門ということで、よい
API ときれいな実装のためには互換性など気にせずにバンバンいじって
しまいましょう。


　今一つだけ気付いたのは、 1...5 形式の Range に対応していないと
いう些細な不具合です。あと、 API についていうと、こんな風にする
のはどうかなーと思いました。

	bsearch(v) で従来の bsearch {|x| x <=> v} と等価になる。
	ただし、要素が降順に並んでいる場合は従来の
	bsearch {|x| v <=> x} と等価。

	bsearch(v) {|x| f(x) } で従来の bsearch {|x| f(x) <=> v }
	と等価になる。ただし、要素が降順の場合は従来の
	bsearch {|x| v <=> f(x) } と等価。

	降順かどうかは最初と最後の要素を比較して判断する。
	ブロックを与えた場合はブロックの評価値を比較して判断する。

まあ、言葉で書くだけではあれなので実装してみました。

  def bsearch_first(value, range = 0...length())
    low = range.first() - 1

    if range.exclude_end?
      high = range.last()
    else 
      high = range.last() + 1
    end

    if block_given?
      desc = yield(first()) > yield(last())
    else
      desc = first() > last()
    end

    while low + 1 != high
      mid = (low + high) / 2

      if block_given?
        cmp = yield(self[mid]) <=> value
      else
        cmp = self[mid] <=> value
      end

      if !desc && cmp < 0 || desc && cmp > 0
        low = mid
      else 
        high = mid
      end
    end

    if high >= self.length
      return nil
    end

    if block_given?
      cmp = yield(self[high]) != value
    else
      cmp = self[high] != value
    end

    if cmp
      return nil
    else 
      return high
    end
  end


　単純な走査の場合はブロックの呼び出しがなくなるものの、条件判断が
いろいろ増えてしまっている気も。。

　まあ、使い方が若干直感的になるという方が主眼です。

> CVSアカウントをもらえれば継続的に保守できます。

　pserver 経由のアクセスになるので、希望のアカウント名と crypt
されたパスワードとを私宛に送ってください。すぐに発行します。


(入力した文字列を crypt する one-liner)

ruby -e "a=(0..127).map{|i|'%c'%i}.grep /[\da-z]/i;puts gets.chomp.crypt(a[rand a.size]+a[rand a.size])"

-- 
                     /
                    /__  __            Akinori.org / MUSHA.org
                   / )  )  ) )  /     FreeBSD.org / Ruby-lang.org
Akinori MUSHA aka / (_ /  ( (__(  @ iDaemons.org / and.or.jp

"Freeze this moment a little bit longer, make each impression
  a little bit stronger..  Experience slips away -- Time stand still"