/*
 * Copyright (c) 1992, The Geometry Center
 *                     University of Minnesota 
 *                     1300 South Second Street
 *                     Minneapolis, MN  55454
 *
 * email address: software@geom.umn.edu
 *
 * This software is copyrighted as noted above.  It may be freely copied,
 * modified, and redistributed, provided that the copyright notice is
 * preserved on all copies.
 *
 * There is no warranty or other guarantee of fitness for this software,
 * it is provided solely "as is".  Bug reports or fixes may be sent
 * to the authors, who may or may not act on them as they desire.
 *
 * You may not include this software in a program or other software product
 * without supplying the source, or without informing the end-user that the
 * source is available for no extra charge.
 *
 * If you modify this software, you should include a notice giving the
 * name of the person performing the modification, the date of modification,
 * and the reason for such modification.
 *
 *     The National Science and Technology Research Center for
 *      Computation and Visualization of Geometric Structures
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "link.h"
#import <zone.h>
#import <mach.h>

#define KEYWORDSIZE	24

#ifdef CRAY
#define EOF	255
#endif

/*
#define DEBUG
*/


#define	perror(s1,s2)	fprintf(stderr,"Error in %s: %s\n",s1,s2)

	static link *linkptr = NULL;

	static char o_u_label[2][10] = { "over", "under"};
	static char r_l_label[2][10] = { "right", "left"};
	static char tf[2][4] = { "no", "yes"};
        static short nstrnd_included = 0;

static int newdirtable[2][4] = {
	P0, N0, P0, N0,
	P1, N1, P1, N1};

char *
getquote(fp, cptr)
FILE *fp;
char *cptr;
{
	int i = 0;
 	char *lbl;
 	char *pc;
  	int p0, p1;

   	pc = cptr;
	while ( (*pc = getc(fp)) != '"') 
	    {if (*pc == '%') {
		fprintf(stderr,"Invalid line in linkfile\n");
		return((char *)NULL);
		}
	    pc++; ++i;}

	p0 = i+1;
	pc++;
	i++;
	while ( (*pc = getc(fp)) != '"') 
	    {if (*pc == '%') {
		fprintf(stderr,"Invalid line in linkfile\n");
		return((char *)NULL);
		}
	    pc++; ++i;}
	p1 = i;

	lbl = (char *) malloc(p1 - p0 + 1);
	strncpy(lbl, cptr+p0, p1-p0);
	*(lbl + (p1-p0)) = '\0';
	return(lbl);
}

