/** paths.c *******************************************************
 *                                                                *
 *     A lot of effort  and  time has  been put  into this code.  *
 *     Permission to  use it is  granted  provided that you keep  *
 *  this header intact! :)                                        *
 *     I would like VERY much any comments/suggestions you might  *
 *  have. If you use this code, I would really appreciate if you  *
 *  could mail me just stating you used it! :)                    *
 *                                                                *
 *  - Evren                                                       *
 *                                                                *
 *  Jorge Ribeiro Pereira <si22668@ci.uminho.pt>      20/12/1998  *
 *                                                                *
 ******************************************************************/

#if defined( macintosh )
#include <types.h>
#else
#include <sys/types.h>
#endif
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <time.h>
#include "merc.h"


/**************************************************************************
 *                                                                        *
 * IMPORTANT FUNCTIONS                                                    *
 * ( note: since the core functions are recursive, most of them need some *
 *         extra parameters,  but  since  they  aren't needed outside,  I *
 *         provide the following functions, that serve as entrance to the *
 *         auxiliar functions (which have "_" appended to their name)     *
 *                                                                        *
 **************************************************************************/

// If you plan to use these functions out from this file,
// THIS SHOULD GO INTO merc.h, FROM HERE -->

typedef struct path_data 	PATH_DATA;

typedef bool ROOM_CMP_FUN 	( ROOM_INDEX_DATA * pRoom,
                            	  void * pArgument );

struct path_data
{
   ROOM_INDEX_DATA	* pRoom;	// room
   int			  dir;		// direction from the previous room
   PATH_DATA		* next;		// next room in path
};

int get_direction		( ROOM_INDEX_DATA * pOrig,
                    	  	  ROOM_INDEX_DATA * pDest, bool pass );
PATH_DATA * get_path		( ROOM_INDEX_DATA * pOrig,
                       	  	  ROOM_INDEX_DATA * pDest, bool pass );

int get_dir_somewhere		( ROOM_INDEX_DATA *pOrig,
                       		  ROOM_CMP_FUN *function, 
                       		  void *pArgument, bool pass );
PATH_DATA * get_path_somewhere	( ROOM_INDEX_DATA *pOrig,
                       		  ROOM_CMP_FUN *function, 
                       		  void *pArgument, bool pass );

void free_path			( PATH_DATA **list );
char * path_string		( PATH_DATA *path );


// <------- TO HERE

/*************************************************************************/

#define	VISITED( room )		( (room)->visited )

// this piece of code is alike in all functions,t shows up, but I'm 
// not gonna make a function out of it due to performance issues
#define IGNORE_ROOM( pOrig, i, pRoom, pass )\
(   !pOrig->exit[i]\
 || !( pRoom = pOrig->exit[i]->to_room )\
 || (  !pass && !IS_SET( pOrig->exit[i]->exit_flags, EX_CLOSED ) )\
 || pOrig->area != pRoom->area  )


// auxiliar data structures
typedef struct full_path_data	FULL_PATH_DATA;	
struct full_path_data		// structure for returning a path and its
{				// length (needed to find the the best path)
   int		  length;	// used in: get_path_, get_path_somewhere
   PATH_DATA	* path;
};

typedef struct dir_data		DIR_DATA;
struct dir_data			// structure for returning the best direction
{				// and the length of the path( needed to find
   int		  length;	// the best direction )
   int		  dir;		// used in: get_direction_, get_dir_somewhere_
};


/*
 *  AUXILIAR FUNCTIONS
 */
// creating a new room for a path
PATH_DATA *new_path_data( ROOM_INDEX_DATA *pRoom, int dir )
{
   PATH_DATA *v;

   v = malloc( sizeof (PATH_DATA) );

   v->pRoom		= pRoom; 
   v->dir		= dir;
   v->next		= NULL;
   return v;
}

// add a room to a path
void append_path( PATH_DATA **list, ROOM_INDEX_DATA *pRoom, int dir )
{
   PATH_DATA *v;

   v = malloc( sizeof (PATH_DATA) );

   v->pRoom		= pRoom; 
   v->dir		= dir;
   v->next		= *list;
   *list		= v;

   return;
}

// freeing memory for a path
void free_path( PATH_DATA **list )
{
   PATH_DATA **v, *v_next;

   if ( !*list )
      return;

   for ( v = list; *v; )
   {
      v_next = (*v)->next;
      free( *v );
      *v = v_next;
   }
}

char * path_string( PATH_DATA *path )
{
   static char buf[MAX_STRING_LENGTH];

   buf[0] = '\0';
   for ( ; path; path = path->next )
   {
      strcat( buf, dir_name[path->dir] );
      if ( path->next && path->next->next )
         strcat( buf, ", " );
      else if ( path->next )
         strcat( buf, " and " );
   }
   return buf;
}

