diff options
Diffstat (limited to 'mrbgems/mruby-array-ext')
| -rw-r--r-- | mrbgems/mruby-array-ext/mrblib/array.rb | 136 | ||||
| -rw-r--r-- | mrbgems/mruby-array-ext/test/array.rb | 50 |
2 files changed, 175 insertions, 11 deletions
diff --git a/mrbgems/mruby-array-ext/mrblib/array.rb b/mrbgems/mruby-array-ext/mrblib/array.rb index 49d0db0d5..67f7e51a7 100644 --- a/mrbgems/mruby-array-ext/mrblib/array.rb +++ b/mrbgems/mruby-array-ext/mrblib/array.rb @@ -313,7 +313,7 @@ class Array def fill(arg0=nil, arg1=nil, arg2=nil, &block) if arg0 == nil && arg1 == nil && arg2 == nil && !block - raise ArgumentError, "wrong number of arguments (0 for 1..3)" + raise ArgumentError, "wrong number of arguments (0 for 1..3)" end beg = len = 0 @@ -323,11 +323,13 @@ class Array # ary.fill { |index| block } -> ary beg = 0 len = self.size - elsif arg0 != nil && arg0.respond_to?(:begin) && arg0.respond_to?(:end) + elsif arg0 != nil && arg0.kind_of?(Range) # ary.fill(range) { |index| block } -> ary beg = arg0.begin beg += self.size if beg < 0 - len = arg0.end - beg + 1 + len = arg0.end + len += self.size if len < 0 + len += 1 unless arg0.exclude_end? elsif arg0 != nil # ary.fill(start [, length] ) { |index| block } -> ary beg = arg0 @@ -342,20 +344,22 @@ class Array if arg0 != nil && arg1 == nil && arg2 == nil # ary.fill(obj) -> ary beg = 0 - len = self.size - elsif arg0 != nil && arg1 != nil && arg1.respond_to?(:begin) && arg1.respond_to?(:end) - # ary.fill(obj, range ) -> ary len = self.size + elsif arg0 != nil && arg1 != nil && arg1.kind_of?(Range) + # ary.fill(obj, range ) -> ary beg = arg1.begin - len = arg1.end - beg + 1 + beg += self.size if beg < 0 + len = arg1.end + len += self.size if len < 0 + len += 1 unless arg1.exclude_end? elsif arg0 != nil && arg1 != nil # ary.fill(obj, start [, length]) -> ary beg = arg1 beg += self.size if beg < 0 - if arg2 == nil + if arg2 == nil len = self.size else - len = arg1 + arg2 + len = beg + arg2 end end end @@ -509,4 +513,118 @@ class Array self[idx, 0] = args self end + + ## + # call-seq: + # ary.bsearch {|x| block } -> elem + # + # By using binary search, finds a value from this array which meets + # the given condition in O(log n) where n is the size of the array. + # + # You can use this method in two use cases: a find-minimum mode and + # a find-any mode. In either case, the elements of the array must be + # monotone (or sorted) with respect to the block. + # + # In find-minimum mode (this is a good choice for typical use case), + # the block must return true or false, and there must be an index i + # (0 <= i <= ary.size) so that: + # + # - the block returns false for any element whose index is less than + # i, and + # - the block returns true for any element whose index is greater + # than or equal to i. + # + # This method returns the i-th element. If i is equal to ary.size, + # it returns nil. + # + # ary = [0, 4, 7, 10, 12] + # ary.bsearch {|x| x >= 4 } #=> 4 + # ary.bsearch {|x| x >= 6 } #=> 7 + # ary.bsearch {|x| x >= -1 } #=> 0 + # ary.bsearch {|x| x >= 100 } #=> nil + # + # In find-any mode (this behaves like libc's bsearch(3)), the block + # must return a number, and there must be two indices i and j + # (0 <= i <= j <= ary.size) so that: + # + # - the block returns a positive number for ary[k] if 0 <= k < i, + # - the block returns zero for ary[k] if i <= k < j, and + # - the block returns a negative number for ary[k] if + # j <= k < ary.size. + # + # Under this condition, this method returns any element whose index + # is within i...j. If i is equal to j (i.e., there is no element + # that satisfies the block), this method returns nil. + # + # ary = [0, 4, 7, 10, 12] + # # try to find v such that 4 <= v < 8 + # ary.bsearch {|x| 1 - (x / 4).truncate } #=> 4 or 7 + # # try to find v such that 8 <= v < 10 + # ary.bsearch {|x| 4 - (x / 2).truncate } #=> nil + # + # You must not mix the two modes at a time; the block must always + # return either true/false, or always return a number. It is + # undefined which value is actually picked up at each iteration. + + def bsearch(&block) + return to_enum :bsearch unless block_given? + + low = 0 + high = self.size + satisfied = false + while low < high + mid = low + ((high - low) / 2).truncate + val = self[mid] + v = block.call(val) + if v.is_a?(Integer) + return val if v == 0 + smaller = v < 0 + elsif v == true + satisfied = true + smaller = true + elsif v == false || v == nil + smaller = false + end + if smaller + high = mid + else + low = mid + 1 + end + end + return nil if low == self.size + return nil unless satisfied + self[low] + end + + ## + # call-seq: + # ary.delete_if { |item| block } -> ary + # ary.delete_if -> Enumerator + # + # Deletes every element of +self+ for which block evaluates to +true+. + # + # The array is changed instantly every time the block is called, not after + # the iteration is over. + # + # See also Array#reject! + # + # If no block is given, an Enumerator is returned instead. + # + # scores = [ 97, 42, 75 ] + # scores.delete_if {|score| score < 80 } #=> [97] + + def delete_if(&block) + return to_enum :delete_if unless block_given? + + idx = 0 + len = self.size + while idx < self.size do + if block.call(self[idx]) + self.delete_at(idx) + else + idx += 1 + end + end + self + end end diff --git a/mrbgems/mruby-array-ext/test/array.rb b/mrbgems/mruby-array-ext/test/array.rb index d15ea2a64..47ffa00cf 100644 --- a/mrbgems/mruby-array-ext/test/array.rb +++ b/mrbgems/mruby-array-ext/test/array.rb @@ -125,14 +125,31 @@ end assert("Array#fill") do a = [ "a", "b", "c", "d" ] assert_equal ["x", "x", "x", "x"], a.fill("x") - assert_equal ["x", "x", "x", "w"], a.fill("w", -1) + assert_equal ["x", "x", "x", "w"], a.fill("w", -1) assert_equal ["x", "x", "z", "z"], a.fill("z", 2, 2) assert_equal ["y", "y", "z", "z"], a.fill("y", 0..1) - assert_equal [0, 1, 4, 9], a.fill { |i| i*i } + assert_equal [0, 1, 4, 9], a.fill { |i| i*i } assert_equal [0, 1, 8, 27], a.fill(-2) { |i| i*i*i } assert_equal [0, 2, 3, 27], a.fill(1, 2) { |i| i+1 } assert_equal [1, 2, 3, 27], a.fill(0..1) { |i| i+1 } assert_raise(ArgumentError) { a.fill } + + assert_equal([0, 1, 2, 3, -1, 5], [0, 1, 2, 3, 4, 5].fill(-1, -2, 1)) + assert_equal([0, 1, 2, 3, -1, -1, -1], [0, 1, 2, 3, 4, 5].fill(-1, -2, 3)) + assert_equal([0, 1, 2, -1, -1, 5], [0, 1, 2, 3, 4, 5].fill(-1, 3..4)) + assert_equal([0, 1, 2, -1, 4, 5], [0, 1, 2, 3, 4, 5].fill(-1, 3...4)) + assert_equal([0, 1, -1, -1, -1, 5], [0, 1, 2, 3, 4, 5].fill(-1, 2..-2)) + assert_equal([0, 1, -1, -1, 4, 5], [0, 1, 2, 3, 4, 5].fill(-1, 2...-2)) + assert_equal([0, 1, 2, 13, 14, 5], [0, 1, 2, 3, 4, 5].fill(3..4){|i| i+10}) + assert_equal([0, 1, 2, 13, 4, 5], [0, 1, 2, 3, 4, 5].fill(3...4){|i| i+10}) + assert_equal([0, 1, 12, 13, 14, 5], [0, 1, 2, 3, 4, 5].fill(2..-2){|i| i+10}) + assert_equal([0, 1, 12, 13, 4, 5], [0, 1, 2, 3, 4, 5].fill(2...-2){|i| i+10}) + + assert_equal [1, 2, 3, 4, 'x', 'x'], [1, 2, 3, 4, 5, 6].fill('x', -2..-1) + assert_equal [1, 2, 3, 4, 'x', 6], [1, 2, 3, 4, 5, 6].fill('x', -2...-1) + assert_equal [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6].fill('x', -2...-2) + assert_equal [1, 2, 3, 4, 'x', 6], [1, 2, 3, 4, 5, 6].fill('x', -2..-2) + assert_equal [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6].fill('x', -2..0) end assert("Array#reverse_each") do @@ -206,3 +223,32 @@ assert("Array#insert") do b = ["a", "b", "c", "d"] assert_equal ["a", "b", "c", "d", nil, nil, 99], b.insert(6, 99) end + +assert("Array#bsearch") do + # Find minimum mode + a = [0, 4, 7, 10, 12] + assert_include [4, 7], a.bsearch {|x| x >= 4 } + assert_equal 7, a.bsearch {|x| x >= 6 } + assert_equal 0, a.bsearch {|x| x >= -1 } + assert_nil a.bsearch {|x| x >= 100 } + + # Find any mode + a = [0, 4, 7, 10, 12] + assert_include [4, 7], a.bsearch {|x| 1 - (x / 4).truncate } + assert_nil a.bsearch {|x| 4 - (x / 2).truncate } + assert_equal(nil, a.bsearch {|x| 1 }) + assert_equal(nil, a.bsearch {|x| -1 }) +end + +assert("Array#delete_if") do + a = [1, 2, 3, 4, 5] + assert_equal [1, 2, 3, 4, 5], a.delete_if { false } + assert_equal [1, 2, 3, 4, 5], a + + a = [1, 2, 3, 4, 5] + assert_equal [], a.delete_if { true } + assert_equal [], a + + a = [ 1, 2, 3, 4, 5 ] + assert_equal [1, 2, 3], a.delete_if { |val| val > 3 } +end |