Module: ALib::Bsearch::BsearchMethods
- Defined in:
- lib/alib.rb,
lib/alib-0.3.1.rb
Instance Method Summary collapse
-
#bsearch(*a, &b) ⇒ Object
alias bsearch bsearch_first.
-
#bsearch_first(arg = nil, &block) ⇒ Object
new.
-
#bsearch_last(arg = nil, &block) ⇒ Object
new.
-
#bsearch_lower_boundary(arg = nil, &block) ⇒ Object
new.
-
#bsearch_range(arg = nil, &block) ⇒ Object
new.
-
#bsearch_upper_boundary(arg = nil, &block) ⇒ Object
new.
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 |