/*
File     : hamster.c
Contents : hamster control program
Author   : Even Langer
*/

#include <stdio.h>
#include <stdlib.h>
#include "hamster.h"
#define null 0


/*
Declarations of the list and the node
*/

typedef struct node     *pnode;
typedef struct nodelist *plist;

typedef struct node
{
 int x,y;
 int corn;
 int come_from;
 plist south;
 plist north;
 plist east;
 plist west;
 plist pred;
 plist pred2;
 int swall;
 int nwall;
 int ewall;
 int wwall;
 int dist;
 int dist2;
} nodeelement;

typedef struct nodelist
{
 plist next;
 pnode data;
} listelement;


/*
Declaration of the queue
*/

typedef struct queue_struct *pqueue;
typedef struct queue_struct
{
 plist  node;
 pqueue next;
} queue_element;


/*
Declaration of the stack
*/

typedef struct stack_struct *pstack;
typedef struct stack_struct
{
 plist  node;
 pstack next;
} stack_element;


/*
Declarations of the used functions
*/

void  get_corn ( plist list , HAMSTER *HMS );
plist node_in_list ( plist list , int x , int y );
pnode create_node ( void );
void  determine_walls ( pnode node , HAMSTER *HMS );
int   determine_next_way ( pnode node, HAMSTER *HMS );
int   allfind ( plist list );
plist find_next_corn ( plist list , plist help , HAMSTER *HMS );

pqueue pushtail ( pqueue pos , plist help );
pqueue pophead ( pqueue pos , plist *help );

pstack push ( pstack stack , plist help );
pstack pop ( pstack stack , plist *help );





/*
Mainprogram
*/

