#include <stdio.h>

#ifndef M_XENIX
/*
#include <stdlib.h>
#include <io.h>
*/
#endif 

#include <fcntl.h>
#include "cell.h"

/*
** visit neighboring cells like this (where [9] is on the other side):
**
**	+---+---+---+
**	| 1 | 2 | 3 |
**	+---+---+---+
**	| 4 |[9]| 5 |
**	+---+---+---+
**	| 6 | 7 | 8 |
**	+---+---+---+
*/

static int delta[8][2] = { /* for visiting neighbors on the same side */
	 {  1, -1 }, /* northwest	*/
	 {  1,  0 }, /* north		*/
	 {  1,  1 }, /* northeast	*/
	 {  0, -1 }, /* west		*/
	 {  0,  1 }, /* east		*/
	 { -1, -1 }, /* southwest	*/
	 { -1,  0 }, /* south		*/
	 { -1,  1 }  /* southeast	*/
	};

static int ndir[8] = { /* for building paths back to source */
	 FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
	 FROM_EAST,                  FROM_WEST,
	 FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
	};

/* blocking masks for neighboring cells */
#define BLOCK_NORTHEAST		( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
				| ANGLE_NEtoSE | ANGLE_NWtoNE \
				| SHARP_NtoNE | SHARP_EtoNE )
#define BLOCK_SOUTHEAST		( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
				| ANGLE_NEtoSE | ANGLE_SEtoSW \
				| SHARP_EtoSE | SHARP_StoSE )
#define BLOCK_SOUTHWEST		( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
				| ANGLE_SEtoSW | ANGLE_SWtoNW \
				| SHARP_StoSW | SHARP_WtoSW )
#define BLOCK_NORTHWEST		( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
				| ANGLE_SWtoNW | ANGLE_NWtoNE \
				| SHARP_WtoNW | SHARP_NtoNW )

struct block {
	int r1, c1;
	long b1, h1;
	int r2, c2;
	long b2, h2;
	};

static struct block blocking[8] = { /* blocking masks */
	 {  0, -1, BLOCK_NORTHEAST, HOLE_NORTHEAST,
	    1,  0, BLOCK_SOUTHWEST, HOLE_SOUTHWEST },
	 {  0,  0, 0, 0, 0, 0, 0, 0 },
	 {  1,  0, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
	    0,  1, BLOCK_NORTHWEST, HOLE_NORTHWEST },
	 {  0,  0, 0, 0, 0, 0, 0, 0 },
	 {  0,  0, 0, 0, 0, 0, 0, 0 },
	 {  0, -1, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
	   -1,  0, BLOCK_NORTHWEST, HOLE_NORTHWEST },
	 {  0,  0, 0, 0, 0, 0, 0, 0 },
	 { -1,  0, BLOCK_NORTHEAST, HOLE_NORTHEAST,
	    0,  1, BLOCK_SOUTHWEST, HOLE_SOUTHWEST }
	};

static int selfok[5][8] = { /* mask for self-blocking corner effects */
	 { 1, 1, 1, 1, 1, 1, 1, 1 },
	 { 0, 0, 0, 0, 1, 0, 1, 0 },
	 { 0, 0, 0, 1, 0, 0, 1, 0 },
	 { 0, 1, 0, 0, 1, 0, 0, 0 },
	 { 0, 1, 0, 1, 0, 0, 0, 0 }
	};

