<commit_before>/* $Id$ $Revision$ */
/* vim:set shiftwidth=4 ts=8: */

/**********************************************************
*      This software is part of the graphviz package      *
*                http://www.graphviz.org/                 *
*                                                         *
*            Copyright (c) 1994-2004 AT&T Corp.           *
*                and is licensed under the                *
*            Common Public License, Version 1.0           *
*                      by AT&T Corp.                      *
*                                                         *
*        Information and Software Systems Research        *
*              AT&T Research, Florham Park NJ             *
**********************************************************/


/*
 * set edge splines.
 */

#include "dot.h"


#define	NSUB	9		/* number of subdivisions, re-aiming splines */
#define	CHUNK	128		/* in building list of edges */

#define MINW 16			/* minimum width of a box in the edge path */
#define HALFMINW 8

#define FWDEDGE    16
#define BWDEDGE    32

#define MAINGRAPH  64
#define AUXGRAPH  128
#define GRAPHTYPEMASK	192	/* the OR of the above */

#define MAKEFWDEDGE(new, old) { \
	edge_t *newp; \
	newp = new; \
	*newp = *old; \
	newp->tail = old->head; \
	newp->head = old->tail; \
	ED_tail_port(newp) = ED_head_port(old); \
	ED_head_port(newp) = ED_tail_port(old); \
	ED_edge_type(newp) = VIRTUAL; \
	ED_to_orig(newp) = old; \
}

#define P2PF(p, pf) (pf.x = p.x, pf.y = p.y)

static int flatsidemap[16][6] = {
    {BOTTOM, BOTTOM, BOTTOM, CCW, CCW, FALSE},
    {TOP, TOP, TOP, CW, CW, FALSE},
    {RIGHT, LEFT, BOTTOM, CW, CW, TRUE},
    {BOTTOM, TOP, RIGHT, CCW, CW, TRUE},
    {TOP, BOTTOM, RIGHT, CW, CCW, TRUE},
    {RIGHT, TOP, RIGHT, CCW, CW, TRUE},
    {RIGHT, BOTTOM, RIGHT, CW, CCW, TRUE},
    {TOP, LEFT, TOP, CW, CCW, TRUE},
    {BOTTOM, LEFT, BOTTOM, CCW, CW, TRUE},
    {RIGHT, RIGHT, BOTTOM, CW, CCW, TRUE},
    {LEFT, LEFT, BOTTOM, CCW, CW, TRUE},
    {LEFT, BOTTOM, BOTTOM, CCW, CCW, FALSE},
    {TOP, RIGHT, TOP, CW, CW, FALSE},
    {LEFT, TOP, TOP, CW, CW, FALSE},
    {BOTTOM, RIGHT, BOTTOM, CCW, CCW, FALSE},
    {LEFT, RIGHT, BOTTOM, CCW, CCW, FALSE},
};

#define AVG(a, b) ((a + b) / 2)

static int LeftBound, RightBound, /* FlatHeight, */ Splinesep, Multisep;
static box *Rank_box;

static box boxes[1000];

static void adjustregularpath(path *, int, int);
static Agedge_t *bot_bound(Agedge_t *, int);
static unsigned char pathscross(Agnode_t *, Agnode_t *, Agedge_t *,
				Agedge_t *);
static void chooseflatsides(pathend_t *, pathend_t *, int *, int *, int *,
			    int *, int *, int *);
static Agraph_t *cl_bound(Agnode_t *, Agnode_t *);
static int cl_vninside(Agraph_t *, Agnode_t *);
static void completeflatpath(path *, pathend_t *, pathend_t *, int, int,
			     int, int, int, box *, box *, int, int);
static void completeregularpath(path *, Agedge_t *, Agedge_t *,
				pathend_t *, pathend_t *, box *, int, int);
static int edgecmp(Agedge_t **, Agedge_t **);
static Agedge_t *getmainedge(Agedge_t *);
static box makeflatcomponent(box, box, int, int, int, int, int);
static void make_flat_edge(path *, Agedge_t **, int, int);
static box makeflatend(box, int, int, box);
static void make_regular_edge(path *, Agedge_t **, int, int);
static box makeregularend(box, int, int);
static box maximal_bbox(Agnode_t *, Agedge_t *, Agedge_t *);
static Agnode_t *neighbor(Agnode_t *, Agedge_t *, Agedge_t *, int);
static void place_vnlabel(Agnode_t *);
static box rank_box(Agraph_t *, int);
static void recover_slack(Agedge_t *, path *);
static void resize_vn(Agnode_t *, int, int, int);
static void setflags(Agedge_t *, int, int, int);
static int straight_len(Agnode_t *);
static Agedge_t *straight_path(Agedge_t *, int, point *, int *);
static Agedge_t *top_bound(Agedge_t *, int);

#define GROWEDGES (edges = ALLOC (n_edges + CHUNK, edges, edge_t*))

static boolean spline_merge(node_t * n)
{
    return ((ND_node_type(n) == VIRTUAL)
	    && ((ND_in(n).size > 1) || (ND_out(n).size > 1)));
}

