/*
 * Walk through subsets in an ordered way.
 *   For all subsets, this is the classic gray code.
 *
 * Graycode_init0 is called once at the very beginning with
 *   the maximum number of categories.  It allocates a scratch vector.
 *
 * Graycode_init1 is called once for each unordered variable.
 * Graycode_init2 is called once for each orderable variable,
 *   the second argument is a vector that will be used to rank the variables
 */
#include "rpart.h"
#include "rpartproto.h"
static int *gray;
static int maxc, gsave;

void
graycode_init0(int maxcat)
{
    gray = (int *) ALLOC(maxcat, sizeof(int));
}

void
graycode_init1(int numcat, int *count)
{
    int i;

    maxc = numcat;
    for (i = 0; i < maxc; i++)
	gray[i] = count[i] ? 1 : 0;
    gsave = -2;
}


void
graycode_init2(int numcat, int *count, double *val)
{
    int i, j, k;
    double temp;
    maxc = numcat;

    /*
     *   sort categories with no members first
     *   then order by val
     */
    gray[0] = 0;
    if (count[0] == 0)
	k = 1;
    else
	k = 0;
    for (i = 1; i < maxc; i++) {
	if (count[i] == 0) {
	    for (j = i - 1; j >= k; j--) {
		gray[j + 1] = gray[j];
		val[j + 1] = val[j];
	    }
	    gray[k++] = i;
	} else {
	    temp = val[i];
	    for (j = i - 1; j >= k && val[j] > temp; j--) {
		gray[j + 1] = gray[j];
		val[j + 1] = val[j];
	    }
	    val[j + 1] = temp;
	    gray[j + 1] = i;
	}
    }
    gsave = k - 1;
}

/*
* Everyone starts in the right hand group
* This routine returns the next subject who needs to
*  change allegiance.
* A value of maxc means that we're done.
*/
int
graycode(void)
{
    int i;

    if (gsave > -2) {           /* ordered data */
	gsave++;
	if (gsave < maxc)
	    return gray[gsave];
	else
	    return maxc;
    } else {
	/*
	 * Form next subgroup.  We do this using the classic Gray code.
	 *  The initial subset has everyone in the right group.  Each
	 *  subset varies from the prior by only one member -- the
	 *  following item changes groups: 1,2,1,4,1,2,1,8,1,2,1,4,1,...
	 *  The outer loop only goes up to maxc-1: we know for rpart that
	 *    changing the allegiance of the last subject is never necessary
	 */
	for (i = 0; i < maxc - 1; i++) {
	    if (gray[i] == 1) {
		gray[i] = 2;
		return i;
	    } else if (gray[i] == 2)
		gray[i] = 1;
	}
	return maxc;            /* signal "done" */
    }
}