/* $Id: cmpnd.c,v 1.3 2009/06/03 01:10:51 ellson Exp $ $Revision: 1.3 $ */
/* 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             *
**********************************************************/

#include <cghdr.h>

/*
 * provides "compound nodes" on top of base Libgraph.
 * a compound node behaves as both an ordinary node and a subgraph.
 * there are additional primitives to "hide" and "expose" its contents.
 *
 * you could think of these as hypergraphs, but there is an assymetry
 * in the operations we have chosen.  i.e. nodes "own" their edges,
 * but nodes and interior edges are "owned by" the hyperedges.
 * also the subgraphs are nested, etc.   the bottom line is that graphs
 * and hypergraphs are just sets, everything else here is convenience
 * and maintaining consistency.
 *
 * this package adds a primitive "agsplice" to move endpoints of edges.
 * this could be useful in other situations.
 */

static char Descriptor_id[] = "AG_cmpnd";

typedef struct Agcmpnode_s {
    Agrec_t hdr;
    Agraph_t *subg;
    int collapsed;
} Agcmpnode_t;

typedef struct Agcmpgraph_s {
    Agrec_t hdr;
    Agnode_t *node;		/* its associated node */
    Dict_t *hidden_node_set;
} Agcmpgraph_t;

typedef struct save_e_s {
    Agnode_t *from, *to;
} save_e_t;

typedef struct save_stack_s {
    save_e_t *mem;
    int stacksize;
} save_stack_t;

typedef struct Agcmpedge_s {
    Agrec_t hdr;
    save_stack_t stack[2];	/* IN and OUT save stacks */
} Agcmpedge_t;
#define IN_STACK 0
#define OUT_STACK 1

static save_stack_t *save_stack_of(Agedge_t * e,
				   Agnode_t * node_being_saved)
{
    int i;
    Agcmpedge_t *edgerec;
    edgerec =
	(Agcmpedge_t *) agbindrec(e, Descriptor_id, sizeof(*edgerec),
				  FALSE);
    if (node_being_saved == AGHEAD(e))
	i = IN_STACK;
    else
	i = OUT_STACK;
    return &(edgerec->stack[i]);
}

static void stackpush(save_stack_t * stk, Agnode_t * from, Agnode_t * to)
{
    int i, osize, nsize;

    osize = (stk->stacksize) * sizeof(stk->mem);
    i = stk->stacksize++;
    nsize = (stk->stacksize) * sizeof(stk->mem);
    stk->mem = agrealloc(agraphof(from), stk->mem, osize, nsize);
    stk->mem[i].from = from;
    stk->mem[i].to = to;
}

static save_e_t stacktop(save_stack_t * stk)
{
    save_e_t rv;
    if (stk->stacksize > 0)
	rv = stk->mem[stk->stacksize - 1];
    else
	rv.from = rv.to = NILnode;
    return rv;
}

/* note: doesn't give back mem, but stackpush() eventually does */
static save_e_t stackpop(save_stack_t * stk)
{
    save_e_t rv;
    rv = stacktop(stk);
    if (stk->stacksize > 0)
	stk->stacksize--;
    return rv;
}

typedef struct Agsplice_arg_s {
    int head_side;
    Agnode_t *target;
} Agsplice_arg_t;

/* perform a splice operation on an individual edge */
static void splice(Agobj_t * obj, void *arg)
{
    Agraph_t *g;
    Agedge_t *e, *opp;
    Agnode_t *target, *t, *h;
    Agedge_t **dict_of_del, **dict_of_ins, **dict_of_relabel;
    Agsplice_arg_t *spl;

    e = (Agedge_t *) obj;
    g = agraphof(e);
    t = AGTAIL(e);
    h = AGHEAD(e);
    opp = AGOPP(e);
    spl = arg;
    target = spl->target;

    /* set e to variant side, opp to invariant */
    if ((e->node == h) != spl->head_side) {
	Agedge_t *t = e;
	e = opp;
	opp = t;
    }

    if (spl->head_side) {
	dict_of_relabel = &(t->out);
	dict_of_del = &(h->in);
	dict_of_ins = &(target->in);
    } else {
	dict_of_relabel = &(h->in);
	dict_of_del = &(t->out);
	dict_of_ins = &(target->out);
    }

    agdeledgeimage(g, dict_of_del, opp);
    agdeledgeimage(g, dict_of_relabel, e);
    e->node = target;
    aginsedgeimage(g, dict_of_ins, opp);
    aginsedgeimage(g, dict_of_relabel, e);
}

