#include "geo.h"
#define DEBUG

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

void doubleBack( DLINK1PTR dptr );

void hprobes(void)
{

DLINK1PTR downPtr , up1ptr , up2ptr , checkPtr , ptr ;
int dx , dy1 , dy2 , dedge , by1 , by2 , uedge , edge , check ;
int u1y2 , u1y1 , u1x , u2y2 , u2y1 , u2x ;

downPtr = vFixedList ;
for( ; downPtr != (DLINK1PTR) NULL ; downPtr = downPtr->next ) {
    dedge = downPtr->edge ;
    if( edgeList[dedge].UorR > 0 ) {
	continue ;
    }
    dx  = edgeList[dedge].loc   ;
    dy1 = edgeList[dedge].start ;
    dy2 = edgeList[dedge].end   ;
    
    if( edgeList[ edgeList[dedge].prevEdge ].UorR == 1 ) {
	up2ptr = Vptrs[ tprop( Vroot , dx ) ] ;
	for(; up2ptr != (DLINK1PTR) NULL ; up2ptr = up2ptr->next){
	    uedge = up2ptr->edge ;
	    if( edgeList[uedge].UorR < 0 ) {
		continue ;
	    }
	    u2x  = edgeList[uedge].loc   ;
	    u2y1 = edgeList[uedge].start ;
	    u2y2 = edgeList[uedge].end   ;
	    if( u2y2 < dy2 || u2y1 >= dy2 ) {
		continue ;
	    }
	    break ;
	}
    } else {
	up2ptr = (DLINK1PTR) NULL ;
    }
    if( edgeList[ edgeList[dedge].nextEdge ].UorR == -1 ) {
	up1ptr = Vptrs[ tprop( Vroot , dx ) ] ;
	for(; up1ptr != (DLINK1PTR) NULL ; up1ptr = up1ptr->next){
	    uedge = up1ptr->edge ;
	    if( edgeList[uedge].UorR < 0 ) {
		continue ;
	    }
	    u1x  = edgeList[uedge].loc   ;
	    u1y1 = edgeList[uedge].start ;
	    u1y2 = edgeList[uedge].end   ;
	    if( u1y2 <= dy1 || u1y1 > dy1 ) {
		continue ;
	    }
	    break ;
	}
    } else {
	up1ptr = (DLINK1PTR) NULL ;
    }
    if( up2ptr != (DLINK1PTR) NULL && up2ptr == up1ptr ) {
	check = 1 ;
	checkPtr = Vptrs[ tprop( Vroot , dx ) ] ;
	for(; checkPtr != (DLINK1PTR) NULL ;
				    checkPtr = checkPtr->next ) {
	    if( edgeList[ checkPtr->edge ].UorR < 0 ) {
		continue ;
	    }
	    if( edgeList[ checkPtr->edge ].loc >= u2x ) {
		break ;
	    }
	    if( edgeList[ checkPtr->edge ].start >= dy2 ||
			edgeList[ checkPtr->edge ].end <= dy1 ) {
		continue ;
	    }
	    check = 0 ;
	    break ;
	}
	if( check ) {
	    edgeList[++numProbes + edgeCount].start  = dx ;
	    edgeList[numProbes + edgeCount].end      = u2x  ;
	    edgeList[numProbes + edgeCount].loc      = dy2 ;
	    edgeList[numProbes + edgeCount].length   = u2x - dx ;
	    edgeList[numProbes + edgeCount].fixed    = 0 ;
	    edgeList[numProbes + edgeCount].cell     = 0 ;
	    edgeList[numProbes + edgeCount].UorR     = 1 ;
	    tinsert( &hEdgeRoot, dy2 , numProbes + edgeCount ) ;
#ifdef DEBUG
	    fprintf(fpdebug,"hprobe:%d  ", numProbes ) ;
	    fprintf(fpdebug,"start:%d  end:%d  loc:%d  UorR:%d\n",
					dx , u2x , dy2 , 1 ) ;
#endif
	    edgeList[++numProbes + edgeCount].start  = dx ;
	    edgeList[numProbes + edgeCount].end      = u2x  ;
	    edgeList[numProbes + edgeCount].loc      = dy1 ;
	    edgeList[numProbes + edgeCount].length   = u2x - dx ;
	    edgeList[numProbes + edgeCount].fixed    = 0 ;
	    edgeList[numProbes + edgeCount].cell     = 0 ;
	    edgeList[numProbes + edgeCount].UorR     = -1 ;
	    tinsert( &hEdgeRoot, dy1 , numProbes + edgeCount ) ;
#ifdef DEBUG
	    fprintf(fpdebug,"hprobe:%d  ", numProbes ) ;
	    fprintf(fpdebug,"start:%d  end:%d  loc:%d  UorR:%d\n",
					dx , u2x , dy1 , -1 ) ;
#endif
	} else {
	    doubleBack( downPtr ) ;	
	}
	continue ;
    }
    if( up2ptr != (DLINK1PTR) NULL &&
	    edgeList[ edgeList[up2ptr->edge].prevEdge ].UorR == -1 ) {
	ptr = Vptrs[ tprop( Vroot , u2x ) ] ;
	for( ptr = ptr->next; ptr != (DLINK1PTR) NULL; ptr = ptr->next){
	    if( edgeList[ptr->edge].loc > u2x ) {
		break ;
	    }
	}
	if( ptr == (DLINK1PTR) NULL ) {
	    ptr = vFixedEnd ;
	} else {
	    ptr = ptr->prev ;
	}
	for( ; ptr != (DLINK1PTR) NULL; ptr = ptr->prev){
	    edge = ptr->edge ;
	    if( edgeList[edge].UorR > 0 ) {
		continue ;
	    }
	    by1 = edgeList[edge].start ;
	    by2 = edgeList[edge].end   ;
	    if( by2 <= u2y1 || by1 > u2y1 ) {
		continue ;
	    }
	    break ;
	}
	if( downPtr == ptr ) {
	    check = 1 ;
	    checkPtr = Vptrs[ tprop( Vroot , dx ) ] ;
	    for(; checkPtr != (DLINK1PTR) NULL ;
				    checkPtr = checkPtr->next ) {
		if( edgeList[ checkPtr->edge ].UorR < 0 ) {
		    continue ;
		}
		if( edgeList[ checkPtr->edge ].loc >= u2x ) {
		    break ;
		}
		if( edgeList[ checkPtr->edge ].start >= dy2 ||
			edgeList[ checkPtr->edge ].end <= u2y1 ) {
		    continue ;
		}
		check = 0 ;
		break ;
	    }
	    if( check ) {
		edgeList[++numProbes + edgeCount].start  = dx ;
		edgeList[numProbes + edgeCount].end      = u2x  ;
		edgeList[numProbes + edgeCount].loc      = dy2 ;
		edgeList[numProbes + edgeCount].length   = u2x - dx ;
		edgeList[numProbes + edgeCount].fixed    = 0 ;
		edgeList[numProbes + edgeCount].cell     = 0 ;
		edgeList[numProbes + edgeCount].UorR     = 1 ;
		tinsert( &hEdgeRoot, dy2 , numProbes + edgeCount ) ;
#ifdef DEBUG
		fprintf(fpdebug,"hprobe:%d  ", numProbes ) ;
		fprintf(fpdebug,"start:%d  end:%d  loc:%d  UorR:%d\n",
					dx , u2x , dy2 , 1 ) ;
#endif
		edgeList[++numProbes + edgeCount].start  = dx ;
		edgeList[numProbes + edgeCount].end      = u2x  ;
		edgeList[numProbes + edgeCount].loc      = u2y1 ;
		edgeList[numProbes + edgeCount].length   = u2x - dx ;
		edgeList[numProbes + edgeCount].fixed    = 0 ;
		edgeList[numProbes + edgeCount].cell     = 0 ;
		edgeList[numProbes + edgeCount].UorR     = -1 ;
		tinsert( &hEdgeRoot, u2y1 , numProbes + edgeCount ) ;
#ifdef DEBUG
		fprintf(fpdebug,"hprobe:%d  ", numProbes ) ;
		fprintf(fpdebug,"start:%d  end:%d  loc:%d  UorR:%d\n",
				    dx , u2x , u2y1 , -1 ) ;
#endif
	    }
	}
    }
    if( up1ptr != (DLINK1PTR) NULL &&
	    edgeList[ edgeList[up1ptr->edge].nextEdge ].UorR == 1 ) {
	ptr = Vptrs[ tprop( Vroot , u1x ) ] ;
	for( ptr = ptr->next; ptr != (DLINK1PTR) NULL; ptr = ptr->next){
	    if( edgeList[ptr->edge].loc > u1x ) {
		break ;
	    }
	}
	if( ptr == (DLINK1PTR) NULL ) {
	    ptr = vFixedEnd ;
	} else {
	    ptr = ptr->prev ;
	}
	for( ; ptr != (DLINK1PTR) NULL; ptr = ptr->prev){
	    edge = ptr->edge ;
	    if( edgeList[edge].UorR > 0 ) {
		continue ;
	    }
	    by1 = edgeList[edge].start ;
	    by2 = edgeList[edge].end   ;
	    if( by2 < u1y2 || by1 >= u1y2 ) {
		continue ;
	    }
	    break ;
	}
	if( downPtr == ptr ) {
	    check = 1 ;
	    checkPtr = Vptrs[ tprop( Vroot , dx ) ] ;
	    for(; checkPtr != (DLINK1PTR) NULL ;
				    checkPtr = checkPtr->next ) {
		if( edgeList[ checkPtr->edge ].UorR < 0 ) {
		    continue ;
		}
		if( edgeList[ checkPtr->edge ].loc >= u1x ) {
		    break ;
		}
		if( edgeList[ checkPtr->edge ].start >= u1y2 ||
			edgeList[ checkPtr->edge ].end <= dy1 ) {
		    continue ;
		}
		check = 0 ;
		break ;
	    }
	    if( check ) {
		edgeList[++numProbes + edgeCount].start  = dx ;
		edgeList[numProbes + edgeCount].end      = u1x  ;
		edgeList[numProbes + edgeCount].loc      = u1y2 ;
		edgeList[numProbes + edgeCount].length   = u1x - dx ;
		edgeList[numProbes + edgeCount].fixed    = 0 ;
		edgeList[numProbes + edgeCount].cell     = 0 ;
		edgeList[numProbes + edgeCount].UorR     = 1 ;
		tinsert( &hEdgeRoot, u1y2 , numProbes + edgeCount ) ;
#ifdef DEBUG
		fprintf(fpdebug,"hprobe:%d  ", numProbes ) ;
		fprintf(fpdebug,"start:%d  end:%d  loc:%d  UorR:%d\n",
					dx , u1x , u1y2 , 1 ) ;
#endif
		edgeList[++numProbes + edgeCount].start  = dx ;
		edgeList[numProbes + edgeCount].end      = u1x  ;
		edgeList[numProbes + edgeCount].loc      = dy1 ;
		edgeList[numProbes + edgeCount].length   = u1x - dx ;
		edgeList[numProbes + edgeCount].fixed    = 0 ;
		edgeList[numProbes + edgeCount].cell     = 0 ;
		edgeList[numProbes + edgeCount].UorR     = -1 ;
		tinsert( &hEdgeRoot, dy1 , numProbes + edgeCount ) ;
#ifdef DEBUG
		fprintf(fpdebug,"hprobe:%d  ", numProbes ) ;
		fprintf(fpdebug,"start:%d  end:%d  loc:%d  UorR:%d\n",
					dx , u1x , dy1 , -1 ) ;
#endif
	    }
	}
    }
    doubleBack( downPtr ) ;
}
return ;
}


