
/*
 *
 * vcg.c
 *
 */


#define VCG_CODE


/*
 *
 * Includes.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "types.h"
#include "vcg.h"
#include "assign.h"
#include "channel.h"


/*
 *
 * Code.
 *
 */

void
AllocVCG(void)
{
    VCG = (nodeVCGType *)malloc((channelNets + 1) * sizeof(nodeVCGType));
    storageRootVCG = (constraintVCGType *)malloc((channelNets + 1) * (channelNets + 1) * sizeof(constraintVCGType));
    storageVCG = storageRootVCG;
    storageLimitVCG = (channelNets + 1) * (channelNets + 1);
    SCC = (ulong *)malloc((channelNets + 1) * sizeof(ulong));
    perSCC = (ulong *)malloc((channelNets + 1) * sizeof(ulong));
    removeVCG = (constraintVCGType * *)malloc((channelNets + 1) * (channelNets + 1) * sizeof(constraintVCGType *));
}

void
FreeVCG(void)
{
    free(VCG);
    free(storageRootVCG);
    storageLimitVCG = 0;
    free(SCC);
    free(perSCC);
    free(removeVCG);
}

void
BuildVCG(void)
{
    ulong	col;
    ulong	net;
    ulong	constraint;
    ulong	check;
    ulong	add;

    /*
     * Allocate VCG storage.
     */
    AllocVCG();

    /*
     * Build VCG one net at a time.
     */
    for (net = 1; net <= channelNets; net++) {
	/*
	 * Above constraints.
	 */
	constraint = 0;
	VCG[net].netsAboveHook = storageVCG;
	for (col = 1; col <= channelColumns; col++) {
	    if ((TOP[col] == net) && (BOT[col] != net) && (BOT[col] != 0)) {
		/*
		 * Check constraint already exist.
		 */
		add = TRUE;
		for (check = 0; check < constraint; check++) {
		    if (VCG[net].netsAboveHook[check].bot == BOT[col]) {
			add = FALSE;
			break;
		    }
		}

		/*
		 * Add constraint.
		 */
		if (add) {
		    assert(storageLimitVCG > 0);
		    VCG[net].netsAboveHook[constraint].top = TOP[col];
		    VCG[net].netsAboveHook[constraint].bot = BOT[col];
		    VCG[net].netsAboveHook[constraint].col = col;
		    VCG[net].netsAboveHook[constraint].removed = FALSE;
		    storageVCG++;
		    storageLimitVCG--;
		    constraint++;
		}
	    }
	}
	VCG[net].netsAbove = constraint;

	/*
	 * Below constraints.
	 */
	constraint = 0;
	VCG[net].netsBelowHook = storageVCG;
	for (col = 1; col <= channelColumns; col++) {
	    if ((BOT[col] == net) && (TOP[col] != net) && (TOP[col] != 0)) {
		/*
		 * Check constraint already exist.
		 */
		add = TRUE;
		for (check = 0; check < constraint; check++) {
		    if (VCG[net].netsBelowHook[check].top == TOP[col]) {
			add = FALSE;
			break;
		    }
		}

		/*
		 * Add constraint.
		 */
		if (add) {
		    assert(storageLimitVCG > 0);
		    VCG[net].netsBelowHook[constraint].top = TOP[col];
		    VCG[net].netsBelowHook[constraint].bot = BOT[col];
		    VCG[net].netsBelowHook[constraint].col = col;
		    VCG[net].netsBelowHook[constraint].removed = FALSE;
		    storageVCG++;
		    storageLimitVCG--;
		    constraint++;
		}
	    }
	}
	VCG[net].netsBelow = constraint;
    }
}

void
DFSClearVCG(nodeVCGType * VCG)
{
    ulong	net;

    for (net = 1; net <= channelNets; net++) {
	VCG[net].netsAboveLabel = 0;
	VCG[net].netsAboveReached = FALSE;
	VCG[net].netsBelowLabel = 0;
	VCG[net].netsBelowReached = FALSE;
    }	
}

