Project

General

Profile

Download (12.9 KB)

Feature #4766 ยป bsearch.patch

mame (Yusuke Endoh), 07/20/2011 11:21 AM

View differences:

array.c
return ary;
}
/*
* call-seq:
* ary.bsearch {|x| block } -> elem
*/
static VALUE
rb_ary_bsearch(VALUE ary)
{
long low = 0, high = RARRAY_LEN(ary), mid;
int smaller, satisfied = 0;
VALUE v, val;
while (low < high) {
mid = low + ((high - low) / 2);
val = rb_ary_entry(ary, mid);
v = rb_yield(val);
if (FIXNUM_P(v)) {
if (FIX2INT(v) == 0) return val;
smaller = FIX2INT(v) < 0;
}
else if (v == Qtrue) {
satisfied = 1;
smaller = 1;
}
else if (v == Qfalse || v == Qnil) {
smaller = 0;
}
else if (rb_obj_is_kind_of(v, rb_cNumeric)) {
switch (rb_cmpint(rb_funcall(v, id_cmp, 1, INT2FIX(0)), v, INT2FIX(0)) < 0) {
case 0: return val;
case 1: smaller = 1;
case -1: smaller = 0;
}
}
else {
smaller = RTEST(v);
}
if (smaller) {
high = mid;
}
else {
low = mid + 1;
}
}
if (low == RARRAY_LEN(ary)) return Qnil;
if (!satisfied) return Qnil;
return rb_ary_entry(ary, low);
}
static VALUE
sort_by_i(VALUE i)
......
rb_define_method(rb_cArray, "take_while", rb_ary_take_while, 0);
rb_define_method(rb_cArray, "drop", rb_ary_drop, 1);
rb_define_method(rb_cArray, "drop_while", rb_ary_drop_while, 0);
rb_define_method(rb_cArray, "bsearch", rb_ary_bsearch, 0);
id_cmp = rb_intern("<=>");
sym_random = ID2SYM(rb_intern("random"));
range.c
#include "ruby/encoding.h"
#include "internal.h"
#ifdef HAVE_FLOAT_H
#include <float.h>
#endif
#include <math.h>
VALUE rb_cRange;
static ID id_cmp, id_succ, id_beg, id_end, id_excl;
......
return range;
}
/*
* call-seq:
* rng.bsearch {|obj| block } -> element
*
* Finds a value in range which meets the given condition in O(n log n)
* where n = (rng.begin - rng.end), by using binary search.
*
* The given block receives a current value, determines if it meets the
* condition and controls search.
* When the condition is satisfied and you want to stop search, the block
* should return zero, and then this method return the value immediately.
* When the condition is satisfied and you want to find minimum bound,
* the block should return true. When the condition is not satisfied and
* the current value is smaller than wanted, the block should return false,
* nil or an integer greater than zero. When the condition is not satisfied
* and the current value is larger than wanted, the block should return an
* integer less than zero.
* Unless the block returns zero, the search will continue until a minimum
* bound is found or no match is found. Returns the minimum bound if any,
* or returns nil when no match is found.
*
* The block must be monotone; there must be two values a and b so that
* the block returns:
* - false, nil or an integer greater than zero for all x of [begin of
* range, a), and
* - zero or true for all x of [a, b), and
* - an integer less than zero for all x of [b, end of range).
* If the block is not monotone, the result is unspecified.
*
* This method takes O(n log n), but it is unspecified which value is
* actually picked up at each iteration.
*
* ary = [0, 4, 7, 10, 12]
* (0...ary.size).bsearch {|i| ary[i] >= 4 } #=> 1
* (0...ary.size).bsearch {|i| ary[i] >= 6 } #=> 2
* (0...ary.size).bsearch {|i| ary[i] >= 8 } #=> 3
* (0...ary.size).bsearch {|i| ary[i] >= 100 } #=> nil
*
* (0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } #=> 1.0
*
* ary = [0, 100, 100, 100, 200]
* (0..4).bsearch {|i| 100 - i } #=> 1, 2 or 3
* (0..4).bsearch {|i| 300 - i } #=> nil
* (0..4).bsearch {|i| 50 - i } #=> nil
*/
static VALUE
range_bsearch(VALUE range)
{
VALUE beg, end;
int smaller, satisfied = 0;
#define BSEARCH_CHECK(val) \
do { \
VALUE v = rb_yield(val); \
if (FIXNUM_P(v)) { \
if (FIX2INT(v) == 0) return val; \
smaller = FIX2INT(v) < 0; \
} \
else if (v == Qtrue) { \
satisfied = 1; \
smaller = 1; \
} \
else if (v == Qfalse || v == Qnil) { \
smaller = 0; \
} \
else if (rb_obj_is_kind_of(v, rb_cNumeric)) { \
switch (rb_cmpint(rb_funcall(v, id_cmp, 1, INT2FIX(0)), v, INT2FIX(0)) < 0) { \
case 0: return val; \
case 1: smaller = 1; \
case -1: smaller = 0; \
} \
} \
else { \
smaller = RTEST(v); \
} \
} while (0)
beg = RANGE_BEG(range);
end = RANGE_END(range);
if (FIXNUM_P(beg) && FIXNUM_P(end)) {
long low = FIX2LONG(beg);
long high = FIX2LONG(end);
long mid, org_high;
if (EXCL(range)) high--;
org_high = high;
while (low < high) {
mid = low + ((high - low) / 2);
BSEARCH_CHECK(INT2FIX(mid));
if (smaller) {
high = mid;
}
else {
low = mid + 1;
}
}
if (low == org_high) {
BSEARCH_CHECK(INT2FIX(low));
if (!smaller) return Qnil;
}
if (!satisfied) return Qnil;
return INT2FIX(low);
}
else if (TYPE(beg) == T_FLOAT || TYPE(end) == T_FLOAT) {
double low = RFLOAT_VALUE(rb_Float(beg));
double high = RFLOAT_VALUE(rb_Float(end));
double mid, org_high, last_found_key = 0.0;
int count, found = 0;
#ifdef FLT_RADIX
#ifdef DBL_MANT_DIG
#define COUNT (((FLT_RADIX) - 1) * (DBL_MANT_DIG + DBL_MAX_EXP) + 100)
#else
#define count (53 + 1023 + 100)
#endif
#else
#define count (53 + 1023 + 100)
#endif
if (isinf(high) && high > 0) {
double nhigh = 1.0, inc;
if (nhigh < low) nhigh = low;
count = COUNT;
while (count >= 0 && !isinf(nhigh)) {
BSEARCH_CHECK(DBL2NUM(nhigh));
if (smaller) break;
high = nhigh;
nhigh *= 2;
count--;
}
if (isinf(nhigh) || count < 0) {
inc = high / 2;
count = COUNT;
while (count >= 0 && inc > 0) {
nhigh = high + inc;
if (!isinf(nhigh)) {
BSEARCH_CHECK(DBL2NUM(nhigh));
if (smaller) {
low = high;
high = nhigh;
goto binsearch;
}
else {
high = nhigh;
}
}
inc /= 2;
count--;
}
high *= 2; /* generate infinity */
if (isinf(high) && !EXCL(range)) {
BSEARCH_CHECK(DBL2NUM(high));
if (!satisfied) return Qnil;
if (smaller) return DBL2NUM(high);
}
return Qnil;
}
high = nhigh;
}
if (isinf(low) && low < 0) {
double nlow = -1.0, dec;
if (nlow > high) nlow = high;
count = COUNT;
while (count >= 0 && !isinf(nlow)) {
BSEARCH_CHECK(DBL2NUM(nlow));
if (!smaller) break;
low = nlow;
nlow *= 2;
count--;
}
if (isinf(nlow) || count < 0) {
dec = low / 2;
count = COUNT;
while (count >= 0 && dec < 0) {
nlow = low + dec;
if (!isinf(nlow)) {
BSEARCH_CHECK(DBL2NUM(nlow));
if (!smaller) {
high = low;
low = nlow;
goto binsearch;
}
else {
low = nlow;
}
}
dec /= 2;
count--;
}
nlow = low * 2; /* generate infinity */
if (isinf(nlow)) {
BSEARCH_CHECK(DBL2NUM(nlow));
if (!satisfied) return Qnil;
if (smaller) return DBL2NUM(nlow);
}
if (!satisfied) return Qnil;
return DBL2NUM(low);
}
low = nlow;
}
binsearch:
org_high = high;
count = COUNT;
while (low < high && count >= 0) {
mid = low + ((high - low) / 2);
BSEARCH_CHECK(DBL2NUM(mid));
if (smaller) {
found = 1;
last_found_key = high;
high = mid;
}
else {
low = mid;
}
count--;
}
BSEARCH_CHECK(DBL2NUM(low));
if (!smaller) {
BSEARCH_CHECK(DBL2NUM(high));
if (!smaller) {
if (found) {
low = last_found_key;
}
else {
return Qnil;
}
}
low = high;
}
if (!satisfied) return Qnil;
if (EXCL(range) && low >= org_high) return Qnil;
return DBL2NUM(low);
#undef COUNT
}
else if (!NIL_P(rb_check_to_integer(beg, "to_int")) &&
!NIL_P(rb_check_to_integer(end, "to_int"))) {
VALUE low = beg;
VALUE high = end;
VALUE mid, org_high;
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), '/', 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;
}
if (!satisfied) return Qnil;
return low;
}
else {
rb_raise(rb_eTypeError, "can't do binary search for %s", rb_obj_classname(beg));
}
return range;
}
static VALUE
each_i(VALUE v, void *arg)
{
......
rb_define_method(rb_cRange, "hash", range_hash, 0);
rb_define_method(rb_cRange, "each", range_each, 0);
rb_define_method(rb_cRange, "step", range_step, -1);
rb_define_method(rb_cRange, "bsearch", range_bsearch, 0);
rb_define_method(rb_cRange, "begin", range_begin, 0);
rb_define_method(rb_cRange, "end", range_end, 0);
rb_define_method(rb_cRange, "first", range_first, -1);
test/ruby/test_range.rb
assert !x.eql?(z)
}
end
def test_bsearch_for_fixnum
ary = [3, 4, 7, 9, 12]
assert_equal(0, (0...ary.size).bsearch {|i| ary[i] >= 2 })
assert_equal(1, (0...ary.size).bsearch {|i| ary[i] >= 4 })
assert_equal(2, (0...ary.size).bsearch {|i| ary[i] >= 6 })
assert_equal(3, (0...ary.size).bsearch {|i| ary[i] >= 8 })
assert_equal(4, (0...ary.size).bsearch {|i| ary[i] >= 10 })
assert_equal(nil, (0...ary.size).bsearch {|i| ary[i] >= 100 })
assert_equal(0, (0...ary.size).bsearch {|i| true })
assert_equal(nil, (0...ary.size).bsearch {|i| false })
ary = [0, 100, 100, 100, 200]
assert_equal(1, (0...ary.size).bsearch {|i| ary[i] >= 100 })
end
def test_bsearch_for_float
inf = Float::INFINITY
assert_in_delta(10.0, (0.0...100.0).bsearch {|x| x > 0 && Math.log(x / 10) >= 0 }, 0.0001)
assert_in_delta(10.0, (0.0...inf).bsearch {|x| x > 0 && Math.log(x / 10) >= 0 }, 0.0001)
assert_in_delta(-10.0, (-inf..100.0).bsearch {|x| x >= 0 || Math.log(-x / 10) < 0 }, 0.0001)
assert_in_delta(10.0, (-inf..inf).bsearch {|x| x > 0 && Math.log(x / 10) >= 0 }, 0.0001)
assert_equal(nil, (-inf..5).bsearch {|x| x > 0 && Math.log(x / 10) >= 0 }, 0.0001)
assert_in_delta(10.0, (-inf.. 10).bsearch {|x| x > 0 && Math.log(x / 10) >= 0 }, 0.0001)
assert_equal(nil, (-inf...10).bsearch {|x| x > 0 && Math.log(x / 10) >= 0 }, 0.0001)
assert_equal(nil, (-inf..inf).bsearch { false })
assert_equal(-inf, (-inf..inf).bsearch { true })
assert_equal(inf, (0..inf).bsearch {|x| x == inf })
assert_equal(nil, (0...inf).bsearch {|x| x == inf })
v = (-inf..0).bsearch {|x| x != -inf }
assert_operator(-Float::MAX, :>=, v)
assert_operator(-inf, :<, v)
v = (0.0..1.0).bsearch {|x| x > 0 } # the nearest positive value to 0.0
assert_in_delta(0, v, 0.0001)
assert_operator(0, :<, v)
assert_equal(0.0, (-1.0..0.0).bsearch {|x| x >= 0 })
assert_equal(nil, (-1.0...0.0).bsearch {|x| x >= 0 })
v = (0..Float::MAX).bsearch {|x| x >= Float::MAX }
assert_in_delta(Float::MAX, v)
assert_equal(nil, v.infinite?)
v = (0..inf).bsearch {|x| x >= Float::MAX }
assert_in_delta(Float::MAX, v)
assert_equal(nil, v.infinite?)
v = (-Float::MAX..0).bsearch {|x| x > -Float::MAX }
assert_operator(-Float::MAX, :<, v)
assert_equal(nil, v.infinite?)
v = (-inf..0).bsearch {|x| x >= -Float::MAX }
assert_in_delta(-Float::MAX, v)
assert_equal(nil, v.infinite?)
end
def test_bsearch_for_bignum
bignum = 2**100
ary = [3, 4, 7, 9, 12]
assert_equal(bignum + 0, (bignum...bignum+ary.size).bsearch {|i| ary[i - bignum] >= 2 })
assert_equal(bignum + 1, (bignum...bignum+ary.size).bsearch {|i| ary[i - bignum] >= 4 })
assert_equal(bignum + 2, (bignum...bignum+ary.size).bsearch {|i| ary[i - bignum] >= 6 })
assert_equal(bignum + 3, (bignum...bignum+ary.size).bsearch {|i| ary[i - bignum] >= 8 })
assert_equal(bignum + 4, (bignum...bignum+ary.size).bsearch {|i| ary[i - bignum] >= 10 })
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_raise(TypeError) { ("a".."z").bsearch {} }
end
end
    (1-1/1)