/*
 * The author of this software is Steven Fortune.  Copyright (c) 1994 by AT&T
 * Bell Laboratories.
 * Permission to use, copy, modify, and distribute this software for any
 * purpose without fee is hereby granted, provided that this entire notice
 * is included in all copies of any software which is or includes a copy
 * or modification of this software and in all copies of the supporting
 * documentation for such software.
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.- */

#
#include "vdefs.h"

#ifndef lint
static char RCSid[] = "$Id: vedglist.c,v 1.2 2003/07/24 15:44:06 pturner Exp $";
#endif

int ntry, totalsearch;

void ELinitialize(void)
{
    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(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(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(he, &hfl);
    return ((struct Halfedge *) NULL);
}

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

/* Use hash table to get close to desired halfedge */
    bucket = (p->x - vxmin) / 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(struct Halfedge * he)
{
    return (he->ELright);
}

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


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