void
DumpVCG(nodeVCGType * VCG)
{
    ulong	net;
    ulong	which;

    for (net = 1; net <= channelNets; net++) {
	printf("[%d]\n", net);
	printf("above: ");
	for (which = 0; which < VCG[net].netsAbove; which++) {
	    if (! VCG[net].netsAboveHook[which].removed) {
		assert(VCG[net].netsAboveHook[which].top == net);
		printf("%d ", VCG[net].netsAboveHook[which].bot);
	    }
	}

	printf("\n");
	printf("below: ");
	for (which = 0; which < VCG[net].netsBelow; which++) {
	    if (! VCG[net].netsBelowHook[which].removed) {
		assert(VCG[net].netsBelowHook[which].bot == net);
		printf("%d ", VCG[net].netsBelowHook[which].top);
	    }
	}
	printf("\n\n");
    }	
}

void
DFSAboveVCG(nodeVCGType * VCG,
	    ulong net)
{
    ulong	s;
    ulong 	above;

    VCG[net].netsAboveReached = TRUE;
    for (s = 0; s < VCG[net].netsAbove; s++) {
	if (! VCG[net].netsAboveHook[s].removed) {
	    assert(VCG[net].netsAboveHook[s].top == net);
	    above = VCG[net].netsAboveHook[s].bot;
	    if (! VCG[above].netsAboveReached) {
		DFSAboveVCG(VCG, above);
	    }
	}
    }
}

void
DFSBelowVCG(nodeVCGType * VCG,
	    ulong net)
{
    ulong	s;
    ulong 	below;

    VCG[net].netsBelowReached = TRUE;
    for (s = 0; s < VCG[net].netsBelow; s++) {
	if (! VCG[net].netsBelowHook[s].removed) {
	    assert(VCG[net].netsBelowHook[s].bot == net);
	    below = VCG[net].netsBelowHook[s].top;
	    if (! VCG[below].netsBelowReached) {
		DFSBelowVCG(VCG, below);
	    }
	}
    }
}

void
SCCofVCG(nodeVCGType * VCG,
	 ulong * SCC,
	 ulong * perSCC)
{
    ulong      	net;
    ulong      	scc;
    ulong      	per;
    ulong      	label;
    ulong      	which;
    ulong	choose;
    ulong	large;
    ulong	done;
    ;

    /*
     * DFS of above edges.
     */
    label = 0;
    for (net = 1; net <= channelNets; net++){
	if (! VCG[net].netsAboveReached) {
	    SCC_DFSAboveVCG(VCG, net, &label);
	}
    }

    /*
     * DFS of below edges.
     */
    which = 0;
    do {
	done = TRUE;

	/*
	 * Choose not reached net with smallest label.
	 */
	choose = 0;
	large = 0;
	for (net = 1; net <= channelNets; net++) {
	    if (! VCG[net].netsBelowReached) {
		assert(VCG[net].netsAboveLabel > 0);
		if (VCG[net].netsAboveLabel > large) {
		    choose = net;
		    large = VCG[net].netsAboveLabel;
		    done = FALSE;
		}
	    }
	}

	/*
	 * Find all nets in this SCC.
	 */
	if (! done) {
	    which++;
	    SCC_DFSBelowVCG(VCG, choose, which);
	}
    } while (! done);

    /*
     * Identify all SCC.
     */
    totalSCC = 0;
    for (net = 1; net <= channelNets; net++) {
	SCC[net] = VCG[net].netsBelowLabel;
	if (SCC[net] > totalSCC) {
	    totalSCC = SCC[net];
	}
    }
    assert(totalSCC > 0);
    for (scc = 1; scc <= totalSCC; scc++) {
	per = 0;
	for (net = 1; net <= channelNets; net++) {
	    if (SCC[net] == scc) {
		per++;
	    }
	}
	perSCC[scc] = per;
    }
    ;
}

void
SCC_DFSAboveVCG(nodeVCGType * VCG,
		ulong net,
		ulong * label)
{
    ulong	s;
    ulong 	above;

    VCG[net].netsAboveReached = TRUE;
    for (s = 0; s < VCG[net].netsAbove; s++) {
	if (! VCG[net].netsAboveHook[s].removed) {
	    assert(VCG[net].netsAboveHook[s].top == net);
	    above = VCG[net].netsAboveHook[s].bot;
	    if (! VCG[above].netsAboveReached) {
		SCC_DFSAboveVCG(VCG, above, label);
	    }
	}
    }
    (*label)++;
    VCG[net].netsAboveLabel = *label;
}

