/*
 * 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
 */

#import <zone.h>
#import <mach.h>

#define        TERMINUS 44
#define		UP	0
#define 	DOWN 	1
#define		RIGHT	0
#define		LEFT	1
#define		UNORIENT	-1

#define		OVER	0
#define		UNDER	1

#define		IGNORE	4		/* bit used in 3-bit crossing fields of crossing structure */
#define MAXSTRANDS	20

typedef struct foo {
  double xyz[3]; } point;

#define NORMAL    0
#define ANCHOR    1
#define LOOSE_END 2

struct crossing	{
  char type;   /* Either NORMAL, ANCHOR, or LOOSE_END */
  short	n;			/* number (name) of crossing */
  short 	orient;			/* this should be 2-bit-field, */
  /* but problems w/ sign extension */
  /* also, is TERMINUS if it's a loose end quasi-
     crossing, and is directed out of knot */
  unsigned int 	overunder:1;
  unsigned short 	ud[4];
  unsigned int 	markedge:4;	/* used to trace out the regions */
  unsigned int	fixed:1;
  short nextR;
  short free[4];			/* used in linkorient */
  short seq_index;		/* used in linkorient */
  struct crossing *nhbr[4];
  struct crossing *next;		/* used to process as linear array */
  struct region *regions[4];	/* pointers to 4 adjacent regions */
  float x,y; 			/* optional coordinates */
  float phase; 			/* rotation of crossing */
  float sep;			/* min distance to nhbr */
  float edgeX[2];               /* Midpoints of edges UP & DOWN */
  float edgeY[2];               /* (edges coming OUT of crossing) */
  struct region *edgeRegions[2][2];  /* Regions adjacent to edges UP & DOWN */
} ;
typedef  struct crossing crossing;

/* location of 4 neighbors (predecessor and follower in two directions) in nhbr array */
#define		P0	0
#define		N0	1
#define		P1	2
#define		N1	3
#define		EP0	1
#define		EN0	2
#define		EP1	4
#define		EN1	8
/* locations of 4 regions adjoining a crossing (names biased to standard orientation) */
#define		NE	0	/* region bounded by N0-N1	*/
#define		SE	1	/* region bounded by N1-P0	*/
#define		SW	2	/* region bounded by P0-P1	*/
#define		NW	3	/* region bounded by P1-N0	*/

#define		BIT(n)	(1<<(n))

struct alpha_graph	{
  int 	**matrix;		/* matrix for alpha-graph of link.
				   if region i and j have no crossing in common,
				   matrix[i][j] = 0; else matrix[i][j] = sign
			 	   of crossing */
};

struct region {
  short n;		/* the "name" of this region */
  unsigned int markreg:1; /* to flag regions already traversed (find_canonical_region) */
  short nv;		/* number of vertices 	*/
  crossing **vlist;	/* list of vertices 	*/	
  short *dlist;		/* list of directions (makes most of vlist redundant) */
  float x,y;            /* For use with new & improved evolution */
};

typedef  struct region region;

/* to find next crossing of explicit listing, use following macro */
#define 	NEXTXING(xx)	(xx->next)

struct link	{
  char 	*label;
  unsigned short	info;
  unsigned short	planar:1;	/* planar graph? prime?	*/
  unsigned short 	orientable:1;
  unsigned short 	prime:1;		
  unsigned short 	lex_order:1;	/* vertices numbered in least lex. order? */
  double	min_sep;	/* minimum separation of nodes 	*/
  int	nstrands;
  crossing *strandlist[MAXSTRANDS];	/* list of where strands begin*/
  int	dirlist[MAXSTRANDS];	/* and the directions to move */
  int  	nxings;		/* number of double points	*/
  int 	nregions;	/* number of regions in the graph */
  crossing *xinglist;	/* linked list of crossings */
  region	**rlist;	/* list of regions	*/
  unsigned short 	canreg;	/* number of the canonical, biggest region */
};
typedef  struct link link;

link *linkread(link **lpp, int **matrix, int numcross, NXZone *zone, short *tangle);
link *linkalloc(NXZone *zone);
void freelink(link *, NXZone *);
#define MAXX_CAT	20	/* maximum # of edges for cataloger */
#define	MAXX		128	/* maximum # of edges for single-link routines */
#define	ALTERNATE_ONLY	1
#define	DRAW_KNOTS	2
#define FAST_REJECT	8
#define MAX_NX  132  /* maximum number of crossings on can-reg.
			(used in find_canonical_crossing) */
#define MAX_CRS 100  /* maximum number of canonical regions
			(if draw_all_regs is set) */

extern int ncan;
extern short draw_all_regs, draw_all_rots;
extern region *canregs[];

/* These are set in [DisplayController doDraw] and used
   in [DisplayView linkdraw] */
extern char *psfile;
extern char *three_d_ext;
extern char *three_d_dir;
extern char *three_d_file;

#define SCREEN          1
#define	THREE_D		4
#define PRINTER         8
void complete_processing(link *linkptr, short tangle);

/* Function declarations */

void
  splineval(double *p0, double *p1,double *p2,double *p3,double *pm,double *dd,double u);
void *mark_regions(link *linkptr);
void linkdyn(link *linkptr, short tangle);
int find_canonical_xing(region *rptr,int offsets[], int *numx);
int whichregion(int dir0, int dir1);
extern void *qsort(void *base, size_t nmemb, size_t size,
		   int (*compar)(const void *, const void *));
void resetEdgeRegions (crossing *xing);
