/*
 * 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 "link.h"
  
#define MAX_BRS 100  /* maximum number of biggest regions */
#define MAX_AR  100  /* maximum number of regions adjacent
		       to each of the biggest regions */
#define	perror(s1,s2)	fprintf(stderr,"Error in %s: %s\n",s1,s2)
#define FIXED
  
  /*
    #define DEBUG
    */
  /* this table is indexed by   up/down x back/forward and tells which
     strand the current direction connects to */
  int tofromtable[2][2] = {{N0, P0}, {N1, P1}};
static int rightturntable[2][4] = {
  N1, P1, P0, N0, 
  P1, N1, N0, P0}; 	/* this row is the other direction */

/* This table is indexed by [orientation-of-crossing] x [out-direction].
   It returns the region determined by the out-dir and its corresponding
   left-hand-turn-dir */
static int adj_reg_table[2][4] = {{SE, NW, SW, NE}, {SW, NE, NW, SE}};
/* given pointers to a crossing and a direction leaving from that crossing,
   use the orientation information at that crossing 
   to update the input pointers to indicate the next crossing and the direction
   leaving from that crossing in order to make a clockwise turn there */


int clockwise(xing, dir)
     crossing **xing;
     int *dir;
{
  /* copy over the inputs */
  int tdir = *dir, inedge;
  crossing *nxing = (*xing)->nhbr[tdir];
  
  inedge = tofromtable[(*xing)->ud[tdir] ][tdir & 1];	
  *dir = rightturntable[nxing->orient][inedge];
  *xing = nxing;
  return(inedge);
} 

static crossing  *vlist[4*MAXX];
static short dlist[4*MAXX];
static region	*rlist[4*MAXX];
#ifdef FIXED
static int xingcnt;
static region	regionarray[4*MAXX];
static short	darray[4*MAXX];
static crossing	*varray[4*MAXX];
#endif

/* beginning at crossing *xing, go out along edge edgenum, take right
   turns until you return, store result in *reg, mark edges that you 
   traverse */
void *traverse_region(crossing *xing, int edgenum, region *reg)


{
  register int start;
  register int i, nv; 
  int dir, odir;

  
  for (start = xing->n, dir = edgenum, nv = 0;  
       !( (nv > 0) && (xing->n == start)); ++nv)	
    {
#ifdef DEBUG
      printf("\tcrossing:\t%d\tdirection:\t%d\n",xing->n,dir);
#endif
      vlist[nv] = xing;	/* store crossing address (see below) */
      dlist[nv] = dir;
      /* mark the outgoing edge: we've done it  */
      xing->markedge |= (1<<dir);
      /* move to next crossing */
      odir = clockwise(&xing, &dir);
      /* store pointer to this region */
      xing->regions[whichregion(odir,dir)] = reg;	
    }
#ifdef DEBUG
  printf("crossing:\t%d\tdirection:\t%d\tmarkedge:\t%d\n",xing->n,dir,xing->markedge);
#endif
  /* we're back where we started; store pointer to this region */
  reg->nv = nv++;			/* the count has to upped one to be right */
#ifdef FIXED
  reg->vlist = varray + xingcnt;
  reg->dlist = darray + xingcnt;
  xingcnt += nv;
#else
  /* allocate new storage for this list of crossings and copy them over */
  if ( (reg->vlist = (crossing **) malloc (nv * sizeof (crossing *))) == NULL) 
    {
      perror ("linkregion.traverse_region","unable to allocate crossing list.");
      return (NULL);
    }
#endif
  for (i=0; i<nv; ++i)	
    {
      reg->vlist[i] = vlist[i];
      reg->dlist[i] = dlist[i];
    }
  return NULL;
}

/* Mark regions adjacent to edges for dandy evolution */
void markEdgeRegions (link *linkptr)
{
  crossing *xing;
  int i;
  for (i=0, xing = linkptr->xinglist; i < linkptr->nxings;
       i++, xing = xing->next)
    {
      xing->edgeRegions[UP][0] = xing->regions[whichregion(N0, N1)];
      xing->edgeRegions[UP][1] = xing->regions[whichregion(N0, P1)];
      xing->edgeRegions[DOWN][0] = xing->regions[whichregion(N1,P0)];
      xing->edgeRegions[DOWN][1] = xing->regions[whichregion(N1, N0)];
    }
}