int agsplice(Agedge_t * e, Agnode_t * target)
{
    Agnode_t *t, *h;
    Agraph_t *g, *root;
    Agsplice_arg_t splice_arg;


    if ((e == NILedge) || (e->node == target))
	return FAILURE;
    g = agraphof(e);
    t = AGTAIL(e);
    h = AGHEAD(e);
    splice_arg.head_side = (e->node == h);
    splice_arg.target = target;
    root = agroot(g);
    agapply(root, (Agobj_t *) e, splice, &splice_arg, TRUE);
    return SUCCESS;
}

Agnode_t *agcmpnode(Agraph_t * g, char *name)
{
    Agnode_t *n;
    Agraph_t *subg;
    n = agnode(g, name, TRUE);
    subg = agsubg(g, name);
    if (n && g && agassociate(n, subg))
	return n;
    else
	return NILnode;
}

int agassociate(Agnode_t * n, Agraph_t * sub)
{
    Agcmpnode_t *noderec;
    Agcmpgraph_t *graphrec;

    if (agsubnode(sub, n, FALSE))
	return FAILURE;		/* avoid cycles */
    noderec = agbindrec(n, Descriptor_id, sizeof(*noderec), FALSE);
    graphrec = agbindrec(sub, Descriptor_id, sizeof(*graphrec), FALSE);
    if (noderec->subg || graphrec->node)
	return FAILURE;
    noderec->subg = sub;
    graphrec->node = n;
    return SUCCESS;
}

/* a utility function for aghide */
static void delete_outside_subg(Agraph_t * g, Agnode_t * node,
				Agraph_t * subg)
{
    Agraph_t *s, **subglist;
    Agnode_t *n;
    Agcmpgraph_t *graphrec;
    Dict_t *d;

    if ((g != subg) && (n = agsubnode(g, (Agnode_t *) node, FALSE))) {
	dtdelete(g->n_dict, n);

	graphrec = agbindrec(g, Descriptor_id, sizeof(*graphrec), FALSE);
	if ((d = graphrec->hidden_node_set) == NIL(Dict_t *)) {
	    /* use name disc. to permit search for hidden node by name */
	    d = graphrec->hidden_node_set
		= agdtopen(g, &Ag_node_name_disc, Dttree);
	}
	dtinsert(d, n);

	subglist = agsubglist(g);
	while ((s = *subglist++))
	    delete_outside_subg(s, node, subg);
    }
}

/*
 *  when we hide a compound node (make it opaque)
 *	1. hide its nodes (option)
 *	2. hide the associated subgraph (option)
 *	3. remap edges to internal nodes (option)
 */
int aghide(Agnode_t * cmpnode)
{
    Agcmpnode_t *noderec;
    Agraph_t *g, *subg, *root;
    Agnode_t *n, *nn, *rootn;
    Agedge_t *e, *opp, *f;

    g = agraphof(cmpnode);
    /* skip operation if node is not compound, or hidden */
    if (agcmpgraph_of(cmpnode) == NILgraph)
	return FAILURE;
    noderec = (Agcmpnode_t *) aggetrec(cmpnode, Descriptor_id, FALSE);

    subg = noderec->subg;
    root = agroot(g);

    /* make sure caller hasn't put a node "inside itself" */
    if ((n = agsubnode(subg, cmpnode, FALSE)))
	agdelnode(n);

    /* remap edges by splicing and saving previous endpt */
    for (n = agfstnode(subg); n; n = agnxtnode(n)) {
	rootn = agsubnode(root, n, FALSE);
	for (e = agfstedge(rootn); e; e = f) {
	    f = agnxtedge(e, rootn);
	    if (agsubedge(subg, e, FALSE))
		continue;	/* an internal edge */
	    opp = AGOPP(e);
	    stackpush(save_stack_of(e, rootn), rootn, cmpnode);
	    agsplice(opp, cmpnode);
	}
    }

    /* hide nodes by deleting from the parent set.  what if they also
       belong to a sibling subg?  weird. possible bug. */
    for (n = agfstnode(subg); n; n = nn) {
	nn = agnxtnode(n);
	delete_outside_subg(root, n, subg);
    }

    /* hide subgraph is easy */
    agdelsubg(agparent(subg), subg);

    noderec->collapsed = TRUE;
    g->desc.has_cmpnd = TRUE;
    return SUCCESS;
}

