#
#include "defs.h"
int nedges;
struct Freelist efl;
struct Freelist hfl;
struct Halfedge *ELleftend, *ELrightend;
int ELhashsize;
struct Halfedge **ELhash;

int ntry, totalsearch;

void ELinitialize() {
	int i;
	freeinit(&hfl, sizeof **ELhash);
	ELhashsize = 2 * sqrt_nsites;
	ELhash = (struct Halfedge **)myalloc(sizeof *ELhash * ELhashsize);
	for (i = 0; i < ELhashsize; i += 1)
		ELhash[i] = (struct Halfedge *)NULL;
	ELleftend = HEcreate((struct Edge *)NULL, 0);
	ELrightend = HEcreate((struct Edge *)NULL, 0);
	ELleftend->ELleft = (struct Halfedge *)NULL;
	ELleftend->ELright = ELrightend;
	ELrightend->ELleft = ELleftend;
	ELrightend->ELright = (struct Halfedge *)NULL;
	ELhash[0] = ELleftend;
	ELhash[ELhashsize - 1] = ELrightend;
}

struct Halfedge *HEcreate(e, pm) struct Edge *e;
int pm;
{
	struct Halfedge *answer;
	answer = (struct Halfedge *)getfree(&hfl);
	answer->ELedge = e;
	answer->ELpm = pm;
	answer->PQnext = (struct Halfedge *)NULL;
	answer->vertex = (struct Site *)NULL;
	answer->ELrefcnt = 0;
	return (answer);
}

void ELinsert(struct Halfedge *lb, struct Halfedge *new) {
	new->ELleft = lb;
	new->ELright = lb->ELright;
	(lb->ELright)->ELleft = new;
	lb->ELright = new;
}

/* Get entry from hash table, pruning any deleted nodes */
struct Halfedge *ELgethash(b) int b;
{
	struct Halfedge *he;

	if (b < 0 || b >= ELhashsize)
		return ((struct Halfedge *)NULL);
	he = ELhash[b];
	if (he == (struct Halfedge *)NULL || he->ELedge != (struct Edge *)DELETED)
		return (he);

	/* Hash table points to deleted half edge.  Patch as necessary. */
	ELhash[b] = (struct Halfedge *)NULL;
	if ((he->ELrefcnt -= 1) == 0)
		makefree((struct Freenode *)he, &hfl);
	return ((struct Halfedge *)NULL);
}

struct Halfedge *ELleftbnd(p) struct Point *p;
{
	int i, bucket;
	struct Halfedge *he;

	/* Use hash table to get close to desired halfedge */
	bucket = (p->x - xmin) / deltax * ELhashsize;
	if (bucket < 0)
		bucket = 0;
	if (bucket >= ELhashsize)
		bucket = ELhashsize - 1;
	he = ELgethash(bucket);
	if (he == (struct Halfedge *)NULL) {
		for (i = 1; 1; i += 1) {
			if ((he = ELgethash(bucket - i)) != (struct Halfedge *)NULL)
				break;
			if ((he = ELgethash(bucket + i)) != (struct Halfedge *)NULL)
				break;
		};
		totalsearch += i;
	};
	ntry += 1;
	/* Now search linear list of halfedges for the corect one */
	if (he == ELleftend || (he != ELrightend && right_of(he, p))) {
		do {
			he = he->ELright;
		} while (he != ELrightend && right_of(he, p));
		he = he->ELleft;
	} else
		do {
			he = he->ELleft;
		} while (he != ELleftend && !right_of(he, p));

	/* Update hash table and reference counts */
	if (bucket > 0 && bucket < ELhashsize - 1) {
		if (ELhash[bucket] != (struct Halfedge *)NULL)
			ELhash[bucket]->ELrefcnt -= 1;
		ELhash[bucket] = he;
		ELhash[bucket]->ELrefcnt += 1;
	};
	return (he);
}

/* This delete routine can't reclaim node, since pointers from hash
	 table may be present.   */
void ELdelete(struct Halfedge *he) {
	(he->ELleft)->ELright = he->ELright;
	(he->ELright)->ELleft = he->ELleft;
	he->ELedge = (struct Edge *)DELETED;
}

struct Halfedge *ELright(he) struct Halfedge *he;
{ return (he->ELright); }

struct Halfedge *ELleft(he) struct Halfedge *he;
{ return (he->ELleft); }

struct Site *leftreg(he) struct Halfedge *he;
{
	if (he->ELedge == (struct Edge *)NULL)
		return (bottomsite);
	return (he->ELpm == le ? he->ELedge->reg[le] : he->ELedge->reg[re]);
}

struct Site *rightreg(he) struct Halfedge *he;
{
	if (he->ELedge == (struct Edge *)NULL)
		return (bottomsite);
	return (he->ELpm == le ? he->ELedge->reg[re] : he->ELedge->reg[le]);
}