/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property 
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: Details at https://graphviz.org
 *************************************************************************/

#include <neatogen/mem.h>
#include <neatogen/hedges.h>
#include <common/render.h>
#include <stdbool.h>
#include <util/alloc.h>

#define DELETED -2

Halfedge *ELleftend, *ELrightend;

static Freelist hfl;
static int ELhashsize;
static Halfedge **ELhash;

void ELcleanup(void)
{
    freeinit(&hfl, sizeof(**ELhash));
    free(ELhash);
    ELhash = NULL;
}

void ELinitialize(void)
{
    int i;

    freeinit(&hfl, sizeof(**ELhash));
    ELhashsize = 2 * sqrt_nsites;
    if (ELhash == NULL)
	ELhash = gv_calloc(ELhashsize, sizeof(Halfedge *));
    for (i = 0; i < ELhashsize; ++i)
	ELhash[i] = NULL;
    ELleftend = HEcreate(NULL, 0);
    ELrightend = HEcreate(NULL, 0);
    ELleftend->ELleft = NULL;
    ELleftend->ELright = ELrightend;
    ELrightend->ELleft = ELleftend;
    ELrightend->ELright = NULL;
    ELhash[0] = ELleftend;
    ELhash[ELhashsize - 1] = ELrightend;
}


Site *hintersect(Halfedge * el1, Halfedge * el2)
{
    Edge *e1, *e2, *e;
    Halfedge *el;
    double d, xint, yint;
    bool right_of_site;
    Site *v;

    e1 = el1->ELedge;
    e2 = el2->ELedge;
    if (e1 == NULL || e2 == NULL)
	return NULL;
    if (e1->reg[1] == e2->reg[1])
	return NULL;

    d = e1->a * e2->b - e1->b * e2->a;
    if (-1.0e-10 < d && d < 1.0e-10)
	return NULL;

    xint = (e1->c * e2->b - e2->c * e1->b) / d;
    yint = (e2->c * e1->a - e1->c * e2->a) / d;

    if (e1->reg[1]->coord.y < e2->reg[1]->coord.y ||
	(e1->reg[1]->coord.y == e2->reg[1]->coord.y &&
	 e1->reg[1]->coord.x < e2->reg[1]->coord.x)) {
	el = el1;
	e = e1;
    } else {
	el = el2;
	e = e2;
    }
    right_of_site = xint >= e->reg[1]->coord.x;
    if ((right_of_site && el->ELpm == le) || (!right_of_site && el->ELpm == re))
	return NULL;

    v = getsite();
    v->refcnt = 0;
    v->coord.x = xint;
    v->coord.y = yint;
    return v;
}

/* returns 1 if p is to right of halfedge e */
int right_of(Halfedge * el, Point * p)
{
    Edge *e;
    Site *topsite;
    int above, fast;
    double dxp, dyp, dxs, t1, t2, t3, yl;

    e = el->ELedge;
    topsite = e->reg[1];
    bool right_of_site = p->x > topsite->coord.x;
    if (right_of_site && el->ELpm == le)
	return 1;
    if (!right_of_site && el->ELpm == re)
	return 0;

    if (e->a == 1.0) {
	dyp = p->y - topsite->coord.y;
	dxp = p->x - topsite->coord.x;
	fast = 0;
	if ((!right_of_site && e->b < 0.0) || (right_of_site && e->b >= 0.0)) {
	    above = dyp >= e->b * dxp;
	    fast = above;
	} else {
	    above = p->x + p->y * e->b > e->c;
	    if (e->b < 0.0)
		above = !above;
	    if (!above)
		fast = 1;
	}
	if (!fast) {
	    dxs = topsite->coord.x - (e->reg[0])->coord.x;
	    above = e->b * (dxp * dxp - dyp * dyp) <
		dxs * dyp * (1.0 + 2.0 * dxp / dxs + e->b * e->b);
	    if (e->b < 0.0)
		above = !above;
	}
    } else {			/*e->b==1.0 */
	yl = e->c - e->a * p->x;
	t1 = p->y - yl;
	t2 = p->x - topsite->coord.x;
	t3 = yl - topsite->coord.y;
	above = t1 * t1 > t2 * t2 + t3 * t3;
    }
    return el->ELpm == le ? above : !above;
}

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


void ELinsert(Halfedge * lb, 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 */
static Halfedge *ELgethash(int b)
{
    Halfedge *he;

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

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

Halfedge *ELleftbnd(Point * p)
{
    int i, bucket;
    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 == NULL) {
	for (i = 1; ; ++i) {
	    if ((he = ELgethash(bucket - i)) != NULL)
		break;
	    if ((he = ELgethash(bucket + i)) != NULL)
		break;
	}
    }
/* 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] != NULL)
	    --ELhash[bucket]->ELrefcnt;
	ELhash[bucket] = he;
	++ELhash[bucket]->ELrefcnt;
    }
    return he;
}


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


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

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


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

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