static boolean swap_ends_p(edge_t * e)
{
    while (ED_to_orig(e))
	e = ED_to_orig(e);
    if (ND_rank(e->head) > ND_rank(e->tail))
	return FALSE;
    if (ND_rank(e->head) < ND_rank(e->tail))
	return TRUE;
    if (ND_order(e->head) >= ND_order(e->tail))
	return FALSE;
    return TRUE;
}

static splineInfo sinfo = { swap_ends_p, spline_merge };

int portcmp(port p0, port p1)
{
    int rv;
    if (p1.defined == FALSE)
	return (p0.defined ? 1 : 0);
    if (p0.defined == FALSE)
	return -1;
    rv = p0.p.x - p1.p.x;
    if (rv == 0)
	rv = p0.p.y - p1.p.y;
    return rv;
}

/* swap_bezier:
 */
static void swap_bezier(bezier * old, bezier * new)
{
    point *list;
    point *lp;
    point *olp;
    int i, sz;

    sz = old->size;
    list = N_GNEW(sz, point);
    lp = list;
    olp = old->list + (sz - 1);
    for (i = 0; i < sz; i++) {	/* reverse list of points */
	*lp++ = *olp--;
    }

    new->list = list;
    new->size = sz;
    new->sflag = old->eflag;
    new->eflag = old->sflag;
    new->sp = old->ep;
    new->ep = old->sp;
}

/* swap_spline:
 */
static void swap_spline(splines * s)
{
    bezier *list;
    bezier *lp;
    bezier *olp;
    int i, sz;

    sz = s->size;
    list = N_GNEW(sz, bezier);
    lp = list;
    olp = s->list + (sz - 1);
    for (i = 0; i < sz; i++) {	/* reverse and swap list of beziers */
	swap_bezier(olp--, lp++);
    }

    /* free old structures */
    for (i = 0; i < sz; i++)
	free(s->list[i].list);
    free(s->list);

    s->list = list;
}

/* edge_normalize:
 * Some back edges are reversed during layout and the reversed edge
 * is used to compute the spline. We would like to guarantee that
 * the order of control points always goes from tail to head, so
 * we reverse them if necessary.
 */
static void edge_normalize(graph_t * g)
{
    edge_t *e;
    node_t *n;

    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
	for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
	    if (sinfo.swapEnds(e) && ED_spl(e))
		swap_spline(ED_spl(e));
	}
    }
}

/* dot_splines:
 */
