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