#ifndef NULL
#define NULL 0
#endif
#define DELETED -2
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

extern int triangulate, sorted, plot, debug;

struct Freenode {
	struct Freenode *nextfree;
};
struct Freelist {
	struct Freenode *head;
	int nodesize;
};
char *getfree();
char *myalloc();

extern double xmin, xmax, ymin, ymax, deltax, deltay;

struct Point {
	double x, y;
};

/* structure used both for sites and for vertices */
struct Site {
	struct Point coord;
	int sitenbr;
	int refcnt;
};

extern struct Site *sites;
extern int nsites;
extern int siteidx;
extern int sqrt_nsites;
extern int nvertices;
extern struct Freelist sfl;
extern struct Site *bottomsite;

void **alloclist;
int allocnum;

struct Edge {
	double a, b, c;
	struct Site *ep[2];
	struct Site *reg[2];
	int edgenbr;
};
#define le 0
#define re 1
extern int nedges;
extern struct Freelist efl;

int has_endpoint(), right_of();
struct Site *intersect();
double dist();
struct Point PQ_min();
struct Halfedge *PQextractmin();
struct Edge *bisect();

struct Halfedge {
	struct Halfedge *ELleft, *ELright;
	struct Edge *ELedge;
	int ELrefcnt;
	char ELpm;
	struct Site *vertex;
	double ystar;
	struct Halfedge *PQnext;
};

extern struct Freelist hfl;
extern struct Halfedge *ELleftend, *ELrightend;
extern int ELhashsize;
extern struct Halfedge **ELhash;
struct Halfedge *HEcreate(), *ELleft(), *ELright(), *ELleftbnd();
struct Site *leftreg(), *rightreg();

extern int PQhashsize;
extern struct Halfedge *PQhash;
extern struct Halfedge *PQfind();
extern int PQcount;
extern int PQmin;
int PQempty();

extern double *site_list;
extern double *vert_list;
extern double *line_list;
extern unsigned int *edge_list;
extern unsigned int *dual_list;

extern int vert_count;
extern int edge_count;
extern int line_count;
extern int dual_count;
extern int site_count;

void makefree(struct Freenode *curr, struct Freelist *fl);
void voronoi(int triangulate, struct Site *(*nextsite)());
char *getfree(struct Freelist *fl);
char *myalloc(unsigned n);
void freeinit(struct Freelist *fl, int size);
void ELinitialize();
struct Halfedge *HEcreate(struct Edge *e, int pm);
void ELinsert(struct Halfedge *lb, struct Halfedge *new);
struct Halfedge *ELgethash(int b);
struct Halfedge *ELleftbnd(struct Point *p);
void ELdelete(struct Halfedge *he);
struct Halfedge *ELright(struct Halfedge *he);
struct Halfedge *ELleft(struct Halfedge *he);
struct Site *leftreg(struct Halfedge *he);
struct Site *rightreg(struct Halfedge *he);
void geominit();
struct Edge *bisect(struct Site *s1, struct Site *s2);
struct Site *intersect(struct Halfedge *el1, struct Halfedge *el2);
int right_of(struct Halfedge *el, struct Point *p);
void endpoint(struct Edge *e, int lr, struct Site *s);
double dist(struct Site *s, struct Site *t);
void makevertex(struct Site *v);
void deref(struct Site *v);
void ref(struct Site *v);
void PQinsert(struct Halfedge *he, struct Site *v, double offset);
void PQdelete(struct Halfedge *he);
int PQbucket(struct Halfedge *he);
int PQempty();
struct Point PQ_min();
struct Halfedge *PQextractmin();
void PQinitialize();
void out_bisector(struct Edge *e);
void out_ep(struct Edge *e);
void out_vertex(struct Site *v);
void out_site(struct Site *s);
void out_triple(struct Site *s1, struct Site *s2, struct Site *s3);