/* weavereduce.c, Copyright (C) 2002, Tim McLarnan

The heart of Tim's Rudimentary Treadle Reducer.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

Do, please, let me hear from you if you use this package, or if you
have questions.

Tim McLarnan, Dept. of Mathematics, Earlham College, Richmond, IN 47374 USA
timm AT cs.earlham.edu

*/


/*
	Tim's Rudimentary Treadle Reducer (Tekla Lewin's weaving problem).
	Tim McLarnan 1/22/2000.
	Modified to run as a cgi script June 2000 TJMcL.
*/

#include <stdio.h>
#include "BigSet.h"
#include "weaving.h"
#include <stdlib.h>
#include <ctype.h>
#include <unistd.h>
#include <signal.h>


/*--------------------------------------------------------------
  Global variables.
----------------------------------------------------------------*/

SetList BrickList = NULL;  /* All intersections of targets.  Later, we
                              eliminate all Bricks not actually used in
			      any of the unions of 2 Bricks to make a Target.
			   */
TargetAndOptions TargetOptionsArray;
/*  Once we have the bricks in a list, we make for each target set
    a list of sets showing the possible ways to represent the
    target set as a union of 1 or 2 bricks.  The target and these
    options are stored in TargetOptionsList.  Later, OptionsArray[k] is
    this list for the target set TargetArray[k].  The sets in each
    list are sets of one or two indices, corresponding to the unions
    of the one or two bricks having these indices in BrickArray.
*/
BigSet *TargetArray;         /* The targets as an array. */
BigSet *BrickArray;          /* After removing unneeded bricks, we store
                                the bricks in this array. */
IntPairList **OptionsArray;  /* An array of lists, one for each target.
                                The lists contain pairs of integers
                                denoting pairs of bricks whose unions are
                                the target set. */
long BrickCount = 0, TargetCount = 0, ShaftCount = 0, TreadleCount = 0;

int Timeout;  /* Seconds remaining until timeout. */


/*----------------------------------------------------------
 * SafeBigSetMake, SafeBigSetCopy, SafeMalloc.  Tim McLarnan 7/10/2000
 * Wrappers for functions using malloc.
-----------------------------------------------------------*/
void SafeBigSetMake(BigSet *b, long max_size) {
  
  if (!BigSetMake(b, max_size)) {
    bailOut(BSMALLOC);
  }
}


void SafeBigSetCopy(BigSet source, BigSet *target) {
  
  if (!BigSetCopy(source, target)) {
    bailOut(BSMALLOC);
  }
}


void *SafeMalloc(size_t size) {
  
  void *result;
  
  if ((result = malloc(size)) == NULL) {
    bailOut(MALLOC);
  }
  return result;
}


/*--------------------------------------------------------------
   SetListLength.  Tim McLarnan 1/15/2000.
   pre:  sl is a SetList.
   post: returns the number of sets in sl.
----------------------------------------------------------------*/
long SetListLength(SetList sl) {

  int count = 0;

  while (sl != NULL) {
    count++;
    sl = sl->next;
  }
  return count;
}


/*------------------------------------------------------------------
   LoadPattern.  Tim McLarnan, 1/2/2000, 7/10/2000.
   pre:  Global vbles TargetCount, TargetArray must exist;
         Global ShaftCount holds the number of shafts in the pattern.
         Global TargetCount holds the number of treadles in the orig tie-up.
         BigSet must be #included.
         InputString is a string of pairs Grid=x+y& produced by the
         page generated by buildgrid.cgi. The meaning is that the
         box in row x, column y is checked, i.e., that shaft x
         is attached to treadle y.
   post: Reads the tie-up in to the array TargetArray.
--------------------------------------------------------------------*/
void LoadPattern(char *InputString) {

  int k, row, col;
  char *curpos;

  TargetArray = (BigSet *) SafeMalloc(TargetCount * sizeof(BigSet));
  for (k = 0; k < TargetCount; k++) {
    SafeBigSetMake(&(TargetArray[k]), ShaftCount);
  }
  while((curpos = strstr(InputString, "Grid")) != NULL) {
    if (sscanf(curpos + 5, "%d+%d", &row, &col) != 2) {
      bailOut(SSCANF);
    }
    if ((row < 0) || (col < 0) || (row >= ShaftCount) || (col >= TargetCount)){
      bailOut(INPUTAREFS);
    } else {
      BigSetAddElement(&(TargetArray[col]), row);
    }
    InputString = curpos + 9;
  }
}  


/*-----------------------------------------------------------------
 * GridOut.  Tim McLarnan 7/6/2000.
 * pre:  grid is an array of characters, which we will interpret as
 *       a Rows x Cols array.  It should consist of X's and .'s,
 *       representing filled and empty positions, resp.
 *       color is the name of one of the 16 standard html colors,
 *       like white or maroon.
 * post: puts out html to print the grid. The grid is displayed as
 *       squares of color color and as white squares. Colored squares
 *       print as X's.
 ----------------------------------------------------------------*/