void
SCC_DFSBelowVCG(nodeVCGType * VCG,
		ulong net,
		ulong label)
{
    ulong	s;
    ulong 	below;

    VCG[net].netsBelowReached = TRUE;
    for (s = 0; s < VCG[net].netsBelow; s++) {
	if (! VCG[net].netsBelowHook[s].removed) {
	    assert(VCG[net].netsBelowHook[s].bot == net);
	    below = VCG[net].netsBelowHook[s].top;
	    if (! VCG[below].netsBelowReached) {
		SCC_DFSBelowVCG(VCG, below, label);
	    }
	}
    }
    VCG[net].netsBelowLabel = label;
}

void
DumpSCC(ulong * SCC,
	ulong * perSCC)
{
    ulong	net;
    ulong	scc;

    for (scc = 1; scc <= totalSCC; scc++) {
	printf("[%d]\t", scc);
	for (net = 1; net <= channelNets; net++) {
	    if (SCC[net] == scc) {
		printf("%d ", net);
	    }
	}
	printf("<%d>", perSCC[scc]);
	printf("\n");
    }
    printf("\n");
}

void
AcyclicVCG(void)
{
    ulong	done;
    ulong	scc;
    ulong	net;
    ulong      	top;
    ulong	bot;
    ulong	rep;
    ulong	which;
    ulong     	total;
    ulong     	cycle;
    ulong	acyclic;

    for (net = 1; net <= channelNets; net++) {
	for (which = 0; which < VCG[net].netsAbove; which++) {
	    VCG[net].netsAboveHook[which].removed = FALSE;
	}
	for (which = 0; which < VCG[net].netsBelow; which++) {
	    VCG[net].netsBelowHook[which].removed = FALSE;
	}
    }	

    acyclic = TRUE;
    removeTotalVCG = 0;
    do {
	done = TRUE;

	/*
	 * Check acyclic (and more).
	 */
	DFSClearVCG(VCG);
	SCCofVCG(VCG, SCC, perSCC);
	for (scc = 1; scc <= totalSCC; scc++) {
	    if (perSCC[scc] > 1) {
		acyclic = FALSE;
		done = FALSE;
		break;
	    }
	}

	/*
	 * Attempt to eliminate cycles by the
	 * removal of a constraint from each SCC.
	 */
	if (! done) {
	    RemoveConstraintVCG(VCG, SCC, perSCC, removeVCG);
	}
    } while (! done);

    /*
     * Replace redundant constraints.
     * That is, those constraints which were removed
     * but can be added back without introducing a cycle.
     */
    total = removeTotalVCG;
    for (rep = 0; rep < removeTotalVCG; rep++) {
	/*
	 * Constraint to consider.
	 */
	
	top = (*removeVCG[rep]).top;
	bot = (*removeVCG[rep]).bot;

	/*
	 * Replace above.
	 */
	for (which = 0; which < VCG[top].netsAbove; which++) {
	    if (VCG[top].netsAboveHook[which].bot == bot) {
		VCG[top].netsAboveHook[which].removed = FALSE;
		break;
	    }
	}
	
	/*
	 * Replace below.
	 */
	for (which = 0; which < VCG[bot].netsBelow; which++) {
	    if (VCG[bot].netsBelowHook[which].top == top) {
		VCG[bot].netsBelowHook[which].removed = FALSE;
		break;
	    }
	}

	/*
	 * Does replacement introduce a cycle?
	 */
	cycle = FALSE;
	DFSClearVCG(VCG);
	SCCofVCG(VCG, SCC, perSCC);
	for (scc = 1; scc <= totalSCC; scc++) {
	    if (perSCC[scc] > 1) {
		cycle = TRUE;
		break;
	    }
	}
	if (cycle) {
	    /*
	     * Introduces cycle.
	     * Remove constraint (again).
	     */
	    for (which = 0; which < VCG[top].netsAbove; which++) {
		if (VCG[top].netsAboveHook[which].bot == bot) {
		    VCG[top].netsAboveHook[which].removed = TRUE;
		    break;
		}
	    }
	    for (which = 0; which < VCG[bot].netsBelow; which++) {
		if (VCG[bot].netsBelowHook[which].top == top) {
		    VCG[bot].netsBelowHook[which].removed = TRUE;
		    break;
		}
	    }
	}
	else {
	    /*
	     * Does not introduce cycle.
	     * Replace ok.
	     */
	    total--;
	}
    }

    if (acyclic) {
	printf("\n*** Input is acyclic! ***\n");
    }
    else {
	printf("\n*** Input is cyclic! ***\n");
	printf("*** VC's removed (%d) ***\n", total);
    }
}