void dot_splines(graph_t * g)
{
    int i, j, k, n_nodes, n_edges, ind, cnt;
    node_t *n;
    edge_t fwdedgea, fwdedgeb;
    edge_t *e, *e0, *e1, *ea, *eb, *le0, *le1, **edges;
    path *P;

    mark_lowclusters(g);
    routesplinesinit();
    P = NEW(path);
    /* FlatHeight = 2 * GD_nodesep(g); */
    Splinesep = GD_nodesep(g) / 4;
    Multisep = GD_nodesep(g);
    edges = N_NEW(CHUNK, edge_t *);

    /* compute boundaries and list of splines */
    LeftBound = RightBound = 0;
    n_edges = n_nodes = 0;
    for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
	n_nodes += GD_rank(g)[i].n;
	if ((n = GD_rank(g)[i].v[0]))
	    LeftBound = MIN(LeftBound, (ND_coord_i(n).x - ND_lw_i(n)));
	if (GD_rank(g)[i].n && (n = GD_rank(g)[i].v[GD_rank(g)[i].n - 1]))
	    RightBound = MAX(RightBound, (ND_coord_i(n).x + ND_rw_i(n)));
	LeftBound -= MINW;
	RightBound += MINW;

	for (j = 0; j < GD_rank(g)[i].n; j++) {
	    n = GD_rank(g)[i].v[j];
		/* if n is the label of a flat edge, copy its position to
		 * the label.
		 */
	    if (ND_alg(n)) {
		edge_t* fe = (edge_t*)ND_alg(n);
		assert (ED_label(fe));
		ED_label(fe)->p = ND_coord_i(n);
	    }
	    if ((ND_node_type(n) != NORMAL) &&
		(sinfo.splineMerge(n) == FALSE))
		continue;
	    for (k = 0; (e = ND_out(n).list[k]); k++) {
		if ((ED_edge_type(e) == FLATORDER)
		    || (ED_edge_type(e) == IGNORED))
		    continue;
		setflags(e, REGULAREDGE, FWDEDGE, MAINGRAPH);
		edges[n_edges++] = e;
		if (n_edges % CHUNK == 0)
		    GROWEDGES;
	    }
	    if (ND_flat_out(n).list)
		for (k = 0; (e = ND_flat_out(n).list[k]); k++) {
		    setflags(e, FLATEDGE, 0, AUXGRAPH);
		    edges[n_edges++] = e;
		    if (n_edges % CHUNK == 0)
			GROWEDGES;
		}
	    if (ND_other(n).list) {
		/* In position, each node has its rw stored in mval and,
                 * if a node is part of a loop, rw may be increased to
                 * reflect the loops and associated labels. We restore
                 * the original value here. 
                 */
		if (ND_node_type(n) == NORMAL) {
		    int tmp = ND_rw_i(n);
		    ND_rw_i(n) = ND_mval(n);
		    ND_mval(n) = tmp;
		}
		for (k = 0; (e = ND_other(n).list[k]); k++) {
		    setflags(e, 0, 0, AUXGRAPH);
		    edges[n_edges++] = e;
		    if (n_edges % CHUNK == 0)
			GROWEDGES;
		}
	    }
	}
    }

    /* Sort so that equivalent edges are contiguous. 
     * Equivalence should basically mean that 2 edges has the
     * same set {(tailnode,tailport),(headnode,headport)}, or
     * alternatively, the edges would be routed identically if
     * routed separately.
     */
    qsort((char *) &edges[0], n_edges, sizeof(edges[0]),
	  (qsort_cmpf) edgecmp);

    /* FIXME: just how many boxes can there be? */
    P->boxes = N_NEW(n_nodes + 20 * 2 * NSUB, box);
    Rank_box = N_NEW(i, box);

    for (i = 0; i < n_edges;) {
	ind = i;
	le0 = getmainedge((e0 = edges[i++]));
	ea = (ED_tail_port(e0).defined
	      || ED_head_port(e0).defined) ? e0 : le0;
	if (ED_tree_index(ea) & BWDEDGE) {
	    MAKEFWDEDGE(&fwdedgea, ea);
	    ea = &fwdedgea;
	}
	for (cnt = 1; i < n_edges; cnt++, i++) {
	    if (le0 != (le1 = getmainedge((e1 = edges[i]))))
		break;
	    if (ED_adjacent(e0)) continue; /* all flat adjacent edges at once */
	    eb = (ED_tail_port(e1).defined
		  || ED_head_port(e1).defined) ? e1 : le1;
	    if (ED_tree_index(eb) & BWDEDGE) {
		MAKEFWDEDGE(&fwdedgeb, eb);
		eb = &fwdedgeb;
	    }
	    if (portcmp(ED_tail_port(ea), ED_tail_port(eb)))
		break;
	    if (portcmp(ED_head_port(ea), ED_head_port(eb)))
		break;
	    if ((ED_tree_index(e0) & EDGETYPEMASK) == FLATEDGE
		&& ED_label(e0) != ED_label(e1))
		break;
	    if (ED_tree_index(edges[i]) & MAINGRAPH)	/* Aha! -C is on */
		break;
	}
	if (e0->tail == e0->head)
	    makeSelfEdge(P, edges, ind, cnt, Multisep, &sinfo);
	else if (ND_rank(e0->tail) == ND_rank(e0->head)) {
	    make_flat_edge(P, edges, ind, cnt);
	}
	else
	    make_regular_edge(P, edges, ind, cnt);
    }

    /* place regular edge labels */
    for (n = GD_nlist(g); n; n = ND_next(n)) {
	if ((ND_node_type(n) == VIRTUAL) && (ND_label(n)))
	    place_vnlabel(n);
    }

    /* normalize splines so they always go from tail to head */
    /* place_portlabel relies on this being done first */
    edge_normalize(g);

    /* vladimir: place port labels */
    /* FIX: head and tail labels are not part of cluster bbox */
    if (E_headlabel || E_taillabel) {
	for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
	    if (E_headlabel) {
		for (e = agfstin(g, n); e; e = agnxtin(g, e))
		    if (ED_head_label(e)) {
			place_portlabel(e, TRUE);
			updateBB(g, ED_head_label(e));
		    }
	    }
	    if (E_taillabel) {
		for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
		    if (ED_tail_label(e)) {
			place_portlabel(e, FALSE);
			updateBB(g, ED_tail_label(e));
		    }
		}
	    }
	}
    }
    /* end vladimir */

    free(edges);
    free(P->boxes);
    free(P);
    free(Rank_box);
    routesplinesterm();
    State = GVSPLINES;
}

/* place_vnlabel:
 * assign position of an edge label from its virtual node
 * This is for regular edges only.
 */
static void 
place_vnlabel(node_t * n)
{
    pointf dimen;
    double width;
    edge_t *e;
    if (ND_in(n).size == 0)
	return;			/* skip flat edge labels here */
    for (e = ND_out(n).list[0]; ED_edge_type(e) != NORMAL;
	 e = ED_to_orig(e));
    dimen = ED_label(e)->dimen;
    width = GD_flip(n->graph) ? dimen.y : dimen.x;
    ED_label(e)->p.x = ND_coord_i(n).x + width / 2.0;
    ED_label(e)->p.y = ND_coord_i(n).y;
}

