#ident "$Id: puzzle.c,v 1.6 2006/06/27 02:47:46 pwh Rel $"

/*
 * Tower of Hanoi puzzle object.
 */

#include        <stdio.h>
#include	<stdlib.h>
#include	<sys/stat.h>
#include	<unistd.h>
#include	<errno.h>
#include	<string.h>

#include	"hanoi.h"

static const char      gameName[] = PUZZLE_TITLE;
static const char	*pegNames[] = { "left peg", "center peg", "right peg" };
#define		PEG_NAME(a)	pegNames[a]

#define		DISK_CH(a)	(((a)->size&1)?(ACS_CKBOARD|A_UNDERLINE\
				|A_REVERSE|A_DIM):(' '|A_UNDERLINE|A_REVERSE))
#define		MOVES_FORMAT	"Moves: %d"
#define		PICKUP_DISK	"^  Pickup disk    s  Solve the puzzle"
#define		DROP_DISK	"v  Drop disk      r  Restart the game"
#define		MOVE_CURSOR	"<> Move cursor    u  Undo last move"
#define		QUIT		"q  Quit"


static void drawTitle ( PUZZLE *puzzle )

{
   int	titleLen = strlen ( gameName );
   int	x = puzzle->xc - ( ( titleLen + 1 ) >> 1 );

   move ( puzzle->y0, x );

   x = 0;
   while ( x < titleLen ) addch ( gameName [ x++] | A_BOLD | A_UNDERLINE );
   move ( puzzle->y0 + 3, puzzle->x0 );
}


static void drawDisk ( const DISK *disk )

{
   if ( disk ) {

	int	diskCh = DISK_CH ( disk );
	int	i = ( disk->size << 1 ) + 3;

	move ( disk->y, disk->x - disk->size - 1 );

	while ( i-- > 0 ) addch ( diskCh );
   }
}


static void eraseDisk ( const DISK *disk )

{
   if ( disk ) {

	int	i = disk->size + 1;

	move ( disk->y, disk->x - disk->size - 1 );

	while ( i-- > 0 ) addch ( ' ' );

	addch ( ACS_VLINE | A_BOLD );

	i = disk->size + 1;

	while ( i-- > 0 ) addch ( ' ' );
   }
}


static void drawBase ( PUZZLE *puzzle )

{
   int	i = 0;

   while ( i < 3 ) {

	int	j = puzzle->height + 1;
	int	y = puzzle->y0 + 3;

	while ( j-- > 0 ) {

		move ( y++, puzzle->xp [i] );
		addch ( ACS_VLINE | A_BOLD );
	}

	++i;
   }

   i = 0;
   move ( puzzle->y0 + puzzle->height + 4, puzzle->x0 );

   while ( i < 3 ) {

	int	j = puzzle->height + 1;

	while ( j-- > 0 ) addch ( ACS_HLINE | A_BOLD );

	addch ( ACS_BTEE | A_BOLD );
	j = puzzle->height;

	while ( j-- > 0 ) addch ( ACS_HLINE | A_BOLD );

	++i;
   }

   addch ( ACS_HLINE | A_BOLD );
}


static void displayMoveCount ( PUZZLE *puzzle )

{
   char	moveBuff [32];
   char	*p = moveBuff;

   sprintf ( moveBuff, MOVES_FORMAT, puzzle->moves );
   move ( puzzle->y0 + puzzle->height + 5,
			puzzle->xc - ( ( sizeof ( MOVES_FORMAT) + 2 ) >> 1 ) );
   while ( *p ) addch ( *p++ );
   addch ( ' ' );
}


static void displayInstructions ( PUZZLE *puzzle )

{
   int	yc = puzzle->y0 + puzzle->height + 7;
   int	xc = puzzle->xc - ( sizeof ( PICKUP_DISK ) >> 1 );
   char	*c;

   c = PICKUP_DISK + 1;
   move ( yc++, xc );
   addch ( ACS_UARROW );
   while ( *c ) addch ( *c++ );

   c = DROP_DISK + 1;
   move ( yc++, xc );
   addch ( ACS_DARROW );
   while ( *c ) addch ( *c++ );

   c = MOVE_CURSOR + 2;
   move ( yc++, xc );
   addch ( ACS_LARROW );
   addch ( ACS_RARROW );
   while ( *c ) addch ( *c++ );

   xc = puzzle->xc - ( sizeof ( QUIT ) >> 1 );
   c = QUIT;
   move ( yc++, xc );
   while ( *c ) addch ( *c++ );
}