static long newmask[5][8] = { /* patterns to mask out in neighbor cells */
	 { 0, 0, 0, 0, 0, 0, 0, 0 },
	 { 0, 0, 0, 0, CORNER_NORTHEAST | CORNER_SOUTHEAST, 0,
		CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
	 { 0, 0, 0, CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0,
		CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
	 { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0, 0,
		CORNER_NORTHEAST | CORNER_SOUTHEAST, 0, 0, 0 },
	 { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0,
		CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0, 0, 0 }
	};

static char fmt[] =
  "  open=%ld, closed=%ld, moved=%ld, max=%ld, %ld%% of board";

/* board dimensions */
extern int Nrows;
extern int Ncols;

/* measures of progress */
int Ntotal = 0;
int Ncurrent = 0;

/* search statistics */
extern long OpenNodes; /* total number of nodes opened */
extern long ClosNodes; /* total number of nodes closed */
extern long MoveNodes; /* total number of nodes moved */
extern long MaxNodes; /* maximum number of nodes opened at one time */

extern int one_side; /* udi 27-2-90 - single sides board flag */

extern void GetWork();

extern void InitQueue();
extern void GetQueue();
extern void SetQueue();
extern void ReSetQueue();
extern long GetCell();
extern void SetCell();
extern void OrCell();
extern int GetDir();
extern void SetDir();
extern int GetDist();
extern void SetDist();
extern int GetApxDist();
extern int CalcDist();

void Solve();
void Retrace();

void Solve () { /* route all traces */
	int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
	int i;
	char *n1;
	char *n2;
	long curcell, newcell, buddy, lastopen, lastclos, lastmove;
	int newdist, olddir, success, self, echo;

	printf( "enter Solve()\n" );
	echo = isatty( fileno(stdout) ) ? 1 : 0;
	/* go until no more work to do */
	while () {
		GetWork( &r1, &c1, &n1, &r2, &c2, &n2 );
		if (r1 == ILLEGAL) break;
		Ncurrent++;
		printf( "routing %s=%s, %d of %d\n", n1, n2, Ncurrent,
			Ntotal );
		if (r1 == r2 && c1 == c2) /* trivial case; already routed */
			continue;
		success = 0;
		lastopen = lastclos = lastmove = 0;
		InitQueue(); /* initialize the search queue */
		a = GetApxDist( r1, c1, r2, c2 ); /* rough estimate */
		SetQueue( r1, c1, TOP, 0, a, r2, c2 );
		if (!one_side) SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
		/* search until success or we exhaust all possibilities */
		for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
			GetQueue( &r, &c, &s, &d, &a )) {
			if (r == r2 && c == c2) { /* success! */
				Retrace( r1, c1, r2, c2, s ); /* lay traces */
				success++;
				break;
				}
			/* report every 100 new nodes or so */
			if (echo && (OpenNodes - lastopen > 100
				|| ClosNodes - lastclos > 100
				|| MoveNodes - lastmove > 100)) {
				lastopen = (OpenNodes/100)*100;
				lastclos = (ClosNodes/100)*100;
				lastmove = (MoveNodes/100)*100;
				printf( fmt, OpenNodes, ClosNodes,
					MoveNodes, MaxNodes,
					(ClosNodes*50)/(Nrows*Ncols) );
				putchar( '\r' );
				}
			curcell = GetCell( r, c, s );
			if (curcell & CORNER_NORTHWEST)
				self = 1;
			else if (curcell & CORNER_NORTHEAST)
				self = 2;
			else if (curcell & CORNER_SOUTHWEST)
				self = 3;
			else if (curcell & CORNER_SOUTHEAST)
				self = 4;
			else
				self = 0;
			for (i = 0; i < 8; i++) { /* consider neighbors */
				if (!selfok[self][i]) /* check self-block */
					continue;
				if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
					|| (nc = c+delta[i][1]) < 0
					|| nc >= Ncols) /* off the edge? */
					continue;
				newcell = GetCell( nr, nc, s );
				/* check for non-target hole */
				if (newcell & HOLE) {
					if (nr != r2 || nc != c2)
						continue;
					}
				else {
					newcell &= ~(newmask[self][i]);
					if (newcell) /* check for traces */
						continue;
					}
				/* check blocking on corner neighbors */
				if (delta[i][0] && delta[i][1]) {
					/* check first buddy */
					buddy = GetCell( r+blocking[i].r1,
						c+blocking[i].c1, s );
					if (buddy & HOLE) {
						if (buddy & (blocking[i].h1))
							continue;
						}
					else if (buddy & (blocking[i].b1))
						continue;
					/* check second buddy */
					buddy = GetCell( r+blocking[i].r2,
						c+blocking[i].c2, s );
					if (buddy & HOLE) {
						if (buddy & (blocking[i].h2))
							continue;
						}
					else if (buddy & (blocking[i].b2))
						continue;
					}
				olddir = GetDir( r, c, s );
				newdist = d+CalcDist( ndir[i], olddir,
					(olddir == FROM_OTHERSIDE)
					? GetDir( r, c, 1-s ) : 0 );
				/* if not visited yet, add it to queue */
				if (!GetDir( nr, nc, s )) {
					SetDir( nr, nc, s, ndir[i] );
					SetDist( nr, nc, s, newdist );
					SetQueue( nr, nc, s, newdist,
						GetApxDist( nr, nc, r2, c2 ),
						r2, c2 );
					}
				/* we might have found a better path */
				else if (newdist < GetDist( nr, nc, s )) {
					SetDir( nr, nc, s, ndir[i] );
					SetDist( nr, nc, s, newdist );
					ReSetQueue( nr, nc, s, newdist,
						GetApxDist( nr, nc, r2, c2 ),
						r2, c2 );
					}
				}
			/* consider other side of board */
			/* check for holes or traces on other side */
/* udi 27-2-90 - add support or single sides boards.
			if (newcell = GetCell( r, c, 1-s ))
*/
			if ((newcell = GetCell( r, c, 1-s )) || one_side)
				continue;
			skip = 0;
			/* check for nearby holes */
			for (i = 0; i < 8; i++) {
				if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
					|| (nc = c+delta[i][1]) < 0
					|| nc >= Ncols) /* off the edge? */
					continue;
				if (GetCell( nr, nc, s ) & HOLE) {
					skip = 1; /* neighboring hole */
					break;
					}
				}
			if (skip) /* neighboring hole? */
				continue; /* yes, can't drill one here */
			olddir = GetDir( r, c, s );
			newdist = d+CalcDist( FROM_OTHERSIDE, olddir,
				(olddir == FROM_OTHERSIDE)
				? GetDir( r, c, 1-s ) : 0 );
			/* if not visited yet, add it to queue */
			if (!GetDir( r, c, 1-s )) {
				SetDir( r, c, 1-s, FROM_OTHERSIDE );
				SetDist( r, c, 1-s, newdist );
				SetQueue( r, c, 1-s, newdist, a, r2, c2 );
				}
			/* we might have found a better path */
			else if (newdist < GetDist( r, c, 1-s )) {
				SetDir( r, c, 1-s, FROM_OTHERSIDE );
				SetDist( r, c, 1-s, newdist );
				ReSetQueue( r, c, 1-s, newdist, a, r2, c2 );
				}
			}
		printf( fmt, OpenNodes, ClosNodes, MoveNodes, MaxNodes,
			(ClosNodes*50)/(Nrows*Ncols) );
		putchar( '\n' );
		if (!success)
			printf( "\t*!* UNSUCCESSFUL *!*\n" );
		/* clear direction flags */
		for (r = 0; r < Nrows; r++) {
			for (c = 0; c < Ncols; c++) {
				SetDir( r, c, TOP, EMPTY );
				SetDir( r, c, BOTTOM, EMPTY );
				}
			}
		}
	printf( "leave Solve()\n" );
	}

