#include "custom.h"
#include "23tree.h"
int *how_many;

extern void tdelete( TNODEPTR *root , int value , int property );
extern void tpop( TNODEPTR *root , TNODEPTR *node , int *value ,
		 int *property);
extern double wireratio( int numofcells, double cellspernet, double netsperd,
			double dnetspercell );

void qsortx(char *base, int n, int size);
void qst(char *base, char *max);

double analyze(void)
{

int **number , i , net , net1 , net2 , num , cell ;
int *count , different , cnum , c2num , *arraynet ;
int num_nets , tot_cels ;
double C , C1 , ratio ;
#ifdef notdef
double C2 , C3;
#endif
NETBOXPTR netptr ;


count  = (int *) malloc( (1 + numcells) * sizeof( int ) ) ;
number = (int **) malloc( (1 + numnets) * sizeof( int *) ) ;
how_many = (int *) malloc( (1 + numnets) * sizeof( int ) ) ;
arraynet = (int *) malloc( (1 + numnets) * sizeof( int ) ) ;
for( net = 0 ; net <= numnets ; net++ ) {
    number[net] = (int *) malloc( (1 + numcells) * sizeof(int) ) ;
}

for( net = 1 ; net <= numnets ; net++ ) {
    for( cell = 0 ; cell <= numcells ; cell++ ) {
	count[cell] = 0 ;
	number[net][cell] = 0 ;
    }
    netptr = netarray[net]->netptr ;
    for( ; netptr != (NETBOXPTR) NULL ; netptr = netptr->nextterm ){
	if( netptr->cell <= numcells ) {
	    count[netptr->cell] = 1 ;
	}
    }
    /*
     *  I would like to find the number of distinct nets
     */
    for( cell = 1 ; cell <= numcells ; cell++ ) { 
	if( count[cell] == 1 ) {
	    number[net][ ++number[net][0] ] = cell ;
	}
    }
}
/* ********************************************************** */
num_nets = 0 ;
tot_cels = 0 ;
for( net1 = 1 ; net1 <= numnets ; net1++ ) {
    if( number[net1][0] <= 1 ) {
	continue ;
    }
    num_nets++ ;
    tot_cels += number[net1][0] ;
}


fprintf(fpo,"\n\n*************************************\n");
fprintf(fpo,"AVERAGE NUMBER OF CELLS PER NET: %f\n",
		(double) tot_cels / (double) num_nets	) ;
fprintf(fpo,"*************************************\n\n\n");
/* ********************************************************** */
for( net1 = 1 ; net1 <= numnets ; net1++ ) {
    if( number[net1][0] == 0 ) {
	how_many[net1] = 0 ;
	continue ;
    }
    if( number[net1][0] == 1 ) {
	number[net1][0] = 0 ;
	how_many[net1] = 0 ;
	continue ;
    }
    how_many[net1] = 1 ;
    for( net2 = net1 + 1 ; net2 <= numnets ; net2++ ) {
	if( number[net2][0] != number[net1][0] ) {
	    continue ;
	}
	different = 0 ;
	for( i = 1 ; i <= numcells ; i++ ) {
	    if( number[net2][i] != number[net1][i] ) {
		different = 1 ;
		break ;
	    }
	}
	if( ! different ) {
	    number[net2][0] = 0 ;
	    how_many[net1]++ ;
	}
    }
}

arraynet[0] = 0 ;
for( net = 1 ; net <= numnets ; net++ ) {
    if( how_many[net] <= 0 ) {
	continue ;
    }
    arraynet[ ++arraynet[0] ] = net ;
}
num = arraynet[0] ;
arraynet[0] = arraynet[ arraynet[0] ] ;
qsortx( (char *) arraynet ,  num , sizeof( int ) ) ;
/*  sorted: most occurrences first  */

num = 0 ;
cnum = 0 ;
c2num = 0 ;
for( net = 1 ; net <= numnets ; net++ ) {
    if( number[net][0] > 0 ) {
	cnum += number[net][0] - 1 ;
	c2num += number[net][0] ;
	num++ ;
    }
}
C = (double) num / (double) numcells ;
C1 = (double) cnum / (double) num ;

#ifdef notdef
C2 = (double) c2num / (double) num ;
C3 = (double) cnum / (double)(numcells - 1) ;

fprintf(fpo,"\n\n\n**********************************************\n\n");
fprintf(fpo,"The average number of distinct nets per cell is\n");
fprintf(fpo,"given by: %6.2f\n\n", C );
fprintf(fpo,"The average number of cells per net is\n");
fprintf(fpo,"given by: %6.2f\n\n", C2 );
fprintf(fpo,"The average number of other cells per net is\n");
fprintf(fpo,"given by: %6.2f\n\n", C1 );
fprintf(fpo,"The ratio of total cells specified per net to\n");
fprintf(fpo,"numcells is given by: %6.2f\n\n", C3 );
fprintf(fpo,"The average number of cells connected to a cell is\n");
fprintf(fpo,"given by: %6.2f\n\n", C * C1 );
fprintf(fpo,"**********************************************\n\n\n");
#endif

ratio = wireratio( numcells, C1, 
		((double) numnets / (double) numcells) / C , C ) ;

fprintf(fpo,"Expected Wire Reduction Relative to Random:%6.2f\n\n",ratio);
fflush(fpo);

return( ratio );
}


