#include "geo.h"
#define DEBUG

extern int tprop( TNODEPTR r , int value );
extern void tinsert( TNODEPTR *root , int value , int property );

void exploreUp(void);
void exploreRite(void);
int constructVedge( int index1 , int index2 );
int constructHedge( int index1 , int index2 );

void changraph(void)
{
#ifdef notdef
char filename[1024] ;
FILE *fp ;
#endif
int i , index1 , index2 , hiend , loend , length ;

vChanBeginRoot = (TNODEPTR) NULL ;
vChanEndRoot   = (TNODEPTR) NULL ;
hChanBeginRoot = (TNODEPTR) NULL ;
hChanEndRoot   = (TNODEPTR) NULL ;
eNum = 0 ;
eArray = (EBOXPTR) malloc( 100 * sizeof(EBOX) ) ;

/* XXX Ahh, Sechen code, lint torture testing */
/* exploreUp( HRlist , 0 , -1000000 ) ; */
exploreUp();

edgeTransition = eNum ;

/* exploreRite( VRlist , 0 , -1000000 ) ; */
exploreRite();

eIndexArray = (int **) malloc( (1 + numRects) * sizeof( int * ) ) ;
for( i = 1 ; i <= numRects ; i++ ) {
    eIndexArray[i] = (int *) malloc( (1 + numRects) * sizeof( int ) ) ;
}

#ifdef notdef
sprintf( filename, "%s.gph", cktName ) ;
fp = fopen( filename , "w" ) ;
#endif

for( i = 1 ; i <= eNum ; i++ ) {
    index1 = eArray[i].index1 ;
    index2 = eArray[i].index2 ;
    eIndexArray[index1][index2] = i ;
    eIndexArray[index2][index1] = i ;
    if( i <= edgeTransition ) {
	hiend = rectArray[index2].b ;
	loend = rectArray[index1].t ;
	length = rectArray[index2].yc - rectArray[index1].yc  ;
	tinsert( &vChanBeginRoot , eArray[i].lbside , i ) ;
	tinsert( &vChanEndRoot , eArray[i].rtside , i ) ;
    } else {
	hiend = rectArray[index2].l ;
	loend = rectArray[index1].r ;
	length = rectArray[index2].xc - rectArray[index1].xc  ;
	tinsert( &hChanBeginRoot , eArray[i].lbside , i ) ;
	tinsert( &hChanEndRoot , eArray[i].rtside , i ) ;
    }
    eArray[i].length = length ;
    eArray[i].hiend = hiend ;
    eArray[i].loend = loend ;
#ifdef notdef
    fprintf( fp, "edge %5d %5d   length %8d  capacity %8d\n",
		    index1 , index2 , length , eArray[i].width ) ;
#endif
}
#ifdef notdef
fclose(fp);
#endif

#ifdef DEBUG
fprintf(fpdebug,"CHANNEL-GRAPH NODES:\n");
for( i = 1 ; i <= numRects ; i++ ) {
    fprintf(fpdebug,"rect Node: %d  at: %d %d  width:%d  height:%d\n",
		i , rectArray[i].xc , rectArray[i].yc ,
		rectArray[i].r - rectArray[i].l ,
				rectArray[i].t - rectArray[i].b ) ;
}
#endif

return ;
}


void exploreUp(void)
{

DLINK2PTR beptr ;
int beg , end , left , rite , finishLine , b , l , r , rec , index ;

for( rec = 1 ; rec <= numRects ; rec++ ) {
    beg  = rectArray[rec].b ;
    end  = rectArray[rec].t ;
    rite = rectArray[rec].r ;
    left = rectArray[rec].l ;
    finishLine = 1000000 ;
    beptr = BEptrs[ tprop( BEroot , beg ) ] ;
    for( ; beptr != (DLINK2PTR) NULL; beptr = beptr->next ){
	index = beptr->index ;
	b = rectArray[index].b ;
	if( b > finishLine ) {
	    break ;
	}
	l = rectArray[index].l ;
	r = rectArray[index].r ;
	if( b <= end || l > rite || r < left ) {
	    continue ;
	}
	if( constructVedge( rec , index ) ) {
	    break ;
	}
	finishLine = rectArray[index].t ;
    }
}
return ;
}