static int displayPuzzle ( PUZZLE *puzzle )

{
   int	status = 1;

   if ( isAnimated ( puzzle ) ) {

	int	max_y;
	int	max_x;
	int	puzzle_y = puzzle->height + 11;
	int	puzzle_x = 6 * puzzle->height + 7;

	getmaxyx ( stdscr, max_y, max_x );

	if ( puzzle_y > max_y || puzzle_x > max_x ) {

		if ( ! isendwin () ) endwin ();

		fprintf ( stderr,
		"Your screen is not big enough to display a %d disk puzzle.\n",
							puzzle->height );
		status = 0;

	} else {

		int	i;

		puzzle->y0 = ( ( max_y - puzzle_y ) >> 1 );
		puzzle->x0 = ( ( max_x - puzzle_x ) >> 1 );
		puzzle->xc = ( max_x >> 1 );
		puzzle->xp [0] = puzzle->x0 + puzzle->height + 1;
		puzzle->xp [1] = puzzle->xp [0]
					+ ( ( puzzle->height + 1 ) << 1 );
		puzzle->xp [2] = puzzle->xp [1]
					+ ( ( puzzle->height + 1 ) << 1 );
		clear ();
		drawTitle ( puzzle );
		drawBase ( puzzle );

		i = puzzle->height; 

		while ( i-- > 0 ) {

			puzzle->disks [i].x = puzzle->xp [LEFT_PEG];
			puzzle->disks [i].y = puzzle->y0 + i + 4;

			drawDisk ( & ( puzzle->disks [i] ) );
		}

		displayMoveCount ( puzzle );
		displayInstructions ( puzzle );
		move ( 0, 0 );
		refresh ();
	}

   } else fprintf ( stdout, "%s -- %d disk solution.\n\n", PUZZLE_TITLE,
							puzzle->height );
   return ( status );
}


static int diskUp ( PUZZLE *puzzle )

{
   int	status = 1;

   if ( isAnimated ( puzzle ) ) {

	int	top = puzzle->y0 + 2;
	DISK	*disk = puzzle->xDisk;

	while ( disk->y > top ) {

		int	c;

		eraseDisk ( disk );
		--disk->y;
		drawDisk ( disk );

		move ( 0, 0 );
		refresh ();
		if ( ( c = getch () ) != ERR && ( puzzle->interactive
						|| c == 'q' || c == ESC ) ) {
			errno = EINTR;
			ungetch ( c );
			status = 0;
			break;
		}
	}

   } else fprintf ( stdout, "%d.  Move disk from %s", puzzle->moves + 1,
					PEG_NAME ( puzzle->xDisk->peg ) );
   return ( status );
}


int	slideDisk ( PUZZLE *puzzle, int dest )

{
   int	status = 1;

   if ( isAnimated ( puzzle ) ) {

	DISK	*disk = puzzle->xDisk;

	errno = 0;

	if ( disk ) {

		int	warpFactor = puzzle->warpFactor;
		int	peg = puzzle->xp [dest];

		if ( disk->x != peg && ( status = diskUp ( puzzle ) ) ) {

			int	ch = DISK_CH ( disk );
			int	ch2;
			int	increment;

			if ( peg < disk->x ) {

				increment = -warpFactor;
				ch2 = ' ';

			} else {

				increment = warpFactor;
				ch2 = ch;
				ch = ' ';
			}

			while ( disk->x != peg ) {

				int	i = warpFactor;

				if ( puzzle->newSpeed ) setSpeed ( puzzle,
							puzzle->newSpeed );

				if ( increment < 0 ) disk->x += increment;

				move ( disk->y, disk->x - disk->size - 1 );

				while ( i-- > 0 ) addch ( ch );

				move ( disk->y, disk->x + disk->size + 2 );

				i = warpFactor;
				while ( i-- > 0 ) addch ( ch2 );

				if ( increment > 0 ) disk->x += increment;

				move ( 0, 0 );
				refresh ();
				if ( ( i = getch () ) != ERR
					&& ( puzzle->interactive
					|| i == 'q' || i == ESC ) ) {

					errno = EINTR;
					ungetch ( i );
					status = 0;
					break;
				}
			}
		}

	} else status = 0;
   }

   return ( status );
}