// This function returns a structure with the path length and the direction.
// Use get_direction(below), to get just the direction.
DIR_DATA get_direction_( ROOM_INDEX_DATA *pOrig,
                         ROOM_INDEX_DATA *pDest, bool pass )
{
   ROOM_INDEX_DATA *pRoom;
   int i;
   DIR_DATA tmp, best;

   if ( pOrig == pDest )
   {
      best.dir		= -1; 
      best.length	= 1;
      return best;
   }

   best.dir	= tmp.dir	= -1;
   best.length	= tmp.length	= 0;

   VISITED( pOrig ) = TRUE;
   for ( i = 0; i< MAX_DIR; i++ )
   {
      if ( IGNORE_ROOM( pOrig, i, pRoom, pass ) )
         continue;

      if ( VISITED( pRoom ) )
         continue;
   
      tmp = get_direction_( pRoom, pDest, pass ); // recursion

      if ( tmp.length < 1 )
         continue;

      if ( best.length == 0 || tmp.length < best.length )
      {
          best.dir	= i;
          best.length	= tmp.length + 1;
      }
   }
   VISITED( pOrig ) = FALSE;

   return best;
}

DIR_DATA get_dir_somewhere_( ROOM_INDEX_DATA *pOrig,
                             ROOM_CMP_FUN *function, 
                             void *pArgument,
                             bool pass )
{
   ROOM_INDEX_DATA *pRoom;
   int i;
   DIR_DATA tmp, best;

   if ( (function)( pOrig, pArgument ) ) // the only change from get_direction_
   {
       best.dir		= -1;
       best.length	= 1;
       return best;
   }

   best.dir	= tmp.dir	= -1;
   best.length	= tmp.length	= 0;

   VISITED( pOrig ) = TRUE;
   for ( i = 0; i< MAX_DIR; i++ )
   {
      if ( IGNORE_ROOM( pOrig, i, pRoom, pass ) )
         continue;
   
      if ( VISITED( pRoom ) )
         continue;
   
      tmp = get_dir_somewhere_( pRoom, function, pArgument, pass ); 

      if ( tmp.length < 1 )
         continue;

      if ( best.length == 0 || tmp.length < best.length )
      {
          best.dir	= i;
          best.length	= tmp.length + 1;
      }
   }
   VISITED( pOrig ) = FALSE;

   return best;
}


FULL_PATH_DATA get_path_( ROOM_INDEX_DATA *pOrig, ROOM_INDEX_DATA *pDest,
                          bool pass )
{
   int i;
   FULL_PATH_DATA tmp, best;
   ROOM_INDEX_DATA *pRoom;

   if ( pOrig == pDest )
   {
       best.length      = 1;
       best.path	= NULL;
       return best;
   }
   
   tmp.length	= best.length	= 0;
   tmp.path	= best.path	= NULL;

   VISITED( pOrig ) = TRUE;
   for ( i = 0; i < MAX_DIR; i++ )
   {
      if ( IGNORE_ROOM( pOrig, i, pRoom, pass ) )
         continue;

      if ( VISITED( pRoom ) )
         continue;

      tmp = get_path_( pRoom, pDest, pass );

      if ( tmp.length < 1 )
         continue;
      
      if ( best.length == 0 || tmp.length < best.length )
      {
         free_path( &best.path );
         best.length	 = tmp.length + 1;
         best.path	 = tmp.path;
         append_path( &best.path, pRoom, i );
      }
      else
      {
         free_path( &tmp.path );
      }
   }
   VISITED( pOrig ) = FALSE;

   return best;
}


FULL_PATH_DATA get_path_somewhere_( ROOM_INDEX_DATA *pOrig,
                                    ROOM_CMP_FUN *function, 
                                    void *pArgument, bool pass )
{
   int i;
   FULL_PATH_DATA tmp, best;
   ROOM_INDEX_DATA *pRoom;

   if ( (function)( pOrig, pArgument ) ) 
   {
       best.length      = 1;
       best.path	= NULL;
       return best;
   }

   tmp.length	= best.length	= 0;
   tmp.path	= best.path	= NULL;

   VISITED( pOrig ) = TRUE;
   for ( i = 0; i < MAX_DIR; i++ )
   {
      if ( IGNORE_ROOM( pOrig, i, pRoom, pass ) )
         continue;

      if ( VISITED( pRoom ) )
         continue;

      tmp = get_path_somewhere_( pRoom, function, pArgument, pass );

      if ( tmp.length < 1 )
         continue;
      
      if ( best.length  == 0 || tmp.length < best.length )
      {
         free_path( &best.path );
         best.length	 = tmp.length + 1;
         best.path	 = tmp.path;
         append_path( &best.path, pRoom, i );
      }
      else
      {
         free_path( &tmp.path );
      }
   }
   VISITED( pOrig ) = FALSE;

   return best;
}

/***********************************************************************/