static void 
setflags(edge_t *e, int hint1, int hint2, int f3)
{
    int f1, f2;
    if (hint1 != 0)
	f1 = hint1;
    else {
	if (e->tail == e->head)
	    if (ED_tail_port(e).defined || ED_head_port(e).defined)
		f1 = SELFWPEDGE;
	    else
		f1 = SELFNPEDGE;
	else if (ND_rank(e->tail) == ND_rank(e->head))
	    f1 = FLATEDGE;
	else
	    f1 = REGULAREDGE;
    }
    if (hint2 != 0)
	f2 = hint2;
    else {
	if (f1 == REGULAREDGE)
	    f2 = (ND_rank(e->tail) < ND_rank(e->head)) ? FWDEDGE : BWDEDGE;
	else if (f1 == FLATEDGE)
	    f2 = (ND_order(e->tail) < ND_order(e->head)) ?
		FWDEDGE : BWDEDGE;
	else			/* f1 == SELF*EDGE */
	    f2 = FWDEDGE;
    }
    ED_tree_index(e) = (f1 | f2 | f3);
}

/* edgecmp:
 * lexicographically order edges by
 *  - edge type
 *  - |rank difference of nodes|
 *  - |x difference of nodes|
 *  - id of witness edge for equivalence class
 *  - port comparison
 *  - graph type
 *  - labels if flat edges
 *  - edge id
 */
static int edgecmp(edge_t** ptr0, edge_t** ptr1)
{
    edge_t fwdedgea, fwdedgeb, *e0, *e1, *ea, *eb, *le0, *le1;
    int et0, et1, v0, v1, rv;

    e0 = (edge_t *) * ptr0;
    e1 = (edge_t *) * ptr1;
    et0 = ED_tree_index(e0) & EDGETYPEMASK;
    et1 = ED_tree_index(e1) & EDGETYPEMASK;
    if (et0 != et1)
	return (et1 - et0);
    le0 = getmainedge(e0);
    le1 = getmainedge(e1);
    v0 = ND_rank(le0->tail) - ND_rank(le0->head), v0 = ABS(v0);
    v1 = ND_rank(le1->tail) - ND_rank(le1->head), v1 = ABS(v1);
    if (v0 != v1)
	return (v0 - v1);
    v0 = ND_coord_i(le0->tail).x - ND_coord_i(le0->head).x, v0 = ABS(v0);
    v1 = ND_coord_i(le1->tail).x - ND_coord_i(le1->head).x, v1 = ABS(v1);
    if (v0 != v1)
	return (v0 - v1);
    /* This provides a cheap test for edges having the same set of endpoints.
     */
    if (le0->id != le1->id)
	return (le0->id - le1->id);
    ea = (ED_tail_port(e0).defined || ED_head_port(e0).defined) ? e0 : le0;
    if (ED_tree_index(ea) & BWDEDGE) {
	MAKEFWDEDGE(&fwdedgea, ea);
	ea = &fwdedgea;
    }
    eb = (ED_tail_port(e1).defined || ED_head_port(e1).defined) ? e1 : le1;
    if (ED_tree_index(eb) & BWDEDGE) {
	MAKEFWDEDGE(&fwdedgeb, eb);
	eb = &fwdedgeb;
    }
    if ((rv = portcmp(ED_tail_port(ea), ED_tail_port(eb))))
	return rv;
    if ((rv = portcmp(ED_head_port(ea), ED_head_port(eb))))
	return rv;
    v0 = ED_tree_index(e0) & GRAPHTYPEMASK;
    v1 = ED_tree_index(e1) & GRAPHTYPEMASK;
    if (v0 != v1)
	return (v0 - v1);
    if (et0 == FLATEDGE && ED_label(e0) != ED_label(e1))
	return (int) (ED_label(e0) - ED_label(e1));
    return (e0->id - e1->id);
}

/* fledgecmp:
 * Sort edges by mid y value of ports.
 * If this is the same, and all y values are the same,
 * check if one segment lies within the other.
 */
static int 
fledgecmp(edge_t** ptr0, edge_t** ptr1)
{
    edge_t* e0 = *ptr0;
    edge_t* e1 = *ptr1;
    point tp0, tp1, hp0, hp1;
    tp0 = ED_tail_port(e0).p;
    hp0 = ED_head_port(e0).p;
    tp1 = ED_tail_port(e1).p;
    hp1 = ED_head_port(e1).p;
    int y0 = (tp0.y + hp0.y)/2;
    int y1 = (tp1.y + hp1.y)/2;
    if (y0 != y1) return (y0-y1);
    if ((tp0.y == hp0.y) && (tp1.y == hp1.y)) {
	if ((tp0.x <= tp1.x) && (hp0.x >= hp1.x)) {
	    if (tp0.y <= 0) return -1;
	    else return 1;
	}
	else if ((tp0.x >= tp1.x) && (hp0.x <= hp1.x)) {
	    if (tp0.y <= 0) return 1;
	    else return -1;
	}
    }
    return (e0->id - e1->id);

}

#define LABEL_SPACE 8

/* setFlatAdjPos:
 * Create middle boxes for routing using ordered list of edges going from
 * bottom to top.
 * Also, set label positions.
 */
