/* Autor    : Tobias Rudolph, IF 01 '97                                      */
/* Datum    : 13.06.1998                                                     */
/* Bemerkung: Programm ist keine Belegaufgabe                                */

/* P.S.     : Ich wollte es wirklich kommentieren !                          */






#include <stdio.h>
#include <stdlib.h>
#include "hamster.h"


/*###########################################################################*/
/* some definitions / declarations                                           */
/*###########################################################################*/

#define WALL ((void *)1)

typedef enum {FALSE, TRUE} bool;

typedef struct coordtype
          {
	    int x;
	    int y;
          } coordinate;

typedef struct MAPTYPE *mapnode;
typedef struct MAPTYPE
          {
            coordinate pos;
	    int corn;
  
	    mapnode nb[4];
	  
	    mapnode next;

	    mapnode prev[2];
	    int dist[2];
	    bool ok;

          } MAPNODE;



/*###########################################################################*/


/*---------------------------------------------------------------------------*/
void get_coordinate(coordinate *pos, int dir)
{
  switch (dir)
    {
    case HMS_EAST  : pos -> x ++;
                     break;
    case HMS_WEST  : pos -> x --;
                     break;
    case HMS_NORTH : pos -> y ++;
                     break;
    case HMS_SOUTH : pos -> y --;
                     break;
    }
}


/*---------------------------------------------------------------------------*/
int next_step(HAMSTER *hms, mapnode from, mapnode to)
{
  int position;
  int step;

  if (from == to) return -1;

  if (to -> pos.x < from -> pos.x)
    position = HMS_WEST;
  else 
    if (to -> pos.x > from -> pos.x)
      position = HMS_EAST;
  else
    if (to -> pos.y < from -> pos.y)
      position = HMS_SOUTH;
  else 
    position = HMS_NORTH;

  switch (hms_dir(hms) - position)
    {
    case 0 : step = 0;
             break;
    case -1:
    case 3 : step = 1;
             break;
    case -2:
    case 2 : step = 2;
             break;
    case 1 :
    case -3: step = 3;
             break;
    }

  return step;
}


/*---------------------------------------------------------------------------*/
bool cmp(coordinate pos1, coordinate pos2)
{
  return ((pos1.x == pos2.x) && (pos1.y == pos2.y));
}


/*---------------------------------------------------------------------------*/
mapnode is_known(mapnode map, coordinate pos)
{
  mapnode temp = map;

  do
    {
      if (cmp(temp -> pos, pos) == TRUE)
	return temp;

      temp = temp -> next;
    }
  while (temp != map);

  return NULL;
}



/*---------------------------------------------------------------------------*/
void reset_waylist0(mapnode map)
{
  coordinate test = {0,0};
  mapnode temp = map;

  do
    {
      temp -> ok = FALSE;
      if (cmp(temp -> pos, test) == FALSE)
	temp -> dist[0] = 10000;

      temp = temp -> next;
    }
  while (temp != map);
}


/*---------------------------------------------------------------------------*/
void reset_waylist1(mapnode map)
{
  mapnode temp = map;

  do
    {
      temp -> ok = FALSE;
      temp -> dist[1] = 10000;
      
      temp = temp -> next;
    }
  while (temp != map);

  map -> dist[1] = 0;
  map -> prev[1] = map;
}


/*---------------------------------------------------------------------------*/
bool edge_exist(mapnode v1, mapnode v2)
{
  int i;

  for (i = 0; i <= 3; i++)
    if (v1 -> nb[i] == v2) return TRUE;

  return FALSE;
}


/*---------------------------------------------------------------------------*/
void shortest_ways(mapnode map, int way)
{
  mapnode temp;
  mapnode v;
  int min;

  if (way == 0)
    reset_waylist0(map);
  else
    reset_waylist1(map);

  do
    {
      min = 10000;
      temp = map;
      v = NULL;

      do
	{
	  if ((temp -> ok == FALSE) &&
	      (temp -> dist[way] < min))
	    {
	      min = temp -> dist[way];
	      v = temp;
	    }
	  temp = temp -> next;	  
	}
      while (temp != map);

      if (v != NULL)
	v -> ok = TRUE;

      temp = map;

      do
	{
	  if ((temp -> ok == FALSE) &&
	      (edge_exist(v, temp) == TRUE))
	    if (temp -> dist[way] > v -> dist[way] + 1)
	      {
		temp -> dist[way] = v -> dist[way] + 1;
		temp -> prev[way] = v;
	      }
	  temp = temp -> next;
	}
      while (temp != map);
    }
  while (v != NULL); 
}


/*---------------------------------------------------------------------------*/
mapnode way_to_corn(mapnode map, int *distance)
{
  mapnode temp = map;
  mapnode v = NULL;
  int min = 10000;

  do
    {
      if ((temp -> corn > 0) &&
	  (temp -> dist[1] < min))
	{
	  min = temp -> dist[1];
	  v = temp;
	}
      temp = temp -> next;
    }      
  while (temp != map);

  *distance = min;
  return v;
}