void GridOut(char *grid, int Rows, int Cols, char *color) {
  
  int row, col;
  
  printf("<table border bordercolorlight=\"#A1A1A1\" ");
  printf("bordercolordark=\"#A1A1A1\">\n");
  printf("<tbody height=10 width=20 cellspacing=0 cellpadding=0>\n");
  for (row = 0; row < Rows; row++) {
    printf("<tr>\n");
    for (col = 0; col < Cols; col++) {
      if (*(grid++) == 'X') {
	printf("    <td height=10 width=15 bgcolor=%s>", color);
	printf("<font color=\"%s\">X</font></td>\n", color);
      } else {
	printf("    <td height=10 width=15 bgcolor=white><br></td>\n");
      }
    }
    printf("</tr>\n");
  }
  printf("</table>\n");
}


/*----------------------------------------------------------------
   PrintPattern.  Tim McLarnan 1/2/2000.
                  Modified for web use 7/10/2000.
   pre:  TargetArray holds the target sets;
         TargetCount is the number of targets.
   post: Prints the targets as a table.
------------------------------------------------------------------*/
void PrintPattern() {
  
  char grid[ShaftCount][TargetCount];
  /* NB: The variable-length array is allowed by Gnu C but not by ANSI/ISO */
  int row, col;

  printf("<p>The original tie-up looks like this:</p>\n");
  for (row = 0; row < ShaftCount; row++) {
    for (col = 0; col < TargetCount; col++) {
      if (BigSetElementOf(TargetArray[col], row)) {
	grid[row][col] = 'X';
      } else {
	grid[row][col] = '.';
      }
    }
  }
  GridOut((char *) grid, ShaftCount, TargetCount, "black");
}


/*--------------------------------------------------------------
 * DeChaff.  Tim McLarnan 7/10/2000.
 * pre:  The original tie-up has been placed in TargetArray.
 *       TargetCount holds the original number of treadles.
 *       ShaftCount holds the number of shafts.
 * post: Duplicate treadles and treadles tied to no shafts are removed.
 *       TargetCount is adjusted to count only surviving targets.
 * returns 1 if the tie-up was modified, 0 otherwise.
---------------------------------------------------------------*/
int DeChaff() {
  
  int changed = 0;
  int i, j, k;
  BigSet emptySet;
  
  SafeBigSetMake(&emptySet, ShaftCount);
  for (i = TargetCount - 1; i >= 0; i--) {
    if (!BigSetDiff(TargetArray[i], emptySet)) {
      /* Target i is the empty set. Get rid of it. */
      changed = 1;
      j = i + 1;
      while (j < TargetCount) {
	TargetArray[j - 1] = TargetArray[j];
	j++;
      }
      TargetCount--;
    }
  }
  for (i = 0; i < TargetCount - 1; i++) {
    j = i + 1;
    while (j < TargetCount) {
      if (!BigSetDiff(TargetArray[i], TargetArray[j])) {
	/*Target j = Target i. Eliminate j. */
	changed = 1;
	k = j + 1;
      while (k < TargetCount) {
	TargetArray[k - 1] = TargetArray[k];
	k++;
      }
      TargetCount--;
      } else {
	j++;
      }
    }
  }
  return(changed);
}


/*------------------------------------------------------------
 * InitializeBrickList.  Tim McLarnan, 7/10/2000.
 * pre:  The targets are placed as sets in TargetArray.
 * post: A list of the targets as SetLists is built as BrickList.
-------------------------------------------------------------*/
void InitializeBrickList() {
  
  SetList slold, slnew;
  int k;
  
  slold = (SetList) SafeMalloc(sizeof(SetList));
  slold->next = NULL;
  slold->set = TargetArray[TargetCount - 1];
  for (k = TargetCount - 2; k >= 0; k--) {
    slnew = (SetList) SafeMalloc(sizeof(SetList));
    slnew->next = slold;
    SafeBigSetCopy(TargetArray[k], &(slnew->set));
    slold = slnew;
  }
  BrickList = slnew;
  BrickCount = TargetCount;
}
	


/*---------------------------------------------------------------
   IsNew.  Tim McLarnan, 1/2/2000.
   pre:  s is a BigSet, and sl is a SetList.
   post: returns non-zero of s is not one of the sets in sl.
----------------------------------------------------------------*/
int IsNew(BigSet s, SetList sl) {

  while (sl != NULL) {
    if (!BigSetDiff(sl->set, s))
      return 0;
    else
      sl = sl->next;
  }
  return 1;
}


/*-------------------------------------------------------------------
   MakeBricks.  Tim McLarnan, 1/2/2000.
                Repaired from hopeless error 7/10/2000.
   pre:  global BrickList contains the target sets;
         global ShaftCount holds the number of shafts.
   post: Global BrickList holds all the intersections of target sets;
         Global BrickCount counts these bricks.
--------------------------------------------------------------------*/
void MakeBricks() {

  BigSet s;
  BigSet nullSet;
  SetList sl, firstSet, secondSet, tail;
  
  tail = BrickList;
  while (tail->next != NULL) {
    tail = tail->next;
  }
  SafeBigSetMake(&nullSet, ShaftCount);
  SafeBigSetMake(&s, ShaftCount);
  firstSet = BrickList;
  while (firstSet != NULL) {
    secondSet = firstSet;
    while (secondSet != NULL) {
      BigSetPlaceIntersection(firstSet->set, secondSet->set, &s);
      if (BigSetDiff(s, nullSet) && IsNew(s, BrickList)) {
	BrickCount++;
	sl = (SetList) SafeMalloc(sizeof(SetListDesc));
	SafeBigSetCopy(s, &sl->set);
	sl->next = NULL;
	tail->next = sl;
	tail = sl;
      }
      secondSet = secondSet->next;
    }
    firstSet = firstSet->next;
  }
  BigSetFree(&s);
  BigSetFree(&nullSet);
}