void exploreRite(void)
{

DLINK2PTR leptr ;
int beg , end , top , bot , finishLine , l , b , t , rec , index ;

for( rec = 1 ; rec <= numRects ; rec++ ) {
    beg = rectArray[rec].l ;
    end = rectArray[rec].r ;
    top = rectArray[rec].t ;
    bot = rectArray[rec].b ;
    finishLine = 1000000 ;
    leptr = LEptrs[ tprop( LEroot , beg ) ] ;
    for( ; leptr != (DLINK2PTR) NULL; leptr = leptr->next ){
	index = leptr->index ;
	l = rectArray[index].l ;
	if( l > finishLine ) {
	    break ;
	}
	b = rectArray[index].b ;
	t = rectArray[index].t ;
	if( l <= end || b > top || t < bot ) {
	    continue ;
	}
	if( constructHedge( rec , index ) ) {
	    break ;
	}
	finishLine = rectArray[index].r ;
    }
}
return ;
}


int constructVedge( int index1 , int index2 )
{

DLINK1PTR v1ptr , v2ptr , vptr ;
int l1 , l2 , r1 , r2 , l , r , b , t , edge1 , edge2 , el , er ;
int eb , et , eb1 , et1 , eb2 , et2 ;
int edge , x ;

l1 = rectArray[index1].l ;
r1 = rectArray[index1].r ;
l2 = rectArray[index2].l ;
r2 = rectArray[index2].r ;
l = ( l1 >= l2 ) ? l1 : l2 ;
r = ( r1 <= r2 ) ? r1 : r2 ;
b = rectArray[index1].t ; 
t = rectArray[index2].b ; 

el = -1000000 ;
v1ptr = VDptrs[ tprop( VDroot , l ) ] ;
for( ; v1ptr != (DLINK1PTR) NULL; v1ptr = v1ptr->next ) {
    edge1 = v1ptr->edge ;
    if( edgeList[edge1].loc > r ) {
	break ;
    }
    if( edgeList[edge1].UorR > 0 ) {
	continue ;
    }
    if( edgeList[edge1].start > b || edgeList[edge1].end < t ) {
	continue ;
    }
    el = edgeList[edge1].loc ;
    vptr = v1ptr ;
}
if( el == -1000000 ) {
    return(0) ;
}
v2ptr = Vptrs[ tprop( Vroot , el ) ] ;
for( ; v2ptr != (DLINK1PTR) NULL; v2ptr = v2ptr->next ) {
    edge2 = v2ptr->edge ;
    if( edgeList[edge2].UorR < 0 ) {
	continue ;
    }
    if( edgeList[edge2].start > b || edgeList[edge2].end < t ) {
	continue ;
    }
    er = edgeList[edge2].loc ;
    break ;
}
if( er > r ) {
    return(0) ;
}
v1ptr = vptr ;
edge1 = v1ptr->edge ;

et1 = edgeList[edge1].end ;
eb1 = edgeList[edge1].start ;
et2 = edgeList[edge2].end ;
eb2 = edgeList[edge2].start ;
if( edgeList[edge1].fixed == 1 && edgeList[edge2].fixed == 1 ) {
    if( edgeList[edge1].cell > 0 && edgeList[edge2].cell > 0 ) {
	et = (et1 >= et2) ? et1 : et2 ;
	eb = (eb1 <= eb2) ? eb1 : eb2 ;
    } else if( edgeList[edge1].cell > 0 ) {
	et = et1 ;
	eb = eb1 ;
    } else if( edgeList[edge2].cell > 0 ) {
	et = et2 ;
	eb = eb2 ;
    } else {
	et = 1000000 ;
	eb = -1000000 ;
    }
} else if( edgeList[edge1].fixed == 1 ) {
    if( edgeList[edge1].cell > 0 ) {
	et = et1 ;
	eb = eb1 ;
    } else {
	et = 1000000 ;
	eb = -1000000 ;
    }
} else if( edgeList[edge2].fixed == 1 ) {
    if( edgeList[edge2].cell > 0 ) {
	et = et2 ;
	eb = eb2 ;
    } else {
	et = 1000000 ;
	eb = -1000000 ;
    }
} else {
    et = 1000000 ;
    eb = -1000000 ;
}
if( ! ( et > rectArray[index2].t ) ){
    if( rectArray[index2].yc < et ) {
	rectArray[index2].yc = et ;
	rectArray[index2].yreset = 2 ;
    }
}
if( ! ( eb < rectArray[index1].b ) ){
    if( rectArray[index1].yc > eb ) {
	rectArray[index1].yc = eb ;
	rectArray[index1].yreset = 1 ;
    }
}
if( rectArray[index1].xc < el || rectArray[index1].xc > er ) {
    rectArray[index1].xc = (el + er) / 2 ;
}
if( rectArray[index2].xc < el || rectArray[index2].xc > er ) {
    rectArray[index2].xc = (el + er) / 2 ;
}

if( edgeList[edge1].fixed == 0 ) {
    vptr = Vptrs[ tprop( Vroot , el ) ] ;
    x = edgeList[vptr->edge].loc ;
    vptr = vptr->next ;
    for( ; vptr != (DLINK1PTR) NULL; vptr = vptr->next ) {
	if( edgeList[vptr->edge].loc > x ) {
	    break ;
	}
    }
    for( vptr = vptr->prev; vptr != (DLINK1PTR) NULL; 
					    vptr = vptr->prev ) {
	if( vptr == v2ptr ) {
	    continue ;
	}
	edge = vptr->edge ;
	if( edgeList[edge].UorR < 0 ) {
	    continue ;
	}
	if( edgeList[edge].start > b || edgeList[edge].end < t ) {
	    continue ;
	}
	break ;
    }
    el -= (el - edgeList[edge].loc) - (el - edgeList[edge].loc) / 2 ;
}
if( edgeList[edge2].fixed == 0 ) {
    vptr = Vptrs[ tprop( Vroot , er ) ] ;
    for(; vptr != (DLINK1PTR) NULL; vptr = vptr->next ) {
	if( vptr == v1ptr ) {
	    continue ;
	}
	edge = vptr->edge ;
	if( edgeList[edge].UorR > 0 ) {
	    continue ;
	}
	if( edgeList[edge].start > b || edgeList[edge].end < t ) {
	    continue ;
	}
	break ;
    }
    er += (edgeList[edge].loc - er) / 2 ;
}

if( ++eNum % 100 == 0 ) {
    eArray = (EBOXPTR) realloc( eArray, (eNum + 100) * sizeof(EBOX));
}
eArray[eNum].index1 = index1 ;
eArray[eNum].index2 = index2 ;
eArray[eNum].width  = er - el ;
eArray[eNum].lbside = el ;
eArray[eNum].rtside = er ;
eArray[eNum].edge1 = edge1 ;
eArray[eNum].edge2 = edge2 ;

return(1) ;
}


