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