void complete_processing(link *linkptr, short tangle)
{
    int i, done, dir, dir0, dir1;
    int nstrands = 0;
    crossing *xingptr = linkptr->xinglist, *xing0, *xing1;
    int didStartWithLooseEnd;

    for (i=0; i<linkptr->nxings; ++i, xingptr = xingptr->next)
	xingptr->markedge = 0;
    dir = N0;
    nstrands = 0;
    if (tangle)                /* process ends of tangle */
      {
	for (xingptr = linkptr->xinglist, i=0; i<4; i++, xingptr = NEXTXING(xingptr))
	  {
	    if (xingptr->orient != TERMINUS)    /* the strand points into the tangle */
	      {
		linkptr->strandlist[nstrands] = xingptr;
		linkptr->dirlist[nstrands] = N0;
		xingptr->markedge |= 1<<N0;
		xingptr->markedge |= 1<<N1;
		xingptr->markedge |= 1<<P1;
		xingptr->markedge |= 1<<P0;
		xing1 = xingptr;
		dir = N0;
		while (xing1->orient != TERMINUS)   /* traverse until reaches opposite end */
		  {
		    xing1->markedge |= 1<<dir;
		    xing0 = xing1->nhbr[dir];
		    dir = newdirtable[xing1->ud[dir]][dir];
		    xing1 = xing0;
		    if ( !((dir == N0) || (dir == N1))) 
		      perror("complete_processing","Bad direction\n");
		  }	
		nstrands++;
	      }
	    else       /* mark "neighbors" of termini */
	      {
		xingptr->markedge |= 1<<N0;
		xingptr->markedge |= 1<<N1;
	      }
	  }
      }
    /* process everything else */
    xingptr = linkptr->xinglist;
    dir = N0;
    while(1)
      {
	xing0 = xingptr;
	dir0 = dir;
	for (xingptr = xing0, done = 1, i=0; 
	     !(i >0 && xingptr == xing0 &&
	       (xing0->type == ANCHOR || dir0 == dir));
	     xingptr = xingptr->next, ++i)
	  {
	    if ( (xingptr->orient != TERMINUS))  /* ignore termini of tangles */
		{
		  if ( !(xingptr->markedge & (1<<N0)))
		    {
		      dir = N0;
		      done = 0;
		      goto OUT1;
		    }
		  else if ( !(xingptr->markedge & (1<<N1))
			   && (xingptr->type == NORMAL))
		    {
		      dir = N1;
		      done = 0;
		      goto OUT1;
		    }
		}
	  }
OUT1:
	    if (done) {
	      goto OUT;
	    }
	    /* traverse_strand(xingptr) */
	    didStartWithLooseEnd = (xingptr->type == LOOSE_END);
	    linkptr->strandlist[nstrands] = xingptr;
	    linkptr->dirlist[nstrands] = dir;
	    nstrands++;
	    xing1 = xingptr;
	    dir1 = dir;
	    for (xingptr = xing1, done = 1, i=0; 
		 !((i > 0  && xing1 == xingptr &&
		    (dir1 == dir || xing1->type == ANCHOR)) ||
		   (xingptr->orient == TERMINUS));
		 ++i)
	      {
		xingptr->markedge |= 1<<dir;
	        xing0 = xingptr->nhbr[dir];
		dir = newdirtable[xingptr->ud[dir]][dir];
		xingptr = xing0;
		if ( !((dir == N0) || (dir == N1))) 
		  perror("complete_processing","Bad direction\n");
	      }
	    /* Ignore what we've done if we didn't start at the
	       beginning of a loose strand */
	    if (xingptr->orient == TERMINUS && !didStartWithLooseEnd)
	      nstrands--;
      }
  OUT:
    if (nstrnd_included && (linkptr->nstrands != nstrands))
      perror("complete_processing"," wrong number of strands\n");
    linkptr->nstrands = nstrands;
  }


void resetEdgeRegions (crossing *xing)
{
  xing->edgeRegions[0][0]
    = xing->edgeRegions[0][1]
      = xing->edgeRegions[1][0]
	= xing->edgeRegions[1][1]
	  = NULL;
}

link *
linkread(link **lpp, int **matrix, int numcross, NXZone *zone, short *tangle)
{

  crossing *xing_array;
  int i, n0, n1;
  char ud0[2], ud1[2], lr[2];
  
  nstrnd_included = 0;
  *tangle = 0;    /* reset tangle */
  
  nstrnd_included = 1;
  linkptr = *lpp = linkalloc(zone);
  linkptr->label = "";
  linkptr->nxings = numcross;
  if ((xing_array = (struct crossing *)
       NXZoneMalloc(zone, sizeof(struct crossing)*linkptr->nxings)) == NULL)
    {
      perror ("readlink","unable to allocate xinglist.");
      return(NULL);
    }
  linkptr->xinglist = xing_array;
  
  for (i=0; i<linkptr->nxings; ++i)	 
    {
      lr[0] = matrix[i][0];
      n0 = (int) matrix[i][1];
      ud0[0] = matrix[i][2];
      n1 = (int) matrix[i][3];
      ud1[0] = matrix[i][4];

      xing_array[i].n = i;
      xing_array[i].type = NORMAL;
      resetEdgeRegions(&xing_array[i]);
      
      /* Set tangle var. if necessary */
      if (lr[0] == '0') *tangle = 1;
      
      xing_array[i].orient = 
	(lr[0] == 'r' || lr[0] == 'R') ? RIGHT : ((n0 == 0) ? TERMINUS : LEFT);
      /* process the up strand */
      if (n0)               /* check is necessary when tangle = 1 */
	{
	  xing_array[i].nhbr[N0] = &xing_array[n0-1];
	  if (ud0[0] == 'u' || ud0[0] == 'U')
	    {
	      xing_array[i].ud[N0] = UP;
	      xing_array[n0-1].nhbr[P0] = &xing_array[i];
	      xing_array[n0-1].ud[P0] = UP;
	    }
	  else
	    {
	      xing_array[i].ud[N0] = DOWN;
	      xing_array[n0-1].nhbr[P1] = &xing_array[i];
	      xing_array[n0-1].ud[P1] = UP;
	    }
	}
      else
	{
	  if (ud0[0] == 'u' || ud0[0] == 'U')
	    xing_array[i].ud[N0] = UP;
	  else
	    xing_array[i].ud[N0] = DOWN;
	  xing_array[i].nhbr[N0] = &xing_array[i];
	}
      
      
      /* process the down strand */
      if (n1)                 /* check is necessary when tangle = 1 */
	{
	  xing_array[i].nhbr[N1] = &xing_array[n1-1];
	  if (ud1[0] == 'u' || ud1[0] == 'U')
	    {
	      xing_array[i].ud[N1] = UP;
	      xing_array[n1-1].nhbr[P0] = &xing_array[i];
	      xing_array[n1-1].ud[P0] = DOWN;
	    }
	  else 
	    {
	      xing_array[i].ud[N1] = DOWN;
	      xing_array[n1-1].nhbr[P1] = &xing_array[i];
	      xing_array[n1-1].ud[P1] = DOWN;
	    }
	}
      else
	{
	  if (ud1[0] == 'u' || ud1[0] == 'U')
	    xing_array[i].ud[N1] = UP;
	  else
	    xing_array[i].ud[N1] = DOWN;
	  xing_array[i].nhbr[N1] = &xing_array[i];
	  xing_array[i].nhbr[P0] = &xing_array[i];
	  xing_array[i].nhbr[P1] = &xing_array[i];
	}
      if (i<linkptr->nxings-1)
	xing_array[i].next = &xing_array[i+1];
      else xing_array[i].next = &xing_array[0];
    }
  complete_processing(linkptr, *tangle);
  return NULL;
}

