diff options
Diffstat (limited to 'enum.c')
| -rw-r--r-- | enum.c | 758 |
1 files changed, 548 insertions, 210 deletions
@@ -127,7 +127,7 @@ static VALUE enum_grep0(VALUE obj, VALUE pat, VALUE test) { VALUE ary = rb_ary_new(); - struct MEMO *memo = MEMO_NEW(pat, ary, test); + struct MEMO *memo = rb_imemo_memo_new(pat, ary, test); rb_block_call_func_t fn; if (rb_block_given_p()) { fn = grep_iter_i; @@ -317,21 +317,38 @@ enum_count(int argc, VALUE *argv, VALUE obj) func = count_i; } - memo = MEMO_NEW(item, 0, 0); + memo = rb_imemo_memo_new(item, 0, 0); rb_block_call(obj, id_each, 0, 0, func, (VALUE)memo); return imemo_count_value(memo); } +NORETURN(static void found(VALUE i, VALUE memop)); +static void +found(VALUE i, VALUE memop) +{ + struct MEMO *memo = MEMO_CAST(memop); + MEMO_V1_SET(memo, i); + memo->u3.cnt = 1; + rb_iter_break(); +} + +static VALUE +find_i_fast(RB_BLOCK_CALL_FUNC_ARGLIST(i, memop)) +{ + if (RTEST(rb_yield_values2(argc, argv))) { + ENUM_WANT_SVALUE(); + found(i, memop); + } + return Qnil; +} + static VALUE find_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, memop)) { ENUM_WANT_SVALUE(); if (RTEST(enum_yield(argc, i))) { - struct MEMO *memo = MEMO_CAST(memop); - MEMO_V1_SET(memo, i); - memo->u3.cnt = 1; - rb_iter_break(); + found(i, memop); } return Qnil; } @@ -354,7 +371,7 @@ find_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, memop)) * {foo: 0, bar: 1, baz: 2}.find {|key, value| key.start_with?('b') } # => [:bar, 1] * {foo: 0, bar: 1, baz: 2}.find(proc {[]}) {|key, value| key.start_with?('c') } # => [] * - * With no block given, returns an \Enumerator. + * With no block given, returns an Enumerator. * */ static VALUE @@ -365,8 +382,11 @@ enum_find(int argc, VALUE *argv, VALUE obj) if_none = rb_check_arity(argc, 0, 1) ? argv[0] : Qnil; RETURN_ENUMERATOR(obj, argc, argv); - memo = MEMO_NEW(Qundef, 0, 0); - rb_block_call(obj, id_each, 0, 0, find_i, (VALUE)memo); + memo = rb_imemo_memo_new(Qundef, 0, 0); + if (rb_block_pair_yield_optimizable()) + rb_block_call2(obj, id_each, 0, 0, find_i_fast, (VALUE)memo, RB_BLOCK_NO_USE_PACKED_ARGS); + else + rb_block_call2(obj, id_each, 0, 0, find_i, (VALUE)memo, RB_BLOCK_NO_USE_PACKED_ARGS); if (memo->u3.cnt) { return memo->v1; } @@ -424,7 +444,7 @@ find_index_iter_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, memop)) * ['a', 'b', 'c', 'b'].find_index {|element| element.start_with?('b') } # => 1 * {foo: 0, bar: 1, baz: 2}.find_index {|key, value| value > 1 } # => 2 * - * With no argument and no block given, returns an \Enumerator. + * With no argument and no block given, returns an Enumerator. * */ @@ -447,7 +467,7 @@ enum_find_index(int argc, VALUE *argv, VALUE obj) func = find_index_i; } - memo = MEMO_NEW(Qnil, condition_value, 0); + memo = rb_imemo_memo_new(Qnil, condition_value, 0); rb_block_call(obj, id_each, 0, 0, func, (VALUE)memo); return memo->v1; } @@ -501,7 +521,7 @@ enum_size_over_p(VALUE obj, long n) * a = {foo: 0, bar: 1, baz: 2}.select {|key, value| key.start_with?('b') } * a # => {:bar=>1, :baz=>2} * - * With no block given, returns an \Enumerator. + * With no block given, returns an Enumerator. * * Related: #reject. */ @@ -543,7 +563,7 @@ filter_map_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, ary)) * (0..9).filter_map {|i| i * 2 if i.even? } # => [0, 4, 8, 12, 16] * {foo: 0, bar: 1, baz: 2}.filter_map {|key, value| key if value.even? } # => [:foo, :baz] * - * When no block given, returns an \Enumerator. + * When no block given, returns an Enumerator. * */ static VALUE @@ -584,7 +604,7 @@ reject_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, ary)) * (0..9).reject {|i| i * 2 if i.even? } # => [1, 3, 5, 7, 9] * {foo: 0, bar: 1, baz: 2}.reject {|key, value| key if value.odd? } # => {:foo=>0, :baz=>2} * - * When no block given, returns an \Enumerator. + * When no block given, returns an Enumerator. * * Related: #select. */ @@ -631,7 +651,7 @@ collect_all(RB_BLOCK_CALL_FUNC_ARGLIST(i, ary)) * (0..4).map {|i| i*i } # => [0, 1, 4, 9, 16] * {foo: 0, bar: 1, baz: 2}.map {|key, value| value*2} # => [0, 2, 4] * - * With no block given, returns an \Enumerator. + * With no block given, returns an Enumerator. * */ static VALUE @@ -681,7 +701,7 @@ flat_map_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, ary)) * [[0, 1], [2, 3]].flat_map {|e| e + [100] } # => [0, 1, 100, 2, 3, 100] * {foo: 0, bar: 1, baz: 2}.flat_map {|key, value| [key, value] } # => [:foo, 0, :bar, 1, :baz, 2] * - * With no block given, returns an \Enumerator. + * With no block given, returns an Enumerator. * * Alias: #collect_concat. */ @@ -870,134 +890,151 @@ ary_inject_op(VALUE ary, VALUE init, VALUE op) /* * call-seq: - * inject(symbol) -> object - * inject(initial_operand, symbol) -> object - * inject {|memo, operand| ... } -> object - * inject(initial_operand) {|memo, operand| ... } -> object - * - * Returns an object formed from operands via either: + * inject(symbol) -> object + * inject(initial_value, symbol) -> object + * inject {|memo, value| ... } -> object + * inject(initial_value) {|memo, value| ... } -> object * - * - A method named by +symbol+. - * - A block to which each operand is passed. - * - * With method-name argument +symbol+, - * combines operands using the method: - * - * # Sum, without initial_operand. - * (1..4).inject(:+) # => 10 - * # Sum, with initial_operand. - * (1..4).inject(10, :+) # => 20 + * Returns the result of applying a reducer to an initial value and + * the first element of the Enumerable. It then takes the result and applies the + * function to it and the second element of the collection, and so on. The + * return value is the result returned by the final call to the function. * - * With a block, passes each operand to the block: - * - * # Sum of squares, without initial_operand. - * (1..4).inject {|sum, n| sum + n*n } # => 30 - * # Sum of squares, with initial_operand. - * (1..4).inject(2) {|sum, n| sum + n*n } # => 32 + * You can think of * - * <b>Operands</b> + * [ a, b, c, d ].inject(i) { |r, v| fn(r, v) } * - * If argument +initial_operand+ is not given, - * the operands for +inject+ are simply the elements of +self+. - * Example calls and their operands: + * as being * - * - <tt>(1..4).inject(:+)</tt>:: <tt>[1, 2, 3, 4]</tt>. - * - <tt>(1...4).inject(:+)</tt>:: <tt>[1, 2, 3]</tt>. - * - <tt>('a'..'d').inject(:+)</tt>:: <tt>['a', 'b', 'c', 'd']</tt>. - * - <tt>('a'...'d').inject(:+)</tt>:: <tt>['a', 'b', 'c']</tt>. + * fn(fn(fn(fn(i, a), b), c), d) * - * Examples with first operand (which is <tt>self.first</tt>) of various types: + * In a way the +inject+ function _injects_ the function + * between the elements of the enumerable. * - * # Integer. - * (1..4).inject(:+) # => 10 - * # Float. - * [1.0, 2, 3, 4].inject(:+) # => 10.0 - * # Character. - * ('a'..'d').inject(:+) # => "abcd" - * # Complex. - * [Complex(1, 2), 3, 4].inject(:+) # => (8+2i) + * +inject+ is aliased as +reduce+. You use it when you want to + * _reduce_ a collection to a single value. * - * If argument +initial_operand+ is given, - * the operands for +inject+ are that value plus the elements of +self+. - * Example calls their operands: + * <b>The Calling Sequences</b> * - * - <tt>(1..4).inject(10, :+)</tt>:: <tt>[10, 1, 2, 3, 4]</tt>. - * - <tt>(1...4).inject(10, :+)</tt>:: <tt>[10, 1, 2, 3]</tt>. - * - <tt>('a'..'d').inject('e', :+)</tt>:: <tt>['e', 'a', 'b', 'c', 'd']</tt>. - * - <tt>('a'...'d').inject('e', :+)</tt>:: <tt>['e', 'a', 'b', 'c']</tt>. + * Let's start with the most verbose: * - * Examples with +initial_operand+ of various types: + * enum.inject(initial_value) do |result, next_value| + * # do something with +result+ and +next_value+ + * # the value returned by the block becomes the + * # value passed in to the next iteration + * # as +result+ + * end * - * # Integer. - * (1..4).inject(2, :+) # => 12 - * # Float. - * (1..4).inject(2.0, :+) # => 12.0 - * # String. - * ('a'..'d').inject('foo', :+) # => "fooabcd" - * # Array. - * %w[a b c].inject(['x'], :push) # => ["x", "a", "b", "c"] - * # Complex. - * (1..4).inject(Complex(2, 2), :+) # => (12+2i) + * For example: * - * <b>Combination by Given \Method</b> + * product = [ 2, 3, 4 ].inject(1) do |result, next_value| + * result * next_value + * end + * product #=> 24 * - * If the method-name argument +symbol+ is given, - * the operands are combined by that method: + * When this runs, the block is first called with +1+ (the initial value) and + * +2+ (the first element of the array). The block returns <tt>1*2</tt>, so on + * the next iteration the block is called with +2+ (the previous result) and + * +3+. The block returns +6+, and is called one last time with +6+ and +4+. + * The result of the block, +24+ becomes the value returned by +inject+. This + * code returns the product of the elements in the enumerable. * - * - The first and second operands are combined. - * - That result is combined with the third operand. - * - That result is combined with the fourth operand. - * - And so on. + * <b>First Shortcut: Default Initial value</b> * - * The return value from +inject+ is the result of the last combination. + * In the case of the previous example, the initial value, +1+, wasn't really + * necessary: the calculation of the product of a list of numbers is self-contained. * - * This call to +inject+ computes the sum of the operands: + * In these circumstances, you can omit the +initial_value+ parameter. +inject+ + * will then initially call the block with the first element of the collection + * as the +result+ parameter and the second element as the +next_value+. * - * (1..4).inject(:+) # => 10 + * [ 2, 3, 4 ].inject do |result, next_value| + * result * next_value + * end * - * Examples with various methods: + * This shortcut is convenient, but can only be used when the block produces a result + * which can be passed back to it as a first parameter. * - * # Integer addition. - * (1..4).inject(:+) # => 10 - * # Integer multiplication. - * (1..4).inject(:*) # => 24 - * # Character range concatenation. - * ('a'..'d').inject('', :+) # => "abcd" - * # String array concatenation. - * %w[foo bar baz].inject('', :+) # => "foobarbaz" - * # Hash update. - * h = [{foo: 0, bar: 1}, {baz: 2}, {bat: 3}].inject(:update) - * h # => {:foo=>0, :bar=>1, :baz=>2, :bat=>3} - * # Hash conversion to nested arrays. - * h = {foo: 0, bar: 1}.inject([], :push) - * h # => [[:foo, 0], [:bar, 1]] + * Here's an example where that's not the case: it returns a hash where the keys are words + * and the values are the number of occurrences of that word in the enumerable. * - * <b>Combination by Given Block</b> + * freqs = File.read("README.md") + * .scan(/\w{2,}/) + * .reduce(Hash.new(0)) do |counts, word| + * counts[word] += 1 + * counts + * end + * freqs #=> {"Actions"=>4, + * "Status"=>5, + * "MinGW"=>3, + * "https"=>27, + * "github"=>10, + * "com"=>15, ... * - * If a block is given, the operands are passed to the block: + * Note that the last line of the block is just the word +counts+. This ensures the + * return value of the block is the result that's being calculated. * - * - The first call passes the first and second operands. - * - The second call passes the result of the first call, - * along with the third operand. - * - The third call passes the result of the second call, - * along with the fourth operand. - * - And so on. + * <b>Second Shortcut: a Reducer function</b> * - * The return value from +inject+ is the return value from the last block call. - * - * This call to +inject+ gives a block - * that writes the memo and element, and also sums the elements: + * A <i>reducer function</i> is a function that takes a partial result and the next value, + * returning the next partial result. The block that is given to +inject+ is a reducer. * - * (1..4).inject do |memo, element| - * p "Memo: #{memo}; element: #{element}" - * memo + element - * end # => 10 + * You can also write a reducer as a function and pass the name of that function + * (as a symbol) to +inject+. However, for this to work, the function * - * Output: + * 1. Must be defined on the type of the result value + * 2. Must accept a single parameter, the next value in the collection, and + * 3. Must return an updated result which will also implement the function. + * + * Here's an example that adds elements to a string. The two calls invoke the functions + * String#concat and String#+ on the result so far, passing it the next value. + * + * s = [ "cat", " ", "dog" ].inject("", :concat) + * s #=> "cat dog" + * s = [ "cat", " ", "dog" ].inject("The result is:", :+) + * s #=> "The result is: cat dog" + * + * Here's a more complex example when the result object maintains + * state of a different type to the enumerable elements. + * + * class Turtle + * + * def initialize + * @x = @y = 0 + * end + * + * def move(dir) + * case dir + * when "n" then @y += 1 + * when "s" then @y -= 1 + * when "e" then @x += 1 + * when "w" then @x -= 1 + * end + * self + * end + * end + * + * position = "nnneesw".chars.reduce(Turtle.new, :move) + * position #=>> #<Turtle:0x00000001052f4698 @y=2, @x=1> + * + * <b>Third Shortcut: Reducer With no Initial Value</b> + * + * If your reducer returns a value that it can accept as a parameter, then you + * don't have to pass in an initial value. Here <tt>:*</tt> is the name of the + * _times_ function: + * + * product = [ 2, 3, 4 ].inject(:*) + * product # => 24 + * + * String concatenation again: * - * "Memo: 1; element: 2" - * "Memo: 3; element: 3" - * "Memo: 6; element: 4" + * s = [ "cat", " ", "dog" ].inject(:+) + * s #=> "cat dog" + * + * And an example that converts a hash to an array of two-element subarrays. + * + * nested = {foo: 0, bar: 1}.inject([], :push) + * nested # => [[:foo, 0], [:bar, 1]] * * */ @@ -1047,7 +1084,7 @@ enum_inject(int argc, VALUE *argv, VALUE obj) return ary_inject_op(obj, init, op); } - memo = MEMO_NEW(init, Qnil, op); + memo = rb_imemo_memo_new(init, Qnil, op); rb_block_call(obj, id_each, 0, 0, iter, (VALUE)memo); if (UNDEF_P(memo->v1)) return Qnil; return memo->v1; @@ -1105,7 +1142,7 @@ enum_partition(VALUE obj) RETURN_SIZED_ENUMERATOR(obj, 0, 0, enum_size); - memo = MEMO_NEW(rb_ary_new(), rb_ary_new(), 0); + memo = rb_imemo_memo_new(rb_ary_new(), rb_ary_new(), 0); rb_block_call(obj, id_each, 0, 0, partition_i, (VALUE)memo); return rb_assoc_new(memo->v1, memo->v2); @@ -1178,14 +1215,15 @@ tally_up(st_data_t *group, st_data_t *value, st_data_t arg, int existing) RB_OBJ_WRITTEN(hash, Qundef, tally); } *value = (st_data_t)tally; - if (!SPECIAL_CONST_P(*group)) RB_OBJ_WRITTEN(hash, Qundef, *group); return ST_CONTINUE; } static VALUE rb_enum_tally_up(VALUE hash, VALUE group) { - rb_hash_stlike_update(hash, group, tally_up, (st_data_t)hash); + if (!rb_hash_stlike_update(hash, group, tally_up, (st_data_t)hash)) { + RB_OBJ_WRITTEN(hash, Qundef, group); + } return hash; } @@ -1199,29 +1237,47 @@ tally_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, hash)) /* * call-seq: - * tally -> new_hash - * tally(hash) -> hash + * tally(hash = {}) -> hash * - * Returns a hash containing the counts of equal elements: + * When argument +hash+ is not given, + * returns a new hash whose keys are the distinct elements in +self+; + * each integer value is the count of occurrences of each element: * - * - Each key is an element of +self+. - * - Each value is the number elements equal to that key. + * %w[a b c b c a c b].tally # => {"a"=>2, "b"=>3, "c"=>3} * - * With no argument: + * When argument +hash+ is given, + * returns +hash+, possibly augmented; for each element +ele+ in +self+: * - * %w[a b c b c a c b].tally # => {"a"=>2, "b"=>3, "c"=>3} + * - Adds it as a key with a zero value if that key does not already exist: + * + * hash[ele] = 0 unless hash.include?(ele) + * + * - Increments the value of key +ele+: + * + * hash[ele] += 1 + * + * This is useful for accumulating tallies across multiple enumerables: * - * With a hash argument, that hash is used for the tally (instead of a new hash), - * and is returned; - * this may be useful for accumulating tallies across multiple enumerables: + * h = {} # => {} + * %w[a c d b c a].tally(h) # => {"a"=>2, "c"=>2, "d"=>1, "b"=>1} + * %w[b a z].tally(h) # => {"a"=>3, "c"=>2, "d"=>1, "b"=>2, "z"=>1} + * %w[b a m].tally(h) # => {"a"=>4, "c"=>2, "d"=>1, "b"=>3, "z"=>1, "m"=>1} * - * hash = {} - * hash = %w[a c d b c a].tally(hash) - * hash # => {"a"=>2, "c"=>2, "d"=>1, "b"=>1} - * hash = %w[b a z].tally(hash) - * hash # => {"a"=>3, "c"=>2, "d"=>1, "b"=>2, "z"=>1} - * hash = %w[b a m].tally(hash) - * hash # => {"a"=>4, "c"=>2, "d"=>1, "b"=>3, "z"=>1, "m"=> 1} + * The key to be added or found for an element depends on the class of +self+; + * see {Enumerable in Ruby Classes}[rdoc-ref:Enumerable@Enumerable+in+Ruby+Classes]. + * + * Examples: + * + * - Array (and certain array-like classes): + * the key is the element (as above). + * - Hash (and certain hash-like classes): + * the key is the 2-element array formed from the key-value pair: + * + * h = {} # => {} + * {foo: 'a', bar: 'b'}.tally(h) # => {[:foo, "a"]=>1, [:bar, "b"]=>1} + * {foo: 'c', bar: 'd'}.tally(h) # => {[:foo, "a"]=>1, [:bar, "b"]=>1, [:foo, "c"]=>1, [:bar, "d"]=>1} + * {foo: 'a', bar: 'b'}.tally(h) # => {[:foo, "a"]=>2, [:bar, "b"]=>2, [:foo, "c"]=>1, [:bar, "d"]=>1} + * {foo: 'c', bar: 'd'}.tally(h) # => {[:foo, "a"]=>2, [:bar, "b"]=>2, [:foo, "c"]=>2, [:bar, "d"]=>2} * */ @@ -1289,7 +1345,7 @@ enum_first(int argc, VALUE *argv, VALUE obj) return enum_take(obj, argv[0]); } else { - memo = MEMO_NEW(Qnil, 0, 0); + memo = rb_imemo_memo_new(Qnil, 0, 0); rb_block_call(obj, id_each, 0, 0, first_i, (VALUE)memo); return memo->v1; } @@ -1304,7 +1360,7 @@ enum_first(int argc, VALUE *argv, VALUE obj) * The ordering of equal elements is indeterminate and may be unstable. * * With no block given, the sort compares - * using the elements' own method <tt><=></tt>: + * using the elements' own method <tt>#<=></tt>: * * %w[b c a d].sort # => ["a", "b", "c", "d"] * {foo: 0, bar: 1, baz: 2}.sort # => [[:bar, 1], [:baz, 2], [:foo, 0]] @@ -1334,10 +1390,12 @@ enum_sort(VALUE obj) } #define SORT_BY_BUFSIZE 16 +#define SORT_BY_UNIFORMED(num, flo, fix) (((num&1)<<2)|((flo&1)<<1)|fix) struct sort_by_data { const VALUE ary; const VALUE buf; - long n; + uint8_t n; + uint8_t primitive_uniformed; }; static VALUE @@ -1358,6 +1416,11 @@ sort_by_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, _data)) rb_raise(rb_eRuntimeError, "sort_by reentered"); } + if (data->primitive_uniformed) { + data->primitive_uniformed &= SORT_BY_UNIFORMED((FIXNUM_P(v)) || (RB_FLOAT_TYPE_P(v)), + RB_FLOAT_TYPE_P(v), + FIXNUM_P(v)); + } RARRAY_ASET(data->buf, data->n*2, v); RARRAY_ASET(data->buf, data->n*2+1, i); data->n++; @@ -1385,6 +1448,179 @@ sort_by_cmp(const void *ap, const void *bp, void *data) return OPTIMIZED_CMP(a, b); } + +/* + This is parts of uniform sort +*/ + +#define uless rb_uniform_is_less +#define UNIFORM_SWAP(a,b)\ + do{struct rb_uniform_sort_data tmp = a; a = b; b = tmp;} while(0) + +struct rb_uniform_sort_data { + VALUE v; + VALUE i; +}; + +static inline bool +rb_uniform_is_less(VALUE a, VALUE b) +{ + + if (FIXNUM_P(a) && FIXNUM_P(b)) { + return (SIGNED_VALUE)a < (SIGNED_VALUE)b; + } + else if (FIXNUM_P(a)) { + RUBY_ASSERT(RB_FLOAT_TYPE_P(b)); + return rb_float_cmp(b, a) > 0; + } + else { + RUBY_ASSERT(RB_FLOAT_TYPE_P(a)); + return rb_float_cmp(a, b) < 0; + } +} + +static inline bool +rb_uniform_is_larger(VALUE a, VALUE b) +{ + + if (FIXNUM_P(a) && FIXNUM_P(b)) { + return (SIGNED_VALUE)a > (SIGNED_VALUE)b; + } + else if (FIXNUM_P(a)) { + RUBY_ASSERT(RB_FLOAT_TYPE_P(b)); + return rb_float_cmp(b, a) < 0; + } + else { + RUBY_ASSERT(RB_FLOAT_TYPE_P(a)); + return rb_float_cmp(a, b) > 0; + } +} + +#define med3_val(a,b,c) (uless(a,b)?(uless(b,c)?b:uless(c,a)?a:c):(uless(c,b)?b:uless(a,c)?a:c)) + +static void +rb_uniform_insertionsort_2(struct rb_uniform_sort_data* ptr_begin, + struct rb_uniform_sort_data* ptr_end) +{ + if ((ptr_end - ptr_begin) < 2) return; + struct rb_uniform_sort_data tmp, *j, *k, + *index = ptr_begin+1; + for (; index < ptr_end; index++) { + tmp = *index; + j = k = index; + if (uless(tmp.v, ptr_begin->v)) { + while (ptr_begin < j) { + *j = *(--k); + j = k; + } + } + else { + while (uless(tmp.v, (--k)->v)) { + *j = *k; + j = k; + } + } + *j = tmp; + } +} + +static inline void +rb_uniform_heap_down_2(struct rb_uniform_sort_data* ptr_begin, + size_t offset, size_t len) +{ + size_t c; + struct rb_uniform_sort_data tmp = ptr_begin[offset]; + while ((c = (offset<<1)+1) <= len) { + if (c < len && uless(ptr_begin[c].v, ptr_begin[c+1].v)) { + c++; + } + if (!uless(tmp.v, ptr_begin[c].v)) break; + ptr_begin[offset] = ptr_begin[c]; + offset = c; + } + ptr_begin[offset] = tmp; +} + +static void +rb_uniform_heapsort_2(struct rb_uniform_sort_data* ptr_begin, + struct rb_uniform_sort_data* ptr_end) +{ + size_t n = ptr_end - ptr_begin; + if (n < 2) return; + + for (size_t offset = n>>1; offset > 0;) { + rb_uniform_heap_down_2(ptr_begin, --offset, n-1); + } + for (size_t offset = n-1; offset > 0;) { + UNIFORM_SWAP(*ptr_begin, ptr_begin[offset]); + rb_uniform_heap_down_2(ptr_begin, 0, --offset); + } +} + + +static void +rb_uniform_quicksort_intro_2(struct rb_uniform_sort_data* ptr_begin, + struct rb_uniform_sort_data* ptr_end, size_t d) +{ + + if (ptr_end - ptr_begin <= 16) { + rb_uniform_insertionsort_2(ptr_begin, ptr_end); + return; + } + if (d == 0) { + rb_uniform_heapsort_2(ptr_begin, ptr_end); + return; + } + + VALUE x = med3_val(ptr_begin->v, + ptr_begin[(ptr_end - ptr_begin)>>1].v, + ptr_end[-1].v); + struct rb_uniform_sort_data *i = ptr_begin; + struct rb_uniform_sort_data *j = ptr_end-1; + + do { + while (uless(i->v, x)) i++; + while (uless(x, j->v)) j--; + if (i <= j) { + UNIFORM_SWAP(*i, *j); + i++; + j--; + } + } while (i <= j); + j++; + if (ptr_end - j > 1) rb_uniform_quicksort_intro_2(j, ptr_end, d-1); + if (i - ptr_begin > 1) rb_uniform_quicksort_intro_2(ptr_begin, i, d-1); +} + +/** + * Direct primitive data compare sort. Implement with intro sort. + * @param[in] ptr_begin The begin address of target rb_ary's raw pointer. + * @param[in] ptr_end The end address of target rb_ary's raw pointer. +**/ +static void +rb_uniform_intro_sort_2(struct rb_uniform_sort_data* ptr_begin, + struct rb_uniform_sort_data* ptr_end) +{ + size_t n = ptr_end - ptr_begin; + size_t d = CHAR_BIT * sizeof(n) - nlz_intptr(n) - 1; + bool sorted_flag = true; + + for (struct rb_uniform_sort_data* ptr = ptr_begin+1; ptr < ptr_end; ptr++) { + if (rb_uniform_is_larger((ptr-1)->v, (ptr)->v)) { + sorted_flag = false; + break; + } + } + + if (sorted_flag) { + return; + } + rb_uniform_quicksort_intro_2(ptr_begin, ptr_end, d<<1); +} + +#undef uless + + /* * call-seq: * sort_by {|element| ... } -> array @@ -1486,11 +1722,14 @@ enum_sort_by(VALUE obj) RBASIC_CLEAR_CLASS(ary); buf = rb_ary_hidden_new(SORT_BY_BUFSIZE*2); rb_ary_store(buf, SORT_BY_BUFSIZE*2-1, Qnil); - memo = MEMO_NEW(0, 0, 0); + memo = rb_imemo_memo_new(0, 0, 0); data = (struct sort_by_data *)&memo->v1; RB_OBJ_WRITE(memo, &data->ary, ary); RB_OBJ_WRITE(memo, &data->buf, buf); data->n = 0; + data->primitive_uniformed = SORT_BY_UNIFORMED((CMP_OPTIMIZABLE(FLOAT) && CMP_OPTIMIZABLE(INTEGER)), + CMP_OPTIMIZABLE(FLOAT), + CMP_OPTIMIZABLE(INTEGER)); rb_block_call(obj, id_each, 0, 0, sort_by_i, (VALUE)memo); ary = data->ary; buf = data->buf; @@ -1499,9 +1738,16 @@ enum_sort_by(VALUE obj) rb_ary_concat(ary, buf); } if (RARRAY_LEN(ary) > 2) { - RARRAY_PTR_USE(ary, ptr, - ruby_qsort(ptr, RARRAY_LEN(ary)/2, 2*sizeof(VALUE), - sort_by_cmp, (void *)ary)); + if (data->primitive_uniformed) { + RARRAY_PTR_USE(ary, ptr, + rb_uniform_intro_sort_2((struct rb_uniform_sort_data*)ptr, + (struct rb_uniform_sort_data*)(ptr + RARRAY_LEN(ary)))); + } + else { + RARRAY_PTR_USE(ary, ptr, + ruby_qsort(ptr, RARRAY_LEN(ary)/2, 2*sizeof(VALUE), + sort_by_cmp, (void *)ary)); + } } if (RBASIC(ary)->klass) { rb_raise(rb_eRuntimeError, "sort_by reentered"); @@ -1517,7 +1763,10 @@ enum_sort_by(VALUE obj) #define ENUMFUNC(name) argc ? name##_eqq : rb_block_given_p() ? name##_iter_i : name##_i -#define MEMO_ENUM_NEW(v1) (rb_check_arity(argc, 0, 1), MEMO_NEW((v1), (argc ? *argv : 0), 0)) +#define ENUM_BLOCK_CALL(name) \ + rb_block_call2(obj, id_each, 0, 0, ENUMFUNC(name), (VALUE)memo, rb_block_given_p() && rb_block_pair_yield_optimizable() ? RB_BLOCK_NO_USE_PACKED_ARGS : 0); + +#define MEMO_ENUM_NEW(v1) (rb_check_arity(argc, 0, 1), rb_imemo_memo_new((v1), (argc ? *argv : 0), 0)) #define DEFINE_ENUMFUNCS(name) \ static VALUE enum_##name##_func(VALUE result, struct MEMO *memo); \ @@ -1567,6 +1816,9 @@ DEFINE_ENUMFUNCS(all) * * Returns whether every element meets a given criterion. * + * If +self+ has no element, returns +true+ and argument or block + * are not used. + * * With no argument and no block, * returns whether every element is truthy: * @@ -1607,7 +1859,7 @@ enum_all(int argc, VALUE *argv, VALUE obj) { struct MEMO *memo = MEMO_ENUM_NEW(Qtrue); WARN_UNUSED_BLOCK(argc); - rb_block_call(obj, id_each, 0, 0, ENUMFUNC(all), (VALUE)memo); + ENUM_BLOCK_CALL(all); return memo->v1; } @@ -1628,6 +1880,9 @@ DEFINE_ENUMFUNCS(any) * * Returns whether any element meets a given criterion. * + * If +self+ has no element, returns +false+ and argument or block + * are not used. + * * With no argument and no block, * returns whether any element is truthy: * @@ -1658,7 +1913,6 @@ DEFINE_ENUMFUNCS(any) * {foo: 0, bar: 1, baz: 2}.any? {|key, value| value < 1 } # => true * {foo: 0, bar: 1, baz: 2}.any? {|key, value| value < 0 } # => false * - * * Related: #all?, #none?, #one?. */ @@ -1667,7 +1921,7 @@ enum_any(int argc, VALUE *argv, VALUE obj) { struct MEMO *memo = MEMO_ENUM_NEW(Qfalse); WARN_UNUSED_BLOCK(argc); - rb_block_call(obj, id_each, 0, 0, ENUMFUNC(any), (VALUE)memo); + ENUM_BLOCK_CALL(any); return memo->v1; } @@ -1956,7 +2210,7 @@ enum_one(int argc, VALUE *argv, VALUE obj) VALUE result; WARN_UNUSED_BLOCK(argc); - rb_block_call(obj, id_each, 0, 0, ENUMFUNC(one), (VALUE)memo); + ENUM_BLOCK_CALL(one); result = memo->v1; if (UNDEF_P(result)) return Qfalse; return result; @@ -2017,7 +2271,7 @@ enum_none(int argc, VALUE *argv, VALUE obj) struct MEMO *memo = MEMO_ENUM_NEW(Qtrue); WARN_UNUSED_BLOCK(argc); - rb_block_call(obj, id_each, 0, 0, ENUMFUNC(none), (VALUE)memo); + ENUM_BLOCK_CALL(none); return memo->v1; } @@ -2075,7 +2329,7 @@ min_ii(RB_BLOCK_CALL_FUNC_ARGLIST(i, args)) * The ordering of equal elements is indeterminate and may be unstable. * * With no argument and no block, returns the minimum element, - * using the elements' own method <tt><=></tt> for comparison: + * using the elements' own method <tt>#<=></tt> for comparison: * * (1..4).min # => 1 * (-4..-1).min # => -4 @@ -2197,7 +2451,7 @@ max_ii(RB_BLOCK_CALL_FUNC_ARGLIST(i, args)) * The ordering of equal elements is indeterminate and may be unstable. * * With no argument and no block, returns the maximum element, - * using the elements' own method <tt><=></tt> for comparison: + * using the elements' own method <tt>#<=></tt> for comparison: * * (1..4).max # => 4 * (-4..-1).max # => -1 @@ -2386,7 +2640,7 @@ minmax_ii(RB_BLOCK_CALL_FUNC_ARGLIST(i, _memo)) * The ordering of equal elements is indeterminate and may be unstable. * * With no argument and no block, returns the minimum and maximum elements, - * using the elements' own method <tt><=></tt> for comparison: + * using the elements' own method <tt>#<=></tt> for comparison: * * (1..4).minmax # => [1, 4] * (-4..-1).minmax # => [-4, -1] @@ -2500,7 +2754,7 @@ enum_min_by(int argc, VALUE *argv, VALUE obj) if (argc && !NIL_P(num = argv[0])) return rb_nmin_run(obj, num, 1, 0, 0); - memo = MEMO_NEW(Qundef, Qnil, 0); + memo = rb_imemo_memo_new(Qundef, Qnil, 0); rb_block_call(obj, id_each, 0, 0, min_by_i, (VALUE)memo); return memo->v2; } @@ -2574,7 +2828,7 @@ enum_max_by(int argc, VALUE *argv, VALUE obj) if (argc && !NIL_P(num = argv[0])) return rb_nmin_run(obj, num, 1, 1, 0); - memo = MEMO_NEW(Qundef, Qnil, 0); + memo = rb_imemo_memo_new(Qundef, Qnil, 0); rb_block_call(obj, id_each, 0, 0, max_by_i, (VALUE)memo); return memo->v2; } @@ -2725,20 +2979,19 @@ member_i(RB_BLOCK_CALL_FUNC_ARGLIST(iter, args)) static VALUE enum_member(VALUE obj, VALUE val) { - struct MEMO *memo = MEMO_NEW(val, Qfalse, 0); + struct MEMO *memo = rb_imemo_memo_new(val, Qfalse, 0); rb_block_call(obj, id_each, 0, 0, member_i, (VALUE)memo); return memo->v2; } static VALUE -each_with_index_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, memo)) +each_with_index_i(RB_BLOCK_CALL_FUNC_ARGLIST(_, index)) { - struct MEMO *m = MEMO_CAST(memo); - VALUE n = imemo_count_value(m); + struct vm_ifunc *ifunc = rb_current_ifunc(); + ifunc->data = (const void *)rb_int_succ(index); - imemo_count_up(m); - return rb_yield_values(2, rb_enum_values_pack(argc, argv), n); + return rb_yield_values(2, rb_enum_values_pack(argc, argv), index); } /* @@ -2746,7 +2999,8 @@ each_with_index_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, memo)) * each_with_index(*args) {|element, i| ..... } -> self * each_with_index(*args) -> enumerator * - * With a block given, calls the block with each element and its index; + * Invoke <tt>self.each</tt> with <tt>*args</tt>. + * With a block given, the block receives each element and its index; * returns +self+: * * h = {} @@ -2771,12 +3025,9 @@ each_with_index_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, memo)) static VALUE enum_each_with_index(int argc, VALUE *argv, VALUE obj) { - struct MEMO *memo; - RETURN_SIZED_ENUMERATOR(obj, argc, argv, enum_size); - memo = MEMO_NEW(0, 0, 0); - rb_block_call(obj, id_each, argc, argv, each_with_index_i, (VALUE)memo); + rb_block_call(obj, id_each, argc, argv, each_with_index_i, INT2FIX(0)); return obj; } @@ -2980,7 +3231,7 @@ enum_each_slice(VALUE obj, VALUE n) size = limit_by_enum_size(obj, size); ary = rb_ary_new2(size); arity = rb_block_arity(); - memo = MEMO_NEW(ary, dont_recycle_block_arg(arity), size); + memo = rb_imemo_memo_new(ary, dont_recycle_block_arg(arity), size); rb_block_call(obj, id_each, 0, 0, each_slice_i, (VALUE)memo); ary = memo->v1; if (RARRAY_LEN(ary) > 0) rb_yield(ary); @@ -3056,7 +3307,7 @@ enum_each_cons(VALUE obj, VALUE n) RETURN_SIZED_ENUMERATOR(obj, 1, &n, enum_each_cons_size); arity = rb_block_arity(); if (enum_size_over_p(obj, size)) return obj; - memo = MEMO_NEW(rb_ary_new2(size), dont_recycle_block_arg(arity), size); + memo = rb_imemo_memo_new(rb_ary_new2(size), dont_recycle_block_arg(arity), size); rb_block_call(obj, id_each, 0, 0, each_cons_i, (VALUE)memo); return obj; @@ -3285,7 +3536,7 @@ enum_zip(int argc, VALUE *argv, VALUE obj) } /* TODO: use NODE_DOT2 as memo(v, v, -) */ - memo = MEMO_NEW(result, args, 0); + memo = rb_imemo_memo_new(result, args, 0); rb_block_call(obj, id_each, 0, 0, allary ? zip_ary : zip_i, (VALUE)memo); return result; @@ -3328,7 +3579,7 @@ enum_take(VALUE obj, VALUE n) if (len == 0) return rb_ary_new2(0); result = rb_ary_new2(len); - memo = MEMO_NEW(result, 0, len); + memo = rb_imemo_memo_new(result, 0, len); rb_block_call(obj, id_each, 0, 0, take_i, (VALUE)memo); return result; } @@ -3416,7 +3667,7 @@ enum_drop(VALUE obj, VALUE n) } result = rb_ary_new(); - memo = MEMO_NEW(result, 0, len); + memo = rb_imemo_memo_new(result, 0, len); rb_block_call(obj, id_each, 0, 0, drop_i, (VALUE)memo); return result; } @@ -3454,6 +3705,17 @@ drop_while_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, args)) * * With no block given, returns an Enumerator. * + * e = (1..4).drop_while + * p e #=> #<Enumerator: 1..4:drop_while> + * i = e.next; p i; e.feed(i < 3) #=> 1 + * i = e.next; p i; e.feed(i < 3) #=> 2 + * i = e.next; p i; e.feed(i < 3) #=> 3 + * begin + * e.next + * rescue StopIteration + * p $!.result #=> [3, 4] + * end + * */ static VALUE @@ -3464,7 +3726,7 @@ enum_drop_while(VALUE obj) RETURN_ENUMERATOR(obj, 0, 0); result = rb_ary_new(); - memo = MEMO_NEW(result, 0, FALSE); + memo = rb_imemo_memo_new(result, 0, FALSE); rb_block_call(obj, id_each, 0, 0, drop_while_i, (VALUE)memo); return result; } @@ -3663,7 +3925,7 @@ chunk_i(RB_BLOCK_CALL_FUNC_ARGLIST(yielder, enumerator)) * e.next # => [2, [6, 7, 8]] * e.next # => [3, [9, 10]] * - * \Method +chunk+ is especially useful for an enumerable that is already sorted. + * Method +chunk+ is especially useful for an enumerable that is already sorted. * This example counts words for each initial letter in a large array of words: * * # Get sorted words from a web page. @@ -3684,7 +3946,7 @@ chunk_i(RB_BLOCK_CALL_FUNC_ARGLIST(yielder, enumerator)) * ["F", 6860] * * You can use the special symbol <tt>:_alone</tt> to force an element - * into its own separate chuck: + * into its own separate chunk: * * a = [0, 0, 1, 1] * e = a.chunk{|i| i.even? ? :_alone : true } @@ -4343,7 +4605,7 @@ struct enum_sum_memo { static void sum_iter_normalize_memo(struct enum_sum_memo *memo) { - assert(FIXABLE(memo->n)); + RUBY_ASSERT(FIXABLE(memo->n)); memo->v = rb_fix_plus(LONG2FIX(memo->n), memo->v); memo->n = 0; @@ -4445,7 +4707,7 @@ sum_iter_Kahan_Babuska(VALUE i, struct enum_sum_memo *memo) static void sum_iter(VALUE i, struct enum_sum_memo *memo) { - assert(memo != NULL); + RUBY_ASSERT(memo != NULL); if (memo->block_given) { i = rb_yield(i); } @@ -4455,7 +4717,7 @@ sum_iter(VALUE i, struct enum_sum_memo *memo) } else switch (TYPE(memo->v)) { default: sum_iter_some_value(i, memo); return; - case T_FLOAT: sum_iter_Kahan_Babuska(i, memo); return; + case T_FLOAT: case T_FIXNUM: case T_BIGNUM: case T_RATIONAL: @@ -4496,8 +4758,8 @@ hash_sum_i(VALUE key, VALUE value, VALUE arg) static void hash_sum(VALUE hash, struct enum_sum_memo *memo) { - assert(RB_TYPE_P(hash, T_HASH)); - assert(memo != NULL); + RUBY_ASSERT(RB_TYPE_P(hash, T_HASH)); + RUBY_ASSERT(memo != NULL); rb_hash_foreach(hash, hash_sum_i, (VALUE)memo); } @@ -4629,13 +4891,13 @@ uniq_iter(RB_BLOCK_CALL_FUNC_ARGLIST(i, hash)) * %w[a b c c b a a b c].uniq # => ["a", "b", "c"] * [0, 1, 2, 2, 1, 0, 0, 1, 2].uniq # => [0, 1, 2] * - * With a block, returns a new array containing only for which the block + * With a block, returns a new array containing elements only for which the block * returns a unique value: * * a = [0, 1, 2, 3, 4, 5, 5, 4, 3, 2, 1] * a.uniq {|i| i.even? ? i : 0 } # => [0, 2, 4] * a = %w[a b c d e e d c b a a b c d e] - a.uniq {|c| c < 'c' } # => ["a", "c"] + * a.uniq {|c| c < 'c' } # => ["a", "c"] * */ @@ -4690,11 +4952,11 @@ enum_compact(VALUE obj) /* * == What's Here * - * \Module \Enumerable provides methods that are useful to a collection class for: + * Module \Enumerable provides methods that are useful to a collection class for: * * - {Querying}[rdoc-ref:Enumerable@Methods+for+Querying] * - {Fetching}[rdoc-ref:Enumerable@Methods+for+Fetching] - * - {Searching}[rdoc-ref:Enumerable@Methods+for+Searching] + * - {Searching and Filtering}[rdoc-ref:Enumerable@Methods+for+Searching+and+Filtering] * - {Sorting}[rdoc-ref:Enumerable@Methods+for+Sorting] * - {Iterating}[rdoc-ref:Enumerable@Methods+for+Iterating] * - {And more....}[rdoc-ref:Enumerable@Other+Methods] @@ -4703,14 +4965,14 @@ enum_compact(VALUE obj) * * These methods return information about the \Enumerable other than the elements themselves: * - * - #include?, #member?: Returns +true+ if <tt>self == object</tt>, +false+ otherwise. + * - #member? (aliased as #include?): Returns +true+ if <tt>self == object</tt>, +false+ otherwise. * - #all?: Returns +true+ if all elements meet a specified criterion; +false+ otherwise. * - #any?: Returns +true+ if any element meets a specified criterion; +false+ otherwise. * - #none?: Returns +true+ if no element meets a specified criterion; +false+ otherwise. * - #one?: Returns +true+ if exactly one element meets a specified criterion; +false+ otherwise. * - #count: Returns the count of elements, * based on an argument or block criterion, if given. - * - #tally: Returns a new \Hash containing the counts of occurrences of each element. + * - #tally: Returns a new Hash containing the counts of occurrences of each element. * * === Methods for Fetching * @@ -4718,7 +4980,7 @@ enum_compact(VALUE obj) * * <i>Leading, trailing, or all elements</i>: * - * - #entries, #to_a: Returns all elements. + * - #to_a (aliased as #entries): Returns all elements. * - #first: Returns the first element or leading elements. * - #take: Returns a specified number of leading elements. * - #drop: Returns a specified number of trailing elements. @@ -4728,24 +4990,24 @@ enum_compact(VALUE obj) * <i>Minimum and maximum value elements</i>: * * - #min: Returns the elements whose values are smallest among the elements, - * as determined by <tt><=></tt> or a given block. + * as determined by <tt>#<=></tt> or a given block. * - #max: Returns the elements whose values are largest among the elements, - * as determined by <tt><=></tt> or a given block. - * - #minmax: Returns a 2-element \Array containing the smallest and largest elements. + * as determined by <tt>#<=></tt> or a given block. + * - #minmax: Returns a 2-element Array containing the smallest and largest elements. * - #min_by: Returns the smallest element, as determined by the given block. * - #max_by: Returns the largest element, as determined by the given block. * - #minmax_by: Returns the smallest and largest elements, as determined by the given block. * * <i>Groups, slices, and partitions</i>: * - * - #group_by: Returns a \Hash that partitions the elements into groups. + * - #group_by: Returns a Hash that partitions the elements into groups. * - #partition: Returns elements partitioned into two new Arrays, as determined by the given block. - * - #slice_after: Returns a new \Enumerator whose entries are a partition of +self+, - based either on a given +object+ or a given block. - * - #slice_before: Returns a new \Enumerator whose entries are a partition of +self+, - based either on a given +object+ or a given block. - * - #slice_when: Returns a new \Enumerator whose entries are a partition of +self+ - based on the given block. + * - #slice_after: Returns a new Enumerator whose entries are a partition of +self+, + * based either on a given +object+ or a given block. + * - #slice_before: Returns a new Enumerator whose entries are a partition of +self+, + * based either on a given +object+ or a given block. + * - #slice_when: Returns a new Enumerator whose entries are a partition of +self+ + * based on the given block. * - #chunk: Returns elements organized into chunks as specified by the given block. * - #chunk_while: Returns elements organized into chunks as specified by the given block. * @@ -4753,8 +5015,8 @@ enum_compact(VALUE obj) * * These methods return elements that meet a specified criterion: * - * - #find, #detect: Returns an element selected by the block. - * - #find_all, #filter, #select: Returns elements selected by the block. + * - #find (aliased as #detect): Returns an element selected by the block. + * - #find_all (aliased as #filter, #select): Returns elements selected by the block. * - #find_index: Returns the index of an element selected by a given object or block. * - #reject: Returns elements not rejected by the block. * - #uniq: Returns elements that are not duplicates. @@ -4763,7 +5025,7 @@ enum_compact(VALUE obj) * * These methods return elements in sorted order: * - * - #sort: Returns the elements, sorted by <tt><=></tt> or the given block. + * - #sort: Returns the elements, sorted by <tt>#<=></tt> or the given block. * - #sort_by: Returns the elements, sorted by the given block. * * === Methods for Iterating @@ -4779,14 +5041,14 @@ enum_compact(VALUE obj) * * === Other Methods * - * - #map, #collect: Returns objects returned by the block. + * - #collect (aliased as #map): Returns objects returned by the block. * - #filter_map: Returns truthy objects returned by the block. - * - #flat_map, #collect_concat: Returns flattened objects returned by the block. + * - #flat_map (aliased as #collect_concat): Returns flattened objects returned by the block. * - #grep: Returns elements selected by a given object * or objects returned by a given block. - * - #grep_v: Returns elements selected by a given object + * - #grep_v: Returns elements not selected by a given object * or objects returned by a given block. - * - #reduce, #inject: Returns the object formed by combining all elements. + * - #inject (aliased as #reduce): Returns the object formed by combining all elements. * - #sum: Returns the sum of the elements, using method <tt>+</tt>. * - #zip: Combines each element with elements from other enumerables; * returns the n-tuples or calls the block with each. @@ -4845,18 +5107,94 @@ enum_compact(VALUE obj) * * Virtually all methods in \Enumerable call method +#each+ in the including class: * - * - <tt>Hash#each</tt> yields the next key-value pair as a 2-element \Array. - * - <tt>Struct#each</tt> yields the next name-value pair as a 2-element \Array. + * - <tt>Hash#each</tt> yields the next key-value pair as a 2-element Array. + * - <tt>Struct#each</tt> yields the next name-value pair as a 2-element Array. * - For the other classes above, +#each+ yields the next object from the collection. * * == About the Examples * * The example code snippets for the \Enumerable methods: * - * - Always show the use of one or more \Array-like classes (often \Array itself). - * - Sometimes show the use of a \Hash-like class. + * - Always show the use of one or more Array-like classes (often Array itself). + * - Sometimes show the use of a Hash-like class. * For some methods, though, the usage would not make sense, - * and so it is not shown. Example: #tally would find exactly one of each \Hash entry. + * and so it is not shown. Example: #tally would find exactly one of each Hash entry. + * + * == Extended Methods + * + * A Enumerable class may define extended methods. This section describes the standard + * behavior of extension methods for reference purposes. + * + * === #size + * + * \Enumerator has a #size method. + * It uses the size function argument passed to +Enumerator.new+. + * + * e = Enumerator.new(-> { 3 }) {|y| p y; y.yield :a; y.yield :b; y.yield :c; :z } + * p e.size #=> 3 + * p e.next #=> :a + * p e.next #=> :b + * p e.next #=> :c + * begin + * e.next + * rescue StopIteration + * p $!.result #=> :z + * end + * + * The result of the size function should represent the number of iterations + * (i.e., the number of times Enumerator::Yielder#yield is called). + * In the above example, the block calls #yield three times, and + * the size function, +-> { 3 }+, returns 3 accordingly. + * The result of the size function can be an integer, +Float::INFINITY+, + * or +nil+. + * An integer means the exact number of times #yield will be called, + * as shown above. + * +Float::INFINITY+ indicates an infinite number of #yield calls. + * +nil+ means the number of #yield calls is difficult or impossible to + * determine. + * + * Many iteration methods return an \Enumerator object with an + * appropriate size function if no block is given. + * + * Examples: + * + * ["a", "b", "c"].each.size #=> 3 + * {a: "x", b: "y", c: "z"}.each.size #=> 3 + * (0..20).to_a.permutation.size #=> 51090942171709440000 + * loop.size #=> Float::INFINITY + * (1..100).drop_while.size #=> nil # size depends on the block's behavior + * STDIN.each.size #=> nil # cannot be computed without consuming input + * File.open("/etc/resolv.conf").each.size #=> nil # cannot be computed without reading the file + * + * The behavior of #size for Range-based enumerators depends on the #begin element: + * + * - If the #begin element is an Integer, the #size method returns an Integer or +Float::INFINITY+. + * - If the #begin element is an object with a #succ method (other than Integer), #size returns +nil+. + * (Computing the size would require repeatedly calling #succ, which may be too slow.) + * - If the #begin element does not have a #succ method, #size raises a TypeError. + * + * Examples: + * + * (10..42).each.size #=> 33 + * (10..42.9).each.size #=> 33 (the #end element may be a non-integer numeric) + * (10..).each.size #=> Float::INFINITY + * ("a".."z").each.size #=> nil + * ("a"..).each.size #=> nil + * (1.0..9.0).each.size # raises TypeError (Float does not have #succ) + * (..10).each.size # raises TypeError (beginless range has nil as its #begin) + * + * The \Enumerable module itself does not define a #size method. + * A class that includes \Enumerable may define its own #size method. + * It is recommended that such a #size method be consistent with + * Enumerator#size. + * + * Array and Hash implement #size and return values consistent with + * Enumerator#size. + * IO and Dir do not define #size, which is also consistent because the + * corresponding enumerator's size function returns +nil+. + * + * However, it is not strictly required for a class's #size method to match Enumerator#size. + * For example, File#size returns the number of bytes in the file, not the number of lines. * */ |