void doubleBack( DLINK1PTR dptr )
{

int dx , dy1 , dy2 , ux , uy1 , uy2 , check , edge ;
DLINK1PTR checkPtr , ptr ;

dx  = edgeList[ dptr->edge ].loc   ;
dy2 = edgeList[ dptr->edge ].end   ;
dy1 = edgeList[ dptr->edge ].start ;

ptr = Vptrs[ tprop( Vroot , dx ) ] ;
for( ; ptr != (DLINK1PTR) NULL ; ptr = ptr->next ) {
    edge = ptr->edge ;
    if( edgeList[edge].UorR < 0 ) {
	continue ;
    }
    ux  = edgeList[edge].loc   ;
    uy1 = edgeList[edge].start ;
    uy2 = edgeList[edge].end   ;
    if( ! ( uy2 < dy2 && uy1 > dy1 )  ) {
	continue ;
    }
    if( edgeList[ edgeList[edge].prevEdge ].UorR == -1 &&
		edgeList[ edgeList[edge].nextEdge ].UorR == 1 ) {
	check = 1 ;
	checkPtr = Vptrs[ tprop( Vroot , dx ) ] ;
	for(; checkPtr != (DLINK1PTR) NULL ; checkPtr = checkPtr->next){
	    if( checkPtr == dptr ) {
		continue ;
	    }
	    if( edgeList[ checkPtr->edge ].UorR > 0 ) {
		continue ;
	    }
	    if( edgeList[ checkPtr->edge ].loc > ux ) {
		break ;
	    }
	    if( edgeList[ checkPtr->edge ].start >= uy2 ||
			edgeList[ checkPtr->edge ].end <= uy1 ) {
		continue ;
	    }
	    check = 0 ;
	    break ;
	}
    } else {
	check = 0 ;
    }
    if( check ) {
	edgeList[++numProbes + edgeCount].start  = dx ;
	edgeList[numProbes + edgeCount].end      = ux ;
	edgeList[numProbes + edgeCount].loc      = uy2 ;
	edgeList[numProbes + edgeCount].length   = ux - dx ;
	edgeList[numProbes + edgeCount].fixed    = 0 ;
	edgeList[numProbes + edgeCount].cell     = 0 ;
	edgeList[numProbes + edgeCount].UorR     = 1 ;
	tinsert( &hEdgeRoot, uy2 , numProbes + edgeCount ) ;
#ifdef DEBUG
	fprintf(fpdebug,"hprobe:%d  start:%d  end:%d  loc:%d  UorR:%d\n",
		    numProbes, dx , ux , uy2 , 1 ) ;
#endif
	edgeList[++numProbes + edgeCount].start  = dx ;
	edgeList[numProbes + edgeCount].end      = ux ;
	edgeList[numProbes + edgeCount].loc      = uy1 ;
	edgeList[numProbes + edgeCount].length   = ux - dx ;
	edgeList[numProbes + edgeCount].fixed    = 0 ;
	edgeList[numProbes + edgeCount].cell     = 0 ;
	edgeList[numProbes + edgeCount].UorR     = -1 ;
	tinsert( &hEdgeRoot, uy1 , numProbes + edgeCount ) ;
#ifdef DEBUG
	fprintf(fpdebug,"hprobe:%d  start:%d  end:%d  loc:%d  UorR:%d\n",
		    numProbes, dx , ux , uy1 , -1 ) ;
#endif
    }
}
return ;
}