self-sorting Array with binary search and effective support for either comparing block or item's own odrer method (<)

sorted_array.rb

# +Array+ that sorts itself on the fly.
#
# * <<, +push+ and +unshift+  insert new item in the right place
#   place, as well as +, += and +concat+.
#
# * +index+ and +find_index+ use extremely effective binary search.
#
# * +insert+ and +[]=+ are made private to forbid order changes.
#
# It is possible to provide comparing procedure in the block passed to the
# constructor. Other Array finctionality should work as supposed to
#
# Examples:
#
#   a = SortedArray[5,4,3]  # => [3, 4, 5]
#   a << 2                  # => [2, 3, 4, 5]
#   a += [0,1,10]           # => [0, 1, 2, 3, 4, 5, 10]
#
class SortedArray < Array

  # Construct sorted array from arguments:
  #
  #   SortedArray[5,4,3] => [3,4,5]
  def self.[] *array
    SortedArray.new array
  end

  # Construct sorted array from optional arguments and optional comparer block:
  #
  #    a = SortedArray.new(1,2,3,4) { |a,b| b <=> a } => [4,3,2,1]
  #    a << 5     => [5,4,3,2,1]
  #    a << 0     => [5,4,3,2,1,0]
  def initialize *array, &block
    super( array.flatten.sort(&block) ) if array
    if block
      instance_eval 'alias binsearch binsearch_comparer'
      @comparer = block
    else
      instance_eval 'alias binsearch binsearch_plain'
    end
  end

  # insert value into the array keeping it sorted
  def push value
    insert binsearch(value), value
  end

  alias << push
  alias unshift push

  # Very effective search. returns the index of the value or nil
  def index value
    i = binsearch(value)-1
    self[i] != value ? nil : i
  end

  alias find_index index

  # concatenate arrays, returns SortedArray instance
  def concat other
    SortedArray.new( other + self, &@comparer ) # !> instance variable @comparer not initialized
  end

  alias + concat

  private;  # ; compensates code formatter bug

  def binsearch_plain value
    l,r = 0, length-1
    while l <= r
      m = (r+l) / 2
      if value < self[m]
        r = m - 1
      else
        l = m + 1
      end
    end
    l
  end

  def binsearch_comparer value
    l,r = 0, length-1
    while l <= r
      m = (r+l) / 2
      if @comparer.call(value, self[m]) < 0
        r = m - 1
      else
        l = m + 1
      end
    end
    l
  end

  def insert *args
    super
  end

  def []= *args
    super
  end
end