/*----------------------------------------------------------------
  MakeTargetOptionsSkeleton.  Tim McLarnan 1/2/2000.
                              Modified for Targets in an array 7/10/2000.
  pre:  Target sets are in global TargetArray.
        Global pointer TargetOptionsList exists (but may be uninitialized).
  post: TargetOptionsArray points to an array of TargetAndOptions whose
        target fields are the target sets and whose options fields are
	NULL pointers.
-----------------------------------------------------------------*/
void MakeTargetOptionsSkeleton() {

  int k;

  TargetOptionsArray =
    (TargetAndOptions)
    SafeMalloc(TargetCount * sizeof(TargetAndOptionsDesc));
  for (k = 0; k < TargetCount; k++) {
    SafeBigSetCopy(TargetArray[k], &(TargetOptionsArray[k].target));
    TargetOptionsArray[k].options = NULL;
  }
}


/*---------------------------------------------------------------
  MakeTargetOptions.  Tim McLarnan 1/2/2000
  pre:  Target sets are in global TargetArray.
        Intersections of target sets are in global BrickList.
        Global pointer TargetOptionsList exists (but may be uninitialized).
  post: TargetOptionsList is built, a list whose records are target sets
        together with lists of pairs of bricks (neither equal to the
	target set in question) whose unions are the target set.
----------------------------------------------------------------*/
void MakeTargetOptions() {

  SetList setl1, setl2;
  BigSet s;
  int k;
  PairList pl;
  int done;

  MakeTargetOptionsSkeleton();
  setl1 = BrickList;
  SafeBigSetMake(&s, ShaftCount);
  while (setl1->next != NULL) {
    setl2 = setl1->next;
    while (setl2 != NULL) {
      BigSetPlaceUnion(setl1->set, setl2->set, &s);
      if (BigSetDiff(s, setl1->set) && BigSetDiff(s, setl2->set)) {
	done = 0;
	k = 0;
	while ((k < TargetCount) && !done) {
	  if (!BigSetDiff(s, TargetOptionsArray[k].target)) {
	    pl = (PairList) SafeMalloc(sizeof(PairListDesc));
	    pl->next = TargetOptionsArray[k].options;
	    TargetOptionsArray[k].options = pl;
	    pl->head = (SetList) SafeMalloc(sizeof(SetListDesc));
	    SafeBigSetCopy(setl1->set, &(pl->head->set));
	    pl->head->next =
		 (SetList) SafeMalloc(sizeof(SetListDesc));
	    SafeBigSetCopy(setl2->set, &(pl->head->next->set));
	    pl->head->next->next = NULL;
	    done = 1;
	  } else {
	    k++;
	  }
	}
      }
      setl2 = setl2->next;
    }
    setl1 = setl1->next;
  }
  BigSetFree(&s);
}


/*-------------------------------------------------------------
PairListLength.  Tim McLarnan 1/2/2000
pre:  pl is a PairList, possibly NULL.
post: returns the length of this list.
--------------------------------------------------------------*/
long PairListLength(PairList pl) {
  long count = 0;

  while (pl != NULL) {
    count++;
    pl = pl->next;
  }
  return count;
}


/*------------------------------------------------------------
 * PLLCompare.  Tim McLarnan 7/10/2000.
 * Comparison function for sorting TargetOptionsArray.
-------------------------------------------------------------*/
int PLLCompare(const void *x, const void *y) {
  long length1 = PairListLength(((TargetAndOptions) x)->options);
  long length2 = PairListLength(((TargetAndOptions) y)->options);
  if (length1 > length2) {
    return (1);
  } else if (length1 < length2) {
    return(-1);
  } else {
    return(0);
  }
}


/*-------------------------------------------------------------
SortTargetOptions.  Tim McLarnan 1/15/2000.
                    Modified to triviality 7/10/2000.
pre:  TargetOptionsArray has been built.
post: sorts TargetOptionsArray so that targets with few representations
      as unions of pairs of bricks come first.
--------------------------------------------------------------*/
void SortTargetOptions() {
  
  qsort(TargetOptionsArray,
	TargetCount,
	sizeof(TargetAndOptionsDesc),
	PLLCompare);
}


