/* squarect.c */
/* Description:
 * This program inputs the tiling file for a quadrilateral and outputs
 * a postscript file for the associated squared rectangle. It uses
 * the cyclic algorithm to either compute exactly or approximate
 * the sizes of the squares. The program writes five files to disk:
 * temp.rot gives the tiling file for the rotated quadrilateral;
 * temp.sk gives the tiling file for the rotated quarilateral with
 * skinny adjacencies added; temp.foropt is an input file for the cyclic
 * algorithm for the original tiling; temp.forskopt is an input file
 * for the cyclic algorithm for the rotated tiling with skinny
 * adjacencies added; and temp.opt gives the weights, heights, and widths
 * for the squared rectangle.
 *
 * Copyright (c) 1998, 2000  James W. Cannon, William J. Floyd, and
 * Walter R. Parry
 *
 * This work was supported in part by National Science Foundation
 * grants DMS-9803868 and DMS-9971783.
 *
 * This is free software and may be freely copied, modified, and
 * redistributed as noted below.
 *      The copyright notice must remain intact.
 *      Modifications must include a notice giving the reason
 *      for the modification and including name and date.
 *      This is provided "as is" and comes with no warranty or
 *      guarantee of fitness. Comments, bugs, and suggestions may be
 *      sent to floyd@math.vt.edu.
 *
 */

/*************** global declarations ********************/

#include <stdio.h>
#include <malloc.h>
#include "math.h"
FILE * fp = NULL, *fopen();
char t[30];
char *s1;
char *s2;

#define MAXVALENCE 50
        /* The assumed maximal number of adjacencies to a tile
         * that is not an edge tile. */
        /* For the edge tiles we assume no more than nooftiles
         * as the maximum number of adjacencies.*/
#define MAXCYCLE 50
        /* The assumed maximal length in a vertex cycle. */

#define XMIN 50  /* Variables for the postscript files. */
#define YMIN 50
#define XMAX 550
#define YMAX 750

/* tiling types and variables */
#define TILINGMAX 200000
#define EDGEMAX   800000
struct tile{
    int type,wt[3],wtsum,size,*edge;
} tiling[TILINGMAX];
int length, * tilinglength;

/* tree and queue types */
struct treenode{
    struct treenode * parent, * lchild, * rchild;
    struct queuenode * firstqueuenode, * lastqueuenode;
    int wtsum;
};

struct queuenode {
    struct queuenode * nextqueuenode;
    int tileoffset;
};

/* interim reporting variables */
int AREA, GCD, HEIGHT;

/* Variables for the old tiling.*/
int noofedges; /* Acts as size of *edges. */
int nooftiles; /* Acts as size of each of next three arrays.*/
int *facetype; /*Array,dynamically allocated:gives type of each tile.*/
int *facesize; /* Array: gives no of edges of each tile.*/
int *facebegin;/* Array: gives first edgeid associated with each tile.*/
int *edges;    /* Array: gives tileid adjacent across each edge of each tile.*/
               /* Since each tile has several edges, there are more edges than
                * tiles.*/

/* Variables for the new adjacency information.*/
int *vertex; /* Indexed by noofedges. */

/* Variables to describe an edge cycle.*/
int cyclelength;
int *tilecycle;
int *frontedge_cycle;
int *backedge_cycle;

/* Variables for the adjacency information for vertices. */
int noofverts, maxnoofverts; /* The number of vertices and an upper.
                              * bound for the number of vertices. */
int v;                       /* The number of the current vertex. */
int *noofvertadj; /* Array: vertadjsize[i] gives the number of vertices
                   * adjacent to vertex i. */
int **vertadj;    /* Array: vertadjac[i] gives the vertices adjacent to
                   * vertex i. */
int *vertused;    /* Array: entry is -1 if the adjacencies of a vertex hasn't
                   * been computed yet. */

/* Variables for the new adjacency information.*/
int *noofnewadj; /* Indexed by nooftiles.*/
int **newadj;    /* Indexed first by nooftiles, then by *noofnewadj.*/
int *edgeused;   /* Indexed by noofedges. Used to keep track of which
                  * edges have already been tested for cycles.*/

/* Variables to describe an edge cycle.*/
int cyclelength;
int *tilecycle;
int *frontedge_cycle;
int *backedge_cycle;

/* Variables for the input for writepsfile. */
float *weight;   /* Array: the approximate weight of each tile. */
float *botdist;  /* Array: the distance from the bottom for each tile. */
float *leftdist; /* Array: the distance from the left side for each tile. */

main(argc, argv) int argc; char *argv[];
{
    /* initialize tiling variables */
    extern int length, * tilinglength;
    extern struct tile tiling[TILINGMAX];
    length = 0;
    tilinglength = &length;
    AREA = 0;
    GCD = 0;
    HEIGHT = 0;
    Init(tiling);

   sqrect(tiling,tilinglength);
} /*end main() */
/******************* end main() ********************/

/******************* begin sqrect ********************/

sqrect(tiling,tilinglength)
    struct tile *tiling;
    int * tilinglength;
{   /* loop variables */
    int i,j,k;
    int cyclebeginstorage, * cyclebegin;

    /* standard input variable and functions */
    char s[256];
    extern char *gets();
    extern int atoi();
    extern int AREA, GCD, HEIGHT;
    float MODULUS;

fprintf(stderr,"This program inputs the tiling file for a ");
fprintf(stderr,"quadrilateral and outputs\n");
fprintf(stderr,"a postscript file ");
fprintf(stderr,"for the associated squared rectangle. It uses the\n");
fprintf(stderr,"cyclic algorithm to compute exactly or approximate ");
fprintf(stderr,"the sizes of the\n");
fprintf(stderr,"squares. The program writes five files to disk.\n");
fprintf(stderr,"temp.rot gives the tiling file for the rotated ");
fprintf(stderr,"quadrilateral.\n");
fprintf(stderr,"temp.sk gives the tiling file for the rotated ");
fprintf(stderr,"quadrilateral with\n");
fprintf(stderr,"skinny adjacancies added. ");
fprintf(stderr,"temp.foropt is an input file for the cyclic\n");
fprintf(stderr,"algorithm for the original tiling. ");
fprintf(stderr,"temp.forskopt is an input file\n");
fprintf(stderr,"for the cyclic algorithm ");
fprintf(stderr,"for the rotated tiling with skinny\n");
fprintf(stderr,"adjacencies added. ");
fprintf(stderr,"temp.opt gives the weights, heights, and widths\n");
fprintf(stderr,"for the squared rectangle.\n");
fprintf(stderr,"\n");

Readtilingandsize(0);
s2 = "temp.foropt";
Prepforcyclicalg(0);
cyclebegin = &cyclebeginstorage;
*cyclebegin=0;
Readfromfile(tiling,tilinglength);
Cycle(tiling,tilinglength,cyclebegin);
Writefordiv(tiling,tilinglength);
s1 = "temp.rot";
Rotatetiling();
Readtilingandsize(1);
Addskinnypathstoold();
Writesktilingandsize();
s1 = "temp.sk";
Readtilingandsize(1);
s2 = "temp.forskopt";
Prepforcyclicalg(1);
*cyclebegin=0;
s2 = "temp.forskopt";
Readfromfile(tiling,tilinglength);
Appendfordiv(tiling,tilinglength);
Readweights();
Printtofile();

} /*end sqrect */

/******************* end div ********************/

