The Ruby Cross Reference

Implementation: mri jruby rubinius
Version: 1.8.7-p374 1.9.1-p431 1.9.2-p381 1.9.3-p547 2.0.0-p481 2.1.0 2.1.1 2.1.2 HEAD
001 /**********************************************************************
002 
003   array.c -
004 
005   $Author$
006   created at: Fri Aug  6 09:46:12 JST 1993
007 
008   Copyright (C) 1993-2007 Yukihiro Matsumoto
009   Copyright (C) 2000  Network Applied Communication Laboratory, Inc.
010   Copyright (C) 2000  Information-technology Promotion Agency, Japan
011 
012 **********************************************************************/
013 
014 #include "ruby/ruby.h"
015 #include "ruby/util.h"
016 #include "ruby/st.h"
017 #include "ruby/encoding.h"
018 #include "internal.h"
019 #include "probes.h"
020 #include "id.h"
021 
022 #ifndef ARRAY_DEBUG
023 # define NDEBUG
024 #endif
025 #include <assert.h>
026 
027 VALUE rb_cArray;
028 
029 static ID id_cmp, id_div, id_power;
030 
031 #define ARY_DEFAULT_SIZE 16
032 #define ARY_MAX_SIZE (LONG_MAX / (int)sizeof(VALUE))
033 
034 void
035 rb_mem_clear(register VALUE *mem, register long size)
036 {
037     while (size--) {
038         *mem++ = Qnil;
039     }
040 }
041 
042 static inline void
043 memfill(register VALUE *mem, register long size, register VALUE val)
044 {
045     while (size--) {
046         *mem++ = val;
047     }
048 }
049 
050 # define ARY_SHARED_P(ary) \
051     (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
052      FL_TEST((ary),ELTS_SHARED)!=0)
053 # define ARY_EMBED_P(ary) \
054     (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
055      FL_TEST((ary), RARRAY_EMBED_FLAG)!=0)
056 
057 #define ARY_HEAP_PTR(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.ptr)
058 #define ARY_HEAP_LEN(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.len)
059 #define ARY_EMBED_PTR(a) (assert(ARY_EMBED_P(a)), RARRAY(a)->as.ary)
060 #define ARY_EMBED_LEN(a) \
061     (assert(ARY_EMBED_P(a)), \
062      (long)((RBASIC(a)->flags >> RARRAY_EMBED_LEN_SHIFT) & \
063          (RARRAY_EMBED_LEN_MASK >> RARRAY_EMBED_LEN_SHIFT)))
064 
065 #define ARY_OWNS_HEAP_P(a) (!FL_TEST((a), ELTS_SHARED|RARRAY_EMBED_FLAG))
066 #define FL_SET_EMBED(a) do { \
067     assert(!ARY_SHARED_P(a)); \
068     FL_SET((a), RARRAY_EMBED_FLAG); \
069 } while (0)
070 #define FL_UNSET_EMBED(ary) FL_UNSET((ary), RARRAY_EMBED_FLAG|RARRAY_EMBED_LEN_MASK)
071 #define FL_SET_SHARED(ary) do { \
072     assert(!ARY_EMBED_P(ary)); \
073     FL_SET((ary), ELTS_SHARED); \
074 } while (0)
075 #define FL_UNSET_SHARED(ary) FL_UNSET((ary), ELTS_SHARED)
076 
077 #define ARY_SET_PTR(ary, p) do { \
078     assert(!ARY_EMBED_P(ary)); \
079     assert(!OBJ_FROZEN(ary)); \
080     RARRAY(ary)->as.heap.ptr = (p); \
081 } while (0)
082 #define ARY_SET_EMBED_LEN(ary, n) do { \
083     long tmp_n = (n); \
084     assert(ARY_EMBED_P(ary)); \
085     assert(!OBJ_FROZEN(ary)); \
086     RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK; \
087     RBASIC(ary)->flags |= (tmp_n) << RARRAY_EMBED_LEN_SHIFT; \
088 } while (0)
089 #define ARY_SET_HEAP_LEN(ary, n) do { \
090     assert(!ARY_EMBED_P(ary)); \
091     RARRAY(ary)->as.heap.len = (n); \
092 } while (0)
093 #define ARY_SET_LEN(ary, n) do { \
094     if (ARY_EMBED_P(ary)) { \
095         ARY_SET_EMBED_LEN((ary), (n)); \
096     } \
097     else { \
098         ARY_SET_HEAP_LEN((ary), (n)); \
099     } \
100     assert(RARRAY_LEN(ary) == (n)); \
101 } while (0)
102 #define ARY_INCREASE_PTR(ary, n) do  { \
103     assert(!ARY_EMBED_P(ary)); \
104     assert(!OBJ_FROZEN(ary)); \
105     RARRAY(ary)->as.heap.ptr += (n); \
106 } while (0)
107 #define ARY_INCREASE_LEN(ary, n) do  { \
108     assert(!OBJ_FROZEN(ary)); \
109     if (ARY_EMBED_P(ary)) { \
110         ARY_SET_EMBED_LEN((ary), RARRAY_LEN(ary)+(n)); \
111     } \
112     else { \
113         RARRAY(ary)->as.heap.len += (n); \
114     } \
115 } while (0)
116 
117 #define ARY_CAPA(ary) (ARY_EMBED_P(ary) ? RARRAY_EMBED_LEN_MAX : \
118                        ARY_SHARED_ROOT_P(ary) ? RARRAY_LEN(ary) : RARRAY(ary)->as.heap.aux.capa)
119 #define ARY_SET_CAPA(ary, n) do { \
120     assert(!ARY_EMBED_P(ary)); \
121     assert(!ARY_SHARED_P(ary)); \
122     assert(!OBJ_FROZEN(ary)); \
123     RARRAY(ary)->as.heap.aux.capa = (n); \
124 } while (0)
125 
126 #define ARY_SHARED(ary) (assert(ARY_SHARED_P(ary)), RARRAY(ary)->as.heap.aux.shared)
127 #define ARY_SET_SHARED(ary, value) do { \
128     const VALUE _ary_ = (ary); \
129     const VALUE _value_ = (value); \
130     assert(!ARY_EMBED_P(_ary_)); \
131     assert(ARY_SHARED_P(_ary_)); \
132     assert(ARY_SHARED_ROOT_P(_value_)); \
133     OBJ_WRITE(_ary_, &RARRAY(_ary_)->as.heap.aux.shared, _value_); \
134 } while (0)
135 #define RARRAY_SHARED_ROOT_FLAG FL_USER5
136 #define ARY_SHARED_ROOT_P(ary) (FL_TEST((ary), RARRAY_SHARED_ROOT_FLAG))
137 #define ARY_SHARED_NUM(ary) \
138     (assert(ARY_SHARED_ROOT_P(ary)), RARRAY(ary)->as.heap.aux.capa)
139 #define ARY_SET_SHARED_NUM(ary, value) do { \
140     assert(ARY_SHARED_ROOT_P(ary)); \
141     RARRAY(ary)->as.heap.aux.capa = (value); \
142 } while (0)
143 #define FL_SET_SHARED_ROOT(ary) do { \
144     assert(!ARY_EMBED_P(ary)); \
145     FL_SET((ary), RARRAY_SHARED_ROOT_FLAG); \
146 } while (0)
147 
148 static void
149 ary_resize_capa(VALUE ary, long capacity)
150 {
151     assert(RARRAY_LEN(ary) <= capacity);
152     assert(!OBJ_FROZEN(ary));
153     assert(!ARY_SHARED_P(ary));
154     if (capacity > RARRAY_EMBED_LEN_MAX) {
155         if (ARY_EMBED_P(ary)) {
156             long len = ARY_EMBED_LEN(ary);
157             VALUE *ptr = ALLOC_N(VALUE, (capacity));
158             MEMCPY(ptr, ARY_EMBED_PTR(ary), VALUE, len);
159             FL_UNSET_EMBED(ary);
160             ARY_SET_PTR(ary, ptr);
161             ARY_SET_HEAP_LEN(ary, len);
162         }
163         else {
164             REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, (capacity));
165         }
166         ARY_SET_CAPA(ary, (capacity));
167     }
168     else {
169         if (!ARY_EMBED_P(ary)) {
170             long len = RARRAY_LEN(ary);
171             VALUE *ptr = RARRAY_PTR(ary);
172             if (len > capacity) len = capacity;
173             MEMCPY((VALUE *)RARRAY(ary)->as.ary, ptr, VALUE, len);
174             FL_SET_EMBED(ary);
175             ARY_SET_LEN(ary, len);
176             xfree(ptr);
177         }
178     }
179 }
180 
181 static inline void
182 ary_shrink_capa(VALUE ary)
183 {
184     long capacity = ARY_HEAP_LEN(ary);
185     long old_capa = RARRAY(ary)->as.heap.aux.capa;
186     assert(!ARY_SHARED_P(ary));
187     assert(old_capa >= capacity);
188     if (old_capa > capacity)
189         REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, capacity);
190 }
191 
192 static void
193 ary_double_capa(VALUE ary, long min)
194 {
195     long new_capa = ARY_CAPA(ary) / 2;
196 
197     if (new_capa < ARY_DEFAULT_SIZE) {
198         new_capa = ARY_DEFAULT_SIZE;
199     }
200     if (new_capa >= ARY_MAX_SIZE - min) {
201         new_capa = (ARY_MAX_SIZE - min) / 2;
202     }
203     new_capa += min;
204     ary_resize_capa(ary, new_capa);
205 }
206 
207 static void
208 rb_ary_decrement_share(VALUE shared)
209 {
210     if (shared) {
211         long num = ARY_SHARED_NUM(shared) - 1;
212         if (num == 0) {
213             rb_ary_free(shared);
214             rb_gc_force_recycle(shared);
215         }
216         else if (num > 0) {
217             ARY_SET_SHARED_NUM(shared, num);
218         }
219     }
220 }
221 
222 static void
223 rb_ary_unshare(VALUE ary)
224 {
225     VALUE shared = RARRAY(ary)->as.heap.aux.shared;
226     rb_ary_decrement_share(shared);
227     FL_UNSET_SHARED(ary);
228 }
229 
230 static inline void
231 rb_ary_unshare_safe(VALUE ary)
232 {
233     if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
234         rb_ary_unshare(ary);
235     }
236 }
237 
238 static VALUE
239 rb_ary_increment_share(VALUE shared)
240 {
241     long num = ARY_SHARED_NUM(shared);
242     if (num >= 0) {
243         ARY_SET_SHARED_NUM(shared, num + 1);
244     }
245     return shared;
246 }
247 
248 static void
249 rb_ary_set_shared(VALUE ary, VALUE shared)
250 {
251     rb_ary_increment_share(shared);
252     FL_SET_SHARED(ary);
253     ARY_SET_SHARED(ary, shared);
254 }
255 
256 static inline void
257 rb_ary_modify_check(VALUE ary)
258 {
259     rb_check_frozen(ary);
260 }
261 
262 void
263 rb_ary_modify(VALUE ary)
264 {
265     rb_ary_modify_check(ary);
266     if (ARY_SHARED_P(ary)) {
267         long len = RARRAY_LEN(ary);
268         VALUE shared = ARY_SHARED(ary);
269         if (len <= RARRAY_EMBED_LEN_MAX) {
270             const VALUE *ptr = ARY_HEAP_PTR(ary);
271             FL_UNSET_SHARED(ary);
272             FL_SET_EMBED(ary);
273             MEMCPY((VALUE *)ARY_EMBED_PTR(ary), ptr, VALUE, len);
274             rb_ary_decrement_share(shared);
275             ARY_SET_EMBED_LEN(ary, len);
276         }
277         else if (ARY_SHARED_NUM(shared) == 1 && len > (RARRAY_LEN(shared)>>1)) {
278             long shift = RARRAY_PTR(ary) - RARRAY_PTR(shared);
279             FL_UNSET_SHARED(ary);
280             ARY_SET_PTR(ary, RARRAY_PTR(shared));
281             ARY_SET_CAPA(ary, RARRAY_LEN(shared));
282             MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+shift, VALUE, len);
283             FL_SET_EMBED(shared);
284             rb_ary_decrement_share(shared);
285         }
286         else {
287             VALUE *ptr = ALLOC_N(VALUE, len);
288             MEMCPY(ptr, RARRAY_PTR(ary), VALUE, len);
289             rb_ary_unshare(ary);
290             ARY_SET_CAPA(ary, len);
291             ARY_SET_PTR(ary, ptr);
292         }
293     }
294 }
295 
296 static void
297 ary_ensure_room_for_push(VALUE ary, long add_len)
298 {
299     long new_len = RARRAY_LEN(ary) + add_len;
300     long capa;
301 
302     if (ARY_SHARED_P(ary)) {
303         if (new_len > RARRAY_EMBED_LEN_MAX) {
304             VALUE shared = ARY_SHARED(ary);
305             if (ARY_SHARED_NUM(shared) == 1) {
306                 if (RARRAY_PTR(ary) - RARRAY_PTR(shared) + new_len <= RARRAY_LEN(shared)) {
307                     rb_ary_modify_check(ary);
308                 }
309                 else {
310                     /* if array is shared, then it is likely it participate in push/shift pattern */
311                     rb_ary_modify(ary);
312                     capa = ARY_CAPA(ary);
313                     if (new_len > capa - (capa >> 6)) {
314                         ary_double_capa(ary, new_len);
315                     }
316                 }
317                 return;
318             }
319         }
320     }
321     rb_ary_modify(ary);
322     capa = ARY_CAPA(ary);
323     if (new_len > capa) {
324         ary_double_capa(ary, new_len);
325     }
326 }
327 
328 /*
329  *  call-seq:
330  *      ary.freeze -> ary
331  *
332  *  Calls Object#freeze on +ary+ to prevent any further
333  *  modification. A RuntimeError will be raised if a modification
334  *  attempt is made.
335  *
336  */
337 
338 VALUE
339 rb_ary_freeze(VALUE ary)
340 {
341     return rb_obj_freeze(ary);
342 }
343 
344 /*
345  *  call-seq:
346  *     ary.frozen?  -> true or false
347  *
348  *  Return +true+ if this array is frozen (or temporarily frozen
349  *  while being sorted). See also Object#frozen?
350  */
351 
352 static VALUE
353 rb_ary_frozen_p(VALUE ary)
354 {
355     if (OBJ_FROZEN(ary)) return Qtrue;
356     return Qfalse;
357 }
358 
359 /* This can be used to take a snapshot of an array (with
360    e.g. rb_ary_replace) and check later whether the array has been
361    modified from the snapshot.  The snapshot is cheap, though if
362    something does modify the array it will pay the cost of copying
363    it.  If Array#pop or Array#shift has been called, the array will
364    be still shared with the snapshot, but the array length will
365    differ. */
366 VALUE
367 rb_ary_shared_with_p(VALUE ary1, VALUE ary2)
368 {
369     if (!ARY_EMBED_P(ary1) && ARY_SHARED_P(ary1) &&
370         !ARY_EMBED_P(ary2) && ARY_SHARED_P(ary2) &&
371         RARRAY(ary1)->as.heap.aux.shared == RARRAY(ary2)->as.heap.aux.shared &&
372         RARRAY(ary1)->as.heap.len == RARRAY(ary2)->as.heap.len) {
373         return Qtrue;
374     }
375     return Qfalse;
376 }
377 
378 static VALUE
379 ary_alloc(VALUE klass)
380 {
381     NEWOBJ_OF(ary, struct RArray, klass, T_ARRAY | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0));
382     FL_SET_EMBED((VALUE)ary);
383     ARY_SET_EMBED_LEN((VALUE)ary, 0);
384 
385     return (VALUE)ary;
386 }
387 
388 static VALUE
389 empty_ary_alloc(VALUE klass)
390 {
391     if (RUBY_DTRACE_ARRAY_CREATE_ENABLED()) {
392         RUBY_DTRACE_ARRAY_CREATE(0, rb_sourcefile(), rb_sourceline());
393     }
394 
395     return ary_alloc(klass);
396 }
397 
398 static VALUE
399 ary_new(VALUE klass, long capa)
400 {
401     VALUE ary,*ptr;
402 
403     if (capa < 0) {
404         rb_raise(rb_eArgError, "negative array size (or size too big)");
405     }
406     if (capa > ARY_MAX_SIZE) {
407         rb_raise(rb_eArgError, "array size too big");
408     }
409 
410     if (RUBY_DTRACE_ARRAY_CREATE_ENABLED()) {
411         RUBY_DTRACE_ARRAY_CREATE(capa, rb_sourcefile(), rb_sourceline());
412     }
413 
414     if (capa > RARRAY_EMBED_LEN_MAX) {
415         ptr = ALLOC_N(VALUE, capa);
416         ary = ary_alloc(klass);
417         FL_UNSET_EMBED(ary);
418         ARY_SET_PTR(ary, ptr);
419         ARY_SET_CAPA(ary, capa);
420         ARY_SET_HEAP_LEN(ary, 0);
421     }
422     else {
423         ary = ary_alloc(klass);
424     }
425 
426     return ary;
427 }
428 
429 VALUE
430 rb_ary_new_capa(long capa)
431 {
432     return ary_new(rb_cArray, capa);
433 }
434 
435 VALUE
436 rb_ary_new(void)
437 {
438     return rb_ary_new2(RARRAY_EMBED_LEN_MAX);
439 }
440 
441 VALUE
442 rb_ary_new_from_args(long n, ...)
443 {
444     va_list ar;
445     VALUE ary;
446     long i;
447 
448     ary = rb_ary_new2(n);
449 
450     va_start(ar, n);
451     for (i=0; i<n; i++) {
452         RARRAY_ASET(ary, i, va_arg(ar, VALUE));
453     }
454     va_end(ar);
455 
456     ARY_SET_LEN(ary, n);
457     return ary;
458 }
459 
460 VALUE
461 rb_ary_new_from_values(long n, const VALUE *elts)
462 {
463     VALUE ary;
464 
465     ary = rb_ary_new2(n);
466     if (n > 0 && elts) {
467         assert(!OBJ_PROMOTED(ary));
468         RARRAY_PTR_USE(ary, ptr, {
469             MEMCPY(ptr, elts, VALUE, n); /* new array is not old gen */
470         });
471         ARY_SET_LEN(ary, n);
472     }
473 
474     return ary;
475 }
476 
477 VALUE
478 rb_ary_tmp_new(long capa)
479 {
480     return ary_new(0, capa);
481 }
482 
483 void
484 rb_ary_free(VALUE ary)
485 {
486     if (ARY_OWNS_HEAP_P(ary)) {
487         xfree((void *)ARY_HEAP_PTR(ary));
488     }
489 }
490 
491 RUBY_FUNC_EXPORTED size_t
492 rb_ary_memsize(VALUE ary)
493 {
494     if (ARY_OWNS_HEAP_P(ary)) {
495         return RARRAY(ary)->as.heap.aux.capa * sizeof(VALUE);
496     }
497     else {
498         return 0;
499     }
500 }
501 
502 static inline void
503 ary_discard(VALUE ary)
504 {
505     rb_ary_free(ary);
506     RBASIC(ary)->flags |= RARRAY_EMBED_FLAG;
507     RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK;
508 }
509 
510 static VALUE
511 ary_make_shared(VALUE ary)
512 {
513     assert(!ARY_EMBED_P(ary));
514     if (ARY_SHARED_P(ary)) {
515         return ARY_SHARED(ary);
516     }
517     else if (ARY_SHARED_ROOT_P(ary)) {
518         return ary;
519     }
520     else if (OBJ_FROZEN(ary)) {
521         ary_shrink_capa(ary);
522         FL_SET_SHARED_ROOT(ary);
523         ARY_SET_SHARED_NUM(ary, 1);
524         return ary;
525     }
526     else {
527         NEWOBJ_OF(shared, struct RArray, 0, T_ARRAY | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0));
528         FL_UNSET_EMBED(shared);
529 
530         ARY_SET_LEN((VALUE)shared, ARY_CAPA(ary));
531         ARY_SET_PTR((VALUE)shared, RARRAY_PTR(ary));
532         rb_mem_clear(RARRAY_PTR(shared) + RARRAY_LEN(ary), ARY_CAPA(ary) - RARRAY_LEN(ary));
533         FL_SET_SHARED_ROOT(shared);
534         ARY_SET_SHARED_NUM((VALUE)shared, 1);
535         FL_SET_SHARED(ary);
536         ARY_SET_SHARED(ary, (VALUE)shared);
537         OBJ_FREEZE(shared);
538         return (VALUE)shared;
539     }
540 }
541 
542 
543 static VALUE
544 ary_make_substitution(VALUE ary)
545 {
546     if (RARRAY_LEN(ary) <= RARRAY_EMBED_LEN_MAX) {
547         VALUE subst = rb_ary_new2(RARRAY_LEN(ary));
548         MEMCPY((VALUE *)ARY_EMBED_PTR(subst), RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
549         ARY_SET_EMBED_LEN(subst, RARRAY_LEN(ary));
550         return subst;
551     }
552     else {
553         return rb_ary_increment_share(ary_make_shared(ary));
554     }
555 }
556 
557 VALUE
558 rb_assoc_new(VALUE car, VALUE cdr)
559 {
560     return rb_ary_new3(2, car, cdr);
561 }
562 
563 static VALUE
564 to_ary(VALUE ary)
565 {
566     return rb_convert_type(ary, T_ARRAY, "Array", "to_ary");
567 }
568 
569 VALUE
570 rb_check_array_type(VALUE ary)
571 {
572     return rb_check_convert_type(ary, T_ARRAY, "Array", "to_ary");
573 }
574 
575 /*
576  *  call-seq:
577  *     Array.try_convert(obj) -> array or nil
578  *
579  *  Tries to convert +obj+ into an array, using +to_ary+ method.  Returns the
580  *  converted array or +nil+ if +obj+ cannot be converted for any reason.
581  *  This method can be used to check if an argument is an array.
582  *
583  *     Array.try_convert([1])   #=> [1]
584  *     Array.try_convert("1")   #=> nil
585  *
586  *     if tmp = Array.try_convert(arg)
587  *       # the argument is an array
588  *     elsif tmp = String.try_convert(arg)
589  *       # the argument is a string
590  *     end
591  *
592  */
593 
594 static VALUE
595 rb_ary_s_try_convert(VALUE dummy, VALUE ary)
596 {
597     return rb_check_array_type(ary);
598 }
599 
600 /*
601  *  call-seq:
602  *     Array.new(size=0, obj=nil)
603  *     Array.new(array)
604  *     Array.new(size) {|index| block }
605  *
606  *  Returns a new array.
607  *
608  *  In the first form, if no arguments are sent, the new array will be empty.
609  *  When a +size+ and an optional +obj+ are sent, an array is created with
610  *  +size+ copies of +obj+.  Take notice that all elements will reference the
611  *  same object +obj+.
612  *
613  *  The second form creates a copy of the array passed as a parameter (the
614  *  array is generated by calling to_ary on the parameter).
615  *
616  *    first_array = ["Matz", "Guido"]
617  *
618  *    second_array = Array.new(first_array) #=> ["Matz", "Guido"]
619  *
620  *    first_array.equal? second_array       #=> false
621  *
622  *  In the last form, an array of the given size is created.  Each element in
623  *  this array is created by passing the element's index to the given block
624  *  and storing the return value.
625  *
626  *    Array.new(3){ |index| index ** 2 }
627  *    # => [0, 1, 4]
628  *
629  *  == Common gotchas
630  *
631  *  When sending the second parameter, the same object will be used as the
632  *  value for all the array elements:
633  *
634  *     a = Array.new(2, Hash.new)
635  *     # => [{}, {}]
636  *
637  *     a[0]['cat'] = 'feline'
638  *     a # => [{"cat"=>"feline"}, {"cat"=>"feline"}]
639  *
640  *     a[1]['cat'] = 'Felix'
641  *     a # => [{"cat"=>"Felix"}, {"cat"=>"Felix"}]
642  *
643  *  Since all the Array elements store the same hash, changes to one of them
644  *  will affect them all.
645  *
646  *  If multiple copies are what you want, you should use the block
647  *  version which uses the result of that block each time an element
648  *  of the array needs to be initialized:
649  *
650  *     a = Array.new(2) { Hash.new }
651  *     a[0]['cat'] = 'feline'
652  *     a # => [{"cat"=>"feline"}, {}]
653  *
654  */
655 
656 static VALUE
657 rb_ary_initialize(int argc, VALUE *argv, VALUE ary)
658 {
659     long len;
660     VALUE size, val;
661 
662     rb_ary_modify(ary);
663     if (argc == 0) {
664         if (ARY_OWNS_HEAP_P(ary) && RARRAY_RAWPTR(ary) != 0) {
665             xfree((void *)RARRAY_RAWPTR(ary));
666         }
667         rb_ary_unshare_safe(ary);
668         FL_SET_EMBED(ary);
669         ARY_SET_EMBED_LEN(ary, 0);
670         if (rb_block_given_p()) {
671             rb_warning("given block not used");
672         }
673         return ary;
674     }
675     rb_scan_args(argc, argv, "02", &size, &val);
676     if (argc == 1 && !FIXNUM_P(size)) {
677         val = rb_check_array_type(size);
678         if (!NIL_P(val)) {
679             rb_ary_replace(ary, val);
680             return ary;
681         }
682     }
683 
684     len = NUM2LONG(size);
685     if (len < 0) {
686         rb_raise(rb_eArgError, "negative array size");
687     }
688     if (len > ARY_MAX_SIZE) {
689         rb_raise(rb_eArgError, "array size too big");
690     }
691     rb_ary_modify(ary);
692     ary_resize_capa(ary, len);
693     if (rb_block_given_p()) {
694         long i;
695 
696         if (argc == 2) {
697             rb_warn("block supersedes default value argument");
698         }
699         for (i=0; i<len; i++) {
700             rb_ary_store(ary, i, rb_yield(LONG2NUM(i)));
701             ARY_SET_LEN(ary, i + 1);
702         }
703     }
704     else {
705         RARRAY_PTR_USE(ary, ptr, {
706             memfill((VALUE *)ptr, len, val);
707         });
708         OBJ_WRITTEN(ary, Qundef, val);
709         ARY_SET_LEN(ary, len);
710     }
711     return ary;
712 }
713 
714 /*
715  * Returns a new array populated with the given objects.
716  *
717  *   Array.[]( 1, 'a', /^A/ ) # => [1, "a", /^A/]
718  *   Array[ 1, 'a', /^A/ ]    # => [1, "a", /^A/]
719  *   [ 1, 'a', /^A/ ]         # => [1, "a", /^A/]
720  */
721 
722 static VALUE
723 rb_ary_s_create(int argc, VALUE *argv, VALUE klass)
724 {
725     VALUE ary = ary_new(klass, argc);
726     if (argc > 0 && argv) {
727         MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
728         ARY_SET_LEN(ary, argc);
729     }
730 
731     return ary;
732 }
733 
734 void
735 rb_ary_store(VALUE ary, long idx, VALUE val)
736 {
737     if (idx < 0) {
738         idx += RARRAY_LEN(ary);
739         if (idx < 0) {
740             rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
741                      idx - RARRAY_LEN(ary), -RARRAY_LEN(ary));
742         }
743     }
744     else if (idx >= ARY_MAX_SIZE) {
745         rb_raise(rb_eIndexError, "index %ld too big", idx);
746     }
747 
748     rb_ary_modify(ary);
749     if (idx >= ARY_CAPA(ary)) {
750         ary_double_capa(ary, idx);
751     }
752     if (idx > RARRAY_LEN(ary)) {
753         rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary),
754                      idx-RARRAY_LEN(ary) + 1);
755     }
756 
757     if (idx >= RARRAY_LEN(ary)) {
758         ARY_SET_LEN(ary, idx + 1);
759     }
760     RARRAY_ASET(ary, idx, val);
761 }
762 
763 static VALUE
764 ary_make_partial(VALUE ary, VALUE klass, long offset, long len)
765 {
766     assert(offset >= 0);
767     assert(len >= 0);
768     assert(offset+len <= RARRAY_LEN(ary));
769 
770     if (len <= RARRAY_EMBED_LEN_MAX) {
771         VALUE result = ary_alloc(klass);
772         MEMCPY((VALUE *)ARY_EMBED_PTR(result), RARRAY_PTR(ary) + offset, VALUE, len);
773         ARY_SET_EMBED_LEN(result, len);
774         return result;
775     }
776     else {
777         VALUE shared, result = ary_alloc(klass);
778         FL_UNSET_EMBED(result);
779 
780         shared = ary_make_shared(ary);
781         ARY_SET_PTR(result, RARRAY_PTR(ary));
782         ARY_SET_LEN(result, RARRAY_LEN(ary));
783         rb_ary_set_shared(result, shared);
784 
785         ARY_INCREASE_PTR(result, offset);
786         ARY_SET_LEN(result, len);
787         return result;
788     }
789 }
790 
791 static VALUE
792 ary_make_shared_copy(VALUE ary)
793 {
794     return ary_make_partial(ary, rb_obj_class(ary), 0, RARRAY_LEN(ary));
795 }
796 
797 enum ary_take_pos_flags
798 {
799     ARY_TAKE_FIRST = 0,
800     ARY_TAKE_LAST = 1
801 };
802 
803 static VALUE
804 ary_take_first_or_last(int argc, VALUE *argv, VALUE ary, enum ary_take_pos_flags last)
805 {
806     VALUE nv;
807     long n;
808     long offset = 0;
809 
810     rb_scan_args(argc, argv, "1", &nv);
811     n = NUM2LONG(nv);
812     if (n > RARRAY_LEN(ary)) {
813         n = RARRAY_LEN(ary);
814     }
815     else if (n < 0) {
816         rb_raise(rb_eArgError, "negative array size");
817     }
818     if (last) {
819         offset = RARRAY_LEN(ary) - n;
820     }
821     return ary_make_partial(ary, rb_cArray, offset, n);
822 }
823 
824 /*
825  *  call-seq:
826  *     ary << obj            -> ary
827  *
828  *  Append---Pushes the given object on to the end of this array. This
829  *  expression returns the array itself, so several appends
830  *  may be chained together.
831  *
832  *     [ 1, 2 ] << "c" << "d" << [ 3, 4 ]
833  *             #=>  [ 1, 2, "c", "d", [ 3, 4 ] ]
834  *
835  */
836 
837 VALUE
838 rb_ary_push(VALUE ary, VALUE item)
839 {
840     long idx = RARRAY_LEN(ary);
841 
842     ary_ensure_room_for_push(ary, 1);
843     RARRAY_ASET(ary, idx, item);
844     ARY_SET_LEN(ary, idx + 1);
845     return ary;
846 }
847 
848 static VALUE
849 rb_ary_push_1(VALUE ary, VALUE item)
850 {
851     long idx = RARRAY_LEN(ary);
852 
853     if (idx >= ARY_CAPA(ary)) {
854         ary_double_capa(ary, idx);
855     }
856     RARRAY_ASET(ary, idx, item);
857     ARY_SET_LEN(ary, idx + 1);
858     return ary;
859 }
860 
861 VALUE
862 rb_ary_cat(VALUE ary, const VALUE *ptr, long len)
863 {
864     long oldlen = RARRAY_LEN(ary);
865 
866     ary_ensure_room_for_push(ary, len);
867     MEMCPY(RARRAY_PTR(ary) + oldlen, ptr, VALUE, len);
868     ARY_SET_LEN(ary, oldlen + len);
869     return ary;
870 }
871 
872 /*
873  *  call-seq:
874  *     ary.push(obj, ... )   -> ary
875  *
876  *  Append --- Pushes the given object(s) on to the end of this array. This
877  *  expression returns the array itself, so several appends
878  *  may be chained together. See also Array#pop for the opposite
879  *  effect.
880  *
881  *     a = [ "a", "b", "c" ]
882  *     a.push("d", "e", "f")
883  *             #=> ["a", "b", "c", "d", "e", "f"]
884  *     [1, 2, 3,].push(4).push(5)
885  *             #=> [1, 2, 3, 4, 5]
886  */
887 
888 static VALUE
889 rb_ary_push_m(int argc, VALUE *argv, VALUE ary)
890 {
891     return rb_ary_cat(ary, argv, argc);
892 }
893 
894 VALUE
895 rb_ary_pop(VALUE ary)
896 {
897     long n;
898     rb_ary_modify_check(ary);
899     if (RARRAY_LEN(ary) == 0) return Qnil;
900     if (ARY_OWNS_HEAP_P(ary) &&
901         RARRAY_LEN(ary) * 3 < ARY_CAPA(ary) &&
902         ARY_CAPA(ary) > ARY_DEFAULT_SIZE)
903     {
904         ary_resize_capa(ary, RARRAY_LEN(ary) * 2);
905     }
906     n = RARRAY_LEN(ary)-1;
907     ARY_SET_LEN(ary, n);
908     return RARRAY_AREF(ary, n);
909 }
910 
911 /*
912  *  call-seq:
913  *     ary.pop    -> obj or nil
914  *     ary.pop(n) -> new_ary
915  *
916  *  Removes the last element from +self+ and returns it, or
917  *  +nil+ if the array is empty.
918  *
919  *  If a number +n+ is given, returns an array of the last +n+ elements
920  *  (or less) just like <code>array.slice!(-n, n)</code> does. See also
921  *  Array#push for the opposite effect.
922  *
923  *     a = [ "a", "b", "c", "d" ]
924  *     a.pop     #=> "d"
925  *     a.pop(2)  #=> ["b", "c"]
926  *     a         #=> ["a"]
927  */
928 
929 static VALUE
930 rb_ary_pop_m(int argc, VALUE *argv, VALUE ary)
931 {
932     VALUE result;
933 
934     if (argc == 0) {
935         return rb_ary_pop(ary);
936     }
937 
938     rb_ary_modify_check(ary);
939     result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_LAST);
940     ARY_INCREASE_LEN(ary, -RARRAY_LEN(result));
941     return result;
942 }
943 
944 VALUE
945 rb_ary_shift(VALUE ary)
946 {
947     VALUE top;
948 
949     rb_ary_modify_check(ary);
950     if (RARRAY_LEN(ary) == 0) return Qnil;
951     top = RARRAY_AREF(ary, 0);
952     if (!ARY_SHARED_P(ary)) {
953         if (RARRAY_LEN(ary) < ARY_DEFAULT_SIZE) {
954             MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+1, VALUE, RARRAY_LEN(ary)-1);
955             ARY_INCREASE_LEN(ary, -1);
956             return top;
957         }
958         assert(!ARY_EMBED_P(ary)); /* ARY_EMBED_LEN_MAX < ARY_DEFAULT_SIZE */
959 
960         RARRAY_ASET(ary, 0, Qnil);
961         ary_make_shared(ary);
962     }
963     else if (ARY_SHARED_NUM(ARY_SHARED(ary)) == 1) {
964         RARRAY_ASET(ary, 0, Qnil);
965     }
966     ARY_INCREASE_PTR(ary, 1);           /* shift ptr */
967     ARY_INCREASE_LEN(ary, -1);
968 
969     return top;
970 }
971 
972 /*
973  *  call-seq:
974  *     ary.shift    -> obj or nil
975  *     ary.shift(n) -> new_ary
976  *
977  *  Removes the first element of +self+ and returns it (shifting all
978  *  other elements down by one). Returns +nil+ if the array
979  *  is empty.
980  *
981  *  If a number +n+ is given, returns an array of the first +n+ elements
982  *  (or less) just like <code>array.slice!(0, n)</code> does. With +ary+
983  *  containing only the remainder elements, not including what was shifted to
984  *  +new_ary+. See also Array#unshift for the opposite effect.
985  *
986  *     args = [ "-m", "-q", "filename" ]
987  *     args.shift     #=> "-m"
988  *     args           #=> ["-q", "filename"]
989  *
990  *     args = [ "-m", "-q", "filename" ]
991  *     args.shift(2)  #=> ["-m", "-q"]
992  *     args           #=> ["filename"]
993  */
994 
995 static VALUE
996 rb_ary_shift_m(int argc, VALUE *argv, VALUE ary)
997 {
998     VALUE result;
999     long n;
1000 
1001     if (argc == 0) {
1002         return rb_ary_shift(ary);
1003     }
1004 
1005     rb_ary_modify_check(ary);
1006     result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
1007     n = RARRAY_LEN(result);
1008     if (ARY_SHARED_P(ary)) {
1009         if (ARY_SHARED_NUM(ARY_SHARED(ary)) == 1) {
1010             rb_mem_clear(RARRAY_PTR(ary), n);
1011         }
1012         ARY_INCREASE_PTR(ary, n);
1013     }
1014     else {
1015         MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+n, VALUE, RARRAY_LEN(ary)-n);
1016     }
1017     ARY_INCREASE_LEN(ary, -n);
1018 
1019     return result;
1020 }
1021 
1022 static void
1023 ary_ensure_room_for_unshift(VALUE ary, int argc)
1024 {
1025     long len = RARRAY_LEN(ary);
1026     long new_len = len + argc;
1027     long capa;
1028     VALUE *head, *sharedp;
1029 
1030     if (ARY_SHARED_P(ary)) {
1031         VALUE shared = ARY_SHARED(ary);
1032         capa = RARRAY_LEN(shared);
1033         if (ARY_SHARED_NUM(shared) == 1 && capa > new_len) {
1034             head = RARRAY_PTR(ary);
1035             sharedp = RARRAY_PTR(shared);
1036             goto makeroom_if_need;
1037         }
1038     }
1039 
1040     rb_ary_modify(ary);
1041     capa = ARY_CAPA(ary);
1042     if (capa - (capa >> 6) <= new_len) {
1043         ary_double_capa(ary, new_len);
1044     }
1045 
1046     /* use shared array for big "queues" */
1047     if (new_len > ARY_DEFAULT_SIZE * 4) {
1048         /* make a room for unshifted items */
1049         capa = ARY_CAPA(ary);
1050         ary_make_shared(ary);
1051 
1052         head = sharedp = RARRAY_PTR(ary);
1053         goto makeroom;
1054       makeroom_if_need:
1055         if (head - sharedp < argc) {
1056             long room;
1057           makeroom:
1058             room = capa - new_len;
1059             room -= room >> 4;
1060             MEMMOVE(sharedp + argc + room, head, VALUE, len);
1061             head = sharedp + argc + room;
1062         }
1063         ARY_SET_PTR(ary, head - argc);
1064     }
1065     else {
1066         /* sliding items */
1067         MEMMOVE(RARRAY_PTR(ary) + argc, RARRAY_PTR(ary), VALUE, len);
1068     }
1069 }
1070 
1071 /*
1072  *  call-seq:
1073  *     ary.unshift(obj, ...)  -> ary
1074  *
1075  *  Prepends objects to the front of +self+, moving other elements upwards.
1076  *  See also Array#shift for the opposite effect.
1077  *
1078  *     a = [ "b", "c", "d" ]
1079  *     a.unshift("a")   #=> ["a", "b", "c", "d"]
1080  *     a.unshift(1, 2)  #=> [ 1, 2, "a", "b", "c", "d"]
1081  */
1082 
1083 static VALUE
1084 rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
1085 {
1086     long len = RARRAY_LEN(ary);
1087 
1088     if (argc == 0) {
1089         rb_ary_modify_check(ary);
1090         return ary;
1091     }
1092 
1093     ary_ensure_room_for_unshift(ary, argc);
1094     MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
1095     ARY_SET_LEN(ary, len + argc);
1096     return ary;
1097 }
1098 
1099 VALUE
1100 rb_ary_unshift(VALUE ary, VALUE item)
1101 {
1102     return rb_ary_unshift_m(1,&item,ary);
1103 }
1104 
1105 /* faster version - use this if you don't need to treat negative offset */
1106 static inline VALUE
1107 rb_ary_elt(VALUE ary, long offset)
1108 {
1109     if (RARRAY_LEN(ary) == 0) return Qnil;
1110     if (offset < 0 || RARRAY_LEN(ary) <= offset) {
1111         return Qnil;
1112     }
1113     return RARRAY_AREF(ary, offset);
1114 }
1115 
1116 VALUE
1117 rb_ary_entry(VALUE ary, long offset)
1118 {
1119     if (offset < 0) {
1120         offset += RARRAY_LEN(ary);
1121     }
1122     return rb_ary_elt(ary, offset);
1123 }
1124 
1125 VALUE
1126 rb_ary_subseq(VALUE ary, long beg, long len)
1127 {
1128     VALUE klass;
1129 
1130     if (beg > RARRAY_LEN(ary)) return Qnil;
1131     if (beg < 0 || len < 0) return Qnil;
1132 
1133     if (RARRAY_LEN(ary) < len || RARRAY_LEN(ary) < beg + len) {
1134         len = RARRAY_LEN(ary) - beg;
1135     }
1136     klass = rb_obj_class(ary);
1137     if (len == 0) return ary_new(klass, 0);
1138 
1139     return ary_make_partial(ary, klass, beg, len);
1140 }
1141 
1142 /*
1143  *  call-seq:
1144  *     ary[index]                -> obj     or nil
1145  *     ary[start, length]        -> new_ary or nil
1146  *     ary[range]                -> new_ary or nil
1147  *     ary.slice(index)          -> obj     or nil
1148  *     ary.slice(start, length)  -> new_ary or nil
1149  *     ary.slice(range)          -> new_ary or nil
1150  *
1151  *  Element Reference --- Returns the element at +index+, or returns a
1152  *  subarray starting at the +start+ index and continuing for +length+
1153  *  elements, or returns a subarray specified by +range+ of indices.
1154  *
1155  *  Negative indices count backward from the end of the array (-1 is the last
1156  *  element).  For +start+ and +range+ cases the starting index is just before
1157  *  an element.  Additionally, an empty array is returned when the starting
1158  *  index for an element range is at the end of the array.
1159  *
1160  *  Returns +nil+ if the index (or starting index) are out of range.
1161  *
1162  *     a = [ "a", "b", "c", "d", "e" ]
1163  *     a[2] +  a[0] + a[1]    #=> "cab"
1164  *     a[6]                   #=> nil
1165  *     a[1, 2]                #=> [ "b", "c" ]
1166  *     a[1..3]                #=> [ "b", "c", "d" ]
1167  *     a[4..7]                #=> [ "e" ]
1168  *     a[6..10]               #=> nil
1169  *     a[-3, 3]               #=> [ "c", "d", "e" ]
1170  *     # special cases
1171  *     a[5]                   #=> nil
1172  *     a[6, 1]                #=> nil
1173  *     a[5, 1]                #=> []
1174  *     a[5..10]               #=> []
1175  *
1176  */
1177 
1178 VALUE
1179 rb_ary_aref(int argc, VALUE *argv, VALUE ary)
1180 {
1181     VALUE arg;
1182     long beg, len;
1183 
1184     if (argc == 2) {
1185         beg = NUM2LONG(argv[0]);
1186         len = NUM2LONG(argv[1]);
1187         if (beg < 0) {
1188             beg += RARRAY_LEN(ary);
1189         }
1190         return rb_ary_subseq(ary, beg, len);
1191     }
1192     if (argc != 1) {
1193         rb_scan_args(argc, argv, "11", NULL, NULL);
1194     }
1195     arg = argv[0];
1196     /* special case - speeding up */
1197     if (FIXNUM_P(arg)) {
1198         return rb_ary_entry(ary, FIX2LONG(arg));
1199     }
1200     /* check if idx is Range */
1201     switch (rb_range_beg_len(arg, &beg, &len, RARRAY_LEN(ary), 0)) {
1202       case Qfalse:
1203         break;
1204       case Qnil:
1205         return Qnil;
1206       default:
1207         return rb_ary_subseq(ary, beg, len);
1208     }
1209     return rb_ary_entry(ary, NUM2LONG(arg));
1210 }
1211 
1212 /*
1213  *  call-seq:
1214  *     ary.at(index)   ->   obj  or nil
1215  *
1216  *  Returns the element at +index+. A negative index counts from the end of
1217  *  +self+. Returns +nil+ if the index is out of range. See also
1218  *  Array#[].
1219  *
1220  *     a = [ "a", "b", "c", "d", "e" ]
1221  *     a.at(0)     #=> "a"
1222  *     a.at(-1)    #=> "e"
1223  */
1224 
1225 static VALUE
1226 rb_ary_at(VALUE ary, VALUE pos)
1227 {
1228     return rb_ary_entry(ary, NUM2LONG(pos));
1229 }
1230 
1231 /*
1232  *  call-seq:
1233  *     ary.first     ->   obj or nil
1234  *     ary.first(n)  ->   new_ary
1235  *
1236  *  Returns the first element, or the first +n+ elements, of the array.
1237  *  If the array is empty, the first form returns +nil+, and the
1238  *  second form returns an empty array. See also Array#last for
1239  *  the opposite effect.
1240  *
1241  *     a = [ "q", "r", "s", "t" ]
1242  *     a.first     #=> "q"
1243  *     a.first(2)  #=> ["q", "r"]
1244  */
1245 
1246 static VALUE
1247 rb_ary_first(int argc, VALUE *argv, VALUE ary)
1248 {
1249     if (argc == 0) {
1250         if (RARRAY_LEN(ary) == 0) return Qnil;
1251         return RARRAY_AREF(ary, 0);
1252     }
1253     else {
1254         return ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
1255     }
1256 }
1257 
1258 /*
1259  *  call-seq:
1260  *     ary.last     ->  obj or nil
1261  *     ary.last(n)  ->  new_ary
1262  *
1263  *  Returns the last element(s) of +self+. If the array is empty,
1264  *  the first form returns +nil+.
1265  *
1266  *  See also Array#first for the opposite effect.
1267  *
1268  *     a = [ "w", "x", "y", "z" ]
1269  *     a.last     #=> "z"
1270  *     a.last(2)  #=> ["y", "z"]
1271  */
1272 
1273 VALUE
1274 rb_ary_last(int argc, VALUE *argv, VALUE ary)
1275 {
1276     if (argc == 0) {
1277         if (RARRAY_LEN(ary) == 0) return Qnil;
1278         return RARRAY_AREF(ary, RARRAY_LEN(ary)-1);
1279     }
1280     else {
1281         return ary_take_first_or_last(argc, argv, ary, ARY_TAKE_LAST);
1282     }
1283 }
1284 
1285 /*
1286  *  call-seq:
1287  *     ary.fetch(index)                    -> obj
1288  *     ary.fetch(index, default)           -> obj
1289  *     ary.fetch(index) { |index| block }  -> obj
1290  *
1291  *  Tries to return the element at position +index+, but throws an IndexError
1292  *  exception if the referenced +index+ lies outside of the array bounds.  This
1293  *  error can be prevented by supplying a second argument, which will act as a
1294  *  +default+ value.
1295  *
1296  *  Alternatively, if a block is given it will only be executed when an
1297  *  invalid +index+ is referenced.  Negative values of +index+ count from the
1298  *  end of the array.
1299  *
1300  *     a = [ 11, 22, 33, 44 ]
1301  *     a.fetch(1)               #=> 22
1302  *     a.fetch(-1)              #=> 44
1303  *     a.fetch(4, 'cat')        #=> "cat"
1304  *     a.fetch(100) { |i| puts "#{i} is out of bounds" }
1305  *                              #=> "100 is out of bounds"
1306  */
1307 
1308 static VALUE
1309 rb_ary_fetch(int argc, VALUE *argv, VALUE ary)
1310 {
1311     VALUE pos, ifnone;
1312     long block_given;
1313     long idx;
1314 
1315     rb_scan_args(argc, argv, "11", &pos, &ifnone);
1316     block_given = rb_block_given_p();
1317     if (block_given && argc == 2) {
1318         rb_warn("block supersedes default value argument");
1319     }
1320     idx = NUM2LONG(pos);
1321 
1322     if (idx < 0) {
1323         idx +=  RARRAY_LEN(ary);
1324     }
1325     if (idx < 0 || RARRAY_LEN(ary) <= idx) {
1326         if (block_given) return rb_yield(pos);
1327         if (argc == 1) {
1328             rb_raise(rb_eIndexError, "index %ld outside of array bounds: %ld...%ld",
1329                         idx - (idx < 0 ? RARRAY_LEN(ary) : 0), -RARRAY_LEN(ary), RARRAY_LEN(ary));
1330         }
1331         return ifnone;
1332     }
1333     return RARRAY_AREF(ary, idx);
1334 }
1335 
1336 /*
1337  *  call-seq:
1338  *     ary.find_index(obj)             ->  int or nil
1339  *     ary.find_index { |item| block } ->  int or nil
1340  *     ary.find_index                  ->  Enumerator
1341  *     ary.index(obj)             ->  int or nil
1342  *     ary.index { |item| block } ->  int or nil
1343  *     ary.index                  ->  Enumerator
1344  *
1345  *  Returns the _index_ of the first object in +ary+ such that the object is
1346  *  <code>==</code> to +obj+.
1347  *
1348  *  If a block is given instead of an argument, returns the _index_ of the
1349  *  first object for which the block returns +true+.  Returns +nil+ if no
1350  *  match is found.
1351  *
1352  *  See also Array#rindex.
1353  *
1354  *  An Enumerator is returned if neither a block nor argument is given.
1355  *
1356  *     a = [ "a", "b", "c" ]
1357  *     a.index("b")              #=> 1
1358  *     a.index("z")              #=> nil
1359  *     a.index { |x| x == "b" }  #=> 1
1360  */
1361 
1362 static VALUE
1363 rb_ary_index(int argc, VALUE *argv, VALUE ary)
1364 {
1365     VALUE val;
1366     long i;
1367 
1368     if (argc == 0) {
1369         RETURN_ENUMERATOR(ary, 0, 0);
1370         for (i=0; i<RARRAY_LEN(ary); i++) {
1371             if (RTEST(rb_yield(RARRAY_AREF(ary, i)))) {
1372                 return LONG2NUM(i);
1373             }
1374         }
1375         return Qnil;
1376     }
1377     rb_scan_args(argc, argv, "1", &val);
1378     if (rb_block_given_p())
1379         rb_warn("given block not used");
1380     for (i=0; i<RARRAY_LEN(ary); i++) {
1381         if (rb_equal(RARRAY_AREF(ary, i), val))
1382             return LONG2NUM(i);
1383     }
1384     return Qnil;
1385 }
1386 
1387 /*
1388  *  call-seq:
1389  *     ary.rindex(obj)             ->  int or nil
1390  *     ary.rindex { |item| block } ->  int or nil
1391  *     ary.rindex                  ->  Enumerator
1392  *
1393  *  Returns the _index_ of the last object in +self+ <code>==</code> to +obj+.
1394  *
1395  *  If a block is given instead of an argument, returns the _index_ of the
1396  *  first object for which the block returns +true+, starting from the last
1397  *  object.
1398  *
1399  *  Returns +nil+ if no match is found.
1400  *
1401  *  See also Array#index.
1402  *
1403  *  If neither block nor argument is given, an Enumerator is returned instead.
1404  *
1405  *     a = [ "a", "b", "b", "b", "c" ]
1406  *     a.rindex("b")             #=> 3
1407  *     a.rindex("z")             #=> nil
1408  *     a.rindex { |x| x == "b" } #=> 3
1409  */
1410 
1411 static VALUE
1412 rb_ary_rindex(int argc, VALUE *argv, VALUE ary)
1413 {
1414     VALUE val;
1415     long i = RARRAY_LEN(ary);
1416 
1417     if (argc == 0) {
1418         RETURN_ENUMERATOR(ary, 0, 0);
1419         while (i--) {
1420             if (RTEST(rb_yield(RARRAY_AREF(ary, i))))
1421                 return LONG2NUM(i);
1422             if (i > RARRAY_LEN(ary)) {
1423                 i = RARRAY_LEN(ary);
1424             }
1425         }
1426         return Qnil;
1427     }
1428     rb_scan_args(argc, argv, "1", &val);
1429     if (rb_block_given_p())
1430         rb_warn("given block not used");
1431     while (i--) {
1432         if (rb_equal(RARRAY_AREF(ary, i), val))
1433             return LONG2NUM(i);
1434         if (i > RARRAY_LEN(ary)) {
1435             i = RARRAY_LEN(ary);
1436         }
1437     }
1438     return Qnil;
1439 }
1440 
1441 VALUE
1442 rb_ary_to_ary(VALUE obj)
1443 {
1444     VALUE tmp = rb_check_array_type(obj);
1445 
1446     if (!NIL_P(tmp)) return tmp;
1447     return rb_ary_new3(1, obj);
1448 }
1449 
1450 static void
1451 rb_ary_splice(VALUE ary, long beg, long len, VALUE rpl)
1452 {
1453     long rlen;
1454 
1455     if (len < 0) rb_raise(rb_eIndexError, "negative length (%ld)", len);
1456     if (beg < 0) {
1457         beg += RARRAY_LEN(ary);
1458         if (beg < 0) {
1459             rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
1460                      beg - RARRAY_LEN(ary), -RARRAY_LEN(ary));
1461         }
1462     }
1463     if (RARRAY_LEN(ary) < len || RARRAY_LEN(ary) < beg + len) {
1464         len = RARRAY_LEN(ary) - beg;
1465     }
1466 
1467     if (rpl == Qundef) {
1468         rlen = 0;
1469     }
1470     else {
1471         rpl = rb_ary_to_ary(rpl);
1472         rlen = RARRAY_LEN(rpl);
1473     }
1474     if (beg >= RARRAY_LEN(ary)) {
1475         if (beg > ARY_MAX_SIZE - rlen) {
1476             rb_raise(rb_eIndexError, "index %ld too big", beg);
1477         }
1478         ary_ensure_room_for_push(ary, rlen-len); /* len is 0 or negative */
1479         len = beg + rlen;
1480         rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary), beg - RARRAY_LEN(ary));
1481         if (rlen > 0) {
1482             MEMCPY(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
1483         }
1484         ARY_SET_LEN(ary, len);
1485     }
1486     else {
1487         long alen;
1488 
1489         rb_ary_modify(ary);
1490         alen = RARRAY_LEN(ary) + rlen - len;
1491         if (alen >= ARY_CAPA(ary)) {
1492             ary_double_capa(ary, alen);
1493         }
1494 
1495         if (len != rlen) {
1496             MEMMOVE(RARRAY_PTR(ary) + beg + rlen, RARRAY_PTR(ary) + beg + len,
1497                     VALUE, RARRAY_LEN(ary) - (beg + len));
1498             ARY_SET_LEN(ary, alen);
1499         }
1500         if (rlen > 0) {
1501             MEMMOVE(RARRAY_PTR(ary) + beg, RARRAY_PTR(rpl), VALUE, rlen);
1502         }
1503     }
1504 }
1505 
1506 void
1507 rb_ary_set_len(VALUE ary, long len)
1508 {
1509     long capa;
1510 
1511     rb_ary_modify_check(ary);
1512     if (ARY_SHARED_P(ary)) {
1513         rb_raise(rb_eRuntimeError, "can't set length of shared ");
1514     }
1515     if (len > (capa = (long)ARY_CAPA(ary))) {
1516         rb_bug("probable buffer overflow: %ld for %ld", len, capa);
1517     }
1518     ARY_SET_LEN(ary, len);
1519 }
1520 
1521 /*!
1522  * expands or shrinks \a ary to \a len elements.
1523  * expanded region will be filled with Qnil.
1524  * \param ary  an array
1525  * \param len  new size
1526  * \return     \a ary
1527  * \post       the size of \a ary is \a len.
1528  */
1529 VALUE
1530 rb_ary_resize(VALUE ary, long len)
1531 {
1532     long olen;
1533 
1534     rb_ary_modify(ary);
1535     olen = RARRAY_LEN(ary);
1536     if (len == olen) return ary;
1537     if (len > ARY_MAX_SIZE) {
1538         rb_raise(rb_eIndexError, "index %ld too big", len);
1539     }
1540     if (len > olen) {
1541         if (len >= ARY_CAPA(ary)) {
1542             ary_double_capa(ary, len);
1543         }
1544         rb_mem_clear(RARRAY_PTR(ary) + olen, len - olen);
1545         ARY_SET_LEN(ary, len);
1546     }
1547     else if (ARY_EMBED_P(ary)) {
1548         ARY_SET_EMBED_LEN(ary, len);
1549     }
1550     else if (len <= RARRAY_EMBED_LEN_MAX) {
1551         VALUE tmp[RARRAY_EMBED_LEN_MAX];
1552         MEMCPY(tmp, ARY_HEAP_PTR(ary), VALUE, len);
1553         ary_discard(ary);
1554         MEMCPY((VALUE *)ARY_EMBED_PTR(ary), tmp, VALUE, len);
1555         ARY_SET_EMBED_LEN(ary, len);
1556     }
1557     else {
1558         if (olen > len + ARY_DEFAULT_SIZE) {
1559             REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, len);
1560             ARY_SET_CAPA(ary, len);
1561         }
1562         ARY_SET_HEAP_LEN(ary, len);
1563     }
1564     return ary;
1565 }
1566 
1567 /*
1568  *  call-seq:
1569  *     ary[index]         = obj                      ->  obj
1570  *     ary[start, length] = obj or other_ary or nil  ->  obj or other_ary or nil
1571  *     ary[range]         = obj or other_ary or nil  ->  obj or other_ary or nil
1572  *
1573  *  Element Assignment --- Sets the element at +index+, or replaces a subarray
1574  *  from the +start+ index for +length+ elements, or replaces a subarray
1575  *  specified by the +range+ of indices.
1576  *
1577  *  If indices are greater than the current capacity of the array, the array
1578  *  grows automatically.  Elements are inserted into the array at +start+ if
1579  *  +length+ is zero.
1580  *
1581  *  Negative indices will count backward from the end of the array.  For
1582  *  +start+ and +range+ cases the starting index is just before an element.
1583  *
1584  *  An IndexError is raised if a negative index points past the beginning of
1585  *  the array.
1586  *
1587  *  See also Array#push, and Array#unshift.
1588  *
1589  *     a = Array.new
1590  *     a[4] = "4";                 #=> [nil, nil, nil, nil, "4"]
1591  *     a[0, 3] = [ 'a', 'b', 'c' ] #=> ["a", "b", "c", nil, "4"]
1592  *     a[1..2] = [ 1, 2 ]          #=> ["a", 1, 2, nil, "4"]
1593  *     a[0, 2] = "?"               #=> ["?", 2, nil, "4"]
1594  *     a[0..2] = "A"               #=> ["A", "4"]
1595  *     a[-1]   = "Z"               #=> ["A", "Z"]
1596  *     a[1..-1] = nil              #=> ["A", nil]
1597  *     a[1..-1] = []               #=> ["A"]
1598  *     a[0, 0] = [ 1, 2 ]          #=> [1, 2, "A"]
1599  *     a[3, 0] = "B"               #=> [1, 2, "A", "B"]
1600  */
1601 
1602 static VALUE
1603 rb_ary_aset(int argc, VALUE *argv, VALUE ary)
1604 {
1605     long offset, beg, len;
1606 
1607     if (argc == 3) {
1608         rb_ary_modify_check(ary);
1609         beg = NUM2LONG(argv[0]);
1610         len = NUM2LONG(argv[1]);
1611         rb_ary_splice(ary, beg, len, argv[2]);
1612         return argv[2];
1613     }
1614     rb_check_arity(argc, 2, 2);
1615     rb_ary_modify_check(ary);
1616     if (FIXNUM_P(argv[0])) {
1617         offset = FIX2LONG(argv[0]);
1618         goto fixnum;
1619     }
1620     if (rb_range_beg_len(argv[0], &beg, &len, RARRAY_LEN(ary), 1)) {
1621         /* check if idx is Range */
1622         rb_ary_splice(ary, beg, len, argv[1]);
1623         return argv[1];
1624     }
1625 
1626     offset = NUM2LONG(argv[0]);
1627 fixnum:
1628     rb_ary_store(ary, offset, argv[1]);
1629     return argv[1];
1630 }
1631 
1632 /*
1633  *  call-seq:
1634  *     ary.insert(index, obj...)  -> ary
1635  *
1636  *  Inserts the given values before the element with the given +index+.
1637  *
1638  *  Negative indices count backwards from the end of the array, where +-1+ is
1639  *  the last element.
1640  *
1641  *     a = %w{ a b c d }
1642  *     a.insert(2, 99)         #=> ["a", "b", 99, "c", "d"]
1643  *     a.insert(-2, 1, 2, 3)   #=> ["a", "b", 99, "c", 1, 2, 3, "d"]
1644  */
1645 
1646 static VALUE
1647 rb_ary_insert(int argc, VALUE *argv, VALUE ary)
1648 {
1649     long pos;
1650 
1651     rb_check_arity(argc, 1, UNLIMITED_ARGUMENTS);
1652     rb_ary_modify_check(ary);
1653     if (argc == 1) return ary;
1654     pos = NUM2LONG(argv[0]);
1655     if (pos == -1) {
1656         pos = RARRAY_LEN(ary);
1657     }
1658     if (pos < 0) {
1659         pos++;
1660     }
1661     rb_ary_splice(ary, pos, 0, rb_ary_new4(argc - 1, argv + 1));
1662     return ary;
1663 }
1664 
1665 static VALUE
1666 rb_ary_length(VALUE ary);
1667 
1668 static VALUE
1669 ary_enum_length(VALUE ary, VALUE args, VALUE eobj)
1670 {
1671     return rb_ary_length(ary);
1672 }
1673 
1674 /*
1675  *  call-seq:
1676  *     ary.each { |item| block }  -> ary
1677  *     ary.each                   -> Enumerator
1678  *
1679  *  Calls the given block once for each element in +self+, passing that element
1680  *  as a parameter.
1681  *
1682  *  An Enumerator is returned if no block is given.
1683  *
1684  *     a = [ "a", "b", "c" ]
1685  *     a.each {|x| print x, " -- " }
1686  *
1687  *  produces:
1688  *
1689  *     a -- b -- c --
1690  */
1691 
1692 VALUE
1693 rb_ary_each(VALUE array)
1694 {
1695     long i;
1696     volatile VALUE ary = array;
1697 
1698     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
1699     for (i=0; i<RARRAY_LEN(ary); i++) {
1700         rb_yield(RARRAY_AREF(ary, i));
1701     }
1702     return ary;
1703 }
1704 
1705 /*
1706  *  call-seq:
1707  *     ary.each_index { |index| block }  -> ary
1708  *     ary.each_index                    -> Enumerator
1709  *
1710  *  Same as Array#each, but passes the +index+ of the element instead of the
1711  *  element itself.
1712  *
1713  *  An Enumerator is returned if no block is given.
1714  *
1715  *     a = [ "a", "b", "c" ]
1716  *     a.each_index {|x| print x, " -- " }
1717  *
1718  *  produces:
1719  *
1720  *     0 -- 1 -- 2 --
1721  */
1722 
1723 static VALUE
1724 rb_ary_each_index(VALUE ary)
1725 {
1726     long i;
1727     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
1728 
1729     for (i=0; i<RARRAY_LEN(ary); i++) {
1730         rb_yield(LONG2NUM(i));
1731     }
1732     return ary;
1733 }
1734 
1735 /*
1736  *  call-seq:
1737  *     ary.reverse_each { |item| block }  -> ary
1738  *     ary.reverse_each                   -> Enumerator
1739  *
1740  *  Same as Array#each, but traverses +self+ in reverse order.
1741  *
1742  *     a = [ "a", "b", "c" ]
1743  *     a.reverse_each {|x| print x, " " }
1744  *
1745  *  produces:
1746  *
1747  *     c b a
1748  */
1749 
1750 static VALUE
1751 rb_ary_reverse_each(VALUE ary)
1752 {
1753     long len;
1754 
1755     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
1756     len = RARRAY_LEN(ary);
1757     while (len--) {
1758         rb_yield(RARRAY_AREF(ary, len));
1759         if (RARRAY_LEN(ary) < len) {
1760             len = RARRAY_LEN(ary);
1761         }
1762     }
1763     return ary;
1764 }
1765 
1766 /*
1767  *  call-seq:
1768  *     ary.length -> int
1769  *
1770  *  Returns the number of elements in +self+. May be zero.
1771  *
1772  *     [ 1, 2, 3, 4, 5 ].length   #=> 5
1773  *     [].length                  #=> 0
1774  */
1775 
1776 static VALUE
1777 rb_ary_length(VALUE ary)
1778 {
1779     long len = RARRAY_LEN(ary);
1780     return LONG2NUM(len);
1781 }
1782 
1783 /*
1784  *  call-seq:
1785  *     ary.empty?   -> true or false
1786  *
1787  *  Returns +true+ if +self+ contains no elements.
1788  *
1789  *     [].empty?   #=> true
1790  */
1791 
1792 static VALUE
1793 rb_ary_empty_p(VALUE ary)
1794 {
1795     if (RARRAY_LEN(ary) == 0)
1796         return Qtrue;
1797     return Qfalse;
1798 }
1799 
1800 VALUE
1801 rb_ary_dup(VALUE ary)
1802 {
1803     VALUE dup = rb_ary_new2(RARRAY_LEN(ary));
1804     MEMCPY(RARRAY_PTR(dup), RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
1805     ARY_SET_LEN(dup, RARRAY_LEN(ary));
1806     return dup;
1807 }
1808 
1809 VALUE
1810 rb_ary_resurrect(VALUE ary)
1811 {
1812     return rb_ary_new4(RARRAY_LEN(ary), RARRAY_PTR(ary));
1813 }
1814 
1815 extern VALUE rb_output_fs;
1816 
1817 static void ary_join_1(VALUE obj, VALUE ary, VALUE sep, long i, VALUE result, int *first);
1818 
1819 static VALUE
1820 recursive_join(VALUE obj, VALUE argp, int recur)
1821 {
1822     VALUE *arg = (VALUE *)argp;
1823     VALUE ary = arg[0];
1824     VALUE sep = arg[1];
1825     VALUE result = arg[2];
1826     int *first = (int *)arg[3];
1827 
1828     if (recur) {
1829         rb_raise(rb_eArgError, "recursive array join");
1830     }
1831     else {
1832         ary_join_1(obj, ary, sep, 0, result, first);
1833     }
1834     return Qnil;
1835 }
1836 
1837 static void
1838 ary_join_0(VALUE ary, VALUE sep, long max, VALUE result)
1839 {
1840     long i;
1841     VALUE val;
1842 
1843     if (max > 0) rb_enc_copy(result, RARRAY_AREF(ary, 0));
1844     for (i=0; i<max; i++) {
1845         val = RARRAY_AREF(ary, i);
1846         if (i > 0 && !NIL_P(sep))
1847             rb_str_buf_append(result, sep);
1848         rb_str_buf_append(result, val);
1849         if (OBJ_TAINTED(val)) OBJ_TAINT(result);
1850     }
1851 }
1852 
1853 static void
1854 ary_join_1(VALUE obj, VALUE ary, VALUE sep, long i, VALUE result, int *first)
1855 {
1856     VALUE val, tmp;
1857 
1858     for (; i<RARRAY_LEN(ary); i++) {
1859         if (i > 0 && !NIL_P(sep))
1860             rb_str_buf_append(result, sep);
1861 
1862         val = RARRAY_AREF(ary, i);
1863         if (RB_TYPE_P(val, T_STRING)) {
1864           str_join:
1865             rb_str_buf_append(result, val);
1866             *first = FALSE;
1867         }
1868         else if (RB_TYPE_P(val, T_ARRAY)) {
1869             obj = val;
1870           ary_join:
1871             if (val == ary) {
1872                 rb_raise(rb_eArgError, "recursive array join");
1873             }
1874             else {
1875                 VALUE args[4];
1876 
1877                 args[0] = val;
1878                 args[1] = sep;
1879                 args[2] = result;
1880                 args[3] = (VALUE)first;
1881                 rb_exec_recursive(recursive_join, obj, (VALUE)args);
1882             }
1883         }
1884         else {
1885             tmp = rb_check_string_type(val);
1886             if (!NIL_P(tmp)) {
1887                 val = tmp;
1888                 goto str_join;
1889             }
1890             tmp = rb_check_convert_type(val, T_ARRAY, "Array", "to_ary");
1891             if (!NIL_P(tmp)) {
1892                 obj = val;
1893                 val = tmp;
1894                 goto ary_join;
1895             }
1896             val = rb_obj_as_string(val);
1897             if (*first) {
1898                 rb_enc_copy(result, val);
1899                 *first = FALSE;
1900             }
1901             goto str_join;
1902         }
1903     }
1904 }
1905 
1906 VALUE
1907 rb_ary_join(VALUE ary, VALUE sep)
1908 {
1909     long len = 1, i;
1910     int taint = FALSE;
1911     VALUE val, tmp, result;
1912 
1913     if (RARRAY_LEN(ary) == 0) return rb_usascii_str_new(0, 0);
1914     if (OBJ_TAINTED(ary)) taint = TRUE;
1915 
1916     if (!NIL_P(sep)) {
1917         StringValue(sep);
1918         len += RSTRING_LEN(sep) * (RARRAY_LEN(ary) - 1);
1919     }
1920     for (i=0; i<RARRAY_LEN(ary); i++) {
1921         val = RARRAY_AREF(ary, i);
1922         tmp = rb_check_string_type(val);
1923 
1924         if (NIL_P(tmp) || tmp != val) {
1925             int first;
1926             result = rb_str_buf_new(len + (RARRAY_LEN(ary)-i)*10);
1927             rb_enc_associate(result, rb_usascii_encoding());
1928             if (taint) OBJ_TAINT(result);
1929             ary_join_0(ary, sep, i, result);
1930             first = i == 0;
1931             ary_join_1(ary, ary, sep, i, result, &first);
1932             return result;
1933         }
1934 
1935         len += RSTRING_LEN(tmp);
1936     }
1937 
1938     result = rb_str_buf_new(len);
1939     if (taint) OBJ_TAINT(result);
1940     ary_join_0(ary, sep, RARRAY_LEN(ary), result);
1941 
1942     return result;
1943 }
1944 
1945 /*
1946  *  call-seq:
1947  *     ary.join(separator=$,)    -> str
1948  *
1949  *  Returns a string created by converting each element of the array to
1950  *  a string, separated by the given +separator+.
1951  *  If the +separator+ is +nil+, it uses current $,.
1952  *  If both the +separator+ and $, are nil, it uses empty string.
1953  *
1954  *     [ "a", "b", "c" ].join        #=> "abc"
1955  *     [ "a", "b", "c" ].join("-")   #=> "a-b-c"
1956  */
1957 
1958 static VALUE
1959 rb_ary_join_m(int argc, VALUE *argv, VALUE ary)
1960 {
1961     VALUE sep;
1962 
1963     rb_scan_args(argc, argv, "01", &sep);
1964     if (NIL_P(sep)) sep = rb_output_fs;
1965 
1966     return rb_ary_join(ary, sep);
1967 }
1968 
1969 static VALUE
1970 inspect_ary(VALUE ary, VALUE dummy, int recur)
1971 {
1972     int tainted = OBJ_TAINTED(ary);
1973     long i;
1974     VALUE s, str;
1975 
1976     if (recur) return rb_usascii_str_new_cstr("[...]");
1977     str = rb_str_buf_new2("[");
1978     for (i=0; i<RARRAY_LEN(ary); i++) {
1979         s = rb_inspect(RARRAY_AREF(ary, i));
1980         if (OBJ_TAINTED(s)) tainted = TRUE;
1981         if (i > 0) rb_str_buf_cat2(str, ", ");
1982         else rb_enc_copy(str, s);
1983         rb_str_buf_append(str, s);
1984     }
1985     rb_str_buf_cat2(str, "]");
1986     if (tainted) OBJ_TAINT(str);
1987     return str;
1988 }
1989 
1990 /*
1991  *  call-seq:
1992  *     ary.inspect  -> string
1993  *     ary.to_s     -> string
1994  *
1995  *  Creates a string representation of +self+.
1996  *
1997  *     [ "a", "b", "c" ].to_s     #=> "[\"a\", \"b\", \"c\"]"
1998  */
1999 
2000 static VALUE
2001 rb_ary_inspect(VALUE ary)
2002 {
2003     if (RARRAY_LEN(ary) == 0) return rb_usascii_str_new2("[]");
2004     return rb_exec_recursive(inspect_ary, ary, 0);
2005 }
2006 
2007 VALUE
2008 rb_ary_to_s(VALUE ary)
2009 {
2010     return rb_ary_inspect(ary);
2011 }
2012 
2013 /*
2014  *  call-seq:
2015  *     ary.to_a     -> ary
2016  *
2017  *  Returns +self+.
2018  *
2019  *  If called on a subclass of Array, converts the receiver to an Array object.
2020  */
2021 
2022 static VALUE
2023 rb_ary_to_a(VALUE ary)
2024 {
2025     if (rb_obj_class(ary) != rb_cArray) {
2026         VALUE dup = rb_ary_new2(RARRAY_LEN(ary));
2027         rb_ary_replace(dup, ary);
2028         return dup;
2029     }
2030     return ary;
2031 }
2032 
2033 /*
2034  *  call-seq:
2035  *     ary.to_ary -> ary
2036  *
2037  *  Returns +self+.
2038  */
2039 
2040 static VALUE
2041 rb_ary_to_ary_m(VALUE ary)
2042 {
2043     return ary;
2044 }
2045 
2046 static void
2047 ary_reverse(VALUE *p1, VALUE *p2)
2048 {
2049     while (p1 < p2) {
2050         VALUE tmp = *p1;
2051         *p1++ = *p2;
2052         *p2-- = tmp;
2053     }
2054 }
2055 
2056 VALUE
2057 rb_ary_reverse(VALUE ary)
2058 {
2059     VALUE *p1, *p2;
2060 
2061     rb_ary_modify(ary);
2062     if (RARRAY_LEN(ary) > 1) {
2063         p1 = RARRAY_PTR(ary);
2064         p2 = p1 + RARRAY_LEN(ary) - 1;  /* points last item */
2065         ary_reverse(p1, p2);
2066     }
2067     return ary;
2068 }
2069 
2070 /*
2071  *  call-seq:
2072  *     ary.reverse!   -> ary
2073  *
2074  *  Reverses +self+ in place.
2075  *
2076  *     a = [ "a", "b", "c" ]
2077  *     a.reverse!       #=> ["c", "b", "a"]
2078  *     a                #=> ["c", "b", "a"]
2079  */
2080 
2081 static VALUE
2082 rb_ary_reverse_bang(VALUE ary)
2083 {
2084     return rb_ary_reverse(ary);
2085 }
2086 
2087 /*
2088  *  call-seq:
2089  *     ary.reverse    -> new_ary
2090  *
2091  *  Returns a new array containing +self+'s elements in reverse order.
2092  *
2093  *     [ "a", "b", "c" ].reverse   #=> ["c", "b", "a"]
2094  *     [ 1 ].reverse               #=> [1]
2095  */
2096 
2097 static VALUE
2098 rb_ary_reverse_m(VALUE ary)
2099 {
2100     long len = RARRAY_LEN(ary);
2101     VALUE dup = rb_ary_new2(len);
2102 
2103     if (len > 0) {
2104         VALUE *p1 = RARRAY_PTR(ary);
2105         VALUE *p2 = RARRAY_PTR(dup) + len - 1;
2106         do *p2-- = *p1++; while (--len > 0);
2107     }
2108     ARY_SET_LEN(dup, RARRAY_LEN(ary));
2109     return dup;
2110 }
2111 
2112 static inline long
2113 rotate_count(long cnt, long len)
2114 {
2115     return (cnt < 0) ? (len - (~cnt % len) - 1) : (cnt % len);
2116 }
2117 
2118 VALUE
2119 rb_ary_rotate(VALUE ary, long cnt)
2120 {
2121     rb_ary_modify(ary);
2122 
2123     if (cnt != 0) {
2124         VALUE *ptr = RARRAY_PTR(ary);
2125         long len = RARRAY_LEN(ary);
2126 
2127         if (len > 0 && (cnt = rotate_count(cnt, len)) > 0) {
2128             --len;
2129             if (cnt < len) ary_reverse(ptr + cnt, ptr + len);
2130             if (--cnt > 0) ary_reverse(ptr, ptr + cnt);
2131             if (len > 0) ary_reverse(ptr, ptr + len);
2132             return ary;
2133         }
2134     }
2135 
2136     return Qnil;
2137 }
2138 
2139 /*
2140  *  call-seq:
2141  *     ary.rotate!(count=1)   -> ary
2142  *
2143  *  Rotates +self+ in place so that the element at +count+ comes first, and
2144  *  returns +self+.
2145  *
2146  *  If +count+ is negative then it rotates in the opposite direction, starting
2147  *  from the end of the array where +-1+ is the last element.
2148  *
2149  *     a = [ "a", "b", "c", "d" ]
2150  *     a.rotate!        #=> ["b", "c", "d", "a"]
2151  *     a                #=> ["b", "c", "d", "a"]
2152  *     a.rotate!(2)     #=> ["d", "a", "b", "c"]
2153  *     a.rotate!(-3)    #=> ["a", "b", "c", "d"]
2154  */
2155 
2156 static VALUE
2157 rb_ary_rotate_bang(int argc, VALUE *argv, VALUE ary)
2158 {
2159     long n = 1;
2160 
2161     switch (argc) {
2162       case 1: n = NUM2LONG(argv[0]);
2163       case 0: break;
2164       default: rb_scan_args(argc, argv, "01", NULL);
2165     }
2166     rb_ary_rotate(ary, n);
2167     return ary;
2168 }
2169 
2170 /*
2171  *  call-seq:
2172  *     ary.rotate(count=1)    -> new_ary
2173  *
2174  *  Returns a new array by rotating +self+ so that the element at +count+ is
2175  *  the first element of the new array.
2176  *
2177  *  If +count+ is negative then it rotates in the opposite direction, starting
2178  *  from the end of +self+ where +-1+ is the last element.
2179  *
2180  *     a = [ "a", "b", "c", "d" ]
2181  *     a.rotate         #=> ["b", "c", "d", "a"]
2182  *     a                #=> ["a", "b", "c", "d"]
2183  *     a.rotate(2)      #=> ["c", "d", "a", "b"]
2184  *     a.rotate(-3)     #=> ["b", "c", "d", "a"]
2185  */
2186 
2187 static VALUE
2188 rb_ary_rotate_m(int argc, VALUE *argv, VALUE ary)
2189 {
2190     VALUE rotated, *ptr, *ptr2;
2191     long len, cnt = 1;
2192 
2193     switch (argc) {
2194       case 1: cnt = NUM2LONG(argv[0]);
2195       case 0: break;
2196       default: rb_scan_args(argc, argv, "01", NULL);
2197     }
2198 
2199     len = RARRAY_LEN(ary);
2200     rotated = rb_ary_new2(len);
2201     if (len > 0) {
2202         cnt = rotate_count(cnt, len);
2203         ptr = RARRAY_PTR(ary);
2204         ptr2 = RARRAY_PTR(rotated);
2205         len -= cnt;
2206         MEMCPY(ptr2, ptr + cnt, VALUE, len);
2207         MEMCPY(ptr2 + len, ptr, VALUE, cnt);
2208     }
2209     ARY_SET_LEN(rotated, RARRAY_LEN(ary));
2210     return rotated;
2211 }
2212 
2213 struct ary_sort_data {
2214     VALUE ary;
2215     int opt_methods;
2216     int opt_inited;
2217 };
2218 
2219 enum {
2220     sort_opt_Fixnum,
2221     sort_opt_String,
2222     sort_optimizable_count
2223 };
2224 
2225 #define STRING_P(s) (RB_TYPE_P((s), T_STRING) && CLASS_OF(s) == rb_cString)
2226 
2227 #define SORT_OPTIMIZABLE_BIT(type) (1U << TOKEN_PASTE(sort_opt_,type))
2228 #define SORT_OPTIMIZABLE(data, type) \
2229     (((data)->opt_inited & SORT_OPTIMIZABLE_BIT(type)) ? \
2230      ((data)->opt_methods & SORT_OPTIMIZABLE_BIT(type)) : \
2231      (((data)->opt_inited |= SORT_OPTIMIZABLE_BIT(type)), \
2232       rb_method_basic_definition_p(TOKEN_PASTE(rb_c,type), id_cmp) && \
2233       ((data)->opt_methods |= SORT_OPTIMIZABLE_BIT(type))))
2234 
2235 static VALUE
2236 sort_reentered(VALUE ary)
2237 {
2238     if (RBASIC(ary)->klass) {
2239         rb_raise(rb_eRuntimeError, "sort reentered");
2240     }
2241     return Qnil;
2242 }
2243 
2244 static int
2245 sort_1(const void *ap, const void *bp, void *dummy)
2246 {
2247     struct ary_sort_data *data = dummy;
2248     VALUE retval = sort_reentered(data->ary);
2249     VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp;
2250     int n;
2251 
2252     retval = rb_yield_values(2, a, b);
2253     n = rb_cmpint(retval, a, b);
2254     sort_reentered(data->ary);
2255     return n;
2256 }
2257 
2258 static int
2259 sort_2(const void *ap, const void *bp, void *dummy)
2260 {
2261     struct ary_sort_data *data = dummy;
2262     VALUE retval = sort_reentered(data->ary);
2263     VALUE a = *(const VALUE *)ap, b = *(const VALUE *)bp;
2264     int n;
2265 
2266     if (FIXNUM_P(a) && FIXNUM_P(b) && SORT_OPTIMIZABLE(data, Fixnum)) {
2267         if ((long)a > (long)b) return 1;
2268         if ((long)a < (long)b) return -1;
2269         return 0;
2270     }
2271     if (STRING_P(a) && STRING_P(b) && SORT_OPTIMIZABLE(data, String)) {
2272         return rb_str_cmp(a, b);
2273     }
2274 
2275     retval = rb_funcall(a, id_cmp, 1, b);
2276     n = rb_cmpint(retval, a, b);
2277     sort_reentered(data->ary);
2278 
2279     return n;
2280 }
2281 
2282 /*
2283  *  call-seq:
2284  *     ary.sort!                   -> ary
2285  *     ary.sort! { |a, b| block }  -> ary
2286  *
2287  *  Sorts +self+ in place.
2288  *
2289  *  Comparisons for the sort will be done using the <code><=></code> operator
2290  *  or using an optional code block.
2291  *
2292  *  The block must implement a comparison between +a+ and +b+, and return
2293  *  +-1+, when +a+ follows +b+, +0+ when +a+ and +b+ are equivalent, or ++1+
2294  *  if +b+ follows +a+.
2295  *
2296  *  See also Enumerable#sort_by.
2297  *
2298  *     a = [ "d", "a", "e", "c", "b" ]
2299  *     a.sort!                    #=> ["a", "b", "c", "d", "e"]
2300  *     a.sort! { |x,y| y <=> x }  #=> ["e", "d", "c", "b", "a"]
2301  */
2302 
2303 VALUE
2304 rb_ary_sort_bang(VALUE ary)
2305 {
2306     rb_ary_modify(ary);
2307     assert(!ARY_SHARED_P(ary));
2308     if (RARRAY_LEN(ary) > 1) {
2309         VALUE tmp = ary_make_substitution(ary); /* only ary refers tmp */
2310         struct ary_sort_data data;
2311         long len = RARRAY_LEN(ary);
2312 
2313         RBASIC_CLEAR_CLASS(tmp);
2314         data.ary = tmp;
2315         data.opt_methods = 0;
2316         data.opt_inited = 0;
2317         ruby_qsort(RARRAY_PTR(tmp), len, sizeof(VALUE),
2318                    rb_block_given_p()?sort_1:sort_2, &data);
2319 
2320         rb_ary_modify(ary);
2321         if (ARY_EMBED_P(tmp)) {
2322             if (ARY_SHARED_P(ary)) { /* ary might be destructively operated in the given block */
2323                 rb_ary_unshare(ary);
2324             }
2325             FL_SET_EMBED(ary);
2326             MEMCPY(RARRAY_PTR(ary), ARY_EMBED_PTR(tmp), VALUE, ARY_EMBED_LEN(tmp));
2327             ARY_SET_LEN(ary, ARY_EMBED_LEN(tmp));
2328         }
2329         else {
2330             if (!ARY_EMBED_P(ary) && ARY_HEAP_PTR(ary) == ARY_HEAP_PTR(tmp)) {
2331                 FL_UNSET_SHARED(ary);
2332                 ARY_SET_CAPA(ary, RARRAY_LEN(tmp));
2333             }
2334             else {
2335                 assert(!ARY_SHARED_P(tmp));
2336                 if (ARY_EMBED_P(ary)) {
2337                     FL_UNSET_EMBED(ary);
2338                 }
2339                 else if (ARY_SHARED_P(ary)) {
2340                     /* ary might be destructively operated in the given block */
2341                     rb_ary_unshare(ary);
2342                 }
2343                 else {
2344                     xfree((void *)ARY_HEAP_PTR(ary));
2345                 }
2346                 ARY_SET_PTR(ary, RARRAY_PTR(tmp));
2347                 ARY_SET_HEAP_LEN(ary, len);
2348                 ARY_SET_CAPA(ary, RARRAY_LEN(tmp));
2349             }
2350             /* tmp was lost ownership for the ptr */
2351             FL_UNSET(tmp, FL_FREEZE);
2352             FL_SET_EMBED(tmp);
2353             ARY_SET_EMBED_LEN(tmp, 0);
2354             FL_SET(tmp, FL_FREEZE);
2355         }
2356         /* tmp will be GC'ed. */
2357         RBASIC_SET_CLASS_RAW(tmp, rb_cArray); /* rb_cArray must be marked */
2358     }
2359     return ary;
2360 }
2361 
2362 /*
2363  *  call-seq:
2364  *     ary.sort                   -> new_ary
2365  *     ary.sort { |a, b| block }  -> new_ary
2366  *
2367  *  Returns a new array created by sorting +self+.
2368  *
2369  *  Comparisons for the sort will be done using the <code><=></code> operator
2370  *  or using an optional code block.
2371  *
2372  *  The block must implement a comparison between +a+ and +b+, and return
2373  *  +-1+, when +a+ follows +b+, +0+ when +a+ and +b+ are equivalent, or ++1+
2374  *  if +b+ follows +a+.
2375  *
2376  *
2377  *  See also Enumerable#sort_by.
2378  *
2379  *     a = [ "d", "a", "e", "c", "b" ]
2380  *     a.sort                    #=> ["a", "b", "c", "d", "e"]
2381  *     a.sort { |x,y| y <=> x }  #=> ["e", "d", "c", "b", "a"]
2382  */
2383 
2384 VALUE
2385 rb_ary_sort(VALUE ary)
2386 {
2387     ary = rb_ary_dup(ary);
2388     rb_ary_sort_bang(ary);
2389     return ary;
2390 }
2391 
2392 /*
2393  *  call-seq:
2394  *     ary.bsearch {|x| block }  -> elem
2395  *
2396  *  By using binary search, finds a value from this array which meets
2397  *  the given condition in O(log n) where n is the size of the array.
2398  *
2399  *  You can use this method in two use cases: a find-minimum mode and
2400  *  a find-any mode.  In either case, the elements of the array must be
2401  *  monotone (or sorted) with respect to the block.
2402  *
2403  *  In find-minimum mode (this is a good choice for typical use case),
2404  *  the block must return true or false, and there must be an index i
2405  *  (0 <= i <= ary.size) so that:
2406  *
2407  *  - the block returns false for any element whose index is less than
2408  *    i, and
2409  *  - the block returns true for any element whose index is greater
2410  *    than or equal to i.
2411  *
2412  *  This method returns the i-th element.  If i is equal to ary.size,
2413  *  it returns nil.
2414  *
2415  *     ary = [0, 4, 7, 10, 12]
2416  *     ary.bsearch {|x| x >=   4 } #=> 4
2417  *     ary.bsearch {|x| x >=   6 } #=> 7
2418  *     ary.bsearch {|x| x >=  -1 } #=> 0
2419  *     ary.bsearch {|x| x >= 100 } #=> nil
2420  *
2421  *  In find-any mode (this behaves like libc's bsearch(3)), the block
2422  *  must return a number, and there must be two indices i and j
2423  *  (0 <= i <= j <= ary.size) so that:
2424  *
2425  *  - the block returns a positive number for ary[k] if 0 <= k < i,
2426  *  - the block returns zero for ary[k] if i <= k < j, and
2427  *  - the block returns a negative number for ary[k] if
2428  *    j <= k < ary.size.
2429  *
2430  *  Under this condition, this method returns any element whose index
2431  *  is within i...j.  If i is equal to j (i.e., there is no element
2432  *  that satisfies the block), this method returns nil.
2433  *
2434  *     ary = [0, 4, 7, 10, 12]
2435  *     # try to find v such that 4 <= v < 8
2436  *     ary.bsearch {|x| 1 - x / 4 } #=> 4 or 7
2437  *     # try to find v such that 8 <= v < 10
2438  *     ary.bsearch {|x| 4 - x / 2 } #=> nil
2439  *
2440  *  You must not mix the two modes at a time; the block must always
2441  *  return either true/false, or always return a number.  It is
2442  *  undefined which value is actually picked up at each iteration.
2443  */
2444 
2445 static VALUE
2446 rb_ary_bsearch(VALUE ary)
2447 {
2448     long low = 0, high = RARRAY_LEN(ary), mid;
2449     int smaller = 0, satisfied = 0;
2450     VALUE v, val;
2451 
2452     RETURN_ENUMERATOR(ary, 0, 0);
2453     while (low < high) {
2454         mid = low + ((high - low) / 2);
2455         val = rb_ary_entry(ary, mid);
2456         v = rb_yield(val);
2457         if (FIXNUM_P(v)) {
2458             if (FIX2INT(v) == 0) return val;
2459             smaller = FIX2INT(v) < 0;
2460         }
2461         else if (v == Qtrue) {
2462             satisfied = 1;
2463             smaller = 1;
2464         }
2465         else if (v == Qfalse || v == Qnil) {
2466             smaller = 0;
2467         }
2468         else if (rb_obj_is_kind_of(v, rb_cNumeric)) {
2469             switch (rb_cmpint(rb_funcall(v, id_cmp, 1, INT2FIX(0)), v, INT2FIX(0))) {
2470                 case 0: return val;
2471                 case 1: smaller = 1; break;
2472                 case -1: smaller = 0;
2473             }
2474         }
2475         else {
2476             rb_raise(rb_eTypeError, "wrong argument type %s"
2477                 " (must be numeric, true, false or nil)",
2478                 rb_obj_classname(v));
2479         }
2480         if (smaller) {
2481             high = mid;
2482         }
2483         else {
2484             low = mid + 1;
2485         }
2486     }
2487     if (low == RARRAY_LEN(ary)) return Qnil;
2488     if (!satisfied) return Qnil;
2489     return rb_ary_entry(ary, low);
2490 }
2491 
2492 
2493 static VALUE
2494 sort_by_i(VALUE i)
2495 {
2496     return rb_yield(i);
2497 }
2498 
2499 /*
2500  *  call-seq:
2501  *     ary.sort_by! { |obj| block }    -> ary
2502  *     ary.sort_by!                    -> Enumerator
2503  *
2504  *  Sorts +self+ in place using a set of keys generated by mapping the
2505  *  values in +self+ through the given block.
2506  *
2507  *  If no block is given, an Enumerator is returned instead.
2508  *
2509  */
2510 
2511 static VALUE
2512 rb_ary_sort_by_bang(VALUE ary)
2513 {
2514     VALUE sorted;
2515 
2516     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
2517     rb_ary_modify(ary);
2518     sorted = rb_block_call(ary, rb_intern("sort_by"), 0, 0, sort_by_i, 0);
2519     rb_ary_replace(ary, sorted);
2520     return ary;
2521 }
2522 
2523 
2524 /*
2525  *  call-seq:
2526  *     ary.collect { |item| block }  -> new_ary
2527  *     ary.map     { |item| block }  -> new_ary
2528  *     ary.collect                   -> Enumerator
2529  *     ary.map                       -> Enumerator
2530  *
2531  *  Invokes the given block once for each element of +self+.
2532  *
2533  *  Creates a new array containing the values returned by the block.
2534  *
2535  *  See also Enumerable#collect.
2536  *
2537  *  If no block is given, an Enumerator is returned instead.
2538  *
2539  *     a = [ "a", "b", "c", "d" ]
2540  *     a.map { |x| x + "!" }   #=> ["a!", "b!", "c!", "d!"]
2541  *     a                       #=> ["a", "b", "c", "d"]
2542  */
2543 
2544 static VALUE
2545 rb_ary_collect(VALUE ary)
2546 {
2547     long i;
2548     VALUE collect;
2549 
2550     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
2551     collect = rb_ary_new2(RARRAY_LEN(ary));
2552     for (i = 0; i < RARRAY_LEN(ary); i++) {
2553         rb_ary_push(collect, rb_yield(RARRAY_AREF(ary, i)));
2554     }
2555     return collect;
2556 }
2557 
2558 
2559 /*
2560  *  call-seq:
2561  *     ary.collect! {|item| block }   -> ary
2562  *     ary.map!     {|item| block }   -> ary
2563  *     ary.collect!                   -> Enumerator
2564  *     ary.map!                       -> Enumerator
2565  *
2566  *  Invokes the given block once for each element of +self+, replacing the
2567  *  element with the value returned by the block.
2568  *
2569  *  See also Enumerable#collect.
2570  *
2571  *  If no block is given, an Enumerator is returned instead.
2572  *
2573  *     a = [ "a", "b", "c", "d" ]
2574  *     a.map! {|x| x + "!" }
2575  *     a #=>  [ "a!", "b!", "c!", "d!" ]
2576  */
2577 
2578 static VALUE
2579 rb_ary_collect_bang(VALUE ary)
2580 {
2581     long i;
2582 
2583     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
2584     rb_ary_modify(ary);
2585     for (i = 0; i < RARRAY_LEN(ary); i++) {
2586         rb_ary_store(ary, i, rb_yield(RARRAY_AREF(ary, i)));
2587     }
2588     return ary;
2589 }
2590 
2591 VALUE
2592 rb_get_values_at(VALUE obj, long olen, int argc, VALUE *argv, VALUE (*func) (VALUE, long))
2593 {
2594     VALUE result = rb_ary_new2(argc);
2595     long beg, len, i, j;
2596 
2597     for (i=0; i<argc; i++) {
2598         if (FIXNUM_P(argv[i])) {
2599             rb_ary_push(result, (*func)(obj, FIX2LONG(argv[i])));
2600             continue;
2601         }
2602         /* check if idx is Range */
2603         if (rb_range_beg_len(argv[i], &beg, &len, olen, 1)) {
2604             long end = olen < beg+len ? olen : beg+len;
2605             for (j = beg; j < end; j++) {
2606                 rb_ary_push(result, (*func)(obj, j));
2607             }
2608             if (beg + len > j)
2609                 rb_ary_resize(result, RARRAY_LEN(result) + (beg + len) - j);
2610             continue;
2611         }
2612         rb_ary_push(result, (*func)(obj, NUM2LONG(argv[i])));
2613     }
2614     return result;
2615 }
2616 
2617 /*
2618  *  call-seq:
2619  *     ary.values_at(selector, ...)  -> new_ary
2620  *
2621  *  Returns an array containing the elements in +self+ corresponding to the
2622  *  given +selector+(s).
2623  *
2624  *  The selectors may be either integer indices or ranges.
2625  *
2626  *  See also Array#select.
2627  *
2628  *     a = %w{ a b c d e f }
2629  *     a.values_at(1, 3, 5)          # => ["b", "d", "f"]
2630  *     a.values_at(1, 3, 5, 7)       # => ["b", "d", "f", nil]
2631  *     a.values_at(-1, -2, -2, -7)   # => ["f", "e", "e", nil]
2632  *     a.values_at(4..6, 3...6)      # => ["e", "f", nil, "d", "e", "f"]
2633  */
2634 
2635 static VALUE
2636 rb_ary_values_at(int argc, VALUE *argv, VALUE ary)
2637 {
2638     return rb_get_values_at(ary, RARRAY_LEN(ary), argc, argv, rb_ary_entry);
2639 }
2640 
2641 
2642 /*
2643  *  call-seq:
2644  *     ary.select { |item| block } -> new_ary
2645  *     ary.select                  -> Enumerator
2646  *
2647  *  Returns a new array containing all elements of +ary+
2648  *  for which the given +block+ returns a true value.
2649  *
2650  *  If no block is given, an Enumerator is returned instead.
2651  *
2652  *     [1,2,3,4,5].select { |num|  num.even?  }   #=> [2, 4]
2653  *
2654  *     a = %w{ a b c d e f }
2655  *     a.select { |v| v =~ /[aeiou]/ }  #=> ["a", "e"]
2656  *
2657  *  See also Enumerable#select.
2658  */
2659 
2660 static VALUE
2661 rb_ary_select(VALUE ary)
2662 {
2663     VALUE result;
2664     long i;
2665 
2666     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
2667     result = rb_ary_new2(RARRAY_LEN(ary));
2668     for (i = 0; i < RARRAY_LEN(ary); i++) {
2669         if (RTEST(rb_yield(RARRAY_AREF(ary, i)))) {
2670             rb_ary_push(result, rb_ary_elt(ary, i));
2671         }
2672     }
2673     return result;
2674 }
2675 
2676 /*
2677  *  call-seq:
2678  *     ary.select!  {|item| block } -> ary or nil
2679  *     ary.select!                  -> Enumerator
2680  *
2681  *  Invokes the given block passing in successive elements from +self+,
2682  *  deleting elements for which the block returns a +false+ value.
2683  *
2684  *  If changes were made, it will return +self+, otherwise it returns +nil+.
2685  *
2686  *  See also Array#keep_if
2687  *
2688  *  If no block is given, an Enumerator is returned instead.
2689  *
2690  */
2691 
2692 static VALUE
2693 rb_ary_select_bang(VALUE ary)
2694 {
2695     long i1, i2;
2696 
2697     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
2698     rb_ary_modify(ary);
2699     for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
2700         VALUE v = RARRAY_AREF(ary, i1);
2701         if (!RTEST(rb_yield(v))) continue;
2702         if (i1 != i2) {
2703             rb_ary_store(ary, i2, v);
2704         }
2705         i2++;
2706     }
2707 
2708     if (RARRAY_LEN(ary) == i2) return Qnil;
2709     if (i2 < RARRAY_LEN(ary))
2710         ARY_SET_LEN(ary, i2);
2711     return ary;
2712 }
2713 
2714 /*
2715  *  call-seq:
2716  *     ary.keep_if { |item| block } -> ary
2717  *     ary.keep_if                  -> Enumerator
2718  *
2719  *  Deletes every element of +self+ for which the given block evaluates to
2720  *  +false+.
2721  *
2722  *  See also Array#select!
2723  *
2724  *  If no block is given, an Enumerator is returned instead.
2725  *
2726  *     a = %w{ a b c d e f }
2727  *     a.keep_if { |v| v =~ /[aeiou]/ }  #=> ["a", "e"]
2728  */
2729 
2730 static VALUE
2731 rb_ary_keep_if(VALUE ary)
2732 {
2733     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
2734     rb_ary_select_bang(ary);
2735     return ary;
2736 }
2737 
2738 static void
2739 ary_resize_smaller(VALUE ary, long len)
2740 {
2741     rb_ary_modify(ary);
2742     if (RARRAY_LEN(ary) > len) {
2743         ARY_SET_LEN(ary, len);
2744         if (len * 2 < ARY_CAPA(ary) &&
2745             ARY_CAPA(ary) > ARY_DEFAULT_SIZE) {
2746             ary_resize_capa(ary, len * 2);
2747         }
2748     }
2749 }
2750 
2751 /*
2752  *  call-seq:
2753  *     ary.delete(obj)            -> item or nil
2754  *     ary.delete(obj) { block }  -> item or result of block
2755  *
2756  *  Deletes all items from +self+ that are equal to +obj+.
2757  *
2758  *  Returns the last deleted item, or +nil+ if no matching item is found.
2759  *
2760  *  If the optional code block is given, the result of the block is returned if
2761  *  the item is not found.  (To remove +nil+ elements and get an informative
2762  *  return value, use Array#compact!)
2763  *
2764  *     a = [ "a", "b", "b", "b", "c" ]
2765  *     a.delete("b")                   #=> "b"
2766  *     a                               #=> ["a", "c"]
2767  *     a.delete("z")                   #=> nil
2768  *     a.delete("z") { "not found" }   #=> "not found"
2769  */
2770 
2771 VALUE
2772 rb_ary_delete(VALUE ary, VALUE item)
2773 {
2774     VALUE v = item;
2775     long i1, i2;
2776 
2777     for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
2778         VALUE e = RARRAY_AREF(ary, i1);
2779 
2780         if (rb_equal(e, item)) {
2781             v = e;
2782             continue;
2783         }
2784         if (i1 != i2) {
2785             rb_ary_store(ary, i2, e);
2786         }
2787         i2++;
2788     }
2789     if (RARRAY_LEN(ary) == i2) {
2790         if (rb_block_given_p()) {
2791             return rb_yield(item);
2792         }
2793         return Qnil;
2794     }
2795 
2796     ary_resize_smaller(ary, i2);
2797 
2798     return v;
2799 }
2800 
2801 void
2802 rb_ary_delete_same(VALUE ary, VALUE item)
2803 {
2804     long i1, i2;
2805 
2806     for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
2807         VALUE e = RARRAY_AREF(ary, i1);
2808 
2809         if (e == item) {
2810             continue;
2811         }
2812         if (i1 != i2) {
2813             rb_ary_store(ary, i2, e);
2814         }
2815         i2++;
2816     }
2817     if (RARRAY_LEN(ary) == i2) {
2818         return;
2819     }
2820 
2821     ary_resize_smaller(ary, i2);
2822 }
2823 
2824 VALUE
2825 rb_ary_delete_at(VALUE ary, long pos)
2826 {
2827     long len = RARRAY_LEN(ary);
2828     VALUE del;
2829 
2830     if (pos >= len) return Qnil;
2831     if (pos < 0) {
2832         pos += len;
2833         if (pos < 0) return Qnil;
2834     }
2835 
2836     rb_ary_modify(ary);
2837     del = RARRAY_AREF(ary, pos);
2838     MEMMOVE(RARRAY_PTR(ary)+pos, RARRAY_PTR(ary)+pos+1, VALUE,
2839             RARRAY_LEN(ary)-pos-1);
2840     ARY_INCREASE_LEN(ary, -1);
2841 
2842     return del;
2843 }
2844 
2845 /*
2846  *  call-seq:
2847  *     ary.delete_at(index)  -> obj or nil
2848  *
2849  *  Deletes the element at the specified +index+, returning that element, or
2850  *  +nil+ if the +index+ is out of range.
2851  *
2852  *  See also Array#slice!
2853  *
2854  *     a = ["ant", "bat", "cat", "dog"]
2855  *     a.delete_at(2)    #=> "cat"
2856  *     a                 #=> ["ant", "bat", "dog"]
2857  *     a.delete_at(99)   #=> nil
2858  */
2859 
2860 static VALUE
2861 rb_ary_delete_at_m(VALUE ary, VALUE pos)
2862 {
2863     return rb_ary_delete_at(ary, NUM2LONG(pos));
2864 }
2865 
2866 /*
2867  *  call-seq:
2868  *     ary.slice!(index)         -> obj or nil
2869  *     ary.slice!(start, length) -> new_ary or nil
2870  *     ary.slice!(range)         -> new_ary or nil
2871  *
2872  *  Deletes the element(s) given by an +index+ (optionally up to +length+
2873  *  elements) or by a +range+.
2874  *
2875  *  Returns the deleted object (or objects), or +nil+ if the +index+ is out of
2876  *  range.
2877  *
2878  *     a = [ "a", "b", "c" ]
2879  *     a.slice!(1)     #=> "b"
2880  *     a               #=> ["a", "c"]
2881  *     a.slice!(-1)    #=> "c"
2882  *     a               #=> ["a"]
2883  *     a.slice!(100)   #=> nil
2884  *     a               #=> ["a"]
2885  */
2886 
2887 static VALUE
2888 rb_ary_slice_bang(int argc, VALUE *argv, VALUE ary)
2889 {
2890     VALUE arg1, arg2;
2891     long pos, len, orig_len;
2892 
2893     rb_ary_modify_check(ary);
2894     if (argc == 2) {
2895         pos = NUM2LONG(argv[0]);
2896         len = NUM2LONG(argv[1]);
2897       delete_pos_len:
2898         if (len < 0) return Qnil;
2899         orig_len = RARRAY_LEN(ary);
2900         if (pos < 0) {
2901             pos += orig_len;
2902             if (pos < 0) return Qnil;
2903         }
2904         else if (orig_len < pos) return Qnil;
2905         if (orig_len < pos + len) {
2906             len = orig_len - pos;
2907         }
2908         if (len == 0) return rb_ary_new2(0);
2909         arg2 = rb_ary_new4(len, RARRAY_PTR(ary)+pos);
2910         RBASIC_SET_CLASS(arg2, rb_obj_class(ary));
2911         rb_ary_splice(ary, pos, len, Qundef);
2912         return arg2;
2913     }
2914 
2915     if (argc != 1) {
2916         /* error report */
2917         rb_scan_args(argc, argv, "11", NULL, NULL);
2918     }
2919     arg1 = argv[0];
2920 
2921     if (!FIXNUM_P(arg1)) {
2922         switch (rb_range_beg_len(arg1, &pos, &len, RARRAY_LEN(ary), 0)) {
2923           case Qtrue:
2924             /* valid range */
2925             goto delete_pos_len;
2926           case Qnil:
2927             /* invalid range */
2928             return Qnil;
2929           default:
2930             /* not a range */
2931             break;
2932         }
2933     }
2934 
2935     return rb_ary_delete_at(ary, NUM2LONG(arg1));
2936 }
2937 
2938 static VALUE
2939 ary_reject(VALUE orig, VALUE result)
2940 {
2941     long i;
2942 
2943     for (i = 0; i < RARRAY_LEN(orig); i++) {
2944         VALUE v = RARRAY_AREF(orig, i);
2945         if (!RTEST(rb_yield(v))) {
2946             rb_ary_push_1(result, v);
2947         }
2948     }
2949     return result;
2950 }
2951 
2952 static VALUE
2953 ary_reject_bang(VALUE ary)
2954 {
2955     long i;
2956     VALUE result = Qnil;
2957 
2958     rb_ary_modify_check(ary);
2959     for (i = 0; i < RARRAY_LEN(ary); ) {
2960         VALUE v = RARRAY_AREF(ary, i);
2961         if (RTEST(rb_yield(v))) {
2962             rb_ary_delete_at(ary, i);
2963             result = ary;
2964         }
2965         else {
2966             i++;
2967         }
2968     }
2969     return result;
2970 }
2971 
2972 /*
2973  *  call-seq:
2974  *     ary.reject! { |item| block }  -> ary or nil
2975  *     ary.reject!                   -> Enumerator
2976  *
2977  *  Equivalent to Array#delete_if, deleting elements from +self+ for which the
2978  *  block evaluates to +true+, but returns +nil+ if no changes were made.
2979  *
2980  *  The array is changed instantly every time the block is called, not after
2981  *  the iteration is over.
2982  *
2983  *  See also Enumerable#reject and Array#delete_if.
2984  *
2985  *  If no block is given, an Enumerator is returned instead.
2986  */
2987 
2988 static VALUE
2989 rb_ary_reject_bang(VALUE ary)
2990 {
2991     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
2992     return ary_reject_bang(ary);
2993 }
2994 
2995 /*
2996  *  call-seq:
2997  *     ary.reject  {|item| block }  -> new_ary
2998  *     ary.reject                   -> Enumerator
2999  *
3000  *  Returns a new array containing the items in +self+ for which the given
3001  *  block is not +true+.
3002  *
3003  *  See also Array#delete_if
3004  *
3005  *  If no block is given, an Enumerator is returned instead.
3006  */
3007 
3008 static VALUE
3009 rb_ary_reject(VALUE ary)
3010 {
3011     VALUE rejected_ary;
3012 
3013     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
3014     rejected_ary = rb_ary_new();
3015     ary_reject(ary, rejected_ary);
3016     return rejected_ary;
3017 }
3018 
3019 /*
3020  *  call-seq:
3021  *     ary.delete_if { |item| block }  -> ary
3022  *     ary.delete_if                   -> Enumerator
3023  *
3024  *  Deletes every element of +self+ for which block evaluates to +true+.
3025  *
3026  *  The array is changed instantly every time the block is called, not after
3027  *  the iteration is over.
3028  *
3029  *  See also Array#reject!
3030  *
3031  *  If no block is given, an Enumerator is returned instead.
3032  *
3033  *     scores = [ 97, 42, 75 ]
3034  *     scores.delete_if {|score| score < 80 }   #=> [97]
3035  */
3036 
3037 static VALUE
3038 rb_ary_delete_if(VALUE ary)
3039 {
3040     RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length);
3041     ary_reject_bang(ary);
3042     return ary;
3043 }
3044 
3045 static VALUE
3046 take_i(VALUE val, VALUE *args, int argc, VALUE *argv)
3047 {
3048     if (args[1]-- == 0) rb_iter_break();
3049     if (argc > 1) val = rb_ary_new4(argc, argv);
3050     rb_ary_push(args[0], val);
3051     return Qnil;
3052 }
3053 
3054 static VALUE
3055 take_items(VALUE obj, long n)
3056 {
3057     VALUE result = rb_check_array_type(obj);
3058     VALUE args[2];
3059 
3060     if (!NIL_P(result)) return rb_ary_subseq(result, 0, n);
3061     result = rb_ary_new2(n);
3062     args[0] = result; args[1] = (VALUE)n;
3063     if (rb_check_block_call(obj, idEach, 0, 0, take_i, (VALUE)args) == Qundef)
3064         rb_raise(rb_eTypeError, "wrong argument type %"PRIsVALUE" (must respond to :each)",
3065                  rb_obj_class(obj));
3066     return result;
3067 }
3068 
3069 
3070 /*
3071  *  call-seq:
3072  *     ary.zip(arg, ...)                  -> new_ary
3073  *     ary.zip(arg, ...) { |arr| block }  -> nil
3074  *
3075  *  Converts any arguments to arrays, then merges elements of +self+ with
3076  *  corresponding elements from each argument.
3077  *
3078  *  This generates a sequence of <code>ary.size</code> _n_-element arrays,
3079  *  where _n_ is one more than the count of arguments.
3080  *
3081  *  If the size of any argument is less than the size of the initial array,
3082  *  +nil+ values are supplied.
3083  *
3084  *  If a block is given, it is invoked for each output +array+, otherwise an
3085  *  array of arrays is returned.
3086  *
3087  *     a = [ 4, 5, 6 ]
3088  *     b = [ 7, 8, 9 ]
3089  *     [1, 2, 3].zip(a, b)   #=> [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
3090  *     [1, 2].zip(a, b)      #=> [[1, 4, 7], [2, 5, 8]]
3091  *     a.zip([1, 2], [8])    #=> [[4, 1, 8], [5, 2, nil], [6, nil, nil]]
3092  */
3093 
3094 static VALUE
3095 rb_ary_zip(int argc, VALUE *argv, VALUE ary)
3096 {
3097     int i, j;
3098     long len;
3099     VALUE result = Qnil;
3100 
3101     len = RARRAY_LEN(ary);
3102     for (i=0; i<argc; i++) {
3103         argv[i] = take_items(argv[i], len);
3104     }
3105     if (!rb_block_given_p()) {
3106         result = rb_ary_new2(len);
3107     }
3108 
3109     for (i=0; i<RARRAY_LEN(ary); i++) {
3110         VALUE tmp = rb_ary_new2(argc+1);
3111 
3112         rb_ary_push(tmp, rb_ary_elt(ary, i));
3113         for (j=0; j<argc; j++) {
3114             rb_ary_push(tmp, rb_ary_elt(argv[j], i));
3115         }
3116         if (NIL_P(result)) {
3117             rb_yield(tmp);
3118         }
3119         else {
3120             rb_ary_push(result, tmp);
3121         }
3122     }
3123     return result;
3124 }
3125 
3126 /*
3127  *  call-seq:
3128  *     ary.transpose -> new_ary
3129  *
3130  *  Assumes that +self+ is an array of arrays and transposes the rows and
3131  *  columns.
3132  *
3133  *     a = [[1,2], [3,4], [5,6]]
3134  *     a.transpose   #=> [[1, 3, 5], [2, 4, 6]]
3135  *
3136  *  If the length of the subarrays don't match, an IndexError is raised.
3137  */
3138 
3139 static VALUE
3140 rb_ary_transpose(VALUE ary)
3141 {
3142     long elen = -1, alen, i, j;
3143     VALUE tmp, result = 0;
3144 
3145     alen = RARRAY_LEN(ary);
3146     if (alen == 0) return rb_ary_dup(ary);
3147     for (i=0; i<alen; i++) {
3148         tmp = to_ary(rb_ary_elt(ary, i));
3149         if (elen < 0) {         /* first element */
3150             elen = RARRAY_LEN(tmp);
3151             result = rb_ary_new2(elen);
3152             for (j=0; j<elen; j++) {
3153                 rb_ary_store(result, j, rb_ary_new2(alen));
3154             }
3155         }
3156         else if (elen != RARRAY_LEN(tmp)) {
3157             rb_raise(rb_eIndexError, "element size differs (%ld should be %ld)",
3158                      RARRAY_LEN(tmp), elen);
3159         }
3160         for (j=0; j<elen; j++) {
3161             rb_ary_store(rb_ary_elt(result, j), i, rb_ary_elt(tmp, j));
3162         }
3163     }
3164     return result;
3165 }
3166 
3167 /*
3168  *  call-seq:
3169  *     ary.replace(other_ary)  -> ary
3170  *     ary.initialize_copy(other_ary)   -> ary
3171  *
3172  *  Replaces the contents of +self+ with the contents of +other_ary+,
3173  *  truncating or expanding if necessary.
3174  *
3175  *     a = [ "a", "b", "c", "d", "e" ]
3176  *     a.replace([ "x", "y", "z" ])   #=> ["x", "y", "z"]
3177  *     a                              #=> ["x", "y", "z"]
3178  */
3179 
3180 VALUE
3181 rb_ary_replace(VALUE copy, VALUE orig)
3182 {
3183     rb_ary_modify_check(copy);
3184     orig = to_ary(orig);
3185     if (copy == orig) return copy;
3186 
3187     if (RARRAY_LEN(orig) <= RARRAY_EMBED_LEN_MAX) {
3188         VALUE *ptr;
3189         VALUE shared = 0;
3190 
3191         if (ARY_OWNS_HEAP_P(copy)) {
3192             xfree(RARRAY_PTR(copy));
3193         }
3194         else if (ARY_SHARED_P(copy)) {
3195             shared = ARY_SHARED(copy);
3196             FL_UNSET_SHARED(copy);
3197         }
3198         FL_SET_EMBED(copy);
3199         ptr = RARRAY_PTR(orig);
3200         MEMCPY(RARRAY_PTR(copy), ptr, VALUE, RARRAY_LEN(orig));
3201         if (shared) {
3202             rb_ary_decrement_share(shared);
3203         }
3204         ARY_SET_LEN(copy, RARRAY_LEN(orig));
3205     }
3206     else {
3207         VALUE shared = ary_make_shared(orig);
3208         if (ARY_OWNS_HEAP_P(copy)) {
3209             xfree(RARRAY_PTR(copy));
3210         }
3211         else {
3212             rb_ary_unshare_safe(copy);
3213         }
3214         FL_UNSET_EMBED(copy);
3215         ARY_SET_PTR(copy, RARRAY_PTR(orig));
3216         ARY_SET_LEN(copy, RARRAY_LEN(orig));
3217         rb_ary_set_shared(copy, shared);
3218     }
3219     return copy;
3220 }
3221 
3222 /*
3223  *  call-seq:
3224  *     ary.clear    -> ary
3225  *
3226  *  Removes all elements from +self+.
3227  *
3228  *     a = [ "a", "b", "c", "d", "e" ]
3229  *     a.clear    #=> [ ]
3230  */
3231 
3232 VALUE
3233 rb_ary_clear(VALUE ary)
3234 {
3235     rb_ary_modify_check(ary);
3236     ARY_SET_LEN(ary, 0);
3237     if (ARY_SHARED_P(ary)) {
3238         if (!ARY_EMBED_P(ary)) {
3239             rb_ary_unshare(ary);
3240             FL_SET_EMBED(ary);
3241         }
3242     }
3243     else if (ARY_DEFAULT_SIZE * 2 < ARY_CAPA(ary)) {
3244         ary_resize_capa(ary, ARY_DEFAULT_SIZE * 2);
3245     }
3246     return ary;
3247 }
3248 
3249 /*
3250  *  call-seq:
3251  *     ary.fill(obj)                                 -> ary
3252  *     ary.fill(obj, start [, length])               -> ary
3253  *     ary.fill(obj, range )                         -> ary
3254  *     ary.fill { |index| block }                    -> ary
3255  *     ary.fill(start [, length] ) { |index| block } -> ary
3256  *     ary.fill(range) { |index| block }             -> ary
3257  *
3258  *  The first three forms set the selected elements of +self+ (which
3259  *  may be the entire array) to +obj+.
3260  *
3261  *  A +start+ of +nil+ is equivalent to zero.
3262  *
3263  *  A +length+ of +nil+ is equivalent to the length of the array.
3264  *
3265  *  The last three forms fill the array with the value of the given block,
3266  *  which is passed the absolute index of each element to be filled.
3267  *
3268  *  Negative values of +start+ count from the end of the array, where +-1+ is
3269  *  the last element.
3270  *
3271  *     a = [ "a", "b", "c", "d" ]
3272  *     a.fill("x")              #=> ["x", "x", "x", "x"]
3273  *     a.fill("z", 2, 2)        #=> ["x", "x", "z", "z"]
3274  *     a.fill("y", 0..1)        #=> ["y", "y", "z", "z"]
3275  *     a.fill { |i| i*i }       #=> [0, 1, 4, 9]
3276  *     a.fill(-2) { |i| i*i*i } #=> [0, 1, 8, 27]
3277  */
3278 
3279 static VALUE
3280 rb_ary_fill(int argc, VALUE *argv, VALUE ary)
3281 {
3282     VALUE item, arg1, arg2;
3283     long beg = 0, end = 0, len = 0;
3284     VALUE *p, *pend;
3285     int block_p = FALSE;
3286 
3287     if (rb_block_given_p()) {
3288         block_p = TRUE;
3289         rb_scan_args(argc, argv, "02", &arg1, &arg2);
3290         argc += 1;              /* hackish */
3291     }
3292     else {
3293         rb_scan_args(argc, argv, "12", &item, &arg1, &arg2);
3294     }
3295     switch (argc) {
3296       case 1:
3297         beg = 0;
3298         len = RARRAY_LEN(ary);
3299         break;
3300       case 2:
3301         if (rb_range_beg_len(arg1, &beg, &len, RARRAY_LEN(ary), 1)) {
3302             break;
3303         }
3304         /* fall through */
3305       case 3:
3306         beg = NIL_P(arg1) ? 0 : NUM2LONG(arg1);
3307         if (beg < 0) {
3308             beg = RARRAY_LEN(ary) + beg;
3309             if (beg < 0) beg = 0;
3310         }
3311         len = NIL_P(arg2) ? RARRAY_LEN(ary) - beg : NUM2LONG(arg2);
3312         break;
3313     }
3314     rb_ary_modify(ary);
3315     if (len < 0) {
3316         return ary;
3317     }
3318     if (beg >= ARY_MAX_SIZE || len > ARY_MAX_SIZE - beg) {
3319         rb_raise(rb_eArgError, "argument too big");
3320     }
3321     end = beg + len;
3322     if (RARRAY_LEN(ary) < end) {
3323         if (end >= ARY_CAPA(ary)) {
3324             ary_resize_capa(ary, end);
3325         }
3326         rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary), end - RARRAY_LEN(ary));
3327         ARY_SET_LEN(ary, end);
3328     }
3329 
3330     if (block_p) {
3331         VALUE v;
3332         long i;
3333 
3334         for (i=beg; i<end; i++) {
3335             v = rb_yield(LONG2NUM(i));
3336             if (i>=RARRAY_LEN(ary)) break;
3337             RARRAY_ASET(ary, i, v);
3338         }
3339     }
3340     else {
3341         p = RARRAY_PTR(ary) + beg;
3342         pend = p + len;
3343         while (p < pend) {
3344             *p++ = item;
3345         }
3346     }
3347     return ary;
3348 }
3349 
3350 /*
3351  *  call-seq:
3352  *     ary + other_ary   -> new_ary
3353  *
3354  *  Concatenation --- Returns a new array built by concatenating the
3355  *  two arrays together to produce a third array.
3356  *
3357  *     [ 1, 2, 3 ] + [ 4, 5 ]    #=> [ 1, 2, 3, 4, 5 ]
3358  *     a = [ "a", "b", "c" ]
3359  *     c = a + [ "d", "e", "f" ]
3360  *     c                         #=> [ "a", "b", "c", "d", "e", "f" ]
3361  *     a                         #=> [ "a", "b", "c" ]
3362  *
3363  *  See also Array#concat.
3364  */
3365 
3366 VALUE
3367 rb_ary_plus(VALUE x, VALUE y)
3368 {
3369     VALUE z;
3370     long len;
3371 
3372     y = to_ary(y);
3373     len = RARRAY_LEN(x) + RARRAY_LEN(y);
3374     z = rb_ary_new2(len);
3375     MEMCPY(RARRAY_PTR(z), RARRAY_PTR(x), VALUE, RARRAY_LEN(x));
3376     MEMCPY(RARRAY_PTR(z) + RARRAY_LEN(x), RARRAY_PTR(y), VALUE, RARRAY_LEN(y));
3377     ARY_SET_LEN(z, len);
3378     return z;
3379 }
3380 
3381 /*
3382  *  call-seq:
3383  *     ary.concat(other_ary)   -> ary
3384  *
3385  *  Appends the elements of +other_ary+ to +self+.
3386  *
3387  *     [ "a", "b" ].concat( ["c", "d"] ) #=> [ "a", "b", "c", "d" ]
3388  *     a = [ 1, 2, 3 ]
3389  *     a.concat( [ 4, 5 ] )
3390  *     a                                 #=> [ 1, 2, 3, 4, 5 ]
3391  *
3392  *  See also Array#+.
3393  */
3394 
3395 VALUE
3396 rb_ary_concat(VALUE x, VALUE y)
3397 {
3398     rb_ary_modify_check(x);
3399     y = to_ary(y);
3400     if (RARRAY_LEN(y) > 0) {
3401         rb_ary_splice(x, RARRAY_LEN(x), 0, y);
3402     }
3403     return x;
3404 }
3405 
3406 
3407 /*
3408  *  call-seq:
3409  *     ary * int     -> new_ary
3410  *     ary * str     -> new_string
3411  *
3412  *  Repetition --- With a String argument, equivalent to
3413  *  <code>ary.join(str)</code>.
3414  *
3415  *  Otherwise, returns a new array built by concatenating the +int+ copies of
3416  *  +self+.
3417  *
3418  *
3419  *     [ 1, 2, 3 ] * 3    #=> [ 1, 2, 3, 1, 2, 3, 1, 2, 3 ]
3420  *     [ 1, 2, 3 ] * ","  #=> "1,2,3"
3421  *
3422  */
3423 
3424 static VALUE
3425 rb_ary_times(VALUE ary, VALUE times)
3426 {
3427     VALUE ary2, tmp, *ptr, *ptr2;
3428     long t, len;
3429 
3430     tmp = rb_check_string_type(times);
3431     if (!NIL_P(tmp)) {
3432         return rb_ary_join(ary, tmp);
3433     }
3434 
3435     len = NUM2LONG(times);
3436     if (len == 0) {
3437         ary2 = ary_new(rb_obj_class(ary), 0);
3438         goto out;
3439     }
3440     if (len < 0) {
3441         rb_raise(rb_eArgError, "negative argument");
3442     }
3443     if (ARY_MAX_SIZE/len < RARRAY_LEN(ary)) {
3444         rb_raise(rb_eArgError, "argument too big");
3445     }
3446     len *= RARRAY_LEN(ary);
3447 
3448     ary2 = ary_new(rb_obj_class(ary), len);
3449     ARY_SET_LEN(ary2, len);
3450 
3451     ptr = RARRAY_PTR(ary);
3452     ptr2 = RARRAY_PTR(ary2);
3453     t = RARRAY_LEN(ary);
3454     if (0 < t) {
3455         MEMCPY(ptr2, ptr, VALUE, t);
3456         while (t <= len/2) {
3457             MEMCPY(ptr2+t, ptr2, VALUE, t);
3458             t *= 2;
3459         }
3460         if (t < len) {
3461             MEMCPY(ptr2+t, ptr2, VALUE, len-t);
3462         }
3463     }
3464   out:
3465     OBJ_INFECT(ary2, ary);
3466 
3467     return ary2;
3468 }
3469 
3470 /*
3471  *  call-seq:
3472  *     ary.assoc(obj)   -> new_ary  or  nil
3473  *
3474  *  Searches through an array whose elements are also arrays comparing +obj+
3475  *  with the first element of each contained array using <code>obj.==</code>.
3476  *
3477  *  Returns the first contained array that matches (that is, the first
3478  *  associated array), or +nil+ if no match is found.
3479  *
3480  *  See also Array#rassoc
3481  *
3482  *     s1 = [ "colors", "red", "blue", "green" ]
3483  *     s2 = [ "letters", "a", "b", "c" ]
3484  *     s3 = "foo"
3485  *     a  = [ s1, s2, s3 ]
3486  *     a.assoc("letters")  #=> [ "letters", "a", "b", "c" ]
3487  *     a.assoc("foo")      #=> nil
3488  */
3489 
3490 VALUE
3491 rb_ary_assoc(VALUE ary, VALUE key)
3492 {
3493     long i;
3494     VALUE v;
3495 
3496     for (i = 0; i < RARRAY_LEN(ary); ++i) {
3497         v = rb_check_array_type(RARRAY_AREF(ary, i));
3498         if (!NIL_P(v) && RARRAY_LEN(v) > 0 &&
3499             rb_equal(RARRAY_AREF(v, 0), key))
3500             return v;
3501     }
3502     return Qnil;
3503 }
3504 
3505 /*
3506  *  call-seq:
3507  *     ary.rassoc(obj) -> new_ary or nil
3508  *
3509  *  Searches through the array whose elements are also arrays.
3510  *
3511  *  Compares +obj+ with the second element of each contained array using
3512  *  <code>obj.==</code>.
3513  *
3514  *  Returns the first contained array that matches +obj+.
3515  *
3516  *  See also Array#assoc.
3517  *
3518  *     a = [ [ 1, "one"], [2, "two"], [3, "three"], ["ii", "two"] ]
3519  *     a.rassoc("two")    #=> [2, "two"]
3520  *     a.rassoc("four")   #=> nil
3521  */
3522 
3523 VALUE
3524 rb_ary_rassoc(VALUE ary, VALUE value)
3525 {
3526     long i;
3527     VALUE v;
3528 
3529     for (i = 0; i < RARRAY_LEN(ary); ++i) {
3530         v = RARRAY_AREF(ary, i);
3531         if (RB_TYPE_P(v, T_ARRAY) &&
3532             RARRAY_LEN(v) > 1 &&
3533             rb_equal(RARRAY_AREF(v, 1), value))
3534             return v;
3535     }
3536     return Qnil;
3537 }
3538 
3539 static VALUE
3540 recursive_equal(VALUE ary1, VALUE ary2, int recur)
3541 {
3542     long i, len1;
3543     VALUE *p1, *p2;
3544 
3545     if (recur) return Qtrue; /* Subtle! */
3546 
3547     p1 = RARRAY_PTR(ary1);
3548     p2 = RARRAY_PTR(ary2);
3549     len1 = RARRAY_LEN(ary1);
3550 
3551     for (i = 0; i < len1; i++) {
3552         if (*p1 != *p2) {
3553             if (rb_equal(*p1, *p2)) {
3554                 len1 = RARRAY_LEN(ary1);
3555                 if (len1 != RARRAY_LEN(ary2))
3556                     return Qfalse;
3557                 if (len1 < i)
3558                     return Qtrue;
3559                 p1 = RARRAY_PTR(ary1) + i;
3560                 p2 = RARRAY_PTR(ary2) + i;
3561             }
3562             else {
3563                 return Qfalse;
3564             }
3565         }
3566         p1++;
3567         p2++;
3568     }
3569     return Qtrue;
3570 }
3571 
3572 /*
3573  *  call-seq:
3574  *     ary == other_ary   ->   bool
3575  *
3576  *  Equality --- Two arrays are equal if they contain the same number of
3577  *  elements and if each element is equal to (according to Object#==) the
3578  *  corresponding element in +other_ary+.
3579  *
3580  *     [ "a", "c" ]    == [ "a", "c", 7 ]     #=> false
3581  *     [ "a", "c", 7 ] == [ "a", "c", 7 ]     #=> true
3582  *     [ "a", "c", 7 ] == [ "a", "d", "f" ]   #=> false
3583  *
3584  */
3585 
3586 static VALUE
3587 rb_ary_equal(VALUE ary1, VALUE ary2)
3588 {
3589     if (ary1 == ary2) return Qtrue;
3590     if (!RB_TYPE_P(ary2, T_ARRAY)) {
3591         if (!rb_respond_to(ary2, rb_intern("to_ary"))) {
3592             return Qfalse;
3593         }
3594         return rb_equal(ary2, ary1);
3595     }
3596     if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
3597     return rb_exec_recursive_paired(recursive_equal, ary1, ary2, ary2);
3598 }
3599 
3600 static VALUE
3601 recursive_eql(VALUE ary1, VALUE ary2, int recur)
3602 {
3603     long i;
3604 
3605     if (recur) return Qtrue; /* Subtle! */
3606     for (i=0; i<RARRAY_LEN(ary1); i++) {
3607         if (!rb_eql(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
3608             return Qfalse;
3609     }
3610     return Qtrue;
3611 }
3612 
3613 /*
3614  *  call-seq:
3615  *     ary.eql?(other)  -> true or false
3616  *
3617  *  Returns +true+ if +self+ and +other+ are the same object,
3618  *  or are both arrays with the same content (according to Object#eql?).
3619  */
3620 
3621 static VALUE
3622 rb_ary_eql(VALUE ary1, VALUE ary2)
3623 {
3624     if (ary1 == ary2) return Qtrue;
3625     if (!RB_TYPE_P(ary2, T_ARRAY)) return Qfalse;
3626     if (RARRAY_LEN(ary1) != RARRAY_LEN(ary2)) return Qfalse;
3627     return rb_exec_recursive_paired(recursive_eql, ary1, ary2, ary2);
3628 }
3629 
3630 static VALUE
3631 recursive_hash(VALUE ary, VALUE dummy, int recur)
3632 {
3633     long i;
3634     st_index_t h;
3635     VALUE n;
3636 
3637     h = rb_hash_start(RARRAY_LEN(ary));
3638     if (recur) {
3639         h = rb_hash_uint(h, NUM2LONG(rb_hash(rb_cArray)));
3640     }
3641     else {
3642         for (i=0; i<RARRAY_LEN(ary); i++) {
3643             n = rb_hash(RARRAY_AREF(ary, i));
3644             h = rb_hash_uint(h, NUM2LONG(n));
3645         }
3646     }
3647     h = rb_hash_end(h);
3648     return LONG2FIX(h);
3649 }
3650 
3651 /*
3652  *  call-seq:
3653  *     ary.hash   -> fixnum
3654  *
3655  *  Compute a hash-code for this array.
3656  *
3657  *  Two arrays with the same content will have the same hash code (and will
3658  *  compare using #eql?).
3659  */
3660 
3661 static VALUE
3662 rb_ary_hash(VALUE ary)
3663 {
3664     return rb_exec_recursive_outer(recursive_hash, ary, 0);
3665 }
3666 
3667 /*
3668  *  call-seq:
3669  *     ary.include?(object)   -> true or false
3670  *
3671  *  Returns +true+ if the given +object+ is present in +self+ (that is, if any
3672  *  element <code>==</code> +object+), otherwise returns +false+.
3673  *
3674  *     a = [ "a", "b", "c" ]
3675  *     a.include?("b")   #=> true
3676  *     a.include?("z")   #=> false
3677  */
3678 
3679 VALUE
3680 rb_ary_includes(VALUE ary, VALUE item)
3681 {
3682     long i;
3683 
3684     for (i=0; i<RARRAY_LEN(ary); i++) {
3685         if (rb_equal(RARRAY_AREF(ary, i), item)) {
3686             return Qtrue;
3687         }
3688     }
3689     return Qfalse;
3690 }
3691 
3692 
3693 static VALUE
3694 recursive_cmp(VALUE ary1, VALUE ary2, int recur)
3695 {
3696     long i, len;
3697 
3698     if (recur) return Qundef;   /* Subtle! */
3699     len = RARRAY_LEN(ary1);
3700     if (len > RARRAY_LEN(ary2)) {
3701         len = RARRAY_LEN(ary2);
3702     }
3703     for (i=0; i<len; i++) {
3704         VALUE v = rb_funcall(rb_ary_elt(ary1, i), id_cmp, 1, rb_ary_elt(ary2, i));
3705         if (v != INT2FIX(0)) {
3706             return v;
3707         }
3708     }
3709     return Qundef;
3710 }
3711 
3712 /*
3713  *  call-seq:
3714  *     ary <=> other_ary   ->  -1, 0, +1 or nil
3715  *
3716  *  Comparison --- Returns an integer (+-1+, +0+, or <code>+1</code>) if this
3717  *  array is less than, equal to, or greater than +other_ary+.
3718  *
3719  *  +nil+ is returned if the two values are incomparable.
3720  *
3721  *  Each object in each array is compared (using the <=> operator).
3722  *
3723  *  Arrays are compared in an "element-wise" manner; the first two elements
3724  *  that are not equal will determine the return value for the whole
3725  *  comparison.
3726  *
3727  *  If all the values are equal, then the return is based on a comparison of
3728  *  the array lengths. Thus, two arrays are "equal" according to Array#<=> if,
3729  *  and only if, they have the same length and the value of each element is
3730  *  equal to the value of the corresponding element in the other array.
3731  *
3732  *     [ "a", "a", "c" ]    <=> [ "a", "b", "c" ]   #=> -1
3733  *     [ 1, 2, 3, 4, 5, 6 ] <=> [ 1, 2 ]            #=> +1
3734  *
3735  */
3736 
3737 VALUE
3738 rb_ary_cmp(VALUE ary1, VALUE ary2)
3739 {
3740     long len;
3741     VALUE v;
3742 
3743     ary2 = rb_check_array_type(ary2);
3744     if (NIL_P(ary2)) return Qnil;
3745     if (ary1 == ary2) return INT2FIX(0);
3746     v = rb_exec_recursive_paired(recursive_cmp, ary1, ary2, ary2);
3747     if (v != Qundef) return v;
3748     len = RARRAY_LEN(ary1) - RARRAY_LEN(ary2);
3749     if (len == 0) return INT2FIX(0);
3750     if (len > 0) return INT2FIX(1);
3751     return INT2FIX(-1);
3752 }
3753 
3754 static VALUE
3755 ary_add_hash(VALUE hash, VALUE ary)
3756 {
3757     long i;
3758 
3759     for (i=0; i<RARRAY_LEN(ary); i++) {
3760         rb_hash_aset(hash, RARRAY_AREF(ary, i), Qtrue);
3761     }
3762     return hash;
3763 }
3764 
3765 static inline VALUE
3766 ary_tmp_hash_new(void)
3767 {
3768     VALUE hash = rb_hash_new();
3769 
3770     RBASIC_CLEAR_CLASS(hash);
3771     return hash;
3772 }
3773 
3774 static VALUE
3775 ary_make_hash(VALUE ary)
3776 {
3777     VALUE hash = ary_tmp_hash_new();
3778     return ary_add_hash(hash, ary);
3779 }
3780 
3781 static VALUE
3782 ary_add_hash_by(VALUE hash, VALUE ary)
3783 {
3784     long i;
3785 
3786     for (i = 0; i < RARRAY_LEN(ary); ++i) {
3787         VALUE v = rb_ary_elt(ary, i), k = rb_yield(v);
3788         if (rb_hash_lookup2(hash, k, Qundef) == Qundef) {
3789             rb_hash_aset(hash, k, v);
3790         }
3791     }
3792     return hash;
3793 }
3794 
3795 static VALUE
3796 ary_make_hash_by(VALUE ary)
3797 {
3798     VALUE hash = ary_tmp_hash_new();
3799     return ary_add_hash_by(hash, ary);
3800 }
3801 
3802 static inline void
3803 ary_recycle_hash(VALUE hash)
3804 {
3805     if (RHASH(hash)->ntbl) {
3806         st_table *tbl = RHASH(hash)->ntbl;
3807         RHASH(hash)->ntbl = 0;
3808         st_free_table(tbl);
3809     }
3810 }
3811 
3812 /*
3813  *  call-seq:
3814  *     ary - other_ary    -> new_ary
3815  *
3816  *  Array Difference
3817  *
3818  *  Returns a new array that is a copy of the original array, removing any
3819  *  items that also appear in +other_ary+. The order is preserved from the
3820  *  original array.
3821  *
3822  *  It compares elements using their #hash and #eql? methods for efficiency.
3823  *
3824  *     [ 1, 1, 2, 2, 3, 3, 4, 5 ] - [ 1, 2, 4 ]  #=>  [ 3, 3, 5 ]
3825  *
3826  *  If you need set-like behavior, see the library class Set.
3827  */
3828 
3829 static VALUE
3830 rb_ary_diff(VALUE ary1, VALUE ary2)
3831 {
3832     VALUE ary3;
3833     volatile VALUE hash;
3834     long i;
3835 
3836     hash = ary_make_hash(to_ary(ary2));
3837     ary3 = rb_ary_new();
3838 
3839     for (i=0; i<RARRAY_LEN(ary1); i++) {
3840         if (st_lookup(rb_hash_tbl_raw(hash), RARRAY_AREF(ary1, i), 0)) continue;
3841         rb_ary_push(ary3, rb_ary_elt(ary1, i));
3842     }
3843     ary_recycle_hash(hash);
3844     return ary3;
3845 }
3846 
3847 /*
3848  *  call-seq:
3849  *     ary & other_ary      -> new_ary
3850  *
3851  *  Set Intersection --- Returns a new array containing elements common to the
3852  *  two arrays, excluding any duplicates. The order is preserved from the
3853  *  original array.
3854  *
3855  *  It compares elements using their #hash and #eql? methods for efficiency.
3856  *
3857  *     [ 1, 1, 3, 5 ] & [ 1, 2, 3 ]                 #=> [ 1, 3 ]
3858  *     [ 'a', 'b', 'b', 'z' ] & [ 'a', 'b', 'c' ]   #=> [ 'a', 'b' ]
3859  *
3860  *  See also Array#uniq.
3861  */
3862 
3863 
3864 static VALUE
3865 rb_ary_and(VALUE ary1, VALUE ary2)
3866 {
3867     VALUE hash, ary3, v;
3868     st_data_t vv;
3869     long i;
3870 
3871     ary2 = to_ary(ary2);
3872     ary3 = rb_ary_new2(RARRAY_LEN(ary1) < RARRAY_LEN(ary2) ?
3873             RARRAY_LEN(ary1) : RARRAY_LEN(ary2));
3874     hash = ary_make_hash(ary2);
3875 
3876     if (RHASH_EMPTY_P(hash))
3877         return ary3;
3878 
3879     for (i=0; i<RARRAY_LEN(ary1); i++) {
3880         vv = (st_data_t)(v = rb_ary_elt(ary1, i));
3881         if (st_delete(rb_hash_tbl_raw(hash), &vv, 0)) {
3882             rb_ary_push(ary3, v);
3883         }
3884     }
3885     ary_recycle_hash(hash);
3886 
3887     return ary3;
3888 }
3889 
3890 /*
3891  *  call-seq:
3892  *     ary | other_ary     -> new_ary
3893  *
3894  *  Set Union --- Returns a new array by joining +ary+ with +other_ary+,
3895  *  excluding any duplicates and preserving the order from the original array.
3896  *
3897  *  It compares elements using their #hash and #eql? methods for efficiency.
3898  *
3899  *     [ "a", "b", "c" ] | [ "c", "d", "a" ]    #=> [ "a", "b", "c", "d" ]
3900  *
3901  *  See also Array#uniq.
3902  */
3903 
3904 static VALUE
3905 rb_ary_or(VALUE ary1, VALUE ary2)
3906 {
3907     VALUE hash, ary3, v;
3908     st_data_t vv;
3909     long i;
3910 
3911     ary2 = to_ary(ary2);
3912     ary3 = rb_ary_new2(RARRAY_LEN(ary1)+RARRAY_LEN(ary2));
3913     hash = ary_add_hash(ary_make_hash(ary1), ary2);
3914 
3915     for (i=0; i<RARRAY_LEN(ary1); i++) {
3916         vv = (st_data_t)(v = rb_ary_elt(ary1, i));
3917         if (st_delete(rb_hash_tbl_raw(hash), &vv, 0)) {
3918             rb_ary_push(ary3, v);
3919         }
3920     }
3921     for (i=0; i<RARRAY_LEN(ary2); i++) {
3922         vv = (st_data_t)(v = rb_ary_elt(ary2, i));
3923         if (st_delete(rb_hash_tbl_raw(hash), &vv, 0)) {
3924             rb_ary_push(ary3, v);
3925         }
3926     }
3927     ary_recycle_hash(hash);
3928     return ary3;
3929 }
3930 
3931 static int
3932 push_value(st_data_t key, st_data_t val, st_data_t ary)
3933 {
3934     rb_ary_push((VALUE)ary, (VALUE)val);
3935     return ST_CONTINUE;
3936 }
3937 
3938 /*
3939  *  call-seq:
3940  *     ary.uniq!                -> ary or nil
3941  *     ary.uniq! { |item| ... } -> ary or nil
3942  *
3943  *  Removes duplicate elements from +self+.
3944  *
3945  *  If a block is given, it will use the return value of the block for
3946  *  comparison.
3947  *
3948  *  It compares values using their #hash and #eql? methods for efficiency.
3949  *
3950  *  Returns +nil+ if no changes are made (that is, no duplicates are found).
3951  *
3952  *     a = [ "a", "a", "b", "b", "c" ]
3953  *     a.uniq!   # => ["a", "b", "c"]
3954  *
3955  *     b = [ "a", "b", "c" ]
3956  *     b.uniq!   # => nil
3957  *
3958  *     c = [["student","sam"], ["student","george"], ["teacher","matz"]]
3959  *     c.uniq! { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]]
3960  *
3961  */
3962 
3963 static VALUE
3964 rb_ary_uniq_bang(VALUE ary)
3965 {
3966     VALUE hash, v;
3967     long i, j;
3968 
3969     rb_ary_modify_check(ary);
3970     if (RARRAY_LEN(ary) <= 1)
3971         return Qnil;
3972     if (rb_block_given_p()) {
3973         hash = ary_make_hash_by(ary);
3974         if (RARRAY_LEN(ary) == (i = RHASH_SIZE(hash))) {
3975             return Qnil;
3976         }
3977         rb_ary_modify(ary);
3978         ARY_SET_LEN(ary, 0);
3979         if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
3980             rb_ary_unshare(ary);
3981             FL_SET_EMBED(ary);
3982         }
3983         ary_resize_capa(ary, i);
3984         st_foreach(rb_hash_tbl_raw(hash), push_value, ary);
3985     }
3986     else {
3987         hash = ary_make_hash(ary);
3988         if (RARRAY_LEN(ary) == (long)RHASH_SIZE(hash)) {
3989             return Qnil;
3990         }
3991         for (i=j=0; i<RARRAY_LEN(ary); i++) {
3992             st_data_t vv = (st_data_t)(v = rb_ary_elt(ary, i));
3993             if (st_delete(rb_hash_tbl_raw(hash), &vv, 0)) {
3994                 rb_ary_store(ary, j++, v);
3995             }
3996         }
3997         ARY_SET_LEN(ary, j);
3998     }
3999     ary_recycle_hash(hash);
4000 
4001     return ary;
4002 }
4003 
4004 /*
4005  *  call-seq:
4006  *     ary.uniq                -> new_ary
4007  *     ary.uniq { |item| ... } -> new_ary
4008  *
4009  *  Returns a new array by removing duplicate values in +self+.
4010  *
4011  *  If a block is given, it will use the return value of the block for comparison.
4012  *
4013  *  It compares values using their #hash and #eql? methods for efficiency.
4014  *
4015  *     a = [ "a", "a", "b", "b", "c" ]
4016  *     a.uniq   # => ["a", "b", "c"]
4017  *
4018  *     b = [["student","sam"], ["student","george"], ["teacher","matz"]]
4019  *     b.uniq { |s| s.first } # => [["student", "sam"], ["teacher", "matz"]]
4020  *
4021  */
4022 
4023 static VALUE
4024 rb_ary_uniq(VALUE ary)
4025 {
4026     VALUE hash, uniq, v;
4027     long i;
4028 
4029     if (RARRAY_LEN(ary) <= 1)
4030         return rb_ary_dup(ary);
4031     if (rb_block_given_p()) {
4032         hash = ary_make_hash_by(ary);
4033         uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash));
4034         st_foreach(rb_hash_tbl_raw(hash), push_value, uniq);
4035     }
4036     else {
4037         hash = ary_make_hash(ary);
4038         uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash));
4039         for (i=0; i<RARRAY_LEN(ary); i++) {
4040             st_data_t vv = (st_data_t)(v = rb_ary_elt(ary, i));
4041             if (st_delete(rb_hash_tbl_raw(hash), &vv, 0)) {
4042                 rb_ary_push(uniq, v);
4043             }
4044         }
4045     }
4046     ary_recycle_hash(hash);
4047 
4048     return uniq;
4049 }
4050 
4051 /*
4052  *  call-seq:
4053  *     ary.compact!    -> ary  or  nil
4054  *
4055  *  Removes +nil+ elements from the array.
4056  *
4057  *  Returns +nil+ if no changes were made, otherwise returns the array.
4058  *
4059  *     [ "a", nil, "b", nil, "c" ].compact! #=> [ "a", "b", "c" ]
4060  *     [ "a", "b", "c" ].compact!           #=> nil
4061  */
4062 
4063 static VALUE
4064 rb_ary_compact_bang(VALUE ary)
4065 {
4066     VALUE *p, *t, *end;
4067     long n;
4068 
4069     rb_ary_modify(ary);
4070     p = t = RARRAY_PTR(ary);
4071     end = p + RARRAY_LEN(ary);
4072 
4073     while (t < end) {
4074         if (NIL_P(*t)) t++;
4075         else *p++ = *t++;
4076     }
4077     n = p - RARRAY_PTR(ary);
4078     if (RARRAY_LEN(ary) == n) {
4079         return Qnil;
4080     }
4081     ARY_SET_LEN(ary, n);
4082     if (n * 2 < ARY_CAPA(ary) && ARY_DEFAULT_SIZE * 2 < ARY_CAPA(ary)) {
4083         ary_resize_capa(ary, n * 2);
4084     }
4085 
4086     return ary;
4087 }
4088 
4089 /*
4090  *  call-seq:
4091  *     ary.compact     -> new_ary
4092  *
4093  *  Returns a copy of +self+ with all +nil+ elements removed.
4094  *
4095  *     [ "a", nil, "b", nil, "c", nil ].compact
4096  *                       #=> [ "a", "b", "c" ]
4097  */
4098 
4099 static VALUE
4100 rb_ary_compact(VALUE ary)
4101 {
4102     ary = rb_ary_dup(ary);
4103     rb_ary_compact_bang(ary);
4104     return ary;
4105 }
4106 
4107 /*
4108  *  call-seq:
4109  *     ary.count                   -> int
4110  *     ary.count(obj)              -> int
4111  *     ary.count { |item| block }  -> int
4112  *
4113  *  Returns the number of elements.
4114  *
4115  *  If an argument is given, counts the number of elements which equal +obj+
4116  *  using <code>===</code>.
4117  *
4118  *  If a block is given, counts the number of elements for which the block
4119  *  returns a true value.
4120  *
4121  *     ary = [1, 2, 4, 2]
4122  *     ary.count                  #=> 4
4123  *     ary.count(2)               #=> 2
4124  *     ary.count { |x| x%2 == 0 } #=> 3
4125  *
4126  */
4127 
4128 static VALUE
4129 rb_ary_count(int argc, VALUE *argv, VALUE ary)
4130 {
4131     long n = 0;
4132 
4133     if (argc == 0) {
4134         VALUE *p, *pend;
4135 
4136         if (!rb_block_given_p())
4137             return LONG2NUM(RARRAY_LEN(ary));
4138 
4139         for (p = RARRAY_PTR(ary), pend = p + RARRAY_LEN(ary); p < pend; p++) {
4140             if (RTEST(rb_yield(*p))) n++;
4141         }
4142     }
4143     else {
4144         VALUE obj, *p, *pend;
4145 
4146         rb_scan_args(argc, argv, "1", &obj);
4147         if (rb_block_given_p()) {
4148             rb_warn("given block not used");
4149         }
4150         for (p = RARRAY_PTR(ary), pend = p + RARRAY_LEN(ary); p < pend; p++) {
4151             if (rb_equal(*p, obj)) n++;
4152         }
4153     }
4154 
4155     return LONG2NUM(n);
4156 }
4157 
4158 static VALUE
4159 flatten(VALUE ary, int level, int *modified)
4160 {
4161     long i = 0;
4162     VALUE stack, result, tmp, elt;
4163     st_table *memo;
4164     st_data_t id;
4165 
4166     stack = ary_new(0, ARY_DEFAULT_SIZE);
4167     result = ary_new(0, RARRAY_LEN(ary));
4168     memo = st_init_numtable();
4169     st_insert(memo, (st_data_t)ary, (st_data_t)Qtrue);
4170     *modified = 0;
4171 
4172     while (1) {
4173         while (i < RARRAY_LEN(ary)) {
4174             elt = RARRAY_AREF(ary, i++);
4175             tmp = rb_check_array_type(elt);
4176             if (RBASIC(result)->klass) {
4177                 rb_raise(rb_eRuntimeError, "flatten reentered");
4178             }
4179             if (NIL_P(tmp) || (level >= 0 && RARRAY_LEN(stack) / 2 >= level)) {
4180                 rb_ary_push(result, elt);
4181             }
4182             else {
4183                 *modified = 1;
4184                 id = (st_data_t)tmp;
4185                 if (st_lookup(memo, id, 0)) {
4186                     st_free_table(memo);
4187                     rb_raise(rb_eArgError, "tried to flatten recursive array");
4188                 }
4189                 st_insert(memo, id, (st_data_t)Qtrue);
4190                 rb_ary_push(stack, ary);
4191                 rb_ary_push(stack, LONG2NUM(i));
4192                 ary = tmp;
4193                 i = 0;
4194             }
4195         }
4196         if (RARRAY_LEN(stack) == 0) {
4197             break;
4198         }
4199         id = (st_data_t)ary;
4200         st_delete(memo, &id, 0);
4201         tmp = rb_ary_pop(stack);
4202         i = NUM2LONG(tmp);
4203         ary = rb_ary_pop(stack);
4204     }
4205 
4206     st_free_table(memo);
4207 
4208     RBASIC_SET_CLASS(result, rb_class_of(ary));
4209     return result;
4210 }
4211 
4212 /*
4213  *  call-seq:
4214  *     ary.flatten!        -> ary or nil
4215  *     ary.flatten!(level) -> ary or nil
4216  *
4217  *  Flattens +self+ in place.
4218  *
4219  *  Returns +nil+ if no modifications were made (i.e., the array contains no
4220  *  subarrays.)
4221  *
4222  *  The optional +level+ argument determines the level of recursion to flatten.
4223  *
4224  *     a = [ 1, 2, [3, [4, 5] ] ]
4225  *     a.flatten!   #=> [1, 2, 3, 4, 5]
4226  *     a.flatten!   #=> nil
4227  *     a            #=> [1, 2, 3, 4, 5]
4228  *     a = [ 1, 2, [3, [4, 5] ] ]
4229  *     a.flatten!(1) #=> [1, 2, 3, [4, 5]]
4230  */
4231 
4232 static VALUE
4233 rb_ary_flatten_bang(int argc, VALUE *argv, VALUE ary)
4234 {
4235     int mod = 0, level = -1;
4236     VALUE result, lv;
4237 
4238     rb_scan_args(argc, argv, "01", &lv);
4239     rb_ary_modify_check(ary);
4240     if (!NIL_P(lv)) level = NUM2INT(lv);
4241     if (level == 0) return Qnil;
4242 
4243     result = flatten(ary, level, &mod);
4244     if (mod == 0) {
4245         ary_discard(result);
4246         return Qnil;
4247     }
4248     if (!(mod = ARY_EMBED_P(result))) rb_obj_freeze(result);
4249     rb_ary_replace(ary, result);
4250     if (mod) ARY_SET_EMBED_LEN(result, 0);
4251 
4252     return ary;
4253 }
4254 
4255 /*
4256  *  call-seq:
4257  *     ary.flatten -> new_ary
4258  *     ary.flatten(level) -> new_ary
4259  *
4260  *  Returns a new array that is a one-dimensional flattening of +self+
4261  *  (recursively).
4262  *
4263  *  That is, for every element that is an array, extract its elements into
4264  *  the new array.
4265  *
4266  *  The optional +level+ argument determines the level of recursion to
4267  *  flatten.
4268  *
4269  *     s = [ 1, 2, 3 ]           #=> [1, 2, 3]
4270  *     t = [ 4, 5, 6, [7, 8] ]   #=> [4, 5, 6, [7, 8]]
4271  *     a = [ s, t, 9, 10 ]       #=> [[1, 2, 3], [4, 5, 6, [7, 8]], 9, 10]
4272  *     a.flatten                 #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
4273  *     a = [ 1, 2, [3, [4, 5] ] ]
4274  *     a.flatten(1)              #=> [1, 2, 3, [4, 5]]
4275  */
4276 
4277 static VALUE
4278 rb_ary_flatten(int argc, VALUE *argv, VALUE ary)
4279 {
4280     int mod = 0, level = -1;
4281     VALUE result, lv;
4282 
4283     rb_scan_args(argc, argv, "01", &lv);
4284     if (!NIL_P(lv)) level = NUM2INT(lv);
4285     if (level == 0) return ary_make_shared_copy(ary);
4286 
4287     result = flatten(ary, level, &mod);
4288     OBJ_INFECT(result, ary);
4289 
4290     return result;
4291 }
4292 
4293 #define OPTHASH_GIVEN_P(opts) \
4294     (argc > 0 && !NIL_P((opts) = rb_check_hash_type(argv[argc-1])) && (--argc, 1))
4295 static VALUE sym_random;
4296 
4297 #define RAND_UPTO(max) (long)rb_random_ulong_limited((randgen), (max)-1)
4298 
4299 /*
4300  *  call-seq:
4301  *     ary.shuffle!              -> ary
4302  *     ary.shuffle!(random: rng) -> ary
4303  *
4304  *  Shuffles elements in +self+ in place.
4305  *
4306  *  The optional +rng+ argument will be used as the random number generator.
4307  */
4308 
4309 static VALUE
4310 rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary)
4311 {
4312     VALUE *ptr, opts, *snap_ptr, randgen = rb_cRandom;
4313     long i, snap_len;
4314 
4315     if (OPTHASH_GIVEN_P(opts)) {
4316         randgen = rb_hash_lookup2(opts, sym_random, randgen);
4317     }
4318     rb_check_arity(argc, 0, 0);
4319     rb_ary_modify(ary);
4320     i = RARRAY_LEN(ary);
4321     ptr = RARRAY_PTR(ary);
4322     snap_len = i;
4323     snap_ptr = ptr;
4324     while (i) {
4325         long j = RAND_UPTO(i);
4326         VALUE tmp;
4327         if (snap_len != RARRAY_LEN(ary) || snap_ptr != RARRAY_PTR(ary)) {
4328             rb_raise(rb_eRuntimeError, "modified during shuffle");
4329         }
4330         tmp = ptr[--i];
4331         ptr[i] = ptr[j];
4332         ptr[j] = tmp;
4333     }
4334     return ary;
4335 }
4336 
4337 
4338 /*
4339  *  call-seq:
4340  *     ary.shuffle              -> new_ary
4341  *     ary.shuffle(random: rng) -> new_ary
4342  *
4343  *  Returns a new array with elements of +self+ shuffled.
4344  *
4345  *     a = [ 1, 2, 3 ]           #=> [1, 2, 3]
4346  *     a.shuffle                 #=> [2, 3, 1]
4347  *
4348  *  The optional +rng+ argument will be used as the random number generator.
4349  *
4350  *     a.shuffle(random: Random.new(1))  #=> [1, 3, 2]
4351  */
4352 
4353 static VALUE
4354 rb_ary_shuffle(int argc, VALUE *argv, VALUE ary)
4355 {
4356     ary = rb_ary_dup(ary);
4357     rb_ary_shuffle_bang(argc, argv, ary);
4358     return ary;
4359 }
4360 
4361 
4362 /*
4363  *  call-seq:
4364  *     ary.sample                  -> obj
4365  *     ary.sample(random: rng)     -> obj
4366  *     ary.sample(n)               -> new_ary
4367  *     ary.sample(n, random: rng)  -> new_ary
4368  *
4369  *  Choose a random element or +n+ random elements from the array.
4370  *
4371  *  The elements are chosen by using random and unique indices into the array
4372  *  in order to ensure that an element doesn't repeat itself unless the array
4373  *  already contained duplicate elements.
4374  *
4375  *  If the array is empty the first form returns +nil+ and the second form
4376  *  returns an empty array.
4377  *
4378  *  The optional +rng+ argument will be used as the random number generator.
4379  *
4380  *     a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
4381  *     a.sample         #=> 7
4382  *     a.sample(4)      #=> [6, 4, 2, 5]
4383  */
4384 
4385 
4386 static VALUE
4387 rb_ary_sample(int argc, VALUE *argv, VALUE ary)
4388 {
4389     VALUE nv, result, *ptr;
4390     VALUE opts, randgen = rb_cRandom;
4391     long n, len, i, j, k, idx[10];
4392     long rnds[numberof(idx)];
4393 
4394     if (OPTHASH_GIVEN_P(opts)) {
4395         randgen = rb_hash_lookup2(opts, sym_random, randgen);
4396     }
4397     ptr = RARRAY_PTR(ary);
4398     len = RARRAY_LEN(ary);
4399     if (argc == 0) {
4400         if (len == 0) return Qnil;
4401         if (len == 1) {
4402             i = 0;
4403         }
4404         else {
4405             i = RAND_UPTO(len);
4406             if ((len = RARRAY_LEN(ary)) <= i) return Qnil;
4407             ptr = RARRAY_PTR(ary);
4408         }
4409         return ptr[i];
4410     }
4411     rb_scan_args(argc, argv, "1", &nv);
4412     n = NUM2LONG(nv);
4413     if (n < 0) rb_raise(rb_eArgError, "negative sample number");
4414     if (n > len) n = len;
4415     if (n <= numberof(idx)) {
4416         for (i = 0; i < n; ++i) {
4417             rnds[i] = RAND_UPTO(len - i);
4418         }
4419     }
4420     k = len;
4421     len = RARRAY_LEN(ary);
4422     ptr = RARRAY_PTR(ary);
4423     if (len < k) {
4424         if (n <= numberof(idx)) {
4425             for (i = 0; i < n; ++i) {
4426                 if (rnds[i] >= len) {
4427                     return rb_ary_new2(0);
4428                 }
4429             }
4430         }
4431     }
4432     if (n > len) n = len;
4433     switch (n) {
4434       case 0:
4435         return rb_ary_new2(0);
4436       case 1:
4437         i = rnds[0];
4438         return rb_ary_new4(1, &ptr[i]);
4439       case 2:
4440         i = rnds[0];
4441         j = rnds[1];
4442         if (j >= i) j++;
4443         return rb_ary_new3(2, ptr[i], ptr[j]);
4444       case 3:
4445         i = rnds[0];
4446         j = rnds[1];
4447         k = rnds[2];
4448         {
4449             long l = j, g = i;
4450             if (j >= i) l = i, g = ++j;
4451             if (k >= l && (++k >= g)) ++k;
4452         }
4453         return rb_ary_new3(3, ptr[i], ptr[j], ptr[k]);
4454     }
4455     if (n <= numberof(idx)) {
4456         VALUE *ptr_result;
4457         long sorted[numberof(idx)];
4458         sorted[0] = idx[0] = rnds[0];
4459         for (i=1; i<n; i++) {
4460             k = rnds[i];
4461             for (j = 0; j < i; ++j) {
4462                 if (k < sorted[j]) break;
4463                 ++k;
4464             }
4465             memmove(&sorted[j+1], &sorted[j], sizeof(sorted[0])*(i-j));
4466             sorted[j] = idx[i] = k;
4467         }
4468         result = rb_ary_new2(n);
4469         ptr_result = RARRAY_PTR(result);
4470         for (i=0; i<n; i++) {
4471             ptr_result[i] = ptr[idx[i]];
4472         }
4473     }
4474     else {
4475         VALUE *ptr_result;
4476         result = rb_ary_new4(len, ptr);
4477         RBASIC_CLEAR_CLASS(result);
4478         ptr_result = RARRAY_PTR(result);
4479         RB_GC_GUARD(ary);
4480         for (i=0; i<n; i++) {
4481             j = RAND_UPTO(len-i) + i;
4482             nv = ptr_result[j];
4483             ptr_result[j] = ptr_result[i];
4484             ptr_result[i] = nv;
4485         }
4486         RBASIC_SET_CLASS_RAW(result, rb_cArray);
4487     }
4488     ARY_SET_LEN(result, n);
4489 
4490     return result;
4491 }
4492 
4493 static VALUE
4494 rb_ary_cycle_size(VALUE self, VALUE args, VALUE eobj)
4495 {
4496     long mul;
4497     VALUE n = Qnil;
4498     if (args && (RARRAY_LEN(args) > 0)) {
4499         n = RARRAY_AREF(args, 0);
4500     }
4501     if (RARRAY_LEN(self) == 0) return INT2FIX(0);
4502     if (n == Qnil) return DBL2NUM(INFINITY);
4503     mul = NUM2LONG(n);
4504     if (mul <= 0) return INT2FIX(0);
4505     return rb_funcall(rb_ary_length(self), '*', 1, LONG2FIX(mul));
4506 }
4507 
4508 /*
4509  *  call-seq:
4510  *     ary.cycle(n=nil) { |obj| block }  -> nil
4511  *     ary.cycle(n=nil)                  -> Enumerator
4512  *
4513  *  Calls the given block for each element +n+ times or forever if +nil+ is
4514  *  given.
4515  *
4516  *  Does nothing if a non-positive number is given or the array is empty.
4517  *
4518  *  Returns +nil+ if the loop has finished without getting interrupted.
4519  *
4520  *  If no block is given, an Enumerator is returned instead.
4521  *
4522  *     a = ["a", "b", "c"]
4523  *     a.cycle { |x| puts x }     # print, a, b, c, a, b, c,.. forever.
4524  *     a.cycle(2) { |x| puts x }  # print, a, b, c, a, b, c.
4525  *
4526  */
4527 
4528 static VALUE
4529 rb_ary_cycle(int argc, VALUE *argv, VALUE ary)
4530 {
4531     long n, i;
4532     VALUE nv = Qnil;
4533 
4534     rb_scan_args(argc, argv, "01", &nv);
4535 
4536     RETURN_SIZED_ENUMERATOR(ary, argc, argv, rb_ary_cycle_size);
4537     if (NIL_P(nv)) {
4538         n = -1;
4539     }
4540     else {
4541         n = NUM2LONG(nv);
4542         if (n <= 0) return Qnil;
4543     }
4544 
4545     while (RARRAY_LEN(ary) > 0 && (n < 0 || 0 < n--)) {
4546         for (i=0; i<RARRAY_LEN(ary); i++) {
4547             rb_yield(RARRAY_AREF(ary, i));
4548         }
4549     }
4550     return Qnil;
4551 }
4552 
4553 #define tmpbuf(n, size) rb_str_tmp_new((n)*(size))
4554 #define tmpbuf_discard(s) (rb_str_resize((s), 0L), RBASIC_SET_CLASS_RAW(s, rb_cString))
4555 #define tmpary(n) rb_ary_tmp_new(n)
4556 #define tmpary_discard(a) (ary_discard(a), RBASIC_SET_CLASS_RAW(a, rb_cArray))
4557 
4558 /*
4559  * Recursively compute permutations of +r+ elements of the set
4560  * <code>[0..n-1]</code>.
4561  *
4562  * When we have a complete permutation of array indexes, copy the values
4563  * at those indexes into a new array and yield that array.
4564  *
4565  * n: the size of the set
4566  * r: the number of elements in each permutation
4567  * p: the array (of size r) that we're filling in
4568  * index: what index we're filling in now
4569  * used: an array of booleans: whether a given index is already used
4570  * values: the Ruby array that holds the actual values to permute
4571  */
4572 static void
4573 permute0(long n, long r, long *p, long index, char *used, VALUE values)
4574 {
4575     long i,j;
4576     for (i = 0; i < n; i++) {
4577         if (used[i] == 0) {
4578             p[index] = i;
4579             if (index < r-1) {             /* if not done yet */
4580                 used[i] = 1;               /* mark index used */
4581                 permute0(n, r, p, index+1, /* recurse */
4582                          used, values);
4583                 used[i] = 0;               /* index unused */
4584             }
4585             else {
4586                 /* We have a complete permutation of array indexes */
4587                 /* Build a ruby array of the corresponding values */
4588                 /* And yield it to the associated block */
4589                 VALUE result = rb_ary_new2(r);
4590                 VALUE *result_array = RARRAY_PTR(result);
4591                 const VALUE *values_array = RARRAY_PTR(values);
4592 
4593                 for (j = 0; j < r; j++) result_array[j] = values_array[p[j]];
4594                 ARY_SET_LEN(result, r);
4595                 rb_yield(result);
4596                 if (RBASIC(values)->klass) {
4597                     rb_raise(rb_eRuntimeError, "permute reentered");
4598                 }
4599             }
4600         }
4601     }
4602 }
4603 
4604 /*
4605  * Returns the product of from, from-1, ..., from - how_many + 1.
4606  * http://en.wikipedia.org/wiki/Pochhammer_symbol
4607  */
4608 static VALUE
4609 descending_factorial(long from, long how_many)
4610 {
4611     VALUE cnt = LONG2FIX(how_many >= 0);
4612     while (how_many-- > 0) {
4613         cnt = rb_funcall(cnt, '*', 1, LONG2FIX(from--));
4614     }
4615     return cnt;
4616 }
4617 
4618 static VALUE
4619 binomial_coefficient(long comb, long size)
4620 {
4621     if (comb > size-comb) {
4622         comb = size-comb;
4623     }
4624     if (comb < 0) {
4625         return LONG2FIX(0);
4626     }
4627     return rb_funcall(descending_factorial(size, comb), id_div, 1, descending_factorial(comb, comb));
4628 }
4629 
4630 static VALUE
4631 rb_ary_permutation_size(VALUE ary, VALUE args, VALUE eobj)
4632 {
4633     long n = RARRAY_LEN(ary);
4634     long k = (args && (RARRAY_LEN(args) > 0)) ? NUM2LONG(RARRAY_AREF(args, 0)) : n;
4635 
4636     return descending_factorial(n, k);
4637 }
4638 
4639 /*
4640  *  call-seq:
4641  *     ary.permutation { |p| block }          -> ary
4642  *     ary.permutation                        -> Enumerator
4643  *     ary.permutation(n) { |p| block }       -> ary
4644  *     ary.permutation(n)                     -> Enumerator
4645  *
4646  * When invoked with a block, yield all permutations of length +n+ of the
4647  * elements of the array, then return the array itself.
4648  *
4649  * If +n+ is not specified, yield all permutations of all elements.
4650  *
4651  * The implementation makes no guarantees about the order in which the
4652  * permutations are yielded.
4653  *
4654  * If no block is given, an Enumerator is returned instead.
4655  *
4656  * Examples:
4657  *
4658  *   a = [1, 2, 3]
4659  *   a.permutation.to_a    #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
4660  *   a.permutation(1).to_a #=> [[1],[2],[3]]
4661  *   a.permutation(2).to_a #=> [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]
4662  *   a.permutation(3).to_a #=> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
4663  *   a.permutation(0).to_a #=> [[]] # one permutation of length 0
4664  *   a.permutation(4).to_a #=> []   # no permutations of length 4
4665  */
4666 
4667 static VALUE
4668 rb_ary_permutation(int argc, VALUE *argv, VALUE ary)
4669 {
4670     VALUE num;
4671     long r, n, i;
4672 
4673     n = RARRAY_LEN(ary);                  /* Array length */
4674     RETURN_SIZED_ENUMERATOR(ary, argc, argv, rb_ary_permutation_size);   /* Return enumerator if no block */
4675     rb_scan_args(argc, argv, "01", &num);
4676     r = NIL_P(num) ? n : NUM2LONG(num);   /* Permutation size from argument */
4677 
4678     if (r < 0 || n < r) {
4679         /* no permutations: yield nothing */
4680     }
4681     else if (r == 0) { /* exactly one permutation: the zero-length array */
4682         rb_yield(rb_ary_new2(0));
4683     }
4684     else if (r == 1) { /* this is a special, easy case */
4685         for (i = 0; i < RARRAY_LEN(ary); i++) {
4686             rb_yield(rb_ary_new3(1, RARRAY_AREF(ary, i)));
4687         }
4688     }
4689     else {             /* this is the general case */
4690         volatile VALUE t0 = tmpbuf(n,sizeof(long));
4691         long *p = (long*)RSTRING_PTR(t0);
4692         volatile VALUE t1 = tmpbuf(n,sizeof(char));
4693         char *used = (char*)RSTRING_PTR(t1);
4694         VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
4695         RBASIC_CLEAR_CLASS(ary0);
4696 
4697         MEMZERO(used, char, n); /* initialize array */
4698 
4699         permute0(n, r, p, 0, used, ary0); /* compute and yield permutations */
4700         tmpbuf_discard(t0);
4701         tmpbuf_discard(t1);
4702         RBASIC_SET_CLASS_RAW(ary0, rb_cArray);
4703     }
4704     return ary;
4705 }
4706 
4707 static VALUE
4708 rb_ary_combination_size(VALUE ary, VALUE args, VALUE eobj)
4709 {
4710     long n = RARRAY_LEN(ary);
4711     long k = NUM2LONG(RARRAY_AREF(args, 0));
4712 
4713     return binomial_coefficient(k, n);
4714 }
4715 
4716 /*
4717  *  call-seq:
4718  *     ary.combination(n) { |c| block }    -> ary
4719  *     ary.combination(n)                  -> Enumerator
4720  *
4721  * When invoked with a block, yields all combinations of length +n+ of elements
4722  * from the array and then returns the array itself.
4723  *
4724  * The implementation makes no guarantees about the order in which the
4725  * combinations are yielded.
4726  *
4727  * If no block is given, an Enumerator is returned instead.
4728  *
4729  * Examples:
4730  *
4731  *     a = [1, 2, 3, 4]
4732  *     a.combination(1).to_a  #=> [[1],[2],[3],[4]]
4733  *     a.combination(2).to_a  #=> [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
4734  *     a.combination(3).to_a  #=> [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
4735  *     a.combination(4).to_a  #=> [[1,2,3,4]]
4736  *     a.combination(0).to_a  #=> [[]] # one combination of length 0
4737  *     a.combination(5).to_a  #=> []   # no combinations of length 5
4738  *
4739  */
4740 
4741 static VALUE
4742 rb_ary_combination(VALUE ary, VALUE num)
4743 {
4744     long n, i, len;
4745 
4746     n = NUM2LONG(num);
4747     RETURN_SIZED_ENUMERATOR(ary, 1, &num, rb_ary_combination_size);
4748     len = RARRAY_LEN(ary);
4749     if (n < 0 || len < n) {
4750         /* yield nothing */
4751     }
4752     else if (n == 0) {
4753         rb_yield(rb_ary_new2(0));
4754     }
4755     else if (n == 1) {
4756         for (i = 0; i < len; i++) {
4757             rb_yield(rb_ary_new3(1, RARRAY_AREF(ary, i)));
4758         }
4759     }
4760     else {
4761         volatile VALUE t0 = tmpbuf(n+1, sizeof(long));
4762         long *stack = (long*)RSTRING_PTR(t0);
4763         volatile VALUE cc = tmpary(n);
4764         VALUE *chosen = RARRAY_PTR(cc);
4765         long lev = 0;
4766 
4767         MEMZERO(stack, long, n);
4768         stack[0] = -1;
4769         for (;;) {
4770             chosen[lev] = RARRAY_AREF(ary, stack[lev+1]);
4771             for (lev++; lev < n; lev++) {
4772                 chosen[lev] = RARRAY_AREF(ary, stack[lev+1] = stack[lev]+1);
4773             }
4774             rb_yield(rb_ary_new4(n, chosen));
4775             if (RBASIC(t0)->klass) {
4776                 rb_raise(rb_eRuntimeError, "combination reentered");
4777             }
4778             do {
4779                 if (lev == 0) goto done;
4780                 stack[lev--]++;
4781             } while (stack[lev+1]+n == len+lev+1);
4782         }
4783     done:
4784         tmpbuf_discard(t0);
4785         tmpary_discard(cc);
4786     }
4787     return ary;
4788 }
4789 
4790 /*
4791  * Recursively compute repeated permutations of +r+ elements of the set
4792  * <code>[0..n-1]</code>.
4793  *
4794  * When we have a complete repeated permutation of array indexes, copy the
4795  * values at those indexes into a new array and yield that array.
4796  *
4797  * n: the size of the set
4798  * r: the number of elements in each permutation
4799  * p: the array (of size r) that we're filling in
4800  * index: what index we're filling in now
4801  * values: the Ruby array that holds the actual values to permute
4802  */
4803 static void
4804 rpermute0(long n, long r, long *p, long index, VALUE values)
4805 {
4806     long i, j;
4807     for (i = 0; i < n; i++) {
4808         p[index] = i;
4809         if (index < r-1) {              /* if not done yet */
4810             rpermute0(n, r, p, index+1, values); /* recurse */
4811         }
4812         else {
4813             /* We have a complete permutation of array indexes */
4814             /* Build a ruby array of the corresponding values */
4815             /* And yield it to the associated block */
4816             VALUE result = rb_ary_new2(r);
4817             VALUE *result_array = RARRAY_PTR(result);
4818             const VALUE *values_array = RARRAY_PTR(values);
4819 
4820             for (j = 0; j < r; j++) result_array[j] = values_array[p[j]];
4821             ARY_SET_LEN(result, r);
4822             rb_yield(result);
4823             if (RBASIC(values)->klass) {
4824                 rb_raise(rb_eRuntimeError, "repeated permute reentered");
4825             }
4826         }
4827     }
4828 }
4829 
4830 static VALUE
4831 rb_ary_repeated_permutation_size(VALUE ary, VALUE args, VALUE eobj)
4832 {
4833     long n = RARRAY_LEN(ary);
4834     long k = NUM2LONG(RARRAY_AREF(args, 0));
4835 
4836     if (k < 0) {
4837         return LONG2FIX(0);
4838     }
4839 
4840     return rb_funcall(LONG2NUM(n), id_power, 1, LONG2NUM(k));
4841 }
4842 
4843 /*
4844  *  call-seq:
4845  *     ary.repeated_permutation(n) { |p| block } -> ary
4846  *     ary.repeated_permutation(n)               -> Enumerator
4847  *
4848  * When invoked with a block, yield all repeated permutations of length +n+ of
4849  * the elements of the array, then return the array itself.
4850  *
4851  * The implementation makes no guarantees about the order in which the repeated
4852  * permutations are yielded.
4853  *
4854  * If no block is given, an Enumerator is returned instead.
4855  *
4856  * Examples:
4857  *
4858  *     a = [1, 2]
4859  *     a.repeated_permutation(1).to_a  #=> [[1], [2]]
4860  *     a.repeated_permutation(2).to_a  #=> [[1,1],[1,2],[2,1],[2,2]]
4861  *     a.repeated_permutation(3).to_a  #=> [[1,1,1],[1,1,2],[1,2,1],[1,2,2],
4862  *                                     #    [2,1,1],[2,1,2],[2,2,1],[2,2,2]]
4863  *     a.repeated_permutation(0).to_a  #=> [[]] # one permutation of length 0
4864  */
4865 
4866 static VALUE
4867 rb_ary_repeated_permutation(VALUE ary, VALUE num)
4868 {
4869     long r, n, i;
4870 
4871     n = RARRAY_LEN(ary);                  /* Array length */
4872     RETURN_SIZED_ENUMERATOR(ary, 1, &num, rb_ary_repeated_permutation_size);      /* Return Enumerator if no block */
4873     r = NUM2LONG(num);                    /* Permutation size from argument */
4874 
4875     if (r < 0) {
4876         /* no permutations: yield nothing */
4877     }
4878     else if (r == 0) { /* exactly one permutation: the zero-length array */
4879         rb_yield(rb_ary_new2(0));
4880     }
4881     else if (r == 1) { /* this is a special, easy case */
4882         for (i = 0; i < RARRAY_LEN(ary); i++) {
4883             rb_yield(rb_ary_new3(1, RARRAY_AREF(ary, i)));
4884         }
4885     }
4886     else {             /* this is the general case */
4887         volatile VALUE t0 = tmpbuf(r, sizeof(long));
4888         long *p = (long*)RSTRING_PTR(t0);
4889         VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
4890         RBASIC_CLEAR_CLASS(ary0);
4891 
4892         rpermute0(n, r, p, 0, ary0); /* compute and yield repeated permutations */
4893         tmpbuf_discard(t0);
4894         RBASIC_SET_CLASS_RAW(ary0, rb_cArray);
4895     }
4896     return ary;
4897 }
4898 
4899 static void
4900 rcombinate0(long n, long r, long *p, long index, long rest, VALUE values)
4901 {
4902     long j;
4903     if (rest > 0) {
4904         for (; index < n; ++index) {
4905             p[r-rest] = index;
4906             rcombinate0(n, r, p, index, rest-1, values);
4907         }
4908     }
4909     else {
4910         VALUE result = rb_ary_new2(r);
4911         VALUE *result_array = RARRAY_PTR(result);
4912         const VALUE *values_array = RARRAY_PTR(values);
4913 
4914         for (j = 0; j < r; ++j) result_array[j] = values_array[p[j]];
4915         ARY_SET_LEN(result, r);
4916         rb_yield(result);
4917         if (RBASIC(values)->klass) {
4918             rb_raise(rb_eRuntimeError, "repeated combination reentered");
4919         }
4920     }
4921 }
4922 
4923 static VALUE
4924 rb_ary_repeated_combination_size(VALUE ary, VALUE args, VALUE eobj)
4925 {
4926     long n = RARRAY_LEN(ary);
4927     long k = NUM2LONG(RARRAY_AREF(args, 0));
4928     if (k == 0) {
4929         return LONG2FIX(1);
4930     }
4931     return binomial_coefficient(k, n + k - 1);
4932 }
4933 
4934 /*
4935  *  call-seq:
4936  *     ary.repeated_combination(n) { |c| block } -> ary
4937  *     ary.repeated_combination(n)               -> Enumerator
4938  *
4939  * When invoked with a block, yields all repeated combinations of length +n+ of
4940  * elements from the array and then returns the array itself.
4941  *
4942  * The implementation makes no guarantees about the order in which the repeated
4943  * combinations are yielded.
4944  *
4945  * If no block is given, an Enumerator is returned instead.
4946  *
4947  * Examples:
4948  *
4949  *   a = [1, 2, 3]
4950  *   a.repeated_combination(1).to_a  #=> [[1], [2], [3]]
4951  *   a.repeated_combination(2).to_a  #=> [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
4952  *   a.repeated_combination(3).to_a  #=> [[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],
4953  *                                   #    [1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]]
4954  *   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],
4955  *                                   #    [1,1,3,3],[1,2,2,2],[1,2,2,3],[1,2,3,3],[1,3,3,3],
4956  *                                   #    [2,2,2,2],[2,2,2,3],[2,2,3,3],[2,3,3,3],[3,3,3,3]]
4957  *   a.repeated_combination(0).to_a  #=> [[]] # one combination of length 0
4958  *
4959  */
4960 
4961 static VALUE
4962 rb_ary_repeated_combination(VALUE ary, VALUE num)
4963 {
4964     long n, i, len;
4965 
4966     n = NUM2LONG(num);                 /* Combination size from argument */
4967     RETURN_SIZED_ENUMERATOR(ary, 1, &num, rb_ary_repeated_combination_size);   /* Return enumerator if no block */
4968     len = RARRAY_LEN(ary);
4969     if (n < 0) {
4970         /* yield nothing */
4971     }
4972     else if (n == 0) {
4973         rb_yield(rb_ary_new2(0));
4974     }
4975     else if (n == 1) {
4976         for (i = 0; i < len; i++) {
4977             rb_yield(rb_ary_new3(1, RARRAY_AREF(ary, i)));
4978         }
4979     }
4980     else if (len == 0) {
4981         /* yield nothing */
4982     }
4983     else {
4984         volatile VALUE t0 = tmpbuf(n, sizeof(long));
4985         long *p = (long*)RSTRING_PTR(t0);
4986         VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */
4987         RBASIC_CLEAR_CLASS(ary0);
4988 
4989         rcombinate0(len, n, p, 0, n, ary0); /* compute and yield repeated combinations */
4990         tmpbuf_discard(t0);
4991         RBASIC_SET_CLASS_RAW(ary0, rb_cArray);
4992     }
4993     return ary;
4994 }
4995 
4996 /*
4997  *  call-seq:
4998  *     ary.product(other_ary, ...)                -> new_ary
4999  *     ary.product(other_ary, ...) { |p| block }  -> ary
5000  *
5001  *  Returns an array of all combinations of elements from all arrays.
5002  *
5003  *  The length of the returned array is the product of the length of +self+ and
5004  *  the argument arrays.
5005  *
5006  *  If given a block, #product will yield all combinations and return +self+
5007  *  instead.
5008  *
5009  *     [1,2,3].product([4,5])     #=> [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]
5010  *     [1,2].product([1,2])       #=> [[1,1],[1,2],[2,1],[2,2]]
5011  *     [1,2].product([3,4],[5,6]) #=> [[1,3,5],[1,3,6],[1,4,5],[1,4,6],
5012  *                                #     [2,3,5],[2,3,6],[2,4,5],[2,4,6]]
5013  *     [1,2].product()            #=> [[1],[2]]
5014  *     [1,2].product([])          #=> []
5015  */
5016 
5017 static VALUE
5018 rb_ary_product(int argc, VALUE *argv, VALUE ary)
5019 {
5020     int n = argc+1;    /* How many arrays we're operating on */
5021     volatile VALUE t0 = tmpary(n);
5022     volatile VALUE t1 = tmpbuf(n, sizeof(int));
5023     VALUE *arrays = RARRAY_PTR(t0); /* The arrays we're computing the product of */
5024     int *counters = (int*)RSTRING_PTR(t1); /* The current position in each one */
5025     VALUE result = Qnil;      /* The array we'll be returning, when no block given */
5026     long i,j;
5027     long resultlen = 1;
5028 
5029     RBASIC_CLEAR_CLASS(t0);
5030     RBASIC_CLEAR_CLASS(t1);
5031 
5032     /* initialize the arrays of arrays */
5033     ARY_SET_LEN(t0, n);
5034     arrays[0] = ary;
5035     for (i = 1; i < n; i++) arrays[i] = Qnil;
5036     for (i = 1; i < n; i++) arrays[i] = to_ary(argv[i-1]);
5037 
5038     /* initialize the counters for the arrays */
5039     for (i = 0; i < n; i++) counters[i] = 0;
5040 
5041     /* Otherwise, allocate and fill in an array of results */
5042     if (rb_block_given_p()) {
5043         /* Make defensive copies of arrays; exit if any is empty */
5044         for (i = 0; i < n; i++) {
5045             if (RARRAY_LEN(arrays[i]) == 0) goto done;
5046             arrays[i] = ary_make_shared_copy(arrays[i]);
5047         }
5048     }
5049     else {
5050         /* Compute the length of the result array; return [] if any is empty */
5051         for (i = 0; i < n; i++) {
5052             long k = RARRAY_LEN(arrays[i]);
5053             if (k == 0) {
5054                 result = rb_ary_new2(0);
5055                 goto done;
5056             }
5057             if (MUL_OVERFLOW_LONG_P(resultlen, k))
5058                 rb_raise(rb_eRangeError, "too big to product");
5059             resultlen *= k;
5060         }
5061         result = rb_ary_new2(resultlen);
5062     }
5063     for (;;) {
5064         int m;
5065         /* fill in one subarray */
5066         VALUE subarray = rb_ary_new2(n);
5067         for (j = 0; j < n; j++) {
5068             rb_ary_push(subarray, rb_ary_entry(arrays[j], counters[j]));
5069         }
5070 
5071         /* put it on the result array */
5072         if (NIL_P(result)) {
5073             FL_SET(t0, FL_USER5);
5074             rb_yield(subarray);
5075             if (! FL_TEST(t0, FL_USER5)) {
5076                 rb_raise(rb_eRuntimeError, "product reentered");
5077             }
5078             else {
5079                 FL_UNSET(t0, FL_USER5);
5080             }
5081         }
5082         else {
5083             rb_ary_push(result, subarray);
5084         }
5085 
5086         /*
5087          * Increment the last counter.  If it overflows, reset to 0
5088          * and increment the one before it.
5089          */
5090         m = n-1;
5091         counters[m]++;
5092         while (counters[m] == RARRAY_LEN(arrays[m])) {
5093             counters[m] = 0;
5094             /* If the first counter overflows, we are done */
5095             if (--m < 0) goto done;
5096             counters[m]++;
5097         }
5098     }
5099 done:
5100     tmpary_discard(t0);
5101     tmpbuf_discard(t1);
5102 
5103     return NIL_P(result) ? ary : result;
5104 }
5105 
5106 /*
5107  *  call-seq:
5108  *     ary.take(n)               -> new_ary
5109  *
5110  *  Returns first +n+ elements from the array.
5111  *
5112  *  If a negative number is given, raises an ArgumentError.
5113  *
5114  *  See also Array#drop
5115  *
5116  *     a = [1, 2, 3, 4, 5, 0]
5117  *     a.take(3)             #=> [1, 2, 3]
5118  *
5119  */
5120 
5121 static VALUE
5122 rb_ary_take(VALUE obj, VALUE n)
5123 {
5124     long len = NUM2LONG(n);
5125     if (len < 0) {
5126         rb_raise(rb_eArgError, "attempt to take negative size");
5127     }
5128     return rb_ary_subseq(obj, 0, len);
5129 }
5130 
5131 /*
5132  *  call-seq:
5133  *     ary.take_while { |arr| block }  -> new_ary
5134  *     ary.take_while                  -> Enumerator
5135  *
5136  *  Passes elements to the block until the block returns +nil+ or +false+, then
5137  *  stops iterating and returns an array of all prior elements.
5138  *
5139  *  If no block is given, an Enumerator is returned instead.
5140  *
5141  *  See also Array#drop_while
5142  *
5143  *     a = [1, 2, 3, 4, 5, 0]
5144  *     a.take_while { |i| i < 3 }  #=> [1, 2]
5145  *
5146  */
5147 
5148 static VALUE
5149 rb_ary_take_while(VALUE ary)
5150 {
5151     long i;
5152 
5153     RETURN_ENUMERATOR(ary, 0, 0);
5154     for (i = 0; i < RARRAY_LEN(ary); i++) {
5155         if (!RTEST(rb_yield(RARRAY_AREF(ary, i)))) break;
5156     }
5157     return rb_ary_take(ary, LONG2FIX(i));
5158 }
5159 
5160 /*
5161  *  call-seq:
5162  *     ary.drop(n)               -> new_ary
5163  *
5164  *  Drops first +n+ elements from +ary+ and returns the rest of the elements in
5165  *  an array.
5166  *
5167  *  If a negative number is given, raises an ArgumentError.
5168  *
5169  *  See also Array#take
5170  *
5171  *     a = [1, 2, 3, 4, 5, 0]
5172  *     a.drop(3)             #=> [4, 5, 0]
5173  *
5174  */
5175 
5176 static VALUE
5177 rb_ary_drop(VALUE ary, VALUE n)
5178 {
5179     VALUE result;
5180     long pos = NUM2LONG(n);
5181     if (pos < 0) {
5182         rb_raise(rb_eArgError, "attempt to drop negative size");
5183     }
5184 
5185     result = rb_ary_subseq(ary, pos, RARRAY_LEN(ary));
5186     if (result == Qnil) result = rb_ary_new();
5187     return result;
5188 }
5189 
5190 /*
5191  *  call-seq:
5192  *     ary.drop_while { |arr| block }   -> new_ary
5193  *     ary.drop_while                  -> Enumerator
5194  *
5195  *  Drops elements up to, but not including, the first element for which the
5196  *  block returns +nil+ or +false+ and returns an array containing the
5197  *  remaining elements.
5198  *
5199  *  If no block is given, an Enumerator is returned instead.
5200  *
5201  *  See also Array#take_while
5202  *
5203  *     a = [1, 2, 3, 4, 5, 0]
5204  *     a.drop_while {|i| i < 3 }   #=> [3, 4, 5, 0]
5205  *
5206  */
5207 
5208 static VALUE
5209 rb_ary_drop_while(VALUE ary)
5210 {
5211     long i;
5212 
5213     RETURN_ENUMERATOR(ary, 0, 0);
5214     for (i = 0; i < RARRAY_LEN(ary); i++) {
5215         if (!RTEST(rb_yield(RARRAY_AREF(ary, i)))) break;
5216     }
5217     return rb_ary_drop(ary, LONG2FIX(i));
5218 }
5219 
5220 /*
5221  *  Arrays are ordered, integer-indexed collections of any object.
5222  *
5223  *  Array indexing starts at 0, as in C or Java.  A negative index is assumed
5224  *  to be relative to the end of the array---that is, an index of -1 indicates
5225  *  the last element of the array, -2 is the next to last element in the
5226  *  array, and so on.
5227  *
5228  *  == Creating Arrays
5229  *
5230  *  A new array can be created by using the literal constructor
5231  *  <code>[]</code>.  Arrays can contain different types of objects.  For
5232  *  example, the array below contains an Integer, a String and a Float:
5233  *
5234  *     ary = [1, "two", 3.0] #=> [1, "two", 3.0]
5235  *
5236  *  An array can also be created by explicitly calling Array.new with zero, one
5237  *  (the initial size of the Array) or two arguments (the initial size and a
5238  *  default object).
5239  *
5240  *     ary = Array.new    #=> []
5241  *     Array.new(3)       #=> [nil, nil, nil]
5242  *     Array.new(3, true) #=> [true, true, true]
5243  *
5244  *  Note that the second argument populates the array with references to the
5245  *  same object.  Therefore, it is only recommended in cases when you need to
5246  *  instantiate arrays with natively immutable objects such as Symbols,
5247  *  numbers, true or false.
5248  *
5249  *  To create an array with separate objects a block can be passed instead.
5250  *  This method is safe to use with mutable objects such as hashes, strings or
5251  *  other arrays:
5252  *
5253  *     Array.new(4) { Hash.new } #=> [{}, {}, {}, {}]
5254  *
5255  *  This is also a quick way to build up multi-dimensional arrays:
5256  *
5257  *     empty_table = Array.new(3) { Array.new(3) }
5258  *     #=> [[nil, nil, nil], [nil, nil, nil], [nil, nil, nil]]
5259  *
5260  *  An array can also be created by using the Array() method, provided by
5261  *  Kernel, which tries to call #to_ary, then #to_a on its argument.
5262  *
5263  *      Array({:a => "a", :b => "b"}) #=> [[:a, "a"], [:b, "b"]]
5264  *
5265  *  == Example Usage
5266  *
5267  *  In addition to the methods it mixes in through the Enumerable module, the
5268  *  Array class has proprietary methods for accessing, searching and otherwise
5269  *  manipulating arrays.
5270  *
5271  *  Some of the more common ones are illustrated below.
5272  *
5273  *  == Accessing Elements
5274  *
5275  *  Elements in an array can be retrieved using the Array#[] method.  It can
5276  *  take a single integer argument (a numeric index), a pair of arguments
5277  *  (start and length) or a range.
5278  *
5279  *     arr = [1, 2, 3, 4, 5, 6]
5280  *     arr[2]    #=> 3
5281  *     arr[100]  #=> nil
5282  *     arr[-3]   #=> 4
5283  *     arr[2, 3] #=> [3, 4, 5]
5284  *     arr[1..4] #=> [2, 3, 4, 5]
5285  *
5286  *  Another way to access a particular array element is by using the #at method
5287  *
5288  *     arr.at(0) #=> 1
5289  *
5290  *  The #slice method works in an identical manner to Array#[].
5291  *
5292  *  To raise an error for indices outside of the array bounds or else to
5293  *  provide a default value when that happens, you can use #fetch.
5294  *
5295  *     arr = ['a', 'b', 'c', 'd', 'e', 'f']
5296  *     arr.fetch(100) #=> IndexError: index 100 outside of array bounds: -6...6
5297  *     arr.fetch(100, "oops") #=> "oops"
5298  *
5299  *  The special methods #first and #last will return the first and last
5300  *  elements of an array, respectively.
5301  *
5302  *     arr.first #=> 1
5303  *     arr.last  #=> 6
5304  *
5305  *  To return the first +n+ elements of an array, use #take
5306  *
5307  *     arr.take(3) #=> [1, 2, 3]
5308  *
5309  *  #drop does the opposite of #take, by returning the elements after +n+
5310  *  elements have been dropped:
5311  *
5312  *     arr.drop(3) #=> [4, 5, 6]
5313  *
5314  *  == Obtaining Information about an Array
5315  *
5316  *  Arrays keep track of their own length at all times.  To query an array
5317  *  about the number of elements it contains, use #length, #count or #size.
5318  *
5319  *    browsers = ['Chrome', 'Firefox', 'Safari', 'Opera', 'IE']
5320  *    browsers.length #=> 5
5321  *    browsers.count #=> 5
5322  *
5323  *  To check whether an array contains any elements at all
5324  *
5325  *    browsers.empty? #=> false
5326  *
5327  *  To check whether a particular item is included in the array
5328  *
5329  *    browsers.include?('Konqueror') #=> false
5330  *
5331  *  == Adding Items to Arrays
5332  *
5333  *  Items can be added to the end of an array by using either #push or #<<
5334  *
5335  *    arr = [1, 2, 3, 4]
5336  *    arr.push(5) #=> [1, 2, 3, 4, 5]
5337  *    arr << 6    #=> [1, 2, 3, 4, 5, 6]
5338  *
5339  *  #unshift will add a new item to the beginning of an array.
5340  *
5341  *     arr.unshift(0) #=> [0, 1, 2, 3, 4, 5, 6]
5342  *
5343  *  With #insert you can add a new element to an array at any position.
5344  *
5345  *     arr.insert(3, 'apple')  #=> [0, 1, 2, 'apple', 3, 4, 5, 6]
5346  *
5347  *  Using the #insert method, you can also insert multiple values at once:
5348  *
5349  *     arr.insert(3, 'orange', 'pear', 'grapefruit')
5350  *     #=> [0, 1, 2, "orange", "pear", "grapefruit", "apple", 3, 4, 5, 6]
5351  *
5352  *  == Removing Items from an Array
5353  *
5354  *  The method #pop removes the last element in an array and returns it:
5355  *
5356  *     arr =  [1, 2, 3, 4, 5, 6]
5357  *     arr.pop #=> 6
5358  *     arr #=> [1, 2, 3, 4, 5]
5359  *
5360  *  To retrieve and at the same time remove the first item, use #shift:
5361  *
5362  *     arr.shift #=> 1
5363  *     arr #=> [2, 3, 4, 5]
5364  *
5365  *  To delete an element at a particular index:
5366  *
5367  *     arr.delete_at(2) #=> 4
5368  *     arr #=> [2, 3, 5]
5369  *
5370  *  To delete a particular element anywhere in an array, use #delete:
5371  *
5372  *     arr = [1, 2, 2, 3]
5373  *     arr.delete(2) #=> 2
5374  *     arr #=> [1,3]
5375  *
5376  *  A useful method if you need to remove +nil+ values from an array is
5377  *  #compact:
5378  *
5379  *     arr = ['foo', 0, nil, 'bar', 7, 'baz', nil]
5380  *     arr.compact  #=> ['foo', 0, 'bar', 7, 'baz']
5381  *     arr          #=> ['foo', 0, nil, 'bar', 7, 'baz', nil]
5382  *     arr.compact! #=> ['foo', 0, 'bar', 7, 'baz']
5383  *     arr          #=> ['foo', 0, 'bar', 7, 'baz']
5384  *
5385  *  Another common need is to remove duplicate elements from an array.
5386  *
5387  *  It has the non-destructive #uniq, and destructive method #uniq!
5388  *
5389  *     arr = [2, 5, 6, 556, 6, 6, 8, 9, 0, 123, 556]
5390  *     arr.uniq #=> [2, 5, 6, 556, 8, 9, 0, 123]
5391  *
5392  *  == Iterating over Arrays
5393  *
5394  *  Like all classes that include the Enumerable module, Array has an each
5395  *  method, which defines what elements should be iterated over and how.  In
5396  *  case of Array's #each, all elements in the Array instance are yielded to
5397  *  the supplied block in sequence.
5398  *
5399  *  Note that this operation leaves the array unchanged.
5400  *
5401  *     arr = [1, 2, 3, 4, 5]
5402  *     arr.each { |a| print a -= 10, " " }
5403  *     # prints: -9 -8 -7 -6 -5
5404  *     #=> [1, 2, 3, 4, 5]
5405  *
5406  *  Another sometimes useful iterator is #reverse_each which will iterate over
5407  *  the elements in the array in reverse order.
5408  *
5409  *     words = %w[first second third fourth fifth sixth]
5410  *     str = ""
5411  *     words.reverse_each { |word| str += "#{word} " }
5412  *     p str #=> "sixth fifth fourth third second first "
5413  *
5414  *  The #map method can be used to create a new array based on the original
5415  *  array, but with the values modified by the supplied block:
5416  *
5417  *     arr.map { |a| 2*a }   #=> [2, 4, 6, 8, 10]
5418  *     arr                   #=> [1, 2, 3, 4, 5]
5419  *     arr.map! { |a| a**2 } #=> [1, 4, 9, 16, 25]
5420  *     arr                   #=> [1, 4, 9, 16, 25]
5421  *
5422  *  == Selecting Items from an Array
5423  *
5424  *  Elements can be selected from an array according to criteria defined in a
5425  *  block.  The selection can happen in a destructive or a non-destructive
5426  *  manner.  While the destructive operations will modify the array they were
5427  *  called on, the non-destructive methods usually return a new array with the
5428  *  selected elements, but leave the original array unchanged.
5429  *
5430  *  === Non-destructive Selection
5431  *
5432  *     arr = [1, 2, 3, 4, 5, 6]
5433  *     arr.select { |a| a > 3 }     #=> [4, 5, 6]
5434  *     arr.reject { |a| a < 3 }     #=> [3, 4, 5, 6]
5435  *     arr.drop_while { |a| a < 4 } #=> [4, 5, 6]
5436  *     arr                          #=> [1, 2, 3, 4, 5, 6]
5437  *
5438  *  === Destructive Selection
5439  *
5440  *  #select! and #reject! are the corresponding destructive methods to #select
5441  *  and #reject
5442  *
5443  *  Similar to #select vs. #reject, #delete_if and #keep_if have the exact
5444  *  opposite result when supplied with the same block:
5445  *
5446  *     arr.delete_if { |a| a < 4 } #=> [4, 5, 6]
5447  *     arr                         #=> [4, 5, 6]
5448  *
5449  *     arr = [1, 2, 3, 4, 5, 6]
5450  *     arr.keep_if { |a| a < 4 } #=> [1, 2, 3]
5451  *     arr                       #=> [1, 2, 3]
5452  *
5453  */
5454 
5455 void
5456 Init_Array(void)
5457 {
5458 #undef rb_intern
5459 #define rb_intern(str) rb_intern_const(str)
5460 
5461     rb_cArray  = rb_define_class("Array", rb_cObject);
5462     rb_include_module(rb_cArray, rb_mEnumerable);
5463 
5464     rb_define_alloc_func(rb_cArray, empty_ary_alloc);
5465     rb_define_singleton_method(rb_cArray, "[]", rb_ary_s_create, -1);
5466     rb_define_singleton_method(rb_cArray, "try_convert", rb_ary_s_try_convert, 1);
5467     rb_define_method(rb_cArray, "initialize", rb_ary_initialize, -1);
5468     rb_define_method(rb_cArray, "initialize_copy", rb_ary_replace, 1);
5469 
5470     rb_define_method(rb_cArray, "inspect", rb_ary_inspect, 0);
5471     rb_define_alias(rb_cArray,  "to_s", "inspect");
5472     rb_define_method(rb_cArray, "to_a", rb_ary_to_a, 0);
5473     rb_define_method(rb_cArray, "to_ary", rb_ary_to_ary_m, 0);
5474     rb_define_method(rb_cArray, "frozen?",  rb_ary_frozen_p, 0);
5475 
5476     rb_define_method(rb_cArray, "==", rb_ary_equal, 1);
5477     rb_define_method(rb_cArray, "eql?", rb_ary_eql, 1);
5478     rb_define_method(rb_cArray, "hash", rb_ary_hash, 0);
5479 
5480     rb_define_method(rb_cArray, "[]", rb_ary_aref, -1);
5481     rb_define_method(rb_cArray, "[]=", rb_ary_aset, -1);
5482     rb_define_method(rb_cArray, "at", rb_ary_at, 1);
5483     rb_define_method(rb_cArray, "fetch", rb_ary_fetch, -1);
5484     rb_define_method(rb_cArray, "first", rb_ary_first, -1);
5485     rb_define_method(rb_cArray, "last", rb_ary_last, -1);
5486     rb_define_method(rb_cArray, "concat", rb_ary_concat, 1);
5487     rb_define_method(rb_cArray, "<<", rb_ary_push, 1);
5488     rb_define_method(rb_cArray, "push", rb_ary_push_m, -1);
5489     rb_define_method(rb_cArray, "pop", rb_ary_pop_m, -1);
5490     rb_define_method(rb_cArray, "shift", rb_ary_shift_m, -1);
5491     rb_define_method(rb_cArray, "unshift", rb_ary_unshift_m, -1);
5492     rb_define_method(rb_cArray, "insert", rb_ary_insert, -1);
5493     rb_define_method(rb_cArray, "each", rb_ary_each, 0);
5494     rb_define_method(rb_cArray, "each_index", rb_ary_each_index, 0);
5495     rb_define_method(rb_cArray, "reverse_each", rb_ary_reverse_each, 0);
5496     rb_define_method(rb_cArray, "length", rb_ary_length, 0);
5497     rb_define_alias(rb_cArray,  "size", "length");
5498     rb_define_method(rb_cArray, "empty?", rb_ary_empty_p, 0);
5499     rb_define_method(rb_cArray, "find_index", rb_ary_index, -1);
5500     rb_define_method(rb_cArray, "index", rb_ary_index, -1);
5501     rb_define_method(rb_cArray, "rindex", rb_ary_rindex, -1);
5502     rb_define_method(rb_cArray, "join", rb_ary_join_m, -1);
5503     rb_define_method(rb_cArray, "reverse", rb_ary_reverse_m, 0);
5504     rb_define_method(rb_cArray, "reverse!", rb_ary_reverse_bang, 0);
5505     rb_define_method(rb_cArray, "rotate", rb_ary_rotate_m, -1);
5506     rb_define_method(rb_cArray, "rotate!", rb_ary_rotate_bang, -1);
5507     rb_define_method(rb_cArray, "sort", rb_ary_sort, 0);
5508     rb_define_method(rb_cArray, "sort!", rb_ary_sort_bang, 0);
5509     rb_define_method(rb_cArray, "sort_by!", rb_ary_sort_by_bang, 0);
5510     rb_define_method(rb_cArray, "collect", rb_ary_collect, 0);
5511     rb_define_method(rb_cArray, "collect!", rb_ary_collect_bang, 0);
5512     rb_define_method(rb_cArray, "map", rb_ary_collect, 0);
5513     rb_define_method(rb_cArray, "map!", rb_ary_collect_bang, 0);
5514     rb_define_method(rb_cArray, "select", rb_ary_select, 0);
5515     rb_define_method(rb_cArray, "select!", rb_ary_select_bang, 0);
5516     rb_define_method(rb_cArray, "keep_if", rb_ary_keep_if, 0);
5517     rb_define_method(rb_cArray, "values_at", rb_ary_values_at, -1);
5518     rb_define_method(rb_cArray, "delete", rb_ary_delete, 1);
5519     rb_define_method(rb_cArray, "delete_at", rb_ary_delete_at_m, 1);
5520     rb_define_method(rb_cArray, "delete_if", rb_ary_delete_if, 0);
5521     rb_define_method(rb_cArray, "reject", rb_ary_reject, 0);
5522     rb_define_method(rb_cArray, "reject!", rb_ary_reject_bang, 0);
5523     rb_define_method(rb_cArray, "zip", rb_ary_zip, -1);
5524     rb_define_method(rb_cArray, "transpose", rb_ary_transpose, 0);
5525     rb_define_method(rb_cArray, "replace", rb_ary_replace, 1);
5526     rb_define_method(rb_cArray, "clear", rb_ary_clear, 0);
5527     rb_define_method(rb_cArray, "fill", rb_ary_fill, -1);
5528     rb_define_method(rb_cArray, "include?", rb_ary_includes, 1);
5529     rb_define_method(rb_cArray, "<=>", rb_ary_cmp, 1);
5530 
5531     rb_define_method(rb_cArray, "slice", rb_ary_aref, -1);
5532     rb_define_method(rb_cArray, "slice!", rb_ary_slice_bang, -1);
5533 
5534     rb_define_method(rb_cArray, "assoc", rb_ary_assoc, 1);
5535     rb_define_method(rb_cArray, "rassoc", rb_ary_rassoc, 1);
5536 
5537     rb_define_method(rb_cArray, "+", rb_ary_plus, 1);
5538     rb_define_method(rb_cArray, "*", rb_ary_times, 1);
5539 
5540     rb_define_method(rb_cArray, "-", rb_ary_diff, 1);
5541     rb_define_method(rb_cArray, "&", rb_ary_and, 1);
5542     rb_define_method(rb_cArray, "|", rb_ary_or, 1);
5543 
5544     rb_define_method(rb_cArray, "uniq", rb_ary_uniq, 0);
5545     rb_define_method(rb_cArray, "uniq!", rb_ary_uniq_bang, 0);
5546     rb_define_method(rb_cArray, "compact", rb_ary_compact, 0);
5547     rb_define_method(rb_cArray, "compact!", rb_ary_compact_bang, 0);
5548     rb_define_method(rb_cArray, "flatten", rb_ary_flatten, -1);
5549     rb_define_method(rb_cArray, "flatten!", rb_ary_flatten_bang, -1);
5550     rb_define_method(rb_cArray, "count", rb_ary_count, -1);
5551     rb_define_method(rb_cArray, "shuffle!", rb_ary_shuffle_bang, -1);
5552     rb_define_method(rb_cArray, "shuffle", rb_ary_shuffle, -1);
5553     rb_define_method(rb_cArray, "sample", rb_ary_sample, -1);
5554     rb_define_method(rb_cArray, "cycle", rb_ary_cycle, -1);
5555     rb_define_method(rb_cArray, "permutation", rb_ary_permutation, -1);
5556     rb_define_method(rb_cArray, "combination", rb_ary_combination, 1);
5557     rb_define_method(rb_cArray, "repeated_permutation", rb_ary_repeated_permutation, 1);
5558     rb_define_method(rb_cArray, "repeated_combination", rb_ary_repeated_combination, 1);
5559     rb_define_method(rb_cArray, "product", rb_ary_product, -1);
5560 
5561     rb_define_method(rb_cArray, "take", rb_ary_take, 1);
5562     rb_define_method(rb_cArray, "take_while", rb_ary_take_while, 0);
5563     rb_define_method(rb_cArray, "drop", rb_ary_drop, 1);
5564     rb_define_method(rb_cArray, "drop_while", rb_ary_drop_while, 0);
5565     rb_define_method(rb_cArray, "bsearch", rb_ary_bsearch, 0);
5566 
5567     id_cmp = rb_intern("<=>");
5568     sym_random = ID2SYM(rb_intern("random"));
5569     id_div = rb_intern("div");
5570     id_power = rb_intern("**");
5571 }