void
RemoveConstraintVCG(nodeVCGType * VCG,
		    ulong * SCC,
		    ulong * perSCC,
		    constraintVCGType * * removeVCG)
{
    ulong			scc;
    ulong			net;
    ulong			which;
    ulong			best;
    ulong			weight;
    ulong			top;
    ulong			bot;
    ulong			col;
    constraintVCGType *	remove;

    for (scc = 1; scc <= totalSCC; scc++) {
	/*
	 * For each SCC attempt to remove cycle.
	 */
	if (perSCC[scc] > 1) {
	    /*
	     * SCC of more than one net in SCC, thus cycle.
	     */
	    remove = NULL;
	    best = FULL + 1;
	    for (net = 1; net <= channelNets; net++) {
		/*
		 * For each net in the SCC.
		 */
		if (SCC[net] == scc) {
		    /*
		     * Choose constraint to remove.
		     * Consider only constraints within SCC.
		     */
		    for (which = 0; which < VCG[net].netsAbove; which++) {
			bot = VCG[net].netsAboveHook[which].bot;
			if ((SCC[bot] == scc) && (! VCG[net].netsAboveHook[which].removed)) {
			    /*
			     * Constraint within SCC.
			     * Weigh its removal.
			     */

			    /*
			     * Note: we consider the column from which the
			     * constraint was added only.  That is, since
			     * we do not add the same constraint twice, only
			     * first occurrence of the constraint has the
			     * column location registered.  Thus, when the
			     * columns are inspected to choose the easiest to
			     * route constraint to remove, the weight of the
			     * chosen constraint will only reflect that single
			     * column.  This may lead to a poor choice, but
			     * it is not likely to occur in practice, and it
			     * is not worth the effort to handle the problem.
			     */
			    col = VCG[net].netsAboveHook[which].col;
			    weight = 0;
			    if (col == 1) {
				weight += 3; /* no left column */
				if (TOP[col+1] && BOT[col+1]) {
				    weight += 3;
				}
				else if (! (TOP[col+1] || BOT[col+1])) {
				}
				else {
				    weight += 2;
				}
			    }
			    else if (col == channelColumns) {
				weight += 3; /* no right column */
				if (TOP[col-1] && BOT[col-1]) {
				    weight += 3;
				}
				else if (! (TOP[col-1] || BOT[col-1])) {
				}
				else {
				    weight += 2;
				}
			    }
			    else {
				if (TOP[col-1] && BOT[col-1]) {
				    weight += 3;
				}
				else if (! (TOP[col-1] || BOT[col-1])) {
				}
				else {
				    weight += 2;
				}
				if (TOP[col+1] && BOT[col+1]) {
				    weight += 3;
				}
				else if (! (TOP[col+1] || BOT[col+1])) {
				}
				else {
				    weight += 2;
				}
			    }
			    
			    /*
			     * Update best.
			     */
			    if (weight < best) {
				best = weight;
				remove = &VCG[net].netsAboveHook[which];
			    }
			}
		    }
		}
	    }

	    /*
	     * Remove.
	     */
	    assert(remove != NULL);
	    fflush(stdout);
	    assert(removeTotalVCG < ((channelNets + 1) * (channelNets + 1)));
	    removeVCG[removeTotalVCG] = remove;
	    removeTotalVCG++;
	    top = (*remove).top;
	    bot = (*remove).bot;

	    /*
	     * Remove above constraint.
	     */
	    (*remove).removed = TRUE;

	    /*
	     * Remove below constraint.
	     */
	    for (which = 0; which < VCG[bot].netsBelow; which++) {
		if (VCG[bot].netsBelowHook[which].top == top) {
		    VCG[bot].netsBelowHook[which].removed = TRUE;
		    break;
		}
	    }
	}
    }
}