/* utility function for agexpose */
static void insert_outside_subg(Agraph_t * g, Agnode_t * node,
				Agraph_t * subg)
{
    Agraph_t *s, **subglist;
    Agnode_t *n;
    Agcmpgraph_t *graphrec;

    if ((g != subg)
	&& ((n = agsubnode(g, (Agnode_t *) node, FALSE)) == NILnode)) {
	graphrec = (Agcmpgraph_t *) aggetrec(g, Descriptor_id, FALSE);
	if (graphrec
	    &&
	    ((n = (Agnode_t *) dtsearch(graphrec->hidden_node_set, node))))
	    dtinsert(g->n_dict, n);

	subglist = agsubglist(g);
	while ((s = *subglist++))
	    delete_outside_subg(s, node, subg);
    }
}

int agexpose(Agnode_t * cmpnode)
{
    Agcmpnode_t *noderec;
    Agcmpedge_t *edgerec;
    Agraph_t *g, *subg, *root;
    Agnode_t *n, *rootcmp;
    Agedge_t *e, *f;
    save_stack_t *stk;
    save_e_t sav;
    int i;

    g = agraphof(cmpnode);

    /* skip if this is not a collapsed subgraph */
    noderec = (Agcmpnode_t *) aggetrec(cmpnode, Descriptor_id, FALSE);
    if ((noderec == NIL(Agcmpnode_t *) || NOT(noderec->collapsed)))
	return FAILURE;

    /* undo aghide (above) in reverse order.  first, expose subgraph */
    subg = noderec->subg;
    agsubgrec_insert(agsubgrec(agparent(subg)), subg);

    /* re-insert nodes */
    for (n = agfstnode(subg); n; n = agnxtnode(n))
	insert_outside_subg(g, n, subg);

    /* re-splice the affected edges */
    root = agroot(g);
    rootcmp = agsubnode(root, cmpnode, FALSE);
    for (e = agfstedge(rootcmp); e; e = f) {
	f = agnxtedge(e, rootcmp);
	if ((edgerec = (Agcmpedge_t *) aggetrec(e, Descriptor_id, FALSE))) {
	    /* anything interesting on either stack? */
	    for (i = 0; i < 2; i++) {
		stk = &(edgerec->stack[i]);
		sav = stacktop(stk);
		if (sav.to && (AGID(sav.to) == AGID(cmpnode))) {
		    if (e->node != sav.to)
			e = AGOPP(e);
		    agsplice(e, sav.from);
		    stackpop(stk);
		    continue;
		}
	    }
	}
    }
    noderec->collapsed = FALSE;
    return SUCCESS;
}

Agraph_t *agcmpgraph_of(Agnode_t * n)
{
    Agcmpnode_t *noderec;
    noderec = (Agcmpnode_t *) aggetrec(n, Descriptor_id, FALSE);
    if (noderec && NOT(noderec->collapsed))
	return noderec->subg;
    else
	return NILgraph;
}

Agnode_t *agcmpnode_of(Agraph_t * g)
{
    Agcmpgraph_t *graphrec;
    graphrec = (Agcmpgraph_t *) aggetrec(g, Descriptor_id, FALSE);
    if (graphrec)
	return graphrec->node;
    else
	return NILnode;
}

Agnode_t *agfindhidden(Agraph_t * g, char *name)
{
    Agcmpgraph_t *graphrec;
    Agnode_t key;

    graphrec = (Agcmpgraph_t *) aggetrec(g, Descriptor_id, FALSE);
    if (graphrec) {
	key.name = name;
	return (Agnode_t *) dtsearch(graphrec->hidden_node_set, &key);
    } else
	return NILnode;
}