// Routine to step through rooted unlabeled trees. V1.0
// Based on Terry Beyer & Sandra Mitchell Hedetniemi, SIAM J. Comput. 1980.
// This is written in standard C except I use the "//" comment style.
// Also, I use 64 bits integers as defined in stdint.h .
// Free distribution of this code is permitted.
// Doug Wiedemann, November 2007.

// Set TEST to 1 to compile into a test program.
// Set to 0 for just the stepping routine.

#define TEST 1

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

struct state {
  int64_t p;
  int64_t *Prev;
  int64_t *Save;
};

// Arguments -
// n: is the number of nodes in the tree.
// L: is an array of n integers. Before the first call it does not
//       have to be set to any particular value.
//       On return, L has entries in the range 1 to n
//       giving the depth first code of the next tree.
//       L (and n) should not be changed if further calls to "genrt" are
//       to be made.
// h: is the location of a pointer to the state. Before the first call it must
//       be set so that *h is NULL. Then it should be retained
//       from one call to the next. If the user does not intend
//       to call genrt until there are no more cases, "free(*h)"
//       will free up a small amount of space.
// If "genrt" is called and there are no more trees, *h is reset to NULL,
// and internal storage is freed.
//
void genrt(int64_t n,int64_t *L,void **h) {
  int64_t i, p, diff;
  struct state *s;
  int64_t *Save, *Prev;
  s = (struct state *)(*h);
  if(!s) {
    if(n==0)
      return;
    s = (struct state *)malloc(sizeof(struct state));
    if(!s)
      exit(1);
    s->Save = (int64_t *)malloc(sizeof(int64_t)*n);
    s->Prev = (int64_t *)malloc(sizeof(int64_t)*n);
    for(i=0;i<n;i++) {
      L[i] = i+1;
    }
    s->p = (n<3) ? 0 : n;
    for(i=0;i<n;i++) {
      s->Save[i] = 0; s->Prev[i] = i+1;
    }
    *h = (void*)s;
  } else {
    Save = s->Save; Prev = s->Prev; p = s->p;
    if(p>1) {
      L[p-1]--;
      if((p<n)&&((L[p-1]!=2)||(L[p-2]!=2))) {
	diff = p - Prev[L[p-1]-1];
	while(p<n) {
	  Save[p-1] = Prev[L[p-1]-1];
	  Prev[L[p-1]-1] = p;
	  p++;
	  L[p-1] = L[p-diff-1];
	}
      }
      while(L[p-1]==2) {
	p--;
	Prev[L[p-1]-1] = Save[p-1];
      }
    s->p = p;
    } else {
      L[0] =0; free(s); *h = NULL;
    }
  }
}

#if TEST == 1

int64_t cmpArrays(int64_t *A,int64_t *B,int64_t n) {
  int i;
  for(i=0;i<n;i++) {
    if( A[i] != B[i] )
      return A[i]>B[i]?1:-1;
  }
  return 0;
}

// Test genrt by stepping though all trees of n nodes.
// n is one argument to the routine.

main(int argc,char **argv) {
  int i;
  int64_t *L, *Lx;
  int64_t n, tot=0;
  void *handle = NULL;
  if( argc != 2 ) {
    printf("Usage: %s n\n",argv[0]);
    exit(1);
  }
  n = atoi(argv[1]);
  if(n<0) {
    printf("Can't handle negative n.\n");
    exit(1);
  }
  L = malloc(n*sizeof(int64_t));
  Lx = malloc(n*sizeof(int64_t));
  while(1) {
    genrt(n,L,&handle);
    if(!handle)
      break;
    tot++;
    if(1) {
      for(i=0;i<n;i++) {
	printf("%d ",(int)L[i]);
      }
      printf("\n");
    };
    if( (tot>1) && (cmpArrays(Lx,L,n) <= 0) ) {
      printf("Error - trees out of order.\n");
    }
    for(i=0;i<n;i++)
      Lx[i] = L[i];
  }
  printf("Total trees %d\n",(int)tot);
  exit(0);
}

#endif