static int	diskDown ( PUZZLE *puzzle, int dest )

{
   int	status = 1;

   if ( isAnimated ( puzzle ) ) {

	DISK	*disk = puzzle->xDisk;

	if ( disk->x == puzzle->xp [dest]
				|| ( status = slideDisk ( puzzle, dest ) ) ) {

		int	bottom = puzzle->y0 + puzzle->height
					- puzzle->peg_tops [dest] + 3;

		if ( disk->y == puzzle->y0 + 2 ) {

			int	i = ( disk->size << 1 ) + 3;

			move ( disk->y, disk->x - disk->size - 1 );

			while ( i-- > 0 ) addch ( ' ' );

			++disk->y;

			drawDisk ( disk );

			move ( 0, 0 );
			refresh ();
			if ( ( i = getch () ) != ERR && ( puzzle->interactive
						|| i == 'q' || i == ESC ) ) {

				errno = EINTR;
				ungetch ( i );
				status = 0;
			}
		}

		if ( status ) {

			while ( disk->y < bottom ) {

				int	c;

				eraseDisk ( disk );
				++disk->y;
				drawDisk ( disk );

				move ( 0, 0 );
				refresh ();
				if ( ( c = getch () ) != ERR
						&& ( puzzle->interactive
						|| c == 'q' || c == ESC ) ) {

					errno = EINTR;
					ungetch ( c );
					status = 0;
					break;
				}
			}
		}
	}

   } else fprintf ( stdout, " to %s.\n", PEG_NAME ( dest ) );

   return ( status );
}


int	dropDisk ( PUZZLE *puzzle, int dest )

{
   int	status = 0;
   DISK	*disk = puzzle->xDisk;

   errno = 0;

   /* Is this a legal move? */
   if ( disk && ( puzzle->peg_tops [dest] == 0
	|| disk->size
		< puzzle->pegs [dest] [puzzle->peg_tops [dest] - 1]->size ) ) {

	if ( status = diskDown ( puzzle, dest ) ) {

		if ( disk->peg != dest ) {

			++puzzle->moves;

			disk->peg = dest;
			disk->height = puzzle->peg_tops [dest];
		}

		displayMoveCount ( puzzle );

		puzzle->pegs [dest] [puzzle->peg_tops [dest]++] = disk;
		puzzle->xDisk = NULL;
	}
   }

   return ( status );
}


int pickupDisk ( PUZZLE *puzzle, int src )

{
   int	status = 0;

   errno = 0;

   if ( ( puzzle->peg_tops [src] > 0
		|| ( puzzle->xDisk && puzzle->xDisk->peg == src ) )
	&& ( ! puzzle->xDisk || puzzle->xDisk->peg == src
		|| ( status = dropDisk ( puzzle, puzzle->xDisk->peg ) ) ) ) {

	if ( ! puzzle->xDisk ) {

		puzzle->xDisk = puzzle->pegs [src] [--puzzle->peg_tops [src]];
		puzzle->pegs [src] [puzzle->peg_tops [src]] = NULL;
	}

	status = diskUp ( puzzle );
   }

   return ( status );
}


void closePuzzle ( PUZZLE *puzzle )

{
   if ( puzzle ) {

	if ( isAnimated ( puzzle ) ) {

		timeout ( -1 );
		if ( puzzle->moves ) getch ();
		if ( ! isendwin () ) endwin ();

	} else putchar ( '\n' );

	free ( puzzle );
   }
}


int resetPuzzle ( PUZZLE *puzzle )