/*-------------------------------------------------------------
Used(b).  Tim McLarnan 1/2/2000
          Modified for arays 7/10/2000.
pre:  TargetOptionsArray has been built.  b is a brick.
post: returns non-zero iff b is either a target set or one of 2 bricks
      whose union is a target set.
--------------------------------------------------------------*/
int Used(BigSet b) {

  int k;
  PairList opt;

  for (k = 0; k < TargetCount; k++) {
    if (!BigSetDiff(b, TargetOptionsArray[k].target))
      return 1;
    opt = TargetOptionsArray[k].options;
    while (opt != NULL) {
      if (!BigSetDiff(b, opt->head->set))
	return 1;
      if (!BigSetDiff(b, opt->head->next->set))
	return 1;
      opt = opt->next;
    }
  }
  return 0;
}


/*-------------------------------------------------------------
RemoveUnusedBricks.  Tim McLarnan 1/2/2000
pre:  BrickList and TargetOptionsArray have been built.
post: removes from BrickList any bricks not used in unions of 1 or 2 bricks
      to make a target set.  Keeps the count of bricks in BrickCount correct.
--------------------------------------------------------------*/
void RemoveUnusedBricks() {

  SetList start, brick, temp;

  start = (SetList) SafeMalloc(sizeof(SetListDesc));
  brick = start;
  brick->next = BrickList;
  while (brick->next != NULL) {
    if (!Used(brick->next->set)) {
      temp = brick->next;
      brick->next = brick->next->next;
      BigSetFree(&(temp->set));
      free(temp);
      BrickCount--;
    } else {
      brick = brick->next;
    }
  }
  BrickList = start->next;
  free(start);
}


/*-------------------------------------------------------------
BrickIndex.  Tim McLarnan 1/2/2000
pre:  Global Array BrickArray has been built.  s is a brick.
post: returns the integer k s.t. BrickArray[k] = s.
--------------------------------------------------------------*/
long BrickIndex(BigSet s) {

  long x;

  for (x = 0; x < BrickCount; x++)
    if (!BigSetDiff(BrickArray[x], s))
      return x;
  return -1;
}


/*-------------------------------------------------------------
OptionsToSets.  Tim McLarnan 1/2/2000
pre:  TargetArray, BrickList, and TargetAndOptionsArray have been made.
      Globals TargetCount and BrickCount count targets and bricks, resp.
post: Builds the global array BrickArray of BigSets
      holding the bricks, and the global array OptionsArray
      holding pairs of ints describing all ways to write the targets as
      unions of 1 or 2 bricks (excluding unions of the target with
      one of its subsets).
--------------------------------------------------------------*/
void OptionsToSets() {

  long count;
  SetList brick;
  IntPairList *list;
  PairList opts;

  BrickArray = (BigSet *) SafeMalloc(BrickCount * sizeof(BigSet));
  OptionsArray =
       (IntPairList **) SafeMalloc(TargetCount * sizeof(IntPairList *));
  brick = BrickList;
  for (count = 0; count < BrickCount; count++) {
    SafeBigSetMake(&BrickArray[count], BrickCount);
    SafeBigSetCopy(brick->set, &(BrickArray[count]));
    brick = brick->next;
  }
  for (count = 0; count < TargetCount; count++) {
    OptionsArray[count] =
	 (IntPairList *) SafeMalloc(sizeof(IntPairList));
    OptionsArray[count]->member[0] =
      OptionsArray[count]->member[1] =
      BrickIndex(TargetOptionsArray[count].target);
    list = OptionsArray[count];
    opts = TargetOptionsArray[count].options;
    while (opts != NULL) {
      list->next = (IntPairList *) SafeMalloc(sizeof(IntPairList));
      list = list->next;
      list->member[0] = BrickIndex(opts->head->set);
      list->member[1] = BrickIndex(opts->head->next->set);
      opts = opts->next;
    }
    list->next = NULL;
  }
}


