class Array - fgmapping-2.0.0 Documentation

bsearch(range = 0 ... self.length, &block)

Alias for: bsearch_first

bsearch_first(range = 0 ... self.length) { |self| ... } click to toggle source

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.

# File lib/fgmapping/bsearch.rb, line 67
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

Also aliased as: bsearch

bsearch_last(range = 0 ... self.length) { |self| ... } click to toggle source

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.

# File lib/fgmapping/bsearch.rb, line 100
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(range = 0 ... self.length) { |self| ... } click to toggle source

Return the lower boundary. (inside)

# File lib/fgmapping/bsearch.rb, line 48
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(range = 0 ... self.length, &block) click to toggle source

Return the search result as a Range object.

# File lib/fgmapping/bsearch.rb, line 114
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(range = 0 ... self.length) { |self| ... } click to toggle source

Return the upper boundary. (outside)

# File lib/fgmapping/bsearch.rb, line 81
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