Ruby  2.0.0p247(2013-06-27revision41674)
range.c
Go to the documentation of this file.
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