static void
setFlatAdjPos (edge_t** edges, int n_edges, int flip, box* boxes, edge_t* e0)
{
    int r, i, x, boxw, availht;
    edge_t* e;<commit_msg>fix syntax error<commit_after>/* $Id$ $Revision$ */
/* vim:set shiftwidth=4 ts=8: */

/**********************************************************
*      This software is part of the graphviz package      *
*                http://www.graphviz.org/                 *
*                                                         *
*            Copyright (c) 1994-2004 AT&T Corp.           *
*                and is licensed under the                *
*            Common Public License, Version 1.0           *
*                      by AT&T Corp.                      *
*                                                         *
*        Information and Software Systems Research        *
*              AT&T Research, Florham Park NJ             *
**********************************************************/


/*
 * set edge splines.
 */

#include "dot.h"


#define	NSUB	9		/* number of subdivisions, re-aiming splines */
#define	CHUNK	128		/* in building list of edges */

#define MINW 16			/* minimum width of a box in the edge path */
#define HALFMINW 8

#define FWDEDGE    16
#define BWDEDGE    32

#define MAINGRAPH  64
#define AUXGRAPH  128
#define GRAPHTYPEMASK	192	/* the OR of the above */

#define MAKEFWDEDGE(new, old) { \
	edge_t *newp; \
	newp = new; \
	*newp = *old; \
	newp->tail = old->head; \
	newp->head = old->tail; \
	ED_tail_port(newp) = ED_head_port(old); \
	ED_head_port(newp) = ED_tail_port(old); \
	ED_edge_type(newp) = VIRTUAL; \
	ED_to_orig(newp) = old; \
}

#define P2PF(p, pf) (pf.x = p.x, pf.y = p.y)

static int flatsidemap[16][6] = {
    {BOTTOM, BOTTOM, BOTTOM, CCW, CCW, FALSE},
    {TOP, TOP, TOP, CW, CW, FALSE},
    {RIGHT, LEFT, BOTTOM, CW, CW, TRUE},
    {BOTTOM, TOP, RIGHT, CCW, CW, TRUE},
    {TOP, BOTTOM, RIGHT, CW, CCW, TRUE},
    {RIGHT, TOP, RIGHT, CCW, CW, TRUE},
    {RIGHT, BOTTOM, RIGHT, CW, CCW, TRUE},
    {TOP, LEFT, TOP, CW, CCW, TRUE},
    {BOTTOM, LEFT, BOTTOM, CCW, CW, TRUE},
    {RIGHT, RIGHT, BOTTOM, CW, CCW, TRUE},
    {LEFT, LEFT, BOTTOM, CCW, CW, TRUE},
    {LEFT, BOTTOM, BOTTOM, CCW, CCW, FALSE},
    {TOP, RIGHT, TOP, CW, CW, FALSE},
    {LEFT, TOP, TOP, CW, CW, FALSE},
    {BOTTOM, RIGHT, BOTTOM, CCW, CCW, FALSE},
    {LEFT, RIGHT, BOTTOM, CCW, CCW, FALSE},
};

#define AVG(a, b) ((a + b) / 2)

static int LeftBound, RightBound, /* FlatHeight, */ Splinesep, Multisep;
static box *Rank_box;

static box boxes[1000];

static void adjustregularpath(path *, int, int);
static Agedge_t *bot_bound(Agedge_t *, int);
static unsigned char pathscross(Agnode_t *, Agnode_t *, Agedge_t *,
				Agedge_t *);
static void chooseflatsides(pathend_t *, pathend_t *, int *, int *, int *,
			    int *, int *, int *);
static Agraph_t *cl_bound(Agnode_t *, Agnode_t *);
static int cl_vninside(Agraph_t *, Agnode_t *);
static void completeflatpath(path *, pathend_t *, pathend_t *, int, int,
			     int, int, int, box *, box *, int, int);
static void completeregularpath(path *, Agedge_t *, Agedge_t *,
				pathend_t *, pathend_t *, box *, int, int);
static int edgecmp(Agedge_t **, Agedge_t **);
static Agedge_t *getmainedge(Agedge_t *);
static box makeflatcomponent(box, box, int, int, int, int, int);
static void make_flat_edge(path *, Agedge_t **, int, int);
static box makeflatend(box, int, int, box);
static void make_regular_edge(path *, Agedge_t **, int, int);
static box makeregularend(box, int, int);
static box maximal_bbox(Agnode_t *, Agedge_t *, Agedge_t *);
static Agnode_t *neighbor(Agnode_t *, Agedge_t *, Agedge_t *, int);
static void place_vnlabel(Agnode_t *);
static box rank_box(Agraph_t *, int);
static void recover_slack(Agedge_t *, path *);
static void resize_vn(Agnode_t *, int, int, int);
static void setflags(Agedge_t *, int, int, int);
static int straight_len(Agnode_t *);
static Agedge_t *straight_path(Agedge_t *, int, point *, int *);
static Agedge_t *top_bound(Agedge_t *, int);

#define GROWEDGES (edges = ALLOC (n_edges + CHUNK, edges, edge_t*))

static boolean spline_merge(node_t * n)
{
    return ((ND_node_type(n) == VIRTUAL)
	    && ((ND_in(n).size > 1) || (ND_out(n).size > 1)));
}

