Ruby: Find index of next match in array, or find with offset

Question

I want to find further matches after Array#find_index { |item| block } matches for the first time. How can I search for the index of the second match, third match, and so on?

In other words, I want the equivalent of the pos argument to Regexp#match(str, pos) for Array#find_index. Then I can maintain a current-position index to continue the search.

I cannot use Enumerable#find_all because I might modify the array between calls (in which case, I will also adjust my current-position index to reflect the modifications). I do not want to copy part of the array, as that would increase the computational complexity of my algorithm. I want to do this without copying the array:

new_pos = pos + array[pos..-1].find_index do |elem|
    elem.matches_condition?
end

The following are different questions. They only ask the first match in the array, plus one:

• https://stackoverflow.com/questions/11300886/ruby-how-to-find-the-next-match-in-an-array
• https://stackoverflow.com/questions/4596517/ruby-find-next-in-array

The following question is closer, but still does not help me, because I need to process the first match before continuing to the next (and this way also conflicts with modification):

• https://stackoverflow.com/questions/9925654/ruby-find-in-array-with-offset

Answer 1

My approach is not much different from the others but perhaps packaged cleaner to be syntactically similar to Array#find_index . Here's the compact form.

def find_next_index(a,prior=nil)
    (((prior||-1)+1)...a.length).find{|i| yield a[i]}
end

Here's a simple test case.

test_arr = %w(aa ab ac ad)
puts find_next_index(test_arr){|v| v.include?('a')}
puts find_next_index(test_arr,1){|v| v.include?('a')}
puts find_next_index(test_arr,3){|v| v.include?('a')}

# evaluates to:
#     0
#     2
#     nil

And of course, with a slight rewrite you could monkey-patch it into the Array class

Answer 2

Here is one way this can be done. We can define a new method in Array class that will allow us to find indexes that match a given condition. The condition can be specified as block that returns boolean.

The new method returns an Enumerator so that we get the benefit of many of the Enumerator methods such next, to_a, etc.

ary = [1,2,3,4,5,6]

class Array
  def find_index_r(&block)
    Enumerator.new do |yielder| 
      self.each_with_index{|i, j| yielder.yield j if block.call(i)}
    end
  end
end

e = ary.find_index_r { |r| r % 2 == 0 }

p e.to_a  #=> [1, 3, 5]
p e.next  
#=> 1
p e.next  
#=> 3
ary[2]=10 
p ary
#=> [1, 2, 10, 4, 5, 6]
p e.next  
#=> 5
e.rewind
p e.next  
#=> 1
p e.next  
#=> 2

_{Note: I added a new method in Array class for demonstration purpose. Solution can be adapted easily to work without the monkey-patching}

Answer 3

Suppose

arr = [9,1,4,1,9,36,25]
findees = [1,6,3,6,3,7]
proc = ->(n) { n**2 }

and for each element n in findees we want the index of the first unmatched element m of arr for which proc[n] == m. For example, if n=3, then proc[3] #==> 9, so the first matching index in arr would be 0. For the next n=3 in findees, the first unmatched match in arr is at index 4.

We can do this like so:

arr = [9,1,4,1,9,36,25]
findees = [1,6,3,6,3,7]
proc = ->(n) { n**2 }

h = arr.each_with_index.with_object(Hash.new { |h,k| h[k] = [] }) { |(n,i),h| h[n] << i }
  #=> {9=>[0, 4], 1=>[1, 3], 4=>[2], 36=>[5], 25=>[6]}
findees.each_with_object([]) { |n,a| v=h[proc[n]]; a << v.shift if v }
  #=> [1, 5, 0, nil, 4, nil]

We can generalize this into a handy Array method as follow:

class Array
  def find_indices(*args)
    h = each_with_index.with_object(Hash.new {|h,k| h[k] = []}) { |(n,i),h| h[n] << i }
    args.each_with_object([]) { |n,a| v=h[yield n]; a << v.shift if v }
  end
end

arr.find_indices(*findees) { |n| n**2 }
  #=> [1, 5, 0, nil, 4, nil]

arr = [3,1,2,1,3,6,5]
findees = [1,6,3,6,3,7]
arr.find_indices(*findees, &:itself)
  #=> [1, 5, 0, nil, 4, nil]

Answer 4

A simpler way to do it is just:

new_pos = pos
while new_pos < array.size and not array[new_pos].matches_condition?
    new_pos += 1
end
new_pos = nil if new_pos == array.size

In fact, I think this is probably better than my other answer, because it's harder to get wrong, and there's no chance of future shadowing problems being introduced from the surrounding code. However, it's still clumsy.

And if the condition is more complex, then you end up needing to do something like this:

new_pos = pos
# this check is only necessary if pos may be == array.size
if new_pos < array.size
    prepare_for_condition
end
while new_pos < array.size and not array[new_pos].matches_condition?
    new_pos += 1
    if new_pos < array.size
        prepare_for_condition
    end
end
new_pos = nil if new_pos == array.size

Or, God forbid, a begin ... end while loop (although then you run into trouble with the initial value of new_pos):

new_pos = pos - 1
begin
    new_pos += 1
    if new_pos < array.size
        prepare_for_condition
    end
end while new_pos < array.size and not array[new_pos].matches_condition?
new_pos = nil if new_pos == array.size

This may seem horrible. However, supposing prepare_for_condition is something that keeps being tweaked in small ways. Those tweaks will eventually get refactored; however, by that time, the output of the refactored code will also end up getting tweaked in small ways that don't belong with the old refactored code, but do not yet seem to justify refactoring of their own - and so on. Occasionally, someone will forget to change both places. This may seem pathological; however, in programming, as we all know, the pathological case has a habit of occurring only too often.

Answer 5

Of course, one way to do it would be:

new_pos = pos + (pos...array.size).find_index do |index|
    elem = array[index]
    elem.matches_condition?
end

However, this is clumsy and easy to get wrong. For example, you may forget to add pos. Also, you have to make sure elem isn't shadowing something. Both of these can lead to hard-to-trace bugs.

I find it hard to believe that an index argument to Array#find_index and Array#index still hasn't made it into the language. However, I notice Regexp#match(str,pos) wasn't there until version 1.9, which is equally surprising.