void *mark_regions(link *linkptr)
{
  register crossing *xing;
  register region *reg;
  register int i, j, edgenum, mark, nregions = 0;
  
#ifdef FIXED
  xingcnt = 0;
#endif
  /* initialize edgemarker to 0 for each crossing	*/
  for (i = 0, xing = linkptr->xinglist; i < linkptr->nxings;  
       xing = xing->next, ++i)
    {	
      xing->markedge = 0;
      for (j=0; j<4; ++j)	xing->regions[j] = NULL;
    }
  
  /* traverse link in the "explicit" ordering of its crossings */
  for (i = 0, xing = linkptr->xinglist; i < linkptr->nxings;  
       xing = xing->next, ++i)
    {
      /* do each crossing totally before moving on to next */ 
      for (mark = xing->markedge, edgenum=0; edgenum<4; ++edgenum)	
	{
	  if ( !(mark & (1<<edgenum)))	/* this edge not followed out yet */
	    {
#ifdef FIXED
	      reg = &(regionarray[nregions]);
#else
	      if ( (reg = (region *) malloc(sizeof (region))) == NULL)
		{
		  perror ("linkregion.mark_egions","unable to allocate region.");
		  return (NULL);
		}
#endif
#ifdef DEBUG
	      printf("\nregion#\t%d\tcrossing#\t%d\n",nregions,xing->n);
#endif
	      traverse_region(xing, edgenum, reg);
	      rlist[nregions] = reg;
	      reg->n = nregions++;
	    }
#ifdef DEBUG
	  else
	    printf("Region already done: xing#  %d,  edge#  %d\n",xing->n,edgenum);
#endif
	  
	}
    }
  linkptr->nregions = nregions;
#ifdef FIXED
  linkptr->rlist = rlist;
#else
  if ( (linkptr->rlist = (region **) malloc (nregions * sizeof(region *))) == NULL)
    {
      perror ("linkregion.traverse_region","unable to allocate region pointer list.");
      return (NULL);
    }
  for (j=0; j<nregions; ++j)	linkptr->rlist[j] = rlist[j];
#endif
  
  /* link lies on sphere if euler characteristic is 2 */
  linkptr->planar = (linkptr->nregions - linkptr->nxings == 2);
  markEdgeRegions(linkptr);
  return NULL;
}

int
  linkplanar(linkptr)
link *linkptr;
{
  mark_regions(linkptr);
  if (!linkptr->planar) return (-1);
  else return(1);
}


/* which quadrant (NE, SE, SW, NW) are we in, depending upon the two edges 
   mark an impossible combination with -1 	*/
static int regiontable[4][4] = {	/* symmetric matrix with 8 valid entries */
  -1, -1, 2, 1,
  -1, -1, 3, 0,
  2,  3, -1, -1,
  1, 0, -1, -1	};

int whichregion(int dir0, int dir1)	
{
  return(regiontable[dir0][dir1]);	
}
void freeregion(link *linkptr)

{
  int i;
  for (i=0; i<linkptr->nregions; ++i)
    {
      free(linkptr->rlist[i]->vlist);
      free(linkptr->rlist[i]);
    }
  free(linkptr->rlist);
}

/* Puts pointers to biggest regions in bigregs[], and returns
   # of bigregs */
int get_biggest_regions(linkptr, bigregs)
     link *linkptr;
     region *bigregs[MAX_BRS];
{
  int maxn, i, num_bigregs;
  region *rptr0;
  num_bigregs = 0;
  /* search for largest # of vertices */
  for (maxn = 0, i = 0; i<linkptr->nregions; ++i)
    {
      rptr0 = linkptr->rlist[i];
      if (rptr0->nv > maxn) 	
	maxn = rptr0->nv;
    }
  /* compose list of biggest regions */
  for (i=0; i<linkptr->nregions; ++i)
    {
      rptr0 = linkptr->rlist[i];
      if (rptr0->nv == maxn)
	bigregs[num_bigregs++] = rptr0;
    }
  return(num_bigregs);
  
}

int compare(m, n)   /* compares two integer pointers--used for qsort */
     char *m, *n;
{
  int *a, *b;
  a = (int *) m;
  b = (int *) n;
  return (*a-*b);
}