static boolean swap_ends_p(edge_t * e)
{
    while (ED_to_orig(e))
	e = ED_to_orig(e);
    if (ND_rank(e->head) > ND_rank(e->tail))
	return FALSE;
    if (ND_rank(e->head) < ND_rank(e->tail))
	return TRUE;
    if (ND_order(e->head) >= ND_order(e->tail))
	return FALSE;
    return TRUE;
}

static splineInfo sinfo = { swap_ends_p, spline_merge };

int portcmp(port p0, port p1)
{
    int rv;
    if (p1.defined == FALSE)
	return (p0.defined ? 1 : 0);
    if (p0.defined == FALSE)
	return -1;
    rv = p0.p.x - p1.p.x;
    if (rv == 0)
	rv = p0.p.y - p1.p.y;
    return rv;
}

/* swap_bezier:
 */
static void swap_bezier(bezier * old, bezier * new)
{
    point *list;
    point *lp;
    point *olp;
    int i, sz;

    sz = old->size;
    list = N_GNEW(sz, point);
    lp = list;
    olp = old->list + (sz - 1);
    for (i = 0; i < sz; i++) {	/* reverse list of points */
	*lp++ = *olp--;
    }

    new->list = list;
    new->size = sz;
    new->sflag = old->eflag;
    new->eflag = old->sflag;
    new->sp = old->ep;
    new->ep = old->sp;
}

/* swap_spline:
 */
static void swap_spline(splines * s)
{
    bezier *list;
    bezier *lp;
    bezier *olp;
    int i, sz;

    sz = s->size;
    list = N_GNEW(sz, bezier);
    lp = list;
    olp = s->list + (sz - 1);
    for (i = 0; i < sz; i++) {	/* reverse and swap list of beziers */
	swap_bezier(olp--, lp++);
    }

    /* free old structures */
    for (i = 0; i < sz; i++)
	free(s->list[i].list);
    free(s->list);

    s->list = list;
}

/* edge_normalize:
 * Some back edges are reversed during layout and the reversed edge
 * is used to compute the spline. We would like to guarantee that
 * the order of control points always goes from tail to head, so
 * we reverse them if necessary.
 */
static void edge_normalize(graph_t * g)
{
    edge_t *e;
    node_t *n;

    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
	for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
	    if (sinfo.swapEnds(e) && ED_spl(e))
		swap_spline(ED_spl(e));
	}
    }
}

/* dot_splines:
 */