/*-------------------------------------------------------------
PrintSolution.  Tim McLarnan 1/2/2000
                Modified for web use 6/27/2000
                and for arrays 7/10/2000
pre:  solutionSet is a set of bricks whose unary and pairwise unions
      include all target sets.  Globals TargetArray, TargetCount,
      BrickArray, BrickCount, and OptionsArray must all be correct.
      verboseQ is non-0 for more verbose printing.
post: prints the solution set.
--------------------------------------------------------------*/
void PrintSolution(const unsigned char solutionSet[]) {

  long k, t, shaft, brick;
  IntPairList *opt;
  char grid[ShaftCount][TreadleCount];
  /* NB: The variable-length array is allowed by Gnu C but not by ANSI/ISO */
  int bricksUsed[BrickCount];
  /* NB: The variable-length array is allowed by Gnu C but not by ANSI/ISO */
  BigSet targset;
  int whichTarget;

  printf("<p>Here's one solution:</p>\n");
  printf("<p>Tie up your loom like this:</p>\n");
  brick = 0;
  for (k = 0; k < BrickCount; k++) {
    if (solutionSet[k]) {
      bricksUsed[k] = 1 + brick;
      for (shaft = 0; shaft < ShaftCount; shaft++) {
	if (BigSetElementOf(BrickArray[k], shaft)) {
	  grid[shaft][brick] = 'X';
	} else {
	  grid[shaft][brick] = '.';
	}
      }
      brick++;
    }
  }
  GridOut((char *) grid, ShaftCount, TreadleCount, "maroon");
  printf("<p>The treadles of the original tie-up correspond to treadles\n");
  printf("or pairs of treadles in the reduced tie-up according to the\n");
  printf("following table:</p>\n");
  printf("<table border>\n<tr>\n");
  printf("<th>Original</th>\n");
  printf("<th><font color=\"maroon\">Reduced</font></th></tr>\n");
  for (whichTarget = 0; whichTarget < TargetCount; whichTarget++) {  
    printf("<tr><td align=center>%d</td>\n", whichTarget + 1);
    targset = TargetArray[whichTarget];
    t = 0;
    while (BigSetDiff(targset, TargetOptionsArray[t].target)) {
      t++;
    }
    opt = OptionsArray[t];
    while((opt != NULL) &&
	  ((solutionSet[opt->member[0]] == 0) ||
	   (solutionSet[opt->member[1]] == 0))) {
      opt = opt->next;
    }
    printf("<td align=center><font color=\"maroon\">%d",
	   bricksUsed[opt->member[0]]);
    if (opt->member[1] != opt->member[0]) {
      printf("+%d", bricksUsed[opt->member[1]]);
    }
    printf("</font></td></tr>\n");
  }
  printf("</table>\n");
  printf("<p>You'll need to modify your treadling draft accordingly.</p>\n");
  printf("<p>When there is one solution, there are often others (sometimes\n");
  printf("thousands of them.) Given one solution, though, you may be able\n");
  printf("to find others. You may also be able to modify this solution,\n");
  printf("by doing things like rearranging the treadles in order to get\n");
  printf("a tie-up which is easier to weave.</p>");
  printf("<p>Need to change your input? Your browser's\n");
  printf("<i>Back</i> button will take you back to the previous\n");
  printf("screen and save you a lot of retyping.</p>\n");
  printf("<p>Questions or comments? Do, please, \n");
  printf("<a href=\"http://www.cs.earlham.edu/~timm/mail.html\">");
  printf("mail them to me.</a></p>\n");
  printf("<hr>\n");
  printf("<a href=\"../treadle/form1.php\">Do another tie-up</a>\n");
  printf("&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp\n");
  printf("<a href=\"../treadle/index.php\">");
  printf("Back to Treadle Reducer home</a>\n");
}


/*-------------------------------------------------------------
DFS (depth-first search).  Tim McLarnan 1/2/2000
    Simplified by removing option to find all solutions, 7/7/2002
pre:  Globals TargetArray, TargetCount,
      BrickArray, BrickCount, and OptionsArray must all be correct.
      solutionSet is an array which is 1 at the positions of
        the bricks that have been included at this point
        in the search, 0 elsewhere.
      size is the size of the current set of bricks, i.e.,
        the numbers of 1's in solutionSet.
      level is the index of TargetArray we are checking at this point
        in the search.
post: recursively looks for a solution.
      Returns 1 if a solution is found, 0 otherwise.
--------------------------------------------------------------*/
int DFS(unsigned char solutionSet[], long size, long level) {

    IntPairList *option;
    int change_stat0, change_stat1, brick0, brick1;
    int newsize;
    
    if (level >= TargetCount) {  /* We're done; search was successful. */
	PrintSolution(solutionSet);
	return(1);
    }

    /* Next, we check whether the target at this level can be made
       using bricks already included. */
    option = OptionsArray[level];
    while (option != NULL) {
	if ((solutionSet[option->member[0]]) &&
	    (solutionSet[option->member[1]])) {
	    /* Both the bricks in this option are already among those chosen.
	     Move on to the next target. */
	    if (DFS(solutionSet, size, level + 1)) { /* Search succeeded. */
		return(1);
	    }
	}
	option = option->next;
    }

    /* The target at this level cannot be made using bricks already included.
       We'll have to add 1 or 2 bricks to make the target at this level. */
    if (size == TreadleCount)
        /* We're already at the max possible number of bricks.  Backtrack. */
	return(0);

    /* Now try each option at this level, adding in the bricks and
       continuing the search. */
    option = OptionsArray[level];
    while (option != NULL) {
	brick0 = option->member[0];
	brick1 = option->member[1];  /* Current target = brick0 union brick1 */
	if (solutionSet[brick0]) {  /* brick0 is already included */
	    change_stat0 = 0;
	} else {                    /* brick0 needs to be added. */
	    change_stat0 = 1;
	    solutionSet[brick0] = 1;
	}
	if (solutionSet[brick1]) {  /* brick1 is already included */
	    change_stat1 = 0;
	} else {                    /* brick1 needs to be added. */
	    change_stat1 = 1;
	    solutionSet[brick1] = 1;
	}
	newsize = size + change_stat0 + change_stat1;
	if (newsize > size) { /* This isn't 1 of the options handled above */
	    if (newsize <= TreadleCount) {
		/* Number of bricks chosen so far < max possible.
		   Move on to the next target. */
		if (DFS(solutionSet, newsize, level + 1)) {
		    /* Search succeeded. */
		    return(1);
		}
	    }
	    /* Search failed. Clean up solutionSet & try next option. */
	    if (change_stat0) solutionSet[brick0] = 0;
	    if (change_stat1) solutionSet[brick1] = 0;
	}
	option = option->next;
    }
    /* Can't do it with the given solutionSet. Backtrack. */
    return(0);
}

