module BinSearch::Methods

Public Instance Methods

bin_assoc(elem, mode, low = 0, high = -1) { |elem, b| ... } click to toggle source

Binary search for the first elem in this array matching according to mode in the range (low..high-1)

By default, <=> is used to compare elements. Alternatively, a comparator may be specified as block parameter

The supported modes are

  • :asc - array is expected to be sorted in ascending order, first geq elem is matched

  • :asc_eq - array expected to be sorted in ascending order, first eq elem is matched

  • :desc - array is expected to be sorted in descending order, first leq elem is matched

  • :desc_eq - array is expected to be sorted in descending order, first eq elem is matched

@param [Object] elem elem to search for @param [Fixnum] low lower bound (inclusive) @param [Fixnum] high upper bound (inclusive, nil for last element) @param [:asc, :desc, :asc_eq, :desc_eq] mode matching mode @return [Array] [index, first matching elem] in self, or nil if not found

# File lib/bin_search/bin_search.rb, line 136
def bin_assoc(elem, mode, low = 0, high = -1)
  dir      = if ::BinSearch::MODE_IS_ASC.include?(mode) then +1 else -1 end
  check_eq = ::BinSearch::MODE_CHECK_EQ.include?(mode)
  high     = size - 1 if high < 0
  if block_given?
    then _bin_assoc(elem, low, high, dir, check_eq) { |b| yield elem, b }
    else _bin_assoc(elem, low, high, dir, check_eq) { |b| elem <=> b } end
end
bin_assoc_by(elem, mode, low = 0, high = -1) { |elem| ... } click to toggle source

Binary search for the first elem in this array matching according to mode in the range (low..high-1)

Elements are compared using <=> after mapping them using the provided block

The supported modes are

  • :asc - array is expected to be sorted in ascending order, first geq elem is matched

  • :asc_eq - array expected to be sorted in ascending order, first eq elem is matched

  • :desc - array is expected to be sorted in descending order, first leq elem is matched

  • :desc_eq - array is expected to be sorted in descending order, first eq elem is matched

@param [Object] elem elem to search for @param [Fixnum] low lower bound (inclusive) @param [Fixnum] high upper bound (inclusive, nil for last element) @param [:asc, :desc, :asc_eq, :desc_eq] mode matching mode @return [Array] [index, first matching elem] in self, or nil if not found

# File lib/bin_search/bin_search.rb, line 162
def bin_assoc_by(elem, mode, low = 0, high = -1)
  dir      = if ::BinSearch::MODE_IS_ASC.include?(mode) then +1 else -1 end
  check_eq = ::BinSearch::MODE_CHECK_EQ.include?(mode)
  high     = size - 1 if high < 0
  e        = yield elem
  _bin_assoc(elem, low, high, dir, check_eq) { |b| e <=> (yield b) }
end
bin_index(elem, mode, low = 0, high = -1) { |elem, b| ... } click to toggle source

Binary search for the first elem in this array matching according to mode in the range (low..high-1)

By default, <=> is used to compare elements. Alternatively, a comparator may be specified as block parameter

The supported modes are

  • :asc - array is expected to be sorted in ascending order, first geq elem is matched

  • :asc_eq - array expected to be sorted in ascending order, first eq elem is matched

  • :desc - array is expected to be sorted in descending order, first leq elem is matched

  • :desc_eq - array is expected to be sorted in descending order, first eq elem is matched

@param [Object] elem elem to search for @param [Fixnum] low lower bound (inclusive) @param [Fixnum] high upper bound (inclusive, -1 for last element) @param [:asc, :desc, :asc_eq, :desc_eq] mode matching mode @return [Fixnum] index of first matching elem in self, or -1 if not found

# File lib/bin_search/bin_search.rb, line 32
def bin_index(elem, mode, low = 0, high = -1)
  dir      = if ::BinSearch::MODE_IS_ASC.include?(mode) then +1 else -1 end
  check_eq = ::BinSearch::MODE_CHECK_EQ.include?(mode)
  high     = size - 1 if high < 0
  if block_given?
    then _bin_index(elem, low, high, dir, check_eq) { |b| yield elem, b }
    else _bin_index(elem, low, high, dir, check_eq) { |b| elem <=> b } end
end
bin_index_by(elem, mode, low = 0, high = -1) { |elem| ... } click to toggle source

Binary search for the first elem in this array matching according to mode in the range (low..high-1)

Elements are compared using <=> after mapping them using the provided block

