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