#
# Ruby/Bsearch - a binary search library for Ruby.
#
# Copyright (C) 2001 Satoru Takabayashi <satoru@namazu.org>
#     All rights reserved.
#     This is free software with ABSOLUTELY NO WARRANTY.
#
# You can redistribute it and/or modify it under the terms of 
# the Ruby's licence.
#
# Example:
#
#  % irb -r ./bsearch.rb
#  >> %w(a b c c c d e f).bsearch_first {|x| x <=> "c"}
#  => 2
#  >> %w(a b c c c d e f).bsearch_last {|x| x <=> "c"}
#  => 4
#  >> %w(a b c e f).bsearch_first {|x| x <=> "c"}
#  => 2
#  >> %w(a b e f).bsearch_first {|x| x <=> "c"}
#  => nil
#  >> %w(a b e f).bsearch_last {|x| x <=> "c"}
#  => nil
#  >> %w(a b e f).bsearch_lower_boundary {|x| x <=> "c"}
#  => 2
#  >> %w(a b e f).bsearch_upper_boundary {|x| x <=> "c"}
#  => 2
#  >> %w(a b c c c d e f).bsearch_range {|x| x <=> "c"}
#  => 2...5
#  >> %w(a b c d e f).bsearch_range {|x| x <=> "c"}
#  => 2...3
#  >> %w(a b d e f).bsearch_range {|x| x <=> "c"}
#  => 2...2
module SimplyUseful
  module Bsearch
    #VERSION = '1.5'

    #
    # The binary search algorithm is extracted from Jon Bentley's
    # Programming Pearls 2nd ed. p.93
    #

    #
    # Return the lower boundary. (inside)
    #
    def bsearch_lower_boundary (range = 0 ... self.length, &block)
      lower = range.first() -1
      upper = if range.exclude_end? then
                range.last
              else
                range.last + 1
              end
      while lower + 1 != upper
        mid = ((lower + upper) / 2).to_i # for working with mathn.rb (Rational)
        if yield(self[mid]) < 0
          lower = mid
        else
          upper = mid
        end
      end
      return upper
    end

    #
    # This method searches the FIRST occurrence which satisfies a
    # condition given by a block in binary fashion and return the
    # index of the first occurrence. Return nil if not found.
    #
    def bsearch_first (range = 0 ... self.length, &block)
      boundary = bsearch_lower_boundary(range, &block)
      if boundary >= self.length || yield(self[boundary]) != 0
        return nil
      else
        return boundary
      end
    end

    alias bsearch bsearch_first

    #
    # Return the upper boundary. (outside)
    #
    def bsearch_upper_boundary (range = 0 ... self.length, &block)
      lower = range.first() -1
      upper = if range.exclude_end? then
                range.last
              else
                range.last + 1
              end
      while lower + 1 != upper
        mid = ((lower + upper) / 2).to_i # for working with mathn.rb (Rational)
        if yield(self[mid]) <= 0
          lower = mid
        else
          upper = mid
        end
      end
      return lower + 1 # outside of the matching range.
    end

    #
    # This method searches the LAST occurrence which satisfies a
    # condition given by a block in binary fashion and return the
    # index of the last occurrence. Return nil if not found.
    #
    def bsearch_last (range = 0 ... self.length, &block)
      # `- 1' for canceling `lower + 1' in bsearch_upper_boundary.
      boundary = bsearch_upper_boundary(range, &block) - 1

      if (boundary <= -1 || yield(self[boundary]) != 0)
        return nil
      else
        return boundary
      end
    end

    #
    # Return the search result as a Range object.
    #
    def bsearch_range (range = 0 ... self.length, &block)
      lower = bsearch_lower_boundary(range, &block)
      upper = bsearch_upper_boundary(range, &block)
      return lower ... upper
    end

    def bfind(range = 0 ... self.length, &block)
      pos = self.bsearch(range, &block)
      return nil if pos.nil?
      self[pos]
    end
  end
end

Array.send :include, SimplyUseful::Bsearch