shithub: zuke

ref: 524e32b1cd45a332c58b8cd681662f815628deee
dir: /shuffle.c/

#include "shuffle.h"

void
shuffle_init(Shuffle *s, int (*rndrange)(int max_excluding), int total, int first)
{
	assert(first < total && total > 0);
	s->m = s->n = total;
	s->i = 0;
	s->xi = s->x0 = first;

	if(total < 4){
		s->a = 1;
		s->c = 3;
		s->m = 7;
		return;
	}

	s->m += 1;
	s->m |= s->m >> 1;
	s->m |= s->m >> 2;
	s->m |= s->m >> 4;
	s->m |= s->m >> 8;
	s->m |= s->m >> 16;

	s->a = 1 + rndrange(s->m/4)*4;     /* 1 ≤ a < m   && a mod 4 = 1 */
	s->c = 3 + rndrange((s->m-2)/2)*2; /* 3 ≤ c < m-1 && c mod 2 = 1 */
}

void
shuffle_resize(Shuffle *s, int total)
{
	assert(total > 0);
	s->n = total;
}

static int
next(Shuffle *s)
{
	int res;

	res = s->xi;
	if(s->n < 2){
		/* if it's less than two items, just use the first one (if any) */
		s->x0 = s->xi = s->i = 0;
		return 0;
	}else if(s->x0 >= s->n){
		/* if items were removed up to this one -- update for a period */
		s->x0 = 0;
	}

	for(;;){
		s->xi = (s->a*s->xi + s->c) & s->m;
		if(s->xi < s->n){
			s->i++;
			if(s->xi == s->x0)
				s->i = 0;
			break;
		}
	}

	return res;
}

int
shuffle_one(Shuffle *s, int index)
{
	if(s->n < 1 || index < 0)
		return index;
	index %= s->n;
	while(s->i < s->n && s->i != index)
		next(s);

	return next(s);
}

int
shuffle_for(Shuffle *s, int index)
{
	int i, r;

	if(index < 0 || index >= s->n)
		return index;
	for(i = 0; i < s->n; i++){
		r = s->i;
		if(next(s) == index){
			next(s);
			return r;
		}
	}

	return index;
}