void hms_ctrl (HAMSTER *HMS)
{
 int      x , y;
 plist 	 list;
 plist    temp;
 plist    help;
 pnode    node;
 int      find;
 int      stop = 0;
 pqueue   pos = null;
 pstack   stack = null;
 /* create node with x,y values 0  ( home ) */

 node = create_node ();
 if ( node == null ) { stop = 1; }
 list = (plist) malloc ( sizeof ( listelement ));
 if ( list == null ) { stop = 1; }

 determine_walls ( node , HMS );
 node->x = 0;
 node->y = 0;
 node->corn = hms_corn ( HMS );
 list->data = node;
 list->next = null;
 node->come_from = 4;

 switch ( hms_dir ( HMS ))
   {
   case HMS_EAST : {
                   if ( node->ewall == 1 ) { break; }
                   if ( node->nwall == 1 )
                     {
                     hms_turn ( HMS , HMS_LEFT );
                     break;
                     }
                   if ( node->swall == 1 )
                     {
                     hms_turn ( HMS , HMS_RIGHT );
                     break;
                     }
                   else
                     {
                     hms_turn ( HMS , HMS_RIGHT );
                     hms_turn ( HMS , HMS_RIGHT );
                     }
                   break;
   				    }
   case HMS_WEST : {
                   if ( node->wwall == 1 ) { break; }
                   if ( node->swall == 1 )
                     {
                     hms_turn ( HMS , HMS_LEFT );
                     break;
                     }
                   if ( node->nwall == 1 )
                     {
                     hms_turn ( HMS , HMS_RIGHT );
                     break;
                     }
                   else
                     {
                     hms_turn ( HMS , HMS_RIGHT );
                     hms_turn ( HMS , HMS_RIGHT );
                     }
                   break;
   				    }
   case HMS_NORTH : {
                    if ( node->nwall == 1 ) { break; }
                    if ( node->ewall == 1 )
                      {
                      hms_turn ( HMS , HMS_RIGHT );
                      break;
                      }
                    if ( node->wwall == 1 )
                      {
                      hms_turn ( HMS , HMS_LEFT );
                      break;
                      }
                    else
                      {
                      hms_turn ( HMS , HMS_RIGHT );
                      hms_turn ( HMS , HMS_RIGHT );
                      }
                    break;
   			        }
   case HMS_SOUTH : {
                    if ( node->swall == 1 ) { break; }
                    if ( node->wwall == 1 )
                      {
                      hms_turn ( HMS , HMS_RIGHT );
                      break;
                      }
                    if ( node->ewall == 1 )
                      {
                      hms_turn ( HMS , HMS_LEFT );
                      break;
                      }
                    else
                      {
                      hms_turn ( HMS , HMS_RIGHT );
                      hms_turn ( HMS , HMS_RIGHT );
                      }
                    break;
   				     }
   }
 hms_move ( HMS );



 /* while not all nodes are 'catched', do ... */

 while ( stop == 0 )
   {
   hms_pos(HMS, &x, &y);

   /* search node in list */

   temp = list;
   find = 0;
   while (( temp->next != 0 )&&( find == 0 ))
     {
     if (( temp->data->x == x )&&( temp->data->y == y ))
       { find = 1; }
     else
       { temp = temp->next; }
     }

   if ( find == 0 )
     {
     node = create_node ();
     if ( node == null ) { stop = 1; }
     help = (plist) malloc ( sizeof ( listelement ));
     if ( help == null ) { stop = 1; }

     node->x = x;
     node->y = y;
     node->corn = hms_corn ( HMS );

     if ( node->corn <= 2 )
       {
       hms_take ( HMS , HMS_MAXLOAD );
       node->corn = hms_corn ( HMS );
       }

     determine_walls ( node , HMS );

     if ( node->swall == 1 )
       {
       node->south = node_in_list ( list , x , y-1 );
       if ( node->south != null ) node->south->data->north = help;
       }
     if ( node->nwall == 1 )
       {
       node->north = node_in_list ( list , x , y+1 );
       if ( node->north != null ) node->north->data->south = help;
       }
     if ( node->ewall == 1 )
       {
       node->east  = node_in_list ( list , x+1 , y );
       if ( node->east != null ) node->east->data->west = help;
       }
     if ( node->wwall == 1 )
       {
       node->west  = node_in_list ( list , x-1 , y );
       if ( node->west != null ) node->west->data->east = help;
       }

     help->data = node;
     help->next = temp->next;
     temp->next = help;
     temp = help;
     }


   /* determine next way ( look for walls ) */

   stop = determine_next_way ( temp->data , HMS );

   if ( allfind ( list ) == 1 ) stop = 1;

   /* go forward */

   if ( stop == 0 ) hms_move( HMS );
   }

 help->data->corn -= hms_take ( HMS , HMS_MAXLOAD );

 pos = pushtail ( pos , help );

 while ( pos != null )
   {
   pos = pophead ( pos , &temp );
   node = temp->data;

   if (( node->ewall == 1 )&&( node->east->data->pred == null ))
     {
     node->east->data->pred = temp;
     node->east->data->dist = temp->data->dist + 1;
     pos = pushtail ( pos , node->east );
     }
   if (( node->wwall == 1 )&&( node->west->data->pred == null ))
     {
     node->west->data->pred = temp;
     node->west->data->dist = temp->data->dist + 1;
     pos = pushtail ( pos , node->west );
     }
   if (( node->swall == 1 )&&( node->south->data->pred == null ))
     {
     node->south->data->pred = temp;
     node->south->data->dist = temp->data->dist + 1;
     pos = pushtail ( pos , node->south );
     }
   if (( node->nwall == 1 )&&( node->north->data->pred == null ))
     {
     node->north->data->pred = temp;
     node->north->data->dist = temp->data->dist + 1;
     pos = pushtail ( pos , node->north );
     }
   }

 temp = list;
 stack = push ( stack , temp );
 while ( temp->data->pred != help )
   {
   stack = push ( stack , temp->data->pred );
   temp = temp->data->pred;
   }

 temp = help;

 while ( stack != 0 )
   {
   stack = pop ( stack , &help );

   if ( temp->data->south == help )
     while ( hms_dir ( HMS ) != HMS_SOUTH )
       hms_turn ( HMS , HMS_RIGHT );
	if ( temp->data->north == help )
     while ( hms_dir ( HMS ) != HMS_NORTH )
       hms_turn ( HMS , HMS_RIGHT );
   if ( temp->data->east == help )
     while ( hms_dir ( HMS ) != HMS_EAST )
       hms_turn ( HMS , HMS_RIGHT );
   if ( temp->data->west == help )
     while ( hms_dir ( HMS ) != HMS_WEST )
       hms_turn ( HMS , HMS_RIGHT );

   hms_move ( HMS );
   temp = help;
   }

 hms_drop ( HMS , HMS_MAXLOAD );

 temp = list;
 while ( temp != null )
   {
   temp->data->pred = null;
   temp->data->dist = 0;
   temp = temp->next;
   }

 /* find the shortest way from home ( 0,0 ) to each node */

 pos = pushtail ( pos , list );

 while ( pos != null )
   {
   pos = pophead ( pos , &help );
   node = help->data;

   if (( node->ewall == 1 )&&( node->east->data->pred == null ))
     {
     node->east->data->pred = help;
     node->east->data->dist = help->data->dist + 1;
     pos = pushtail ( pos , node->east );
     }
   if (( node->wwall == 1 )&&( node->west->data->pred == null ))
     {
     node->west->data->pred = help;
     node->west->data->dist = help->data->dist + 1;
     pos = pushtail ( pos , node->west );
     }
   if (( node->swall == 1 )&&( node->south->data->pred == null ))
     {
     node->south->data->pred = help;
     node->south->data->dist = help->data->dist + 1;
     pos = pushtail ( pos , node->south );
     }
   if (( node->nwall == 1 )&&( node->north->data->pred == null ))
     {
     node->north->data->pred = help;
     node->north->data->dist = help->data->dist + 1;
     pos = pushtail ( pos , node->north );
     }
   }

 /* get the corn */

 get_corn ( list , HMS );
}






