Module: Functional::Search

Extended by:
Search
Included in:
Functional, Search
Defined in:
lib/functional/search.rb

Instance Method Summary collapse

Instance Method Details

#binary_search(data, key, opts = {}, &block) {|item| ... } ⇒ Array Also known as: bsearch, half_interval_search

Conduct a binary search against the sorted collection and return a pair of indexes indicating the result of the search. The indexes will be returned as a two-element array.

The default behavior is to search the entire collections. The options hash can be used to provide optional low and high indexes (:imin and :imax). If either :imin or :imax is out of range the natural collection boundary will be used.

When a block is given the block will be applied to both arguments. Using a block in this way allows computation against a specific field in a data set of hashes or objects.

When the key is found both returned indexes will be the index of the item. When the key is not found but the value is within the range of value in the data set the returned indexes will be immediately above and below where the key would reside. When the key is below the lowest value in the search range the result will be nil and the lowest index. When the key is higher than the highest value in the search range the result will be the highest index and nil.

Parameters:

  • data (Enumerable) —

    the data set to search

  • opts (Hash) (defaults to: {}) —

    search options

  • block (Block) —

    optional block for per-item processing

Options Hash (opts):

  • :imin (Integer) —

    minimum index to search

  • :imax (Integer) —

    maximum index to search

Yields:

  • iterates over each element in the data set

Yield Parameters:

  • item —

    each element in the data set

Returns:

  • (Array) —

    pair of indexes (see above) or nil when the collection is empty or nil



82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/functional/search.rb', line 82

def binary_search(data, key, opts={}, &block)

  imin, imax = check_search_options(data, key, opts, &block)
  return nil if imin.nil? && imax.nil?
  return [imin, imax] if imin == imax || imin.nil? || imax.nil?

  while (imax >= imin)
    imid = (imin + imax) / 2
    current = data[imid]
    current = yield(current) if block_given?
    if current < key
      imin = imid + 1
    elsif current > key
      imax = imid - 1
    else
      imin = imax = imid
      break
    end
  end

  return imax, imin
end

#linear_search(data, key, opts = {}, &block) {|item| ... } ⇒ Array

Conduct a linear search against an unsorted collection and return the index where the item was found. Returns nil if the item is not found.

The default behavior is to search the entire collections. The options hash can be used to provide optional low and high indexes (:imin and :imax). If either :imin or :imax is out of range the natural collection boundary will be used.

When a block is given the block will be applied to both arguments. Using a block in this way allows computation against a specific field in a data set of hashes or objects.

Parameters:

  • data (Enumerable) —

    the data set to search

  • opts (Hash) (defaults to: {}) —

    search options

  • block (Block) —

    optional block for per-item processing

Options Hash (opts):

  • :imin (Integer) —

    minimum index to search

  • :imax (Integer) —

    maximum index to search

Yields:

  • iterates over each element in the data set

Yield Parameters:

  • item —

    each element in the data set

Returns:

  • (Array) —

    the index where the item is found or nil when the collection is empty or nil



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/functional/search.rb', line 31

def linear_search(data, key, opts={}, &block)

  imin, imax = check_search_options(data, key, opts, &block)
  return nil if imin.nil? || imax.nil?
  return imin if imin == imax

  index = nil
  (imin..imax).each do |i|
    if (block_given? && yield(data[i]) == key) || data[i] == key
      index = i
      break
    end
  end

  return index
end