Module: ALib::Bsearch::BsearchMethods

Defined in:
lib/alib-0.5.1/bsearch.rb

Instance Method Summary collapse

Instance Method Details

#bsearch(*a, &b) ⇒ Object

alias bsearch bsearch_first



124
125
126
127
128
129
130
131
132
133
134
 
# File 'lib/alib-0.5.1/bsearch.rb', line 124

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



95
96
97
98
99
100
101
102
103
104
 
# File 'lib/alib-0.5.1/bsearch.rb', line 95

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



183
184
185
186
187
188
189
190
191
192
193
194
 
# File 'lib/alib-0.5.1/bsearch.rb', line 183

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



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/alib-0.5.1/bsearch.rb', line 50

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



219
220
221
222
223
224
225
 
# File 'lib/alib-0.5.1/bsearch.rb', line 219

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



139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/alib-0.5.1/bsearch.rb', line 139

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