/* Readtilingandsize */
/* Description:

 * The text portions of the format are 1-string comments that must
 * appear in the file.
 * The comments are read and discarded by fscanf as a single string.
 * The content of the comment lines is only to help those writing input
 * files.
 * Here is the format:

   Number_of_tiles_including_the_four_standard_ends:
   <number>
   Type_of_each_of_these_tiles:
   <numbers (no tile-number id is to be included)>
   Size_of_each_of_these_tiles:
   <numbers (no tile-number id is to be included)>
   Tile-ids_--_Adjacent_tiles_in_correct_order:
   <id number ... number>
   <id number ... number>
   ...
   <any number of comments or extra data not to be used by the program>
 */

Readtilingandsize(ifread)
    int ifread;
{   /* loop variables */
    int i,j,k,l,m;

    /* standard input variable and functions */
    char s[256];
    extern char *gets();
    extern int atoi();

FILE *fp;  
if (ifread == 0){
fprintf(stderr,"Read which tiling file? \n");
fprintf(stderr,"\n");
gets(s);
if ((fp = fopen(s,"r")) == NULL)
{
  fprintf(stderr," cannot open file \n");
  exit();
}
}
else 
{
if ((fp = fopen(s1,"r")) == NULL)
{
  fprintf(stderr," cannot open file \n");
  exit();
}
}

/* Read nooftiles.*/
fscanf(fp," %s",s);/* Skip comment string.*/
fscanf(fp," %d",&nooftiles);

    if((facetype =
       (int *)malloc(nooftiles * sizeof(int))) ==
       NULL)
    {fprintf(stderr,"allocation error - aborting\n");
       exit(0);
    }

/* Read the type information. */
fscanf(fp," %s",s);/* Skip comment string.*/
for(i = 0; i < nooftiles; i++){
   fscanf(fp," %d", &l);
   facetype[i] = l;    
}/* end for(i */

/* Read the sizes of the tiles( *facesize).*/
fscanf(fp," %s",s);/* Skip comment string. */
    if((facesize =
       (int *)malloc(nooftiles * sizeof(int))) ==
       NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
        exit(0);
    }
    for( i = 0; i < nooftiles ; i++){
        fscanf(fp," %d",&l);
        facesize[i] = l;  
    }/*endfor */

/* Calculate the array *facebegin.*/
  /* Allocate space for the array. */

    if((facebegin =
       (int *)malloc(nooftiles * sizeof(int))) ==
       NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
        exit(0);
    }

  /* Calculate the array. */

    /* Calculate facebegin.*/
    facebegin[0] = 0;
    for( i = 0; i < nooftiles -1  ; i++){
        facebegin[i+1] = facebegin[i]+facesize[i];
    }/*endfor */
    noofedges = facebegin[nooftiles - 1] + facesize[nooftiles - 1];

/* For each tile read the id and the adjacent tiles.*/
fscanf(fp," %s",s);/* Skip comment string.*/

    /* Allocate space for edges.*/

    if((edges =
       (int *)malloc(noofedges * sizeof(int))) ==
       NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
        exit(0);
    }

    /* Read the edges. */
    for( i = 0; i < nooftiles ; i++){
        /* Read and discard id.*/
        fscanf(fp," %d",&k);

        /* Read the tiles adjacent to the given tile.*/
        j = facesize[i];
        for( k = 0; k < j ; k++){
            fscanf(fp," %d",&l);
            m = facebegin[i]+k;
            edges[m] = l;
        }/*endfor */
    }/*endfor */

fclose(fp);

} /*end Readtilingandsize */

/******************* end Readtilingandsize ********************/

/* Prepforcyclicalg */
/* Description:
 * Since the cycle algorithm uses a different data structure, we
 * need to reformat the tiling files to fit that data structure.
 *
 * The format expected by Cycle is the following:

            <nooftiles>
    <tileid facetype wt facesize edge_adjacency edge_adjacency ...>
    <tileid facetype wt facesize edge_adjacency edge_adjacency ...>
    ...

 * Furthermore, it is expected that the bottom is 0, the top is 1, and
 * that the sides are negative.
 * The sides do not occur as separate tiles. They are referred to only
 * as adjacent tiles by other tiles.

 * We shall implement the rewriting of the file exactly as we
 * implemented rotation except that
(1) strings will be omitted;
(2) the transform and inverse transform will be different;
(3) some of the information will be scrambled so as to fit;
    the format above;
(4) weights will be read in or will be taken to be 1;
(5) tile types will not be changed;

 * Tile numbers other than end tiles will have their ids decremented
 * by 2 since there are two fewer tiles being considered; it is
 * IMPORTANT TO NOTE THIS FOR GEOMETRIC INTERPRETION.

 */

Prepforcyclicalg(ifweights)
    int ifweights;
{   /* loop variables */
    int i,j,k,l,m;
    int *weight;   /* weight[i] is the weight of tile i. */

    /* standard input variable and functions */
    char s[256];
    extern char *s2;
    char s3[] = "temp.opt";
    extern char *gets();
    extern int atoi();

int *transform, *itransform;
int linesize;

FILE *fp;  
FILE *fp2;  

linesize = 8;

/* Calculate transform and itransform. */
if((transform = (int *)malloc(nooftiles * sizeof(int))) == NULL)
  {   fprintf(stderr,"allocation error - aborting\n");
                exit(0); }
if((itransform = (int *)malloc(nooftiles * sizeof(int))) == NULL)
  {   fprintf(stderr,"allocation error - aborting\n");
exit(0); }
transform[0] = 0;
itransform[0 + 2] = 0;
transform[1] = -1;
itransform[-1 + 2] = 1;
transform[2] = 1;
itransform[1 + 2] = 2;
transform[3] = -2;
itransform[-2 + 2] = 3;
for( i = 4; i < nooftiles ; i++){
    transform[i] = i - 2;
    itransform[i - 2 + 2] = i;
}/*endfor */

/* Create and initialize the weights. */
if((weight = (int *)malloc(nooftiles * sizeof(int))) == NULL)
  {   fprintf(stderr,"allocation error - aborting\n");
                exit(0); }
for(i = 0; i < 4; i++){
    weight[i] = 0;
}/* endfor */
for(i = 4; i < nooftiles; i++){
    weight[i] = 1;
}/* endfor */

if ((fp = fopen(s2,"w")) == NULL)
{
  fprintf(stderr," cannot open file \n");
  exit();
}

/* Read in the weights if ifweights == 1. */
if(ifweights == 1){
    if ((fp2 = fopen(s3,"r")) == NULL)
    {
      fprintf(stderr," cannot open file \n");
      exit();
    }

    /* Read the weights. */
    fscanf(fp2," %s",s); /* Skip comment. */
    fscanf(fp2," %d",&k); /* Skip the number of tiles. */
    fscanf(fp2," %s",s); /* Skip comment. */
    for(i = 0; i < nooftiles - 4; i++){
        fscanf(fp2," %d", &k);
        weight[i+4] = k;
    }/* endfor */
fclose(fp2);
}/* endif */

fprintf(fp,"%d\n\n",nooftiles -2);

/* Rewrite tiles. */
    for( i = 0; i < nooftiles-2 ; i++){
fprintf(fp,"%d",i);
fprintf(fp," %d",facetype[itransform[i+ 2]]);
fprintf(fp," %d",weight[i+2]);
fprintf(fp," %d  ",facesize[itransform[i+ 2]]);
j = facebegin[itransform[i + 2]];

/* Print line control. */
m = 3;

for( k = 0; k < facesize[itransform[i + 2]] ; k++){

    /* Print line control. */
    m++;
    if( m == linesize
    ){
m = 0;
fprintf(fp,"\n  ");
    }/*endif */

    l = j + k;
    fprintf(fp," %d", transform[edges[l]]);
}/*endfor */
fprintf(fp,"\n");
    }/*endfor */

fclose(fp);

} /*end Prepforcyclicalg */

