static VALUE
rb_ary_sample(int argc, VALUE *argv, VALUE ary)
{
VALUE nv, result, *ptr;
VALUE opts, randgen = rb_cRandom;
long n, len, i, j, k, idx[10];
double rnds[numberof(idx)];
if (OPTHASH_GIVEN_P(opts)) {
randgen = rb_hash_lookup2(opts, sym_random, randgen);
}
ptr = RARRAY_PTR(ary);
len = RARRAY_LEN(ary);
if (argc == 0) {
if (len == 0) return Qnil;
if (len == 1) {
i = 0;
}
else {
double x = rb_random_real(randgen);
if ((len = RARRAY_LEN(ary)) == 0) return Qnil;
i = (long)(x * len);
}
return RARRAY_PTR(ary)[i];
}
rb_scan_args(argc, argv, "1", &nv);
n = NUM2LONG(nv);
if (n < 0) rb_raise(rb_eArgError, "negative sample number");
if (n > len) n = len;
if (n <= numberof(idx)) {
for (i = 0; i < n; ++i) {
rnds[i] = rb_random_real(randgen);
}
}
len = RARRAY_LEN(ary);
ptr = RARRAY_PTR(ary);
if (n > len) n = len;
switch (n) {
case 0:
return rb_ary_new2(0);
case 1:
i = (long)(rnds[0] * len);
return rb_ary_new4(1, &ptr[i]);
case 2:
i = (long)(rnds[0] * len);
j = (long)(rnds[1] * (len-1));
if (j >= i) j++;
return rb_ary_new3(2, ptr[i], ptr[j]);
case 3:
i = (long)(rnds[0] * len);
j = (long)(rnds[1] * (len-1));
k = (long)(rnds[2] * (len-2));
{
long l = j, g = i;
if (j >= i) l = i, g = ++j;
if (k >= l && (++k >= g)) ++k;
}
return rb_ary_new3(3, ptr[i], ptr[j], ptr[k]);
}
if (n <= numberof(idx)) {
VALUE *ptr_result;
long sorted[numberof(idx)];
sorted[0] = idx[0] = (long)(rnds[0] * len);
for (i=1; i<n; i++) {
k = (long)(rnds[i] * --len);
for (j = 0; j < i; ++j) {
if (k < sorted[j]) break;
++k;
}
memmove(&sorted[j+1], &sorted[j], sizeof(sorted[0])*(i-j));
sorted[j] = idx[i] = k;
}
result = rb_ary_new2(n);
ptr_result = RARRAY_PTR(result);
for (i=0; i<n; i++) {
ptr_result[i] = ptr[idx[i]];
}
}
else {
VALUE *ptr_result;
result = rb_ary_new4(len, ptr);
RBASIC(result)->klass = 0;
ptr_result = RARRAY_PTR(result);
RB_GC_GUARD(ary);
for (i=0; i<n; i++) {
j = RAND_UPTO(len-i) + i;
nv = ptr_result[j];
ptr_result[j] = ptr_result[i];
ptr_result[i] = nv;
}
RBASIC(result)->klass = rb_cArray;
}
ARY_SET_LEN(result, n);
return result;
}