The supported modes are

  • :asc - array is expected to be sorted in ascending order, first geq elem is matched

  • :asc_eq - array expected to be sorted in ascending order, first eq elem is matched

  • :desc - array is expected to be sorted in descending order, first leq elem is matched

  • :desc_eq - array is expected to be sorted in descending order, first eq elem is matched

@param [Object] elem elem to search for @param [Fixnum] low lower bound (inclusive) @param [Fixnum] high upper bound (inclusive, -1 for last element) @param [:asc, :desc, :asc_eq, :desc_eq] mode matching mode @return [Fixnum] index of first matching elem in self, or -1 if not found

# File lib/bin_search/bin_search.rb, line 58
def bin_index_by(elem, mode, low = 0, high = -1)
  dir      = if ::BinSearch::MODE_IS_ASC.include?(mode) then +1 else -1 end
  check_eq = ::BinSearch::MODE_CHECK_EQ.include?(mode)
  high     = size - 1 if high < 0
  e        = yield elem
  _bin_index(elem, low, high, dir, check_eq) { |b| e <=> (yield b) }
end
bin_search_by(elem, mode, low = 0, high = -1) { |elem| ... } click to toggle source

Binary search for the first elem in this array matching according to mode in the range (low..high-1)

Elements are compared using <=> after mapping them using the provided block

The supported modes are

  • :asc - array is expected to be sorted in ascending order, first geq elem is matched

  • :asc_eq - array expected to be sorted in ascending order, first eq elem is matched

  • :desc - array is expected to be sorted in descending order, first leq elem is matched

  • :desc_eq - array is expected to be sorted in descending order, first eq elem is matched

@param [Object] elem elem to search for @param [Fixnum] low lower bound (inclusive) @param [Fixnum] high upper bound (inclusive, nil for last element) @param [:asc, :desc, :asc_eq, :desc_eq] mode matching mode @return [Object] first matching elem in self, or nil if not found

# File lib/bin_search/bin_search.rb, line 110
def bin_search_by(elem, mode, low = 0, high = -1)
  dir      = if ::BinSearch::MODE_IS_ASC.include?(mode) then +1 else -1 end
  check_eq = ::BinSearch::MODE_CHECK_EQ.include?(mode)
  high     = size - 1 if high < 0
  e        = yield elem
  _bin_search(elem, low, high, dir, check_eq) { |b| e <=> (yield b) }
end

Private Instance Methods

_bin_assoc(elem, low, high, dir, check_eq) { |cur| ... } click to toggle source
# File lib/bin_search/bin_search.rb, line 244
def _bin_assoc(elem, low, high, dir, check_eq)
  sz   = high - low
  cur  = nil
  if (sz >> LIN_BITS).zero?
    # On 2012 cpus, linear search is slightly faster than binary search
    # if the number of searched elements is in the range of 50-100 elts
    cur_index = low
    while cur_index <= high
      cur = self[cur_index]
      cmp = yield cur
      if cmp == dir
        cur_index += 1
      else
        return (if (!cur || (check_eq && cmp.nonzero?)) then nil else [cur_index, cur] end)
      end
    end
    return nil
  else
    # Classic binary search
    cmp_ = 0
    last = -1
    while low <= high
      mid_index = low + (sz >> 1)
      mid = self[mid_index]
      cmp = yield mid
      if cmp == dir
        low  = mid_index + 1
      else
        cmp_ = cmp
        cur  = mid
        last = mid_index
        high = mid_index - 1
      end
      sz -= 1
    end
    return (if (!cur || (check_eq && cmp_.nonzero?)) then nil else [last, cur] end)
  end
end
_bin_index(elem, low, high, dir, check_eq) { |cur| ... } click to toggle source
# File lib/bin_search/bin_search.rb, line 172
def _bin_index(elem, low, high, dir, check_eq)
  sz   = high - low
  if (sz >> LIN_BITS).zero?
    # On 2012 cpus, linear search is slightly faster than binary search
    # if the number of searched elements is in the range of 50-100 elts
    cur_index = low
    while cur_index <= high
      cur = self[cur_index]
      cmp = yield cur
      if cmp == dir
        then cur_index += 1
        else return (if (check_eq && cmp.nonzero?) then -1 else cur_index end) end
    end
    return -1
  else
    # Classic binary search
    cmp_ = 0
    last = -1
    while low <= high
      mid_index = low + (sz >> 1)
      mid = self[mid_index]
      cmp = yield mid
      if cmp == dir
        low  = mid_index + 1
      else
        cmp_ = cmp
        last = mid_index
        high = mid_index - 1
      end
      sz -= 1
    end
    return (if (check_eq && cmp_.nonzero?) then -1 else last end)
  end
end