/******************* end Prepforcyclicalg ********************/

/* Rotatetiling */
/* Description:
 * The four end tiles are denoted by 0 = bottom, 1 = left, 2 = top,
 * and 3 = right.

 * Rotatetiling renumbers the end tiles. We think of turning the
 * tiling one quarter turn to the left so that what was the left becomes
 * 0 = bottom, what was top becomes 1 = left, what was right becomes
 * 2 = top, and what was bottom becomes 3 = right.

 * In keeping with the principal that we may want to change the nature
 * of the rotation at a later time, we define new values, TRANSFORM0RM0,
 * TRANSFORM1, TRANSFORM2, and TRANSFORM3, for the old values of 0, 1, 2,
 * 3 and these transformed values may simply be redefined at will without
 * changing the rest of the program. There are of course also the
inverse
 * transforms ITRANSFORMi which must match.
 */
#define TRANSFORM0 3
#define TRANSFORM1 0
#define TRANSFORM2 1
#define TRANSFORM3 2
#define ITRANSFORM0 1
#define ITRANSFORM1 2
#define ITRANSFORM2 3
#define ITRANSFORM3 0

Rotatetiling()
{   /* loop variables */
    int i,j,k,l,m;

    /* standard input variable and functions */
    char s[256];
    extern char *s1;
    extern char *gets();
    extern int atoi();

    int *transform, *itransform;
    int linesize;

FILE *fp;  

/* Calculate transform and itransform. */
    if((transform =
       (int *)malloc(nooftiles * sizeof(int))) ==
       NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
exit(0);
    }
    if((itransform =
       (int *)malloc(nooftiles * sizeof(int))) ==
       NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
exit(0);
    }
    transform[0] = TRANSFORM0;
    transform[1] = TRANSFORM1;
    transform[2] = TRANSFORM2;
    transform[3] = TRANSFORM3;
    itransform[0] = ITRANSFORM0;
    itransform[1] = ITRANSFORM1;
    itransform[2] = ITRANSFORM2;
    itransform[3] = ITRANSFORM3;
    for( i = 4; i < nooftiles ; i++){
transform[i] = i;
itransform[i] = i;
    }/*endfor */

if ((fp = fopen(s1,"w")) == NULL)
{
  fprintf(stderr," cannot open file \n");
  exit();
}

/* Print linesize control. */
linesize = 8; /* Print control size to keep file lines from becoming
               * too long. Used in conjunction with a print control
               * loop variable m. */

fprintf(fp,"Number_of_tiles_including_the_four_standard_ends:  \n");
fprintf(fp,"%d\n", nooftiles);

fprintf(fp,"Type_of_each_of_these_tiles: \n");

    /* Print linesize control. */
    m = -1;
    for( i = 0; i < nooftiles ; i++){

/* Print linesize control. */
m++;
if( m == linesize
){
    m = 0;
    fprintf(fp,"\n");
}/*endif */

  fprintf(fp," %d",facetype[i]);   /* The types associated with any
* tile number remains unchanged. */
    }/*endfor */
fprintf(fp,"\n");

fprintf(fp,"Size_of_the_end_tiles_(tiles_0_1_2_3):\n");
/*fprintf(fp,"%d\n",facesize[itransform[0]]);
fprintf(fp,"%d\n",facesize[itransform[1]]);
fprintf(fp,"%d\n",facesize[itransform[2]]);
fprintf(fp,"%d\n",facesize[itransform[3]]); */

m = -1;
for (i = 0; i < nooftiles; i++){
    m++;
    if ( m == linesize){
        m = 0;
        fprintf(fp,"\n");
    }/* endif */
    fprintf(fp," %d", facesize[itransform[i]]);
}/*endfor*/
fprintf(fp,"\n");

/* Write rotated tiles. */
fprintf(fp,"Tile-ids_--_Adjacent_tiles_in_correct_order):\n");
    for( i = 0; i < nooftiles ; i++){
fprintf(fp,"%d",i);
j = facebegin[itransform[i]];

/* Print line control. */
m = -1;

for( k = 0; k < facesize[itransform[i]] ; k++){

    /* Print line control. */
    m++;
    if( m == linesize
    ){
m = 0;
fprintf(fp,"\n  ");
    }/*endif */

    l = j + k;
    fprintf(fp," %d", transform[edges[l]]);
}/*endfor */
fprintf(fp,"\n");
    }/*endfor */
fclose(fp);

} /*end Rotatetiling */

/******************* end Rotatetiling ********************/

/* Writesktilingandsize */
/* Description:
 * Write to file the old information on tiling together with
 * the skinny adjacencies.
 * Write out size information and type information. That is,
 * the size information can be used, if necessary as type information.
 * The resulting file will then have to be modified to be suitable
 * for the cyclic algorithm.
 * Here is the format:

   Number_of_tiles_including_the_four_standard_ends:
   <number>
   Type_of_each_of_these_tiles:
   <numbers (no tile-number id is to beincluded)>
   Size_of_each_of_these_tiles:
   <numbers (no tile-number id is to be included)>
   Tile-ids_--_Adjacent_tiles_in_correct_order:
   <id number ... number>
   <id number ... number>
   ...
   <any number of comments or extra data not to be used by the program>
 */

Writesktilingandsize()
{   /* loop variables */
    int i,j,k,l,m;
    int linesize;

    /* standard input variable and functions */
    char s[256];
    char s2[] = "temp.sk";
    extern char *gets();
    extern int atoi();

FILE *fp;  

linesize = 10;
if ((fp = fopen(s2,"w")) == NULL)
{
  fprintf(stderr," cannot open file \n");
  exit();
}

fprintf(fp,"Number_of_tiles_including_the_four_standard_ends:  \n");
fprintf(fp,"%d\n", nooftiles);
fprintf(fp,"Type_of_each_of_these_tiles: \n");
    m = -1;
    for ( i = 0; i < nooftiles; i++){
        m++;
        if (m == linesize){
            m = 0;
            fprintf(fp,"\n");
        }/*endif */
        fprintf(fp," %d",facetype[i]);   
    }/*endfor */
    fprintf(fp,"\n");
fprintf(fp,"Size_of_each_of_these_tiles: \n");
    m = -1;
    for( i = 0; i < nooftiles ; i++){
        m++;
        if( m == linesize
        ){
            m = 0;
            fprintf(fp,"\n");
        }/*endif */
        j = facesize[i] + noofnewadj[i];
        fprintf(fp," %d",j);
    }/*endfor */
        fprintf(fp," \n");
fprintf(fp,"Tile-ids_--_Adjacent_tiles_in_correct_order:\n");
    for( i = 0; i < nooftiles ; i++){
        fprintf(fp,"%d  ",i);
        j = facebegin[i];
        m = 0;
        for( k = 0; k < facesize[i] ; k++){
            m++;
            if( m == linesize
            ){
                m = 0;
                fprintf(fp,"\n");
            }/*endif */
            l = j + k;
            fprintf(fp," %d", edges[l]);
        }/*endfor */
        for( k = 0; k < noofnewadj[i] ; k++){
            m++;
            if( m == linesize
            ){
                m = 0;
                fprintf(fp,"\n");
            }/*endif */
            fprintf(fp," %d", newadj[i][k]);
        }/*endfor */
        fprintf(fp," \n");
    }/*endfor */
fclose(fp);
} /*end Writesktilingandsize */

/******************* end Writesktilingandsize ********************/


/* Addskinnypathstoold */
/* Description:
 * Saturate the tiling by adding adjacencies across corners.
 */