/*
int
writelink(linkptr, fp)
link *linkptr;
FILE *fp;
{
	int i, j;
	crossing *xing;
	region *reg;

	fprintf(fp,"%s %s %s\n","%L",linkptr->label," L%");
	fprintf(fp,"%s %d %s\n","%Ns ",linkptr->nstrands, " Ns%");
	fprintf(fp,"%s %d %s\n","%Nx ",linkptr->nxings," Nx%");
#ifdef FALSE
	fprintf(fp,"%Key ");
	if (linkptr->planar == 1)	fprintf(fp,"planar ");
	if (linkptr->prime == 1)	fprintf(fp,"prime ");
	fprintf(fp," Key%\n");
#endif
	fprintf(fp,"%s ","%X");
	for (xing = linkptr->xinglist, i=0;i<linkptr->nxings; xing = NEXTXING(xing),++i)
	    fprintf(fp," %5d",xing->n);
	fprintf(fp," %s\n","X%");
	fprintf(fp,"%s ","%O");
	for (xing = linkptr->xinglist, i=0;i<linkptr->nxings; xing = NEXTXING(xing),++i)
	    fprintf(fp,"%c",ou[xing->overunder]);
	fprintf(fp," %s\n","O%");
	fprintf(fp,"%s ","%R");
	for (xing = linkptr->xinglist, i=0;i<linkptr->nxings; xing = NEXTXING(xing),++i)
	    fprintf(fp,"%c",lr[((xing->orient == 1) ? 1 : 0)]);
	fprintf(fp," %s\n","R%");
#ifdef FALSE
	fprintf(fp,"%Nr %d Nr%\n",linkptr->nregions);
	for (reg = linkptr->rlist[0], i=0;i<linkptr->nregions; 
	    ++i, reg = linkptr->rlist[i])
	    {
	    fprintf(fp,"Re %d ", i);
	    for (j = 0; j < reg->nv; ++j)	
		fprintf(fp," %5d", reg->vlist[j]->n);
	    fprintf(fp," Re%\n");
	    }
#endif
}
*/	    

/* following gets the next %keyword from file.
   returns 0 if EOF, otherwise 1 */
int
get_keyword(fp, string)	
FILE *fp;
char *string;
{
	char t;
	if (fp == NULL)
	  {
	    *string = 'M';
	    return 1;
	  }
	/* search for '%' */
	while ((t = getc(fp)) != '%')	{
	    if (t == (char) EOF) return(0);
	    }
	if (fscanf(fp,"%s",string) == 0) 	{
	    perror("readlink.get_keyword","Unexpected EOF.");
	    return (0);
	    }
	
#ifdef DEBUG
	fprintf(stderr,"keyword %s\n",string);
#endif
	return (1);
}