/*-----------------------------------------------------------
FreeSetList.  Tim McLarnan 1/4/2000
pre:  sl is a SetList.
post: frees all dynamically allocated storage in sl.
      Does not set sl to NULL.
-------------------------------------------------------------*/
void FreeSetList(SetList sl) {

  SetList temp;

  while (sl != NULL) {
    temp = sl->next;
    BigSetFree(&(sl->set));
    free(sl);
    sl = temp;
  }
}


/*-----------------------------------------------------------
FreePairList.  Tim McLarnan 1/4/2000
pre:  pl is a PairList.
post: frees all dynamically allocated storage in pl.
      Does not set pl to NULL.
-------------------------------------------------------------*/
void FreePairList(PairList pl) {

  PairList temp;

  while (pl != NULL) {
    temp = pl->next;
    FreeSetList(pl->head);
    free(pl);
    pl = temp;
  }
}


/*-----------------------------------------------------------
FreeIntPairList.  Tim McLarnan 1/22/2000
pre:  *ipl is an IntPairList.
post: frees all dynamically allocated storage in ipl.
      Does not set ipl to NULL.
-------------------------------------------------------------*/
void FreeIntPairList(IntPairList *ipl) {

  IntPairList *temp;

  while (ipl != NULL) {
    temp = ipl->next;
    free(ipl);
    ipl = temp;
  }
}


/*-----------------------------------------------------------
CleanUp.  Tim McLarnan 1/4/2000
pre:  All the various globals have been used.
post: frees all dynamically allocated storage in the globals.
      Sets globals to to NULL or 0.
-------------------------------------------------------------*/
void CleanUp() {

  int k;

  FreeSetList(BrickList);
  BrickList = NULL;
  for (k = 0; k < TargetCount; k++) {
    BigSetFree(&(TargetOptionsArray[k].target));
    FreePairList(TargetOptionsArray[k].options);
    BigSetFree(&(TargetArray[k]));
  }
  free(TargetArray);
  free(TargetOptionsArray);
  for (k = 0; k < BrickCount; k++) {
    BigSetFree(&(BrickArray[k]));
  }
  free(BrickArray);
  for (k = 0; k < TargetCount; k++) {
    FreeIntPairList(OptionsArray[k]);
  }
  free(OptionsArray);
  BrickList = NULL;
  TargetArray = NULL;
  BrickArray = NULL;
  OptionsArray = NULL;
  TreadleCount = 0;
  TargetCount = 0;
  BrickCount = 0;
  ShaftCount = 0;
}   


/*-------------------------------------------------------------
getNumericalValue.  Tim McLarnan 6/26/2000
pre:  instring is a standard input string from an html form.
      name is the name of a variable which will have an integer value.
      name must appear in instring.
post: returns the value of name in the input string.
--------------------------------------------------------------*/
int getNumericalValue(char *instring, char *name) {
  int value;
  char *start;

  if ((start = strstr(instring, name)) == NULL) {
    bailOut(GNV);
  }
  start = start + strlen(name) + 1;
  if (sscanf(start, "%d", &value) != 1) {
    bailOut(GNV);
  }
  return(value);
}


/*-------------------------------------------------------------
bailOut(). Tim McLarnan 6/26/2000
pre:  We should be in the middle of writing a web page.
post: Prints an unhelpful error message and exits.
--------------------------------------------------------------*/
void bailOut(int errcode) { 

  printf("<p>Sorry. An error happened where I thought everything would\n");
  printf("be fine. Please try again or \n");
  printf("<a href=\"http://www.cs.earlham.edu/~timm/mail.html\">");
  printf("send me mail.</a>\n");
  printf("<p>It would help me a lot if you could include the tie-up that\n");
  printf("produced the problem.</p>\n");
  printf("Telling me that it failed with error code %d ", errcode);
  printf("would also be a big help.</p>\n");
  printf("<p>Need to change your input? Your browser's\n");
  printf("<i>Back</i> button will take you back to the previous\n");
  printf("screen and save you a lot of retyping.</p>\n");
  printf("<hr>\n");
  printf("<a href=\"../treadle/form1.php\">Do another tie-up</a>\n");
  printf("&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp\n");
  printf("<a href=\"../treadle/index.php\">");
  printf("Back to Treadle Reducer home</a>\n");
  printf("</html>\n");
  exit(errcode);
}