Addskinnypathstoold()
{   /* loop variables */
    int i,j,k;

    /* standard input variable and functions */
    char s[256];
    extern char *gets();
    extern int atoi();

    /* tile and edge loop variables */
    int t,e;

/* Allocate space for variables. */

    if((noofnewadj =
       (int *)malloc(nooftiles * sizeof(int))) == NULL)
    {   fprintf(stderr,"allocation error - aborting\n"); exit(0); }

    if((newadj =
       (int **)malloc(nooftiles * sizeof(int *))) == NULL)
    {   fprintf(stderr,"allocation error - aborting\n"); exit(0); }
    for( i = 0; i < 4 ; i++){
        if((newadj[i] =
           (int *)malloc(nooftiles * sizeof(int))) == NULL)
        {   fprintf(stderr,"allocation error - aborting\n"); exit(0); }
    }/*endfor */
    for( i = 4; i < nooftiles ; i++){
        if((newadj[i] =
           (int *)malloc(MAXVALENCE * sizeof(int))) == NULL)
        {   fprintf(stderr,"allocation error - aborting\n"); exit(0); }
    }/*endfor */

    if((edgeused =
       (int *)malloc(noofedges * sizeof(int))) == NULL)
    {   fprintf(stderr,"allocation error - aborting\n"); exit(0); }

    if((tilecycle =
       (int *)malloc(MAXCYCLE * sizeof(int))) == NULL)
    {   fprintf(stderr,"allocation error - aborting\n"); exit(0); }

    if((frontedge_cycle =
       (int *)malloc(MAXCYCLE * sizeof(int))) == NULL)
    {   fprintf(stderr,"allocation error - aborting\n"); exit(0); }

    if((backedge_cycle =
       (int *)malloc(MAXCYCLE * sizeof(int))) == NULL)
    {   fprintf(stderr,"allocation error - aborting\n"); exit(0); }

/* Initialize the global variables not initialized by
 * Readtilingandsize. */
    for( i = 0; i < nooftiles ; i++){
        noofnewadj[i] = 0;
    }/*endfor */
    for( i = 0; i < nooftiles ; i++){
            newadj[i][0] = -1;
    }/*endfor */
    for( i = 0; i < noofedges ; i++){
        edgeused[i] = 0;
    }/*endfor */

/* Process each vertex (indicated by oriented edge) provided
 * that that vertex has not already been processed.*/
    for( t = 0; t < nooftiles ; t++){ /* each tile */
        for( e = 0; e < facesize[t] ; e++){ /* each edge of that tile */
            /* Edge not already used?  i == 0*/
            i = edgeused[facebegin[t]+e];
            if( i == 0
            ){
                Buildcycle(t,e);
                Recordcycle();
            }/*endif */
        }/*endfor e = edge no*/
    }/*endfor t = tile no*/

} /*end Addskinnypathstoold */

/******************* end Addskinnypathstoold ********************/

/* edgefromtiletotile */
/* Description:
 * Return the edge number of tile t1 that is adjacent to tile t2
 * corresponding to edge e of tile t2.
 */
int edgefromtiletotile(t1,t2,e)
    int t1,t2,e;
{   /* loop variables */
    int i,j,k;
    /* edge variables to check whether t1 and t2 are incident in more
     * than one adjacent face. */
    int incre,decrj,eplus,jminus;
    i = facebegin[t1];
    j = 0;
    while( edges[i + j] != t2
    ){
        j++;
    }/*endwhile */
    incre = incr(t2,e);
    eplus=0;
    while (
    (edges[facebegin[t2] + incre] == t1)
     &&
    ((t2 > 3) || (incre > 0))
    ){  incre = incr(t2,incre);
         eplus++;
      }
    decrj = decr(t1,j);
    jminus=0;
    while (
    (edges[facebegin[t1] + decrj] == t2)
     &&
    ((t1 > 3) || (decrj < facesize[t1] - 1))
    ){
        decrj = decr(t1,decrj);
        jminus++;
    }
    if (eplus == jminus) {
        k = j;
    }
    if (eplus > jminus) {
        k = j;
        for (i=0; i < (eplus - jminus); i++) {
            k = incr(t1,k);
        }
    }
    if (eplus < jminus) {
        k = j;
        for (i=0; i < (jminus - eplus); i++) {
            k = decr(t1,k);
        }
    }
    return k;

} /*end edgefromtiletotile */

/******************* end edgefromtiletotile ********************/

/* Buildcycle */
/* Description:
 */
Buildcycle(t,e) /* t = tile, e = edge */
    int t,e;
{   /* loop variables */
    int i,j,k;
    char s[256];

/* Initialize the cycle information. */
    cyclelength = 0;
    tilecycle[cyclelength] = t;
    backedge_cycle[cyclelength] = e;
    edgeused[facebegin[t]+e] = 1;

/* Add tiles to the cycle until the first tile or an edge tile
 * is reached. */
    do {
        cyclelength++;

        /* Calculate adjacent tile across backedge.*/
         tilecycle[cyclelength] =
            edges[facebegin[tilecycle[cyclelength - 1]] +
            backedge_cycle[cyclelength - 1]];

        /* If adjacent tile is not the ending tile...*/
        if(
            (tilecycle[cyclelength] > 3)
            &&
            (tilecycle[cyclelength] != tilecycle[0] )
        ){
            /* Calculate frontedge (adjacent to previous tile).*/
            frontedge_cycle[cyclelength] =
                edgefromtiletotile(tilecycle[cyclelength],
                   tilecycle[cyclelength-1], backedge_cycle[cyclelength - 1]);

            /* Calculate backedge (clockwise around tile). */
            backedge_cycle[cyclelength] =
                incr(tilecycle[cyclelength],
                   frontedge_cycle[cyclelength]);

            /* Mark each backedge as it is used. */
            edgeused[facebegin[tilecycle[cyclelength]]+
                backedge_cycle[cyclelength]] = 1;
        }/*endif */

    }while(
            (tilecycle[cyclelength] > 3)
            &&
            (tilecycle[cyclelength] != tilecycle[0] )
 ); /*enddo */

    cyclelength++;

} /*end Buildcycle */

/******************* end Buildcycle ********************/

/* Recordcycle */
/* Description:
 * Use tilecycle as a list to be used in searching for new
 * (that is, corner) adjacencies. When a new adjacency is
 * found, record it in *noofnewadj and in **newadj.
 */
Recordcycle()
{   /* loop variables */
    int i,j,k;
    int oldadjacency;
    char s[256];
    int t1,t2;

    int bgn, size;

for( i = 0; i < cyclelength ; i++){ /* for each element of *tilecyle..*/
    if( tilecycle[i] > 3            /* If the tile is internal... */
    ){
        for( j = 0; j < cyclelength ; j++){
            oldadjacency = 0;
            t1=tilecycle[i];
            t2=tilecycle[j];
            if( t1 == t2
            ){
                continue;
            }/*endif */

                /* Search the original adjacencies.*/
                bgn=facebegin[t1];
                size=facesize[t1];
                for( k = 0; k < size ; k++){
                    if( edges[bgn + k] == t2
                    ){
                    oldadjacency = 1;
                    break;
                    }/*endif */
                }/*endfor k*/

                /* If necessary, search the newadjacencies. */
                if( oldadjacency == 0
                ){
                    k = 0;
                    while(
                        ( newadj[t1][k] != t2)
                        &&
                        ( newadj[t1][k] >= 0)
                    ){
                    k++;
                    }/*endwhile */
                   if( newadj[t1][k] < 0 /* new adjacency found */
                    ){
                        /* Record in newadj[t1]. */
                        newadj[t1][k] = t2;
                        newadj[t1][k+1] = -1;
                        noofnewadj[t1]++;

                        /* Record in newadj[t2]. */
                        newadj[t2][noofnewadj[t2]] = t1;
                        newadj[t2][noofnewadj[t2]+1] = -1;
                        noofnewadj[t2]++;
                    }/*endif */
                }/*endif */

        }/*endfor j*/


    }/*endif tile is internal*/
}/*endfor i: for each element of *tilecycle..*/

} /*end Recordcycle */

