From de07850e47ac41149304c58e9ebdbed47af23a70 Mon Sep 17 00:00:00 2001 From: mame Date: Wed, 14 Nov 2012 15:53:50 +0000 Subject: * array.c (rb_ary_bsearch): add Array#bsearch for binary search. [ruby-core:36390] [Feature #4766] * test/ruby/test_array.rb: add a test for above. * range.c (range_bsearch): add Range#bsearch for binary search. [ruby-core:36390] [Feature #4766] * test/ruby/test_range.rb: add a test for above * NEWS: added the two new methods. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@37655 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- test/ruby/test_array.rb | 27 +++++++++++++++++ test/ruby/test_range.rb | 78 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 105 insertions(+) (limited to 'test') diff --git a/test/ruby/test_array.rb b/test/ruby/test_array.rb index 8d264d9230..6c447c2626 100644 --- a/test/ruby/test_array.rb +++ b/test/ruby/test_array.rb @@ -2240,4 +2240,31 @@ class TestArray < Test::Unit::TestCase a = [1,2,3] assert_raise(ArgumentError) { a.rotate!(1, 1) } end + + def test_bsearch_in_find_minimum_mode + a = [0, 4, 7, 10, 12] + assert_equal(4, a.bsearch {|x| x >= 4 }) + assert_equal(7, a.bsearch {|x| x >= 6 }) + assert_equal(0, a.bsearch {|x| x >= -1 }) + assert_equal(nil, a.bsearch {|x| x >= 100 }) + end + + def test_bsearch_in_find_any_mode + a = [0, 4, 7, 10, 12] + assert_include([4, 7], a.bsearch {|x| 1 - x / 4 }) + assert_equal(nil, a.bsearch {|x| 4 - x / 2 }) + assert_equal(nil, a.bsearch {|x| 1 }) + assert_equal(nil, a.bsearch {|x| -1 }) + + assert_include([4, 7], a.bsearch {|x| (1 - x / 4) * (2**100) }) + assert_equal(nil, a.bsearch {|x| 1 * (2**100) }) + assert_equal(nil, a.bsearch {|x| (-1) * (2**100) }) + + assert_include([4, 7], a.bsearch {|x| (2**100).coerce((1 - x / 4) * (2**100)).first }) + end + + def test_bsearch_undefined + a = [0, 4, 7, 10, 12] + assert_equal(nil, a.bsearch {|x| "foo" }) # undefined behavior + end end diff --git a/test/ruby/test_range.rb b/test/ruby/test_range.rb index 2827bc1396..0600f694f7 100644 --- a/test/ruby/test_range.rb +++ b/test/ruby/test_range.rb @@ -355,4 +355,82 @@ class TestRange < Test::Unit::TestCase assert_equal 5, (1.1...6).size assert_equal 42, (1..42).each.size 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?) + + v = (-inf..0).bsearch {|x| x > -Float::MAX } + assert_operator(-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 -- cgit v1.2.3