int
get_matching_keyword(fp, keyword)
FILE *fp;
char *keyword;
{
	char keyword2[KEYWORDSIZE];
	fscanf(fp,"%s",keyword2);
	if (strncmp(keyword, keyword2, strlen(keyword)) != 0)	{
	    perror("readlink.get_matching_keyword","Invalid matching string.");
	    return(0);
	    }
	if (keyword2[strlen(keyword)] != '%')	{
	    perror("readlink.get_matching_keyword","Invalid matching %.");
	    return(0);
	    }
	return(1);
}

/* crossing *
get_xing_addr(k, linkptr)
link *linkptr;
{
	int i;
	crossing *xing;
	for (xing = linkptr->xinglist,i=0; i<linkptr->nxings; 
	    xing = NEXTXING(xing),++i)
	        if (xing->n == k)  return(xing);
	return(NULL);
} */
int
get_index(int k, crossing *array, int n)

{
	int i;

	for (i=0; i<n; ++i)
	       if (array[i].n == k)  return(i);
	return(-1);
}
void printlink(linkptr)
link *linkptr;
{
	int i, j;
	crossing *kn;
	region **rn;

	printf("Knot %s\n",linkptr->label);
	printf("\tPrime:\t%s\n",tf[linkptr->prime]);
	printf("\tPlanar:\t%s\n",tf[linkptr->planar]);
	printf("\t%d crossings\n",linkptr->nxings);
	printf("Crossing list:\n");
	printf("\tn:\to/u\tr/l\tP0:\tN0:\tP1:\tN1::\n");
	for (i=0, kn = linkptr->xinglist; i<linkptr->nxings; 
	    ++i, kn = NEXTXING(kn)) 	
		{
		printf("\t%d\t%s\t%s\t%d\t%d\t%d\t%d\n",kn->n,
		    o_u_label[kn->overunder & 1], r_l_label[kn->orient & 1],
		    kn->nhbr[P0]->n, kn->nhbr[N0]->n, kn->nhbr[P1]->n, kn->nhbr[N1]->n);
		}
	printf("Region list\n");
	for (i=0, rn = linkptr->rlist; i<linkptr->nregions; ++i)
	    {
	    printf("\tRegion #\t%d:",rn[i]->n);
	    for (j=0; j<rn[i]->nv; ++j)	printf("%5d",rn[i]->vlist[j]->n);
	    printf("\n");
	    }
}

int 
make_link_from_xings(linkp, xing_array)
link *linkp;
crossing *xing_array;
{
	    int i, n, t, s0, s1;
	    /* construct pointers to neighboring 4 xings */
	    /* this takes advantage of the special way the xings are input */
	    linkptr = linkp;
	    n = linkp->nxings;
	    for ( i = 0; i<n; ++i)
		{
	 	/* look up indices of two (implicit) neighbor xings  */
		s0 = get_index(i, xing_array,n);
		s1 = get_index((i+1)%n, xing_array,n);
		if (s0 < 0 || s1 < 0)	{
		    perror ("readlink","Incomplete crossing list.");
		    return(0);
		    }
		t = xing_array[i].n;
	    /* the orientation of a crossing is determined by its explicit
	    rather than implicit appearance in the crossing list */
		
		xing_array[i].nhbr[P0] = &(xing_array[s0]);
		xing_array[i].nhbr[N0] = &(xing_array[s1]);

		xing_array[i].nhbr[P1] = &(xing_array[(t-1+n)%n]);
		xing_array[i].nhbr[N1] = &(xing_array[t]);
		}
	    /* everything above assumes we start from xing 0 and go 
	       to neighbor N0 */
	    linkp->xinglist = xing_array;
	    return (0);
}

int
check_file_format(fp)
FILE *fp;
{
    int ok;
    char x = getc(fp);
    /* discard blanks */
    while (  x == ' ' || x == '\t' || x == '\n') x = getc(fp);
    if (x == '%')	ok = 1;
    else ok = 0;
    ungetc(x,fp);
    return(ok);
}