/******************* end Recordcycle ********************/


/* incr */
/* Description:
 * Return the next edge number in the clockwise direction.
 */
int incr(t,e)
    int t,e;
{   /* loop variables */
    int i,j,k;

    i = e+1;
    if( i == facesize[t]
    ){
        i = 0;
    }/*endif */

    return i;

} /*end incr */

/******************* end incr ********************/

/* decr */
/* Description:
 * Return the previous edge number in the clockwise direction.
 */
int decr(t,e)
    int t,e;
{   /* loop variables */
    int i,j,k;

    i = e-1;
    if( i == -1
    ){
        i = facesize[t] - 1;
    }/*endif*/

    return i;
} /* end decr */

/******************* end decr ********************/

/* Readweights */
/* Description:
 * The text portions of the format are 1-string comments that must appear
 * in the file.  The comments are read and discarded by fscanf as a single
 * string.  The content of the comment lines is only to help those writing
 * input files.  Here is the format.

   Number_of_tiles_not_including_the_four_standard_ends.
   <number>
   Weight_of_each_tile.
   <number ... number>
   Distance_to_bottom_from_each_tile.
   <number ... number>
   Distance_to_left_side_from_each_tile.
   <number ... number>
 */

Readweights()
{   /* loop variables */
    int i,j,k,l,m;

    /* standard input variable and functions */
    char s[256];
    char s1[] = "temp.opt";
    extern char *gets();
    extern int atoi();

FILE *fp;  

if ((fp = fopen(s1,"r")) == NULL)
{
  fprintf(stderr," cannot open file \n");
  exit();
}

/* Read nooftiles.*/
fscanf(fp," %s",s);/* Skip comment string.*/
fscanf(fp," %d",&nooftiles);

/* Allocate space for weight, botdist, and leftdist. */
if((weight =
  (float *)malloc(nooftiles * sizeof(int))) ==
  NULL){
  fprintf(stderr,"allocation error - aborting\n");
  exit(0);
}
if((botdist =
  (float *)malloc(nooftiles * sizeof(int))) ==
  NULL){
  fprintf(stderr,"allocation error - aborting\n");
  exit(0);
}
if((leftdist =
  (float *)malloc(nooftiles * sizeof(int))) ==
  NULL){
  fprintf(stderr,"allocation error - aborting\n");
  exit(0);
}

/* Read the weights. */
fscanf(fp," %s",s);/* Skip comment string.*/
for( i = 0; i < nooftiles ; i++){
   fscanf(fp," %d",&l);
   weight[i] = l;
}/* endfor */

/* Read the distances from the bottom. */
fscanf(fp," %s",s);/* Skip comment string.*/
for( i = 0; i < nooftiles ; i++){
   fscanf(fp," %d",&l);
   botdist[i] = l;
}/* endfor */

/* Read the distances from the left side. */
fscanf(fp," %s",s);/* Skip comment string.*/
for( i = 0; i < nooftiles ; i++){
   fscanf(fp," %d",&l);
   leftdist[i] = l;
}/* endfor */

fclose(fp);

} /*end Readweights */

/******************* end Readweights ********************/

/* Printtofile */
/* Description:
 */

Printtofile()
{   /* loop variables */
    int i,j,k,l,m;
    float r;

/* Variables computing the amount to scale. */
    float maxheight, maxwidth;
    float scale;

    /* standard input variable and functions */
    char s[256];
    extern char *gets();
    extern int atoi();

FILE *fp;  

/* Compute the maximum height. */
maxheight = 0.0; /* Initialize maxheight. */
for(i = 0; i < nooftiles; i++){
   r = weight[i] + botdist[i];
   if(r > maxheight){maxheight = r;}
}/* end for(i */

/* Compute the maximum circumference. */
maxwidth = 0.0; /* Initialize maxwidth. */
for(i = 0; i < nooftiles; i++){
   r = weight[i] + leftdist[i];
   if(r > maxwidth){maxwidth = r;}
}/* end for(i */

/* Compute the maximum of height/700 and circumference/500. */
if(( XMAX - XMIN )* maxheight < (YMAX - YMIN) * maxwidth){
  scale = (XMAX - XMIN) / maxwidth;
  }else{
  scale = (YMAX - YMIN) / maxheight;
}/* end if(( */

/* Scale weight, botdist, and leftdist; translate botdist and leftdist. */
for(i = 0; i < nooftiles; i++){
   weight[i] = scale * weight[i];
   botdist[i] = YMIN + (scale * botdist[i]);
   leftdist[i] = XMIN + (scale * leftdist[i]);
}/* end for(i */

/* Open a file for printing. */
fprintf(stderr," Write which postscript file? \n");
fprintf(stderr,"\n");
gets(s);
if ((fp = fopen(s,"w")) == NULL)
{
  fprintf(stderr," cannot open file \n");
  exit();
}

/* Print the header for the file. */
fprintf(fp, "%%!PS\n");

/* Print the bounding box for the file. */
fprintf(fp, "%%%%BoundingBox: 50 50 ");
fprintf(fp, "%.0f ",YMIN + scale*(maxwidth));
fprintf(fp, "%.0f\n",XMIN + scale*(maxheight));

/* Print a square for each tile with nonzero weight. */
for(i = 0; i < nooftiles; i++){
     fprintf(fp, "newpath\n");
     fprintf(fp, " %.1f %.1f moveto\n",leftdist[i], botdist[i]);
     fprintf(fp, " %.1f %.1f rlineto ", 0.0, weight[i]);
     fprintf(fp, " %.1f %.1f rlineto ", weight[i], 0.0);
     fprintf(fp, " %.1f %.1f rlineto ", 0.0, - weight[i]);
     fprintf(fp, " %.1f %.1f rlineto\n", - weight[i], 0.0);
     fprintf(fp, "closepath\n");
     fprintf(fp, "stroke\n");
}/* end for(i */

/* Print the footer of the file. */
fprintf(fp,"showpage\n");

fclose(fp);

}/* end printtofile */

/******************* end printtofile ********************/

/* Init(tiling) */
/* Description:
 * Initialize the tiling.
 */
Init(tiling)
    struct tile *tiling;
{   /* loop variables */
    int i,j,k;
    for( i=0; i<TILINGMAX ; i++){
if(  ((tiling+i)->edge)!= NULL
){
    free((tiling+i)->edge);
}/*endif */
    }/*endfor */
    for( i=0; i<TILINGMAX ; i++){
(tiling + i) -> type = 0;
(tiling + i) -> size = 0;
for( j = 0; j < 3 ; j++){
    (tiling + i) -> wt[j] = 0;
}/*endfor */
(tiling + i) -> wtsum = 0;
(tiling + i) -> edge = NULL;
    }/*endfor */

} /*end Init(tiling) */

/******************* end Init(tiling) ********************/

/* Description:
 * Enter tiling from file into memory.
 */
