#include <stdio.h>
#include <stdlib.h> /* For exit() */

/* Based on an algorithm from Brian Wickman to generate unique racks.
   #define DBMAIN to get the stand-alone version complete with main().
   Heavily modified to make it a producer and non-recursive.
   Uses manually-programmed co-routine structure.

   Does 2 iterations in 2.9s on a 2.5GHz Dell
 */

static char *nextdraw(int drawsize, char *rack)
{
#define RUNNING 0
#define COBREAK 1
#define push(i) stack[stackp++] = i
#define pop(i)  i = stack[--stackp]
     static int tot[256];
     static int rackcount[256];
     static int FIRSTTILE = 0;  /* defaults work, but narrow these for speed */
     static int LASTTILE = 256; /* The closer the blank is to the letters (eg 'A'-1), the better */
     static int stackp = 0;
     static char buffer[8];     // Max rack size + 1
     static int state=RUNNING;
     static int stack[(256+COBREAK)*3]; /* Alphabet size * 3 */
     int i, tile, sum, nexttile, nextsum;
     if (state == COBREAK) goto RESUME; // resume co-routine

     // otherwise initial entry point.  Set everything up here.
     for (i = 0; i < 256; i++) {rackcount[i] = 0;tot[i] = 0;}
     {char *s = rack; while (*s != '\0') tot[*s++]++;}
     LASTTILE = 256; while (tot[--LASTTILE] == 0); ++LASTTILE;
     FIRSTTILE = 0; while (tot[FIRSTTILE++] == 0); --FIRSTTILE;
     stackp = 0; tile = FIRSTTILE; sum = 0;
RECURSE:
     i = ((tot[tile] >= drawsize) ? drawsize : tot[tile])+1;
     NEXT: if (--i < 0) goto BREAK;
         rackcount[tile] = i;
                        /* Because there may be gaps in the alphabet */
                        /* (and also the blank is off to one side)   */
         nexttile = tile;
         while ((++nexttile < LASTTILE) && (tot[nexttile] == 0));
         if ((nexttile <= LASTTILE) && ((nextsum = sum + i) <= drawsize)) {
             if (nextsum == drawsize) {
                 int k, j;
                 char *p = buffer;
                 for (k = FIRSTTILE; k < LASTTILE; k++)
                     if (rackcount[k] > 0)
                         for (j = 0; j < rackcount[k]; j++) *p++ = k; *p = 0;
                 push(tile); push(sum); push(i); state=COBREAK;
                 return(buffer); RESUME: state=RUNNING;
             } else {
                 push(tile); push(sum); push(i);
                 tile = nexttile; sum = nextsum;
                 goto RECURSE; RETURN:;
             }
             pop(i); pop(sum); pop(tile);
         }
     goto NEXT; BREAK:
     rackcount[tile] = 0;
     if (stackp != 0) goto RETURN;
     return(NULL); /* DONE */
}

#ifdef DBMAIN
#define FULLRACK "aaaaaaaaabbccddddeeeeeeeeeeeeffggghhiiiiiiiiijkllllmm\
nnnnnnooooooooppqrrrrrrssssttttttuuuuvvwwxyyz??"

int main(void)
{
    int i, j;

    for (j = 0; j < 2; j++) {  // We do it twice to test the termination/reset
    i = 0;
    for (;;) {
      char *s = nextdraw(7, FULLRACK);
      if (s == NULL) break;
      if ((i < 3) || (i > 3199720)) fprintf(stdout, "%d: %s\n", i, s);
      i += 1;
    }
    if (i != 3199724) fprintf(stderr, "The last item was #%d - should have been 3199724\n", i);
    }
    exit(0);
    return(0);
}
#endif