static long bit[8][9] = { /* OT=Otherside */
	 /* N, NE, E, SE, S, SW, W, NW, OT */
/* N */  { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE, 0,
	   SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW, (HOLE | HOLE_SOUTH) },
/* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW, SHARP_StoSW,
	   0, SHARP_WtoSW, ANGLE_SWtoNW, (HOLE | HOLE_SOUTHWEST) },
/* E */  { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
	   CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW, (HOLE | HOLE_WEST) },
/* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW, BENT_StoNW,
	   ANGLE_SWtoNW, SHARP_WtoNW, 0, (HOLE | HOLE_NORTHWEST) },
/* S */  { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE, LINE_VERTICAL,
	   BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW, (HOLE | HOLE_NORTH) },
/* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE, DIAG_NEtoSW,
	   BENT_WtoNE, ANGLE_NWtoNE, (HOLE | HOLE_NORTHEAST) },
/* W */  { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE, CORNER_SOUTHEAST,
	   BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW, (HOLE | HOLE_EAST) },
/* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
           ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW, (HOLE | HOLE_SOUTHEAST) }
	};

void Retrace ( rr1, cc1, rr2, cc2, s )
	/* work from target back to source, actually laying the traces */
	int rr1, cc1, rr2, cc2, s; /* start on side s */
	{
	int r0, c0, s0, r1, c1, s1, r2, c2, s2;
	register int x, y;
	long b;

	r1 = rr2;
	c1 = cc2;
	s1 = s;
	r0 = c0 = s0 = ILLEGAL;
	do {
		/* find where we came from to get here */
		switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
		case FROM_NORTH:	r2++;		break;
		case FROM_EAST:			c2++;	break;
		case FROM_SOUTH:	r2--;		break;
		case FROM_WEST:			c2--;	break;
		case FROM_NORTHEAST:	r2++;	c2++;	break;
		case FROM_SOUTHEAST:	r2--;	c2++;	break;
		case FROM_SOUTHWEST:	r2--;	c2--;	break;
		case FROM_NORTHWEST:	r2++;	c2--;	break;
		case FROM_OTHERSIDE:	s2 = 1-s2;	break;
		default:
			printf( "internal error: no way back\n" );
			exit( -1 );
			break;
			}
		if (r0 != ILLEGAL)
			y = GetDir( r0, c0, s0 );
		/* see if target or hole */
		if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
			switch (x) {
			case FROM_NORTH:
				OrCell( r1, c1, s1, HOLE_NORTH );	break;
			case FROM_EAST:
				OrCell( r1, c1, s1, HOLE_EAST );	break;
			case FROM_SOUTH:
				OrCell( r1, c1, s1, HOLE_SOUTH );	break;
			case FROM_WEST:
				OrCell( r1, c1, s1, HOLE_WEST );	break;
			case FROM_NORTHEAST:
				OrCell( r1, c1, s1, HOLE_NORTHEAST );	break;
			case FROM_SOUTHEAST:
				OrCell( r1, c1, s1, HOLE_SOUTHEAST );	break;
			case FROM_SOUTHWEST:
				OrCell( r1, c1, s1, HOLE_SOUTHWEST );	break;
			case FROM_NORTHWEST:
				OrCell( r1, c1, s1, HOLE_NORTHWEST );	break;
			case FROM_OTHERSIDE:
			default:
				printf( "internal error\n" );
				exit( -1 );
				break;
				}
			}
		else {
			if ((y == FROM_NORTH || y == FROM_NORTHEAST
				|| y == FROM_EAST || y == FROM_SOUTHEAST
				|| y == FROM_SOUTH || y == FROM_SOUTHWEST
				|| y == FROM_WEST || y == FROM_NORTHWEST)
				&& (x == FROM_NORTH || x == FROM_NORTHEAST
				|| x == FROM_EAST || x == FROM_SOUTHEAST
				|| x == FROM_SOUTH || x == FROM_SOUTHWEST
				|| x == FROM_WEST || x == FROM_NORTHWEST
				|| x == FROM_OTHERSIDE)
				&& (b = bit[y-1][x-1])) {
				OrCell( r1, c1, s1, b );
				if (b & HOLE)
					OrCell( r2, c2, s2, HOLE );
				}
			else {
				printf( "internal error\n" );
				exit( -1 );
				}
			}
		if (r2 == rr1 && c2 == cc1) { /* see if source */
			switch (x) {
			case FROM_NORTH:
				OrCell( r2, c2, s2, HOLE_SOUTH );	break;
			case FROM_EAST:
				OrCell( r2, c2, s2, HOLE_WEST );	break;
			case FROM_SOUTH:
				OrCell( r2, c2, s2, HOLE_NORTH );	break;
			case FROM_WEST:
				OrCell( r2, c2, s2, HOLE_EAST );	break;
			case FROM_NORTHEAST:
				OrCell( r2, c2, s2, HOLE_SOUTHWEST );	break;
			case FROM_SOUTHEAST:
				OrCell( r2, c2, s2, HOLE_NORTHWEST );	break;
			case FROM_SOUTHWEST:
				OrCell( r2, c2, s2, HOLE_NORTHEAST );	break;
			case FROM_NORTHWEST:
				OrCell( r2, c2, s2, HOLE_SOUTHEAST );	break;
			case FROM_OTHERSIDE:
			default:
				printf( "internal error\n" );
				exit( -1 );
				break;
				}
			}
		/* move to next cell */
		r0 = r1; c0 = c1; s0 = s1;
		r1 = r2; c1 = c2; s1 = s2;
		} while (!(r2 == rr1 && c2 == cc1));
	}