Readfromfile(tiling,tilinglength)
    struct tile * tiling;
    int * tilinglength;
{   int i,j,k,l, *m;
    extern FILE *fp, *fopen();
    extern char t[30];
    extern char *s2;

    /* standard input variable and functions */
    char s[30];
    
    extern char *gets();
    extern int atoi();

    /* Initialize tiling and file */
    Init(tiling);

if( fp != NULL
        ){
    fclose(fp);
    fp = NULL;
}/*endif */

strcpy(t,s2);
if((fp = fopen(s2,"r") )== NULL
){
    fprintf(stderr,"Cannot open file for Readfromfile.\n");
}/*endif */

    if( fp != NULL
    ){
fscanf(fp," %d",tilinglength); /* tilinglength is a pointer */
j = *tilinglength;

for( i=0; i<j ; i++){
    /* read and discard tile number */
            fscanf(fp," %d",&k);
    /* read type number */
            fscanf(fp," %d",&k);
    (tiling + i) -> type = k;
    /* read wt and size */
            fscanf(fp," %d",&k);
    (tiling + i) -> wt[0] = k;
            fscanf(fp," %d",&k);
    (tiling + i) -> size = k;

    /* allocate space for the edges */
    if( k > 0
    ){ /* allocate space for the edge pointer */
l = k * sizeof(int);
if(
    (   ( (tiling + i) -> edge) = (int *)malloc(l) )
    == NULL
){
    fprintf(stderr," Allocation error. Aborting. \n");
    exit(0);
}/*endif */
    }/*endif */

    /* read the edges */
    for( l=0; l<k ; l++){
m =  ((tiling + i)->edge)+l;
fscanf(fp," %d",m);
    }/*endfor */

}/*endfor */
    }/*endif */
    else{
fprintf(stderr,"fp = NULL \n");
    }/*endelse */
    if( fp != NULL
    ){
fclose(fp);
fp = NULL;
    }/*endif */

} /*end Readfromfile(tiling,tilinglength)*/

/********************************************************/

/* Description:
 * Write weights and integrated fat distances  into file.
 */
Writefordiv(tiling,tilinglength)
    struct tile * tiling;
    int * tilinglength;
{   int i,j,k,m;
    extern FILE *fp;
    int linesize;

    /* standard input variable and functions */
    char s[30];
    char s1[] = "temp.opt";
    extern char *gets();
    extern int atoi();

if( fp != NULL
        ){
    fclose(fp);
    fp = NULL;
}/*endif */
if((fp = fopen(s1,"w") )== NULL
){
    fprintf(stderr,"Cannot open temp.opt for writing fat info.\n");
}/*endif */

    /* Enter tiling length as first entry in file. */
    fprintf(fp,"Number_of_tiles_not_including_the_four_standard_ends.\n");
    j = *tilinglength;
    m = j - 2;
    fprintf(fp," %d \n",m);

linesize = 8;
m = 0;
fprintf(fp,"Weight_of_each_tile.\n");
for(i = 2; i < j; i++){
m++;
if (m == linesize){
   m = 0;
   fprintf(fp,"\n");
}/* endif */
fprintf(fp," %d",(tiling + i)->wt[2]);
}
fprintf(fp," \n");

fprintf(fp,"Distance_to_bottom_from_each_tile.\n");
m = 0;
for( i=2; i<j ; i++){
   m++;
   if (m == linesize ){
      m=0;
      fprintf(fp,"\n");
   }/* endif */
   k = (tiling + i)->wtsum - (tiling + i)->wt[2];
fprintf(fp," %d",k);
    }/*endfor */
fprintf(fp," \n");

    if( fp != NULL
    ){
fclose(fp);
fp = NULL;
    }/*endif */

} /*end Writefordiv(tiling,tilinglength) */

/********************************************************/

/* Description:
 * Append integrated skinny distances into file.
 */
Appendfordiv(tiling,tilinglength)
     struct tile * tiling;
     int * tilinglength;
{    int i,j,k,m;
     extern FILE *fp;
     int linesize;

     /* standard input variables and functions */
     char s[30];
     char s1[] = "temp.opt";
     extern char *gets();
     extern int atoi();

     if(  fp != NULL
              ){
          fclose(fp);
          fp = NULL;
     }/*endif */
     if((fp = fopen(s1,"a") ) == NULL
     ){
          fprintf(stderr,"Cannot open filefor Appendfordiv. \n");
     }/* endif */
   
     Integrate(tiling,tilinglength,0);
     linesize = 8;
     m = 0;
     j = *tilinglength;
     fprintf(fp,"Distance_to_left_side_from_each_tile.\n");
     for( i=2; i<j; i++){
        m++;
        if (m == linesize){
          m=0;
          fprintf(fp,"\n");
        }/* endif */
        k = (tiling + i)->wtsum - (tiling + i)->wt[0];
        fprintf(fp," %d", k);
     }/* endfor */
     fprintf(fp," \n");
     
     if( fp != NULL
     ){
          fclose(fp);
          fp = NULL;
     }/* endif */

}/* end Appendfordiv(tiling,tilinglength) */

/**********************************************************/

/* Cycle() */
/* Description:
 * Accumulate paths and test for optimality through
 * one cycle.
 */
Cycle(tiling,tilinglength,cyclebegin,automatic)
    struct tile * tiling;
    int * tilinglength,*cyclebegin,automatic;
{   /* loop variables */
    int i,j,k,gcd;
    int pathtotal,* pathtotalptr,
cyclelength,success, * successptr,
iteration,wtno,cyclesneeded;

    /* standard input variable and functions */
    char s[15];
    extern char *gets();
    extern int atoi();

/* initialize */
    cyclesneeded = 0;
    /* set wt[2] = wt[1] = 0 */
    for( i = 0; i < *tilinglength ; i++){
(tiling + i) -> wt[1] = 0;
(tiling + i) -> wt[2] = 0;
    }/*endfor */
    /* set pathtotal = 0 */
    pathtotal = 0;
    pathtotalptr = &pathtotal;
    /* determine cycle length */
    if( automatic == 1
    ){
if( *cyclebegin > 0
){
    cyclelength = *cyclebegin;
}/*endif */
else{
    cyclelength = 1;
}/*endelse */
    }/*endif */
    else{
fprintf(stderr,"\n");
fprintf(stderr,"Enter how many cycles you want to run for the ");
fprintf(stderr,"cyclic algorithm.\n");
fprintf(stderr,"10,000 should be sufficient for ");
fprintf(stderr,"tilings with fewer than 10,000 tiles,\n");
fprintf(stderr,"but you may need more cycles for larger tilings. ");
fprintf(stderr,"This is the\n");
fprintf(stderr,"time consuming part of the program.\n");
fprintf(stderr,"\n");
gets(s);
cyclelength = atoi(s);
fprintf(stderr,"\n");
    }/*endelse */
    /* set success = 0 */
    success = 0;
    successptr = & success;

/* for each iteration in the cycle */
for( iteration = 0; iteration < cyclelength ; iteration++){
    cyclesneeded++;
    /* integrate wt[0] */
    Integrate(tiling,tilinglength,0);
    /* determine addition and accumulate pathtotal */
    /* enter addition into wt[1] and add to wt[0]
     * and wt[2] */
    Add(tiling,tilinglength,pathtotalptr);
    /* integrate wt[2] */
    Integrate(tiling,tilinglength,2);
    /* check for optimality of wt[2] */
    /* if successful, mark success and break */
    Optimality(tiling,tilinglength,pathtotal,successptr,
cyclesneeded,cyclebegin);
    if( success == 1
    ){
break;
    }/*endif */
}/*endfor */

/* print out either "failure" or optimal wt function */
*cyclebegin = *cyclebegin + cyclesneeded;
if( success == 1
){
    return 1;
}/*endif */
else{
    return 0;
}/*endelse */

} /*end Cycle() */

/************ end Cycle() *******/

/* Integrate(tiling,tilinglength,wtno) */
/* Description:
 * Find which tiles represent the two ends of the tiling.
 * Starting at the 0 end, add up the weights along minimal
 * paths to determine the wtsum or integrated weights.
 */

