ruby-changes:50989
From: mame <ko1@a...>
Date: Fri, 20 Apr 2018 00:28:32 +0900 (JST)
Subject: [ruby-changes:50989] mame:r63195 (trunk): range.c: Make Range#bsearch support endless ranges
mame 2018-04-20 00:18:57 +0900 (Fri, 20 Apr 2018) New Revision: 63195 https://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=63195 Log: range.c: Make Range#bsearch support endless ranges Modified files: trunk/range.c trunk/test/ruby/test_range.rb Index: range.c =================================================================== --- range.c (revision 63194) +++ range.c (revision 63195) @@ -18,7 +18,7 @@ https://github.com/ruby/ruby/blob/trunk/range.c#L18 #include <math.h> VALUE rb_cRange; -static ID id_beg, id_end, id_excl, id_integer_p, id_div; +static ID id_beg, id_end, id_excl, id_integer_p, id_add, id_mul, id_div; #define id_cmp idCmp #define id_succ idSucc @@ -526,6 +526,62 @@ is_integer_p(VALUE v) https://github.com/ruby/ruby/blob/trunk/range.c#L526 return RTEST(is_int) && is_int != Qundef; } +static VALUE +bsearch_integer_range(VALUE beg, VALUE end, int excl) +{ + VALUE satisfied = Qnil; + int smaller; + +#define BSEARCH_CHECK(expr) \ + do { \ + VALUE val = (expr); \ + VALUE v = rb_yield(val); \ + if (FIXNUM_P(v)) { \ + if (v == INT2FIX(0)) return val; \ + smaller = (SIGNED_VALUE)v < 0; \ + } \ + else if (v == Qtrue) { \ + satisfied = val; \ + smaller = 1; \ + } \ + else if (v == Qfalse || v == Qnil) { \ + smaller = 0; \ + } \ + else if (rb_obj_is_kind_of(v, rb_cNumeric)) { \ + int cmp = rb_cmpint(rb_funcall(v, id_cmp, 1, INT2FIX(0)), v, INT2FIX(0)); \ + if (!cmp) return val; \ + smaller = cmp < 0; \ + } \ + else { \ + rb_raise(rb_eTypeError, "wrong argument type %"PRIsVALUE \ + " (must be numeric, true, false or nil)", \ + rb_obj_class(v)); \ + } \ + } while (0) + + VALUE low = rb_to_int(beg); + VALUE high = rb_to_int(end); + VALUE mid, org_high; + if (excl) high = rb_funcall(high, '-', 1, INT2FIX(1)); + org_high = high; + + while (rb_cmpint(rb_funcall(low, id_cmp, 1, high), low, high) < 0) { + mid = rb_funcall(rb_funcall(high, '+', 1, low), id_div, 1, INT2FIX(2)); + BSEARCH_CHECK(mid); + if (smaller) { + high = mid; + } + else { + low = rb_funcall(mid, '+', 1, INT2FIX(1)); + } + } + if (rb_equal(low, org_high)) { + BSEARCH_CHECK(low); + if (!smaller) return Qnil; + } + return satisfied; +} + /* * call-seq: * rng.bsearch {|obj| block } -> value @@ -598,33 +654,6 @@ range_bsearch(VALUE range) https://github.com/ruby/ruby/blob/trunk/range.c#L654 * (-1...0.0).bsearch to yield -0.0. */ -#define BSEARCH_CHECK(expr) \ - do { \ - VALUE val = (expr); \ - VALUE v = rb_yield(val); \ - if (FIXNUM_P(v)) { \ - if (v == INT2FIX(0)) return val; \ - smaller = (SIGNED_VALUE)v < 0; \ - } \ - else if (v == Qtrue) { \ - satisfied = val; \ - smaller = 1; \ - } \ - else if (v == Qfalse || v == Qnil) { \ - smaller = 0; \ - } \ - else if (rb_obj_is_kind_of(v, rb_cNumeric)) { \ - int cmp = rb_cmpint(rb_funcall(v, id_cmp, 1, INT2FIX(0)), v, INT2FIX(0)); \ - if (!cmp) return val; \ - smaller = cmp < 0; \ - } \ - else { \ - rb_raise(rb_eTypeError, "wrong argument type %"PRIsVALUE \ - " (must be numeric, true, false or nil)", \ - rb_obj_class(v)); \ - } \ - } while (0) - #define BSEARCH(conv) \ do { \ RETURN_ENUMERATOR(range, 0, 0); \ @@ -661,34 +690,26 @@ range_bsearch(VALUE range) https://github.com/ruby/ruby/blob/trunk/range.c#L690 #if SIZEOF_DOUBLE == 8 && defined(HAVE_INT64_T) else if (RB_TYPE_P(beg, T_FLOAT) || RB_TYPE_P(end, T_FLOAT)) { int64_t low = double_as_int64(RFLOAT_VALUE(rb_Float(beg))); - int64_t high = double_as_int64(RFLOAT_VALUE(rb_Float(end))); + int64_t high = double_as_int64(NIL_P(end) ? HUGE_VAL : RFLOAT_VALUE(rb_Float(end))); int64_t mid, org_high; BSEARCH(int64_as_double_to_num); } #endif else if (is_integer_p(beg) && is_integer_p(end)) { - VALUE low = rb_to_int(beg); - VALUE high = rb_to_int(end); - VALUE mid, org_high; RETURN_ENUMERATOR(range, 0, 0); - if (EXCL(range)) high = rb_funcall(high, '-', 1, INT2FIX(1)); - org_high = high; - - while (rb_cmpint(rb_funcall(low, id_cmp, 1, high), low, high) < 0) { - mid = rb_funcall(rb_funcall(high, '+', 1, low), id_div, 1, INT2FIX(2)); + return bsearch_integer_range(beg, end, EXCL(range)); + } + else if (is_integer_p(beg) && NIL_P(end)) { + VALUE diff = LONG2FIX(1); + RETURN_ENUMERATOR(range, 0, 0); + while (1) { + VALUE mid = rb_funcall(beg, id_add, 1, diff); BSEARCH_CHECK(mid); if (smaller) { - high = mid; - } - else { - low = rb_funcall(mid, '+', 1, INT2FIX(1)); + return bsearch_integer_range(beg, mid, 0); } + diff = rb_funcall(diff, id_mul, 1, LONG2FIX(2)); } - if (rb_equal(low, org_high)) { - BSEARCH_CHECK(low); - if (!smaller) return Qnil; - } - return satisfied; } else { rb_raise(rb_eTypeError, "can't do binary search for %s", rb_obj_classname(beg)); @@ -1363,6 +1384,8 @@ Init_Range(void) https://github.com/ruby/ruby/blob/trunk/range.c#L1384 id_end = rb_intern("end"); id_excl = rb_intern("excl"); id_integer_p = rb_intern("integer?"); + id_add = rb_intern("+"); + id_mul = rb_intern("*"); id_div = rb_intern("div"); rb_cRange = rb_struct_define_without_accessor( Index: test/ruby/test_range.rb =================================================================== --- test/ruby/test_range.rb (revision 63194) +++ test/ruby/test_range.rb (revision 63195) @@ -581,6 +581,8 @@ class TestRange < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_range.rb#L581 ary = [0, 100, 100, 100, 200] assert_equal(1, (0...ary.size).bsearch {|i| ary[i] >= 100 }) + + assert_equal(1_000_001, (0...).bsearch {|i| i > 1_000_000 }) end def test_bsearch_for_float @@ -632,6 +634,8 @@ class TestRange < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_range.rb#L634 assert_in_delta(1.0, (0.0..inf).bsearch {|x| Math.log(x) >= 0 }) assert_in_delta(7.0, (0.0..10).bsearch {|x| 7.0 - x }) + + assert_equal(1_000_000.0.next_float, (0.0..).bsearch {|x| x > 1_000_000 }) end def check_bsearch_values(range, search, a) @@ -733,6 +737,7 @@ class TestRange < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_range.rb#L737 assert_equal(nil, (bignum...bignum+ary.size).bsearch {|i| ary[i - bignum] >= 100 }) assert_equal(bignum + 0, (bignum...bignum+ary.size).bsearch {|i| true }) assert_equal(nil, (bignum...bignum+ary.size).bsearch {|i| false }) + assert_equal(bignum * 2 + 1, (bignum...).bsearch {|i| i > bignum * 2 }) assert_raise(TypeError) { ("a".."z").bsearch {} } end -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/