/*
Function    : find_next_corn
Parameter   : pointer to the begin of the list and to the node,
              number of corn
Returnvalue : pointer top the found node
*/

plist find_next_corn ( plist list , plist help , HAMSTER *HMS )
{
 if ( help->data->south != null )
   if ( help->data->south->data->corn != 0 )
     {
     while ( hms_dir ( HMS ) != HMS_SOUTH )
       hms_turn ( HMS , HMS_RIGHT );
     hms_move ( HMS );

     help->data->south->data->corn -= hms_take ( HMS , HMS_MAXLOAD );

     hms_turn ( HMS , HMS_RIGHT );
     hms_turn ( HMS , HMS_RIGHT );
     hms_move ( HMS );
     }
 if ( help->data->west != null )
   if ( help->data->west->data->corn != 0 )
     {
     while ( hms_dir ( HMS ) != HMS_WEST )
       hms_turn ( HMS , HMS_RIGHT );
     hms_move ( HMS );

     help->data->west->data->corn -= hms_take ( HMS , HMS_MAXLOAD );

     hms_turn ( HMS , HMS_RIGHT );
     hms_turn ( HMS , HMS_RIGHT );
     hms_move ( HMS );
     }
 if ( help->data->north != null )
   if ( help->data->north->data->corn != 0 )
     {
     while ( hms_dir ( HMS ) != HMS_NORTH )
       hms_turn ( HMS , HMS_RIGHT );
     hms_move ( HMS );

     help->data->north->data->corn -= hms_take ( HMS , HMS_MAXLOAD );

     hms_turn ( HMS , HMS_RIGHT );
     hms_turn ( HMS , HMS_RIGHT );
     hms_move ( HMS );
     }
 if ( help->data->east != null )
   if ( help->data->east->data->corn != 0 )
     {
     while ( hms_dir ( HMS ) != HMS_EAST )
       hms_turn ( HMS , HMS_RIGHT );
     hms_move ( HMS );

     help->data->east->data->corn -= hms_take ( HMS , HMS_MAXLOAD );

     hms_turn ( HMS , HMS_RIGHT );
     hms_turn ( HMS , HMS_RIGHT );
     hms_move ( HMS );

     }

 return help;
}


