Module: ALib::Bsearch::BsearchMethods

Defined in:
lib/alib.rb,
lib/alib-0.3.1.rb

Instance Method Summary collapse

Instance Method Details

#bsearch(*a, &b) ⇒ Object

alias bsearch bsearch_first



1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
 
# File 'lib/alib.rb', line 1936

def bsearch(*a, &b)
    #--{{{
  unless b
    obj = a.first
    b = lambda{|x| x <=> obj}
    bsearch_first(&b)
  else
    bsearch_first(*a, &b)
  end
    #--}}}
end

#bsearch_first(arg = nil, &block) ⇒ Object

new



1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
 
# File 'lib/alib.rb', line 1907

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

#bsearch_last(arg = nil, &block) ⇒ Object

new



1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
 
# File 'lib/alib.rb', line 1995

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

#bsearch_lower_boundary(arg = nil, &block) ⇒ Object

new



1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
 
# File 'lib/alib.rb', line 1862

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

#bsearch_range(arg = nil, &block) ⇒ Object

new



2031
2032
2033
2034
2035
2036
2037
 
# File 'lib/alib.rb', line 2031

def bsearch_range (range = 0 ... self.length, &block)
    #--{{{
  lower = bsearch_lower_boundary(range, &block)
  upper = bsearch_upper_boundary(range, &block)
  return lower ... upper
    #--}}}
end

#bsearch_upper_boundary(arg = nil, &block) ⇒ Object

new



1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
 
# File 'lib/alib.rb', line 1951

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