void dot_splines(graph_t * g)
{
    int i, j, k, n_nodes, n_edges, ind, cnt;
    node_t *n;
    edge_t fwdedgea, fwdedgeb;
    edge_t *e, *e0, *e1, *ea, *eb, *le0, *le1, **edges;
    path *P;

    mark_lowclusters(g);
    routesplinesinit();
    P = NEW(path);
    /* FlatHeight = 2 * GD_nodesep(g); */
    Splinesep = GD_nodesep(g) / 4;
    Multisep = GD_nodesep(g);
    edges = N_NEW(CHUNK, edge_t *);

    /* compute boundaries and list of splines */
    LeftBound = RightBound = 0;
    n_edges = n_nodes = 0;
    for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
	n_nodes += GD_rank(g)[i].n;
	if ((n = GD_rank(g)[i].v[0]))
	    LeftBound = MIN(LeftBound, (ND_coord_i(n).x - ND_lw_i(n)));
	if (GD_rank(g)[i].n && (n = GD_rank(g)[i].v[GD_rank(g)[i].n - 1]))
	    RightBound = MAX(RightBound, (ND_coord_i(n).x + ND_rw_i(n)));
	LeftBound -= MINW;
	RightBound += MINW;

	for (j = 0; j < GD_rank(g)[i].n; j++) {
	    n = GD_rank(g)[i].v[j];
		/* if n is the label of a flat edge, copy its position to
		 * the label.
		 */
	    if (ND_alg(n)) {
		edge_t* fe = (edge_t*)ND_alg(n);
		assert (ED_label(fe));
		ED_label(fe)->p = ND_coord_i(n);
	    }
	    if ((ND_node_type(n) != NORMAL) &&
		(sinfo.splineMerge(n) == FALSE))
		continue;
	    for (k = 0; (e = ND_out(n).list[k]); k++) {
		if ((ED_edge_type(e) == FLATORDER)
		    || (ED_edge_type(e) == IGNORED))
		    continue;
		setflags(e, REGULAREDGE, FWDEDGE, MAINGRAPH);
		edges[n_edges++] = e;
		if (n_edges % CHUNK == 0)
		    GROWEDGES;
	    }
	    if (ND_flat_out(n).list)
		for (k = 0; (e = ND_flat_out(n).list[k]); k++) {
		    setflags(e, FLATEDGE, 0, AUXGRAPH);
		    edges[n_edges++] = e;
		    if (n_edges % CHUNK == 0)
			GROWEDGES;
		}
	    if (ND_other(n).list) {
		/* In position, each node has its rw stored in mval and,
                 * if a node is part of a loop, rw may be increased to
                 * reflect the loops and associated labels. We restore
                 * the original value here. 
                 */
		if (ND_node_type(n) == NORMAL) {
		    int tmp = ND_rw_i(n);
		    ND_rw_i(n) = ND_mval(n);
		    ND_mval(n) = tmp;
		}
		for (k = 0; (e = ND_other(n).list[k]); k++) {
		    setflags(e, 0, 0, AUXGRAPH);
		    edges[n_edges++] = e;
		    if (n_edges % CHUNK == 0)
			GROWEDGES;
		}
	    }
	}
    }

    /* Sort so that equivalent edges are contiguous. 
     * Equivalence should basically mean that 2 edges has the
     * same set {(tailnode,tailport),(headnode,headport)}, or
     * alternatively, the edges would be routed identically if
     * routed separately.
     */
    qsort((char *) &edges[0], n_edges, sizeof(edges[0]),
	  (qsort_cmpf) edgecmp);

    /* FIXME: just how many boxes can there be? */
    P->boxes = N_NEW(n_nodes + 20 * 2 * NSUB, box);
    Rank_box = N_NEW(i, box);

    for (i = 0; i < n_edges;) {
	ind = i;
	le0 = getmainedge((e0 = edges[i++]));
	ea = (ED_tail_port(e0).defined
	      || ED_head_port(e0).defined) ? e0 : le0;
	if (ED_tree_index(ea) & BWDEDGE) {
	    MAKEFWDEDGE(&fwdedgea, ea);
	    ea = &fwdedgea;
	}
	for (cnt = 1; i < n_edges; cnt++, i++) {
	    if (le0 != (le1 = getmainedge((e1 = edges[i]))))
		break;
	    if (ED_adjacent(e0)) continue; /* all flat adjacent edges at once */
	    eb = (ED_tail_port(e1).defined
		  || ED_head_port(e1).defined) ? e1 : le1;
	    if (ED_tree_index(eb) & BWDEDGE) {
		MAKEFWDEDGE(&fwdedgeb, eb);
		eb = &fwdedgeb;
	    }
	    if (portcmp(ED_tail_port(ea), ED_tail_port(eb)))
		break;
	    if (portcmp(ED_head_port(ea), ED_head_port(eb)))
		break;
	    if ((ED_tree_index(e0) & EDGETYPEMASK) == FLATEDGE
		&& ED_label(e0) != ED_label(e1))
		break;
	    if (ED_tree_index(edges[i]) & MAINGRAPH)	/* Aha! -C is on */
		break;
	}
	if (e0->tail == e0->head)
	    makeSelfEdge(P, edges, ind, cnt, Multisep, &sinfo);
	else if (ND_rank(e0->tail) == ND_rank(e0->head)) {
	    make_flat_edge(P, edges, ind, cnt);
	}
	else
	    make_regular_edge(P, edges, ind, cnt);
    }

    /* place regular edge labels */
    for (n = GD_nlist(g); n; n = ND_next(n)) {
	if ((ND_node_type(n) == VIRTUAL) && (ND_label(n)))
	    place_vnlabel(n);
    }

    /* normalize splines so they always go from tail to head */
    /* place_portlabel relies on this being done first */
    edge_normalize(g);

    /* vladimir: place port labels */
    /* FIX: head and tail labels are not part of cluster bbox */
    if (E_headlabel || E_taillabel) {
	for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
	    if (E_headlabel) {
		for (e = agfstin(g, n); e; e = agnxtin(g, e))
		    if (ED_head_label(e)) {
			place_portlabel(e, TRUE);
			updateBB(g, ED_head_label(e));
		    }
	    }
	    if (E_taillabel) {
		for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
		    if (ED_tail_label(e)) {
			place_portlabel(e, FALSE);
			updateBB(g, ED_tail_label(e));
		    }
		}
	    }
	}
    }
    /* end vladimir */

    free(edges);
    free(P->boxes);
    free(P);
    free(Rank_box);
    routesplinesterm();
    State = GVSPLINES;
}

/* place_vnlabel:
 * assign position of an edge label from its virtual node
 * This is for regular edges only.
 */
static void 
place_vnlabel(node_t * n)
{
    pointf dimen;
    double width;
    edge_t *e;
    if (ND_in(n).size == 0)
	return;			/* skip flat edge labels here */
    for (e = ND_out(n).list[0]; ED_edge_type(e) != NORMAL;
	 e = ED_to_orig(e));
    dimen = ED_label(e)->dimen;
    width = GD_flip(n->graph) ? dimen.y : dimen.x;
    ED_label(e)->p.x = ND_coord_i(n).x + width / 2.0;
    ED_label(e)->p.y = ND_coord_i(n).y;
}

static void 
setflags(edge_t *e, int hint1, int hint2, int f3)
{
    int f1, f2;
    if (hint1 != 0)
	f1 = hint1;
    else {
	if (e->tail == e->head)
	    if (ED_tail_port(e).defined || ED_head_port(e).defined)
		f1 = SELFWPEDGE;
	    else
		f1 = SELFNPEDGE;
	else if (ND_rank(e->tail) == ND_rank(e->head))
	    f1 = FLATEDGE;
	else
	    f1 = REGULAREDGE;
    }
    if (hint2 != 0)
	f2 = hint2;
    else {
	if (f1 == REGULAREDGE)
	    f2 = (ND_rank(e->tail) < ND_rank(e->head)) ? FWDEDGE : BWDEDGE;
	else if (f1 == FLATEDGE)
	    f2 = (ND_order(e->tail) < ND_order(e->head)) ?
		FWDEDGE : BWDEDGE;
	else			/* f1 == SELF*EDGE */
	    f2 = FWDEDGE;
    }
    ED_tree_index(e) = (f1 | f2 | f3);
}