int comparex( int *a , int *b )
{
    return( how_many[*b] - how_many[*a] ) ;
}


/* @(#)qsort.c	4.2 (Berkeley) 3/9/83 */


#define		THRESH		4	/* threshold for insertion */
#define		MTHRESH		6	/* threshold for median */

int	qsz;			/* size of each record */
int	thresh;			/* THRESHold in chars */
int	mthresh;		/* MTHRESHold in chars */


void qsortx(char *base, int n, int size)
{
	register char c, *i, *j, *lo, *hi;
	char *min, *max;

	if (n <= 1)
		return;
	qsz = size;
	thresh = qsz * THRESH;
	mthresh = qsz * MTHRESH;
	max = base + n * qsz;
	if (n >= THRESH) {
		qst(base, max);
		hi = base + thresh;
	} else {
		hi = max;
	}
	/*
	 * First put smallest element, which must be in the first THRESH, in
	 * the first position as a sentinel.  This is done just by searching
	 * the first THRESH elements (or the first n if n < THRESH), finding
	 * the min, and swapping it into the first position.
	 */
	for (j = lo = base; (lo += qsz) < hi; )
		if (comparex(j, lo) > 0)
			j = lo;
	if (j != base) {
		/* swap j into place */
		for (i = base, hi = base + qsz; i < hi; ) {
			c = *j;
			*j++ = *i;
			*i++ = c;
		}
	}
	/*
	 * With our sentinel in place, we now run the following hyper-fast
	 * insertion sort.  For each remaining element, min, from [1] to [n-1],
	 * set hi to the index of the element AFTER which this one goes.
	 * Then, do the standard insertion sort shift on a character at a time
	 * basis for each element in the frob.
	 */
	for (min = base; (hi = min += qsz) < max; ) {
		while (comparex(hi -= qsz, min) > 0)
			/* void */;
		if ((hi += qsz) != min) {
			for (lo = min + qsz; --lo >= min; ) {
				c = *lo;
				for (i = j = lo; (j -= qsz) >= hi; i = j)
					*i = *j;
				*i = c;
			}
		}
	}
}

/*
 * qst:
 * Do a quicksort
 * First, find the median element, and put that one in the first place as the
 * discriminator.  (This "median" is just the median of the first, last and
 * middle elements).  (Using this median instead of the first element is a big
 * win).  Then, the usual partitioning/swapping, followed by moving the
 * discriminator into the right place.  Then, figure out the sizes of the two
 * partions, do the smaller one recursively and the larger one via a repeat of
 * this code.  Stopping when there are less than THRESH elements in a partition
 * and cleaning up with an insertion sort (in our caller) is a huge win.
 * All data swaps are done in-line, which is space-losing but time-saving.
 * (And there are only three places where this is done).
 */

void qst(char *base, char *max)
{
	register char c, *i, *j, *jj;
	register int ii;
	char *mid, *tmp;
	int lo, hi;

	/*
	 * At the top here, lo is the number of characters of elements in the
	 * current partition.  (Which should be max - base).
	 * Find the median of the first, last, and middle element and make
	 * that the middle element.  Set j to largest of first and middle.
	 * If max is larger than that guy, then it's that guy, else compare
	 * max with loser of first and take larger.  Things are set up to
	 * prefer the middle, then the first in case of ties.
	 */
	lo = max - base;		/* number of elements as chars */
	do	{
		mid = i = base + qsz * ((lo / qsz) >> 1);
		if (lo >= mthresh) {
			j = (comparex((jj = base), i) > 0 ? jj : i);
			if (comparex(j, (tmp = max - qsz)) > 0) {
				/* switch to first loser */
				j = (j == jj ? i : jj);
				if (comparex(j, tmp) < 0)
					j = tmp;
			}
			if (j != i) {
				ii = qsz;
				do	{
					c = *i;
					*i++ = *j;
					*j++ = c;
				} while (--ii);
			}
		}
		/*
		 * Semi-standard quicksort partitioning/swapping
		 */
		for (i = base, j = max - qsz; ; ) {
			while (i < mid && comparex(i, mid) <= 0)
				i += qsz;
			while (j > mid) {
				if (comparex(mid, j) <= 0) {
					j -= qsz;
					continue;
				}
				tmp = i + qsz;	/* value of i after swap */
				if (i == mid) {
					/* j <-> mid, new mid is j */
					mid = jj = j;
				} else {
					/* i <-> j */
					jj = j;
					j -= qsz;
				}
				goto swap;
			}
			if (i == mid) {
				break;
			} else {
				/* i <-> mid, new mid is i */
				jj = mid;
				tmp = mid = i;	/* value of i after swap */
				j -= qsz;
			}
		swap:
			ii = qsz;
			do	{
				c = *i;
				*i++ = *jj;
				*jj++ = c;
			} while (--ii);
			i = tmp;
		}
		/*
		 * Look at sizes of the two partitions, do the smaller
		 * one first by recursion, then do the larger one by
		 * making sure lo is its size, base and max are update
		 * correctly, and branching back.  But only repeat
		 * (recursively or by branching) if the partition is
		 * of at least size THRESH.
		 */
		i = (j = mid) + qsz;
		if ((lo = j - base) <= (hi = max - i)) {
			if (lo >= thresh)
				qst(base, j);
			base = i;
			lo = hi;
		} else {
			if (hi >= thresh)
				qst(i, max);
			max = j;
		}
	} while (lo >= thresh);
}