/*
Function    : get_corn
Parameter   : pointer of the begin of the list
Returnvalue : -
*/

void get_corn ( plist list , HAMSTER *HMS )
{
 plist  temp = list->next;
 plist  help , temp2;
 pstack stack = null;
 int    corn;

 while ( temp != null )
   {
   corn = temp->data->corn;
   while ( corn != 0 )
     {
     if (( temp->data->dist >= 10 * 12 )&&( corn > HMS_MAXLOAD )) break;
     /* Anfang Korrektur, Christian Borgelt, 16.06.1998 */
     /* In der untigen if-Anweisung wurde "ubersehen, da\3 die Zeiger */
     /* auf die in westlicher, "ostlicher etc. Richung liegenden Felder, */
     /* d.h. die Zeiger temp->data->west, etc. auch NULL sein k"onnen. */
     /* Sind sie es, wird "uber einen NULL-Zeiger zugegriffen, was zu */
     /* einer Speicherverletzung und damit zum Programmabsturz f"uhrt. */
     #if 1
     if (( temp->data->dist >= 10 * corn )&&( corn < HMS_MAXLOAD )
     && ((temp->data->east  ? temp->data->east ->data->corn : 0)
     +   (temp->data->west  ? temp->data->west ->data->corn : 0)
     +   (temp->data->south ? temp->data->south->data->corn : 0)
     +   (temp->data->north ? temp->data->north->data->corn : 0)
     + corn < HMS_MAXLOAD )) break;
     #else
     if (( temp->data->dist >= 10 * corn )&&( corn < HMS_MAXLOAD ))
       if ( temp->data->east->data->corn + temp->data->west->data->corn +
            temp->data->south->data->corn + temp->data->north->data->corn +
            corn < HMS_MAXLOAD ) break;
     #endif
     /* Ende Korrektur, Christian Borgelt, 16.06.1998 */

     help = temp;
     stack = push ( stack , temp );

     while ( help->data->pred != list )
       {
       stack = push ( stack , help->data->pred );
       help = help->data->pred;
       }
     temp2 = list;

     while ( stack != 0 )
       {
       stack = pop ( stack , &help );

       if ( temp2->data->south == help )
         while ( hms_dir ( HMS ) != HMS_SOUTH )
           hms_turn ( HMS , HMS_RIGHT );
		 if ( temp2->data->north == help )
         while ( hms_dir ( HMS ) != HMS_NORTH )
           hms_turn ( HMS , HMS_RIGHT );
		 if ( temp2->data->east == help )
         while ( hms_dir ( HMS ) != HMS_EAST )
           hms_turn ( HMS , HMS_RIGHT );
		 if ( temp2->data->west == help )
         while ( hms_dir ( HMS ) != HMS_WEST )
           hms_turn ( HMS , HMS_RIGHT );

       hms_move ( HMS );
       temp2 = help;
       }

     corn -= hms_take ( HMS , HMS_MAXLOAD );
     temp->data->corn = corn;

     if ( corn < 12 )
       {
       find_next_corn ( list , temp , HMS );
       }

     /*temp2 = temp;*/

     while ( temp2->data->come_from != 4 )
       {
       if ( temp2->data->south == temp2->data->pred )
         while ( hms_dir ( HMS ) != HMS_SOUTH )
           hms_turn ( HMS , HMS_RIGHT );
		 if ( temp2->data->north == temp2->data->pred )
         while ( hms_dir ( HMS ) != HMS_NORTH )
           hms_turn ( HMS , HMS_RIGHT );
		 if ( temp2->data->east == temp2->data->pred )
         while ( hms_dir ( HMS ) != HMS_EAST )
           hms_turn ( HMS , HMS_RIGHT );
		 if ( temp2->data->west == temp2->data->pred )
         while ( hms_dir ( HMS ) != HMS_WEST )
           hms_turn ( HMS , HMS_RIGHT );

       hms_move ( HMS );
       temp2 = temp2->data->pred;
       }

     hms_drop ( HMS , HMS_MAXLOAD );
     }
   temp = temp->next;
   }
}


