Module: BinSearch::Methods

Included in:
Array
Defined in:
lib/bin_search/bin_search.rb

Instance Method Summary collapse

Instance Method Details

#bin_assoc(elem, mode, low = 0, high = -1)) ⇒ Array

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

Parameters:

  • elem (Object) —

    elem to search for

  • low (Fixnum) (defaults to: 0) —

    lower bound (inclusive)

  • high (Fixnum) (defaults to: -1)) —

    upper bound (inclusive, nil for last element)

  • mode (:asc, :desc, :asc_eq, :desc_eq) —

    matching mode

Returns:

  • (Array) —
    index, first matching elem

    in self, or nil if not found



136
137
138
139
140
141
142
143
 
# 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)) ⇒ Array

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

Parameters:

  • elem (Object) —

    elem to search for

  • low (Fixnum) (defaults to: 0) —

    lower bound (inclusive)

  • high (Fixnum) (defaults to: -1)) —

    upper bound (inclusive, nil for last element)

  • mode (:asc, :desc, :asc_eq, :desc_eq) —

    matching mode

Returns:

  • (Array) —
    index, first matching elem

    in self, or nil if not found



162
163
164
165
166
167
168
 
# 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)) ⇒ Fixnum

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

Parameters:

  • elem (Object) —

    elem to search for

  • low (Fixnum) (defaults to: 0) —

    lower bound (inclusive)

  • high (Fixnum) (defaults to: -1)) —

    upper bound (inclusive, -1 for last element)

  • mode (:asc, :desc, :asc_eq, :desc_eq) —

    matching mode

Returns:

  • (Fixnum) —

    index of first matching elem in self, or -1 if not found



32
33
34
35
36
37
38
39
 
# 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)) ⇒ Fixnum

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

Parameters:

  • elem (Object) —

    elem to search for

  • low (Fixnum) (defaults to: 0) —

    lower bound (inclusive)

  • high (Fixnum) (defaults to: -1)) —

    upper bound (inclusive, -1 for last element)

  • mode (:asc, :desc, :asc_eq, :desc_eq) —

    matching mode

Returns:

  • (Fixnum) —

    index of first matching elem in self, or -1 if not found



58
59
60
61
62
63
64
 
# 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(elem, mode, low = 0, high = -1)) ⇒ Object

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

Parameters:

  • elem (Object) —

    elem to search for

  • low (Fixnum) (defaults to: 0) —

    lower bound (inclusive)

  • high (Fixnum) (defaults to: -1)) —

    upper bound (inclusive, nil for last element)

  • mode (:asc, :desc, :asc_eq, :desc_eq) —

    matching mode

Returns:

  • (Object) —

    first matching elem in self, or nil if not found



84
85
86
87
88
89
90
91
 
# File 'lib/bin_search/bin_search.rb', line 84

def bin_search(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_search(elem, low, high, dir, check_eq) { |b| yield elem, b }
    else _bin_search(elem, low, high, dir, check_eq) { |b| elem <=> b } end
end

#bin_search_by(elem, mode, low = 0, high = -1)) ⇒ Object

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

Parameters:

  • elem (Object) —

    elem to search for

  • low (Fixnum) (defaults to: 0) —

    lower bound (inclusive)

  • high (Fixnum) (defaults to: -1)) —

    upper bound (inclusive, nil for last element)

  • mode (:asc, :desc, :asc_eq, :desc_eq) —

    matching mode

Returns:

  • (Object) —

    first matching elem in self, or nil if not found



110
111
112
113
114
115
116
 
# 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