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