/*---------------------------------------------------------------------------*/
mapnode way_to_field(mapnode map, int what, int *distance)
{
  mapnode temp = map;
  mapnode v = NULL;
  int min = 10000;

  do
    {
      if ((temp -> corn == what) &&
	  (temp -> dist[1] < min))
	{
	  min = temp -> dist[1];
	  v = temp;
	}
      temp = temp -> next;
    }      
  while (temp != map);

  *distance = min;
  return v;
}


/*---------------------------------------------------------------------------*/
void make_move(HAMSTER *hms, mapnode *map, mapnode from, mapnode to)
{
  bool flag = FALSE;

  do 
    {
      switch(next_step(hms, from, to))
	{
	case 0 :
	  hms_move(hms);
	  *map = (*map) -> nb[hms_dir(hms)];
	  flag = TRUE;
	  break;
	case 1 : 
	  hms_turn(hms, HMS_LEFT);
	  break;
	case 2 :
	  hms_turn(hms, HMS_LEFT);
	  hms_turn(hms, HMS_LEFT); 
	  break;
	case 3 : hms_turn(hms, HMS_RIGHT);
	  break;
	case -1: flag = TRUE;
	}
    }
  while (flag == FALSE);
}


/*---------------------------------------------------------------------------*/
void go(HAMSTER *hms, mapnode *map, mapnode from, mapnode to)
{
  if (from -> dist[1] != 0)
    go (hms, map, from -> prev[1], from);

  make_move(hms, map, from, to);
}


/*---------------------------------------------------------------------------*/
void go_back(HAMSTER *hms, mapnode *map)
{
  while ((*map) -> dist[0] != 0)
    make_move(hms, map, *map, (*map) -> prev[0]);
}


/*---------------------------------------------------------------------------*/
mapnode insert(mapnode current, coordinate pos)
{
  mapnode temp;
  
  temp = (mapnode) malloc(sizeof(MAPNODE));

  temp -> pos = pos;

  temp -> next = current -> next;
  current -> next = temp;

  return temp;
}


/*---------------------------------------------------------------------------*/
void discover(HAMSTER *hms, mapnode current)
{
  int i;
  coordinate pos;
  mapnode temp;

  if ( (current -> corn == -3) ||
       (current -> corn >= 0) )
    return;

  current -> corn = hms_corn(hms);

  for (i = 0; i <= 3; i++)
    {
      if (hms_look(hms) == HMS_WALL)
	current -> nb[hms_dir(hms)] = WALL;
      else
	{
	  hms_pos(hms, &(pos.x), &(pos.y));
          get_coordinate(&pos, hms_dir(hms));
	  
	  temp = is_known(current, pos);

	  if (temp == NULL)
	    {
	      temp = insert(current, pos);

	      if (hms_look(hms) == HMS_CORN) 
		temp -> corn = -2;
	      else 
		temp -> corn = -1;
	    }

	  current -> nb[hms_dir(hms)] = temp;

	}
      hms_turn(hms, HMS_LEFT);
    }
  shortest_ways(current, 0);
}


/*---------------------------------------------------------------------------*/
void hms_ctrl(HAMSTER *hms)
{
  mapnode map;
  mapnode g[3];
  int dist[3];
  bool flag = FALSE;


  map = (mapnode) malloc(sizeof(MAPNODE));
  map -> pos.x = 0;
  map -> pos.y = 0;
  map -> next = map;
  map -> prev[0] = map;
  map -> dist[0] = 0;
  map -> corn = -2;
  discover(hms, map);
  map -> corn = -3;

  do
    {
      discover(hms, map);

      shortest_ways(map, 1);
      
      g[0] = way_to_corn(map, dist + 0);
      g[1] = way_to_field(map, -2, dist + 1);
      g[2] = way_to_field(map, -1, dist + 2);

      if ( (g[0] != NULL) &&
	   (dist[0] <= dist[1]) &&
	   (dist[0] <= dist[2]) &&
           ((2 * g[0]->dist[0]) < 2550) )
	{
	  go(hms, &map, g[0] -> prev[1], g[0]);
	  map -> corn -= hms_take(hms, HMS_MAXLOAD);
	}
      else

      if ( (g[1] != NULL) &&
	   (dist[1] <= dist[2]) &&
           ((2 * g[1]->dist[0]) < 2550) )
	go(hms, &map, g[1] -> prev[1], g[1]);
      else

      if ( (g[2] != NULL) &&
           ((2 * g[2]->dist[0]) < 2550) )
	go(hms, &map, g[2] -> prev[1], g[2]);
      else
	flag = TRUE;  

      if (hms_load(hms) == HMS_MAXLOAD)
	{
	  go_back(hms, &map);
	  hms_drop(hms, HMS_MAXLOAD);
	}
    }
  while (flag == FALSE);

  if (hms_load(hms) > 0)
    {
      go_back(hms, &map);
      hms_drop(hms, HMS_MAXLOAD);
    }

}