int get_direction( ROOM_INDEX_DATA *pOrig,
                    ROOM_INDEX_DATA *pDest, bool pass )
{
   return get_direction_( pOrig, pDest, pass ).dir;
}


PATH_DATA * get_path( ROOM_INDEX_DATA *pOrig,
                     ROOM_INDEX_DATA *pDest, bool pass )
{
   return get_path_( pOrig, pDest, pass ).path;
}


int get_dir_somewhere( ROOM_INDEX_DATA *pOrig,
                       ROOM_CMP_FUN *function, 
                       void *pArgument, bool pass )
{
   return get_dir_somewhere_( pOrig, function, pArgument, pass ).dir;
}


PATH_DATA * get_path_somewhere( ROOM_INDEX_DATA *pOrig,
                                ROOM_CMP_FUN *function, 
                                void *pArgument, bool pass )
{
   return get_path_somewhere_( pOrig, function, pArgument, pass ).path;
}


/**************************************************************************/

void do_path( CHAR_DATA *ch, char *argument )
{
  ROOM_INDEX_DATA	* pDest;
  PATH_DATA		* path;
  char 			  arg[MAX_INPUT_LENGTH];
  int 			  vnum;
  char			  buf[MAX_STRING_LENGTH];

  argument = one_argument( argument, arg );

  if ( arg[0] == '\0' )
  {
     send_to_char( "Find path to which room (vnum)?\n\r", ch );
     return;
  }

  if ( ( vnum = atoi( arg ) ) <= 0 )   
  {  
     send_to_char( "Invalid room vnum.\n\r", ch );
     return;
  }

  if ( !( pDest = get_room_index( vnum ) ) )
  {  
     send_to_char( "Destination room not found.\n\r", ch );
     return;
  }

  if ( ch->in_room == pDest )
  {  
     send_to_char( "I suggest you stay right where you are.\n\r", ch );
     return;
  }

  path = get_path( ch->in_room, pDest, TRUE );

  if ( !path )
  {  
     send_to_char( "No path found.\n\r", ch );
     return;
  }

  sprintf( buf, "To get there you'll have to go: %s.\n\r",
                path_string( path ) );
  
  free_path( &path );		// don't forget to free the memory used

  send_to_char( buf, ch );
}


void do_direction( CHAR_DATA *ch, char *argument )
{ 
  ROOM_INDEX_DATA       * pDest;
  char                    arg[MAX_INPUT_LENGTH];
  int                     vnum;
  char                    buf[MAX_STRING_LENGTH];
  int dir;

  argument = one_argument( argument, arg );

  if ( arg[0] == '\0' )
  {
     send_to_char( "Find direction to which room (vnum)?\n\r", ch );
     return;
  }

  if ( ( vnum = atoi( arg ) ) <= 0 )
  {
     send_to_char( "Invalid room vnum.\n\r", ch );
     return;
  }

  if ( !( pDest = get_room_index( vnum ) ) )
  {  
     send_to_char( "Destination room not found.\n\r", ch );
     return;
  }

  if ( ch->in_room == pDest )
  {  
     send_to_char( "I suggest you stay right where you are.\n\r", ch );
     return;
  }

  dir = get_direction( ch->in_room, pDest, TRUE );

  if ( dir == -1 )
  {  
     send_to_char( "No path found.\n\r", ch );
     return;
  }

  sprintf( buf, "I suggest you go %s.\n\r", dir_name[dir] );
  send_to_char( buf, ch );
}


/**********************************************************************/

// see how simple it is?
bool is_room_name( ROOM_INDEX_DATA *pRoom, void * pArgument )
{
   char *argument = (char *) pArgument;
   return is_name( argument, pRoom->name );
}

void do_whereto( CHAR_DATA *ch, char *argument )
{
   PATH_DATA *path;
   char buf[MAX_STRING_LENGTH];

   if ( argument[0] == '\0' )
   {
      // I hope this sentence isn't MS copyrighted...
      send_to_char( "Where do you want to go? \n\r", ch );
      return;
   }

   path = get_path_somewhere( ch->in_room, is_room_name,
                              argument, TRUE );

   if ( !path )
   {
      send_to_char( "You can't remember how to get there.\n\r", ch );
      return;
   }

   sprintf( buf, "To get to %s you'll have to go: %s.\n\r",
                 argument, path_string( path ) );

   free_path( &path );           // don't forget to free the memory used
 
   send_to_char( buf, ch );
}


/* NOTE FOR PROGRAMMERS
If we didn't care for performance, we could carve get_direction_
and get_path_ out from get_dir_somewhere_ and get_path_somewhere_
using the following predicate function:

bool is_equal( ROOM_INDEX_DATA *pRoom, void * pArgument )
{
   ROOM_INDEX_DATA *pDest = (ROOM_INDEX_DATA *) pArgument;
   return pRoom == pDest;
}

and passing the destination room pointer as the pArgument to the _somewhere_
functions.
*/