/* edgecmp:
 * lexicographically order edges by
 *  - edge type
 *  - |rank difference of nodes|
 *  - |x difference of nodes|
 *  - id of witness edge for equivalence class
 *  - port comparison
 *  - graph type
 *  - labels if flat edges
 *  - edge id
 */
static int edgecmp(edge_t** ptr0, edge_t** ptr1)
{
    edge_t fwdedgea, fwdedgeb, *e0, *e1, *ea, *eb, *le0, *le1;
    int et0, et1, v0, v1, rv;

    e0 = (edge_t *) * ptr0;
    e1 = (edge_t *) * ptr1;
    et0 = ED_tree_index(e0) & EDGETYPEMASK;
    et1 = ED_tree_index(e1) & EDGETYPEMASK;
    if (et0 != et1)
	return (et1 - et0);
    le0 = getmainedge(e0);
    le1 = getmainedge(e1);
    v0 = ND_rank(le0->tail) - ND_rank(le0->head), v0 = ABS(v0);
    v1 = ND_rank(le1->tail) - ND_rank(le1->head), v1 = ABS(v1);
    if (v0 != v1)
	return (v0 - v1);
    v0 = ND_coord_i(le0->tail).x - ND_coord_i(le0->head).x, v0 = ABS(v0);
    v1 = ND_coord_i(le1->tail).x - ND_coord_i(le1->head).x, v1 = ABS(v1);
    if (v0 != v1)
	return (v0 - v1);
    /* This provides a cheap test for edges having the same set of endpoints.
     */
    if (le0->id != le1->id)
	return (le0->id - le1->id);
    ea = (ED_tail_port(e0).defined || ED_head_port(e0).defined) ? e0 : le0;
    if (ED_tree_index(ea) & BWDEDGE) {
	MAKEFWDEDGE(&fwdedgea, ea);
	ea = &fwdedgea;
    }
    eb = (ED_tail_port(e1).defined || ED_head_port(e1).defined) ? e1 : le1;
    if (ED_tree_index(eb) & BWDEDGE) {
	MAKEFWDEDGE(&fwdedgeb, eb);
	eb = &fwdedgeb;
    }
    if ((rv = portcmp(ED_tail_port(ea), ED_tail_port(eb))))
	return rv;
    if ((rv = portcmp(ED_head_port(ea), ED_head_port(eb))))
	return rv;
    v0 = ED_tree_index(e0) & GRAPHTYPEMASK;
    v1 = ED_tree_index(e1) & GRAPHTYPEMASK;
    if (v0 != v1)
	return (v0 - v1);
    if (et0 == FLATEDGE && ED_label(e0) != ED_label(e1))
	return (int) (ED_label(e0) - ED_label(e1));
    return (e0->id - e1->id);
}

/* fledgecmp:
 * Sort edges by mid y value of ports.
 * If this is the same, and all y values are the same,
 * check if one segment lies within the other.
 */
static int 
fledgecmp(edge_t** ptr0, edge_t** ptr1)
{
    edge_t *e0, *e1;
    point tp0, tp1, hp0, hp1;
    int y0, y1;

    e0 = *ptr0;
    e1 = *ptr1;
    tp0 = ED_tail_port(e0).p;
    hp0 = ED_head_port(e0).p;
    tp1 = ED_tail_port(e1).p;
    hp1 = ED_head_port(e1).p;
    y0 = (tp0.y + hp0.y)/2;
    y1 = (tp1.y + hp1.y)/2;
    if (y0 != y1) return (y0-y1);
    if ((tp0.y == hp0.y) && (tp1.y == hp1.y)) {
	if ((tp0.x <= tp1.x) && (hp0.x >= hp1.x)) {
	    if (tp0.y <= 0) return -1;
	    else return 1;
	}
	else if ((tp0.x >= tp1.x) && (hp0.x <= hp1.x)) {
	    if (tp0.y <= 0) return 1;
	    else return -1;
	}
    }
    return (e0->id - e1->id);

}

#define LABEL_SPACE 8

/* setFlatAdjPos:
 * Create middle boxes for routing using ordered list of edges going from
 * bottom to top.
 * Also, set label positions.
 */
static void
setFlatAdjPos (edge_t** edges, int n_edges, int flip, box* boxes, edge_t* e0)
{
    int r, i, x, boxw, availht;
    edge_t* e;
{'fraction_non_alphanumeric': 0.17019605276077635, 'fraction_numerical': 0.018066965600759335, 'mean_word_length': 2.6963464795548027, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 139, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4517888', 'n_tokens_mistral': 13312, 'n_tokens_neox': 12619, 'n_words': 3159}