ulong
ExistPathAboveVCG(nodeVCGType * VCG,
		  ulong above,
		  ulong below)
{
    DFSClearVCG(VCG);
    DFSAboveVCG(VCG, above);
    return(VCG[below].netsAboveReached);
}

void
LongestPathVCG(nodeVCGType * VCG,
	       ulong net)
{
    ulong	track;
    ulong	bot;
    ulong	top;
    ulong	not;

    /*
     * How many nets this net is above (including this net)?
     * That is, longest path through nets which this net
     * is above.
     */
    DFSClearVCG(VCG);
    cardBotNotPref = DFSAboveLongestPathVCG(VCG, net) - 1;
    bot = cardBotNotPref;
    for (track = channelTracks; track >= 1; track--) {
	if (bot > 0) {
	    tracksBotNotPref[track] = TRUE;
	    bot--;
	}
	else {
	    tracksBotNotPref[track] = FALSE;
	}
    }
    
    /*
     * How many nets this net is below (including this net)?
     * That is, longest path through nets which this net
     * is below.
     */
    DFSClearVCG(VCG);
    cardTopNotPref = DFSBelowLongestPathVCG(VCG, net) - 1;
    top = cardTopNotPref;
    for (track = 1; track <= channelTracks; track++) {
	if (top > 0) {
	    tracksTopNotPref[track] = TRUE;
	    top--;
	}
	else {
	    tracksTopNotPref[track] = FALSE;
	}
    }

    /*
     * How many tracks are guaranteed to make an HCV?
     * That is, what tracks contain nets which this
     * net must either be above or below.
     */

    not = 0;
    for (track = 1; track <= channelTracks; track++) {
	if (tracksTopNotPref[track] || tracksBotNotPref[track]) {
	    tracksNotPref[track] = TRUE;
	    not++;
	}
	else {
	    tracksNotPref[track] = FALSE;
	}
    }
    cardNotPref = not;
}

ulong
DFSAboveLongestPathVCG(nodeVCGType * VCG,
		       ulong net)
{
    ulong	s;
    ulong 	above;
    ulong	path;
    ulong	longest;

    longest = 0;
    VCG[net].netsAboveReached = TRUE;
    for (s = 0; s < VCG[net].netsAbove; s++) {
	if (! VCG[net].netsAboveHook[s].removed) {
	    assert(VCG[net].netsAboveHook[s].top == net);
	    above = VCG[net].netsAboveHook[s].bot;
	    if (! VCG[above].netsAboveReached) {
		path = DFSAboveLongestPathVCG(VCG, above);
		if (path > longest) {
		    longest = path;
		}
	    }
	}
    }
    return(longest+1);
}

ulong
DFSBelowLongestPathVCG(nodeVCGType * VCG,
		       ulong net)
{
    ulong	s;
    ulong 	below;
    ulong	path;
    ulong	longest;

    longest = 0;
    VCG[net].netsBelowReached = TRUE;
    for (s = 0; s < VCG[net].netsBelow; s++) {
	if (! VCG[net].netsBelowHook[s].removed) {
	    assert(VCG[net].netsBelowHook[s].bot == net);
	    below = VCG[net].netsBelowHook[s].top;
	    if (! VCG[below].netsBelowReached) {
		path = DFSBelowLongestPathVCG(VCG, below);
		if (path > longest) {
		    longest = path;
		}
	    }
	}
    }
    return(longest+1);
}

ulong
VCV(nodeVCGType * VCG,
    ulong check,
    ulong track,
    ulong * assign)
{
    ulong	net;
    ulong	vcv;

    vcv = 0;
    for (net = 1; net <= channelNets; net++) {
	if (assign[net]) {
	    if (assign[net] < track) {
		/*
		 * Above VCV?
		 */
		if (ExistPathAboveVCG(VCG, net, check)) {
		    vcv++;
		}
	    }
	    else if (assign[net] > track) {
		/*
		 * Below VCV?
		 */
		if (ExistPathAboveVCG(VCG, check, net)) {
		    vcv++;
		}
	    }
	    else {
		/*
		 * Above or Below VCV?
		 */
		if (ExistPathAboveVCG(VCG, net, check) || ExistPathAboveVCG(VCG, check, net)) {
		    vcv++;
		}
	    }
	}
    }
    return(vcv);
}