region *find_canonical_region(linkptr)
     link *linkptr;
{

  register int i, j;
  int dir, num_bigregs, can, k;
  region *bigregs[MAX_BRS], *reg, *rptr;
  crossing *xing;
  int adj_reg_size[MAX_BRS][MAX_AR]; /* for each bigreg, provides an
					array of sizes of adjacent regions */
  int num_adj_regs[MAX_BRS]; /* gives number of adjacent regions for each bigreg */
  
  num_bigregs = get_biggest_regions (linkptr, bigregs);
  if (num_bigregs == 1) return(bigregs[0]);
  else
    {
      /* initialize adj_reg_size */
      for (i=0; i<MAX_BRS; i++)
	for (j=0; j<MAX_AR; j++)
	  adj_reg_size[i][j] = 0;
      
      /* iterate for each of the biggest regions */
      for (i = 0; i < num_bigregs; i++)
	{
	  k = 0;  /* reset neighbor-region count */
	  /* unmark all regions */
	  for (j = 0; j<linkptr->nregions; j++)
	    linkptr->rlist[j]->markreg = 0;
	  reg = bigregs[i];
	  /* traverse crossings of reg */
	  for (j=0; j < reg->nv; j++)
	    {
	      xing = reg->vlist[j];
	      dir = reg->dlist[j];
	      rptr = xing->regions[adj_reg_table[xing->orient][dir]];
	      if (rptr->markreg == 0)
		{ 
		  adj_reg_size[i][k++] = rptr->nv;  /* record size of region, mark it */
		  rptr->markreg = 1;
		}
	    }
	  num_adj_regs[i] = k;
	  /* sort sizes of neighboring regions */
	  qsort ((char *) adj_reg_size[i], num_adj_regs[i], sizeof(int), compare);
	}
      
      /* find canonical biggest region */
      ncan = can = 0;
      canregs[0] = bigregs[0];
      for (i=1; i<num_bigregs; i++)
	{
	  for (j=0; j<num_adj_regs[i]; j++)
	    {
	      if (j == num_adj_regs[can])  /* found one equal but longer than can */
		{
		  ncan=0;
		  can=i;
		  canregs[ncan] = bigregs[i];
		  break;
		}
	      else if (adj_reg_size[can][j] < adj_reg_size[i][j]) /* found one bigger than can */
		{
		  ncan=0;
		  can=i;
		  canregs[ncan] = bigregs[i];
		  break;
		}
	      else if (adj_reg_size[can][j] > adj_reg_size[i][j]) /* can is definitely bigger */
		break;
	      else if (j == num_adj_regs[can] - 1)   /* there's a tie */
		{
		  ++ncan;        /* increment number of extra can's */
		  canregs[ncan] = bigregs[i];  /* record extra canreg */
		}
	    }
	}
      if (ncan != 0)
	{
	  if (draw_all_regs == 0)
	    fprintf(stderr,"find_canonical_region: chose one of %d regions\n", ncan+1);
	  else fprintf(stderr,"find_canonical_region: drawing %d versions\n", ncan+1);
	}
      if (draw_all_regs) return (canregs[0]);
      else return (bigregs[can]);
    }
}

/* Determines which crossing of the canonical region to place at zero degrees */
int find_canonical_xing(region *rptr,int offsets[], int *numx)


{
  short i,j, canx=0;
  int sizelist[MAX_NX][4];

  offsets[0]=0;
  *numx = 0;
  if (rptr->nv > 1)
    {
      /* construct sizelists for each crossing */
      for (i=0; i<rptr->nv; i++)
	{
	  for (j=0; j<4; j++)
	    sizelist[i][j] = rptr->vlist[i]->regions[j]->nv;
	  qsort ((char *) sizelist[i], 4, sizeof(int), compare);
	}

      /* find "biggest" sizelist */

      /* iterate for each crossing */
      for (i=1; i<rptr->nv; i++)
	for (j=0; j<4; j++)
	  {
	    if (sizelist[i][j] > sizelist[canx][j])  /* bigger than canx */
	      {
		canx = i;
		*numx = 0;
		offsets[*numx] = i;
		break;
	      }
	    else if (sizelist[canx][j] > sizelist[i][j])  /* canx is definitely bigger */
	      break;
	    else if (j==3)
	      {
		(*numx)++;      /* since loop was completed, the number of ties for canx increased */
		offsets[*numx] = i; /* record extra crossing */
	      }
	  }
      if (*numx > 0)
	{
	  if (draw_all_rots)
	    fprintf (stderr,"find_canonical_xing: making %d versions\n",(*numx)+1);
	  else fprintf(stderr, "find_canonical_xing: chose one of %d crossings\n",(*numx)+1);
	}
    }
  return(offsets[0]);
}
