Skip to content

Commit

Permalink
Showing 2 changed files with 43 additions and 14 deletions.
14 changes: 0 additions & 14 deletions spec/truffle/tags/core/array/bsearch_index_tags.txt

This file was deleted.

43 changes: 43 additions & 0 deletions truffle/src/main/ruby/core/array.rb
Original file line number Diff line number Diff line change
@@ -196,6 +196,49 @@ def bsearch
nil
end

def bsearch_index
return to_enum :bsearch_index unless block_given?

m = Rubinius::Mirror::Array.reflect self

tuple = m.tuple

min = start = m.start
max = total = start + m.total

last_true = nil
i = start + m.total / 2

while max >= min and i >= start and i < total
x = yield tuple.at(i)

return i if x == 0

case x
when Numeric
if x > 0
min = i + 1
else
max = i - 1
end
when true
last_true = i
max = i - 1
when false, nil
min = i + 1
else
raise TypeError, "wrong argument type (must be numeric, true, false or nil)"
end

i = min + (max - min) / 2
end

return i if max > min
return last_true if last_true

nil
end

This comment has been minimized.

Copy link
@eregon

eregon Jun 27, 2016

Member

Can we make bsearch use it so the code is not duplicated?

This comment has been minimized.

Copy link
@bjfish

bjfish Jun 27, 2016

Author Contributor

@eregon Yes, I was thinking that too. I'll add this to my TODO list.

I tried once:

  def bsearch(&block)
    return to_enum :bsearch unless block_given?

    idx = self.bsearch_index(&block)

    return nil if idx.nil?

    m = Rubinius::Mirror::Array.reflect self
    m.tuple.at(idx)
  end

This would result in calling reflect twice so I think I should refactor these to call a shared private method that finds the index on the tuple.

This comment has been minimized.

Copy link
@eregon

eregon Jun 28, 2016

Member

@bjfish Calling reflect should be fast (or we should make it if it's not), so don't worry too much about calling it twice.
But here, there is a simpler solution. Our Array does not have a tuple, @tuple only returns self (start is 0 and total is size). So we can just use self.at(i) for indexing :)

This comment has been minimized.

Copy link
@bjfish

bjfish Jun 28, 2016

Author Contributor

@eregon I've refactor bsearch here 8ea2dae , thanks!


def combination(num)
num = Rubinius::Type.coerce_to_collection_index num

0 comments on commit a000060

Please sign in to comment.