Ruby
2.0.0p247(2013-06-27revision41674)
|
00001 /********************************************************************** 00002 00003 range.c - 00004 00005 $Author: nagachika $ 00006 created at: Thu Aug 19 17:46:47 JST 1993 00007 00008 Copyright (C) 1993-2007 Yukihiro Matsumoto 00009 00010 **********************************************************************/ 00011 00012 #include "ruby/ruby.h" 00013 #include "ruby/encoding.h" 00014 #include "internal.h" 00015 #include "id.h" 00016 00017 #ifdef HAVE_FLOAT_H 00018 #include <float.h> 00019 #endif 00020 #include <math.h> 00021 00022 VALUE rb_cRange; 00023 static ID id_cmp, id_succ, id_beg, id_end, id_excl, id_integer_p, id_div; 00024 00025 #define RANGE_BEG(r) (RSTRUCT(r)->as.ary[0]) 00026 #define RANGE_END(r) (RSTRUCT(r)->as.ary[1]) 00027 #define RANGE_EXCL(r) (RSTRUCT(r)->as.ary[2]) 00028 00029 #define EXCL(r) RTEST(RANGE_EXCL(r)) 00030 #define SET_EXCL(r,v) (RSTRUCT(r)->as.ary[2] = (v) ? Qtrue : Qfalse) 00031 00032 static VALUE 00033 range_failed(void) 00034 { 00035 rb_raise(rb_eArgError, "bad value for range"); 00036 return Qnil; /* dummy */ 00037 } 00038 00039 static VALUE 00040 range_check(VALUE *args) 00041 { 00042 return rb_funcall(args[0], id_cmp, 1, args[1]); 00043 } 00044 00045 static void 00046 range_init(VALUE range, VALUE beg, VALUE end, int exclude_end) 00047 { 00048 VALUE args[2]; 00049 00050 args[0] = beg; 00051 args[1] = end; 00052 00053 if (!FIXNUM_P(beg) || !FIXNUM_P(end)) { 00054 VALUE v; 00055 00056 v = rb_rescue(range_check, (VALUE)args, range_failed, 0); 00057 if (NIL_P(v)) 00058 range_failed(); 00059 } 00060 00061 SET_EXCL(range, exclude_end); 00062 RSTRUCT(range)->as.ary[0] = beg; 00063 RSTRUCT(range)->as.ary[1] = end; 00064 } 00065 00066 VALUE 00067 rb_range_new(VALUE beg, VALUE end, int exclude_end) 00068 { 00069 VALUE range = rb_obj_alloc(rb_cRange); 00070 00071 range_init(range, beg, end, exclude_end); 00072 return range; 00073 } 00074 00075 /* 00076 * call-seq: 00077 * Range.new(begin, end, exclude_end=false) -> rng 00078 * 00079 * Constructs a range using the given +begin+ and +end+. If the +exclude_end+ 00080 * parameter is omitted or is <code>false</code>, the +rng+ will include 00081 * the end object; otherwise, it will be excluded. 00082 */ 00083 00084 static VALUE 00085 range_initialize(int argc, VALUE *argv, VALUE range) 00086 { 00087 VALUE beg, end, flags; 00088 00089 rb_scan_args(argc, argv, "21", &beg, &end, &flags); 00090 /* Ranges are immutable, so that they should be initialized only once. */ 00091 if (RANGE_EXCL(range) != Qnil) { 00092 rb_name_error(idInitialize, "`initialize' called twice"); 00093 } 00094 range_init(range, beg, end, RTEST(flags)); 00095 return Qnil; 00096 } 00097 00098 #define range_initialize_copy rb_struct_init_copy /* :nodoc: */ 00099 00100 /* 00101 * call-seq: 00102 * rng.exclude_end? -> true or false 00103 * 00104 * Returns <code>true</code> if the range excludes its end value. 00105 * 00106 * (1..5).exclude_end? #=> false 00107 * (1...5).exclude_end? #=> true 00108 */ 00109 00110 static VALUE 00111 range_exclude_end_p(VALUE range) 00112 { 00113 return EXCL(range) ? Qtrue : Qfalse; 00114 } 00115 00116 static VALUE 00117 recursive_equal(VALUE range, VALUE obj, int recur) 00118 { 00119 if (recur) return Qtrue; /* Subtle! */ 00120 if (!rb_equal(RANGE_BEG(range), RANGE_BEG(obj))) 00121 return Qfalse; 00122 if (!rb_equal(RANGE_END(range), RANGE_END(obj))) 00123 return Qfalse; 00124 00125 if (EXCL(range) != EXCL(obj)) 00126 return Qfalse; 00127 return Qtrue; 00128 } 00129 00130 00131 /* 00132 * call-seq: 00133 * rng == obj -> true or false 00134 * 00135 * Returns <code>true</code> only if +obj+ is a Range, has equivalent 00136 * begin and end items (by comparing them with <code>==</code>), and has 00137 * the same #exclude_end? setting as the range. 00138 * 00139 * (0..2) == (0..2) #=> true 00140 * (0..2) == Range.new(0,2) #=> true 00141 * (0..2) == (0...2) #=> false 00142 * 00143 */ 00144 00145 static VALUE 00146 range_eq(VALUE range, VALUE obj) 00147 { 00148 if (range == obj) 00149 return Qtrue; 00150 if (!rb_obj_is_kind_of(obj, rb_cRange)) 00151 return Qfalse; 00152 00153 return rb_exec_recursive_paired(recursive_equal, range, obj, obj); 00154 } 00155 00156 static int 00157 r_lt(VALUE a, VALUE b) 00158 { 00159 VALUE r = rb_funcall(a, id_cmp, 1, b); 00160 00161 if (NIL_P(r)) 00162 return (int)Qfalse; 00163 if (rb_cmpint(r, a, b) < 0) 00164 return (int)Qtrue; 00165 return (int)Qfalse; 00166 } 00167 00168 static int 00169 r_le(VALUE a, VALUE b) 00170 { 00171 int c; 00172 VALUE r = rb_funcall(a, id_cmp, 1, b); 00173 00174 if (NIL_P(r)) 00175 return (int)Qfalse; 00176 c = rb_cmpint(r, a, b); 00177 if (c == 0) 00178 return (int)INT2FIX(0); 00179 if (c < 0) 00180 return (int)Qtrue; 00181 return (int)Qfalse; 00182 } 00183 00184 00185 static VALUE 00186 recursive_eql(VALUE range, VALUE obj, int recur) 00187 { 00188 if (recur) return Qtrue; /* Subtle! */ 00189 if (!rb_eql(RANGE_BEG(range), RANGE_BEG(obj))) 00190 return Qfalse; 00191 if (!rb_eql(RANGE_END(range), RANGE_END(obj))) 00192 return Qfalse; 00193 00194 if (EXCL(range) != EXCL(obj)) 00195 return Qfalse; 00196 return Qtrue; 00197 } 00198 00199 /* 00200 * call-seq: 00201 * rng.eql?(obj) -> true or false 00202 * 00203 * Returns <code>true</code> only if +obj+ is a Range, has equivalent 00204 * begin and end items (by comparing them with <code>eql?</code>), 00205 * and has the same #exclude_end? setting as the range. 00206 * 00207 * (0..2).eql?(0..2) #=> true 00208 * (0..2).eql?(Range.new(0,2)) #=> true 00209 * (0..2).eql?(0...2) #=> false 00210 * 00211 */ 00212 00213 static VALUE 00214 range_eql(VALUE range, VALUE obj) 00215 { 00216 if (range == obj) 00217 return Qtrue; 00218 if (!rb_obj_is_kind_of(obj, rb_cRange)) 00219 return Qfalse; 00220 return rb_exec_recursive_paired(recursive_eql, range, obj, obj); 00221 } 00222 00223 static VALUE 00224 recursive_hash(VALUE range, VALUE dummy, int recur) 00225 { 00226 st_index_t hash = EXCL(range); 00227 VALUE v; 00228 00229 hash = rb_hash_start(hash); 00230 if (!recur) { 00231 v = rb_hash(RANGE_BEG(range)); 00232 hash = rb_hash_uint(hash, NUM2LONG(v)); 00233 v = rb_hash(RANGE_END(range)); 00234 hash = rb_hash_uint(hash, NUM2LONG(v)); 00235 } 00236 hash = rb_hash_uint(hash, EXCL(range) << 24); 00237 hash = rb_hash_end(hash); 00238 00239 return LONG2FIX(hash); 00240 } 00241 00242 /* 00243 * call-seq: 00244 * rng.hash -> fixnum 00245 * 00246 * Compute a hash-code for this range. Two ranges with equal 00247 * begin and end points (using <code>eql?</code>), and the same 00248 * #exclude_end? value will generate the same hash-code. 00249 */ 00250 00251 static VALUE 00252 range_hash(VALUE range) 00253 { 00254 return rb_exec_recursive_outer(recursive_hash, range, 0); 00255 } 00256 00257 static void 00258 range_each_func(VALUE range, VALUE (*func) (VALUE, void *), void *arg) 00259 { 00260 int c; 00261 VALUE b = RANGE_BEG(range); 00262 VALUE e = RANGE_END(range); 00263 VALUE v = b; 00264 00265 if (EXCL(range)) { 00266 while (r_lt(v, e)) { 00267 (*func) (v, arg); 00268 v = rb_funcall(v, id_succ, 0, 0); 00269 } 00270 } 00271 else { 00272 while ((c = r_le(v, e)) != Qfalse) { 00273 (*func) (v, arg); 00274 if (c == (int)INT2FIX(0)) 00275 break; 00276 v = rb_funcall(v, id_succ, 0, 0); 00277 } 00278 } 00279 } 00280 00281 static VALUE 00282 sym_step_i(VALUE i, void *arg) 00283 { 00284 VALUE *iter = arg; 00285 00286 if (FIXNUM_P(iter[0])) { 00287 iter[0] -= INT2FIX(1) & ~FIXNUM_FLAG; 00288 } 00289 else { 00290 iter[0] = rb_funcall(iter[0], '-', 1, INT2FIX(1)); 00291 } 00292 if (iter[0] == INT2FIX(0)) { 00293 rb_yield(rb_str_intern(i)); 00294 iter[0] = iter[1]; 00295 } 00296 return Qnil; 00297 } 00298 00299 static VALUE 00300 step_i(VALUE i, void *arg) 00301 { 00302 VALUE *iter = arg; 00303 00304 if (FIXNUM_P(iter[0])) { 00305 iter[0] -= INT2FIX(1) & ~FIXNUM_FLAG; 00306 } 00307 else { 00308 iter[0] = rb_funcall(iter[0], '-', 1, INT2FIX(1)); 00309 } 00310 if (iter[0] == INT2FIX(0)) { 00311 rb_yield(i); 00312 iter[0] = iter[1]; 00313 } 00314 return Qnil; 00315 } 00316 00317 static int 00318 discrete_object_p(VALUE obj) 00319 { 00320 if (rb_obj_is_kind_of(obj, rb_cTime)) return FALSE; /* until Time#succ removed */ 00321 return rb_respond_to(obj, id_succ); 00322 } 00323 00324 static VALUE 00325 range_step_size(VALUE range, VALUE args) 00326 { 00327 VALUE b = RANGE_BEG(range), e = RANGE_END(range); 00328 VALUE step = INT2FIX(1); 00329 if (args) { 00330 step = RARRAY_PTR(args)[0]; 00331 if (!rb_obj_is_kind_of(step, rb_cNumeric)) { 00332 step = rb_to_int(step); 00333 } 00334 } 00335 if (rb_funcall(step, '<', 1, INT2FIX(0))) { 00336 rb_raise(rb_eArgError, "step can't be negative"); 00337 } 00338 else if (!rb_funcall(step, '>', 1, INT2FIX(0))) { 00339 rb_raise(rb_eArgError, "step can't be 0"); 00340 } 00341 00342 if (rb_obj_is_kind_of(b, rb_cNumeric) && rb_obj_is_kind_of(e, rb_cNumeric)) { 00343 return num_interval_step_size(b, e, step, EXCL(range)); 00344 } 00345 return Qnil; 00346 } 00347 00348 /* 00349 * call-seq: 00350 * rng.step(n=1) {| obj | block } -> rng 00351 * rng.step(n=1) -> an_enumerator 00352 * 00353 * Iterates over the range, passing each <code>n</code>th element to the block. 00354 * If begin and end are numeric, +n+ is added for each iteration. 00355 * Otherwise <code>step</code> invokes <code>succ</code> to iterate through 00356 * range elements. 00357 * 00358 * If no block is given, an enumerator is returned instead. 00359 * 00360 * range = Xs.new(1)..Xs.new(10) 00361 * range.step(2) {|x| puts x} 00362 * puts 00363 * range.step(3) {|x| puts x} 00364 * 00365 * <em>produces:</em> 00366 * 00367 * 1 x 00368 * 3 xxx 00369 * 5 xxxxx 00370 * 7 xxxxxxx 00371 * 9 xxxxxxxxx 00372 * 00373 * 1 x 00374 * 4 xxxx 00375 * 7 xxxxxxx 00376 * 10 xxxxxxxxxx 00377 * 00378 * See Range for the definition of class Xs. 00379 */ 00380 00381 00382 static VALUE 00383 range_step(int argc, VALUE *argv, VALUE range) 00384 { 00385 VALUE b, e, step, tmp; 00386 00387 RETURN_SIZED_ENUMERATOR(range, argc, argv, range_step_size); 00388 00389 b = RANGE_BEG(range); 00390 e = RANGE_END(range); 00391 if (argc == 0) { 00392 step = INT2FIX(1); 00393 } 00394 else { 00395 rb_scan_args(argc, argv, "01", &step); 00396 if (!rb_obj_is_kind_of(step, rb_cNumeric)) { 00397 step = rb_to_int(step); 00398 } 00399 if (rb_funcall(step, '<', 1, INT2FIX(0))) { 00400 rb_raise(rb_eArgError, "step can't be negative"); 00401 } 00402 else if (!rb_funcall(step, '>', 1, INT2FIX(0))) { 00403 rb_raise(rb_eArgError, "step can't be 0"); 00404 } 00405 } 00406 00407 if (FIXNUM_P(b) && FIXNUM_P(e) && FIXNUM_P(step)) { /* fixnums are special */ 00408 long end = FIX2LONG(e); 00409 long i, unit = FIX2LONG(step); 00410 00411 if (!EXCL(range)) 00412 end += 1; 00413 i = FIX2LONG(b); 00414 while (i < end) { 00415 rb_yield(LONG2NUM(i)); 00416 if (i + unit < i) break; 00417 i += unit; 00418 } 00419 00420 } 00421 else if (SYMBOL_P(b) && SYMBOL_P(e)) { /* symbols are special */ 00422 VALUE args[2], iter[2]; 00423 00424 args[0] = rb_sym_to_s(e); 00425 args[1] = EXCL(range) ? Qtrue : Qfalse; 00426 iter[0] = INT2FIX(1); 00427 iter[1] = step; 00428 rb_block_call(rb_sym_to_s(b), rb_intern("upto"), 2, args, sym_step_i, (VALUE)iter); 00429 } 00430 else if (ruby_float_step(b, e, step, EXCL(range))) { 00431 /* done */ 00432 } 00433 else if (rb_obj_is_kind_of(b, rb_cNumeric) || 00434 !NIL_P(rb_check_to_integer(b, "to_int")) || 00435 !NIL_P(rb_check_to_integer(e, "to_int"))) { 00436 ID op = EXCL(range) ? '<' : idLE; 00437 VALUE v = b; 00438 int i = 0; 00439 00440 while (RTEST(rb_funcall(v, op, 1, e))) { 00441 rb_yield(v); 00442 i++; 00443 v = rb_funcall(b, '+', 1, rb_funcall(INT2NUM(i), '*', 1, step)); 00444 } 00445 } 00446 else { 00447 tmp = rb_check_string_type(b); 00448 00449 if (!NIL_P(tmp)) { 00450 VALUE args[2], iter[2]; 00451 00452 b = tmp; 00453 args[0] = e; 00454 args[1] = EXCL(range) ? Qtrue : Qfalse; 00455 iter[0] = INT2FIX(1); 00456 iter[1] = step; 00457 rb_block_call(b, rb_intern("upto"), 2, args, step_i, (VALUE)iter); 00458 } 00459 else { 00460 VALUE args[2]; 00461 00462 if (!discrete_object_p(b)) { 00463 rb_raise(rb_eTypeError, "can't iterate from %s", 00464 rb_obj_classname(b)); 00465 } 00466 args[0] = INT2FIX(1); 00467 args[1] = step; 00468 range_each_func(range, step_i, args); 00469 } 00470 } 00471 return range; 00472 } 00473 00474 #if SIZEOF_DOUBLE == 8 && defined(HAVE_INT64_T) 00475 union int64_double { 00476 int64_t i; 00477 double d; 00478 }; 00479 00480 static VALUE 00481 int64_as_double_to_num(int64_t i) 00482 { 00483 union int64_double convert; 00484 if (i < 0) { 00485 convert.i = -i; 00486 return DBL2NUM(-convert.d); 00487 } 00488 else { 00489 convert.i = i; 00490 return DBL2NUM(convert.d); 00491 } 00492 } 00493 00494 static int64_t 00495 double_as_int64(double d) 00496 { 00497 union int64_double convert; 00498 convert.d = fabs(d); 00499 return d < 0 ? -convert.i : convert.i; 00500 } 00501 #endif 00502 00503 static int 00504 is_integer_p(VALUE v) 00505 { 00506 VALUE is_int = rb_check_funcall(v, id_integer_p, 0, 0); 00507 return RTEST(is_int) && is_int != Qundef; 00508 } 00509 00510 /* 00511 * call-seq: 00512 * rng.bsearch {|obj| block } -> value 00513 * 00514 * By using binary search, finds a value in range which meets the given 00515 * condition in O(log n) where n is the size of the range. 00516 * 00517 * You can use this method in two use cases: a find-minimum mode and 00518 * a find-any mode. In either case, the elements of the range must be 00519 * monotone (or sorted) with respect to the block. 00520 * 00521 * In find-minimum mode (this is a good choice for typical use case), 00522 * the block must return true or false, and there must be a value x 00523 * so that: 00524 * 00525 * - the block returns false for any value which is less than x, and 00526 * - the block returns true for any value which is greater than or 00527 * equal to i. 00528 * 00529 * If x is within the range, this method returns the value x. 00530 * Otherwise, it returns nil. 00531 * 00532 * ary = [0, 4, 7, 10, 12] 00533 * (0...ary.size).bsearch {|i| ary[i] >= 4 } #=> 1 00534 * (0...ary.size).bsearch {|i| ary[i] >= 6 } #=> 2 00535 * (0...ary.size).bsearch {|i| ary[i] >= 8 } #=> 3 00536 * (0...ary.size).bsearch {|i| ary[i] >= 100 } #=> nil 00537 * 00538 * (0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } #=> 1.0 00539 * 00540 * In find-any mode (this behaves like libc's bsearch(3)), the block 00541 * must return a number, and there must be two values x and y (x <= y) 00542 * so that: 00543 * 00544 * - the block returns a positive number for v if v < x, 00545 * - the block returns zero for v if x <= v < y, and 00546 * - the block returns a negative number for v if y <= v. 00547 * 00548 * This method returns any value which is within the intersection of 00549 * the given range and x...y (if any). If there is no value that 00550 * satisfies the condition, it returns nil. 00551 * 00552 * ary = [0, 100, 100, 100, 200] 00553 * (0..4).bsearch {|i| 100 - ary[i] } #=> 1, 2 or 3 00554 * (0..4).bsearch {|i| 300 - ary[i] } #=> nil 00555 * (0..4).bsearch {|i| 50 - ary[i] } #=> nil 00556 * 00557 * You must not mix the two modes at a time; the block must always 00558 * return either true/false, or always return a number. It is 00559 * undefined which value is actually picked up at each iteration. 00560 */ 00561 00562 static VALUE 00563 range_bsearch(VALUE range) 00564 { 00565 VALUE beg, end; 00566 int smaller, satisfied = 0; 00567 00568 /* Implementation notes: 00569 * Floats are handled by mapping them to 64 bits integers. 00570 * Apart from sign issues, floats and their 64 bits integer have the 00571 * same order, assuming they are represented as exponent followed 00572 * by the mantissa. This is true with or without implicit bit. 00573 * 00574 * Finding the average of two ints needs to be careful about 00575 * potential overflow (since float to long can use 64 bits) 00576 * as well as the fact that -1/2 can be 0 or -1 in C89. 00577 * 00578 * Note that -0.0 is mapped to the same int as 0.0 as we don't want 00579 * (-1...0.0).bsearch to yield -0.0. 00580 */ 00581 00582 #define BSEARCH_CHECK(val) \ 00583 do { \ 00584 VALUE v = rb_yield(val); \ 00585 if (FIXNUM_P(v)) { \ 00586 if (FIX2INT(v) == 0) return val; \ 00587 smaller = FIX2INT(v) < 0; \ 00588 } \ 00589 else if (v == Qtrue) { \ 00590 satisfied = 1; \ 00591 smaller = 1; \ 00592 } \ 00593 else if (v == Qfalse || v == Qnil) { \ 00594 smaller = 0; \ 00595 } \ 00596 else if (rb_obj_is_kind_of(v, rb_cNumeric)) { \ 00597 int cmp = rb_cmpint(rb_funcall(v, id_cmp, 1, INT2FIX(0)), v, INT2FIX(0)); \ 00598 if (!cmp) return val; \ 00599 smaller = cmp < 0; \ 00600 } \ 00601 else { \ 00602 rb_raise(rb_eTypeError, "wrong argument type %s" \ 00603 " (must be numeric, true, false or nil)", \ 00604 rb_obj_classname(v)); \ 00605 } \ 00606 } while (0) 00607 00608 #define BSEARCH(conv) \ 00609 do { \ 00610 RETURN_ENUMERATOR(range, 0, 0); \ 00611 if (EXCL(range)) high--; \ 00612 org_high = high; \ 00613 while (low < high) { \ 00614 mid = ((high < 0) == (low < 0)) ? low + ((high - low) / 2) \ 00615 : (low < -high) ? -((-1 - low - high)/2 + 1) : (low + high) / 2; \ 00616 BSEARCH_CHECK(conv(mid)); \ 00617 if (smaller) { \ 00618 high = mid; \ 00619 } \ 00620 else { \ 00621 low = mid + 1; \ 00622 } \ 00623 } \ 00624 if (low == org_high) { \ 00625 BSEARCH_CHECK(conv(low)); \ 00626 if (!smaller) return Qnil; \ 00627 } \ 00628 if (!satisfied) return Qnil; \ 00629 return conv(low); \ 00630 } while (0) 00631 00632 00633 beg = RANGE_BEG(range); 00634 end = RANGE_END(range); 00635 00636 if (FIXNUM_P(beg) && FIXNUM_P(end)) { 00637 long low = FIX2LONG(beg); 00638 long high = FIX2LONG(end); 00639 long mid, org_high; 00640 BSEARCH(INT2FIX); 00641 } 00642 #if SIZEOF_DOUBLE == 8 && defined(HAVE_INT64_T) 00643 else if (RB_TYPE_P(beg, T_FLOAT) || RB_TYPE_P(end, T_FLOAT)) { 00644 int64_t low = double_as_int64(RFLOAT_VALUE(rb_Float(beg))); 00645 int64_t high = double_as_int64(RFLOAT_VALUE(rb_Float(end))); 00646 int64_t mid, org_high; 00647 BSEARCH(int64_as_double_to_num); 00648 } 00649 #endif 00650 else if (is_integer_p(beg) && is_integer_p(end)) { 00651 VALUE low = rb_to_int(beg); 00652 VALUE high = rb_to_int(end); 00653 VALUE mid, org_high; 00654 RETURN_ENUMERATOR(range, 0, 0); 00655 if (EXCL(range)) high = rb_funcall(high, '-', 1, INT2FIX(1)); 00656 org_high = high; 00657 00658 while (rb_cmpint(rb_funcall(low, id_cmp, 1, high), low, high) < 0) { 00659 mid = rb_funcall(rb_funcall(high, '+', 1, low), id_div, 1, INT2FIX(2)); 00660 BSEARCH_CHECK(mid); 00661 if (smaller) { 00662 high = mid; 00663 } 00664 else { 00665 low = rb_funcall(mid, '+', 1, INT2FIX(1)); 00666 } 00667 } 00668 if (rb_equal(low, org_high)) { 00669 BSEARCH_CHECK(low); 00670 if (!smaller) return Qnil; 00671 } 00672 if (!satisfied) return Qnil; 00673 return low; 00674 } 00675 else { 00676 rb_raise(rb_eTypeError, "can't do binary search for %s", rb_obj_classname(beg)); 00677 } 00678 return range; 00679 } 00680 00681 static VALUE 00682 each_i(VALUE v, void *arg) 00683 { 00684 rb_yield(v); 00685 return Qnil; 00686 } 00687 00688 static VALUE 00689 sym_each_i(VALUE v, void *arg) 00690 { 00691 rb_yield(rb_str_intern(v)); 00692 return Qnil; 00693 } 00694 00695 /* 00696 * call-seq: 00697 * rng.size -> num 00698 * 00699 * Returns the number of elements in the range. 00700 * 00701 * (10..20).size #=> 11 00702 */ 00703 00704 static VALUE 00705 range_size(VALUE range) 00706 { 00707 VALUE b = RANGE_BEG(range), e = RANGE_END(range); 00708 if (rb_obj_is_kind_of(b, rb_cNumeric) && rb_obj_is_kind_of(e, rb_cNumeric)) { 00709 return num_interval_step_size(b, e, INT2FIX(1), EXCL(range)); 00710 } 00711 return Qnil; 00712 } 00713 00714 /* 00715 * call-seq: 00716 * rng.each {| i | block } -> rng 00717 * rng.each -> an_enumerator 00718 * 00719 * Iterates over the elements of range, passing each in turn to the 00720 * block. 00721 * 00722 * The +each+ method can only be used if the begin object of the range 00723 * supports the +succ+ method. A TypeError is raised if the object 00724 * does not have +succ+ method defined (like Float). 00725 * 00726 * If no block is given, an enumerator is returned instead. 00727 * 00728 * (10..15).each {|n| print n, ' ' } 00729 * # prints: 10 11 12 13 14 15 00730 * 00731 * (2.5..5).each {|n| print n, ' ' } 00732 * # raises: TypeError: can't iterate from Float 00733 */ 00734 00735 static VALUE 00736 range_each(VALUE range) 00737 { 00738 VALUE beg, end; 00739 00740 RETURN_SIZED_ENUMERATOR(range, 0, 0, range_size); 00741 00742 beg = RANGE_BEG(range); 00743 end = RANGE_END(range); 00744 00745 if (FIXNUM_P(beg) && FIXNUM_P(end)) { /* fixnums are special */ 00746 long lim = FIX2LONG(end); 00747 long i; 00748 00749 if (!EXCL(range)) 00750 lim += 1; 00751 for (i = FIX2LONG(beg); i < lim; i++) { 00752 rb_yield(LONG2FIX(i)); 00753 } 00754 } 00755 else if (SYMBOL_P(beg) && SYMBOL_P(end)) { /* symbols are special */ 00756 VALUE args[2]; 00757 00758 args[0] = rb_sym_to_s(end); 00759 args[1] = EXCL(range) ? Qtrue : Qfalse; 00760 rb_block_call(rb_sym_to_s(beg), rb_intern("upto"), 2, args, sym_each_i, 0); 00761 } 00762 else { 00763 VALUE tmp = rb_check_string_type(beg); 00764 00765 if (!NIL_P(tmp)) { 00766 VALUE args[2]; 00767 00768 args[0] = end; 00769 args[1] = EXCL(range) ? Qtrue : Qfalse; 00770 rb_block_call(tmp, rb_intern("upto"), 2, args, rb_yield, 0); 00771 } 00772 else { 00773 if (!discrete_object_p(beg)) { 00774 rb_raise(rb_eTypeError, "can't iterate from %s", 00775 rb_obj_classname(beg)); 00776 } 00777 range_each_func(range, each_i, NULL); 00778 } 00779 } 00780 return range; 00781 } 00782 00783 /* 00784 * call-seq: 00785 * rng.begin -> obj 00786 * 00787 * Returns the object that defines the beginning of the range. 00788 * 00789 * (1..10).begin #=> 1 00790 */ 00791 00792 static VALUE 00793 range_begin(VALUE range) 00794 { 00795 return RANGE_BEG(range); 00796 } 00797 00798 00799 /* 00800 * call-seq: 00801 * rng.end -> obj 00802 * 00803 * Returns the object that defines the end of the range. 00804 * 00805 * (1..10).end #=> 10 00806 * (1...10).end #=> 10 00807 */ 00808 00809 00810 static VALUE 00811 range_end(VALUE range) 00812 { 00813 return RANGE_END(range); 00814 } 00815 00816 00817 static VALUE 00818 first_i(VALUE i, VALUE *ary) 00819 { 00820 long n = NUM2LONG(ary[0]); 00821 00822 if (n <= 0) { 00823 rb_iter_break(); 00824 } 00825 rb_ary_push(ary[1], i); 00826 n--; 00827 ary[0] = INT2NUM(n); 00828 return Qnil; 00829 } 00830 00831 /* 00832 * call-seq: 00833 * rng.first -> obj 00834 * rng.first(n) -> an_array 00835 * 00836 * Returns the first object in the range, or an array of the first +n+ 00837 * elements. 00838 * 00839 * (10..20).first #=> 10 00840 * (10..20).first(3) #=> [10, 11, 12] 00841 */ 00842 00843 static VALUE 00844 range_first(int argc, VALUE *argv, VALUE range) 00845 { 00846 VALUE n, ary[2]; 00847 00848 if (argc == 0) return RANGE_BEG(range); 00849 00850 rb_scan_args(argc, argv, "1", &n); 00851 ary[0] = n; 00852 ary[1] = rb_ary_new2(NUM2LONG(n)); 00853 rb_block_call(range, idEach, 0, 0, first_i, (VALUE)ary); 00854 00855 return ary[1]; 00856 } 00857 00858 00859 /* 00860 * call-seq: 00861 * rng.last -> obj 00862 * rng.last(n) -> an_array 00863 * 00864 * Returns the last object in the range, 00865 * or an array of the last +n+ elements. 00866 * 00867 * Note that with no arguments +last+ will return the object that defines 00868 * the end of the range even if #exclude_end? is +true+. 00869 * 00870 * (10..20).last #=> 20 00871 * (10...20).last #=> 20 00872 * (10..20).last(3) #=> [18, 19, 20] 00873 * (10...20).last(3) #=> [17, 18, 19] 00874 */ 00875 00876 static VALUE 00877 range_last(int argc, VALUE *argv, VALUE range) 00878 { 00879 if (argc == 0) return RANGE_END(range); 00880 return rb_ary_last(argc, argv, rb_Array(range)); 00881 } 00882 00883 00884 /* 00885 * call-seq: 00886 * rng.min -> obj 00887 * rng.min {| a,b | block } -> obj 00888 * 00889 * Returns the minimum value in the range. Returns +nil+ if the begin 00890 * value of the range is larger than the end value. 00891 * 00892 * Can be given an optional block to override the default comparison 00893 * method <code>a <=> b</code>. 00894 * 00895 * (10..20).min #=> 10 00896 */ 00897 00898 00899 static VALUE 00900 range_min(VALUE range) 00901 { 00902 if (rb_block_given_p()) { 00903 return rb_call_super(0, 0); 00904 } 00905 else { 00906 VALUE b = RANGE_BEG(range); 00907 VALUE e = RANGE_END(range); 00908 int c = rb_cmpint(rb_funcall(b, id_cmp, 1, e), b, e); 00909 00910 if (c > 0 || (c == 0 && EXCL(range))) 00911 return Qnil; 00912 return b; 00913 } 00914 } 00915 00916 /* 00917 * call-seq: 00918 * rng.max -> obj 00919 * rng.max {| a,b | block } -> obj 00920 * 00921 * Returns the maximum value in the range. Returns +nil+ if the begin 00922 * value of the range larger than the end value. 00923 * 00924 * Can be given an optional block to override the default comparison 00925 * method <code>a <=> b</code>. 00926 * 00927 * (10..20).max #=> 20 00928 */ 00929 00930 static VALUE 00931 range_max(VALUE range) 00932 { 00933 VALUE e = RANGE_END(range); 00934 int nm = FIXNUM_P(e) || rb_obj_is_kind_of(e, rb_cNumeric); 00935 00936 if (rb_block_given_p() || (EXCL(range) && !nm)) { 00937 return rb_call_super(0, 0); 00938 } 00939 else { 00940 VALUE b = RANGE_BEG(range); 00941 int c = rb_cmpint(rb_funcall(b, id_cmp, 1, e), b, e); 00942 00943 if (c > 0) 00944 return Qnil; 00945 if (EXCL(range)) { 00946 if (!FIXNUM_P(e) && !rb_obj_is_kind_of(e, rb_cInteger)) { 00947 rb_raise(rb_eTypeError, "cannot exclude non Integer end value"); 00948 } 00949 if (c == 0) return Qnil; 00950 if (!FIXNUM_P(b) && !rb_obj_is_kind_of(b,rb_cInteger)) { 00951 rb_raise(rb_eTypeError, "cannot exclude end value with non Integer begin value"); 00952 } 00953 if (FIXNUM_P(e)) { 00954 return LONG2NUM(FIX2LONG(e) - 1); 00955 } 00956 return rb_funcall(e, '-', 1, INT2FIX(1)); 00957 } 00958 return e; 00959 } 00960 } 00961 00962 int 00963 rb_range_values(VALUE range, VALUE *begp, VALUE *endp, int *exclp) 00964 { 00965 VALUE b, e; 00966 int excl; 00967 00968 if (rb_obj_is_kind_of(range, rb_cRange)) { 00969 b = RANGE_BEG(range); 00970 e = RANGE_END(range); 00971 excl = EXCL(range); 00972 } 00973 else { 00974 if (!rb_respond_to(range, id_beg)) return (int)Qfalse; 00975 if (!rb_respond_to(range, id_end)) return (int)Qfalse; 00976 b = rb_funcall(range, id_beg, 0); 00977 e = rb_funcall(range, id_end, 0); 00978 excl = RTEST(rb_funcall(range, rb_intern("exclude_end?"), 0)); 00979 } 00980 *begp = b; 00981 *endp = e; 00982 *exclp = excl; 00983 return (int)Qtrue; 00984 } 00985 00986 VALUE 00987 rb_range_beg_len(VALUE range, long *begp, long *lenp, long len, int err) 00988 { 00989 long beg, end, origbeg, origend; 00990 VALUE b, e; 00991 int excl; 00992 00993 if (!rb_range_values(range, &b, &e, &excl)) 00994 return Qfalse; 00995 beg = NUM2LONG(b); 00996 end = NUM2LONG(e); 00997 origbeg = beg; 00998 origend = end; 00999 if (beg < 0) { 01000 beg += len; 01001 if (beg < 0) 01002 goto out_of_range; 01003 } 01004 if (end < 0) 01005 end += len; 01006 if (!excl) 01007 end++; /* include end point */ 01008 if (err == 0 || err == 2) { 01009 if (beg > len) 01010 goto out_of_range; 01011 if (end > len) 01012 end = len; 01013 } 01014 len = end - beg; 01015 if (len < 0) 01016 len = 0; 01017 01018 *begp = beg; 01019 *lenp = len; 01020 return Qtrue; 01021 01022 out_of_range: 01023 if (err) { 01024 rb_raise(rb_eRangeError, "%ld..%s%ld out of range", 01025 origbeg, excl ? "." : "", origend); 01026 } 01027 return Qnil; 01028 } 01029 01030 /* 01031 * call-seq: 01032 * rng.to_s -> string 01033 * 01034 * Convert this range object to a printable form (using #to_s to convert the 01035 * begin and end objects). 01036 */ 01037 01038 static VALUE 01039 range_to_s(VALUE range) 01040 { 01041 VALUE str, str2; 01042 01043 str = rb_obj_as_string(RANGE_BEG(range)); 01044 str2 = rb_obj_as_string(RANGE_END(range)); 01045 str = rb_str_dup(str); 01046 rb_str_cat(str, "...", EXCL(range) ? 3 : 2); 01047 rb_str_append(str, str2); 01048 OBJ_INFECT(str, str2); 01049 01050 return str; 01051 } 01052 01053 static VALUE 01054 inspect_range(VALUE range, VALUE dummy, int recur) 01055 { 01056 VALUE str, str2; 01057 01058 if (recur) { 01059 return rb_str_new2(EXCL(range) ? "(... ... ...)" : "(... .. ...)"); 01060 } 01061 str = rb_inspect(RANGE_BEG(range)); 01062 str2 = rb_inspect(RANGE_END(range)); 01063 str = rb_str_dup(str); 01064 rb_str_cat(str, "...", EXCL(range) ? 3 : 2); 01065 rb_str_append(str, str2); 01066 OBJ_INFECT(str, str2); 01067 01068 return str; 01069 } 01070 01071 /* 01072 * call-seq: 01073 * rng.inspect -> string 01074 * 01075 * Convert this range object to a printable form (using 01076 * <code>inspect</code> to convert the begin and end 01077 * objects). 01078 */ 01079 01080 01081 static VALUE 01082 range_inspect(VALUE range) 01083 { 01084 return rb_exec_recursive(inspect_range, range, 0); 01085 } 01086 01087 /* 01088 * call-seq: 01089 * rng === obj -> true or false 01090 * 01091 * Returns <code>true</code> if +obj+ is an element of the range, 01092 * <code>false</code> otherwise. Conveniently, <code>===</code> is the 01093 * comparison operator used by <code>case</code> statements. 01094 * 01095 * case 79 01096 * when 1..50 then print "low\n" 01097 * when 51..75 then print "medium\n" 01098 * when 76..100 then print "high\n" 01099 * end 01100 * 01101 * <em>produces:</em> 01102 * 01103 * high 01104 */ 01105 01106 static VALUE 01107 range_eqq(VALUE range, VALUE val) 01108 { 01109 return rb_funcall(range, rb_intern("include?"), 1, val); 01110 } 01111 01112 01113 /* 01114 * call-seq: 01115 * rng.member?(obj) -> true or false 01116 * rng.include?(obj) -> true or false 01117 * 01118 * Returns <code>true</code> if +obj+ is an element of 01119 * the range, <code>false</code> otherwise. If begin and end are 01120 * numeric, comparison is done according to the magnitude of the values. 01121 * 01122 * ("a".."z").include?("g") #=> true 01123 * ("a".."z").include?("A") #=> false 01124 * ("a".."z").include?("cc") #=> false 01125 */ 01126 01127 static VALUE 01128 range_include(VALUE range, VALUE val) 01129 { 01130 VALUE beg = RANGE_BEG(range); 01131 VALUE end = RANGE_END(range); 01132 int nv = FIXNUM_P(beg) || FIXNUM_P(end) || 01133 rb_obj_is_kind_of(beg, rb_cNumeric) || 01134 rb_obj_is_kind_of(end, rb_cNumeric); 01135 01136 if (nv || 01137 !NIL_P(rb_check_to_integer(beg, "to_int")) || 01138 !NIL_P(rb_check_to_integer(end, "to_int"))) { 01139 if (r_le(beg, val)) { 01140 if (EXCL(range)) { 01141 if (r_lt(val, end)) 01142 return Qtrue; 01143 } 01144 else { 01145 if (r_le(val, end)) 01146 return Qtrue; 01147 } 01148 } 01149 return Qfalse; 01150 } 01151 else if (RB_TYPE_P(beg, T_STRING) && RB_TYPE_P(end, T_STRING) && 01152 RSTRING_LEN(beg) == 1 && RSTRING_LEN(end) == 1) { 01153 if (NIL_P(val)) return Qfalse; 01154 if (RB_TYPE_P(val, T_STRING)) { 01155 if (RSTRING_LEN(val) == 0 || RSTRING_LEN(val) > 1) 01156 return Qfalse; 01157 else { 01158 char b = RSTRING_PTR(beg)[0]; 01159 char e = RSTRING_PTR(end)[0]; 01160 char v = RSTRING_PTR(val)[0]; 01161 01162 if (ISASCII(b) && ISASCII(e) && ISASCII(v)) { 01163 if (b <= v && v < e) return Qtrue; 01164 if (!EXCL(range) && v == e) return Qtrue; 01165 return Qfalse; 01166 } 01167 } 01168 } 01169 } 01170 /* TODO: ruby_frame->this_func = rb_intern("include?"); */ 01171 return rb_call_super(1, &val); 01172 } 01173 01174 01175 /* 01176 * call-seq: 01177 * rng.cover?(obj) -> true or false 01178 * 01179 * Returns <code>true</code> if +obj+ is between the begin and end of 01180 * the range. 01181 * 01182 * This tests <code>begin <= obj <= end</code> when #exclude_end? is +false+ 01183 * and <code>begin <= obj < end</code> when #exclude_end? is +true+. 01184 * 01185 * ("a".."z").cover?("c") #=> true 01186 * ("a".."z").cover?("5") #=> false 01187 * ("a".."z").cover?("cc") #=> true 01188 */ 01189 01190 static VALUE 01191 range_cover(VALUE range, VALUE val) 01192 { 01193 VALUE beg, end; 01194 01195 beg = RANGE_BEG(range); 01196 end = RANGE_END(range); 01197 if (r_le(beg, val)) { 01198 if (EXCL(range)) { 01199 if (r_lt(val, end)) 01200 return Qtrue; 01201 } 01202 else { 01203 if (r_le(val, end)) 01204 return Qtrue; 01205 } 01206 } 01207 return Qfalse; 01208 } 01209 01210 static VALUE 01211 range_dumper(VALUE range) 01212 { 01213 VALUE v; 01214 NEWOBJ_OF(m, struct RObject, rb_cObject, T_OBJECT); 01215 01216 v = (VALUE)m; 01217 01218 rb_ivar_set(v, id_excl, RANGE_EXCL(range)); 01219 rb_ivar_set(v, id_beg, RANGE_BEG(range)); 01220 rb_ivar_set(v, id_end, RANGE_END(range)); 01221 return v; 01222 } 01223 01224 static VALUE 01225 range_loader(VALUE range, VALUE obj) 01226 { 01227 if (!RB_TYPE_P(obj, T_OBJECT) || RBASIC(obj)->klass != rb_cObject) { 01228 rb_raise(rb_eTypeError, "not a dumped range object"); 01229 } 01230 01231 RSTRUCT(range)->as.ary[0] = rb_ivar_get(obj, id_beg); 01232 RSTRUCT(range)->as.ary[1] = rb_ivar_get(obj, id_end); 01233 RSTRUCT(range)->as.ary[2] = rb_ivar_get(obj, id_excl); 01234 return range; 01235 } 01236 01237 static VALUE 01238 range_alloc(VALUE klass) 01239 { 01240 /* rb_struct_alloc_noinit itself should not be used because 01241 * rb_marshal_define_compat uses equality of allocaiton function */ 01242 return rb_struct_alloc_noinit(klass); 01243 } 01244 01245 /* A <code>Range</code> represents an interval---a set of values with a 01246 * beginning and an end. Ranges may be constructed using the 01247 * <em>s</em><code>..</code><em>e</em> and 01248 * <em>s</em><code>...</code><em>e</em> literals, or with 01249 * Range::new. Ranges constructed using <code>..</code> 01250 * run from the beginning to the end inclusively. Those created using 01251 * <code>...</code> exclude the end value. When used as an iterator, 01252 * ranges return each value in the sequence. 01253 * 01254 * (-1..-5).to_a #=> [] 01255 * (-5..-1).to_a #=> [-5, -4, -3, -2, -1] 01256 * ('a'..'e').to_a #=> ["a", "b", "c", "d", "e"] 01257 * ('a'...'e').to_a #=> ["a", "b", "c", "d"] 01258 * 01259 * == Custom Objects in Ranges 01260 * 01261 * Ranges can be constructed using any objects that can be compared 01262 * using the <code><=></code> operator. 01263 * Methods that treat the range as a sequence (#each and methods inherited 01264 * from Enumerable) expect the begin object to implement a 01265 * <code>succ</code> method to return the next object in sequence. 01266 * The #step and #include? methods require the begin 01267 * object to implement <code>succ</code> or to be numeric. 01268 * 01269 * In the <code>Xs</code> class below both <code><=></code> and 01270 * <code>succ</code> are implemented so <code>Xs</code> can be used 01271 * to construct ranges. Note that the Comparable module is included 01272 * so the <code>==</code> method is defined in terms of <code><=></code>. 01273 * 01274 * class Xs # represent a string of 'x's 01275 * include Comparable 01276 * attr :length 01277 * def initialize(n) 01278 * @length = n 01279 * end 01280 * def succ 01281 * Xs.new(@length + 1) 01282 * end 01283 * def <=>(other) 01284 * @length <=> other.length 01285 * end 01286 * def to_s 01287 * sprintf "%2d #{inspect}", @length 01288 * end 01289 * def inspect 01290 * 'x' * @length 01291 * end 01292 * end 01293 * 01294 * An example of using <code>Xs</code> to construct a range: 01295 * 01296 * r = Xs.new(3)..Xs.new(6) #=> xxx..xxxxxx 01297 * r.to_a #=> [xxx, xxxx, xxxxx, xxxxxx] 01298 * r.member?(Xs.new(5)) #=> true 01299 * 01300 */ 01301 01302 void 01303 Init_Range(void) 01304 { 01305 #undef rb_intern 01306 #define rb_intern(str) rb_intern_const(str) 01307 01308 id_cmp = rb_intern("<=>"); 01309 id_succ = rb_intern("succ"); 01310 id_beg = rb_intern("begin"); 01311 id_end = rb_intern("end"); 01312 id_excl = rb_intern("excl"); 01313 id_integer_p = rb_intern("integer?"); 01314 id_div = rb_intern("div"); 01315 01316 rb_cRange = rb_struct_define_without_accessor( 01317 "Range", rb_cObject, range_alloc, 01318 "begin", "end", "excl", NULL); 01319 01320 rb_include_module(rb_cRange, rb_mEnumerable); 01321 rb_marshal_define_compat(rb_cRange, rb_cObject, range_dumper, range_loader); 01322 rb_define_method(rb_cRange, "initialize", range_initialize, -1); 01323 rb_define_method(rb_cRange, "initialize_copy", range_initialize_copy, 1); 01324 rb_define_method(rb_cRange, "==", range_eq, 1); 01325 rb_define_method(rb_cRange, "===", range_eqq, 1); 01326 rb_define_method(rb_cRange, "eql?", range_eql, 1); 01327 rb_define_method(rb_cRange, "hash", range_hash, 0); 01328 rb_define_method(rb_cRange, "each", range_each, 0); 01329 rb_define_method(rb_cRange, "step", range_step, -1); 01330 rb_define_method(rb_cRange, "bsearch", range_bsearch, 0); 01331 rb_define_method(rb_cRange, "begin", range_begin, 0); 01332 rb_define_method(rb_cRange, "end", range_end, 0); 01333 rb_define_method(rb_cRange, "first", range_first, -1); 01334 rb_define_method(rb_cRange, "last", range_last, -1); 01335 rb_define_method(rb_cRange, "min", range_min, 0); 01336 rb_define_method(rb_cRange, "max", range_max, 0); 01337 rb_define_method(rb_cRange, "size", range_size, 0); 01338 rb_define_method(rb_cRange, "to_s", range_to_s, 0); 01339 rb_define_method(rb_cRange, "inspect", range_inspect, 0); 01340 01341 rb_define_method(rb_cRange, "exclude_end?", range_exclude_end_p, 0); 01342 01343 rb_define_method(rb_cRange, "member?", range_include, 1); 01344 rb_define_method(rb_cRange, "include?", range_include, 1); 01345 rb_define_method(rb_cRange, "cover?", range_cover, 1); 01346 } 01347