/*
Function    : node_in_list
Parameter   : pointer of the beginning of the nodelist,
			     coordinates x and y
Returnvalue : pointer to the element with the coordinates x,y or null
*/

plist node_in_list ( plist list , int x , int y )
{
 plist temp = list;

 while (( temp != null )&&(( temp->data->x != x )||( temp->data->y != y )))
   {
   temp = temp->next;
   }

 return temp;
}



/*
Function    : create_node
Parameter	: -
Returnvalue : pointer to the node
*/

pnode create_node ( void )
{
 pnode node;

 node = (pnode) malloc ( sizeof ( nodeelement ));

 node->north = null;
 node->south = null;
 node->west  = null;
 node->east  = null;
 node->pred  = null;

 /* no wall = 1 , wall = 0 */

 node->nwall = 1;
 node->swall = 1;
 node->wwall = 1;
 node->ewall = 1;
 node->dist  = 0;

 return node;
}



/*
Function    : determine_walls
Parameter   : pointer to the node
Returnvalue : -
*/

void  determine_walls ( pnode node , HAMSTER *HMS )
{
 int dir;

 dir = hms_dir ( HMS );

 switch ( dir )
   {
   case HMS_EAST :
           {
           if ( hms_look ( HMS ) == HMS_WALL ) { node->ewall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->swall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->wwall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->nwall = 0; }
           hms_turn ( HMS , HMS_RIGHT );

           node->come_from = HMS_WEST;
           break;
           }
   case HMS_NORTH :
           {
           if ( hms_look ( HMS ) == HMS_WALL ) { node->nwall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->ewall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->swall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->wwall = 0; }
           hms_turn ( HMS , HMS_RIGHT );

           node->come_from = HMS_SOUTH;
           break;
           }
   case HMS_WEST :
           {
           if ( hms_look ( HMS ) == HMS_WALL ) { node->wwall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->nwall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->ewall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->swall = 0; }
           hms_turn ( HMS , HMS_RIGHT );

           node->come_from = HMS_EAST;
           break;
           }
   case HMS_SOUTH :
           {
           if ( hms_look ( HMS ) == HMS_WALL ) { node->swall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->wwall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->nwall = 0; }
           hms_turn ( HMS , HMS_RIGHT );
           if ( hms_look ( HMS ) == HMS_WALL ) { node->ewall = 0; }
           hms_turn ( HMS , HMS_RIGHT );

           node->come_from = HMS_NORTH;
           break;
           }
   }
}


/*
Function    : determine_next_way
Parameter   : pointer to the node
Returnvalue : 1 or 0
*/