int constructHedge( int index1 , int index2 )
{

DLINK1PTR h1ptr , h2ptr , hptr ;
int b1 , b2 , t1 , t2 , b , l , r , t , edge1 , edge2 , eb , et ;
int el , er , el1 , er1 , el2 , er2 ;
int edge , x ;

b1 = rectArray[index1].b ;
t1 = rectArray[index1].t ;
b2 = rectArray[index2].b ;
t2 = rectArray[index2].t ;
b = ( b1 >= b2 ) ? b1 : b2 ;
t = ( t1 <= t2 ) ? t1 : t2 ;
l = rectArray[index1].r ; 
r = rectArray[index2].l ; 

eb = -1000000 ;
h1ptr = HRptrs[ tprop( HRroot , b ) ] ;
for( ; h1ptr != (DLINK1PTR) NULL; h1ptr = h1ptr->next ) {
    edge1 = h1ptr->edge ;
    if( edgeList[edge1].loc > t ) {
	break ;
    }
    if( edgeList[edge1].UorR < 0 ) {
	continue ;
    }
    if( edgeList[edge1].start > l || edgeList[edge1].end < r ) {
	continue ;
    }
    eb = edgeList[edge1].loc ;
    hptr = h1ptr ;
}
if( eb == -1000000 ) {
    return(0) ;
}
h2ptr = Hptrs[ tprop( Hroot , eb ) ] ;
for( ; h2ptr != (DLINK1PTR) NULL; h2ptr = h2ptr->next ) {
    edge2 = h2ptr->edge ;
    if( edgeList[edge2].UorR > 0 ) {
	continue ;
    }
    if( edgeList[edge2].start > l || edgeList[edge2].end < r ) {
	continue ;
    }
    et = edgeList[edge2].loc ;
    break ;
}
if( et > t ) {
    return(0) ;
}
h1ptr = hptr ;
edge1 = h1ptr->edge ;

er1 = edgeList[edge1].end ;
el1 = edgeList[edge1].start ;
er2 = edgeList[edge2].end ;
el2 = edgeList[edge2].start ;
if( edgeList[edge1].fixed == 1 && edgeList[edge2].fixed == 1 ) {
    if( edgeList[edge1].cell > 0 && edgeList[edge2].cell > 0 ) {
	er = (er1 >= er2) ? er1 : er2 ;
	el = (el1 <= el2) ? el1 : el2 ;
    } else if( edgeList[edge1].cell > 0 ) {
	er = er1 ;
	el = el1 ;
    } else if( edgeList[edge2].cell > 0 ) {
	er = er2 ;
	el = el2 ;
    } else {
	er = 1000000 ;
	el = -1000000 ;
    }
} else if( edgeList[edge1].fixed == 1 ) {
    if( edgeList[edge1].cell > 0 ) {
	er = er1 ;
	el = el1 ;
    } else {
	er = 1000000 ;
	el = -1000000 ;
    }
} else if( edgeList[edge2].fixed == 1 ) {
    if( edgeList[edge2].cell > 0 ) {
	er = er2 ;
	el = el2 ;
    } else {
	er = 1000000 ;
	el = -1000000 ;
    }
} else {
    er = 1000000 ;
    el = -1000000 ;
}
if( ! ( er > rectArray[index2].r ) ){
    if( rectArray[index2].xc < er ) {
	rectArray[index2].xc = er ;
	rectArray[index2].xreset = 2 ;
    }
}
if( ! ( el < rectArray[index1].l ) ){
    if( rectArray[index1].xc > el ) {
	rectArray[index1].xc = el ;
	rectArray[index1].xreset = 1 ;
    }
}
if( rectArray[index1].yc < eb || rectArray[index1].yc > et ) {
    rectArray[index1].yc = (eb + et) / 2 ;
}
if( rectArray[index2].yc < eb || rectArray[index2].yc > et ) {
    rectArray[index2].yc = (eb + et) / 2 ;
}

if( edgeList[edge1].fixed == 0 ) {
    hptr = Hptrs[ tprop( Hroot , eb ) ] ;
    x = edgeList[hptr->edge].loc ;
    hptr = hptr->next ;
    for( ; hptr != (DLINK1PTR) NULL; hptr = hptr->next ) {
	if( edgeList[hptr->edge].loc > x ) {
	    break ;
	}
    }
    for( hptr = hptr->prev; hptr != (DLINK1PTR) NULL; 
					    hptr = hptr->prev ) {
	if( hptr == h2ptr ) {
	    continue ;
	}
	edge = hptr->edge ;
	if( edgeList[edge].UorR > 0 ) {
	    continue ;
	}
	if( edgeList[edge].start > l || edgeList[edge].end < r ) {
	    continue ;
	}
	break ;
    }
    eb -= (eb - edgeList[edge].loc) - (eb - edgeList[edge].loc) / 2 ;
}
if( edgeList[edge2].fixed == 0 ) {
    hptr = Hptrs[ tprop( Hroot , et ) ] ;
    for(; hptr != (DLINK1PTR) NULL; hptr = hptr->next ) {
	if( hptr == h1ptr ) {
	    continue ;
	}
	edge = hptr->edge ;
	if( edgeList[edge].UorR < 0 ) {
	    continue ;
	}
	if( edgeList[edge].start > l || edgeList[edge].end < r ) {
	    continue ;
	}
	break ;
    }
    et += (edgeList[edge].loc - et) / 2 ;
}

if( ++eNum % 100 == 0 ) {
    eArray = (EBOXPTR) realloc( eArray, (eNum + 100) * sizeof(EBOX));
}
eArray[eNum].index1 = index1 ;
eArray[eNum].index2 = index2 ;
eArray[eNum].width  = et - eb ;
eArray[eNum].lbside = eb ;
eArray[eNum].rtside = et ;
eArray[eNum].edge1 = edge1 ;
eArray[eNum].edge2 = edge2 ;

return(1) ;
}