Integrate(tiling,tilinglength,wtno)
    struct tile *tiling;
    int * tilinglength;
    int wtno;
{
    /* list structures and variables */
    struct treenode *rootnode,*leftnode,*treechaser;
    struct queuenode *queuechaser;
    int tilechaser,tilechecker;
    int offset,size,weight;

    /* loop variables */
    int i,j,k;

    /* tiles pointing to the two ends of the tiling */
    int tileoffset0, tileoffset1;

    /* standard input variable and functions */
    char s[30];
    extern char *gets();
    extern int atoi();

    /* Check that *tilinglength is in range. */
    if( *tilinglength < 1
    ){
return 0;
    }/*endif */
    if( *tilinglength > TILINGMAX
    ){
return 0;
    }/*endif */

    /* Check that wtno is in range. */
    if(
            (wtno != 0 )
            &&
            (wtno != 2 )
    ){
return 0;
    }/*endif */

    /* Initialize all of the weight sums at -1. */
    for( i=0; i< * tilinglength ; i++){
(tiling + i) -> wtsum = -1;
    }/*endfor */

    /* Determine the beginning and ending tiles. */
    tileoffset0 = 0;
    tileoffset1 = 1;

    /* Enter wtsum 0 into the tree list of wtsums. */
    if( (rootnode=(struct treenode *)malloc(sizeof(struct treenode)))
==NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
exit(0);
    }
    rootnode -> parent = NULL;
    rootnode -> lchild = NULL;
    rootnode -> rchild = NULL;
    rootnode -> firstqueuenode = NULL;
    rootnode -> lastqueuenode = NULL;
    rootnode -> wtsum = 0;
    leftnode = rootnode;

    /* Enter tile0 in the queue under weight 0. */
    if( ((rootnode -> firstqueuenode)
    =(struct queuenode *)malloc(sizeof(struct queuenode))) ==NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
exit(0);
    }
    rootnode -> lastqueuenode = rootnode -> firstqueuenode;
    rootnode -> firstqueuenode -> nextqueuenode = NULL;
    rootnode -> firstqueuenode -> tileoffset = tileoffset0;
    (tiling + tileoffset0) -> wtsum = 0;

    /* While the tree of lists is not empty, process the
     * next entry.*/

    /* Find the next offset entry and set tilechaser = that entry. */
    while( (treechaser = leftnode) != NULL
    ){

    while( (queuechaser = treechaser -> firstqueuenode) != NULL
    ){
    tilechaser = queuechaser -> tileoffset;

    /* Process each of the pointers of tilechaser.*/
    size = (tiling + tilechaser) -> size;
    for( i=0; i<size ; i++){
tilechecker = (tiling + tilechaser) -> edge[i];
if( tilechecker < 0
){
    continue;
}/*endif */
/* Has a pointer already been used?
 * If not, use it and enter it in the tree list.
 * If it has been used, ignore it.*/
if( (tiling + tilechecker) -> wtsum == -1
){
    weight = (tiling + tilechecker) -> wt[wtno]
        + (tiling + tilechaser) -> wtsum;
    (tiling + tilechecker) -> wtsum = weight;
    if( tilechecker != tileoffset1
    ){
Enterintree(rootnode,weight,tilechecker);
    }/*endif */
}/*endif */
    }/*endfor i < size */

    /* Shorten the queue. */
    if(
treechaser -> firstqueuenode -> nextqueuenode != NULL
    ){
treechaser -> firstqueuenode =
    treechaser -> firstqueuenode -> nextqueuenode;
    }/*endif */
    else{
treechaser -> firstqueuenode = NULL;		
    }/*endelse */
    free(queuechaser);
    }/*endwhile queuechaser != NULL */

    /* Move leftnode and  free treechaser. */
    if( treechaser -> rchild != NULL
    ){
if( treechaser -> parent != NULL
){
    treechaser -> rchild -> parent = treechaser -> parent;
    treechaser -> parent -> lchild = treechaser -> rchild;
    leftnode = treechaser -> rchild;
    free(treechaser);
    treechaser = NULL;
}/*endif */
else{
    rootnode = treechaser -> rchild;
    rootnode -> parent = NULL;
    leftnode = rootnode;
    free(treechaser);
    treechaser = NULL;
}/*endelse */
while( leftnode -> lchild != NULL
){
    leftnode = leftnode -> lchild;
}/*endwhile */
    }/*endif */
    else{  /* treechaser -> rchild == NULL */
if( treechaser -> parent != NULL
){
    leftnode = leftnode -> parent;
    free(treechaser);
    treechaser = NULL;
}/*endif */
else{
    rootnode = NULL;
    leftnode = NULL;
    free(treechaser);
    treechaser = NULL;
}/*endelse */
    }/*endelse */
    }/*endwhile treechaser != NULL*/

} /*end Integrate(tiling,tilinglength,wtno) */

/**** end Integrate(tiling,tilinglength,wtno) ********/

/* Enterintree() */
/* Description:
 * The wtsum of a tile has just been determined.
 * Enter this tile (its offset == tilechecker) into the list.
 * The first step is to find the proper list in which to enter
 * this offset.  First search the tree to see if that wtsum
 * already has been entered.  If so, then add the offset to
 * the already existing queue under that wtsum.
 * If that wtsum does not already exist, make a new entry,
 * then begin a new queue into which to enter the offset.
 */
Enterintree(rootnode,weight,tilechecker)
    struct treenode *rootnode;
    int weight,tilechecker;
{   /* loop variables */
    int i,j,k,done;
    struct treenode *treechaser;

    /* standard input variable and functions */
    char s[15];
    extern char *gets();
    extern int atoi();

    done = 0;
    treechaser = rootnode;
    while( done == 0
    ){
if( weight < treechaser -> wtsum
){
    if( treechaser -> lchild != NULL
    ){
treechaser = treechaser -> lchild;
    }/*endif */
    else{

    /* make a new entry */
    if( (treechaser -> lchild =
    (struct treenode *)malloc(sizeof(struct treenode))) ==NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
exit(0);
    }
    treechaser -> lchild -> parent = treechaser;
    treechaser = treechaser -> lchild;
    treechaser -> lchild = NULL;
    treechaser -> rchild = NULL;
    treechaser -> wtsum = weight;
    if( (treechaser -> firstqueuenode =
    (struct queuenode *)malloc(sizeof(struct queuenode))) ==NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
exit(0);
    }
    treechaser -> lastqueuenode = treechaser -> firstqueuenode;
    treechaser -> firstqueuenode -> nextqueuenode = NULL;
    treechaser -> firstqueuenode -> tileoffset = tilechecker;
    done = 1;
    /* end of new entry */

    }/*endelse */
}/*endif */
else if ( treechaser -> wtsum < weight
){
    if( treechaser -> rchild != NULL
    ){
treechaser = treechaser -> rchild;
    }/*endif */
    else{

    /* make a new entry */
    if( (treechaser -> rchild =
    (struct treenode *)malloc(sizeof(struct treenode))) ==NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
exit(0);
    }
    treechaser -> rchild -> parent = treechaser;
    treechaser = treechaser -> rchild;
    treechaser -> lchild = NULL;
    treechaser -> rchild = NULL;
    treechaser -> wtsum = weight;
    if( (treechaser -> firstqueuenode =
    (struct queuenode *)malloc(sizeof(struct queuenode))) ==NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
exit(0);
    }
    treechaser -> lastqueuenode = treechaser -> firstqueuenode;
    treechaser -> firstqueuenode -> nextqueuenode = NULL;
    treechaser -> firstqueuenode -> tileoffset = tilechecker;
    done = 1;
    /* end of new entry */

    }/*endelse */
}/*endelse */
else{  /* weight == treechaser -> wtsum*/

    /* append tilechecker to the already existent queue */
    if( (treechaser -> lastqueuenode -> nextqueuenode =
    (struct queuenode *)malloc(sizeof(struct queuenode))) ==NULL)
    {   fprintf(stderr,"allocation error - aborting\n");
exit(0);
    }
    treechaser -> lastqueuenode = treechaser -> lastqueuenode ->
nextqueuenode;
    treechaser -> lastqueuenode -> nextqueuenode = NULL;
    treechaser -> lastqueuenode -> tileoffset = tilechecker;
    done = 1;
    /* end of append */

}/*endelse */
    }/*endwhile */

} /*end Enterintree(rootnode,weight,tilechecker) */