/*--------------------------------------------------------------
 * regrets(). Tim McLarnan 6/26/2000
 * pre:  We should be writing a web page .
 * post: Prints a message that we have timed out and exits.
---------------------------------------------------------------*/
void regrets() {

  static int FirstTime = 1;

  Timeout -= 10;
  if (Timeout <= 0) {
    printf("<p>Sorry. No solutions were found in the allotted time.\n");
    printf("You could try again with a longer time limit. It may also\n");
    printf("be that no solutions exist.</p>\n");
    printf("<p>If you think you should not have timed out, please \n");
    printf("<a href=\"http://www.cs.earlham.edu/~timm/mail.html\">");
    printf("send me mail.</a></p>\n");
    printf("<p>Need to change your input? Your browser's\n");
    printf("<i>Back</i> button will take you back to the previous\n");
    printf("screen and save you a lot of retyping.</p>\n");
    printf("<hr>\n");
    printf("<a href=\"../treadle/form1.php\">Do another tie-up</a>\n");
    printf("&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp\n");
    printf("<a href=\"../treadle/index.php\">");
    printf("Back to Treadle Reducer home</a>\n");
    printf("</html>\n");
    exit(TIMEOUT);
  } else {
    if (FirstTime) {
      printf("<p><font color=\"green\">Seconds remaining ");
      printf("until timeout:<br></font>\n");
      FirstTime = 0;
    }
    printf("<font color=\"green\"> %d<br></font>\n", Timeout);
    fflush(stdout);
    alarm(10);
  }
}
  


/*-------------------------------------------------------------
main. Tim McLarnan 1/2/2000
      Modified as a CGI script 6/26/2000
pre:  Input comes from the form produced by buildgrid.c.
post: Finds a representation of the pattern using the requested
      number of treadles, if one exists.
--------------------------------------------------------------*/
int main(void) {

  const int MinShaft = 2,
    MaxShaft = 40,
    MinTarget = 2,
    MaxTarget = 100,
    MinTreadle = 2,
    MaxTreadle = 100,
    MaxInput = 50000;

  char InputString[MaxInput];
  /* NB: The variable-length array is allowed by Gnu C but not by ANSI/ISO */
  unsigned char *solutionSet;

  fgets(InputString, MaxInput, stdin);
  printf("Content-type: text/html\n\n");
  printf("<html><title>Treadle Reducer Output</title></head>\n");
  printf("<body bgcolor=white>\n");
  ShaftCount = getNumericalValue(InputString, "ShaftCount");
  if ((ShaftCount < MinShaft) || (ShaftCount > MaxShaft)) {
    printf("<p>Sorry. The number of shafts must be between\n");
    printf("%d and %d.</p>\n", MinShaft, MaxShaft);
    printf("<p>Please go back to the previous page and try again.</p>\n");
    printf("<p>If your problems persist, please \n");
    printf("<a href=\"http://www.cs.earlham.edu/~timm/mail.html\">");
    printf("send me mail.</a>\n");
    printf("</html>\n");
    exit(SHAFTCOUNT);
  }
  TargetCount = getNumericalValue(InputString, "TargetCount");
  if ((TargetCount < MinTarget) || (TargetCount > MaxTarget)) {
    printf("<p>Sorry. The number of treadles on the original tie-up must \n");
    printf("be between %d and %d.</p>\n", MinTarget, MaxTarget);
    printf("<p>Please go back to the previous page and try again.</p>\n");
    printf("<p>If your problems persist, please \n");
    printf("<a href=\"http://www.cs.earlham.edu/~timm/mail.html\">");
    printf("send me mail.</a>\n");
    printf("</html>\n");
    exit(TARGETCOUNT);
  }
  TreadleCount = getNumericalValue(InputString, "TreadleCount");
  if ((TreadleCount < MinTreadle) || (TreadleCount > MaxTreadle)) {
    printf("<p>Sorry. The number of treadles on your loom must be between\n");
    printf("%d and %d.</p>\n", MinTreadle, MaxTreadle);
    printf("<p>Please go back to the previous page and try again.</p>\n");
    printf("<p>If your problems persist, please \n");
    printf("<a href=\"http://www.cs.earlham.edu/~timm/mail.html\">");
    printf("send me mail.</a>\n");
    printf("</html>\n");
    exit(TREADLECOUNT);
  }
  LoadPattern(InputString);
  Timeout = getNumericalValue(InputString, "Timeout");
  signal(SIGALRM, regrets);
  alarm(10);
  PrintPattern();
  if (DeChaff()) {
    printf("<p>The original tie-up either contains treadles not tied to\n");
    printf("any shaft or 2 treadles tied to the same set of shafts.\n");
    printf("We'll therefore start by eliminating the empty or duplicate\n");
    printf("treadles and will work with the simplified tie-up below.</p>\n");
    printf("References below to the treadling draft will refer to the\n");
    printf("treadling draft for this simplified tie-up.</p>\n");
    PrintPattern();
    if (TargetCount <= TreadleCount) {
      printf("<p>This simplification is all that is required to reduce\n");
      printf("the number of treadles to at most %ld.</p>\n", TreadleCount);
      printf("<p>We're therefore done.</p>\n");
      printf("<p>Need to change your input? Your browser's\n");
      printf("<i>Back</i> button will take you back to the previous\n");
      printf("screen and save you a lot of retyping.</p>\n");
      printf("<hr>\n");
      printf("<a href=\"../treadle/form1.php\">Do another tie-up</a>\n");
      printf("&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp\n");
      printf("<a href=\"../treadle/index.php\">");
      printf("Back to Treadle Reducer home</a>\n");
      printf("</html>\n");
      exit(0);
    }
  }
  fflush(stdout);
  InitializeBrickList();
  MakeBricks();
  /*  PrintBricks(); */
  MakeTargetOptions();
  /*  PrintTargetOptions(0); */
  SortTargetOptions();
  /*  PrintTargetOptions(0); */
  RemoveUnusedBricks();
  /*  PrintBricks(); */
  OptionsToSets();
  /*  PrintWorkSets(); */
  solutionSet =
    (unsigned char *) SafeMalloc(BrickCount * sizeof (unsigned char));
  if (!DFS(solutionSet, 0, 0)) {
    printf("<p>Sorry, it is impossible to reduce this tie-up to the number\n");
    printf("treadles you asked.</p>\n");
    printf("<p>We didn't run out of time: we tried all the possibilities,\n");
    printf("and none of them worked.</p>\n");
    printf("<p>A caveat: this program does not attempt to find reductions\n");
    printf("in which the weaver must depress more than one treadle at a\n");
    printf("time with each foot. You might therefore try running it again,\n");
    printf("asking for a solution with slightly more treadles than you\n");
    printf("actually have. Maybe looking at the solution would help you\n");
    printf("see how to find a reduction in which you use one foot to press\n");
    printf("2 treadles at once.</p>");
    printf("<p>Hitting the <i>back</i> button on your browser\n");
    printf("will put you back at the previous screen so you can\n");
    printf("change the number of treadles without retyping\n");
    printf("the tie-up.</p>\n");
    printf("If you have other suggestions, do, please, \n");
    printf("<a href=\"http://www.cs.earlham.edu/~timm/mail.html\">");
    printf("send me mail.</a>\n");
    printf("<hr>\n");
    printf("<a href=\"../treadle/form1.php\">Do another tie-up</a>\n");
    printf("&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp\n");
    printf("<a href=\"../treadle/index.php\">");
    printf("Back to Treadle Reducer home</a>\n");
    printf("</html>\n");
    exit(NOSOLN);
  }
  printf("</html>\n");
  CleanUp();
  free(solutionSet);
  exit(0);
}


