1/********************************************************************** 2 3 range.c - 4 5 $Author: nagachika $ 6 created at: Thu Aug 19 17:46:47 JST 1993 7 8 Copyright (C) 1993-2007 Yukihiro Matsumoto 9 10**********************************************************************/ 11 12#include "ruby/ruby.h" 13#include "ruby/encoding.h" 14#include "internal.h" 15#include "id.h" 16 17#ifdef HAVE_FLOAT_H 18#include <float.h> 19#endif 20#include <math.h> 21 22VALUE rb_cRange; 23static ID id_cmp, id_succ, id_beg, id_end, id_excl, id_integer_p, id_div; 24 25#define RANGE_BEG(r) (RSTRUCT(r)->as.ary[0]) 26#define RANGE_END(r) (RSTRUCT(r)->as.ary[1]) 27#define RANGE_EXCL(r) (RSTRUCT(r)->as.ary[2]) 28 29#define EXCL(r) RTEST(RANGE_EXCL(r)) 30#define SET_EXCL(r,v) (RSTRUCT(r)->as.ary[2] = (v) ? Qtrue : Qfalse) 31 32static VALUE 33range_failed(void) 34{ 35 rb_raise(rb_eArgError, "bad value for range"); 36 return Qnil; /* dummy */ 37} 38 39static VALUE 40range_check(VALUE *args) 41{ 42 return rb_funcall(args[0], id_cmp, 1, args[1]); 43} 44 45static void 46range_init(VALUE range, VALUE beg, VALUE end, int exclude_end) 47{ 48 VALUE args[2]; 49 50 args[0] = beg; 51 args[1] = end; 52 53 if (!FIXNUM_P(beg) || !FIXNUM_P(end)) { 54 VALUE v; 55 56 v = rb_rescue(range_check, (VALUE)args, range_failed, 0); 57 if (NIL_P(v)) 58 range_failed(); 59 } 60 61 SET_EXCL(range, exclude_end); 62 RSTRUCT(range)->as.ary[0] = beg; 63 RSTRUCT(range)->as.ary[1] = end; 64} 65 66VALUE 67rb_range_new(VALUE beg, VALUE end, int exclude_end) 68{ 69 VALUE range = rb_obj_alloc(rb_cRange); 70 71 range_init(range, beg, end, exclude_end); 72 return range; 73} 74 75/* 76 * call-seq: 77 * Range.new(begin, end, exclude_end=false) -> rng 78 * 79 * Constructs a range using the given +begin+ and +end+. If the +exclude_end+ 80 * parameter is omitted or is <code>false</code>, the +rng+ will include 81 * the end object; otherwise, it will be excluded. 82 */ 83 84static VALUE 85range_initialize(int argc, VALUE *argv, VALUE range) 86{ 87 VALUE beg, end, flags; 88 89 rb_scan_args(argc, argv, "21", &beg, &end, &flags); 90 /* Ranges are immutable, so that they should be initialized only once. */ 91 if (RANGE_EXCL(range) != Qnil) { 92 rb_name_error(idInitialize, "`initialize' called twice"); 93 } 94 range_init(range, beg, end, RTEST(flags)); 95 return Qnil; 96} 97 98#define range_initialize_copy rb_struct_init_copy /* :nodoc: */ 99 100/* 101 * call-seq: 102 * rng.exclude_end? -> true or false 103 * 104 * Returns <code>true</code> if the range excludes its end value. 105 * 106 * (1..5).exclude_end? #=> false 107 * (1...5).exclude_end? #=> true 108 */ 109 110static VALUE 111range_exclude_end_p(VALUE range) 112{ 113 return EXCL(range) ? Qtrue : Qfalse; 114} 115 116static VALUE 117recursive_equal(VALUE range, VALUE obj, int recur) 118{ 119 if (recur) return Qtrue; /* Subtle! */ 120 if (!rb_equal(RANGE_BEG(range), RANGE_BEG(obj))) 121 return Qfalse; 122 if (!rb_equal(RANGE_END(range), RANGE_END(obj))) 123 return Qfalse; 124 125 if (EXCL(range) != EXCL(obj)) 126 return Qfalse; 127 return Qtrue; 128} 129 130 131/* 132 * call-seq: 133 * rng == obj -> true or false 134 * 135 * Returns <code>true</code> only if +obj+ is a Range, has equivalent 136 * begin and end items (by comparing them with <code>==</code>), and has 137 * the same #exclude_end? setting as the range. 138 * 139 * (0..2) == (0..2) #=> true 140 * (0..2) == Range.new(0,2) #=> true 141 * (0..2) == (0...2) #=> false 142 * 143 */ 144 145static VALUE 146range_eq(VALUE range, VALUE obj) 147{ 148 if (range == obj) 149 return Qtrue; 150 if (!rb_obj_is_kind_of(obj, rb_cRange)) 151 return Qfalse; 152 153 return rb_exec_recursive_paired(recursive_equal, range, obj, obj); 154} 155 156static int 157r_lt(VALUE a, VALUE b) 158{ 159 VALUE r = rb_funcall(a, id_cmp, 1, b); 160 161 if (NIL_P(r)) 162 return (int)Qfalse; 163 if (rb_cmpint(r, a, b) < 0) 164 return (int)Qtrue; 165 return (int)Qfalse; 166} 167 168static int 169r_le(VALUE a, VALUE b) 170{ 171 int c; 172 VALUE r = rb_funcall(a, id_cmp, 1, b); 173 174 if (NIL_P(r)) 175 return (int)Qfalse; 176 c = rb_cmpint(r, a, b); 177 if (c == 0) 178 return (int)INT2FIX(0); 179 if (c < 0) 180 return (int)Qtrue; 181 return (int)Qfalse; 182} 183 184 185static VALUE 186recursive_eql(VALUE range, VALUE obj, int recur) 187{ 188 if (recur) return Qtrue; /* Subtle! */ 189 if (!rb_eql(RANGE_BEG(range), RANGE_BEG(obj))) 190 return Qfalse; 191 if (!rb_eql(RANGE_END(range), RANGE_END(obj))) 192 return Qfalse; 193 194 if (EXCL(range) != EXCL(obj)) 195 return Qfalse; 196 return Qtrue; 197} 198 199/* 200 * call-seq: 201 * rng.eql?(obj) -> true or false 202 * 203 * Returns <code>true</code> only if +obj+ is a Range, has equivalent 204 * begin and end items (by comparing them with <code>eql?</code>), 205 * and has the same #exclude_end? setting as the range. 206 * 207 * (0..2).eql?(0..2) #=> true 208 * (0..2).eql?(Range.new(0,2)) #=> true 209 * (0..2).eql?(0...2) #=> false 210 * 211 */ 212 213static VALUE 214range_eql(VALUE range, VALUE obj) 215{ 216 if (range == obj) 217 return Qtrue; 218 if (!rb_obj_is_kind_of(obj, rb_cRange)) 219 return Qfalse; 220 return rb_exec_recursive_paired(recursive_eql, range, obj, obj); 221} 222 223static VALUE 224recursive_hash(VALUE range, VALUE dummy, int recur) 225{ 226 st_index_t hash = EXCL(range); 227 VALUE v; 228 229 hash = rb_hash_start(hash); 230 if (!recur) { 231 v = rb_hash(RANGE_BEG(range)); 232 hash = rb_hash_uint(hash, NUM2LONG(v)); 233 v = rb_hash(RANGE_END(range)); 234 hash = rb_hash_uint(hash, NUM2LONG(v)); 235 } 236 hash = rb_hash_uint(hash, EXCL(range) << 24); 237 hash = rb_hash_end(hash); 238 239 return LONG2FIX(hash); 240} 241 242/* 243 * call-seq: 244 * rng.hash -> fixnum 245 * 246 * Compute a hash-code for this range. Two ranges with equal 247 * begin and end points (using <code>eql?</code>), and the same 248 * #exclude_end? value will generate the same hash-code. 249 */ 250 251static VALUE 252range_hash(VALUE range) 253{ 254 return rb_exec_recursive_outer(recursive_hash, range, 0); 255} 256 257static void 258range_each_func(VALUE range, VALUE (*func) (VALUE, void *), void *arg) 259{ 260 int c; 261 VALUE b = RANGE_BEG(range); 262 VALUE e = RANGE_END(range); 263 VALUE v = b; 264 265 if (EXCL(range)) { 266 while (r_lt(v, e)) { 267 (*func) (v, arg); 268 v = rb_funcall(v, id_succ, 0, 0); 269 } 270 } 271 else { 272 while ((c = r_le(v, e)) != Qfalse) { 273 (*func) (v, arg); 274 if (c == (int)INT2FIX(0)) 275 break; 276 v = rb_funcall(v, id_succ, 0, 0); 277 } 278 } 279} 280 281static VALUE 282sym_step_i(VALUE i, void *arg) 283{ 284 VALUE *iter = arg; 285 286 if (FIXNUM_P(iter[0])) { 287 iter[0] -= INT2FIX(1) & ~FIXNUM_FLAG; 288 } 289 else { 290 iter[0] = rb_funcall(iter[0], '-', 1, INT2FIX(1)); 291 } 292 if (iter[0] == INT2FIX(0)) { 293 rb_yield(rb_str_intern(i)); 294 iter[0] = iter[1]; 295 } 296 return Qnil; 297} 298 299static VALUE 300step_i(VALUE i, void *arg) 301{ 302 VALUE *iter = arg; 303 304 if (FIXNUM_P(iter[0])) { 305 iter[0] -= INT2FIX(1) & ~FIXNUM_FLAG; 306 } 307 else { 308 iter[0] = rb_funcall(iter[0], '-', 1, INT2FIX(1)); 309 } 310 if (iter[0] == INT2FIX(0)) { 311 rb_yield(i); 312 iter[0] = iter[1]; 313 } 314 return Qnil; 315} 316 317static int 318discrete_object_p(VALUE obj) 319{ 320 if (rb_obj_is_kind_of(obj, rb_cTime)) return FALSE; /* until Time#succ removed */ 321 return rb_respond_to(obj, id_succ); 322} 323 324static VALUE 325range_step_size(VALUE range, VALUE args) 326{ 327 VALUE b = RANGE_BEG(range), e = RANGE_END(range); 328 VALUE step = INT2FIX(1); 329 if (args) { 330 step = RARRAY_PTR(args)[0]; 331 if (!rb_obj_is_kind_of(step, rb_cNumeric)) { 332 step = rb_to_int(step); 333 } 334 } 335 if (rb_funcall(step, '<', 1, INT2FIX(0))) { 336 rb_raise(rb_eArgError, "step can't be negative"); 337 } 338 else if (!rb_funcall(step, '>', 1, INT2FIX(0))) { 339 rb_raise(rb_eArgError, "step can't be 0"); 340 } 341 342 if (rb_obj_is_kind_of(b, rb_cNumeric) && rb_obj_is_kind_of(e, rb_cNumeric)) { 343 return num_interval_step_size(b, e, step, EXCL(range)); 344 } 345 return Qnil; 346} 347 348/* 349 * call-seq: 350 * rng.step(n=1) {| obj | block } -> rng 351 * rng.step(n=1) -> an_enumerator 352 * 353 * Iterates over the range, passing each <code>n</code>th element to the block. 354 * If begin and end are numeric, +n+ is added for each iteration. 355 * Otherwise <code>step</code> invokes <code>succ</code> to iterate through 356 * range elements. 357 * 358 * If no block is given, an enumerator is returned instead. 359 * 360 * range = Xs.new(1)..Xs.new(10) 361 * range.step(2) {|x| puts x} 362 * puts 363 * range.step(3) {|x| puts x} 364 * 365 * <em>produces:</em> 366 * 367 * 1 x 368 * 3 xxx 369 * 5 xxxxx 370 * 7 xxxxxxx 371 * 9 xxxxxxxxx 372 * 373 * 1 x 374 * 4 xxxx 375 * 7 xxxxxxx 376 * 10 xxxxxxxxxx 377 * 378 * See Range for the definition of class Xs. 379 */ 380 381 382static VALUE 383range_step(int argc, VALUE *argv, VALUE range) 384{ 385 VALUE b, e, step, tmp; 386 387 RETURN_SIZED_ENUMERATOR(range, argc, argv, range_step_size); 388 389 b = RANGE_BEG(range); 390 e = RANGE_END(range); 391 if (argc == 0) { 392 step = INT2FIX(1); 393 } 394 else { 395 rb_scan_args(argc, argv, "01", &step); 396 if (!rb_obj_is_kind_of(step, rb_cNumeric)) { 397 step = rb_to_int(step); 398 } 399 if (rb_funcall(step, '<', 1, INT2FIX(0))) { 400 rb_raise(rb_eArgError, "step can't be negative"); 401 } 402 else if (!rb_funcall(step, '>', 1, INT2FIX(0))) { 403 rb_raise(rb_eArgError, "step can't be 0"); 404 } 405 } 406 407 if (FIXNUM_P(b) && FIXNUM_P(e) && FIXNUM_P(step)) { /* fixnums are special */ 408 long end = FIX2LONG(e); 409 long i, unit = FIX2LONG(step); 410 411 if (!EXCL(range)) 412 end += 1; 413 i = FIX2LONG(b); 414 while (i < end) { 415 rb_yield(LONG2NUM(i)); 416 if (i + unit < i) break; 417 i += unit; 418 } 419 420 } 421 else if (SYMBOL_P(b) && SYMBOL_P(e)) { /* symbols are special */ 422 VALUE args[2], iter[2]; 423 424 args[0] = rb_sym_to_s(e); 425 args[1] = EXCL(range) ? Qtrue : Qfalse; 426 iter[0] = INT2FIX(1); 427 iter[1] = step; 428 rb_block_call(rb_sym_to_s(b), rb_intern("upto"), 2, args, sym_step_i, (VALUE)iter); 429 } 430 else if (ruby_float_step(b, e, step, EXCL(range))) { 431 /* done */ 432 } 433 else if (rb_obj_is_kind_of(b, rb_cNumeric) || 434 !NIL_P(rb_check_to_integer(b, "to_int")) || 435 !NIL_P(rb_check_to_integer(e, "to_int"))) { 436 ID op = EXCL(range) ? '<' : idLE; 437 VALUE v = b; 438 int i = 0; 439 440 while (RTEST(rb_funcall(v, op, 1, e))) { 441 rb_yield(v); 442 i++; 443 v = rb_funcall(b, '+', 1, rb_funcall(INT2NUM(i), '*', 1, step)); 444 } 445 } 446 else { 447 tmp = rb_check_string_type(b); 448 449 if (!NIL_P(tmp)) { 450 VALUE args[2], iter[2]; 451 452 b = tmp; 453 args[0] = e; 454 args[1] = EXCL(range) ? Qtrue : Qfalse; 455 iter[0] = INT2FIX(1); 456 iter[1] = step; 457 rb_block_call(b, rb_intern("upto"), 2, args, step_i, (VALUE)iter); 458 } 459 else { 460 VALUE args[2]; 461 462 if (!discrete_object_p(b)) { 463 rb_raise(rb_eTypeError, "can't iterate from %s", 464 rb_obj_classname(b)); 465 } 466 args[0] = INT2FIX(1); 467 args[1] = step; 468 range_each_func(range, step_i, args); 469 } 470 } 471 return range; 472} 473 474#if SIZEOF_DOUBLE == 8 && defined(HAVE_INT64_T) 475union int64_double { 476 int64_t i; 477 double d; 478}; 479 480static VALUE 481int64_as_double_to_num(int64_t i) 482{ 483 union int64_double convert; 484 if (i < 0) { 485 convert.i = -i; 486 return DBL2NUM(-convert.d); 487 } 488 else { 489 convert.i = i; 490 return DBL2NUM(convert.d); 491 } 492} 493 494static int64_t 495double_as_int64(double d) 496{ 497 union int64_double convert; 498 convert.d = fabs(d); 499 return d < 0 ? -convert.i : convert.i; 500} 501#endif 502 503static int 504is_integer_p(VALUE v) 505{ 506 VALUE is_int = rb_check_funcall(v, id_integer_p, 0, 0); 507 return RTEST(is_int) && is_int != Qundef; 508} 509 510/* 511 * call-seq: 512 * rng.bsearch {|obj| block } -> value 513 * 514 * By using binary search, finds a value in range which meets the given 515 * condition in O(log n) where n is the size of the range. 516 * 517 * You can use this method in two use cases: a find-minimum mode and 518 * a find-any mode. In either case, the elements of the range must be 519 * monotone (or sorted) with respect to the block. 520 * 521 * In find-minimum mode (this is a good choice for typical use case), 522 * the block must return true or false, and there must be a value x 523 * so that: 524 * 525 * - the block returns false for any value which is less than x, and 526 * - the block returns true for any value which is greater than or 527 * equal to i. 528 * 529 * If x is within the range, this method returns the value x. 530 * Otherwise, it returns nil. 531 * 532 * ary = [0, 4, 7, 10, 12] 533 * (0...ary.size).bsearch {|i| ary[i] >= 4 } #=> 1 534 * (0...ary.size).bsearch {|i| ary[i] >= 6 } #=> 2 535 * (0...ary.size).bsearch {|i| ary[i] >= 8 } #=> 3 536 * (0...ary.size).bsearch {|i| ary[i] >= 100 } #=> nil 537 * 538 * (0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } #=> 1.0 539 * 540 * In find-any mode (this behaves like libc's bsearch(3)), the block 541 * must return a number, and there must be two values x and y (x <= y) 542 * so that: 543 * 544 * - the block returns a positive number for v if v < x, 545 * - the block returns zero for v if x <= v < y, and 546 * - the block returns a negative number for v if y <= v. 547 * 548 * This method returns any value which is within the intersection of 549 * the given range and x...y (if any). If there is no value that 550 * satisfies the condition, it returns nil. 551 * 552 * ary = [0, 100, 100, 100, 200] 553 * (0..4).bsearch {|i| 100 - ary[i] } #=> 1, 2 or 3 554 * (0..4).bsearch {|i| 300 - ary[i] } #=> nil 555 * (0..4).bsearch {|i| 50 - ary[i] } #=> nil 556 * 557 * You must not mix the two modes at a time; the block must always 558 * return either true/false, or always return a number. It is 559 * undefined which value is actually picked up at each iteration. 560 */ 561 562static VALUE 563range_bsearch(VALUE range) 564{ 565 VALUE beg, end; 566 int smaller, satisfied = 0; 567 568 /* Implementation notes: 569 * Floats are handled by mapping them to 64 bits integers. 570 * Apart from sign issues, floats and their 64 bits integer have the 571 * same order, assuming they are represented as exponent followed 572 * by the mantissa. This is true with or without implicit bit. 573 * 574 * Finding the average of two ints needs to be careful about 575 * potential overflow (since float to long can use 64 bits) 576 * as well as the fact that -1/2 can be 0 or -1 in C89. 577 * 578 * Note that -0.0 is mapped to the same int as 0.0 as we don't want 579 * (-1...0.0).bsearch to yield -0.0. 580 */ 581 582#define BSEARCH_CHECK(val) \ 583 do { \ 584 VALUE v = rb_yield(val); \ 585 if (FIXNUM_P(v)) { \ 586 if (FIX2INT(v) == 0) return val; \ 587 smaller = FIX2INT(v) < 0; \ 588 } \ 589 else if (v == Qtrue) { \ 590 satisfied = 1; \ 591 smaller = 1; \ 592 } \ 593 else if (v == Qfalse || v == Qnil) { \ 594 smaller = 0; \ 595 } \ 596 else if (rb_obj_is_kind_of(v, rb_cNumeric)) { \ 597 int cmp = rb_cmpint(rb_funcall(v, id_cmp, 1, INT2FIX(0)), v, INT2FIX(0)); \ 598 if (!cmp) return val; \ 599 smaller = cmp < 0; \ 600 } \ 601 else { \ 602 rb_raise(rb_eTypeError, "wrong argument type %s" \ 603 " (must be numeric, true, false or nil)", \ 604 rb_obj_classname(v)); \ 605 } \ 606 } while (0) 607 608#define BSEARCH(conv) \ 609 do { \ 610 RETURN_ENUMERATOR(range, 0, 0); \ 611 if (EXCL(range)) high--; \ 612 org_high = high; \ 613 while (low < high) { \ 614 mid = ((high < 0) == (low < 0)) ? low + ((high - low) / 2) \ 615 : (low < -high) ? -((-1 - low - high)/2 + 1) : (low + high) / 2; \ 616 BSEARCH_CHECK(conv(mid)); \ 617 if (smaller) { \ 618 high = mid; \ 619 } \ 620 else { \ 621 low = mid + 1; \ 622 } \ 623 } \ 624 if (low == org_high) { \ 625 BSEARCH_CHECK(conv(low)); \ 626 if (!smaller) return Qnil; \ 627 } \ 628 if (!satisfied) return Qnil; \ 629 return conv(low); \ 630 } while (0) 631 632 633 beg = RANGE_BEG(range); 634 end = RANGE_END(range); 635 636 if (FIXNUM_P(beg) && FIXNUM_P(end)) { 637 long low = FIX2LONG(beg); 638 long high = FIX2LONG(end); 639 long mid, org_high; 640 BSEARCH(INT2FIX); 641 } 642#if SIZEOF_DOUBLE == 8 && defined(HAVE_INT64_T) 643 else if (RB_TYPE_P(beg, T_FLOAT) || RB_TYPE_P(end, T_FLOAT)) { 644 int64_t low = double_as_int64(RFLOAT_VALUE(rb_Float(beg))); 645 int64_t high = double_as_int64(RFLOAT_VALUE(rb_Float(end))); 646 int64_t mid, org_high; 647 BSEARCH(int64_as_double_to_num); 648 } 649#endif 650 else if (is_integer_p(beg) && is_integer_p(end)) { 651 VALUE low = rb_to_int(beg); 652 VALUE high = rb_to_int(end); 653 VALUE mid, org_high; 654 RETURN_ENUMERATOR(range, 0, 0); 655 if (EXCL(range)) high = rb_funcall(high, '-', 1, INT2FIX(1)); 656 org_high = high; 657 658 while (rb_cmpint(rb_funcall(low, id_cmp, 1, high), low, high) < 0) { 659 mid = rb_funcall(rb_funcall(high, '+', 1, low), id_div, 1, INT2FIX(2)); 660 BSEARCH_CHECK(mid); 661 if (smaller) { 662 high = mid; 663 } 664 else { 665 low = rb_funcall(mid, '+', 1, INT2FIX(1)); 666 } 667 } 668 if (rb_equal(low, org_high)) { 669 BSEARCH_CHECK(low); 670 if (!smaller) return Qnil; 671 } 672 if (!satisfied) return Qnil; 673 return low; 674 } 675 else { 676 rb_raise(rb_eTypeError, "can't do binary search for %s", rb_obj_classname(beg)); 677 } 678 return range; 679} 680 681static VALUE 682each_i(VALUE v, void *arg) 683{ 684 rb_yield(v); 685 return Qnil; 686} 687 688static VALUE 689sym_each_i(VALUE v, void *arg) 690{ 691 rb_yield(rb_str_intern(v)); 692 return Qnil; 693} 694 695/* 696 * call-seq: 697 * rng.size -> num 698 * 699 * Returns the number of elements in the range. Both the begin and the end of 700 * the Range must be Numeric, otherwise nil is returned. 701 * 702 * (10..20).size #=> 11 703 * ('a'..'z').size #=> nil 704 * (-Float::INFINITY..Float::INFINITY).size #=> Infinity 705 */ 706 707static VALUE 708range_size(VALUE range) 709{ 710 VALUE b = RANGE_BEG(range), e = RANGE_END(range); 711 if (rb_obj_is_kind_of(b, rb_cNumeric) && rb_obj_is_kind_of(e, rb_cNumeric)) { 712 return num_interval_step_size(b, e, INT2FIX(1), EXCL(range)); 713 } 714 return Qnil; 715} 716 717/* 718 * call-seq: 719 * rng.each {| i | block } -> rng 720 * rng.each -> an_enumerator 721 * 722 * Iterates over the elements of range, passing each in turn to the 723 * block. 724 * 725 * The +each+ method can only be used if the begin object of the range 726 * supports the +succ+ method. A TypeError is raised if the object 727 * does not have +succ+ method defined (like Float). 728 * 729 * If no block is given, an enumerator is returned instead. 730 * 731 * (10..15).each {|n| print n, ' ' } 732 * # prints: 10 11 12 13 14 15 733 * 734 * (2.5..5).each {|n| print n, ' ' } 735 * # raises: TypeError: can't iterate from Float 736 */ 737 738static VALUE 739range_each(VALUE range) 740{ 741 VALUE beg, end; 742 743 RETURN_SIZED_ENUMERATOR(range, 0, 0, range_size); 744 745 beg = RANGE_BEG(range); 746 end = RANGE_END(range); 747 748 if (FIXNUM_P(beg) && FIXNUM_P(end)) { /* fixnums are special */ 749 long lim = FIX2LONG(end); 750 long i; 751 752 if (!EXCL(range)) 753 lim += 1; 754 for (i = FIX2LONG(beg); i < lim; i++) { 755 rb_yield(LONG2FIX(i)); 756 } 757 } 758 else if (SYMBOL_P(beg) && SYMBOL_P(end)) { /* symbols are special */ 759 VALUE args[2]; 760 761 args[0] = rb_sym_to_s(end); 762 args[1] = EXCL(range) ? Qtrue : Qfalse; 763 rb_block_call(rb_sym_to_s(beg), rb_intern("upto"), 2, args, sym_each_i, 0); 764 } 765 else { 766 VALUE tmp = rb_check_string_type(beg); 767 768 if (!NIL_P(tmp)) { 769 VALUE args[2]; 770 771 args[0] = end; 772 args[1] = EXCL(range) ? Qtrue : Qfalse; 773 rb_block_call(tmp, rb_intern("upto"), 2, args, rb_yield, 0); 774 } 775 else { 776 if (!discrete_object_p(beg)) { 777 rb_raise(rb_eTypeError, "can't iterate from %s", 778 rb_obj_classname(beg)); 779 } 780 range_each_func(range, each_i, NULL); 781 } 782 } 783 return range; 784} 785 786/* 787 * call-seq: 788 * rng.begin -> obj 789 * 790 * Returns the object that defines the beginning of the range. 791 * 792 * (1..10).begin #=> 1 793 */ 794 795static VALUE 796range_begin(VALUE range) 797{ 798 return RANGE_BEG(range); 799} 800 801 802/* 803 * call-seq: 804 * rng.end -> obj 805 * 806 * Returns the object that defines the end of the range. 807 * 808 * (1..10).end #=> 10 809 * (1...10).end #=> 10 810 */ 811 812 813static VALUE 814range_end(VALUE range) 815{ 816 return RANGE_END(range); 817} 818 819 820static VALUE 821first_i(VALUE i, VALUE *ary) 822{ 823 long n = NUM2LONG(ary[0]); 824 825 if (n <= 0) { 826 rb_iter_break(); 827 } 828 rb_ary_push(ary[1], i); 829 n--; 830 ary[0] = INT2NUM(n); 831 return Qnil; 832} 833 834/* 835 * call-seq: 836 * rng.first -> obj 837 * rng.first(n) -> an_array 838 * 839 * Returns the first object in the range, or an array of the first +n+ 840 * elements. 841 * 842 * (10..20).first #=> 10 843 * (10..20).first(3) #=> [10, 11, 12] 844 */ 845 846static VALUE 847range_first(int argc, VALUE *argv, VALUE range) 848{ 849 VALUE n, ary[2]; 850 851 if (argc == 0) return RANGE_BEG(range); 852 853 rb_scan_args(argc, argv, "1", &n); 854 ary[0] = n; 855 ary[1] = rb_ary_new2(NUM2LONG(n)); 856 rb_block_call(range, idEach, 0, 0, first_i, (VALUE)ary); 857 858 return ary[1]; 859} 860 861 862/* 863 * call-seq: 864 * rng.last -> obj 865 * rng.last(n) -> an_array 866 * 867 * Returns the last object in the range, 868 * or an array of the last +n+ elements. 869 * 870 * Note that with no arguments +last+ will return the object that defines 871 * the end of the range even if #exclude_end? is +true+. 872 * 873 * (10..20).last #=> 20 874 * (10...20).last #=> 20 875 * (10..20).last(3) #=> [18, 19, 20] 876 * (10...20).last(3) #=> [17, 18, 19] 877 */ 878 879static VALUE 880range_last(int argc, VALUE *argv, VALUE range) 881{ 882 if (argc == 0) return RANGE_END(range); 883 return rb_ary_last(argc, argv, rb_Array(range)); 884} 885 886 887/* 888 * call-seq: 889 * rng.min -> obj 890 * rng.min {| a,b | block } -> obj 891 * 892 * Returns the minimum value in the range. Returns +nil+ if the begin 893 * value of the range is larger than the end value. 894 * 895 * Can be given an optional block to override the default comparison 896 * method <code>a <=> b</code>. 897 * 898 * (10..20).min #=> 10 899 */ 900 901 902static VALUE 903range_min(VALUE range) 904{ 905 if (rb_block_given_p()) { 906 return rb_call_super(0, 0); 907 } 908 else { 909 VALUE b = RANGE_BEG(range); 910 VALUE e = RANGE_END(range); 911 int c = rb_cmpint(rb_funcall(b, id_cmp, 1, e), b, e); 912 913 if (c > 0 || (c == 0 && EXCL(range))) 914 return Qnil; 915 return b; 916 } 917} 918 919/* 920 * call-seq: 921 * rng.max -> obj 922 * rng.max {| a,b | block } -> obj 923 * 924 * Returns the maximum value in the range. Returns +nil+ if the begin 925 * value of the range larger than the end value. 926 * 927 * Can be given an optional block to override the default comparison 928 * method <code>a <=> b</code>. 929 * 930 * (10..20).max #=> 20 931 */ 932 933static VALUE 934range_max(VALUE range) 935{ 936 VALUE e = RANGE_END(range); 937 int nm = FIXNUM_P(e) || rb_obj_is_kind_of(e, rb_cNumeric); 938 939 if (rb_block_given_p() || (EXCL(range) && !nm)) { 940 return rb_call_super(0, 0); 941 } 942 else { 943 VALUE b = RANGE_BEG(range); 944 int c = rb_cmpint(rb_funcall(b, id_cmp, 1, e), b, e); 945 946 if (c > 0) 947 return Qnil; 948 if (EXCL(range)) { 949 if (!FIXNUM_P(e) && !rb_obj_is_kind_of(e, rb_cInteger)) { 950 rb_raise(rb_eTypeError, "cannot exclude non Integer end value"); 951 } 952 if (c == 0) return Qnil; 953 if (!FIXNUM_P(b) && !rb_obj_is_kind_of(b,rb_cInteger)) { 954 rb_raise(rb_eTypeError, "cannot exclude end value with non Integer begin value"); 955 } 956 if (FIXNUM_P(e)) { 957 return LONG2NUM(FIX2LONG(e) - 1); 958 } 959 return rb_funcall(e, '-', 1, INT2FIX(1)); 960 } 961 return e; 962 } 963} 964 965int 966rb_range_values(VALUE range, VALUE *begp, VALUE *endp, int *exclp) 967{ 968 VALUE b, e; 969 int excl; 970 971 if (rb_obj_is_kind_of(range, rb_cRange)) { 972 b = RANGE_BEG(range); 973 e = RANGE_END(range); 974 excl = EXCL(range); 975 } 976 else { 977 if (!rb_respond_to(range, id_beg)) return (int)Qfalse; 978 if (!rb_respond_to(range, id_end)) return (int)Qfalse; 979 b = rb_funcall(range, id_beg, 0); 980 e = rb_funcall(range, id_end, 0); 981 excl = RTEST(rb_funcall(range, rb_intern("exclude_end?"), 0)); 982 } 983 *begp = b; 984 *endp = e; 985 *exclp = excl; 986 return (int)Qtrue; 987} 988 989VALUE 990rb_range_beg_len(VALUE range, long *begp, long *lenp, long len, int err) 991{ 992 long beg, end, origbeg, origend; 993 VALUE b, e; 994 int excl; 995 996 if (!rb_range_values(range, &b, &e, &excl)) 997 return Qfalse; 998 beg = NUM2LONG(b); 999 end = NUM2LONG(e); 1000 origbeg = beg; 1001 origend = end; 1002 if (beg < 0) { 1003 beg += len; 1004 if (beg < 0) 1005 goto out_of_range; 1006 } 1007 if (end < 0) 1008 end += len; 1009 if (!excl) 1010 end++; /* include end point */ 1011 if (err == 0 || err == 2) { 1012 if (beg > len) 1013 goto out_of_range; 1014 if (end > len) 1015 end = len; 1016 } 1017 len = end - beg; 1018 if (len < 0) 1019 len = 0; 1020 1021 *begp = beg; 1022 *lenp = len; 1023 return Qtrue; 1024 1025 out_of_range: 1026 if (err) { 1027 rb_raise(rb_eRangeError, "%ld..%s%ld out of range", 1028 origbeg, excl ? "." : "", origend); 1029 } 1030 return Qnil; 1031} 1032 1033/* 1034 * call-seq: 1035 * rng.to_s -> string 1036 * 1037 * Convert this range object to a printable form (using #to_s to convert the 1038 * begin and end objects). 1039 */ 1040 1041static VALUE 1042range_to_s(VALUE range) 1043{ 1044 VALUE str, str2; 1045 1046 str = rb_obj_as_string(RANGE_BEG(range)); 1047 str2 = rb_obj_as_string(RANGE_END(range)); 1048 str = rb_str_dup(str); 1049 rb_str_cat(str, "...", EXCL(range) ? 3 : 2); 1050 rb_str_append(str, str2); 1051 OBJ_INFECT(str, str2); 1052 1053 return str; 1054} 1055 1056static VALUE 1057inspect_range(VALUE range, VALUE dummy, int recur) 1058{ 1059 VALUE str, str2; 1060 1061 if (recur) { 1062 return rb_str_new2(EXCL(range) ? "(... ... ...)" : "(... .. ...)"); 1063 } 1064 str = rb_inspect(RANGE_BEG(range)); 1065 str2 = rb_inspect(RANGE_END(range)); 1066 str = rb_str_dup(str); 1067 rb_str_cat(str, "...", EXCL(range) ? 3 : 2); 1068 rb_str_append(str, str2); 1069 OBJ_INFECT(str, str2); 1070 1071 return str; 1072} 1073 1074/* 1075 * call-seq: 1076 * rng.inspect -> string 1077 * 1078 * Convert this range object to a printable form (using 1079 * <code>inspect</code> to convert the begin and end 1080 * objects). 1081 */ 1082 1083 1084static VALUE 1085range_inspect(VALUE range) 1086{ 1087 return rb_exec_recursive(inspect_range, range, 0); 1088} 1089 1090/* 1091 * call-seq: 1092 * rng === obj -> true or false 1093 * 1094 * Returns <code>true</code> if +obj+ is an element of the range, 1095 * <code>false</code> otherwise. Conveniently, <code>===</code> is the 1096 * comparison operator used by <code>case</code> statements. 1097 * 1098 * case 79 1099 * when 1..50 then print "low\n" 1100 * when 51..75 then print "medium\n" 1101 * when 76..100 then print "high\n" 1102 * end 1103 * 1104 * <em>produces:</em> 1105 * 1106 * high 1107 */ 1108 1109static VALUE 1110range_eqq(VALUE range, VALUE val) 1111{ 1112 return rb_funcall(range, rb_intern("include?"), 1, val); 1113} 1114 1115 1116/* 1117 * call-seq: 1118 * rng.member?(obj) -> true or false 1119 * rng.include?(obj) -> true or false 1120 * 1121 * Returns <code>true</code> if +obj+ is an element of 1122 * the range, <code>false</code> otherwise. If begin and end are 1123 * numeric, comparison is done according to the magnitude of the values. 1124 * 1125 * ("a".."z").include?("g") #=> true 1126 * ("a".."z").include?("A") #=> false 1127 * ("a".."z").include?("cc") #=> false 1128 */ 1129 1130static VALUE 1131range_include(VALUE range, VALUE val) 1132{ 1133 VALUE beg = RANGE_BEG(range); 1134 VALUE end = RANGE_END(range); 1135 int nv = FIXNUM_P(beg) || FIXNUM_P(end) || 1136 rb_obj_is_kind_of(beg, rb_cNumeric) || 1137 rb_obj_is_kind_of(end, rb_cNumeric); 1138 1139 if (nv || 1140 !NIL_P(rb_check_to_integer(beg, "to_int")) || 1141 !NIL_P(rb_check_to_integer(end, "to_int"))) { 1142 if (r_le(beg, val)) { 1143 if (EXCL(range)) { 1144 if (r_lt(val, end)) 1145 return Qtrue; 1146 } 1147 else { 1148 if (r_le(val, end)) 1149 return Qtrue; 1150 } 1151 } 1152 return Qfalse; 1153 } 1154 else if (RB_TYPE_P(beg, T_STRING) && RB_TYPE_P(end, T_STRING) && 1155 RSTRING_LEN(beg) == 1 && RSTRING_LEN(end) == 1) { 1156 if (NIL_P(val)) return Qfalse; 1157 if (RB_TYPE_P(val, T_STRING)) { 1158 if (RSTRING_LEN(val) == 0 || RSTRING_LEN(val) > 1) 1159 return Qfalse; 1160 else { 1161 char b = RSTRING_PTR(beg)[0]; 1162 char e = RSTRING_PTR(end)[0]; 1163 char v = RSTRING_PTR(val)[0]; 1164 1165 if (ISASCII(b) && ISASCII(e) && ISASCII(v)) { 1166 if (b <= v && v < e) return Qtrue; 1167 if (!EXCL(range) && v == e) return Qtrue; 1168 return Qfalse; 1169 } 1170 } 1171 } 1172 } 1173 /* TODO: ruby_frame->this_func = rb_intern("include?"); */ 1174 return rb_call_super(1, &val); 1175} 1176 1177 1178/* 1179 * call-seq: 1180 * rng.cover?(obj) -> true or false 1181 * 1182 * Returns <code>true</code> if +obj+ is between the begin and end of 1183 * the range. 1184 * 1185 * This tests <code>begin <= obj <= end</code> when #exclude_end? is +false+ 1186 * and <code>begin <= obj < end</code> when #exclude_end? is +true+. 1187 * 1188 * ("a".."z").cover?("c") #=> true 1189 * ("a".."z").cover?("5") #=> false 1190 * ("a".."z").cover?("cc") #=> true 1191 */ 1192 1193static VALUE 1194range_cover(VALUE range, VALUE val) 1195{ 1196 VALUE beg, end; 1197 1198 beg = RANGE_BEG(range); 1199 end = RANGE_END(range); 1200 if (r_le(beg, val)) { 1201 if (EXCL(range)) { 1202 if (r_lt(val, end)) 1203 return Qtrue; 1204 } 1205 else { 1206 if (r_le(val, end)) 1207 return Qtrue; 1208 } 1209 } 1210 return Qfalse; 1211} 1212 1213static VALUE 1214range_dumper(VALUE range) 1215{ 1216 VALUE v; 1217 NEWOBJ_OF(m, struct RObject, rb_cObject, T_OBJECT); 1218 1219 v = (VALUE)m; 1220 1221 rb_ivar_set(v, id_excl, RANGE_EXCL(range)); 1222 rb_ivar_set(v, id_beg, RANGE_BEG(range)); 1223 rb_ivar_set(v, id_end, RANGE_END(range)); 1224 return v; 1225} 1226 1227static VALUE 1228range_loader(VALUE range, VALUE obj) 1229{ 1230 if (!RB_TYPE_P(obj, T_OBJECT) || RBASIC(obj)->klass != rb_cObject) { 1231 rb_raise(rb_eTypeError, "not a dumped range object"); 1232 } 1233 1234 RSTRUCT(range)->as.ary[0] = rb_ivar_get(obj, id_beg); 1235 RSTRUCT(range)->as.ary[1] = rb_ivar_get(obj, id_end); 1236 RSTRUCT(range)->as.ary[2] = rb_ivar_get(obj, id_excl); 1237 return range; 1238} 1239 1240static VALUE 1241range_alloc(VALUE klass) 1242{ 1243 /* rb_struct_alloc_noinit itself should not be used because 1244 * rb_marshal_define_compat uses equality of allocaiton function */ 1245 return rb_struct_alloc_noinit(klass); 1246} 1247 1248/* A <code>Range</code> represents an interval---a set of values with a 1249 * beginning and an end. Ranges may be constructed using the 1250 * <em>s</em><code>..</code><em>e</em> and 1251 * <em>s</em><code>...</code><em>e</em> literals, or with 1252 * Range::new. Ranges constructed using <code>..</code> 1253 * run from the beginning to the end inclusively. Those created using 1254 * <code>...</code> exclude the end value. When used as an iterator, 1255 * ranges return each value in the sequence. 1256 * 1257 * (-1..-5).to_a #=> [] 1258 * (-5..-1).to_a #=> [-5, -4, -3, -2, -1] 1259 * ('a'..'e').to_a #=> ["a", "b", "c", "d", "e"] 1260 * ('a'...'e').to_a #=> ["a", "b", "c", "d"] 1261 * 1262 * == Custom Objects in Ranges 1263 * 1264 * Ranges can be constructed using any objects that can be compared 1265 * using the <code><=></code> operator. 1266 * Methods that treat the range as a sequence (#each and methods inherited 1267 * from Enumerable) expect the begin object to implement a 1268 * <code>succ</code> method to return the next object in sequence. 1269 * The #step and #include? methods require the begin 1270 * object to implement <code>succ</code> or to be numeric. 1271 * 1272 * In the <code>Xs</code> class below both <code><=></code> and 1273 * <code>succ</code> are implemented so <code>Xs</code> can be used 1274 * to construct ranges. Note that the Comparable module is included 1275 * so the <code>==</code> method is defined in terms of <code><=></code>. 1276 * 1277 * class Xs # represent a string of 'x's 1278 * include Comparable 1279 * attr :length 1280 * def initialize(n) 1281 * @length = n 1282 * end 1283 * def succ 1284 * Xs.new(@length + 1) 1285 * end 1286 * def <=>(other) 1287 * @length <=> other.length 1288 * end 1289 * def to_s 1290 * sprintf "%2d #{inspect}", @length 1291 * end 1292 * def inspect 1293 * 'x' * @length 1294 * end 1295 * end 1296 * 1297 * An example of using <code>Xs</code> to construct a range: 1298 * 1299 * r = Xs.new(3)..Xs.new(6) #=> xxx..xxxxxx 1300 * r.to_a #=> [xxx, xxxx, xxxxx, xxxxxx] 1301 * r.member?(Xs.new(5)) #=> true 1302 * 1303 */ 1304 1305void 1306Init_Range(void) 1307{ 1308#undef rb_intern 1309#define rb_intern(str) rb_intern_const(str) 1310 1311 id_cmp = rb_intern("<=>"); 1312 id_succ = rb_intern("succ"); 1313 id_beg = rb_intern("begin"); 1314 id_end = rb_intern("end"); 1315 id_excl = rb_intern("excl"); 1316 id_integer_p = rb_intern("integer?"); 1317 id_div = rb_intern("div"); 1318 1319 rb_cRange = rb_struct_define_without_accessor( 1320 "Range", rb_cObject, range_alloc, 1321 "begin", "end", "excl", NULL); 1322 1323 rb_include_module(rb_cRange, rb_mEnumerable); 1324 rb_marshal_define_compat(rb_cRange, rb_cObject, range_dumper, range_loader); 1325 rb_define_method(rb_cRange, "initialize", range_initialize, -1); 1326 rb_define_method(rb_cRange, "initialize_copy", range_initialize_copy, 1); 1327 rb_define_method(rb_cRange, "==", range_eq, 1); 1328 rb_define_method(rb_cRange, "===", range_eqq, 1); 1329 rb_define_method(rb_cRange, "eql?", range_eql, 1); 1330 rb_define_method(rb_cRange, "hash", range_hash, 0); 1331 rb_define_method(rb_cRange, "each", range_each, 0); 1332 rb_define_method(rb_cRange, "step", range_step, -1); 1333 rb_define_method(rb_cRange, "bsearch", range_bsearch, 0); 1334 rb_define_method(rb_cRange, "begin", range_begin, 0); 1335 rb_define_method(rb_cRange, "end", range_end, 0); 1336 rb_define_method(rb_cRange, "first", range_first, -1); 1337 rb_define_method(rb_cRange, "last", range_last, -1); 1338 rb_define_method(rb_cRange, "min", range_min, 0); 1339 rb_define_method(rb_cRange, "max", range_max, 0); 1340 rb_define_method(rb_cRange, "size", range_size, 0); 1341 rb_define_method(rb_cRange, "to_s", range_to_s, 0); 1342 rb_define_method(rb_cRange, "inspect", range_inspect, 0); 1343 1344 rb_define_method(rb_cRange, "exclude_end?", range_exclude_end_p, 0); 1345 1346 rb_define_method(rb_cRange, "member?", range_include, 1); 1347 rb_define_method(rb_cRange, "include?", range_include, 1); 1348 rb_define_method(rb_cRange, "cover?", range_cover, 1); 1349} 1350