int determine_next_way ( pnode node , HAMSTER *HMS )
{
 switch ( hms_dir ( HMS ))
   {
   case HMS_EAST : {
                   if (( node->ewall == 1 )&&( node->east == null )) { break; }
                   if (( node->nwall == 1 )&&( node->north == null ))
                     {
                     hms_turn ( HMS , HMS_LEFT );
                     break;
                     }
                   if (( node->swall == 1 )&&( node->south == null ))
                     {
                     hms_turn ( HMS , HMS_RIGHT );
                     break;
                     }
                   else
                     {
                     if ( node->come_from == 4 )
                       return 1;
                     else
                       while ( hms_dir ( HMS ) != node->come_from )
                         hms_turn ( HMS , HMS_RIGHT );
                     }
                   break;
   				    }
   case HMS_WEST : {
                   if (( node->wwall == 1 )&&( node->west == null )) { break; }
                   if (( node->swall == 1 )&&( node->south == null ))
                     {
                     hms_turn ( HMS , HMS_LEFT );
                     break;
                     }
                   if (( node->nwall == 1 )&&( node->north == null ))
                     {
                     hms_turn ( HMS , HMS_RIGHT );
                     break;
                     }
                   else
                     {
                     if ( node->come_from == 4 )
                       return 1;
                     else
                       while ( hms_dir ( HMS ) != node->come_from )
                         hms_turn ( HMS , HMS_RIGHT );
                     }
                   break;
   				    }
   case HMS_NORTH : {
                    if (( node->nwall == 1 )&&( node->north == null )) { break; }
                    if (( node->ewall == 1 )&&( node->east == null ))
                      {
                      hms_turn ( HMS , HMS_RIGHT );
                      break;
                      }
                    if (( node->wwall == 1 )&&( node->west == null ))
                      {
                      hms_turn ( HMS , HMS_LEFT );
                      break;
                      }
                    else
                      {
                      if ( node->come_from == 4 )
                        return 1;
                      else
                        while ( hms_dir ( HMS ) != node->come_from )
                          hms_turn ( HMS , HMS_RIGHT );
                      }
                    break;
   			        }
   case HMS_SOUTH : {
                    if (( node->swall == 1 )&&( node->south == null )) { break; }
                    if (( node->wwall == 1 )&&( node->west == null ))
                      {
                      hms_turn ( HMS , HMS_RIGHT );
                      break;
                      }
                    if (( node->ewall == 1 )&&( node->east == null ))
                      {
                      hms_turn ( HMS , HMS_LEFT );
                      break;
                      }
                    else
                      {
                      if ( node->come_from == 4 )
                        return 1;
                      else
                        while ( hms_dir ( HMS ) != node->come_from )
                          hms_turn ( HMS , HMS_RIGHT );
                      }
                    break;
   				     }
   }
 return 0;
}


/*
Function    : allfind
Parameter   : pointer to the begin of the list
Returnvalue : 1, if all nodes are find, else 0
*/

int allfind ( plist list )
{
 plist temp = list;
 int   stop = 1;

 while (( temp != null )&&( stop == 1 ))
   {
   if (( temp->data->ewall == 1 )&&( temp->data->east == null )) stop = 0;
   if (( temp->data->wwall == 1 )&&( temp->data->west == null )) stop = 0;
   if (( temp->data->nwall == 1 )&&( temp->data->north == null )) stop = 0;
   if (( temp->data->swall == 1 )&&( temp->data->south == null )) stop = 0;

   temp = temp->next;
   }

 return stop;
}


/*
Function    : pushtail
Parameter   : pointer to the queue, pointer to the node
Returnvalue : ( new ) pointer to the queue
*/

pqueue pushtail ( pqueue pos , plist node )
{
 pqueue temp;
 pqueue help = pos;

 temp = (pqueue) malloc ( sizeof( queue_element ));
 temp->next = null;
 temp->node = node;

 if ( help == null )
   {
   return temp;
   }
 else
   {
   while ( help->next != null )
     help = help->next;

   help->next = temp;
   return pos;
   }
}


/*
Function    : pophead ( get the first element of the queue )
Parameter   : pointer to the queue, address of the node
Returnvalue : ( new ) pointer to the queue
*/

pqueue pophead ( pqueue pos , plist *node )
{
 pqueue help;

 if ( pos != null )
   {
   *node = pos->node;
   help = pos;
   pos = pos->next;
   free ( help );
   return pos;
   }
 else
   {
   return null;
   }
}


/*
Function    : push
Parameter   : pointer to the stack, pointer to the node
Returnvalue : ( new ) pointer to the stack
*/

pstack push ( pstack pos , plist node )
{
 pstack temp;

 temp = (pstack) malloc ( sizeof( stack_element ));
 temp->next = pos;
 temp->node = node;
 pos = temp;

 return pos;
}


/*
Function    : pop ( get the first element of the stack )
Parameter   : pointer to the stack, address of the node
Returnvalue : ( new ) pointer to the stack
*/

pstack pop ( pstack pos , plist *node )
{
 pstack help;

 if ( pos != null )
   {
   *node = pos->node;
   help = pos;
   pos = pos->next;
   free ( help );
   return pos;
   }
 else
   {
   return null;
   }
}