Ruby 1.9.3p327(2012-11-10revision37606)
array.c
Go to the documentation of this file.
00001 /**********************************************************************
00002 
00003   array.c -
00004 
00005   $Author: marcandre $
00006   created at: Fri Aug  6 09:46:12 JST 1993
00007 
00008   Copyright (C) 1993-2007 Yukihiro Matsumoto
00009   Copyright (C) 2000  Network Applied Communication Laboratory, Inc.
00010   Copyright (C) 2000  Information-technology Promotion Agency, Japan
00011 
00012 **********************************************************************/
00013 
00014 #include "ruby/ruby.h"
00015 #include "ruby/util.h"
00016 #include "ruby/st.h"
00017 #include "ruby/encoding.h"
00018 #include "internal.h"
00019 
00020 #ifndef ARRAY_DEBUG
00021 # define NDEBUG
00022 #endif
00023 #include <assert.h>
00024 
00025 #define numberof(array) (int)(sizeof(array) / sizeof((array)[0]))
00026 
00027 VALUE rb_cArray;
00028 
00029 static ID id_cmp;
00030 
00031 #define ARY_DEFAULT_SIZE 16
00032 #define ARY_MAX_SIZE (LONG_MAX / (int)sizeof(VALUE))
00033 
00034 void
00035 rb_mem_clear(register VALUE *mem, register long size)
00036 {
00037     while (size--) {
00038         *mem++ = Qnil;
00039     }
00040 }
00041 
00042 static inline void
00043 memfill(register VALUE *mem, register long size, register VALUE val)
00044 {
00045     while (size--) {
00046         *mem++ = val;
00047     }
00048 }
00049 
00050 # define ARY_SHARED_P(ary) \
00051     (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
00052      FL_TEST((ary),ELTS_SHARED)!=0)
00053 # define ARY_EMBED_P(ary) \
00054     (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
00055      FL_TEST((ary), RARRAY_EMBED_FLAG)!=0)
00056 
00057 #define ARY_HEAP_PTR(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.ptr)
00058 #define ARY_HEAP_LEN(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.len)
00059 #define ARY_EMBED_PTR(a) (assert(ARY_EMBED_P(a)), RARRAY(a)->as.ary)
00060 #define ARY_EMBED_LEN(a) \
00061     (assert(ARY_EMBED_P(a)), \
00062      (long)((RBASIC(a)->flags >> RARRAY_EMBED_LEN_SHIFT) & \
00063          (RARRAY_EMBED_LEN_MASK >> RARRAY_EMBED_LEN_SHIFT)))
00064 
00065 #define ARY_OWNS_HEAP_P(a) (!FL_TEST((a), ELTS_SHARED|RARRAY_EMBED_FLAG))
00066 #define FL_SET_EMBED(a) do { \
00067     assert(!ARY_SHARED_P(a)); \
00068     assert(!OBJ_FROZEN(a)); \
00069     FL_SET((a), RARRAY_EMBED_FLAG); \
00070 } while (0)
00071 #define FL_UNSET_EMBED(ary) FL_UNSET((ary), RARRAY_EMBED_FLAG|RARRAY_EMBED_LEN_MASK)
00072 #define FL_SET_SHARED(ary) do { \
00073     assert(!ARY_EMBED_P(ary)); \
00074     FL_SET((ary), ELTS_SHARED); \
00075 } while (0)
00076 #define FL_UNSET_SHARED(ary) FL_UNSET((ary), ELTS_SHARED)
00077 
00078 #define ARY_SET_PTR(ary, p) do { \
00079     assert(!ARY_EMBED_P(ary)); \
00080     assert(!OBJ_FROZEN(ary)); \
00081     RARRAY(ary)->as.heap.ptr = (p); \
00082 } while (0)
00083 #define ARY_SET_EMBED_LEN(ary, n) do { \
00084     long tmp_n = (n); \
00085     assert(ARY_EMBED_P(ary)); \
00086     assert(!OBJ_FROZEN(ary)); \
00087     RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK; \
00088     RBASIC(ary)->flags |= (tmp_n) << RARRAY_EMBED_LEN_SHIFT; \
00089 } while (0)
00090 #define ARY_SET_HEAP_LEN(ary, n) do { \
00091     assert(!ARY_EMBED_P(ary)); \
00092     RARRAY(ary)->as.heap.len = (n); \
00093 } while (0)
00094 #define ARY_SET_LEN(ary, n) do { \
00095     if (ARY_EMBED_P(ary)) { \
00096         ARY_SET_EMBED_LEN((ary), (n)); \
00097     } \
00098     else { \
00099         ARY_SET_HEAP_LEN((ary), (n)); \
00100     } \
00101     assert(RARRAY_LEN(ary) == (n)); \
00102 } while (0)
00103 #define ARY_INCREASE_PTR(ary, n) do  { \
00104     assert(!ARY_EMBED_P(ary)); \
00105     assert(!OBJ_FROZEN(ary)); \
00106     RARRAY(ary)->as.heap.ptr += (n); \
00107 } while (0)
00108 #define ARY_INCREASE_LEN(ary, n) do  { \
00109     assert(!OBJ_FROZEN(ary)); \
00110     if (ARY_EMBED_P(ary)) { \
00111         ARY_SET_EMBED_LEN((ary), RARRAY_LEN(ary)+(n)); \
00112     } \
00113     else { \
00114         RARRAY(ary)->as.heap.len += (n); \
00115     } \
00116 } while (0)
00117 
00118 #define ARY_CAPA(ary) (ARY_EMBED_P(ary) ? RARRAY_EMBED_LEN_MAX : \
00119                        ARY_SHARED_ROOT_P(ary) ? RARRAY_LEN(ary) : RARRAY(ary)->as.heap.aux.capa)
00120 #define ARY_SET_CAPA(ary, n) do { \
00121     assert(!ARY_EMBED_P(ary)); \
00122     assert(!ARY_SHARED_P(ary)); \
00123     assert(!OBJ_FROZEN(ary)); \
00124     RARRAY(ary)->as.heap.aux.capa = (n); \
00125 } while (0)
00126 
00127 #define ARY_SHARED(ary) (assert(ARY_SHARED_P(ary)), RARRAY(ary)->as.heap.aux.shared)
00128 #define ARY_SET_SHARED(ary, value) do { \
00129     assert(!ARY_EMBED_P(ary)); \
00130     assert(ARY_SHARED_P(ary)); \
00131     assert(ARY_SHARED_ROOT_P(value)); \
00132     RARRAY(ary)->as.heap.aux.shared = (value); \
00133 } while (0)
00134 #define RARRAY_SHARED_ROOT_FLAG FL_USER5
00135 #define ARY_SHARED_ROOT_P(ary) (FL_TEST((ary), RARRAY_SHARED_ROOT_FLAG))
00136 #define ARY_SHARED_NUM(ary) \
00137     (assert(ARY_SHARED_ROOT_P(ary)), RARRAY(ary)->as.heap.aux.capa)
00138 #define ARY_SET_SHARED_NUM(ary, value) do { \
00139     assert(ARY_SHARED_ROOT_P(ary)); \
00140     RARRAY(ary)->as.heap.aux.capa = (value); \
00141 } while (0)
00142 #define FL_SET_SHARED_ROOT(ary) do { \
00143     assert(!ARY_EMBED_P(ary)); \
00144     FL_SET((ary), RARRAY_SHARED_ROOT_FLAG); \
00145 } while (0)
00146 
00147 static void
00148 ary_resize_capa(VALUE ary, long capacity)
00149 {
00150     assert(RARRAY_LEN(ary) <= capacity);
00151     assert(!OBJ_FROZEN(ary));
00152     assert(!ARY_SHARED_P(ary));
00153     if (capacity > RARRAY_EMBED_LEN_MAX) {
00154         if (ARY_EMBED_P(ary)) {
00155             long len = ARY_EMBED_LEN(ary);
00156             VALUE *ptr = ALLOC_N(VALUE, (capacity));
00157             MEMCPY(ptr, ARY_EMBED_PTR(ary), VALUE, len);
00158             FL_UNSET_EMBED(ary);
00159             ARY_SET_PTR(ary, ptr);
00160             ARY_SET_HEAP_LEN(ary, len);
00161         }
00162         else {
00163             REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, (capacity));
00164         }
00165         ARY_SET_CAPA(ary, (capacity));
00166     }
00167     else {
00168         if (!ARY_EMBED_P(ary)) {
00169             long len = RARRAY_LEN(ary);
00170             VALUE *ptr = RARRAY_PTR(ary);
00171             if (len > capacity) len = capacity;
00172             MEMCPY(RARRAY(ary)->as.ary, ptr, VALUE, len);
00173             FL_SET_EMBED(ary);
00174             ARY_SET_LEN(ary, len);
00175             xfree(ptr);
00176         }
00177     }
00178 }
00179 
00180 static void
00181 ary_double_capa(VALUE ary, long min)
00182 {
00183     long new_capa = ARY_CAPA(ary) / 2;
00184 
00185     if (new_capa < ARY_DEFAULT_SIZE) {
00186         new_capa = ARY_DEFAULT_SIZE;
00187     }
00188     if (new_capa >= ARY_MAX_SIZE - min) {
00189         new_capa = (ARY_MAX_SIZE - min) / 2;
00190     }
00191     new_capa += min;
00192     ary_resize_capa(ary, new_capa);
00193 }
00194 
00195 static void
00196 rb_ary_decrement_share(VALUE shared)
00197 {
00198     if (shared) {
00199         long num = ARY_SHARED_NUM(shared) - 1;
00200         if (num == 0) {
00201             rb_ary_free(shared);
00202             rb_gc_force_recycle(shared);
00203         }
00204         else if (num > 0) {
00205             ARY_SET_SHARED_NUM(shared, num);
00206         }
00207     }
00208 }
00209 
00210 static void
00211 rb_ary_unshare(VALUE ary)
00212 {
00213     VALUE shared = RARRAY(ary)->as.heap.aux.shared;
00214     rb_ary_decrement_share(shared);
00215     FL_UNSET_SHARED(ary);
00216 }
00217 
00218 static inline void
00219 rb_ary_unshare_safe(VALUE ary)
00220 {
00221     if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
00222         rb_ary_unshare(ary);
00223     }
00224 }
00225 
00226 static VALUE
00227 rb_ary_increment_share(VALUE shared)
00228 {
00229     long num = ARY_SHARED_NUM(shared);
00230     if (num >= 0) {
00231         ARY_SET_SHARED_NUM(shared, num + 1);
00232     }
00233     return shared;
00234 }
00235 
00236 static void
00237 rb_ary_set_shared(VALUE ary, VALUE shared)
00238 {
00239     rb_ary_increment_share(shared);
00240     FL_SET_SHARED(ary);
00241     ARY_SET_SHARED(ary, shared);
00242 }
00243 
00244 static inline void
00245 rb_ary_modify_check(VALUE ary)
00246 {
00247     rb_check_frozen(ary);
00248     if (!OBJ_UNTRUSTED(ary) && rb_safe_level() >= 4)
00249         rb_raise(rb_eSecurityError, "Insecure: can't modify array");
00250 }
00251 
00252 void
00253 rb_ary_modify(VALUE ary)
00254 {
00255     rb_ary_modify_check(ary);
00256     if (ARY_SHARED_P(ary)) {
00257         long len = RARRAY_LEN(ary);
00258         if (len <= RARRAY_EMBED_LEN_MAX) {
00259             VALUE *ptr = ARY_HEAP_PTR(ary);
00260             VALUE shared = ARY_SHARED(ary);
00261             FL_UNSET_SHARED(ary);
00262             FL_SET_EMBED(ary);
00263             MEMCPY(ARY_EMBED_PTR(ary), ptr, VALUE, len);
00264             rb_ary_decrement_share(shared);
00265             ARY_SET_EMBED_LEN(ary, len);
00266         }
00267         else {
00268             VALUE *ptr = ALLOC_N(VALUE, len);
00269             MEMCPY(ptr, RARRAY_PTR(ary), VALUE, len);
00270             rb_ary_unshare(ary);
00271             ARY_SET_CAPA(ary, len);
00272             ARY_SET_PTR(ary, ptr);
00273         }
00274     }
00275 }
00276 
00277 VALUE
00278 rb_ary_freeze(VALUE ary)
00279 {
00280     return rb_obj_freeze(ary);
00281 }
00282 
00283 /*
00284  *  call-seq:
00285  *     ary.frozen?  -> true or false
00286  *
00287  *  Return <code>true</code> if this array is frozen (or temporarily frozen
00288  *  while being sorted).
00289  */
00290 
00291 static VALUE
00292 rb_ary_frozen_p(VALUE ary)
00293 {
00294     if (OBJ_FROZEN(ary)) return Qtrue;
00295     return Qfalse;
00296 }
00297 
00298 static VALUE
00299 ary_alloc(VALUE klass)
00300 {
00301     NEWOBJ(ary, struct RArray);
00302     OBJSETUP(ary, klass, T_ARRAY);
00303     FL_SET_EMBED((VALUE)ary);
00304     ARY_SET_EMBED_LEN((VALUE)ary, 0);
00305 
00306     return (VALUE)ary;
00307 }
00308 
00309 static VALUE
00310 ary_new(VALUE klass, long capa)
00311 {
00312     VALUE ary;
00313 
00314     if (capa < 0) {
00315         rb_raise(rb_eArgError, "negative array size (or size too big)");
00316     }
00317     if (capa > ARY_MAX_SIZE) {
00318         rb_raise(rb_eArgError, "array size too big");
00319     }
00320     ary = ary_alloc(klass);
00321     if (capa > RARRAY_EMBED_LEN_MAX) {
00322         FL_UNSET_EMBED(ary);
00323         ARY_SET_PTR(ary, ALLOC_N(VALUE, capa));
00324         ARY_SET_CAPA(ary, capa);
00325         ARY_SET_HEAP_LEN(ary, 0);
00326     }
00327 
00328     return ary;
00329 }
00330 
00331 VALUE
00332 rb_ary_new2(long capa)
00333 {
00334     return ary_new(rb_cArray, capa);
00335 }
00336 
00337 
00338 VALUE
00339 rb_ary_new(void)
00340 {
00341     return rb_ary_new2(RARRAY_EMBED_LEN_MAX);
00342 }
00343 
00344 #include <stdarg.h>
00345 
00346 VALUE
00347 rb_ary_new3(long n, ...)
00348 {
00349     va_list ar;
00350     VALUE ary;
00351     long i;
00352 
00353     ary = rb_ary_new2(n);
00354 
00355     va_start(ar, n);
00356     for (i=0; i<n; i++) {
00357         RARRAY_PTR(ary)[i] = va_arg(ar, VALUE);
00358     }
00359     va_end(ar);
00360 
00361     ARY_SET_LEN(ary, n);
00362     return ary;
00363 }
00364 
00365 VALUE
00366 rb_ary_new4(long n, const VALUE *elts)
00367 {
00368     VALUE ary;
00369 
00370     ary = rb_ary_new2(n);
00371     if (n > 0 && elts) {
00372         MEMCPY(RARRAY_PTR(ary), elts, VALUE, n);
00373         ARY_SET_LEN(ary, n);
00374     }
00375 
00376     return ary;
00377 }
00378 
00379 VALUE
00380 rb_ary_tmp_new(long capa)
00381 {
00382     return ary_new(0, capa);
00383 }
00384 
00385 void
00386 rb_ary_free(VALUE ary)
00387 {
00388     if (ARY_OWNS_HEAP_P(ary)) {
00389         xfree(ARY_HEAP_PTR(ary));
00390     }
00391 }
00392 
00393 RUBY_FUNC_EXPORTED size_t
00394 rb_ary_memsize(VALUE ary)
00395 {
00396     if (ARY_OWNS_HEAP_P(ary)) {
00397         return RARRAY(ary)->as.heap.aux.capa * sizeof(VALUE);
00398     }
00399     else {
00400         return 0;
00401     }
00402 }
00403 
00404 static inline void
00405 ary_discard(VALUE ary)
00406 {
00407     rb_ary_free(ary);
00408     RBASIC(ary)->flags |= RARRAY_EMBED_FLAG;
00409     RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK;
00410 }
00411 
00412 static VALUE
00413 ary_make_shared(VALUE ary)
00414 {
00415     assert(!ARY_EMBED_P(ary));
00416     if (ARY_SHARED_P(ary)) {
00417         return ARY_SHARED(ary);
00418     }
00419     else if (ARY_SHARED_ROOT_P(ary)) {
00420         return ary;
00421     }
00422     else if (OBJ_FROZEN(ary)) {
00423         ary_resize_capa(ary, ARY_HEAP_LEN(ary));
00424         FL_SET_SHARED_ROOT(ary);
00425         ARY_SET_SHARED_NUM(ary, 1);
00426         return ary;
00427     }
00428     else {
00429         NEWOBJ(shared, struct RArray);
00430         OBJSETUP(shared, 0, T_ARRAY);
00431         FL_UNSET_EMBED(shared);
00432 
00433         ARY_SET_LEN((VALUE)shared, RARRAY_LEN(ary));
00434         ARY_SET_PTR((VALUE)shared, RARRAY_PTR(ary));
00435         FL_SET_SHARED_ROOT(shared);
00436         ARY_SET_SHARED_NUM((VALUE)shared, 1);
00437         FL_SET_SHARED(ary);
00438         ARY_SET_SHARED(ary, (VALUE)shared);
00439         OBJ_FREEZE(shared);
00440         return (VALUE)shared;
00441     }
00442 }
00443 
00444 
00445 static VALUE
00446 ary_make_substitution(VALUE ary)
00447 {
00448     if (RARRAY_LEN(ary) <= RARRAY_EMBED_LEN_MAX) {
00449         VALUE subst = rb_ary_new2(RARRAY_LEN(ary));
00450         MEMCPY(ARY_EMBED_PTR(subst), RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
00451         ARY_SET_EMBED_LEN(subst, RARRAY_LEN(ary));
00452         return subst;
00453     }
00454     else {
00455         return rb_ary_increment_share(ary_make_shared(ary));
00456     }
00457 }
00458 
00459 VALUE
00460 rb_assoc_new(VALUE car, VALUE cdr)
00461 {
00462     return rb_ary_new3(2, car, cdr);
00463 }
00464 
00465 static VALUE
00466 to_ary(VALUE ary)
00467 {
00468     return rb_convert_type(ary, T_ARRAY, "Array", "to_ary");
00469 }
00470 
00471 VALUE
00472 rb_check_array_type(VALUE ary)
00473 {
00474     return rb_check_convert_type(ary, T_ARRAY, "Array", "to_ary");
00475 }
00476 
00477 /*
00478  *  call-seq:
00479  *     Array.try_convert(obj) -> array or nil
00480  *
00481  *  Tries to convert +obj+ into an array, using +to_ary+ method.  Returns the
00482  *  converted array or +nil+ if +obj+ cannot be converted for any reason.
00483  *  This method can be used to check if an argument is an array.
00484  *
00485  *     Array.try_convert([1])   #=> [1]
00486  *     Array.try_convert("1")   #=> nil
00487  *
00488  *     if tmp = Array.try_convert(arg)
00489  *       # the argument is an array
00490  *     elsif tmp = String.try_convert(arg)
00491  *       # the argument is a string
00492  *     end
00493  *
00494  */
00495 
00496 static VALUE
00497 rb_ary_s_try_convert(VALUE dummy, VALUE ary)
00498 {
00499     return rb_check_array_type(ary);
00500 }
00501 
00502 /*
00503  *  call-seq:
00504  *     Array.new(size=0, obj=nil)
00505  *     Array.new(array)
00506  *     Array.new(size) {|index| block }
00507  *
00508  *  Returns a new array.
00509  *
00510  *  In the first form, if no arguments are sent, the new array will be empty.
00511  *  When a +size+ and an optional +obj+ are sent, an array is created with
00512  *  +size+ copies of +obj+.  Take notice that all elements will reference the
00513  *  same object +obj+.
00514  *
00515  *  The second form creates a copy of the array passed as a parameter (the
00516  *  array is generated by calling to_ary on the parameter).
00517  *
00518  *    first_array = ["Matz", "Guido"]
00519  *
00520  *    second_array = Array.new(first_array) #=> ["Matz", "Guido"]
00521  *
00522  *    first_array.equal? second_array       #=> false
00523  *
00524  *  In the last form, an array of the given size is created.  Each element in
00525  *  this array is created by passing the element's index to the given block
00526  *  and storing the return value.
00527  *
00528  *    Array.new(3){ |index| index ** 2 }
00529  *    # => [0, 1, 4]
00530  *
00531  *  == Common gotchas
00532  *
00533  *  When sending the second parameter, the same object will be used as the
00534  *  value for all the array elements:
00535  *
00536  *     a = Array.new(2, Hash.new)
00537  *     # => [{}, {}]
00538  *
00539  *     a[0]['cat'] = 'feline'
00540  *     a # => [{"cat"=>"feline"}, {"cat"=>"feline"}]
00541  *
00542  *     a[1]['cat'] = 'Felix'
00543  *     a # => [{"cat"=>"Felix"}, {"cat"=>"Felix"}]
00544  *
00545  *  Since all the Array elements store the same hash, changes to one of them
00546  *  will affect them all.
00547  *
00548  *  If multiple copies are what you want, you should use the block
00549  *  version which uses the result of that block each time an element
00550  *  of the array needs to be initialized:
00551  *
00552  *     a = Array.new(2) { Hash.new }
00553  *     a[0]['cat'] = 'feline'
00554  *     a # => [{"cat"=>"feline"}, {}]
00555  *
00556  */
00557 
00558 static VALUE
00559 rb_ary_initialize(int argc, VALUE *argv, VALUE ary)
00560 {
00561     long len;
00562     VALUE size, val;
00563 
00564     rb_ary_modify(ary);
00565     if (argc == 0) {
00566         if (ARY_OWNS_HEAP_P(ary) && RARRAY_PTR(ary)) {
00567             xfree(RARRAY_PTR(ary));
00568         }
00569         rb_ary_unshare_safe(ary);
00570         FL_SET_EMBED(ary);
00571         ARY_SET_EMBED_LEN(ary, 0);
00572         if (rb_block_given_p()) {
00573             rb_warning("given block not used");
00574         }
00575         return ary;
00576     }
00577     rb_scan_args(argc, argv, "02", &size, &val);
00578     if (argc == 1 && !FIXNUM_P(size)) {
00579         val = rb_check_array_type(size);
00580         if (!NIL_P(val)) {
00581             rb_ary_replace(ary, val);
00582             return ary;
00583         }
00584     }
00585 
00586     len = NUM2LONG(size);
00587     if (len < 0) {
00588         rb_raise(rb_eArgError, "negative array size");
00589     }
00590     if (len > ARY_MAX_SIZE) {
00591         rb_raise(rb_eArgError, "array size too big");
00592     }
00593     rb_ary_modify(ary);
00594     ary_resize_capa(ary, len);
00595     if (rb_block_given_p()) {
00596         long i;
00597 
00598         if (argc == 2) {
00599             rb_warn("block supersedes default value argument");
00600         }
00601         for (i=0; i<len; i++) {
00602             rb_ary_store(ary, i, rb_yield(LONG2NUM(i)));
00603             ARY_SET_LEN(ary, i + 1);
00604         }
00605     }
00606     else {
00607         memfill(RARRAY_PTR(ary), len, val);
00608         ARY_SET_LEN(ary, len);
00609     }
00610     return ary;
00611 }
00612 
00613 
00614 /*
00615 * Returns a new array populated with the given objects.
00616 *
00617 *   Array.[]( 1, 'a', /^A/ )
00618 *   Array[ 1, 'a', /^A/ ]
00619 *   [ 1, 'a', /^A/ ]
00620 */
00621 
00622 static VALUE
00623 rb_ary_s_create(int argc, VALUE *argv, VALUE klass)
00624 {
00625     VALUE ary = ary_new(klass, argc);
00626     if (argc > 0 && argv) {
00627         MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
00628         ARY_SET_LEN(ary, argc);
00629     }
00630 
00631     return ary;
00632 }
00633 
00634 void
00635 rb_ary_store(VALUE ary, long idx, VALUE val)
00636 {
00637     if (idx < 0) {
00638         idx += RARRAY_LEN(ary);
00639         if (idx < 0) {
00640             rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
00641                      idx - RARRAY_LEN(ary), -RARRAY_LEN(ary));
00642         }
00643     }
00644     else if (idx >= ARY_MAX_SIZE) {
00645         rb_raise(rb_eIndexError, "index %ld too big", idx);
00646     }
00647 
00648     rb_ary_modify(ary);
00649     if (idx >= ARY_CAPA(ary)) {
00650         ary_double_capa(ary, idx);
00651     }
00652     if (idx > RARRAY_LEN(ary)) {
00653         rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary),
00654                      idx-RARRAY_LEN(ary) + 1);
00655     }
00656 
00657     if (idx >= RARRAY_LEN(ary)) {
00658         ARY_SET_LEN(ary, idx + 1);
00659     }
00660     RARRAY_PTR(ary)[idx] = val;
00661 }
00662 
00663 static VALUE
00664 ary_make_partial(VALUE ary, VALUE klass, long offset, long len)
00665 {
00666     assert(offset >= 0);
00667     assert(len >= 0);
00668     assert(offset+len <= RARRAY_LEN(ary));
00669 
00670     if (len <= RARRAY_EMBED_LEN_MAX) {
00671         VALUE result = ary_alloc(klass);
00672         MEMCPY(ARY_EMBED_PTR(result), RARRAY_PTR(ary) + offset, VALUE, len);
00673         ARY_SET_EMBED_LEN(result, len);
00674         return result;
00675     }
00676     else {
00677         VALUE shared, result = ary_alloc(klass);
00678         FL_UNSET_EMBED(result);
00679 
00680         shared = ary_make_shared(ary);
00681         ARY_SET_PTR(result, RARRAY_PTR(ary));
00682         ARY_SET_LEN(result, RARRAY_LEN(ary));
00683         rb_ary_set_shared(result, shared);
00684 
00685         ARY_INCREASE_PTR(result, offset);
00686         ARY_SET_LEN(result, len);
00687         return result;
00688     }
00689 }
00690 
00691 static VALUE
00692 ary_make_shared_copy(VALUE ary)
00693 {
00694     return ary_make_partial(ary, rb_obj_class(ary), 0, RARRAY_LEN(ary));
00695 }
00696 
00697 enum ary_take_pos_flags
00698 {
00699     ARY_TAKE_FIRST = 0,
00700     ARY_TAKE_LAST = 1
00701 };
00702 
00703 static VALUE
00704 ary_take_first_or_last(int argc, VALUE *argv, VALUE ary, enum ary_take_pos_flags last)
00705 {
00706     VALUE nv;
00707     long n;
00708     long offset = 0;
00709 
00710     rb_scan_args(argc, argv, "1", &nv);
00711     n = NUM2LONG(nv);
00712     if (n > RARRAY_LEN(ary)) {
00713         n = RARRAY_LEN(ary);
00714     }
00715     else if (n < 0) {
00716         rb_raise(rb_eArgError, "negative array size");
00717     }
00718     if (last) {
00719         offset = RARRAY_LEN(ary) - n;
00720     }
00721     return ary_make_partial(ary, rb_cArray, offset, n);
00722 }
00723 
00724 static VALUE rb_ary_push_1(VALUE ary, VALUE item);
00725 
00726 /*
00727  *  call-seq:
00728  *     ary << obj            -> ary
00729  *
00730  *  Append---Pushes the given object on to the end of this array. This
00731  *  expression returns the array itself, so several appends
00732  *  may be chained together.
00733  *
00734  *     [ 1, 2 ] << "c" << "d" << [ 3, 4 ]
00735  *             #=>  [ 1, 2, "c", "d", [ 3, 4 ] ]
00736  *
00737  */
00738 
00739 VALUE
00740 rb_ary_push(VALUE ary, VALUE item)
00741 {
00742     rb_ary_modify(ary);
00743     return rb_ary_push_1(ary, item);
00744 }
00745 
00746 static VALUE
00747 rb_ary_push_1(VALUE ary, VALUE item)
00748 {
00749     long idx = RARRAY_LEN(ary);
00750 
00751     if (idx >= ARY_CAPA(ary)) {
00752         ary_double_capa(ary, idx);
00753     }
00754     RARRAY_PTR(ary)[idx] = item;
00755     ARY_SET_LEN(ary, idx + 1);
00756     return ary;
00757 }
00758 
00759 /*
00760  *  call-seq:
00761  *     ary.push(obj, ... )   -> ary
00762  *
00763  *  Append---Pushes the given object(s) on to the end of this array. This
00764  *  expression returns the array itself, so several appends
00765  *  may be chained together.
00766  *
00767  *     a = [ "a", "b", "c" ]
00768  *     a.push("d", "e", "f")
00769  *             #=> ["a", "b", "c", "d", "e", "f"]
00770  */
00771 
00772 static VALUE
00773 rb_ary_push_m(int argc, VALUE *argv, VALUE ary)
00774 {
00775     rb_ary_modify(ary);
00776     while (argc--) {
00777         rb_ary_push_1(ary, *argv++);
00778     }
00779     return ary;
00780 }
00781 
00782 VALUE
00783 rb_ary_pop(VALUE ary)
00784 {
00785     long n;
00786     rb_ary_modify_check(ary);
00787     if (RARRAY_LEN(ary) == 0) return Qnil;
00788     if (ARY_OWNS_HEAP_P(ary) &&
00789         RARRAY_LEN(ary) * 3 < ARY_CAPA(ary) &&
00790         ARY_CAPA(ary) > ARY_DEFAULT_SIZE)
00791     {
00792         ary_resize_capa(ary, RARRAY_LEN(ary) * 2);
00793     }
00794     n = RARRAY_LEN(ary)-1;
00795     ARY_SET_LEN(ary, n);
00796     return RARRAY_PTR(ary)[n];
00797 }
00798 
00799 /*
00800  *  call-seq:
00801  *     ary.pop    -> obj or nil
00802  *     ary.pop(n) -> new_ary
00803  *
00804  *  Removes the last element from +self+ and returns it, or
00805  *  <code>nil</code> if the array is empty.
00806  *
00807  *  If a number _n_ is given, returns an array of the last n elements
00808  *  (or less) just like <code>array.slice!(-n, n)</code> does.
00809  *
00810  *     a = [ "a", "b", "c", "d" ]
00811  *     a.pop     #=> "d"
00812  *     a.pop(2)  #=> ["b", "c"]
00813  *     a         #=> ["a"]
00814  */
00815 
00816 static VALUE
00817 rb_ary_pop_m(int argc, VALUE *argv, VALUE ary)
00818 {
00819     VALUE result;
00820 
00821     if (argc == 0) {
00822         return rb_ary_pop(ary);
00823     }
00824 
00825     rb_ary_modify_check(ary);
00826     result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_LAST);
00827     ARY_INCREASE_LEN(ary, -RARRAY_LEN(result));
00828     return result;
00829 }
00830 
00831 VALUE
00832 rb_ary_shift(VALUE ary)
00833 {
00834     VALUE top;
00835 
00836     rb_ary_modify_check(ary);
00837     if (RARRAY_LEN(ary) == 0) return Qnil;
00838     top = RARRAY_PTR(ary)[0];
00839     if (!ARY_SHARED_P(ary)) {
00840         if (RARRAY_LEN(ary) < ARY_DEFAULT_SIZE) {
00841             MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+1, VALUE, RARRAY_LEN(ary)-1);
00842             ARY_INCREASE_LEN(ary, -1);
00843             return top;
00844         }
00845         assert(!ARY_EMBED_P(ary)); /* ARY_EMBED_LEN_MAX < ARY_DEFAULT_SIZE */
00846 
00847         RARRAY_PTR(ary)[0] = Qnil;
00848         ary_make_shared(ary);
00849     }
00850     else if (ARY_SHARED_NUM(ARY_SHARED(ary)) == 1) {
00851         RARRAY_PTR(ary)[0] = Qnil;
00852     }
00853     ARY_INCREASE_PTR(ary, 1);           /* shift ptr */
00854     ARY_INCREASE_LEN(ary, -1);
00855 
00856     return top;
00857 }
00858 
00859 /*
00860  *  call-seq:
00861  *     ary.shift    -> obj or nil
00862  *     ary.shift(n) -> new_ary
00863  *
00864  *  Returns the first element of +self+ and removes it (shifting all
00865  *  other elements down by one). Returns <code>nil</code> if the array
00866  *  is empty.
00867  *
00868  *  If a number _n_ is given, returns an array of the first n elements
00869  *  (or less) just like <code>array.slice!(0, n)</code> does.
00870  *
00871  *     args = [ "-m", "-q", "filename" ]
00872  *     args.shift     #=> "-m"
00873  *     args           #=> ["-q", "filename"]
00874  *
00875  *     args = [ "-m", "-q", "filename" ]
00876  *     args.shift(2)  #=> ["-m", "-q"]
00877  *     args           #=> ["filename"]
00878  */
00879 
00880 static VALUE
00881 rb_ary_shift_m(int argc, VALUE *argv, VALUE ary)
00882 {
00883     VALUE result;
00884     long n;
00885 
00886     if (argc == 0) {
00887         return rb_ary_shift(ary);
00888     }
00889 
00890     rb_ary_modify_check(ary);
00891     result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
00892     n = RARRAY_LEN(result);
00893     if (ARY_SHARED_P(ary)) {
00894         if (ARY_SHARED_NUM(ARY_SHARED(ary)) == 1) {
00895             rb_mem_clear(RARRAY_PTR(ary), n);
00896         }
00897         ARY_INCREASE_PTR(ary, n);
00898     }
00899     else {
00900         MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+n, VALUE, RARRAY_LEN(ary)-n);
00901     }
00902     ARY_INCREASE_LEN(ary, -n);
00903 
00904     return result;
00905 }
00906 
00907 /*
00908  *  call-seq:
00909  *     ary.unshift(obj, ...)  -> ary
00910  *
00911  *  Prepends objects to the front of +self+,
00912  *  moving other elements upwards.
00913  *
00914  *     a = [ "b", "c", "d" ]
00915  *     a.unshift("a")   #=> ["a", "b", "c", "d"]
00916  *     a.unshift(1, 2)  #=> [ 1, 2, "a", "b", "c", "d"]
00917  */
00918 
00919 static VALUE
00920 rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
00921 {
00922     long len;
00923 
00924     rb_ary_modify(ary);
00925     if (argc == 0) return ary;
00926     if (ARY_CAPA(ary) <= (len = RARRAY_LEN(ary)) + argc) {
00927         ary_double_capa(ary, len + argc);
00928     }
00929 
00930     /* sliding items */
00931     MEMMOVE(RARRAY_PTR(ary) + argc, RARRAY_PTR(ary), VALUE, len);
00932     MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
00933     ARY_INCREASE_LEN(ary, argc);
00934 
00935     return ary;
00936 }
00937 
00938 VALUE
00939 rb_ary_unshift(VALUE ary, VALUE item)
00940 {
00941     return rb_ary_unshift_m(1,&item,ary);
00942 }
00943 
00944 /* faster version - use this if you don't need to treat negative offset */
00945 static inline VALUE
00946 rb_ary_elt(VALUE ary, long offset)
00947 {
00948     if (RARRAY_LEN(ary) == 0) return Qnil;
00949     if (offset < 0 || RARRAY_LEN(ary) <= offset) {
00950         return Qnil;
00951     }
00952     return RARRAY_PTR(ary)[offset];
00953 }
00954 
00955 VALUE
00956 rb_ary_entry(VALUE ary, long offset)
00957 {
00958     if (offset < 0) {
00959         offset += RARRAY_LEN(ary);
00960     }
00961     return rb_ary_elt(ary, offset);
00962 }
00963 
00964 VALUE
00965 rb_ary_subseq(VALUE ary, long beg, long len)
00966 {
00967     VALUE klass;
00968 
00969     if (beg > RARRAY_LEN(ary)) return Qnil;
00970     if (beg < 0 || len < 0) return Qnil;
00971 
00972     if (RARRAY_LEN(ary) < len || RARRAY_LEN(ary) < beg + len) {
00973         len = RARRAY_LEN(ary) - beg;
00974     }
00975     klass = rb_obj_class(ary);
00976     if (len == 0) return ary_new(klass, 0);
00977 
00978     return ary_make_partial(ary, klass, beg, len);
00979 }
00980 
00981 /*
00982  *  call-seq:
00983  *     ary[index]                -> obj     or nil
00984  *     ary[start, length]        -> new_ary or nil
00985  *     ary[range]                -> new_ary or nil
00986  *     ary.slice(index)          -> obj     or nil
00987  *     ary.slice(start, length)  -> new_ary or nil
00988  *     ary.slice(range)          -> new_ary or nil
00989  *
00990  *  Element Reference---Returns the element at _index_,
00991  *  or returns a subarray starting at _start_ and
00992  *  continuing for _length_ elements, or returns a subarray
00993  *  specified by _range_.
00994  *  Negative indices count backward from the end of the
00995  *  array (-1 is the last element). Returns +nil+ if the index
00996  *  (or starting index) are out of range.
00997  *
00998  *     a = [ "a", "b", "c", "d", "e" ]
00999  *     a[2] +  a[0] + a[1]    #=> "cab"
01000  *     a[6]                   #=> nil
01001  *     a[1, 2]                #=> [ "b", "c" ]
01002  *     a[1..3]                #=> [ "b", "c", "d" ]
01003  *     a[4..7]                #=> [ "e" ]
01004  *     a[6..10]               #=> nil
01005  *     a[-3, 3]               #=> [ "c", "d", "e" ]
01006  *     # special cases
01007  *     a[5]                   #=> nil
01008  *     a[5, 1]                #=> []
01009  *     a[5..10]               #=> []
01010  *
01011  */
01012 
01013 VALUE
01014 rb_ary_aref(int argc, VALUE *argv, VALUE ary)
01015 {
01016     VALUE arg;
01017     long beg, len;
01018 
01019     if (argc == 2) {
01020         beg = NUM2LONG(argv[0]);
01021         len = NUM2LONG(argv[1]);
01022         if (beg < 0) {
01023             beg += RARRAY_LEN(ary);
01024         }
01025         return rb_ary_subseq(ary, beg, len);
01026     }
01027     if (argc != 1) {
01028         rb_scan_args(argc, argv, "11", 0, 0);
01029     }
01030     arg = argv[0];
01031     /* special case - speeding up */
01032     if (FIXNUM_P(arg)) {
01033         return rb_ary_entry(ary, FIX2LONG(arg));
01034     }
01035     /* check if idx is Range */
01036     switch (rb_range_beg_len(arg, &beg, &len, RARRAY_LEN(ary), 0)) {
01037       case Qfalse:
01038         break;
01039       case Qnil:
01040         return Qnil;
01041       default:
01042         return rb_ary_subseq(ary, beg, len);
01043     }
01044     return rb_ary_entry(ary, NUM2LONG(arg));
01045 }
01046 
01047 /*
01048  *  call-seq:
01049  *     ary.at(index)   ->   obj  or nil
01050  *
01051  *  Returns the element at _index_. A
01052  *  negative index counts from the end of +self+.  Returns +nil+
01053  *  if the index is out of range. See also <code>Array#[]</code>.
01054  *
01055  *     a = [ "a", "b", "c", "d", "e" ]
01056  *     a.at(0)     #=> "a"
01057  *     a.at(-1)    #=> "e"
01058  */
01059 
01060 static VALUE
01061 rb_ary_at(VALUE ary, VALUE pos)
01062 {
01063     return rb_ary_entry(ary, NUM2LONG(pos));
01064 }
01065 
01066 /*
01067  *  call-seq:
01068  *     ary.first     ->   obj or nil
01069  *     ary.first(n)  ->   new_ary
01070  *
01071  *  Returns the first element, or the first +n+ elements, of the array.
01072  *  If the array is empty, the first form returns <code>nil</code>, and the
01073  *  second form returns an empty array.
01074  *
01075  *     a = [ "q", "r", "s", "t" ]
01076  *     a.first     #=> "q"
01077  *     a.first(2)  #=> ["q", "r"]
01078  */
01079 
01080 static VALUE
01081 rb_ary_first(int argc, VALUE *argv, VALUE ary)
01082 {
01083     if (argc == 0) {
01084         if (RARRAY_LEN(ary) == 0) return Qnil;
01085         return RARRAY_PTR(ary)[0];
01086     }
01087     else {
01088         return ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
01089     }
01090 }
01091 
01092 /*
01093  *  call-seq:
01094  *     ary.last     ->  obj or nil
01095  *     ary.last(n)  ->  new_ary
01096  *
01097  *  Returns the last element(s) of +self+. If the array is empty,
01098  *  the first form returns <code>nil</code>.
01099  *
01100  *     a = [ "w", "x", "y", "z" ]
01101  *     a.last     #=> "z"
01102  *     a.last(2)  #=> ["y", "z"]
01103  */
01104 
01105 VALUE
01106 rb_ary_last(int argc, VALUE *argv, VALUE ary)
01107 {
01108     if (argc == 0) {
01109         if (RARRAY_LEN(ary) == 0) return Qnil;
01110         return RARRAY_PTR(ary)[RARRAY_LEN(ary)-1];
01111     }
01112     else {
01113         return ary_take_first_or_last(argc, argv, ary, ARY_TAKE_LAST);
01114     }
01115 }
01116 
01117 /*
01118  *  call-seq:
01119  *     ary.fetch(index)                    -> obj
01120  *     ary.fetch(index, default )          -> obj
01121  *     ary.fetch(index) {|index| block }   -> obj
01122  *
01123  *  Tries to return the element at position <i>index</i>. If the index
01124  *  lies outside the array, the first form throws an
01125  *  <code>IndexError</code> exception, the second form returns
01126  *  <i>default</i>, and the third form returns the value of invoking
01127  *  the block, passing in the index. Negative values of <i>index</i>
01128  *  count from the end of the array.
01129  *
01130  *     a = [ 11, 22, 33, 44 ]
01131  *     a.fetch(1)               #=> 22
01132  *     a.fetch(-1)              #=> 44
01133  *     a.fetch(4, 'cat')        #=> "cat"
01134  *     a.fetch(4) { |i| i*i }   #=> 16
01135  */
01136 
01137 static VALUE
01138 rb_ary_fetch(int argc, VALUE *argv, VALUE ary)
01139 {
01140     VALUE pos, ifnone;
01141     long block_given;
01142     long idx;
01143 
01144     rb_scan_args(argc, argv, "11", &pos, &ifnone);
01145     block_given = rb_block_given_p();
01146     if (block_given && argc == 2) {
01147         rb_warn("block supersedes default value argument");
01148     }
01149     idx = NUM2LONG(pos);
01150 
01151     if (idx < 0) {
01152         idx +=  RARRAY_LEN(ary);
01153     }
01154     if (idx < 0 || RARRAY_LEN(ary) <= idx) {
01155         if (block_given) return rb_yield(pos);
01156         if (argc == 1) {
01157             rb_raise(rb_eIndexError, "index %ld outside of array bounds: %ld...%ld",
01158                         idx - (idx < 0 ? RARRAY_LEN(ary) : 0), -RARRAY_LEN(ary), RARRAY_LEN(ary));
01159         }
01160         return ifnone;
01161     }
01162     return RARRAY_PTR(ary)[idx];
01163 }
01164 
01165 /*
01166  *  call-seq:
01167  *     ary.index(obj)           ->  int or nil
01168  *     ary.index {|item| block} ->  int or nil
01169  *     ary.index                ->  an_enumerator
01170  *
01171  *  Returns the index of the first object in +self+ such that the object is
01172  *  <code>==</code> to <i>obj</i>. If a block is given instead of an
01173  *  argument, returns index of first object for which <em>block</em> is true.
01174  *  Returns <code>nil</code> if no match is found.
01175  *  See also <code>Array#rindex</code>.
01176  *
01177  *  If neither block nor argument is given, an enumerator is returned instead.
01178  *
01179  *     a = [ "a", "b", "c" ]
01180  *     a.index("b")        #=> 1
01181  *     a.index("z")        #=> nil
01182  *     a.index{|x|x=="b"}  #=> 1
01183  *
01184  *  This is an alias of <code>#find_index</code>.
01185  */
01186 
01187 static VALUE
01188 rb_ary_index(int argc, VALUE *argv, VALUE ary)
01189 {
01190     VALUE val;
01191     long i;
01192 
01193     if (argc == 0) {
01194         RETURN_ENUMERATOR(ary, 0, 0);
01195         for (i=0; i<RARRAY_LEN(ary); i++) {
01196             if (RTEST(rb_yield(RARRAY_PTR(ary)[i]))) {
01197                 return LONG2NUM(i);
01198             }
01199         }
01200         return Qnil;
01201     }
01202     rb_scan_args(argc, argv, "1", &val);
01203     if (rb_block_given_p())
01204         rb_warn("given block not used");
01205     for (i=0; i<RARRAY_LEN(ary); i++) {
01206         if (rb_equal(RARRAY_PTR(ary)[i], val))
01207             return LONG2NUM(i);
01208     }
01209     return Qnil;
01210 }
01211 
01212 /*
01213  *  call-seq:
01214  *     ary.rindex(obj)           ->  int or nil
01215  *     ary.rindex {|item| block} ->  int or nil
01216  *     ary.rindex                ->  an_enumerator
01217  *
01218  *  Returns the index of the last object in +self+
01219  *  <code>==</code> to <i>obj</i>. If a block is given instead of an
01220  *  argument, returns index of first object for which <em>block</em> is
01221  *  true, starting from the last object.
01222  *  Returns <code>nil</code> if no match is found.
01223  *  See also <code>Array#index</code>.
01224  *
01225  *  If neither block nor argument is given, an enumerator is returned instead.
01226  *
01227  *     a = [ "a", "b", "b", "b", "c" ]
01228  *     a.rindex("b")             #=> 3
01229  *     a.rindex("z")             #=> nil
01230  *     a.rindex { |x| x == "b" } #=> 3
01231  */
01232 
01233 static VALUE
01234 rb_ary_rindex(int argc, VALUE *argv, VALUE ary)
01235 {
01236     VALUE val;
01237     long i = RARRAY_LEN(ary);
01238 
01239     if (argc == 0) {
01240         RETURN_ENUMERATOR(ary, 0, 0);
01241         while (i--) {
01242             if (RTEST(rb_yield(RARRAY_PTR(ary)[i])))
01243                 return LONG2NUM(i);
01244             if (i > RARRAY_LEN(ary)) {
01245                 i = RARRAY_LEN(ary);
01246             }
01247         }
01248         return Qnil;
01249     }
01250     rb_scan_args(argc, argv, "1", &val);
01251     if (rb_block_given_p())
01252         rb_warn("given block not used");
01253     while (i--) {
01254         if (rb_equal(RARRAY_PTR(ary)[i], val))
01255             return LONG2NUM(i);
01256         if (i > RARRAY_LEN(ary)) {
01257             i = RARRAY_LEN(ary);
01258         }
01259     }
01260     return Qnil;
01261 }
01262 
01263 VALUE
01264 rb_ary_to_ary(VALUE obj)
01265 {
01266     VALUE tmp = rb_check_array_type(obj);
01267 
01268     if (!NIL_P(tmp)) return tmp;
01269     return rb_ary_new3(1, obj);
01270 }
01271 
01272 static void
01273 rb_ary_splice(VALUE ary, long beg, long len, VALUE rpl)
01274 {
01275     long rlen;
01276 
01277     if (len < 0) rb_raise(rb_eIndexError, "negative length (%ld)", len);
01278     if (beg < 0) {
01279         beg += RARRAY_LEN(ary);
01280         if (beg < 0) {
01281             rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
01282                      beg - RARRAY_LEN(ary), -RARRAY_LEN(ary));
01283         }
01284     }
01285     if (RARRAY_LEN(ary) < len || RARRAY_LEN(ary) < beg + len) {
01286         len = RARRAY_LEN(ary) - beg;
01287     }
01288 
01289     if (rpl == Qundef) {
01290         rlen = 0;
01291     }
01292     else {
01293         rpl = rb_ary_to_ary(rpl);
01294         rlen = RARRAY_LEN(rpl);
01295     }
01296     rb_ary_modify(ary);
01297     if (beg >= RARRAY_LEN(ary)) {
01298         if (beg > ARY_MAX_SIZE - rlen) {
01299             rb_raise(rb_eIndexError, "index %ld too big", beg);
01300         }
01301         len = beg + rlen;
01302         if (len >= ARY_CAPA(ary)) {
01303             ary_double_capa(ary, len);
01304         }
01305         rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary), beg - RARRAY_LEN(ary));
01306         if (rlen > 0) {
01307             MEMCPY(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
01308         }
01309         ARY_SET_LEN(ary, len);
01310     }
01311     else {
01312         long alen;
01313 
01314         alen = RARRAY_LEN(ary) + rlen - len;
01315         if (alen >= ARY_CAPA(ary)) {
01316             ary_double_capa(ary, alen);
01317         }
01318 
01319         if (len != rlen) {
01320             MEMMOVE(RARRAY_PTR(ary) + beg + rlen, RARRAY_PTR(ary) + beg + len,
01321                     VALUE, RARRAY_LEN(ary) - (beg + len));
01322             ARY_SET_LEN(ary, alen);
01323         }
01324         if (rlen > 0) {
01325             MEMMOVE(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
01326         }
01327     }
01328 }
01329 
01338 VALUE
01339 rb_ary_resize(VALUE ary, long len)
01340 {
01341     long olen;
01342 
01343     rb_ary_modify(ary);
01344     olen = RARRAY_LEN(ary);
01345     if (len == olen) return ary;
01346     if (len > ARY_MAX_SIZE) {
01347         rb_raise(rb_eIndexError, "index %ld too big", len);
01348     }
01349     if (len > olen) {
01350         if (len >= ARY_CAPA(ary)) {
01351             ary_double_capa(ary, len);
01352         }
01353         rb_mem_clear(RARRAY_PTR(ary) + olen, len - olen);
01354         ARY_SET_LEN(ary, len);
01355     }
01356     else if (ARY_EMBED_P(ary)) {
01357         ARY_SET_EMBED_LEN(ary, len);
01358     }
01359     else if (len <= RARRAY_EMBED_LEN_MAX) {
01360         VALUE tmp[RARRAY_EMBED_LEN_MAX];
01361         MEMCPY(tmp, ARY_HEAP_PTR(ary), VALUE, len);
01362         ary_discard(ary);
01363         MEMCPY(ARY_EMBED_PTR(ary), tmp, VALUE, len);
01364         ARY_SET_EMBED_LEN(ary, len);
01365     }
01366     else {
01367         if (olen > len + ARY_DEFAULT_SIZE) {
01368             REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, len);
01369             ARY_SET_CAPA(ary, len);
01370         }
01371         ARY_SET_HEAP_LEN(ary, len);
01372     }
01373     return ary;
01374 }
01375 
01376 /*
01377  *  call-seq:
01378  *     ary[index]         = obj                      ->  obj
01379  *     ary[start, length] = obj or other_ary or nil  ->  obj or other_ary or nil
01380  *     ary[range]         = obj or other_ary or nil  ->  obj or other_ary or nil
01381  *
01382  *  Element Assignment---Sets the element at _index_,
01383  *  or replaces a subarray starting at _start_ and
01384  *  continuing for _length_ elements, or replaces a subarray
01385  *  specified by _range_.  If indices are greater than
01386  *  the current capacity of the array, the array grows
01387  *  automatically. A negative indices will count backward
01388  *  from the end of the array. Inserts elements if _length_ is
01389  *  zero. An +IndexError+ is raised if a negative index points
01390  *  past the beginning of the array. See also
01391  *  <code>Array#push</code>, and <code>Array#unshift</code>.
01392  *
01393  *     a = Array.new
01394  *     a[4] = "4";                 #=> [nil, nil, nil, nil, "4"]
01395  *     a[0, 3] = [ 'a', 'b', 'c' ] #=> ["a", "b", "c", nil, "4"]
01396  *     a[1..2] = [ 1, 2 ]          #=> ["a", 1, 2, nil, "4"]
01397  *     a[0, 2] = "?"               #=> ["?", 2, nil, "4"]
01398  *     a[0..2] = "A"               #=> ["A", "4"]
01399  *     a[-1]   = "Z"               #=> ["A", "Z"]
01400  *     a[1..-1] = nil              #=> ["A", nil]
01401  *     a[1..-1] = []               #=> ["A"]
01402  */
01403 
01404 static VALUE
01405 rb_ary_aset(int argc, VALUE *argv, VALUE ary)
01406 {
01407     long offset, beg, len;
01408 
01409     if (argc == 3) {
01410         rb_ary_modify_check(ary);
01411         beg = NUM2LONG(argv[0]);
01412         len = NUM2LONG(argv[1]);
01413         rb_ary_splice(ary, beg, len, argv[2]);
01414         return argv[2];
01415     }
01416     if (argc != 2) {
01417         rb_raise(rb_eArgError, "wrong number of arguments (%d for 2)", argc);
01418     }
01419     rb_ary_modify_check(ary);
01420     if (FIXNUM_P(argv[0])) {
01421         offset = FIX2LONG(argv[0]);
01422         goto fixnum;
01423     }
01424     if (rb_range_beg_len(argv[0], &beg, &len, RARRAY_LEN(ary), 1)) {
01425         /* check if idx is Range */
01426         rb_ary_splice(ary, beg, len, argv[1]);
01427         return argv[1];
01428     }
01429 
01430     offset = NUM2LONG(argv[0]);
01431 fixnum:
01432     rb_ary_store(ary, offset, argv[1]);
01433     return argv[1];
01434 }
01435 
01436 /*
01437  *  call-seq:
01438  *     ary.insert(index, obj...)  -> ary
01439  *
01440  *  Inserts the given values before the element with the given index
01441  *  (which may be negative).
01442  *
01443  *     a = %w{ a b c d }
01444  *     a.insert(2, 99)         #=> ["a", "b", 99, "c", "d"]
01445  *     a.insert(-2, 1, 2, 3)   #=> ["a", "b", 99, "c", 1, 2, 3, "d"]
01446  */
01447 
01448 static VALUE
01449 rb_ary_insert(int argc, VALUE *argv, VALUE ary)
01450 {
01451     long pos;
01452 
01453     if (argc < 1) {
01454         rb_raise(rb_eArgError, "wrong number of arguments (at least 1)");
01455     }
01456     rb_ary_modify_check(ary);
01457     if (argc == 1) return ary;
01458     pos = NUM2LONG(argv[0]);
01459     if (pos == -1) {
01460         pos = RARRAY_LEN(ary);
01461     }
01462     if (pos < 0) {
01463         pos++;
01464     }
01465     rb_ary_splice(ary, pos, 0, rb_ary_new4(argc - 1, argv + 1));
01466     return ary;
01467 }
01468 
01469 /*
01470  *  call-seq:
01471  *     ary.each {|item| block }   -> ary
01472  *     ary.each                   -> an_enumerator
01473  *
01474  *  Calls <i>block</i> once for each element in +self+, passing that
01475  *  element as a parameter.
01476  *
01477  *  If no block is given, an enumerator is returned instead.
01478  *
01479  *     a = [ "a", "b", "c" ]
01480  *     a.each {|x| print x, " -- " }
01481  *
01482  *  produces:
01483  *
01484  *     a -- b -- c --
01485  */
01486 
01487 VALUE
01488 rb_ary_each(VALUE array)
01489 {
01490     long i;
01491     volatile VALUE ary = array;
01492 
01493     RETURN_ENUMERATOR(ary, 0, 0);
01494     for (i=0; i<RARRAY_LEN(ary); i++) {
01495         rb_yield(RARRAY_PTR(ary)[i]);
01496     }
01497     return ary;
01498 }
01499 
01500 /*
01501  *  call-seq:
01502  *     ary.each_index {|index| block }  -> ary
01503  *     ary.each_index                   -> an_enumerator
01504  *
01505  *  Same as <code>Array#each</code>, but passes the index of the element
01506  *  instead of the element itself.
01507  *
01508  *  If no block is given, an enumerator is returned instead.
01509  *
01510  *
01511  *     a = [ "a", "b", "c" ]
01512  *     a.each_index {|x| print x, " -- " }
01513  *
01514  *  produces:
01515  *
01516  *     0 -- 1 -- 2 --
01517  */
01518 
01519 static VALUE
01520 rb_ary_each_index(VALUE ary)
01521 {
01522     long i;
01523     RETURN_ENUMERATOR(ary, 0, 0);
01524 
01525     for (i=0; i<RARRAY_LEN(ary); i++) {
01526         rb_yield(LONG2NUM(i));
01527     }
01528     return ary;
01529 }
01530 
01531 /*
01532  *  call-seq:
01533  *     ary.reverse_each {|item| block }   -> ary
01534  *     ary.reverse_each                   -> an_enumerator
01535  *
01536  *  Same as <code>Array#each</code>, but traverses +self+ in reverse
01537  *  order.
01538  *
01539  *     a = [ "a", "b", "c" ]
01540  *     a.reverse_each {|x| print x, " " }
01541  *
01542  *  produces:
01543  *
01544  *     c b a
01545  */
01546 
01547 static VALUE
01548 rb_ary_reverse_each(VALUE ary)
01549 {
01550     long len;
01551 
01552     RETURN_ENUMERATOR(ary, 0, 0);
01553     len = RARRAY_LEN(ary);
01554     while (len--) {
01555         rb_yield(RARRAY_PTR(ary)[len]);
01556         if (RARRAY_LEN(ary) < len) {
01557             len = RARRAY_LEN(ary);
01558         }
01559     }
01560     return ary;
01561 }
01562 
01563 /*
01564  *  call-seq:
01565  *     ary.length -> int
01566  *
01567  *  Returns the number of elements in +self+. May be zero.
01568  *
01569  *     [ 1, 2, 3, 4, 5 ].length   #=> 5
01570  */
01571 
01572 static VALUE
01573 rb_ary_length(VALUE ary)
01574 {
01575     long len = RARRAY_LEN(ary);
01576     return LONG2NUM(len);
01577 }
01578 
01579 /*
01580  *  call-seq:
01581  *     ary.empty?   -> true or false
01582  *
01583  *  Returns <code>true</code> if +self+ contains no elements.
01584  *
01585  *     [].empty?   #=> true
01586  */
01587 
01588 static VALUE
01589 rb_ary_empty_p(VALUE ary)
01590 {
01591     if (RARRAY_LEN(ary) == 0)
01592         return Qtrue;
01593     return Qfalse;
01594 }
01595 
01596 VALUE
01597 rb_ary_dup(VALUE ary)
01598 {
01599     VALUE dup = rb_ary_new2(RARRAY_LEN(ary));
01600     MEMCPY(RARRAY_PTR(dup), RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
01601     ARY_SET_LEN(dup, RARRAY_LEN(ary));
01602     return dup;
01603 }
01604 
01605 VALUE
01606 rb_ary_resurrect(VALUE ary)
01607 {
01608     return rb_ary_new4(RARRAY_LEN(ary), RARRAY_PTR(ary));
01609 }
01610 
01611 extern VALUE rb_output_fs;
01612 
01613 static void ary_join_1(VALUE obj, VALUE ary, VALUE sep, long i, VALUE result, int *first);
01614 
01615 static VALUE
01616 recursive_join(VALUE obj, VALUE argp, int recur)
01617 {
01618     VALUE *arg = (VALUE *)argp;
01619     VALUE ary = arg[0];
01620     VALUE sep = arg[1];
01621     VALUE result = arg[2];
01622     int *first = (int *)arg[3];
01623 
01624     if (recur) {
01625         rb_raise(rb_eArgError, "recursive array join");
01626     }
01627     else {
01628         ary_join_1(obj, ary, sep, 0, result, first);
01629     }
01630     return Qnil;
01631 }
01632 
01633 static void
01634 ary_join_0(VALUE ary, VALUE sep, long max, VALUE result)
01635 {
01636     long i;
01637     VALUE val;
01638 
01639     if (max > 0) rb_enc_copy(result, RARRAY_PTR(ary)[0]);
01640     for (i=0; i<max; i++) {
01641         val = RARRAY_PTR(ary)[i];
01642         if (i > 0 && !NIL_P(sep))
01643             rb_str_buf_append(result, sep);
01644         rb_str_buf_append(result, val);
01645         if (OBJ_TAINTED(val)) OBJ_TAINT(result);
01646         if (OBJ_UNTRUSTED(val)) OBJ_TAINT(result);
01647     }
01648 }
01649 
01650 static void
01651 ary_join_1(VALUE obj, VALUE ary, VALUE sep, long i, VALUE result, int *first)
01652 {
01653     VALUE val, tmp;
01654 
01655     for (; i<RARRAY_LEN(ary); i++) {
01656         if (i > 0 && !NIL_P(sep))
01657             rb_str_buf_append(result, sep);
01658 
01659         val = RARRAY_PTR(ary)[i];
01660         switch (TYPE(val)) {
01661           case T_STRING:
01662           str_join:
01663             rb_str_buf_append(result, val);
01664             *first = FALSE;
01665             break;
01666           case T_ARRAY:
01667             obj = val;
01668           ary_join:
01669             if (val == ary) {
01670                 rb_raise(rb_eArgError, "recursive array join");
01671             }
01672             else {
01673                 VALUE args[4];
01674 
01675                 args[0] = val;
01676                 args[1] = sep;
01677                 args[2] = result;
01678                 args[3] = (VALUE)first;
01679                 rb_exec_recursive(recursive_join, obj, (VALUE)args);
01680             }
01681             break;
01682           default:
01683             tmp = rb_check_string_type(val);
01684             if (!NIL_P(tmp)) {
01685                 val = tmp;
01686                 goto str_join;
01687             }
01688             tmp = rb_check_convert_type(val, T_ARRAY, "Array", "to_ary");
01689             if (!NIL_P(tmp)) {
01690                 obj = val;
01691                 val = tmp;
01692                 goto ary_join;
01693             }
01694             val = rb_obj_as_string(val);
01695             if (*first) {
01696                 rb_enc_copy(result, val);
01697                 *first = FALSE;
01698             }
01699             goto str_join;
01700         }
01701     }
01702 }
01703 
01704 VALUE
01705 rb_ary_join(VALUE ary, VALUE sep)
01706 {
01707     long len = 1, i;
01708     int taint = FALSE;
01709     int untrust = FALSE;
01710     VALUE val, tmp, result;
01711 
01712     if (RARRAY_LEN(ary) == 0) return rb_usascii_str_new(0, 0);
01713     if (OBJ_TAINTED(ary) || OBJ_TAINTED(sep)) taint = TRUE;
01714     if (OBJ_UNTRUSTED(ary) || OBJ_UNTRUSTED(sep)) untrust = TRUE;
01715 
01716     if (!NIL_P(sep)) {
01717         StringValue(sep);
01718         len += RSTRING_LEN(sep) * (RARRAY_LEN(ary) - 1);
01719     }
01720     for (i=0; i<RARRAY_LEN(ary); i++) {
01721         val = RARRAY_PTR(ary)[i];
01722         tmp = rb_check_string_type(val);
01723 
01724         if (NIL_P(tmp) || tmp != val) {
01725             int first;
01726             result = rb_str_buf_new(len + (RARRAY_LEN(ary)-i)*10);
01727             rb_enc_associate(result, rb_usascii_encoding());
01728             if (taint) OBJ_TAINT(result);
01729             if (untrust) OBJ_UNTRUST(result);
01730             ary_join_0(ary, sep, i, result);
01731             first = i == 0;
01732             ary_join_1(ary, ary, sep, i, result, &first);
01733             return result;
01734         }
01735 
01736         len += RSTRING_LEN(tmp);
01737     }
01738 
01739     result = rb_str_buf_new(len);
01740     if (taint) OBJ_TAINT(result);
01741     if (untrust) OBJ_UNTRUST(result);
01742     ary_join_0(ary, sep, RARRAY_LEN(ary), result);
01743 
01744     return result;
01745 }
01746 
01747 /*
01748  *  call-seq:
01749  *     ary.join(sep=$,)    -> str
01750  *
01751  *  Returns a string created by converting each element of the array to
01752  *  a string, separated by <i>sep</i>.
01753  *
01754  *     [ "a", "b", "c" ].join        #=> "abc"
01755  *     [ "a", "b", "c" ].join("-")   #=> "a-b-c"
01756  */
01757 
01758 static VALUE
01759 rb_ary_join_m(int argc, VALUE *argv, VALUE ary)
01760 {
01761     VALUE sep;
01762 
01763     rb_scan_args(argc, argv, "01", &sep);
01764     if (NIL_P(sep)) sep = rb_output_fs;
01765 
01766     return rb_ary_join(ary, sep);
01767 }
01768 
01769 static VALUE
01770 inspect_ary(VALUE ary, VALUE dummy, int recur)
01771 {
01772     int tainted = OBJ_TAINTED(ary);
01773     int untrust = OBJ_UNTRUSTED(ary);
01774     long i;
01775     VALUE s, str;
01776 
01777     if (recur) return rb_usascii_str_new_cstr("[...]");
01778     str = rb_str_buf_new2("[");
01779     for (i=0; i<RARRAY_LEN(ary); i++) {
01780         s = rb_inspect(RARRAY_PTR(ary)[i]);
01781         if (OBJ_TAINTED(s)) tainted = TRUE;
01782         if (OBJ_UNTRUSTED(s)) untrust = TRUE;
01783         if (i > 0) rb_str_buf_cat2(str, ", ");
01784         else rb_enc_copy(str, s);
01785         rb_str_buf_append(str, s);
01786     }
01787     rb_str_buf_cat2(str, "]");
01788     if (tainted) OBJ_TAINT(str);
01789     if (untrust) OBJ_UNTRUST(str);
01790     return str;
01791 }
01792 
01793 /*
01794  *  call-seq:
01795  *     ary.to_s -> string
01796  *     ary.inspect  -> string
01797  *
01798  *  Creates a string representation of +self+.
01799  */
01800 
01801 static VALUE
01802 rb_ary_inspect(VALUE ary)
01803 {
01804     if (RARRAY_LEN(ary) == 0) return rb_usascii_str_new2("[]");
01805     return rb_exec_recursive(inspect_ary, ary, 0);
01806 }
01807 
01808 VALUE
01809 rb_ary_to_s(VALUE ary)
01810 {
01811     return rb_ary_inspect(ary);
01812 }
01813 
01814 /*
01815  *  call-seq:
01816  *     ary.to_a     -> ary
01817  *
01818  *  Returns +self+. If called on a subclass of Array, converts
01819  *  the receiver to an Array object.
01820  */
01821 
01822 static VALUE
01823 rb_ary_to_a(VALUE ary)
01824 {
01825     if (rb_obj_class(ary) != rb_cArray) {
01826         VALUE dup = rb_ary_new2(RARRAY_LEN(ary));
01827         rb_ary_replace(dup, ary);
01828         return dup;
01829     }
01830     return ary;
01831 }
01832 
01833 /*
01834  *  call-seq:
01835  *     ary.to_ary -> ary
01836  *
01837  *  Returns +self+.
01838  */
01839 
01840 static VALUE
01841 rb_ary_to_ary_m(VALUE ary)
01842 {
01843     return ary;
01844 }
01845 
01846 static void
01847 ary_reverse(p1, p2)
01848     VALUE *p1, *p2;
01849 {
01850     while (p1 < p2) {
01851         VALUE tmp = *p1;
01852         *p1++ = *p2;
01853         *p2-- = tmp;
01854     }
01855 }
01856 
01857 VALUE
01858 rb_ary_reverse(VALUE ary)
01859 {
01860     VALUE *p1, *p2;
01861 
01862     rb_ary_modify(ary);
01863     if (RARRAY_LEN(ary) > 1) {
01864         p1 = RARRAY_PTR(ary);
01865         p2 = p1 + RARRAY_LEN(ary) - 1;  /* points last item */
01866         ary_reverse(p1, p2);
01867     }
01868     return ary;
01869 }
01870 
01871 /*
01872  *  call-seq:
01873  *     ary.reverse!   -> ary
01874  *
01875  *  Reverses +self+ in place.
01876  *
01877  *     a = [ "a", "b", "c" ]
01878  *     a.reverse!       #=> ["c", "b", "a"]
01879  *     a                #=> ["c", "b", "a"]
01880  */
01881 
01882 static VALUE
01883 rb_ary_reverse_bang(VALUE ary)
01884 {
01885     return rb_ary_reverse(ary);
01886 }
01887 
01888 /*
01889  *  call-seq:
01890  *     ary.reverse -> new_ary
01891  *
01892  *  Returns a new array containing +self+'s elements in reverse order.
01893  *
01894  *     [ "a", "b", "c" ].reverse   #=> ["c", "b", "a"]
01895  *     [ 1 ].reverse               #=> [1]
01896  */
01897 
01898 static VALUE
01899 rb_ary_reverse_m(VALUE ary)
01900 {
01901     long len = RARRAY_LEN(ary);
01902     VALUE dup = rb_ary_new2(len);
01903 
01904     if (len > 0) {
01905         VALUE *p1 = RARRAY_PTR(ary);
01906         VALUE *p2 = RARRAY_PTR(dup) + len - 1;
01907         do *p2-- = *p1++; while (--len > 0);
01908     }
01909     ARY_SET_LEN(dup, RARRAY_LEN(ary));
01910     return dup;
01911 }
01912 
01913 static inline long
01914 rotate_count(long cnt, long len)
01915 {
01916     return (cnt < 0) ? (len - (~cnt % len) - 1) : (cnt % len);
01917 }
01918 
01919 VALUE
01920 rb_ary_rotate(VALUE ary, long cnt)
01921 {
01922     rb_ary_modify(ary);
01923 
01924     if (cnt != 0) {
01925         VALUE *ptr = RARRAY_PTR(ary);
01926         long len = RARRAY_LEN(ary);
01927 
01928         if (len > 0 && (cnt = rotate_count(cnt, len)) > 0) {
01929             --len;
01930             if (cnt < len) ary_reverse(ptr + cnt, ptr + len);
01931             if (--cnt > 0) ary_reverse(ptr, ptr + cnt);
01932             if (len > 0) ary_reverse(ptr, ptr + len);
01933             return ary;
01934         }
01935     }
01936 
01937     return Qnil;
01938 }
01939 
01940 /*
01941  *  call-seq:
01942  *     ary.rotate!(cnt=1) -> ary
01943  *
01944  *  Rotates +self+ in place so that the element at +cnt+ comes first,
01945  *  and returns +self+.  If +cnt+ is negative then it rotates in
01946  *  the opposite direction.
01947  *
01948  *     a = [ "a", "b", "c", "d" ]
01949  *     a.rotate!        #=> ["b", "c", "d", "a"]
01950  *     a                #=> ["b", "c", "d", "a"]
01951  *     a.rotate!(2)     #=> ["d", "a", "b", "c"]
01952  *     a.rotate!(-3)    #=> ["a", "b", "c", "d"]
01953  */
01954 
01955 static VALUE
01956 rb_ary_rotate_bang(int argc, VALUE *argv, VALUE ary)
01957 {
01958     long n = 1;
01959 
01960     switch (argc) {
01961       case 1: n = NUM2LONG(argv[0]);
01962       case 0: break;
01963       default: rb_scan_args(argc, argv, "01", NULL);
01964     }
01965     rb_ary_rotate(ary, n);
01966     return ary;
01967 }
01968 
01969 /*
01970  *  call-seq:
01971  *     ary.rotate(cnt=1) -> new_ary
01972  *
01973  *  Returns new array by rotating +self+ so that the element at
01974  *  +cnt+ in +self+ is the first element of the new array. If +cnt+
01975  *  is negative then it rotates in the opposite direction.
01976  *
01977  *     a = [ "a", "b", "c", "d" ]
01978  *     a.rotate         #=> ["b", "c", "d", "a"]
01979  *     a                #=> ["a", "b", "c", "d"]
01980  *     a.rotate(2)      #=> ["c", "d", "a", "b"]
01981  *     a.rotate(-3)     #=> ["b", "c", "d", "a"]
01982  */
01983 
01984 static VALUE
01985 rb_ary_rotate_m(int argc, VALUE *argv, VALUE ary)
01986 {
01987     VALUE rotated, *ptr, *ptr2;
01988     long len, cnt = 1;
01989 
01990     switch (argc) {
01991       case 1: cnt = NUM2LONG(argv[0]);
01992       case 0: break;
01993       default: rb_scan_args(argc, argv, "01", NULL);
01994     }
01995 
01996     len = RARRAY_LEN(ary);
01997     rotated = rb_ary_new2(len);
01998     if (len > 0) {
01999         cnt = rotate_count(cnt, len);
02000         ptr = RARRAY_PTR(ary);
02001         ptr2 = RARRAY_PTR(rotated);
02002         len -= cnt;
02003         MEMCPY(ptr2, ptr + cnt, VALUE, len);
02004         MEMCPY(ptr2 + len, ptr, VALUE, cnt);
02005     }
02006     ARY_SET_LEN(rotated, RARRAY_LEN(ary));
02007     return rotated;
02008 }
02009 
02010 struct ary_sort_data {
02011     VALUE ary;
02012     int opt_methods;
02013     int opt_inited;
02014 };
02015 
02016 enum {
02017     sort_opt_Fixnum,
02018     sort_opt_String,
02019     sort_optimizable_count
02020 };
02021 
02022 #define STRING_P(s) (TYPE(s) == T_STRING && CLASS_OF(s) == rb_cString)
02023 
02024 #define SORT_OPTIMIZABLE_BIT(type) (1U << TOKEN_PASTE(sort_opt_,type))
02025 #define SORT_OPTIMIZABLE(data, type) \
02026     (((data)->opt_inited & SORT_OPTIMIZABLE_BIT(type)) ? \
02027      ((data)->opt_methods & SORT_OPTIMIZABLE_BIT(type)) : \
02028      (((data)->opt_inited |= SORT_OPTIMIZABLE_BIT(type)), \
02029       rb_method_basic_definition_p(TOKEN_PASTE(rb_c,type), id_cmp) && \
02030       ((data)->opt_methods |= SORT_OPTIMIZABLE_BIT(type))))
02031 
02032 static VALUE
02033 sort_reentered(VALUE ary)
02034 {
02035     if (RBASIC(ary)->klass) {
02036         rb_raise(rb_eRuntimeError, "sort reentered");
02037     }
02038     return Qnil;
02039 }
02040 
02041 static int
02042 sort_1(const void *ap, const void *bp, void *dummy)
02043 {
02044     struct ary_sort_data *data = dummy;
02045     VALUE retval = sort_reentered(data->ary);
02046     VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp;
02047     int n;
02048 
02049     retval = rb_yield_values(2, a, b);
02050     n = rb_cmpint(retval, a, b);
02051     sort_reentered(data->ary);
02052     return n;
02053 }
02054 
02055 static int
02056 sort_2(const void *ap, const void *bp, void *dummy)
02057 {
02058     struct ary_sort_data *data = dummy;
02059     VALUE retval = sort_reentered(data->ary);
02060     VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp;
02061     int n;
02062 
02063     if (FIXNUM_P(a) && FIXNUM_P(b) && SORT_OPTIMIZABLE(data, Fixnum)) {
02064         if ((long)a > (long)b) return 1;
02065         if ((long)a < (long)b) return -1;
02066         return 0;
02067     }
02068     if (STRING_P(a) && STRING_P(b) && SORT_OPTIMIZABLE(data, String)) {
02069         return rb_str_cmp(a, b);
02070     }
02071 
02072     retval = rb_funcall(a, id_cmp, 1, b);
02073     n = rb_cmpint(retval, a, b);
02074     sort_reentered(data->ary);
02075 
02076     return n;
02077 }
02078 
02079 /*
02080  *  call-seq:
02081  *     ary.sort!                   -> ary
02082  *     ary.sort! {| a,b | block }  -> ary
02083  *
02084  *  Sorts +self+. Comparisons for
02085  *  the sort will be done using the <code><=></code> operator or using
02086  *  an optional code block. The block implements a comparison between
02087  *  <i>a</i> and <i>b</i>, returning -1, 0, or +1. See also
02088  *  <code>Enumerable#sort_by</code>.
02089  *
02090  *     a = [ "d", "a", "e", "c", "b" ]
02091  *     a.sort!                    #=> ["a", "b", "c", "d", "e"]
02092  *     a.sort! {|x,y| y <=> x }   #=> ["e", "d", "c", "b", "a"]
02093  */
02094 
02095 VALUE
02096 rb_ary_sort_bang(VALUE ary)
02097 {
02098     rb_ary_modify(ary);
02099     assert(!ARY_SHARED_P(ary));
02100     if (RARRAY_LEN(ary) > 1) {
02101         VALUE tmp = ary_make_substitution(ary); /* only ary refers tmp */
02102         struct ary_sort_data data;
02103 
02104         RBASIC(tmp)->klass = 0;
02105         data.ary = tmp;
02106         data.opt_methods = 0;
02107         data.opt_inited = 0;
02108         ruby_qsort(RARRAY_PTR(tmp), RARRAY_LEN(tmp), sizeof(VALUE),
02109                    rb_block_given_p()?sort_1:sort_2, &data);
02110 
02111         if (ARY_EMBED_P(tmp)) {
02112             assert(ARY_EMBED_P(tmp));
02113             if (ARY_SHARED_P(ary)) { /* ary might be destructively operated in the given block */
02114                 rb_ary_unshare(ary);
02115             }
02116             FL_SET_EMBED(ary);
02117             MEMCPY(RARRAY_PTR(ary), ARY_EMBED_PTR(tmp), VALUE, ARY_EMBED_LEN(tmp));
02118             ARY_SET_LEN(ary, ARY_EMBED_LEN(tmp));
02119         }
02120         else {
02121             assert(!ARY_EMBED_P(tmp));
02122             if (ARY_HEAP_PTR(ary) == ARY_HEAP_PTR(tmp)) {
02123                 assert(!ARY_EMBED_P(ary));
02124                 FL_UNSET_SHARED(ary);
02125                 ARY_SET_CAPA(ary, ARY_CAPA(tmp));
02126             }
02127             else {
02128                 assert(!ARY_SHARED_P(tmp));
02129                 if (ARY_EMBED_P(ary)) {
02130                     FL_UNSET_EMBED(ary);
02131                 }
02132                 else if (ARY_SHARED_P(ary)) {
02133                     /* ary might be destructively operated in the given block */
02134                     rb_ary_unshare(ary);
02135                 }
02136                 else {
02137                     xfree(ARY_HEAP_PTR(ary));
02138                 }
02139                 ARY_SET_PTR(ary, RARRAY_PTR(tmp));
02140                 ARY_SET_HEAP_LEN(ary, RARRAY_LEN(tmp));
02141                 ARY_SET_CAPA(ary, ARY_CAPA(tmp));
02142             }
02143             /* tmp was lost ownership for the ptr */
02144             FL_UNSET(tmp, FL_FREEZE);
02145             FL_SET_EMBED(tmp);
02146             ARY_SET_EMBED_LEN(tmp, 0);
02147             FL_SET(tmp, FL_FREEZE);
02148         }
02149         /* tmp will be GC'ed. */
02150         RBASIC(tmp)->klass = rb_cArray;
02151     }
02152     return ary;
02153 }
02154 
02155 /*
02156  *  call-seq:
02157  *     ary.sort                   -> new_ary
02158  *     ary.sort {| a,b | block }  -> new_ary
02159  *
02160  *  Returns a new array created by sorting +self+. Comparisons for
02161  *  the sort will be done using the <code><=></code> operator or using
02162  *  an optional code block. The block implements a comparison between
02163  *  <i>a</i> and <i>b</i>, returning -1, 0, or +1. See also
02164  *  <code>Enumerable#sort_by</code>.
02165  *
02166  *     a = [ "d", "a", "e", "c", "b" ]
02167  *     a.sort                    #=> ["a", "b", "c", "d", "e"]
02168  *     a.sort {|x,y| y <=> x }   #=> ["e", "d", "c", "b", "a"]
02169  */
02170 
02171 VALUE
02172 rb_ary_sort(VALUE ary)
02173 {
02174     ary = rb_ary_dup(ary);
02175     rb_ary_sort_bang(ary);
02176     return ary;
02177 }
02178 
02179 
02180 static VALUE
02181 sort_by_i(VALUE i)
02182 {
02183     return rb_yield(i);
02184 }
02185 
02186 /*
02187  *  call-seq:
02188  *     ary.sort_by! {| obj | block }    -> ary
02189  *     ary.sort_by!                     -> an_enumerator
02190  *
02191  *  Sorts +self+ in place using a set of keys generated by mapping the
02192  *  values in +self+ through the given block.
02193  *
02194  *  If no block is given, an enumerator is returned instead.
02195  *
02196  */
02197 
02198 static VALUE
02199 rb_ary_sort_by_bang(VALUE ary)
02200 {
02201     VALUE sorted;
02202 
02203     RETURN_ENUMERATOR(ary, 0, 0);
02204     rb_ary_modify(ary);
02205     sorted = rb_block_call(ary, rb_intern("sort_by"), 0, 0, sort_by_i, 0);
02206     rb_ary_replace(ary, sorted);
02207     return ary;
02208 }
02209 
02210 
02211 /*
02212  *  call-seq:
02213  *     ary.collect {|item| block }  -> new_ary
02214  *     ary.map     {|item| block }  -> new_ary
02215  *     ary.collect                  -> an_enumerator
02216  *     ary.map                      -> an_enumerator
02217  *
02218  *  Invokes <i>block</i> once for each element of +self+. Creates a
02219  *  new array containing the values returned by the block.
02220  *  See also <code>Enumerable#collect</code>.
02221  *
02222  *  If no block is given, an enumerator is returned instead.
02223  *
02224  *     a = [ "a", "b", "c", "d" ]
02225  *     a.collect {|x| x + "!" }   #=> ["a!", "b!", "c!", "d!"]
02226  *     a                          #=> ["a", "b", "c", "d"]
02227  */
02228 
02229 static VALUE
02230 rb_ary_collect(VALUE ary)
02231 {
02232     long i;
02233     VALUE collect;
02234 
02235     RETURN_ENUMERATOR(ary, 0, 0);
02236     collect = rb_ary_new2(RARRAY_LEN(ary));
02237     for (i = 0; i < RARRAY_LEN(ary); i++) {
02238         rb_ary_push(collect, rb_yield(RARRAY_PTR(ary)[i]));
02239     }
02240     return collect;
02241 }
02242 
02243 
02244 /*
02245  *  call-seq:
02246  *     ary.collect! {|item| block }   -> ary
02247  *     ary.map!     {|item| block }   -> ary
02248  *     ary.collect                    -> an_enumerator
02249  *     ary.map                        -> an_enumerator
02250  *
02251  *  Invokes the block once for each element of +self+, replacing the
02252  *  element with the value returned by _block_.
02253  *  See also <code>Enumerable#collect</code>.
02254  *
02255  *  If no block is given, an enumerator is returned instead.
02256  *
02257  *     a = [ "a", "b", "c", "d" ]
02258  *     a.collect! {|x| x + "!" }
02259  *     a             #=>  [ "a!", "b!", "c!", "d!" ]
02260  */
02261 
02262 static VALUE
02263 rb_ary_collect_bang(VALUE ary)
02264 {
02265     long i;
02266 
02267     RETURN_ENUMERATOR(ary, 0, 0);
02268     rb_ary_modify(ary);
02269     for (i = 0; i < RARRAY_LEN(ary); i++) {
02270         rb_ary_store(ary, i, rb_yield(RARRAY_PTR(ary)[i]));
02271     }
02272     return ary;
02273 }
02274 
02275 VALUE
02276 rb_get_values_at(VALUE obj, long olen, int argc, VALUE *argv, VALUE (*func) (VALUE, long))
02277 {
02278     VALUE result = rb_ary_new2(argc);
02279     long beg, len, i, j;
02280 
02281     for (i=0; i<argc; i++) {
02282         if (FIXNUM_P(argv[i])) {
02283             rb_ary_push(result, (*func)(obj, FIX2LONG(argv[i])));
02284             continue;
02285         }
02286         /* check if idx is Range */
02287         switch (rb_range_beg_len(argv[i], &beg, &len, olen, 0)) {
02288           case Qfalse:
02289             break;
02290           case Qnil:
02291             continue;
02292           default:
02293             for (j=0; j<len; j++) {
02294                 rb_ary_push(result, (*func)(obj, j+beg));
02295             }
02296             continue;
02297         }
02298         rb_ary_push(result, (*func)(obj, NUM2LONG(argv[i])));
02299     }
02300     return result;
02301 }
02302 
02303 /*
02304  *  call-seq:
02305  *     ary.values_at(selector,... )  -> new_ary
02306  *
02307  *  Returns an array containing the elements in
02308  *  +self+ corresponding to the given selector(s). The selectors
02309  *  may be either integer indices or ranges.
02310  *  See also <code>Array#select</code>.
02311  *
02312  *     a = %w{ a b c d e f }
02313  *     a.values_at(1, 3, 5)
02314  *     a.values_at(1, 3, 5, 7)
02315  *     a.values_at(-1, -3, -5, -7)
02316  *     a.values_at(1..3, 2...5)
02317  */
02318 
02319 static VALUE
02320 rb_ary_values_at(int argc, VALUE *argv, VALUE ary)
02321 {
02322     return rb_get_values_at(ary, RARRAY_LEN(ary), argc, argv, rb_ary_entry);
02323 }
02324 
02325 
02326 /*
02327  *  call-seq:
02328  *     ary.select {|item| block } -> new_ary
02329  *     ary.select                 -> an_enumerator
02330  *
02331  *  Invokes the block passing in successive elements from +self+,
02332  *  returning an array containing those elements for which the block
02333  *  returns a true value (equivalent to <code>Enumerable#select</code>).
02334  *
02335  *  If no block is given, an enumerator is returned instead.
02336  *
02337  *     a = %w{ a b c d e f }
02338  *     a.select {|v| v =~ /[aeiou]/}   #=> ["a", "e"]
02339  */
02340 
02341 static VALUE
02342 rb_ary_select(VALUE ary)
02343 {
02344     VALUE result;
02345     long i;
02346 
02347     RETURN_ENUMERATOR(ary, 0, 0);
02348     result = rb_ary_new2(RARRAY_LEN(ary));
02349     for (i = 0; i < RARRAY_LEN(ary); i++) {
02350         if (RTEST(rb_yield(RARRAY_PTR(ary)[i]))) {
02351             rb_ary_push(result, rb_ary_elt(ary, i));
02352         }
02353     }
02354     return result;
02355 }
02356 
02357 /*
02358  *  call-seq:
02359  *     ary.select! {|item| block } -> ary or nil
02360  *     ary.select!                 -> an_enumerator
02361  *
02362  *  Invokes the block passing in successive elements from
02363  *  +self+, deleting elements for which the block returns a
02364  *  false value. It returns +self+ if changes were made,
02365  *  otherwise it returns <code>nil</code>.
02366  *  See also <code>Array#keep_if</code>
02367  *
02368  *  If no block is given, an enumerator is returned instead.
02369  *
02370  */
02371 
02372 static VALUE
02373 rb_ary_select_bang(VALUE ary)
02374 {
02375     long i1, i2;
02376 
02377     RETURN_ENUMERATOR(ary, 0, 0);
02378     rb_ary_modify(ary);
02379     for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
02380         VALUE v = RARRAY_PTR(ary)[i1];
02381         if (!RTEST(rb_yield(v))) continue;
02382         if (i1 != i2) {
02383             rb_ary_store(ary, i2, v);
02384         }
02385         i2++;
02386     }
02387 
02388     if (RARRAY_LEN(ary) == i2) return Qnil;
02389     if (i2 < RARRAY_LEN(ary))
02390         ARY_SET_LEN(ary, i2);
02391     return ary;
02392 }
02393 
02394 /*
02395  *  call-seq:
02396  *     ary.keep_if {|item| block } -> ary
02397  *     ary.keep_if                 -> an_enumerator
02398  *
02399  *  Deletes every element of +self+ for which <i>block</i> evaluates
02400  *  to false.
02401  *  See also <code>Array#select!</code>
02402  *
02403  *  If no block is given, an enumerator is returned instead.
02404  *
02405  *     a = %w{ a b c d e f }
02406  *     a.keep_if {|v| v =~ /[aeiou]/}   #=> ["a", "e"]
02407  */
02408 
02409 static VALUE
02410 rb_ary_keep_if(VALUE ary)
02411 {
02412     RETURN_ENUMERATOR(ary, 0, 0);
02413     rb_ary_select_bang(ary);
02414     return ary;
02415 }
02416 
02417 /*
02418  *  call-seq:
02419  *     ary.delete(obj)            -> obj or nil
02420  *     ary.delete(obj) { block }  -> obj or nil
02421  *
02422  *  Deletes items from +self+ that are equal to <i>obj</i>.
02423  *  If any items are found, returns <i>obj</i>.   If
02424  *  the item is not found, returns <code>nil</code>. If the optional
02425  *  code block is given, returns the result of <i>block</i> if the item
02426  *  is not found.  (To remove <code>nil</code> elements and
02427  *  get an informative return value, use #compact!)
02428  *
02429  *     a = [ "a", "b", "b", "b", "c" ]
02430  *     a.delete("b")                   #=> "b"
02431  *     a                               #=> ["a", "c"]
02432  *     a.delete("z")                   #=> nil
02433  *     a.delete("z") { "not found" }   #=> "not found"
02434  */
02435 
02436 VALUE
02437 rb_ary_delete(VALUE ary, VALUE item)
02438 {
02439     VALUE v = item;
02440     long i1, i2;
02441 
02442     for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
02443         VALUE e = RARRAY_PTR(ary)[i1];
02444 
02445         if (rb_equal(e, item)) {
02446             v = e;
02447             continue;
02448         }
02449         if (i1 != i2) {
02450             rb_ary_store(ary, i2, e);
02451         }
02452         i2++;
02453     }
02454     if (RARRAY_LEN(ary) == i2) {
02455         if (rb_block_given_p()) {
02456             return rb_yield(item);
02457         }
02458         return Qnil;
02459     }
02460 
02461     rb_ary_modify(ary);
02462     if (RARRAY_LEN(ary) > i2) {
02463         ARY_SET_LEN(ary, i2);
02464         if (i2 * 2 < ARY_CAPA(ary) &&
02465             ARY_CAPA(ary) > ARY_DEFAULT_SIZE) {
02466             ary_resize_capa(ary, i2*2);
02467         }
02468     }
02469 
02470     return v;
02471 }
02472 
02473 VALUE
02474 rb_ary_delete_at(VALUE ary, long pos)
02475 {
02476     long len = RARRAY_LEN(ary);
02477     VALUE del;
02478 
02479     if (pos >= len) return Qnil;
02480     if (pos < 0) {
02481         pos += len;
02482         if (pos < 0) return Qnil;
02483     }
02484 
02485     rb_ary_modify(ary);
02486     del = RARRAY_PTR(ary)[pos];
02487     MEMMOVE(RARRAY_PTR(ary)+pos, RARRAY_PTR(ary)+pos+1, VALUE,
02488             RARRAY_LEN(ary)-pos-1);
02489     ARY_INCREASE_LEN(ary, -1);
02490 
02491     return del;
02492 }
02493 
02494 /*
02495  *  call-seq:
02496  *     ary.delete_at(index)  -> obj or nil
02497  *
02498  *  Deletes the element at the specified index, returning that element,
02499  *  or <code>nil</code> if the index is out of range. See also
02500  *  <code>Array#slice!</code>.
02501  *
02502  *     a = %w( ant bat cat dog )
02503  *     a.delete_at(2)    #=> "cat"
02504  *     a                 #=> ["ant", "bat", "dog"]
02505  *     a.delete_at(99)   #=> nil
02506  */
02507 
02508 static VALUE
02509 rb_ary_delete_at_m(VALUE ary, VALUE pos)
02510 {
02511     return rb_ary_delete_at(ary, NUM2LONG(pos));
02512 }
02513 
02514 /*
02515  *  call-seq:
02516  *     ary.slice!(index)         -> obj or nil
02517  *     ary.slice!(start, length) -> new_ary or nil
02518  *     ary.slice!(range)         -> new_ary or nil
02519  *
02520  *  Deletes the element(s) given by an index (optionally with a length)
02521  *  or by a range. Returns the deleted object (or objects), or
02522  *  <code>nil</code> if the index is out of range.
02523  *
02524  *     a = [ "a", "b", "c" ]
02525  *     a.slice!(1)     #=> "b"
02526  *     a               #=> ["a", "c"]
02527  *     a.slice!(-1)    #=> "c"
02528  *     a               #=> ["a"]
02529  *     a.slice!(100)   #=> nil
02530  *     a               #=> ["a"]
02531  */
02532 
02533 static VALUE
02534 rb_ary_slice_bang(int argc, VALUE *argv, VALUE ary)
02535 {
02536     VALUE arg1, arg2;
02537     long pos, len, orig_len;
02538 
02539     rb_ary_modify_check(ary);
02540     if (argc == 2) {
02541         pos = NUM2LONG(argv[0]);
02542         len = NUM2LONG(argv[1]);
02543       delete_pos_len:
02544         if (len < 0) return Qnil;
02545         orig_len = RARRAY_LEN(ary);
02546         if (pos < 0) {
02547             pos += orig_len;
02548             if (pos < 0) return Qnil;
02549         }
02550         else if (orig_len < pos) return Qnil;
02551         if (orig_len < pos + len) {
02552             len = orig_len - pos;
02553         }
02554         if (len == 0) return rb_ary_new2(0);
02555         arg2 = rb_ary_new4(len, RARRAY_PTR(ary)+pos);
02556         RBASIC(arg2)->klass = rb_obj_class(ary);
02557         rb_ary_splice(ary, pos, len, Qundef);
02558         return arg2;
02559     }
02560 
02561     if (argc != 1) {
02562         /* error report */
02563         rb_scan_args(argc, argv, "11", NULL, NULL);
02564     }
02565     arg1 = argv[0];
02566 
02567     if (!FIXNUM_P(arg1)) {
02568         switch (rb_range_beg_len(arg1, &pos, &len, RARRAY_LEN(ary), 0)) {
02569           case Qtrue:
02570             /* valid range */
02571             goto delete_pos_len;
02572           case Qnil:
02573             /* invalid range */
02574             return Qnil;
02575           default:
02576             /* not a range */
02577             break;
02578         }
02579     }
02580 
02581     return rb_ary_delete_at(ary, NUM2LONG(arg1));
02582 }
02583 
02584 static VALUE
02585 ary_reject(VALUE orig, VALUE result)
02586 {
02587     long i;
02588 
02589     for (i = 0; i < RARRAY_LEN(orig); i++) {
02590         VALUE v = RARRAY_PTR(orig)[i];
02591         if (!RTEST(rb_yield(v))) {
02592             rb_ary_push_1(result, v);
02593         }
02594     }
02595     return result;
02596 }
02597 
02598 static VALUE
02599 ary_reject_bang(VALUE ary)
02600 {
02601     long i;
02602     VALUE result = Qnil;
02603 
02604     rb_ary_modify_check(ary);
02605     for (i = 0; i < RARRAY_LEN(ary); ) {
02606         VALUE v = RARRAY_PTR(ary)[i];
02607         if (RTEST(rb_yield(v))) {
02608             rb_ary_delete_at(ary, i);
02609             result = ary;
02610         }
02611         else {
02612             i++;
02613         }
02614     }
02615     return result;
02616 }
02617 
02618 /*
02619  *  call-seq:
02620  *     ary.reject! {|item| block }  -> ary or nil
02621  *     ary.reject!                  -> an_enumerator
02622  *
02623  *  Equivalent to <code>Array#delete_if</code>, deleting elements from
02624  *  +self+ for which the block evaluates to true, but returns
02625  *  <code>nil</code> if no changes were made.
02626  *  The array is changed instantly every time the block is called and
02627  *  not after the iteration is over.
02628  *  See also <code>Enumerable#reject</code> and <code>Array#delete_if</code>.
02629  *
02630  *  If no block is given, an enumerator is returned instead.
02631  *
02632  */
02633 
02634 static VALUE
02635 rb_ary_reject_bang(VALUE ary)
02636 {
02637     RETURN_ENUMERATOR(ary, 0, 0);
02638     return ary_reject_bang(ary);
02639 }
02640 
02641 /*
02642  *  call-seq:
02643  *     ary.reject {|item| block }  -> new_ary
02644  *     ary.reject                  -> an_enumerator
02645  *
02646  *  Returns a new array containing the items in +self+
02647  *  for which the block is not true.
02648  *  See also <code>Array#delete_if</code>
02649  *
02650  *  If no block is given, an enumerator is returned instead.
02651  *
02652  */
02653 
02654 static VALUE
02655 rb_ary_reject(VALUE ary)
02656 {
02657     VALUE rejected_ary;
02658 
02659     RETURN_ENUMERATOR(ary, 0, 0);
02660     rejected_ary = rb_ary_new();
02661     ary_reject(ary, rejected_ary);
02662     return rejected_ary;
02663 }
02664 
02665 /*
02666  *  call-seq:
02667  *     ary.delete_if {|item| block }  -> ary
02668  *     ary.delete_if                  -> an_enumerator
02669  *
02670  *  Deletes every element of +self+ for which <i>block</i> evaluates
02671  *  to true.
02672  *  The array is changed instantly every time the block is called and
02673  *  not after the iteration is over.
02674  *  See also <code>Array#reject!</code>
02675  *
02676  *  If no block is given, an enumerator is returned instead.
02677  *
02678  *     a = [ "a", "b", "c" ]
02679  *     a.delete_if {|x| x >= "b" }   #=> ["a"]
02680  */
02681 
02682 static VALUE
02683 rb_ary_delete_if(VALUE ary)
02684 {
02685     RETURN_ENUMERATOR(ary, 0, 0);
02686     ary_reject_bang(ary);
02687     return ary;
02688 }
02689 
02690 static VALUE
02691 take_i(VALUE val, VALUE *args, int argc, VALUE *argv)
02692 {
02693     if (args[1]-- == 0) rb_iter_break();
02694     if (argc > 1) val = rb_ary_new4(argc, argv);
02695     rb_ary_push(args[0], val);
02696     return Qnil;
02697 }
02698 
02699 static VALUE
02700 take_items(VALUE obj, long n)
02701 {
02702     VALUE result = rb_check_array_type(obj);
02703     VALUE args[2];
02704 
02705     if (!NIL_P(result)) return rb_ary_subseq(result, 0, n);
02706     result = rb_ary_new2(n);
02707     args[0] = result; args[1] = (VALUE)n;
02708     rb_block_call(obj, rb_intern("each"), 0, 0, take_i, (VALUE)args);
02709     return result;
02710 }
02711 
02712 
02713 /*
02714  *  call-seq:
02715  *     ary.zip(arg, ...)                   -> new_ary
02716  *     ary.zip(arg, ...) {| arr | block }  -> nil
02717  *
02718  *  Converts any arguments to arrays, then merges elements of
02719  *  +self+ with corresponding elements from each argument. This
02720  *  generates a sequence of <code>self.size</code> <em>n</em>-element
02721  *  arrays, where <em>n</em> is one more that the count of arguments. If
02722  *  the size of any argument is less than <code>enumObj.size</code>,
02723  *  <code>nil</code> values are supplied. If a block is given, it is
02724  *  invoked for each output array, otherwise an array of arrays is
02725  *  returned.
02726  *
02727  *     a = [ 4, 5, 6 ]
02728  *     b = [ 7, 8, 9 ]
02729  *     [1,2,3].zip(a, b)      #=> [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
02730  *     [1,2].zip(a,b)         #=> [[1, 4, 7], [2, 5, 8]]
02731  *     a.zip([1,2],[8])       #=> [[4,1,8], [5,2,nil], [6,nil,nil]]
02732  */
02733 
02734 static VALUE
02735 rb_ary_zip(int argc, VALUE *argv, VALUE ary)
02736 {
02737     int i, j;
02738     long len;
02739     VALUE result = Qnil;
02740 
02741     len = RARRAY_LEN(ary);
02742     for (i=0; i<argc; i++) {
02743         argv[i] = take_items(argv[i], len);
02744     }
02745     if (!rb_block_given_p()) {
02746         result = rb_ary_new2(len);
02747     }
02748 
02749     for (i=0; i<RARRAY_LEN(ary); i++) {
02750         VALUE tmp = rb_ary_new2(argc+1);
02751 
02752         rb_ary_push(tmp, rb_ary_elt(ary, i));
02753         for (j=0; j<argc; j++) {
02754             rb_ary_push(tmp, rb_ary_elt(argv[j], i));
02755         }
02756         if (NIL_P(result)) {
02757             rb_yield(tmp);
02758         }
02759         else {
02760             rb_ary_push(result, tmp);
02761         }
02762     }
02763     return result;
02764 }
02765 
02766 /*
02767  *  call-seq:
02768  *     ary.transpose -> new_ary
02769  *
02770  *  Assumes that +self+ is an array of arrays and transposes the
02771  *  rows and columns.
02772  *
02773  *     a = [[1,2], [3,4], [5,6]]
02774  *     a.transpose   #=> [[1, 3, 5], [2, 4, 6]]
02775  */
02776 
02777 static VALUE
02778 rb_ary_transpose(VALUE ary)
02779 {
02780     long elen = -1, alen, i, j;
02781     VALUE tmp, result = 0;
02782 
02783     alen = RARRAY_LEN(ary);
02784     if (alen == 0) return rb_ary_dup(ary);
02785     for (i=0; i<alen; i++) {
02786         tmp = to_ary(rb_ary_elt(ary, i));
02787         if (elen < 0) {         /* first element */
02788             elen = RARRAY_LEN(tmp);
02789             result = rb_ary_new2(elen);
02790             for (j=0; j<elen; j++) {
02791                 rb_ary_store(result, j, rb_ary_new2(alen));
02792             }
02793         }
02794         else if (elen != RARRAY_LEN(tmp)) {
02795             rb_raise(rb_eIndexError, "element size differs (%ld should be %ld)",
02796                      RARRAY_LEN(tmp), elen);
02797         }
02798         for (j=0; j<elen; j++) {
02799             rb_ary_store(rb_ary_elt(result, j), i, rb_ary_elt(tmp, j));
02800         }
02801     }
02802     return result;
02803 }
02804 
02805 /*
02806  *  call-seq:
02807  *     ary.replace(other_ary)  -> ary
02808  *
02809  *  Replaces the contents of +self+ with the contents of
02810  *  <i>other_ary</i>, truncating or expanding if necessary.
02811  *
02812  *     a = [ "a", "b", "c", "d", "e" ]
02813  *     a.replace([ "x", "y", "z" ])   #=> ["x", "y", "z"]
02814  *     a                              #=> ["x", "y", "z"]
02815  */
02816 
02817 VALUE
02818 rb_ary_replace(VALUE copy, VALUE orig)
02819 {
02820     rb_ary_modify_check(copy);
02821     orig = to_ary(orig);
02822     if (copy == orig) return copy;
02823 
02824     if (RARRAY_LEN(orig) <= RARRAY_EMBED_LEN_MAX) {
02825         VALUE *ptr;
02826         VALUE shared = 0;
02827 
02828         if (ARY_OWNS_HEAP_P(copy)) {
02829             xfree(RARRAY_PTR(copy));
02830         }
02831         else if (ARY_SHARED_P(copy)) {
02832             shared = ARY_SHARED(copy);
02833             FL_UNSET_SHARED(copy);
02834         }
02835         FL_SET_EMBED(copy);
02836         ptr = RARRAY_PTR(orig);
02837         MEMCPY(RARRAY_PTR(copy), ptr, VALUE, RARRAY_LEN(orig));
02838         if (shared) {
02839             rb_ary_decrement_share(shared);
02840         }
02841         ARY_SET_LEN(copy, RARRAY_LEN(orig));
02842     }
02843     else {
02844         VALUE shared = ary_make_shared(orig);
02845         if (ARY_OWNS_HEAP_P(copy)) {
02846             xfree(RARRAY_PTR(copy));
02847         }
02848         else {
02849             rb_ary_unshare_safe(copy);
02850         }
02851         FL_UNSET_EMBED(copy);
02852         ARY_SET_PTR(copy, RARRAY_PTR(orig));
02853         ARY_SET_LEN(copy, RARRAY_LEN(orig));
02854         rb_ary_set_shared(copy, shared);
02855     }
02856     return copy;
02857 }
02858 
02859 /*
02860  *  call-seq:
02861  *     ary.clear    -> ary
02862  *
02863  *  Removes all elements from +self+.
02864  *
02865  *     a = [ "a", "b", "c", "d", "e" ]
02866  *     a.clear    #=> [ ]
02867  */
02868 
02869 VALUE
02870 rb_ary_clear(VALUE ary)
02871 {
02872     rb_ary_modify_check(ary);
02873     ARY_SET_LEN(ary, 0);
02874     if (ARY_SHARED_P(ary)) {
02875         if (!ARY_EMBED_P(ary)) {
02876             rb_ary_unshare(ary);
02877             FL_SET_EMBED(ary);
02878         }
02879     }
02880     else if (ARY_DEFAULT_SIZE * 2 < ARY_CAPA(ary)) {
02881         ary_resize_capa(ary, ARY_DEFAULT_SIZE * 2);
02882     }
02883     return ary;
02884 }
02885 
02886 /*
02887  *  call-seq:
02888  *     ary.fill(obj)                                -> ary
02889  *     ary.fill(obj, start [, length])              -> ary
02890  *     ary.fill(obj, range )                        -> ary
02891  *     ary.fill {|index| block }                    -> ary
02892  *     ary.fill(start [, length] ) {|index| block } -> ary
02893  *     ary.fill(range) {|index| block }             -> ary
02894  *
02895  *  The first three forms set the selected elements of +self+ (which
02896  *  may be the entire array) to <i>obj</i>. A <i>start</i> of
02897  *  <code>nil</code> is equivalent to zero. A <i>length</i> of
02898  *  <code>nil</code> is equivalent to <i>self.length</i>. The last three
02899  *  forms fill the array with the value of the block. The block is
02900  *  passed the absolute index of each element to be filled.
02901  *  Negative values of <i>start</i> count from the end of the array.
02902  *
02903  *     a = [ "a", "b", "c", "d" ]
02904  *     a.fill("x")              #=> ["x", "x", "x", "x"]
02905  *     a.fill("z", 2, 2)        #=> ["x", "x", "z", "z"]
02906  *     a.fill("y", 0..1)        #=> ["y", "y", "z", "z"]
02907  *     a.fill {|i| i*i}         #=> [0, 1, 4, 9]
02908  *     a.fill(-2) {|i| i*i*i}   #=> [0, 1, 8, 27]
02909  */
02910 
02911 static VALUE
02912 rb_ary_fill(int argc, VALUE *argv, VALUE ary)
02913 {
02914     VALUE item, arg1, arg2;
02915     long beg = 0, end = 0, len = 0;
02916     VALUE *p, *pend;
02917     int block_p = FALSE;
02918 
02919     if (rb_block_given_p()) {
02920         block_p = TRUE;
02921         rb_scan_args(argc, argv, "02", &arg1, &arg2);
02922         argc += 1;              /* hackish */
02923     }
02924     else {
02925         rb_scan_args(argc, argv, "12", &item, &arg1, &arg2);
02926     }
02927     switch (argc) {
02928       case 1:
02929         beg = 0;
02930         len = RARRAY_LEN(ary);
02931         break;
02932       case 2:
02933         if (rb_range_beg_len(arg1, &beg, &len, RARRAY_LEN(ary), 1)) {
02934             break;
02935         }
02936         /* fall through */
02937       case 3:
02938         beg = NIL_P(arg1) ? 0 : NUM2LONG(arg1);
02939         if (beg < 0) {
02940             beg = RARRAY_LEN(ary) + beg;
02941             if (beg < 0) beg = 0;
02942         }
02943         len = NIL_P(arg2) ? RARRAY_LEN(ary) - beg : NUM2LONG(arg2);
02944         break;
02945     }
02946     rb_ary_modify(ary);
02947     if (len < 0) {
02948         return ary;
02949     }
02950     if (beg >= ARY_MAX_SIZE || len > ARY_MAX_SIZE - beg) {
02951         rb_raise(rb_eArgError, "argument too big");
02952     }
02953     end = beg + len;
02954     if (RARRAY_LEN(ary) < end) {
02955         if (end >= ARY_CAPA(ary)) {
02956             ary_resize_capa(ary, end);
02957         }
02958         rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary), end - RARRAY_LEN(ary));
02959         ARY_SET_LEN(ary, end);
02960     }
02961 
02962     if (block_p) {
02963         VALUE v;
02964         long i;
02965 
02966         for (i=beg; i<end; i++) {
02967             v = rb_yield(LONG2NUM(i));
02968             if (i>=RARRAY_LEN(ary)) break;
02969             RARRAY_PTR(ary)[i] = v;
02970         }
02971     }
02972     else {
02973         p = RARRAY_PTR(ary) + beg;
02974         pend = p + len;
02975         while (p < pend) {
02976             *p++ = item;
02977         }
02978     }
02979     return ary;
02980 }
02981 
02982 /*
02983  *  call-seq:
02984  *     ary + other_ary   -> new_ary
02985  *
02986  *  Concatenation---Returns a new array built by concatenating the
02987  *  two arrays together to produce a third array.
02988  *
02989  *     [ 1, 2, 3 ] + [ 4, 5 ]    #=> [ 1, 2, 3, 4, 5 ]
02990  */
02991 
02992 VALUE
02993 rb_ary_plus(VALUE x, VALUE y)
02994 {
02995     VALUE z;
02996     long len;
02997 
02998     y = to_ary(y);
02999     len = RARRAY_LEN(x) + RARRAY_LEN(y);
03000     z = rb_ary_new2(len);
03001     MEMCPY(RARRAY_PTR(z), RARRAY_PTR(x), VALUE, RARRAY_LEN(x));
03002     MEMCPY(RARRAY_PTR(z) + RARRAY_LEN(x), RARRAY_PTR(y), VALUE, RARRAY_LEN(y));
03003     ARY_SET_LEN(z, len);
03004     return z;
03005 }
03006 
03007 /*
03008  *  call-seq:
03009  *     ary.concat(other_ary)   -> ary
03010  *
03011  *  Appends the elements of <i>other_ary</i> to +self+.
03012  *
03013  *     [ "a", "b" ].concat( ["c", "d"] ) #=> [ "a", "b", "c", "d" ]
03014  */
03015 
03016 
03017 VALUE
03018 rb_ary_concat(VALUE x, VALUE y)
03019 {
03020     rb_ary_modify_check(x);
03021     y = to_ary(y);
03022     if (RARRAY_LEN(y) > 0) {
03023         rb_ary_splice(x, RARRAY_LEN(x), 0, y);
03024     }
03025     return x;
03026 }
03027 
03028 
03029 /*
03030  *  call-seq:
03031  *     ary * int     -> new_ary
03032  *     ary * str     -> new_string
03033  *
03034  *  Repetition---With a String argument, equivalent to
03035  *  self.join(str). Otherwise, returns a new array
03036  *  built by concatenating the _int_ copies of +self+.
03037  *
03038  *
03039  *     [ 1, 2, 3 ] * 3    #=> [ 1, 2, 3, 1, 2, 3, 1, 2, 3 ]
03040  *     [ 1, 2, 3 ] * ","  #=> "1,2,3"
03041  *
03042  */
03043 
03044 static VALUE
03045 rb_ary_times(VALUE ary, VALUE times)
03046 {
03047     VALUE ary2, tmp, *ptr, *ptr2;
03048     long t, len;
03049 
03050     tmp = rb_check_string_type(times);
03051     if (!NIL_P(tmp)) {
03052         return rb_ary_join(ary, tmp);
03053     }
03054 
03055     len = NUM2LONG(times);
03056     if (len == 0) {
03057         ary2 = ary_new(rb_obj_class(ary), 0);
03058         goto out;
03059     }
03060     if (len < 0) {
03061         rb_raise(rb_eArgError, "negative argument");
03062     }
03063     if (ARY_MAX_SIZE/len < RARRAY_LEN(ary)) {
03064         rb_raise(rb_eArgError, "argument too big");
03065     }
03066     len *= RARRAY_LEN(ary);
03067 
03068     ary2 = ary_new(rb_obj_class(ary), len);
03069     ARY_SET_LEN(ary2, len);
03070 
03071     ptr = RARRAY_PTR(ary);
03072     ptr2 = RARRAY_PTR(ary2);
03073     t = RARRAY_LEN(ary);
03074     if (0 < t) {
03075         MEMCPY(ptr2, ptr, VALUE, t);
03076         while (t <= len/2) {
03077             MEMCPY(ptr2+t, ptr2, VALUE, t);
03078             t *= 2;
03079         }
03080         if (t < len) {
03081             MEMCPY(ptr2+t, ptr2, VALUE, len-t);
03082         }
03083     }
03084   out:
03085     OBJ_INFECT(ary2, ary);
03086 
03087     return ary2;
03088 }
03089 
03090 /*
03091  *  call-seq:
03092  *     ary.assoc(obj)   -> new_ary  or  nil
03093  *
03094  *  Searches through an array whose elements are also arrays
03095  *  comparing _obj_ with the first element of each contained array
03096  *  using obj.==.
03097  *  Returns the first contained array that matches (that
03098  *  is, the first associated array),
03099  *  or +nil+ if no match is found.
03100  *  See also <code>Array#rassoc</code>.
03101  *
03102  *     s1 = [ "colors", "red", "blue", "green" ]
03103  *     s2 = [ "letters", "a", "b", "c" ]
03104  *     s3 = "foo"
03105  *     a  = [ s1, s2, s3 ]
03106  *     a.assoc("letters")  #=> [ "letters", "a", "b", "c" ]
03107  *     a.assoc("foo")      #=> nil
03108  */
03109 
03110 VALUE
03111 rb_ary_assoc(VALUE ary, VALUE key)
03112 {
03113     long i;
03114     VALUE v;
03115 
03116     for (i = 0; i < RARRAY_LEN(ary); ++i) {
03117         v = rb_check_array_type(RARRAY_PTR(ary)[i]);
03118         if (!NIL_P(v) && RARRAY_LEN(v) > 0 &&
03119             rb_equal(RARRAY_PTR(v)[0], key))
03120             return v;
03121     }
03122     return Qnil;
03123 }
03124 
03125 /*
03126  *  call-seq:
03127  *     ary.rassoc(obj) -> new_ary or nil
03128  *
03129  *  Searches through the array whose elements are also arrays. Compares
03130  *  _obj_ with the second element of each contained array using
03131  *  <code>==</code>. Returns the first contained array that matches. See
03132  *  also <code>Array#assoc</code>.
03133  *
03134  *     a = [ [ 1, "one"], [2, "two"], [3, "three"], ["ii", "two"] ]
03135  *     a.rassoc("two")    #=> [2, "two"]
03136  *     a.rassoc("four")   #=> nil
03137  */
03138 
03139 VALUE
03140 rb_ary_rassoc(VALUE ary, VALUE value)
03141 {
03142     long i;
03143     VALUE v;
03144 
03145     for (i = 0; i < RARRAY_LEN(ary); ++i) {
03146         v = RARRAY_PTR(ary)[i];
03147         if (TYPE(v) == T_ARRAY &&
03148             RARRAY_LEN(v) > 1 &&
03149             rb_equal(RARRAY_PTR(v)[1], value))
03150             return v;
03151     }
03152     return Qnil;
03153 }
03154 
03155 static VALUE
03156 recursive_equal(VALUE ary1, VALUE ary2, int recur)
03157 {
03158     long i;
03159 
03160     if (recur) return Qtrue; /* Subtle! */
03161     for (i=0; i<RARRAY_LEN(ary1); i++) {
03162         if (!rb_equal(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
03163             return Qfalse;
03164     }
03165     return Qtrue;
03166 }
03167 
03168 /*
03169  *  call-seq:
03170  *     ary == other_ary   ->   bool
03171  *
03172  *  Equality---Two arrays are equal if they contain the same number
03173  *  of elements and if each element is equal to (according to
03174  *  Object.==) the corresponding element in the other array.
03175  *
03176  *     [ "a", "c" ]    == [ "a", "c", 7 ]     #=> false
03177  *     [ "a", "c", 7 ] == [ "a", "c", 7 ]     #=> true
03178  *     [ "a", "c", 7 ] == [ "a", "d", "f" ]   #=> false
03179  *
03180  */
03181 
03182 static VALUE
03183 rb_ary_equal(VALUE ary1, VALUE ary2)
03184 {
03185     if (ary1 == ary2) return Qtrue;
03186     if (TYPE(ary2) != T_ARRAY) {
03187         if (!rb_respond_to(ary2, rb_intern("to_ary"))) {
03188             return Qfalse;
03189         }
03190         return rb_equal(ary2, ary1);
03191     }
03192     if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
03193     return rb_exec_recursive_paired(recursive_equal, ary1, ary2, ary2);
03194 }
03195 
03196 static VALUE
03197 recursive_eql(VALUE ary1, VALUE ary2, int recur)
03198 {
03199     long i;
03200 
03201     if (recur) return Qtrue; /* Subtle! */
03202     for (i=0; i<RARRAY_LEN(ary1); i++) {
03203         if (!rb_eql(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
03204             return Qfalse;
03205     }
03206     return Qtrue;
03207 }
03208 
03209 /*
03210  *  call-seq:
03211  *     ary.eql?(other)  -> true or false
03212  *
03213  *  Returns <code>true</code> if +self+ and _other_ are the same object,
03214  *  or are both arrays with the same content.
03215  */
03216 
03217 static VALUE
03218 rb_ary_eql(VALUE ary1, VALUE ary2)
03219 {
03220     if (ary1 == ary2) return Qtrue;
03221     if (TYPE(ary2) != T_ARRAY) return Qfalse;
03222     if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
03223     return rb_exec_recursive_paired(recursive_eql, ary1, ary2, ary2);
03224 }
03225 
03226 static VALUE
03227 recursive_hash(VALUE ary, VALUE dummy, int recur)
03228 {
03229     long i;
03230     st_index_t h;
03231     VALUE n;
03232 
03233     h = rb_hash_start(RARRAY_LEN(ary));
03234     if (recur) {
03235         h = rb_hash_uint(h, NUM2LONG(rb_hash(rb_cArray)));
03236     }
03237     else {
03238         for (i=0; i<RARRAY_LEN(ary); i++) {
03239             n = rb_hash(RARRAY_PTR(ary)[i]);
03240             h = rb_hash_uint(h, NUM2LONG(n));
03241         }
03242     }
03243     h = rb_hash_end(h);
03244     return LONG2FIX(h);
03245 }
03246 
03247 /*
03248  *  call-seq:
03249  *     ary.hash   -> fixnum
03250  *
03251  *  Compute a hash-code for this array. Two arrays with the same content
03252  *  will have the same hash code (and will compare using <code>eql?</code>).
03253  */
03254 
03255 static VALUE
03256 rb_ary_hash(VALUE ary)
03257 {
03258     return rb_exec_recursive_outer(recursive_hash, ary, 0);
03259 }
03260 
03261 /*
03262  *  call-seq:
03263  *     ary.include?(obj)   -> true or false
03264  *
03265  *  Returns <code>true</code> if the given object is present in
03266  *  +self+ (that is, if any object <code>==</code> <i>anObject</i>),
03267  *  <code>false</code> otherwise.
03268  *
03269  *     a = [ "a", "b", "c" ]
03270  *     a.include?("b")   #=> true
03271  *     a.include?("z")   #=> false
03272  */
03273 
03274 VALUE
03275 rb_ary_includes(VALUE ary, VALUE item)
03276 {
03277     long i;
03278 
03279     for (i=0; i<RARRAY_LEN(ary); i++) {
03280         if (rb_equal(RARRAY_PTR(ary)[i], item)) {
03281             return Qtrue;
03282         }
03283     }
03284     return Qfalse;
03285 }
03286 
03287 
03288 static VALUE
03289 recursive_cmp(VALUE ary1, VALUE ary2, int recur)
03290 {
03291     long i, len;
03292 
03293     if (recur) return Qundef;   /* Subtle! */
03294     len = RARRAY_LEN(ary1);
03295     if (len > RARRAY_LEN(ary2)) {
03296         len = RARRAY_LEN(ary2);
03297     }
03298     for (i=0; i<len; i++) {
03299         VALUE v = rb_funcall(rb_ary_elt(ary1, i), id_cmp, 1, rb_ary_elt(ary2, i));
03300         if (v != INT2FIX(0)) {
03301             return v;
03302         }
03303     }
03304     return Qundef;
03305 }
03306 
03307 /*
03308  *  call-seq:
03309  *     ary <=> other_ary   ->  -1, 0, +1 or nil
03310  *
03311  *  Comparison---Returns an integer (-1, 0,
03312  *  or +1) if this array is less than, equal to, or greater than
03313  *  <i>other_ary</i>.  Each object in each array is compared
03314  *  (using <=>). If any value isn't
03315  *  equal, then that inequality is the return value. If all the
03316  *  values found are equal, then the return is based on a
03317  *  comparison of the array lengths.  Thus, two arrays are
03318  *  ``equal'' according to <code>Array#<=></code> if and only if they have
03319  *  the same length and the value of each element is equal to the
03320  *  value of the corresponding element in the other array.
03321  *
03322  *     [ "a", "a", "c" ]    <=> [ "a", "b", "c" ]   #=> -1
03323  *     [ 1, 2, 3, 4, 5, 6 ] <=> [ 1, 2 ]            #=> +1
03324  *
03325  */
03326 
03327 VALUE
03328 rb_ary_cmp(VALUE ary1, VALUE ary2)
03329 {
03330     long len;
03331     VALUE v;
03332 
03333     ary2 = rb_check_array_type(ary2);
03334     if (NIL_P(ary2)) return Qnil;
03335     if (ary1 == ary2) return INT2FIX(0);
03336     v = rb_exec_recursive_paired(recursive_cmp, ary1, ary2, ary2);
03337     if (v != Qundef) return v;
03338     len = RARRAY_LEN(ary1) - RARRAY_LEN(ary2);
03339     if (len == 0) return INT2FIX(0);
03340     if (len > 0) return INT2FIX(1);
03341     return INT2FIX(-1);
03342 }
03343 
03344 static VALUE
03345 ary_add_hash(VALUE hash, VALUE ary)
03346 {
03347     long i;
03348 
03349     for (i=0; i<RARRAY_LEN(ary); i++) {
03350         rb_hash_aset(hash, RARRAY_PTR(ary)[i], Qtrue);
03351     }
03352     return hash;
03353 }
03354 
03355 static inline VALUE
03356 ary_tmp_hash_new(void)
03357 {
03358     VALUE hash = rb_hash_new();
03359 
03360     RBASIC(hash)->klass = 0;
03361     return hash;
03362 }
03363 
03364 static VALUE
03365 ary_make_hash(VALUE ary)
03366 {
03367     VALUE hash = ary_tmp_hash_new();
03368     return ary_add_hash(hash, ary);
03369 }
03370 
03371 static VALUE
03372 ary_add_hash_by(VALUE hash, VALUE ary)
03373 {
03374     long i;
03375 
03376     for (i = 0; i < RARRAY_LEN(ary); ++i) {
03377         VALUE v = rb_ary_elt(ary, i), k = rb_yield(v);
03378         if (rb_hash_lookup2(hash, k, Qundef) == Qundef) {
03379             rb_hash_aset(hash, k, v);
03380         }
03381     }
03382     return hash;
03383 }
03384 
03385 static VALUE
03386 ary_make_hash_by(VALUE ary)
03387 {
03388     VALUE hash = ary_tmp_hash_new();
03389     return ary_add_hash_by(hash, ary);
03390 }
03391 
03392 static inline void
03393 ary_recycle_hash(VALUE hash)
03394 {
03395     if (RHASH(hash)->ntbl) {
03396         st_table *tbl = RHASH(hash)->ntbl;
03397         RHASH(hash)->ntbl = 0;
03398         st_free_table(tbl);
03399     }
03400 }
03401 
03402 /*
03403  *  call-seq:
03404  *     ary - other_ary    -> new_ary
03405  *
03406  *  Array Difference---Returns a new array that is a copy of
03407  *  the original array, removing any items that also appear in
03408  *  <i>other_ary</i>. (If you need set-like behavior, see the
03409  *  library class Set.)
03410  *
03411  *     [ 1, 1, 2, 2, 3, 3, 4, 5 ] - [ 1, 2, 4 ]  #=>  [ 3, 3, 5 ]
03412  */
03413 
03414 static VALUE
03415 rb_ary_diff(VALUE ary1, VALUE ary2)
03416 {
03417     VALUE ary3;
03418     volatile VALUE hash;
03419     long i;
03420 
03421     hash = ary_make_hash(to_ary(ary2));
03422     ary3 = rb_ary_new();
03423 
03424     for (i=0; i<RARRAY_LEN(ary1); i++) {
03425         if (st_lookup(RHASH_TBL(hash), RARRAY_PTR(ary1)[i], 0)) continue;
03426         rb_ary_push(ary3, rb_ary_elt(ary1, i));
03427     }
03428     ary_recycle_hash(hash);
03429     return ary3;
03430 }
03431 
03432 /*
03433  *  call-seq:
03434  *     ary & other_ary      -> new_ary
03435  *
03436  *  Set Intersection---Returns a new array
03437  *  containing elements common to the two arrays, with no duplicates.
03438  *
03439  *     [ 1, 1, 3, 5 ] & [ 1, 2, 3 ]   #=> [ 1, 3 ]
03440  */
03441 
03442 
03443 static VALUE
03444 rb_ary_and(VALUE ary1, VALUE ary2)
03445 {
03446     VALUE hash, ary3, v;
03447     st_data_t vv;
03448     long i;
03449 
03450     ary2 = to_ary(ary2);
03451     ary3 = rb_ary_new2(RARRAY_LEN(ary1) < RARRAY_LEN(ary2) ?
03452             RARRAY_LEN(ary1) : RARRAY_LEN(ary2));
03453     hash = ary_make_hash(ary2);
03454 
03455     if (RHASH_EMPTY_P(hash))
03456         return ary3;
03457 
03458     for (i=0; i<RARRAY_LEN(ary1); i++) {
03459         vv = (st_data_t)(v = rb_ary_elt(ary1, i));
03460         if (st_delete(RHASH_TBL(hash), &vv, 0)) {
03461             rb_ary_push(ary3, v);
03462         }
03463     }
03464     ary_recycle_hash(hash);
03465 
03466     return ary3;
03467 }
03468 
03469 /*
03470  *  call-seq:
03471  *     ary | other_ary     -> new_ary
03472  *
03473  *  Set Union---Returns a new array by joining this array with
03474  *  <i>other_ary</i>, removing duplicates.
03475  *
03476  *     [ "a", "b", "c" ] | [ "c", "d", "a" ]
03477  *            #=> [ "a", "b", "c", "d" ]
03478  */
03479 
03480 static VALUE
03481 rb_ary_or(VALUE ary1, VALUE ary2)
03482 {
03483     VALUE hash, ary3, v;
03484     st_data_t vv;
03485     long i;
03486 
03487     ary2 = to_ary(ary2);
03488     ary3 = rb_ary_new2(RARRAY_LEN(ary1)+RARRAY_LEN(ary2));
03489     hash = ary_add_hash(ary_make_hash(ary1), ary2);
03490 
03491     for (i=0; i<RARRAY_LEN(ary1); i++) {
03492         vv = (st_data_t)(v = rb_ary_elt(ary1, i));
03493         if (st_delete(RHASH_TBL(hash), &vv, 0)) {
03494             rb_ary_push(ary3, v);
03495         }
03496     }
03497     for (i=0; i<RARRAY_LEN(ary2); i++) {
03498         vv = (st_data_t)(v = rb_ary_elt(ary2, i));
03499         if (st_delete(RHASH_TBL(hash), &vv, 0)) {
03500             rb_ary_push(ary3, v);
03501         }
03502     }
03503     ary_recycle_hash(hash);
03504     return ary3;
03505 }
03506 
03507 static int
03508 push_value(st_data_t key, st_data_t val, st_data_t ary)
03509 {
03510     rb_ary_push((VALUE)ary, (VALUE)val);
03511     return ST_CONTINUE;
03512 }
03513 
03514 /*
03515  *  call-seq:
03516  *     ary.uniq!                -> ary or nil
03517  *     ary.uniq! { |item| ... } -> ary or nil
03518  *
03519  *  Removes duplicate elements from +self+. If a block is given,
03520  *  it will use the return value of the block for comparison.
03521  *  Returns <code>nil</code> if no changes are made (that is, no
03522  *  duplicates are found).
03523  *
03524  *     a = [ "a", "a", "b", "b", "c" ]
03525  *     a.uniq!   # => ["a", "b", "c"]
03526  *
03527  *     b = [ "a", "b", "c" ]
03528  *     b.uniq!   # => nil
03529  *
03530  *     c = [["student","sam"], ["student","george"], ["teacher","matz"]]
03531  *     c.uniq! { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]]
03532  *
03533  */
03534 
03535 static VALUE
03536 rb_ary_uniq_bang(VALUE ary)
03537 {
03538     VALUE hash, v;
03539     long i, j;
03540 
03541     rb_ary_modify_check(ary);
03542     if (RARRAY_LEN(ary) <= 1)
03543         return Qnil;
03544     if (rb_block_given_p()) {
03545         hash = ary_make_hash_by(ary);
03546         if (RARRAY_LEN(ary) == (i = RHASH_SIZE(hash))) {
03547             return Qnil;
03548         }
03549         ARY_SET_LEN(ary, 0);
03550         if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
03551             rb_ary_unshare(ary);
03552             FL_SET_EMBED(ary);
03553         }
03554         ary_resize_capa(ary, i);
03555         st_foreach(RHASH_TBL(hash), push_value, ary);
03556     }
03557     else {
03558         hash = ary_make_hash(ary);
03559         if (RARRAY_LEN(ary) == (long)RHASH_SIZE(hash)) {
03560             return Qnil;
03561         }
03562         for (i=j=0; i<RARRAY_LEN(ary); i++) {
03563             st_data_t vv = (st_data_t)(v = rb_ary_elt(ary, i));
03564             if (st_delete(RHASH_TBL(hash), &vv, 0)) {
03565                 rb_ary_store(ary, j++, v);
03566             }
03567         }
03568         ARY_SET_LEN(ary, j);
03569     }
03570     ary_recycle_hash(hash);
03571 
03572     return ary;
03573 }
03574 
03575 /*
03576  *  call-seq:
03577  *     ary.uniq                -> new_ary
03578  *     ary.uniq { |item| ... } -> new_ary
03579  *
03580  *  Returns a new array by removing duplicate values in +self+. If a block
03581  *  is given, it will use the return value of the block for comparison.
03582  *
03583  *     a = [ "a", "a", "b", "b", "c" ]
03584  *     a.uniq   # => ["a", "b", "c"]
03585  *
03586  *     b = [["student","sam"], ["student","george"], ["teacher","matz"]]
03587  *     b.uniq { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]]
03588  *
03589  */
03590 
03591 static VALUE
03592 rb_ary_uniq(VALUE ary)
03593 {
03594     VALUE hash, uniq, v;
03595     long i;
03596 
03597     if (RARRAY_LEN(ary) <= 1)
03598         return rb_ary_dup(ary);
03599     if (rb_block_given_p()) {
03600         hash = ary_make_hash_by(ary);
03601         uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash));
03602         st_foreach(RHASH_TBL(hash), push_value, uniq);
03603     }
03604     else {
03605         hash = ary_make_hash(ary);
03606         uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash));
03607         for (i=0; i<RARRAY_LEN(ary); i++) {
03608             st_data_t vv = (st_data_t)(v = rb_ary_elt(ary, i));
03609             if (st_delete(RHASH_TBL(hash), &vv, 0)) {
03610                 rb_ary_push(uniq, v);
03611             }
03612         }
03613     }
03614     ary_recycle_hash(hash);
03615 
03616     return uniq;
03617 }
03618 
03619 /*
03620  *  call-seq:
03621  *     ary.compact!    -> ary  or  nil
03622  *
03623  *  Removes +nil+ elements from the array.
03624  *  Returns +nil+ if no changes were made, otherwise returns
03625  *  <i>ary</i>.
03626  *
03627  *     [ "a", nil, "b", nil, "c" ].compact! #=> [ "a", "b", "c" ]
03628  *     [ "a", "b", "c" ].compact!           #=> nil
03629  */
03630 
03631 static VALUE
03632 rb_ary_compact_bang(VALUE ary)
03633 {
03634     VALUE *p, *t, *end;
03635     long n;
03636 
03637     rb_ary_modify(ary);
03638     p = t = RARRAY_PTR(ary);
03639     end = p + RARRAY_LEN(ary);
03640 
03641     while (t < end) {
03642         if (NIL_P(*t)) t++;
03643         else *p++ = *t++;
03644     }
03645     n = p - RARRAY_PTR(ary);
03646     if (RARRAY_LEN(ary) == n) {
03647         return Qnil;
03648     }
03649     ARY_SET_LEN(ary, n);
03650     if (n * 2 < ARY_CAPA(ary) && ARY_DEFAULT_SIZE * 2 < ARY_CAPA(ary)) {
03651         ary_resize_capa(ary, n * 2);
03652     }
03653 
03654     return ary;
03655 }
03656 
03657 /*
03658  *  call-seq:
03659  *     ary.compact     -> new_ary
03660  *
03661  *  Returns a copy of +self+ with all +nil+ elements removed.
03662  *
03663  *     [ "a", nil, "b", nil, "c", nil ].compact
03664  *                       #=> [ "a", "b", "c" ]
03665  */
03666 
03667 static VALUE
03668 rb_ary_compact(VALUE ary)
03669 {
03670     ary = rb_ary_dup(ary);
03671     rb_ary_compact_bang(ary);
03672     return ary;
03673 }
03674 
03675 /*
03676  *  call-seq:
03677  *     ary.count      -> int
03678  *     ary.count(obj) -> int
03679  *     ary.count { |item| block }  -> int
03680  *
03681  *  Returns the number of elements.  If an argument is given, counts
03682  *  the number of elements which equals to <i>obj</i>.  If a block is
03683  *  given, counts the number of elements yielding a true value.
03684  *
03685  *     ary = [1, 2, 4, 2]
03686  *     ary.count             #=> 4
03687  *     ary.count(2)          #=> 2
03688  *     ary.count{|x|x%2==0}  #=> 3
03689  *
03690  */
03691 
03692 static VALUE
03693 rb_ary_count(int argc, VALUE *argv, VALUE ary)
03694 {
03695     long n = 0;
03696 
03697     if (argc == 0) {
03698         VALUE *p, *pend;
03699 
03700         if (!rb_block_given_p())
03701             return LONG2NUM(RARRAY_LEN(ary));
03702 
03703         for (p = RARRAY_PTR(ary), pend = p + RARRAY_LEN(ary); p < pend; p++) {
03704             if (RTEST(rb_yield(*p))) n++;
03705         }
03706     }
03707     else {
03708         VALUE obj, *p, *pend;
03709 
03710         rb_scan_args(argc, argv, "1", &obj);
03711         if (rb_block_given_p()) {
03712             rb_warn("given block not used");
03713         }
03714         for (p = RARRAY_PTR(ary), pend = p + RARRAY_LEN(ary); p < pend; p++) {
03715             if (rb_equal(*p, obj)) n++;
03716         }
03717     }
03718 
03719     return LONG2NUM(n);
03720 }
03721 
03722 static VALUE
03723 flatten(VALUE ary, int level, int *modified)
03724 {
03725     long i = 0;
03726     VALUE stack, result, tmp, elt;
03727     st_table *memo;
03728     st_data_t id;
03729 
03730     stack = ary_new(0, ARY_DEFAULT_SIZE);
03731     result = ary_new(0, RARRAY_LEN(ary));
03732     memo = st_init_numtable();
03733     st_insert(memo, (st_data_t)ary, (st_data_t)Qtrue);
03734     *modified = 0;
03735 
03736     while (1) {
03737         while (i < RARRAY_LEN(ary)) {
03738             elt = RARRAY_PTR(ary)[i++];
03739             tmp = rb_check_array_type(elt);
03740             if (RBASIC(result)->klass) {
03741                 rb_raise(rb_eRuntimeError, "flatten reentered");
03742             }
03743             if (NIL_P(tmp) || (level >= 0 && RARRAY_LEN(stack) / 2 >= level)) {
03744                 rb_ary_push(result, elt);
03745             }
03746             else {
03747                 *modified = 1;
03748                 id = (st_data_t)tmp;
03749                 if (st_lookup(memo, id, 0)) {
03750                     st_free_table(memo);
03751                     rb_raise(rb_eArgError, "tried to flatten recursive array");
03752                 }
03753                 st_insert(memo, id, (st_data_t)Qtrue);
03754                 rb_ary_push(stack, ary);
03755                 rb_ary_push(stack, LONG2NUM(i));
03756                 ary = tmp;
03757                 i = 0;
03758             }
03759         }
03760         if (RARRAY_LEN(stack) == 0) {
03761             break;
03762         }
03763         id = (st_data_t)ary;
03764         st_delete(memo, &id, 0);
03765         tmp = rb_ary_pop(stack);
03766         i = NUM2LONG(tmp);
03767         ary = rb_ary_pop(stack);
03768     }
03769 
03770     st_free_table(memo);
03771 
03772     RBASIC(result)->klass = rb_class_of(ary);
03773     return result;
03774 }
03775 
03776 /*
03777  *  call-seq:
03778  *     ary.flatten!        -> ary or nil
03779  *     ary.flatten!(level) -> array or nil
03780  *
03781  *  Flattens +self+ in place.
03782  *  Returns <code>nil</code> if no modifications were made (i.e.,
03783  *  <i>ary</i> contains no subarrays.)  If the optional <i>level</i>
03784  *  argument determines the level of recursion to flatten.
03785  *
03786  *     a = [ 1, 2, [3, [4, 5] ] ]
03787  *     a.flatten!   #=> [1, 2, 3, 4, 5]
03788  *     a.flatten!   #=> nil
03789  *     a            #=> [1, 2, 3, 4, 5]
03790  *     a = [ 1, 2, [3, [4, 5] ] ]
03791  *     a.flatten!(1) #=> [1, 2, 3, [4, 5]]
03792  */
03793 
03794 static VALUE
03795 rb_ary_flatten_bang(int argc, VALUE *argv, VALUE ary)
03796 {
03797     int mod = 0, level = -1;
03798     VALUE result, lv;
03799 
03800     rb_scan_args(argc, argv, "01", &lv);
03801     rb_ary_modify_check(ary);
03802     if (!NIL_P(lv)) level = NUM2INT(lv);
03803     if (level == 0) return Qnil;
03804 
03805     result = flatten(ary, level, &mod);
03806     if (mod == 0) {
03807         ary_discard(result);
03808         return Qnil;
03809     }
03810     if (!(mod = ARY_EMBED_P(result))) rb_obj_freeze(result);
03811     rb_ary_replace(ary, result);
03812     if (mod) ARY_SET_EMBED_LEN(result, 0);
03813 
03814     return ary;
03815 }
03816 
03817 /*
03818  *  call-seq:
03819  *     ary.flatten -> new_ary
03820  *     ary.flatten(level) -> new_ary
03821  *
03822  *  Returns a new array that is a one-dimensional flattening of this
03823  *  array (recursively). That is, for every element that is an array,
03824  *  extract its elements into the new array.  If the optional
03825  *  <i>level</i> argument determines the level of recursion to flatten.
03826  *
03827  *     s = [ 1, 2, 3 ]           #=> [1, 2, 3]
03828  *     t = [ 4, 5, 6, [7, 8] ]   #=> [4, 5, 6, [7, 8]]
03829  *     a = [ s, t, 9, 10 ]       #=> [[1, 2, 3], [4, 5, 6, [7, 8]], 9, 10]
03830  *     a.flatten                 #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
03831  *     a = [ 1, 2, [3, [4, 5] ] ]
03832  *     a.flatten(1)              #=> [1, 2, 3, [4, 5]]
03833  */
03834 
03835 static VALUE
03836 rb_ary_flatten(int argc, VALUE *argv, VALUE ary)
03837 {
03838     int mod = 0, level = -1;
03839     VALUE result, lv;
03840 
03841     rb_scan_args(argc, argv, "01", &lv);
03842     if (!NIL_P(lv)) level = NUM2INT(lv);
03843     if (level == 0) return ary_make_shared_copy(ary);
03844 
03845     result = flatten(ary, level, &mod);
03846     OBJ_INFECT(result, ary);
03847 
03848     return result;
03849 }
03850 
03851 #define OPTHASH_GIVEN_P(opts) \
03852     (argc > 0 && !NIL_P((opts) = rb_check_hash_type(argv[argc-1])) && (--argc, 1))
03853 static VALUE sym_random;
03854 
03855 #define RAND_UPTO(max) (long)(rb_random_real(randgen)*(max))
03856 
03857 /*
03858  *  call-seq:
03859  *     ary.shuffle!              -> ary
03860  *     ary.shuffle!(random: rng) -> ary
03861  *
03862  *  Shuffles elements in +self+ in place.
03863  *  If +rng+ is given, it will be used as the random number generator.
03864  */
03865 
03866 static VALUE
03867 rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary)
03868 {
03869     VALUE *ptr, opts, *snap_ptr, randgen = rb_cRandom;
03870     long i, snap_len;
03871 
03872     if (OPTHASH_GIVEN_P(opts)) {
03873         randgen = rb_hash_lookup2(opts, sym_random, randgen);
03874     }
03875     if (argc > 0) {
03876         rb_raise(rb_eArgError, "wrong number of arguments (%d for 0)", argc);
03877     }
03878     rb_ary_modify(ary);
03879     i = RARRAY_LEN(ary);
03880     ptr = RARRAY_PTR(ary);
03881     snap_len = i;
03882     snap_ptr = ptr;
03883     while (i) {
03884         long j = RAND_UPTO(i);
03885         VALUE tmp;
03886         if (snap_len != RARRAY_LEN(ary) || snap_ptr != RARRAY_PTR(ary)) {
03887             rb_raise(rb_eRuntimeError, "modified during shuffle");
03888         }
03889         tmp = ptr[--i];
03890         ptr[i] = ptr[j];
03891         ptr[j] = tmp;
03892     }
03893     return ary;
03894 }
03895 
03896 
03897 /*
03898  *  call-seq:
03899  *     ary.shuffle              -> new_ary
03900  *     ary.shuffle(random: rng) -> new_ary
03901  *
03902  *  Returns a new array with elements of this array shuffled.
03903  *
03904  *     a = [ 1, 2, 3 ]           #=> [1, 2, 3]
03905  *     a.shuffle                 #=> [2, 3, 1]
03906  *
03907  *  If +rng+ is given, it will be used as the random number generator.
03908  *
03909  *     a.shuffle(random: Random.new(1))  #=> [1, 3, 2]
03910  */
03911 
03912 static VALUE
03913 rb_ary_shuffle(int argc, VALUE *argv, VALUE ary)
03914 {
03915     ary = rb_ary_dup(ary);
03916     rb_ary_shuffle_bang(argc, argv, ary);
03917     return ary;
03918 }
03919 
03920 
03921 /*
03922  *  call-seq:
03923  *     ary.sample                  -> obj
03924  *     ary.sample(random: rng)     -> obj
03925  *     ary.sample(n)               -> new_ary
03926  *     ary.sample(n, random: rng)  -> new_ary
03927  *
03928  *  Choose a random element or +n+ random elements from the array. The elements
03929  *  are chosen by using random and unique indices into the array in order to
03930  *  ensure that an element doesn't repeat itself unless the array already
03931  *  contained duplicate elements. If the array is empty the first form returns
03932  *  <code>nil</code> and the second form returns an empty array.
03933  *
03934  *  If +rng+ is given, it will be used as the random number generator.
03935  */
03936 
03937 
03938 static VALUE
03939 rb_ary_sample(int argc, VALUE *argv, VALUE ary)
03940 {
03941     VALUE nv, result, *ptr;
03942     VALUE opts, randgen = rb_cRandom;
03943     long n, len, i, j, k, idx[10];
03944     double rnds[numberof(idx)];
03945 
03946     if (OPTHASH_GIVEN_P(opts)) {
03947         randgen = rb_hash_lookup2(opts, sym_random, randgen);
03948     }
03949     ptr = RARRAY_PTR(ary);
03950     len = RARRAY_LEN(ary);
03951     if (argc == 0) {
03952         if (len == 0) return Qnil;
03953         if (len == 1) {
03954             i = 0;
03955         }
03956         else {
03957             double x = rb_random_real(randgen);
03958             if ((len = RARRAY_LEN(ary)) == 0) return Qnil;
03959             i = (long)(x * len);
03960         }
03961         return RARRAY_PTR(ary)[i];
03962     }
03963     rb_scan_args(argc, argv, "1", &nv);
03964     n = NUM2LONG(nv);
03965     if (n < 0) rb_raise(rb_eArgError, "negative sample number");
03966     if (n > len) n = len;
03967     if (n <= numberof(idx)) {
03968         for (i = 0; i < n; ++i) {
03969             rnds[i] = rb_random_real(randgen);
03970         }
03971     }
03972     len = RARRAY_LEN(ary);
03973     ptr = RARRAY_PTR(ary);
03974     if (n > len) n = len;
03975     switch (n) {
03976       case 0:
03977         return rb_ary_new2(0);
03978       case 1:
03979         i = (long)(rnds[0] * len);
03980         return rb_ary_new4(1, &ptr[i]);
03981       case 2:
03982         i = (long)(rnds[0] * len);
03983         j = (long)(rnds[1] * (len-1));
03984         if (j >= i) j++;
03985         return rb_ary_new3(2, ptr[i], ptr[j]);
03986       case 3:
03987         i = (long)(rnds[0] * len);
03988         j = (long)(rnds[1] * (len-1));
03989         k = (long)(rnds[2] * (len-2));
03990         {
03991             long l = j, g = i;
03992             if (j >= i) l = i, g = ++j;
03993             if (k >= l && (++k >= g)) ++k;
03994         }
03995         return rb_ary_new3(3, ptr[i], ptr[j], ptr[k]);
03996     }
03997     if (n <= numberof(idx)) {
03998         VALUE *ptr_result;
03999         long sorted[numberof(idx)];
04000         sorted[0] = idx[0] = (long)(rnds[0] * len);
04001         for (i=1; i<n; i++) {
04002             k = (long)(rnds[i] * --len);
04003             for (j = 0; j < i; ++j) {
04004                 if (k < sorted[j]) break;
04005                 ++k;
04006             }
04007             memmove(&sorted[j+1], &sorted[j], sizeof(sorted[0])*(i-j));
04008             sorted[j] = idx[i] = k;
04009         }
04010         result = rb_ary_new2(n);
04011         ptr_result = RARRAY_PTR(result);
04012         for (i=0; i<n; i++) {
04013             ptr_result[i] = ptr[idx[i]];
04014         }
04015     }
04016     else {
04017         VALUE *ptr_result;
04018         result = rb_ary_new4(len, ptr);
04019         RBASIC(result)->klass = 0;
04020         ptr_result = RARRAY_PTR(result);
04021         RB_GC_GUARD(ary);
04022         for (i=0; i<n; i++) {
04023             j = RAND_UPTO(len-i) + i;
04024             nv = ptr_result[j];
04025             ptr_result[j] = ptr_result[i];
04026             ptr_result[i] = nv;
04027         }
04028         RBASIC(result)->klass = rb_cArray;
04029     }
04030     ARY_SET_LEN(result, n);
04031 
04032     return result;
04033 }
04034 
04035 
04036 /*
04037  *  call-seq:
04038  *     ary.cycle(n=nil) {|obj| block }  -> nil
04039  *     ary.cycle(n=nil)                 -> an_enumerator
04040  *
04041  *  Calls <i>block</i> for each element repeatedly _n_ times or
04042  *  forever if none or +nil+ is given.  If a non-positive number is
04043  *  given or the array is empty, does nothing.  Returns +nil+ if the
04044  *  loop has finished without getting interrupted.
04045  *
04046  *  If no block is given, an enumerator is returned instead.
04047  *
04048  *
04049  *     a = ["a", "b", "c"]
04050  *     a.cycle {|x| puts x }  # print, a, b, c, a, b, c,.. forever.
04051  *     a.cycle(2) {|x| puts x }  # print, a, b, c, a, b, c.
04052  *
04053  */
04054 
04055 static VALUE
04056 rb_ary_cycle(int argc, VALUE *argv, VALUE ary)
04057 {
04058     long n, i;
04059     VALUE nv = Qnil;
04060 
04061     rb_scan_args(argc, argv, "01", &nv);
04062 
04063     RETURN_ENUMERATOR(ary, argc, argv);
04064     if (NIL_P(nv)) {
04065         n = -1;
04066     }
04067     else {
04068         n = NUM2LONG(nv);
04069         if (n <= 0) return Qnil;
04070     }
04071 
04072     while (RARRAY_LEN(ary) > 0 && (n < 0 || 0 < n--)) {
04073         for (i=0; i<RARRAY_LEN(ary); i++) {
04074             rb_yield(RARRAY_PTR(ary)[i]);
04075         }
04076     }
04077     return Qnil;
04078 }
04079 
04080 #define tmpbuf(n, size) rb_str_tmp_new((n)*(size))
04081 #define tmpbuf_discard(s) (rb_str_resize((s), 0L), RBASIC(s)->klass = rb_cString)
04082 #define tmpary(n) rb_ary_tmp_new(n)
04083 #define tmpary_discard(a) (ary_discard(a), RBASIC(a)->klass = rb_cArray)
04084 
04085 /*
04086  * Recursively compute permutations of r elements of the set [0..n-1].
04087  * When we have a complete permutation of array indexes, copy the values
04088  * at those indexes into a new array and yield that array.
04089  *
04090  * n: the size of the set
04091  * r: the number of elements in each permutation
04092  * p: the array (of size r) that we're filling in
04093  * index: what index we're filling in now
04094  * used: an array of booleans: whether a given index is already used
04095  * values: the Ruby array that holds the actual values to permute
04096  */
04097 static void
04098 permute0(long n, long r, long *p, long index, char *used, VALUE values)
04099 {
04100     long i,j;
04101     for (i = 0; i < n; i++) {
04102         if (used[i] == 0) {
04103             p[index] = i;
04104             if (index < r-1) {             /* if not done yet */
04105                 used[i] = 1;               /* mark index used */
04106                 permute0(n, r, p, index+1, /* recurse */
04107                          used, values);
04108                 used[i] = 0;               /* index unused */
04109             }
04110             else {
04111                 /* We have a complete permutation of array indexes */
04112                 /* Build a ruby array of the corresponding values */
04113                 /* And yield it to the associated block */
04114                 VALUE result = rb_ary_new2(r);
04115                 VALUE *result_array = RARRAY_PTR(result);
04116                 const VALUE *values_array = RARRAY_PTR(values);
04117 
04118                 for (j = 0; j < r; j++) result_array[j] = values_array[p[j]];
04119                 ARY_SET_LEN(result, r);
04120                 rb_yield(result);
04121                 if (RBASIC(values)->klass) {
04122                     rb_raise(rb_eRuntimeError, "permute reentered");
04123                 }
04124             }
04125         }
04126     }
04127 }
04128 
04129 /*
04130  *  call-seq:
04131  *     ary.permutation { |p| block }          -> ary
04132  *     ary.permutation                        -> an_enumerator
04133  *     ary.permutation(n) { |p| block }       -> ary
04134  *     ary.permutation(n)                     -> an_enumerator
04135  *
04136  * When invoked with a block, yield all permutations of length <i>n</i>
04137  * of the elements of <i>ary</i>, then return the array itself.
04138  * If <i>n</i> is not specified, yield all permutations of all elements.
04139  * The implementation makes no guarantees about the order in which
04140  * the permutations are yielded.
04141  *
04142  * If no block is given, an enumerator is returned instead.
04143  *
04144  * Examples:
04145  *
04146  *     a = [1, 2, 3]
04147  *     a.permutation.to_a     #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
04148  *     a.permutation(1).to_a  #=> [[1],[2],[3]]
04149  *     a.permutation(2).to_a  #=> [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]
04150  *     a.permutation(3).to_a  #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
04151  *     a.permutation(0).to_a  #=> [[]] # one permutation of length 0
04152  *     a.permutation(4).to_a  #=> []   # no permutations of length 4
04153  */
04154 
04155 static VALUE
04156 rb_ary_permutation(int argc, VALUE *argv, VALUE ary)
04157 {
04158     VALUE num;
04159     long r, n, i;
04160 
04161     n = RARRAY_LEN(ary);                  /* Array length */
04162     RETURN_ENUMERATOR(ary, argc, argv);   /* Return enumerator if no block */
04163     rb_scan_args(argc, argv, "01", &num);
04164     r = NIL_P(num) ? n : NUM2LONG(num);   /* Permutation size from argument */
04165 
04166     if (r < 0 || n < r) {
04167         /* no permutations: yield nothing */
04168     }
04169     else if (r == 0) { /* exactly one permutation: the zero-length array */
04170         rb_yield(rb_ary_new2(0));
04171     }
04172     else if (r == 1) { /* this is a special, easy case */
04173         for (i = 0; i < RARRAY_LEN(ary); i++) {
04174             rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
04175         }
04176     }
04177     else {             /* this is the general case */
04178         volatile VALUE t0 = tmpbuf(n,sizeof(long));
04179         long *p = (long*)RSTRING_PTR(t0);
04180         volatile VALUE t1 = tmpbuf(n,sizeof(char));
04181         char *used = (char*)RSTRING_PTR(t1);
04182         VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
04183         RBASIC(ary0)->klass = 0;
04184 
04185         MEMZERO(used, char, n); /* initialize array */
04186 
04187         permute0(n, r, p, 0, used, ary0); /* compute and yield permutations */
04188         tmpbuf_discard(t0);
04189         tmpbuf_discard(t1);
04190         RBASIC(ary0)->klass = rb_cArray;
04191     }
04192     return ary;
04193 }
04194 
04195 /*
04196  *  call-seq:
04197  *     ary.combination(n) { |c| block }    -> ary
04198  *     ary.combination(n)                  -> an_enumerator
04199  *
04200  * When invoked with a block, yields all combinations of length <i>n</i>
04201  * of elements from <i>ary</i> and then returns <i>ary</i> itself.
04202  * The implementation makes no guarantees about the order in which
04203  * the combinations are yielded.
04204  *
04205  * If no block is given, an enumerator is returned instead.
04206  *
04207  * Examples:
04208  *
04209  *     a = [1, 2, 3, 4]
04210  *     a.combination(1).to_a  #=> [[1],[2],[3],[4]]
04211  *     a.combination(2).to_a  #=> [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
04212  *     a.combination(3).to_a  #=> [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
04213  *     a.combination(4).to_a  #=> [[1,2,3,4]]
04214  *     a.combination(0).to_a  #=> [[]] # one combination of length 0
04215  *     a.combination(5).to_a  #=> []   # no combinations of length 5
04216  *
04217  */
04218 
04219 static VALUE
04220 rb_ary_combination(VALUE ary, VALUE num)
04221 {
04222     long n, i, len;
04223 
04224     n = NUM2LONG(num);
04225     RETURN_ENUMERATOR(ary, 1, &num);
04226     len = RARRAY_LEN(ary);
04227     if (n < 0 || len < n) {
04228         /* yield nothing */
04229     }
04230     else if (n == 0) {
04231         rb_yield(rb_ary_new2(0));
04232     }
04233     else if (n == 1) {
04234         for (i = 0; i < len; i++) {
04235             rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
04236         }
04237     }
04238     else {
04239         volatile VALUE t0 = tmpbuf(n+1, sizeof(long));
04240         long *stack = (long*)RSTRING_PTR(t0);
04241         volatile VALUE cc = tmpary(n);
04242         VALUE *chosen = RARRAY_PTR(cc);
04243         long lev = 0;
04244 
04245         MEMZERO(stack, long, n);
04246         stack[0] = -1;
04247         for (;;) {
04248             chosen[lev] = RARRAY_PTR(ary)[stack[lev+1]];
04249             for (lev++; lev < n; lev++) {
04250                 chosen[lev] = RARRAY_PTR(ary)[stack[lev+1] = stack[lev]+1];
04251             }
04252             rb_yield(rb_ary_new4(n, chosen));
04253             if (RBASIC(t0)->klass) {
04254                 rb_raise(rb_eRuntimeError, "combination reentered");
04255             }
04256             do {
04257                 if (lev == 0) goto done;
04258                 stack[lev--]++;
04259             } while (stack[lev+1]+n == len+lev+1);
04260         }
04261     done:
04262         tmpbuf_discard(t0);
04263         tmpary_discard(cc);
04264     }
04265     return ary;
04266 }
04267 
04268 /*
04269  * Recursively compute repeated permutations of r elements of the set
04270  * [0..n-1].
04271  * When we have a complete repeated permutation of array indexes, copy the
04272  * values at those indexes into a new array and yield that array.
04273  *
04274  * n: the size of the set
04275  * r: the number of elements in each permutation
04276  * p: the array (of size r) that we're filling in
04277  * index: what index we're filling in now
04278  * values: the Ruby array that holds the actual values to permute
04279  */
04280 static void
04281 rpermute0(long n, long r, long *p, long index, VALUE values)
04282 {
04283     long i, j;
04284     for (i = 0; i < n; i++) {
04285         p[index] = i;
04286         if (index < r-1) {              /* if not done yet */
04287             rpermute0(n, r, p, index+1, values); /* recurse */
04288         }
04289         else {
04290             /* We have a complete permutation of array indexes */
04291             /* Build a ruby array of the corresponding values */
04292             /* And yield it to the associated block */
04293             VALUE result = rb_ary_new2(r);
04294             VALUE *result_array = RARRAY_PTR(result);
04295             const VALUE *values_array = RARRAY_PTR(values);
04296 
04297             for (j = 0; j < r; j++) result_array[j] = values_array[p[j]];
04298             ARY_SET_LEN(result, r);
04299             rb_yield(result);
04300             if (RBASIC(values)->klass) {
04301                 rb_raise(rb_eRuntimeError, "repeated permute reentered");
04302             }
04303         }
04304     }
04305 }
04306 
04307 /*
04308  *  call-seq:
04309  *     ary.repeated_permutation(n) { |p| block } -> ary
04310  *     ary.repeated_permutation(n)               -> an_enumerator
04311  *
04312  * When invoked with a block, yield all repeated permutations of length
04313  * <i>n</i> of the elements of <i>ary</i>, then return the array itself.
04314  * The implementation makes no guarantees about the order in which
04315  * the repeated permutations are yielded.
04316  *
04317  * If no block is given, an enumerator is returned instead.
04318  *
04319  * Examples:
04320  *
04321  *     a = [1, 2]
04322  *     a.repeated_permutation(1).to_a  #=> [[1], [2]]
04323  *     a.repeated_permutation(2).to_a  #=> [[1,1],[1,2],[2,1],[2,2]]
04324  *     a.repeated_permutation(3).to_a  #=> [[1,1,1],[1,1,2],[1,2,1],[1,2,2],
04325  *                                     #    [2,1,1],[2,1,2],[2,2,1],[2,2,2]]
04326  *     a.repeated_permutation(0).to_a  #=> [[]] # one permutation of length 0
04327  */
04328 
04329 static VALUE
04330 rb_ary_repeated_permutation(VALUE ary, VALUE num)
04331 {
04332     long r, n, i;
04333 
04334     n = RARRAY_LEN(ary);                  /* Array length */
04335     RETURN_ENUMERATOR(ary, 1, &num);      /* Return enumerator if no block */
04336     r = NUM2LONG(num);                    /* Permutation size from argument */
04337 
04338     if (r < 0) {
04339         /* no permutations: yield nothing */
04340     }
04341     else if (r == 0) { /* exactly one permutation: the zero-length array */
04342         rb_yield(rb_ary_new2(0));
04343     }
04344     else if (r == 1) { /* this is a special, easy case */
04345         for (i = 0; i < RARRAY_LEN(ary); i++) {
04346             rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
04347         }
04348     }
04349     else {             /* this is the general case */
04350         volatile VALUE t0 = tmpbuf(r, sizeof(long));
04351         long *p = (long*)RSTRING_PTR(t0);
04352         VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
04353         RBASIC(ary0)->klass = 0;
04354 
04355         rpermute0(n, r, p, 0, ary0); /* compute and yield repeated permutations */
04356         tmpbuf_discard(t0);
04357         RBASIC(ary0)->klass = rb_cArray;
04358     }
04359     return ary;
04360 }
04361 
04362 static void
04363 rcombinate0(long n, long r, long *p, long index, long rest, VALUE values)
04364 {
04365     long j;
04366     if (rest > 0) {
04367         for (; index < n; ++index) {
04368             p[r-rest] = index;
04369             rcombinate0(n, r, p, index, rest-1, values);
04370         }
04371     }
04372     else {
04373         VALUE result = rb_ary_new2(r);
04374         VALUE *result_array = RARRAY_PTR(result);
04375         const VALUE *values_array = RARRAY_PTR(values);
04376 
04377         for (j = 0; j < r; ++j) result_array[j] = values_array[p[j]];
04378         ARY_SET_LEN(result, r);
04379         rb_yield(result);
04380         if (RBASIC(values)->klass) {
04381             rb_raise(rb_eRuntimeError, "repeated combination reentered");
04382         }
04383     }
04384 }
04385 
04386 /*
04387  *  call-seq:
04388  *     ary.repeated_combination(n) { |c| block } -> ary
04389  *     ary.repeated_combination(n)               -> an_enumerator
04390  *
04391  * When invoked with a block, yields all repeated combinations of
04392  * length <i>n</i> of elements from <i>ary</i> and then returns
04393  * <i>ary</i> itself.
04394  * The implementation makes no guarantees about the order in which
04395  * the repeated combinations are yielded.
04396  *
04397  * If no block is given, an enumerator is returned instead.
04398  *
04399  * Examples:
04400  *
04401  *     a = [1, 2, 3]
04402  *     a.repeated_combination(1).to_a  #=> [[1], [2], [3]]
04403  *     a.repeated_combination(2).to_a  #=> [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
04404  *     a.repeated_combination(3).to_a  #=> [[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],
04405  *                                     #    [1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]]
04406  *     a.repeated_combination(4).to_a  #=> [[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,2,2],[1,1,2,3],
04407  *                                     #    [1,1,3,3],[1,2,2,2],[1,2,2,3],[1,2,3,3],[1,3,3,3],
04408  *                                     #    [2,2,2,2],[2,2,2,3],[2,2,3,3],[2,3,3,3],[3,3,3,3]]
04409  *     a.repeated_combination(0).to_a  #=> [[]] # one combination of length 0
04410  *
04411  */
04412 
04413 static VALUE
04414 rb_ary_repeated_combination(VALUE ary, VALUE num)
04415 {
04416     long n, i, len;
04417 
04418     n = NUM2LONG(num);                 /* Combination size from argument */
04419     RETURN_ENUMERATOR(ary, 1, &num);   /* Return enumerator if no block */
04420     len = RARRAY_LEN(ary);
04421     if (n < 0) {
04422         /* yield nothing */
04423     }
04424     else if (n == 0) {
04425         rb_yield(rb_ary_new2(0));
04426     }
04427     else if (n == 1) {
04428         for (i = 0; i < len; i++) {
04429             rb_yield(rb_ary_new3(1, RARRAY_PTR(ary)[i]));
04430         }
04431     }
04432     else if (len == 0) {
04433         /* yield nothing */
04434     }
04435     else {
04436         volatile VALUE t0 = tmpbuf(n, sizeof(long));
04437         long *p = (long*)RSTRING_PTR(t0);
04438         VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
04439         RBASIC(ary0)->klass = 0;
04440 
04441         rcombinate0(len, n, p, 0, n, ary0); /* compute and yield repeated combinations */
04442         tmpbuf_discard(t0);
04443         RBASIC(ary0)->klass = rb_cArray;
04444     }
04445     return ary;
04446 }
04447 
04448 /*
04449  *  call-seq:
04450  *     ary.product(other_ary, ...)                -> new_ary
04451  *     ary.product(other_ary, ...) { |p| block }  -> ary
04452  *
04453  *  Returns an array of all combinations of elements from all arrays.
04454  *  The length of the returned array is the product of the length
04455  *  of +self+ and the argument arrays.
04456  *  If given a block, <i>product</i> will yield all combinations
04457  *  and return +self+ instead.
04458  *
04459  *
04460  *     [1,2,3].product([4,5])     #=> [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]
04461  *     [1,2].product([1,2])       #=> [[1,1],[1,2],[2,1],[2,2]]
04462  *     [1,2].product([3,4],[5,6]) #=> [[1,3,5],[1,3,6],[1,4,5],[1,4,6],
04463  *                                #     [2,3,5],[2,3,6],[2,4,5],[2,4,6]]
04464  *     [1,2].product()            #=> [[1],[2]]
04465  *     [1,2].product([])          #=> []
04466  */
04467 
04468 static VALUE
04469 rb_ary_product(int argc, VALUE *argv, VALUE ary)
04470 {
04471     int n = argc+1;    /* How many arrays we're operating on */
04472     volatile VALUE t0 = tmpary(n);
04473     volatile VALUE t1 = tmpbuf(n, sizeof(int));
04474     VALUE *arrays = RARRAY_PTR(t0); /* The arrays we're computing the product of */
04475     int *counters = (int*)RSTRING_PTR(t1); /* The current position in each one */
04476     VALUE result = Qnil;      /* The array we'll be returning, when no block given */
04477     long i,j;
04478     long resultlen = 1;
04479 
04480     RBASIC(t0)->klass = 0;
04481     RBASIC(t1)->klass = 0;
04482 
04483     /* initialize the arrays of arrays */
04484     ARY_SET_LEN(t0, n);
04485     arrays[0] = ary;
04486     for (i = 1; i < n; i++) arrays[i] = Qnil;
04487     for (i = 1; i < n; i++) arrays[i] = to_ary(argv[i-1]);
04488 
04489     /* initialize the counters for the arrays */
04490     for (i = 0; i < n; i++) counters[i] = 0;
04491 
04492     /* Otherwise, allocate and fill in an array of results */
04493     if (rb_block_given_p()) {
04494         /* Make defensive copies of arrays; exit if any is empty */
04495         for (i = 0; i < n; i++) {
04496             if (RARRAY_LEN(arrays[i]) == 0) goto done;
04497             arrays[i] = ary_make_shared_copy(arrays[i]);
04498         }
04499     }
04500     else {
04501         /* Compute the length of the result array; return [] if any is empty */
04502         for (i = 0; i < n; i++) {
04503             long k = RARRAY_LEN(arrays[i]), l = resultlen;
04504             if (k == 0) {
04505                 result = rb_ary_new2(0);
04506                 goto done;
04507             }
04508             resultlen *= k;
04509             if (resultlen < k || resultlen < l || resultlen / k != l) {
04510                 rb_raise(rb_eRangeError, "too big to product");
04511             }
04512         }
04513         result = rb_ary_new2(resultlen);
04514     }
04515     for (;;) {
04516         int m;
04517         /* fill in one subarray */
04518         VALUE subarray = rb_ary_new2(n);
04519         for (j = 0; j < n; j++) {
04520             rb_ary_push(subarray, rb_ary_entry(arrays[j], counters[j]));
04521         }
04522 
04523         /* put it on the result array */
04524         if(NIL_P(result)) {
04525             FL_SET(t0, FL_USER5);
04526             rb_yield(subarray);
04527             if (! FL_TEST(t0, FL_USER5)) {
04528                 rb_raise(rb_eRuntimeError, "product reentered");
04529             }
04530             else {
04531                 FL_UNSET(t0, FL_USER5);
04532             }
04533         }
04534         else {
04535             rb_ary_push(result, subarray);
04536         }
04537 
04538         /*
04539          * Increment the last counter.  If it overflows, reset to 0
04540          * and increment the one before it.
04541          */
04542         m = n-1;
04543         counters[m]++;
04544         while (counters[m] == RARRAY_LEN(arrays[m])) {
04545             counters[m] = 0;
04546             /* If the first counter overflows, we are done */
04547             if (--m < 0) goto done;
04548             counters[m]++;
04549         }
04550     }
04551 done:
04552     tmpary_discard(t0);
04553     tmpbuf_discard(t1);
04554 
04555     return NIL_P(result) ? ary : result;
04556 }
04557 
04558 /*
04559  *  call-seq:
04560  *     ary.take(n)               -> new_ary
04561  *
04562  *  Returns first n elements from <i>ary</i>.
04563  *
04564  *     a = [1, 2, 3, 4, 5, 0]
04565  *     a.take(3)             #=> [1, 2, 3]
04566  *
04567  */
04568 
04569 static VALUE
04570 rb_ary_take(VALUE obj, VALUE n)
04571 {
04572     long len = NUM2LONG(n);
04573     if (len < 0) {
04574         rb_raise(rb_eArgError, "attempt to take negative size");
04575     }
04576     return rb_ary_subseq(obj, 0, len);
04577 }
04578 
04579 /*
04580  *  call-seq:
04581  *     ary.take_while {|arr| block }   -> new_ary
04582  *     ary.take_while                  -> an_enumerator
04583  *
04584  *  Passes elements to the block until the block returns +nil+ or +false+,
04585  *  then stops iterating and returns an array of all prior elements.
04586  *
04587  *  If no block is given, an enumerator is returned instead.
04588  *
04589  *     a = [1, 2, 3, 4, 5, 0]
04590  *     a.take_while {|i| i < 3 }   #=> [1, 2]
04591  *
04592  */
04593 
04594 static VALUE
04595 rb_ary_take_while(VALUE ary)
04596 {
04597     long i;
04598 
04599     RETURN_ENUMERATOR(ary, 0, 0);
04600     for (i = 0; i < RARRAY_LEN(ary); i++) {
04601         if (!RTEST(rb_yield(RARRAY_PTR(ary)[i]))) break;
04602     }
04603     return rb_ary_take(ary, LONG2FIX(i));
04604 }
04605 
04606 /*
04607  *  call-seq:
04608  *     ary.drop(n)               -> new_ary
04609  *
04610  *  Drops first n elements from +ary+ and returns the rest of
04611  *  the elements in an array.
04612  *
04613  *     a = [1, 2, 3, 4, 5, 0]
04614  *     a.drop(3)             #=> [4, 5, 0]
04615  *
04616  */
04617 
04618 static VALUE
04619 rb_ary_drop(VALUE ary, VALUE n)
04620 {
04621     VALUE result;
04622     long pos = NUM2LONG(n);
04623     if (pos < 0) {
04624         rb_raise(rb_eArgError, "attempt to drop negative size");
04625     }
04626 
04627     result = rb_ary_subseq(ary, pos, RARRAY_LEN(ary));
04628     if (result == Qnil) result = rb_ary_new();
04629     return result;
04630 }
04631 
04632 /*
04633  *  call-seq:
04634  *     ary.drop_while {|arr| block }   -> new_ary
04635  *     ary.drop_while                  -> an_enumerator
04636  *
04637  *  Drops elements up to, but not including, the first element for
04638  *  which the block returns +nil+ or +false+ and returns an array
04639  *  containing the remaining elements.
04640  *
04641  *  If no block is given, an enumerator is returned instead.
04642  *
04643  *     a = [1, 2, 3, 4, 5, 0]
04644  *     a.drop_while {|i| i < 3 }   #=> [3, 4, 5, 0]
04645  *
04646  */
04647 
04648 static VALUE
04649 rb_ary_drop_while(VALUE ary)
04650 {
04651     long i;
04652 
04653     RETURN_ENUMERATOR(ary, 0, 0);
04654     for (i = 0; i < RARRAY_LEN(ary); i++) {
04655         if (!RTEST(rb_yield(RARRAY_PTR(ary)[i]))) break;
04656     }
04657     return rb_ary_drop(ary, LONG2FIX(i));
04658 }
04659 
04660 
04661 
04662 /* Arrays are ordered, integer-indexed collections of any object.
04663  * Array indexing starts at 0, as in C or Java.  A negative index is
04664  * assumed to be relative to the end of the array---that is, an index of -1
04665  * indicates the last element of the array, -2 is the next to last
04666  * element in the array, and so on.
04667  */
04668 
04669 void
04670 Init_Array(void)
04671 {
04672 #undef rb_intern
04673 #define rb_intern(str) rb_intern_const(str)
04674 
04675     rb_cArray  = rb_define_class("Array", rb_cObject);
04676     rb_include_module(rb_cArray, rb_mEnumerable);
04677 
04678     rb_define_alloc_func(rb_cArray, ary_alloc);
04679     rb_define_singleton_method(rb_cArray, "[]", rb_ary_s_create, -1);
04680     rb_define_singleton_method(rb_cArray, "try_convert", rb_ary_s_try_convert, 1);
04681     rb_define_method(rb_cArray, "initialize", rb_ary_initialize, -1);
04682     rb_define_method(rb_cArray, "initialize_copy", rb_ary_replace, 1);
04683 
04684     rb_define_method(rb_cArray, "inspect", rb_ary_inspect, 0);
04685     rb_define_alias(rb_cArray,  "to_s", "inspect");
04686     rb_define_method(rb_cArray, "to_a", rb_ary_to_a, 0);
04687     rb_define_method(rb_cArray, "to_ary", rb_ary_to_ary_m, 0);
04688     rb_define_method(rb_cArray, "frozen?",  rb_ary_frozen_p, 0);
04689 
04690     rb_define_method(rb_cArray, "==", rb_ary_equal, 1);
04691     rb_define_method(rb_cArray, "eql?", rb_ary_eql, 1);
04692     rb_define_method(rb_cArray, "hash", rb_ary_hash, 0);
04693 
04694     rb_define_method(rb_cArray, "[]", rb_ary_aref, -1);
04695     rb_define_method(rb_cArray, "[]=", rb_ary_aset, -1);
04696     rb_define_method(rb_cArray, "at", rb_ary_at, 1);
04697     rb_define_method(rb_cArray, "fetch", rb_ary_fetch, -1);
04698     rb_define_method(rb_cArray, "first", rb_ary_first, -1);
04699     rb_define_method(rb_cArray, "last", rb_ary_last, -1);
04700     rb_define_method(rb_cArray, "concat", rb_ary_concat, 1);
04701     rb_define_method(rb_cArray, "<<", rb_ary_push, 1);
04702     rb_define_method(rb_cArray, "push", rb_ary_push_m, -1);
04703     rb_define_method(rb_cArray, "pop", rb_ary_pop_m, -1);
04704     rb_define_method(rb_cArray, "shift", rb_ary_shift_m, -1);
04705     rb_define_method(rb_cArray, "unshift", rb_ary_unshift_m, -1);
04706     rb_define_method(rb_cArray, "insert", rb_ary_insert, -1);
04707     rb_define_method(rb_cArray, "each", rb_ary_each, 0);
04708     rb_define_method(rb_cArray, "each_index", rb_ary_each_index, 0);
04709     rb_define_method(rb_cArray, "reverse_each", rb_ary_reverse_each, 0);
04710     rb_define_method(rb_cArray, "length", rb_ary_length, 0);
04711     rb_define_alias(rb_cArray,  "size", "length");
04712     rb_define_method(rb_cArray, "empty?", rb_ary_empty_p, 0);
04713     rb_define_method(rb_cArray, "find_index", rb_ary_index, -1);
04714     rb_define_method(rb_cArray, "index", rb_ary_index, -1);
04715     rb_define_method(rb_cArray, "rindex", rb_ary_rindex, -1);
04716     rb_define_method(rb_cArray, "join", rb_ary_join_m, -1);
04717     rb_define_method(rb_cArray, "reverse", rb_ary_reverse_m, 0);
04718     rb_define_method(rb_cArray, "reverse!", rb_ary_reverse_bang, 0);
04719     rb_define_method(rb_cArray, "rotate", rb_ary_rotate_m, -1);
04720     rb_define_method(rb_cArray, "rotate!", rb_ary_rotate_bang, -1);
04721     rb_define_method(rb_cArray, "sort", rb_ary_sort, 0);
04722     rb_define_method(rb_cArray, "sort!", rb_ary_sort_bang, 0);
04723     rb_define_method(rb_cArray, "sort_by!", rb_ary_sort_by_bang, 0);
04724     rb_define_method(rb_cArray, "collect", rb_ary_collect, 0);
04725     rb_define_method(rb_cArray, "collect!", rb_ary_collect_bang, 0);
04726     rb_define_method(rb_cArray, "map", rb_ary_collect, 0);
04727     rb_define_method(rb_cArray, "map!", rb_ary_collect_bang, 0);
04728     rb_define_method(rb_cArray, "select", rb_ary_select, 0);
04729     rb_define_method(rb_cArray, "select!", rb_ary_select_bang, 0);
04730     rb_define_method(rb_cArray, "keep_if", rb_ary_keep_if, 0);
04731     rb_define_method(rb_cArray, "values_at", rb_ary_values_at, -1);
04732     rb_define_method(rb_cArray, "delete", rb_ary_delete, 1);
04733     rb_define_method(rb_cArray, "delete_at", rb_ary_delete_at_m, 1);
04734     rb_define_method(rb_cArray, "delete_if", rb_ary_delete_if, 0);
04735     rb_define_method(rb_cArray, "reject", rb_ary_reject, 0);
04736     rb_define_method(rb_cArray, "reject!", rb_ary_reject_bang, 0);
04737     rb_define_method(rb_cArray, "zip", rb_ary_zip, -1);
04738     rb_define_method(rb_cArray, "transpose", rb_ary_transpose, 0);
04739     rb_define_method(rb_cArray, "replace", rb_ary_replace, 1);
04740     rb_define_method(rb_cArray, "clear", rb_ary_clear, 0);
04741     rb_define_method(rb_cArray, "fill", rb_ary_fill, -1);
04742     rb_define_method(rb_cArray, "include?", rb_ary_includes, 1);
04743     rb_define_method(rb_cArray, "<=>", rb_ary_cmp, 1);
04744 
04745     rb_define_method(rb_cArray, "slice", rb_ary_aref, -1);
04746     rb_define_method(rb_cArray, "slice!", rb_ary_slice_bang, -1);
04747 
04748     rb_define_method(rb_cArray, "assoc", rb_ary_assoc, 1);
04749     rb_define_method(rb_cArray, "rassoc", rb_ary_rassoc, 1);
04750 
04751     rb_define_method(rb_cArray, "+", rb_ary_plus, 1);
04752     rb_define_method(rb_cArray, "*", rb_ary_times, 1);
04753 
04754     rb_define_method(rb_cArray, "-", rb_ary_diff, 1);
04755     rb_define_method(rb_cArray, "&", rb_ary_and, 1);
04756     rb_define_method(rb_cArray, "|", rb_ary_or, 1);
04757 
04758     rb_define_method(rb_cArray, "uniq", rb_ary_uniq, 0);
04759     rb_define_method(rb_cArray, "uniq!", rb_ary_uniq_bang, 0);
04760     rb_define_method(rb_cArray, "compact", rb_ary_compact, 0);
04761     rb_define_method(rb_cArray, "compact!", rb_ary_compact_bang, 0);
04762     rb_define_method(rb_cArray, "flatten", rb_ary_flatten, -1);
04763     rb_define_method(rb_cArray, "flatten!", rb_ary_flatten_bang, -1);
04764     rb_define_method(rb_cArray, "count", rb_ary_count, -1);
04765     rb_define_method(rb_cArray, "shuffle!", rb_ary_shuffle_bang, -1);
04766     rb_define_method(rb_cArray, "shuffle", rb_ary_shuffle, -1);
04767     rb_define_method(rb_cArray, "sample", rb_ary_sample, -1);
04768     rb_define_method(rb_cArray, "cycle", rb_ary_cycle, -1);
04769     rb_define_method(rb_cArray, "permutation", rb_ary_permutation, -1);
04770     rb_define_method(rb_cArray, "combination", rb_ary_combination, 1);
04771     rb_define_method(rb_cArray, "repeated_permutation", rb_ary_repeated_permutation, 1);
04772     rb_define_method(rb_cArray, "repeated_combination", rb_ary_repeated_combination, 1);
04773     rb_define_method(rb_cArray, "product", rb_ary_product, -1);
04774 
04775     rb_define_method(rb_cArray, "take", rb_ary_take, 1);
04776     rb_define_method(rb_cArray, "take_while", rb_ary_take_while, 0);
04777     rb_define_method(rb_cArray, "drop", rb_ary_drop, 1);
04778     rb_define_method(rb_cArray, "drop_while", rb_ary_drop_while, 0);
04779 
04780     id_cmp = rb_intern("<=>");
04781     sym_random = ID2SYM(rb_intern("random"));
04782 }
04783