/* What follows is some code possibly useful for debugging. */


/*-------------------------------------------------------------------
   PrintBricks.  Tim McLarnan 1/2/2000.
   pre:  BrickList is a global SetList holding the intersections oftarget sets;
         BrickCount is the number of these bricks.
   post: Prints the bricks and their number, for debugging.
--------------------------------------------------------------------*/
void PrintBricks() {

  SetList targ = BrickList;

  printf("<p></p><p>There are %ld bricks:<br>\n", BrickCount);
  while (targ != NULL) {
    BigSetPrint(targ->set);
    printf("<br>\n");
    targ = targ->next;
  }
  printf("</p>\n");
}


/*---------------------------------------------------------------
PrintTargetOptions.  Tim McLarnan 1/2/2000
pre:  Global TargetOptionsArray built.
post: Prints TargetOptionsArray, for debugging.
----------------------------------------------------------------*/
void PrintTargetOptions(int verbosity) {

  int k;
  PairList pl;

  printf("<p></p><p>Target options:<br>\n");
  for (k = 0; k < TargetCount; k++) {
    BigSetPrint(TargetOptionsArray[k].target);
    printf("  ->");
    pl = TargetOptionsArray[k].options;
    if (verbosity == 0) {
    	printf("  %ld<br>\n", PairListLength(pl));
    } else {
    	while (pl != NULL) {
      		printf("  ");
      		BigSetPrint(pl->head->set);
      		printf("+");
      		BigSetPrint(pl->head->next->set);
      		pl = pl->next;
    	}
    	printf("<br>\n");
    }
  }
  printf("</p>\n");
}


/*-------------------------------------------------------------
PrintWorkSets.  Tim McLarnan 1/2/2000
pre:  Global Arrays TargetArray, BrickArray, OptionsArray have been built.
      Globals TargetCount and BrickCount count targets and bricks.
post: Prints the targets, bricks, and options, both for debugging and as
      a normal summary of the work.
--------------------------------------------------------------*/
void PrintWorkSets() {

  IntPairList *ipl;
  long k;

  printf("<p></p><p>Targets:<br>\n");
  for (k = 0; k < TargetCount; k++) {
    printf("%3ld   ", k);
    BigSetPrint(TargetArray[k]);
    printf("<br>\n");
  }
  printf("\n</p><p>Bricks:<br>\n");
  for (k = 0; k < BrickCount; k++) {
    printf("%3ld   ", k);
    BigSetPrint(BrickArray[k]);
    printf("<br>\n");
  }
  printf("</p><p>\nRepresentations of targets in terms of bricks:<br>\n");
  for (k = 0; k < TargetCount; k++) {
    printf("%3ld", k);
    ipl = OptionsArray[k];
    while (ipl != NULL) {
      printf("  {%d,%d}", ipl->member[0], ipl->member[1]);
      ipl = ipl->next;
    }
    printf("<br>\n");
  }
  printf("</p>\n");
}