Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: jruby/jruby
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: 2653de163e3e
Choose a base ref
...
head repository: jruby/jruby
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: ef6d89a3491e
Choose a head ref
  • 3 commits
  • 2 files changed
  • 2 contributors

Commits on Dec 12, 2015

  1. [ruby-2.3] Feature #10730: Implement Array#bsearch_index 

    Implements Array#bsearch_index. The binary search is now a private method which returns an int
index, and the public #bsearch and #bsearch_index methods utilize it to return an appropriate
IRubyObject instance.
    @cheald
    cheald committed Dec 12, 2015
    Copy the full SHA
    f6aa701 View commit details

  2. [skip ci] minor style fix

    @cheald
    cheald committed Dec 12, 2015
    Copy the full SHA
    5bbbce3 View commit details

  3. Merge pull request #3532 from cheald/array_bsearch_index 

    [ruby-2.3] Feature #10730: Implement Array#bsearch_index
    @kares
    kares committed Dec 12, 2015
    Copy the full SHA
    ef6d89a View commit details
Showing with 66 additions and 10 deletions.
  1. +31 −10 core/src/main/java/org/jruby/RubyArray.java
  2. +35 −0 test/mri/ruby/test_array.rb
41 changes: 31 additions & 10 deletions core/src/main/java/org/jruby/RubyArray.java
View file
Original file line number Diff line number Diff line change
@@ -2111,24 +2111,45 @@ public IRubyObject index(ThreadContext context, Block block) {

@JRubyMethod
public IRubyObject bsearch(ThreadContext context, Block block) {
Ruby runtime = context.runtime;

if (!block.isGiven()) {
return enumeratorize(context.runtime, this, "bsearch");
}

int rVal = bsearch_index_internal(context, block);
if (rVal == -1) {
return context.nil;
} else {
return eltOk(rVal);
}
}

@JRubyMethod
public IRubyObject bsearch_index(ThreadContext context, Block block) {
if (!block.isGiven()) {
return enumeratorize(context.runtime, this, "bsearch_index");
}
int rVal = bsearch_index_internal(context, block);
if (rVal == -1) {
return context.nil;
} else {
return RubyFixnum.newFixnum(context.runtime, rVal);
}
}

private int bsearch_index_internal(ThreadContext context, Block block) {
Ruby runtime = context.runtime;

int low = 0, high = realLength, mid;
boolean smaller = false, satisfied = false;
IRubyObject v, val;
IRubyObject v;

while (low < high) {
mid = low + ((high - low) / 2);
val = eltOk(mid);
v = block.yieldSpecific(context, val);
v = block.yieldSpecific(context, eltOk(mid));

if (v instanceof RubyFixnum) {
long fixValue = ((RubyFixnum)v).getLongValue();
if (fixValue == 0) return val;
if (fixValue == 0) return mid;
smaller = fixValue < 0;
} else if (v == runtime.getTrue()) {
satisfied = true;
@@ -2137,7 +2158,7 @@ public IRubyObject bsearch(ThreadContext context, Block block) {
smaller = false;
} else if (runtime.getNumeric().isInstance(v)) {
switch (RubyComparable.cmpint(context, invokedynamic(context, v, OP_CMP, RubyFixnum.zero(runtime)), v, RubyFixnum.zero(runtime))) {
case 0: return val;
case 0: return mid;
case 1: smaller = true; break;
case -1: smaller = false;
}
@@ -2150,9 +2171,9 @@ public IRubyObject bsearch(ThreadContext context, Block block) {
low = mid + 1;
}
}
if (low == realLength) return context.nil;
if (!satisfied) return context.nil;
return eltOk(low);
if (low == realLength) return -1;
if (!satisfied) return -1;
return low;
}

/** rb_ary_rindex
35 changes: 35 additions & 0 deletions test/mri/ruby/test_array.rb
View file
Original file line number Diff line number Diff line change
@@ -2473,6 +2473,41 @@ def test_bsearch_in_find_any_mode
assert_include([4, 7], a.bsearch {|x| (2**100).coerce((1 - x / 4) * (2**100)).first })
end

def test_bsearch_index_typechecks_return_values
assert_raise(TypeError) do
[1, 2, 42, 100, 666].bsearch_index {"not ok"}
end
assert_equal [1, 2, 42, 100, 666].bsearch_index {}, [1, 2, 42, 100, 666].bsearch_index {false}
end

def test_bsearch_index_with_no_block
enum = [1, 2, 42, 100, 666].bsearch_index
assert_nil enum.size
assert_equal 2, enum.each{|x| x >= 33 }
end

def test_bsearch_index_in_find_minimum_mode
a = [0, 4, 7, 10, 12]
assert_equal(1, a.bsearch_index {|x| x >= 4 })
assert_equal(2, a.bsearch_index {|x| x >= 6 })
assert_equal(0, a.bsearch_index {|x| x >= -1 })
assert_equal(nil, a.bsearch_index {|x| x >= 100 })
end

def test_bsearch_index_in_find_any_mode
a = [0, 4, 7, 10, 12]
assert_include([1, 2], a.bsearch_index {|x| 1 - x / 4 })
assert_equal(nil, a.bsearch_index {|x| 4 - x / 2 })
assert_equal(nil, a.bsearch_index {|x| 1 })
assert_equal(nil, a.bsearch_index {|x| -1 })

assert_include([1, 2], a.bsearch_index {|x| (1 - x / 4) * (2**100) })
assert_equal(nil, a.bsearch_index {|x| 1 * (2**100) })
assert_equal(nil, a.bsearch_index {|x| (-1) * (2**100) })

assert_include([1, 2], a.bsearch_index {|x| (2**100).coerce((1 - x / 4) * (2**100)).first })
end

def test_shared_marking
reduce = proc do |s|
s.gsub(/(verify_internal_consistency_reachable_i:\sWB\smiss\s\S+\s\(T_ARRAY\)\s->\s)\S+\s\((proc|T_NONE)\)\n