{
   int	height = puzzle->height;
   int	i;

   puzzle->interactive = 1;
   puzzle->moves = 0;

   puzzle->peg_tops [LEFT_PEG] = height;
   puzzle->peg_tops [CENTER_PEG] = 0;
   puzzle->peg_tops [RIGHT_PEG] = 0;
   puzzle->xDisk = NULL;

   for ( i = 0; i < height; ++i ) {

	puzzle->disks [i].peg = LEFT_PEG;
	puzzle->disks [i].height = height - 1 - i;

	puzzle->pegs [LEFT_PEG] [i] = & ( puzzle->disks[height - 1 - i] );
	puzzle->pegs [CENTER_PEG] [i] = NULL;
	puzzle->pegs [RIGHT_PEG] [i] = NULL;
   }

   return ( displayPuzzle ( puzzle ) );
}


void setSpeed ( PUZZLE *puzzle, int speed )

{
   puzzle->newSpeed = speed ? speed : NORMAL_SPEED;

   if ( isAnimated ( puzzle )
		&& ( ! puzzle->xDisk || puzzle->xDisk->y != puzzle->y0 + 2
			|| ! ( ( puzzle->xDisk->x - puzzle->xp[0] ) & 1 ) ) ) {

	if ( puzzle->newSpeed == WARP_SPEED ) {

		puzzle->speed = XTREME_SPEED;
		puzzle->warpFactor = 2;

	} else {

		puzzle->speed = puzzle->newSpeed;
		puzzle->warpFactor = 1;
	}

	puzzle->newSpeed = 0;

	timeout ( puzzle->speed );
   }
}


PUZZLE *openPuzzle ( int height, int animated, int speed )

{
   PUZZLE	*puzzle = NULL;
   struct stat	st_buff;

   /* Check if standard out is a terminal. */
   if ( fstat ( 1, &st_buff ) < 0 ) {

	perror ( "Standard out not available" );

   /* Allocate space for a PUZZLE object. */
   } else if ( puzzle = ( PUZZLE * ) malloc ( sizeof ( PUZZLE ) + height
			* ( sizeof ( DISK ) + 3 * sizeof ( DISK * ) ) ) ) {

	puzzle->speed = 0;

	/* If animated flag is set and standard out is a terminal... */
	if ( animated && S_ISCHR ( st_buff.st_mode ) ) {

		if ( initscr () ) {

			cbreak ();
			noecho ();
			nonl ();
			intrflush ( stdscr, FALSE );
			keypad ( stdscr, TRUE );
			puzzle->speed = 1;	/* Kludge. */
			setSpeed ( puzzle, speed );

		} else fprintf ( stderr, "Cannot take control of terminal.\n" );
	}

	puzzle->height = height;

	puzzle->disks = ( DISK * ) ( puzzle + 1 );
	puzzle->pegs [LEFT_PEG] = ( DISK ** ) ( puzzle->disks + height );
	puzzle->pegs [CENTER_PEG] = puzzle->pegs [LEFT_PEG] + height;
	puzzle->pegs [RIGHT_PEG] = puzzle->pegs [CENTER_PEG] + height;

	while ( height-- > 0 ) puzzle->disks [height].size = height;

	if ( ! resetPuzzle ( puzzle ) ) {

		closePuzzle ( puzzle );
		puzzle = NULL;

	} else if ( isAnimated ( puzzle ) ) {

		timeout ( 200 );
		getch ();
		timeout ( puzzle->speed );
	}
   }

   return ( puzzle );
}


int solvePuzzle ( PUZZLE *puzzle, int speed )

{
   int	status = 1;

   puzzle->interactive = 0;

   setSpeed ( puzzle, speed );
   status = solve ( puzzle );

   return ( status );
}


int undoMove ( PUZZLE *puzzle, int src, int dest )

{
   int	status = 0;

   errno = 0;

   if ( puzzle->moves > 0 && ! puzzle->xDisk && puzzle->peg_tops [dest] > 0 ) {

	puzzle->xDisk = puzzle->pegs [dest] [--puzzle->peg_tops [dest]];
	puzzle->pegs [dest] [puzzle->peg_tops [dest]] = NULL;
	puzzle->xDisk->peg = src;
	puzzle->moves -= 1;
	status = 1;
   }

   return ( status );
}


int moveDisk ( PUZZLE *puzzle, int src_peg, int dest_peg )

{
   return ( ( ( puzzle->xDisk && puzzle->xDisk->peg == src_peg )
					|| pickupDisk ( puzzle, src_peg ) )
					&& dropDisk ( puzzle, dest_peg ) );
}