summaryrefslogtreecommitdiff
path: root/range.c
diff options
context:
space:
mode:
authormame <mame@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2018-04-19 15:18:57 (GMT)
committermame <mame@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2018-04-19 15:18:57 (GMT)
commitd658a8d56802b9d20b666bbc08fa12b2050b2f93 (patch)
tree3b1e2dd33873e0333997c431af2402c22a014594 /range.c
parentdb1bdecb0d925b4668c0735158fce466333848f1 (diff)
range.c: Make Range#bsearch support endless ranges
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@63195 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'range.c')
-rw-r--r--range.c115
1 files changed, 69 insertions, 46 deletions
diff --git a/range.c b/range.c
index 864f6c0..7dedb32 100644
--- a/range.c
+++ b/range.c
@@ -18,7 +18,7 @@
#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)
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)
* (-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)
#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)
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(