#include <stdio.h>
double hypot();
char *malloc();
void free();

#define EPSILON (1.0e-6)

#ifndef TRUE
#define TRUE 1==1
#define FALSE 0==1
#endif

/******************************************************************************/
/* Reference for Quad-edge data structure:

Leonidas Guibas and Jorge Stolfi, "Primitives for the manipulation of general
     subdivisions and the computations of Voronoi diagrams",
     ACM Transactions on Graphics 4, 74-123 (1985).
*/
/******************************************************************************/
/**************************** Common data structures **************************/

typedef int BOOLEAN;
typedef int SITE_PTR;
typedef int EDGE_PTR;
typedef int TRI_PTR;
typedef int INFO_PTR;

struct VEC2 {
    double x,y;
};

struct SITE {
    double temp;
    double volume; /* area of the voronoi cell */
    double specific_heat;
    double heat_cond;
    struct VEC2 vc;
    struct VEC2 lgrad;
    struct VEC2 agrad;
    char boundary;
    char type;
};

struct EDGE_INFO {
    double del_length;
    double vor_length; /* really may be a crystalline energy */
    double coupling;
    int see;
    int which_wulff;
};

struct TRI {
    TRI_PTR next;
    struct VEC2 vc; /* location of the voronoi center */
    double area; /* area of the triangle */
};

extern EDGE_PTR alloc_edge();
extern EDGE_PTR makeedge();
extern splice();
extern swapedge();
extern EDGE_PTR connect();
extern deleteedge();
extern build_delaunay_triangulation();
extern zero_seen();

#ifdef DEFINE_GLOBALS
#define EXTERN 
#else
#define EXTERN extern
#endif

EXTERN struct SITE *sa ;
EXTERN EDGE_PTR One_bndry_edge;
EXTERN EDGE_PTR *next ;
EXTERN SITE_PTR *org ;
EXTERN struct EDGE_INFO *ei ;
EXTERN struct TRI *fa ;
EXTERN int n_sites;
EXTERN struct VEC2 *wulff;
EXTERN int n_wulff;

/******************************************************************************/
/********************** Macros for manipulation of quad-edges *****************/

/*  SITE_PTR s  */
#define X(s) sa[s].vc.x
#define Y(s) sa[s].vc.y
#define Site(s) sa[s].vc
#define Temp(s) sa[s].temp
#define Vol(s) sa[s].volume
#define Bdy(s) sa[s].boundary
#define Type(s) sa[s].type
#define T_LIQUID 0
#define T_SOLID 1
#define Len_grad(s) sa[s].lgrad
#define Sol_agrad(s) sa[s].agrad
#define HtCond(s) sa[s].heat_cond
#define SpHeat(s) sa[s].specific_heat

/*  EDGE_PTR a  */
#define sym(a) ((a) ^ 2)
#define rot(a) ( (((a) + 1) & 3) | ((a) & ~3) )
#define rotinv(a) ( (((a) + 3) & 3) | ((a) & ~3) )

#define onext(a) next[a]
#define oprev(a) rot(onext(rot(a)))
#define lnext(a) rot(onext(rotinv(a)))
#define lprev(a) sym(onext(a))
#define rnext(a) rotinv(onext(rot(a)))
#define rprev(a) onext(sym(a))
#define dnext(a) sym(onext(sym(a)))
#define dprev(a) rotinv(onext(rotinv(a)))

#define orig(a) org[a]
#define dest(a) orig(sym(a))
#define left(a) orig(rotinv(a))
#define right(a) orig(rot(a))

#define origv(a) sa[orig(a)].vc
#define destv(a) sa[dest(a)].vc
#define leftv(a) fa[left(a)].vc
#define rightv(a) fa[right(a)].vc

#define info(a) ei[(a)>>2]
#define Wulffv(a) wulff[info(a).which_wulff]

#define seen(a) (info(a).see)
#define dir_see(a) (((a)&2)+2)

/*  TRI_PTR c  */
#define Corner(c) fa[c].vc
#define tnext(c) fa[c].next
#define Area(c) fa[c].area

/******************************************************************************/
/******************************* General macros *******************************/

#define my_alloc(str_name, str_type, str_cnt) \
		if (NULL == ((str_name) = (str_type *) \
			malloc ((unsigned) ((str_cnt) * sizeof(str_type))))) \
		exit(fprintf(stderr," cannot malloc (str_name) \n"))

#define V2_dotq(u,v) ((u).x*(v).x + (u).y*(v).y)
#define V2_cprodq(u,v) ((u).x*(v).y - (u).y*(v).x)
#define V2_magnq(u) hypot((u).x,(u).y)

#define INITRAND	srand48( (long) time( (long *) 0 ) )
#define RAND		drand48()
long time();
double drand48();
void srand48();

#include "traverse.h"