/********* end Enterintree(rootnode,weight,tilechecker) ******/

/* Add(tiling,tilinglength,pathtotalptr) */
/* Description:
 * For each tile pointed to by the 1 end,
 * check to see whether it is in a minimal path.  If so, find
 * such a minimal path and add it to the
 * three weight functions.
 */

Add(tiling,tilinglength,pathtotalptr)
    struct tile *tiling;
    int * tilinglength;
    int * pathtotalptr;
{   /* loop variables */
    int i,j,k;
    int noofpaths,path,pathchaser,tilechecker,
nextwtsum,newwtsum,minimallength,checkersize;
    struct tile *pathpointer;
    int addition[TILINGMAX];

    /* standard input variable and functions */
    char s[15];
    extern char *gets();
    extern int atoi();

/* Initialize addition */
for( i = 2; i < *tilinglength  ; i++){
    addition[i] = 0;
}/*endfor */

/* Initialize wt[1] = 0 */
    for( i=2; i < *tilinglength ; i++){
(tiling + i) -> wt[1] = 0;
    }/*endfor */

/* Find number of paths and check each path. */
pathpointer = tiling + 1;
noofpaths = pathpointer -> size;
minimallength = pathpointer -> wtsum;
for( path = 0; path < noofpaths ; path++){
    pathchaser = (tiling + 1) -> edge[path];
    if( pathchaser < 0
    ){
	continue;
    }/*endif */
    /* determine whether the path is minimal */
    if((tiling + pathchaser)-> wtsum == minimallength
    ){
if(pathchaser != 0
){
    *pathtotalptr = *pathtotalptr + 1;
}/*endif */
while( pathchaser != 0
){
    addition[pathchaser] = addition[pathchaser] + 1;
    nextwtsum = (tiling + pathchaser) -> wtsum -
(tiling + pathchaser) -> wt[0];

    checkersize = (tiling + pathchaser) -> size;
    for( i = 0; i < checkersize ;
    i++){
tilechecker = (tiling + pathchaser) ->edge[i];
if( tilechecker < 0
){
    continue;
}/*endif */
newwtsum = (tiling + tilechecker) -> wtsum;
if( newwtsum == nextwtsum
){
   pathchaser = tilechecker;
   break;
}/*endif */
    }/*endfor */
}/*endwhile */
    }/*endif */
}/*endfor */

for( i = 2; i < *tilinglength ; i++){
    (tiling + i) -> wt[0] =
        (tiling + i) -> wt[0] + addition[i];
    (tiling + i) -> wt[1] =
        (tiling + i) -> wt[1] + addition[i];
    (tiling + i) -> wt[2] =
        (tiling + i) -> wt[2] + addition[i];
}/*endfor */

} /*end Add(tiling,tilinglength) */

/**************** end Add(tiling,tilinglength) ********/

/* Optimality(tiling,tilinglength,pathtotal,successptr) */
/* Description:
 *
 */

Optimality(tiling,tilinglength,pathtotal,successptr,
    cyclesneeded,cyclebegin)
    struct tile * tiling;
    int * tilinglength;
    int pathtotal,cyclesneeded, *cyclebegin;
    int * successptr;
{   /* loop variables */
    int i,j,k;
    int area, height,gcd;
    extern int AREA, HEIGHT, GCD;

    /* standard input variable and functions */
    char s[15];
    extern char *gets();
    extern int atoi();
    extern char t[30];
    extern FILE *fp;

    /* Calculate the area of wt[2].*/
    area = 0;
    for( i = 2; i < *tilinglength ; i++){
j = (tiling + i) -> wt[2];
area = area + j * j;
    AREA = area;
    }/*endfor */

    /* Calculate the height of wt[2].*/
    height = (tiling + 1) -> wtsum;
    HEIGHT = height;

    /* Check whether area == pathtotal * height. */
    if( area == pathtotal * height
    ){
*successptr = 1;
    }/*endif */

    if( *successptr == 1
    ){
gcd = Calcgcd(tiling,tilinglength);
GCD = gcd;
if( fp != NULL
){
    fclose(fp);
    fp = NULL;
}/*endif */
if((fp = fopen(t,"a") )== NULL
){
    fprintf(stderr,"Cannot open file in Optimality.\n");
    return gcd;
}/*endif */

if( gcd == 0
){
    gcd = 1;
}/*endif */
j = 0;
for( i=2; i < *tilinglength ; i++){
    if( gcd == 0
    ){
gcd = 1;
    }/*endif */
    j++;
    if( j == 8
    ){
j = 0;
    }/*endif */
}/*endfor */
j = 0;
for( i=2; i < *tilinglength ; i++){
    fprintf(fp," %d", (tiling + i) -> wt[2]/gcd);
    j++;
    if( j == 8
    ){
j = 0;
fprintf(fp," \n");
    }/*endif */
}/*endfor */
fprintf(fp,"\n");
fprintf(fp," Cyclesneeded == %d ", cyclesneeded);
fprintf(fp," beginning at %d .\n", *cyclebegin);
fclose(fp);
fp = NULL;
return gcd;
    }/*endif */


} /*end Optimality() */

/*************** end Optimality() *************/

/* Calcgcd() */
/* Description:
 * Return the gcd of the entries in wt[2].
 */

Calcgcd(tiling,tilinglength)
    struct tile * tiling;
    int * tilinglength;
{   /* loop variables */
    int i,j,k;
    int a,b;

    /* standard input variable and functions */
    char s[15];
    extern char *gets();
    extern int atoi();

    a = 0;
    for( i = 0; i < *tilinglength ; i++){
b = (tiling + i)->wt[2];
a = Gcd(a,b);
    }/*endfor */
    return a;

} /*end Calcgcd() */

/******************* end Calcgcd() ********************/

/* Gcd() */
/* Description:
 * Returns 0 if both a and b are 0.
 * Otherwise returns the standard gcd of a and b.
 */

Gcd(a,b)
    int a,b;
{   /* loop variables */
    int i,j,k;

    /* standard input variable and functions */
    char s[15];
    extern char *gets();
    extern int atoi();

    int c;

    /* Replace a and b by absolute values. */
    if( a < 0
    ){
a = -a;
    }/*endif */
    if( b < 0
    ){
b = -b;
    }/*endif */

    /* Interchange a and b so that a is smaller. */
    if( b < a
    ){
c = b;
b = a;
a = c;
    }/*endif */

    /* If a == 0, return b. */
    if( a == 0
    ){
return b;
    }/*endif */

    /* Cycle through division, replacing one of entries
     * by remainder of division. */
    while( a != 0
    ){
c = b%a;
b = a;
a = c;
if( a == 0
){
    return b;
}/*endif */
    }/*endwhile */

} /*end Gcd() */

/******************* end Gcd() ********************/