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

int moves = 0;
int lastx, lasty;
typedef struct position *POS;
typedef struct position
{
	POS next;
	int x;
	int y;
	int lock;
	int move;
}
POSELEM;

typedef struct listelem *LISTPTR;
typedef int DATATYPE;
typedef struct listelem
{
	LISTPTR next;
	LISTPTR prev;
	DATATYPE datum;
}
LISTELEM;

LISTPTR insert (LISTPTR list, DATATYPE dat)
{
	LISTPTR tmp;
	tmp = (LISTPTR)malloc(sizeof(LISTELEM));
	tmp->datum = dat;
	tmp->next = list->next;
	list->next = tmp;
	return list;
}

POS insertpos (POS list, int x, int y) /* insert in list */
{
	POS tmp;
	tmp = (POS)malloc(sizeof(POSELEM));
	tmp->x = x;
	tmp->y = y;
	tmp->lock = 0;
	tmp->next = list->next;
	list->next = tmp;
	return list;
}

void delete_path (LISTPTR path)
{
	LISTPTR tmp;
	while(path != NULL)
	{
		tmp = path;
		path = path->next;
		free(tmp);
	}
}

POS delete_feldelem (POS feld, int x, int y)
{
	POS tmp;
	while(feld != NULL && (feld->next->x != x || feld->next->y != y))
	{
		feld = feld->next;
		if(feld->lock == -1) return feld;
		if(feld->next == NULL) return feld;
	}
	tmp = feld->next;
	feld->next = feld->next->next;
	free(tmp);
	return feld;
}

void go_home(HAMSTER *hms, LISTPTR path, POS feld)
{
	int dir, x, y;
	hms_turn(hms, HMS_LEFT);
	hms_turn(hms, HMS_LEFT);
	while(path != NULL)
	{
		if(path->datum == 0) dir = 2;
		if(path->datum == 1) dir = 3;
		if(path->datum == 2) dir = 0;
		if(path->datum == 3) dir = 1;
		while(dir != hms_dir(hms))
		hms_turn(hms, HMS_LEFT);
		hms_pos(hms, &x, &y);
		hms_move(hms);
		path = path->next;
	}
	hms_drop(hms, HMS_MAXLOAD);
}

POS search_pos(POS feld, int x, int y)
{
	while(feld != NULL && (feld->x != x || feld->y != y))
	feld = feld->next;
	return feld;
}

POS search_last(POS feld, int x, int y)
{
	while(feld != NULL && (feld->x != x || feld->y != y))
	feld = feld->next;
	if(feld == NULL) return feld;
	if(feld->move >= moves - 20) return feld;
	return NULL;
}




void getnext(HAMSTER *hms, int *nx, int *ny)
{
	switch (hms_dir(hms))
	{
		case HMS_EAST:
		{
			hms_pos(hms, nx, ny);
			*nx = *nx + 1;
			break;
		}
		case HMS_NORTH:
		{
			hms_pos(hms, nx, ny);
			*ny = *ny + 1;
			break;
		}
		case HMS_WEST:
		{
			hms_pos(hms, nx, ny);
			*nx = *nx - 1;
			break;
		}
		case HMS_SOUTH:
		{
			hms_pos(hms, nx, ny);
			*ny = *ny - 1;
			break;
		}
	}
}

void add_to_feld (HAMSTER *hms, POS feld)
{
	int x, y;
	POS feldbegin;
	feldbegin = feld;
	hms_pos(hms, &x, &y);
	feld = search_pos(feld->next, x, y);
	if(feld == NULL)
	{
		feld = feldbegin;
		feld = insertpos(feld, x, y);
	}
	feld->move = moves;
}

void check_way(HAMSTER *hms, POS feld)
{
	int nx1, ny1, nx2, ny2, nx3, ny3, c1 = 0, c2 = 0, c3 = 0;
	int x, y;
	int random, exits = 0;
	POS feldbegin;
	feldbegin = feld;

	getnext(hms, &nx1, &ny1);
	if(hms_look(hms) == HMS_CORN) c1 = 1;
	if(hms_look(hms) == HMS_WALL) c1 = -1;

	hms_turn(hms, HMS_NEG);
	getnext(hms, &nx2, &ny2);
	if(hms_look(hms) == HMS_CORN) c2 = 1;
	if(hms_look(hms) == HMS_WALL) c2 = -1;

	hms_turn(hms, HMS_POS);
	hms_turn(hms, HMS_POS);
	getnext(hms, &nx3, &ny3);
	if(hms_look(hms) == HMS_CORN) c3 = 1;
	if(hms_look(hms) == HMS_WALL) c3 = -1;

	hms_turn(hms, HMS_NEG);

	feld = search_pos(feld, nx1, ny1);
	if(feld != NULL && c1 != -1)
		if(feld->lock == -1) c1 = -2;

	feld = feldbegin;
	feld = search_pos(feld, nx2, ny2);
	if(feld != NULL && c2 != -1)
		if(feld->lock == -1) c2 = -2;

	feld = feldbegin;
	feld = search_pos(feld, nx3, ny3);
	if(feld != NULL && c3 != -1)
		if(feld->lock == -1) c3 = -2;

	feld = feldbegin;

	if(c1 != -1 && c1 != -2) exits++;
	if(c2 != -1 && c2 != -2) exits++;
	if(c3 != -1 && c3 != -2) exits++;

	feld = search_pos(feld, lastx, lasty);
	if(exits == 1 && feld != NULL && feld->lock == -1 && lastx != 0 && lasty != 0)
	{
		feld = feldbegin;
		hms_pos(hms, &x, &y);
		feld = search_pos(feld, x, y);
		if(feld == NULL) feld = insertpos(feld, x, y);
		feld->lock = -1;
	}

	feld = feldbegin;
	if(c1 == 1)
	{
		return;
	}
	if(c2 == 1)
	{
		hms_turn(hms, HMS_RIGHT);
		return;
	}
	if(c3 == 1)
	{
		hms_turn(hms, HMS_LEFT);
		return;
	}

	feld = feldbegin;
	if(c1 == 0 && NULL == search_pos(feld, nx1, ny1)) return;

	if(c2 == 0 && NULL == search_pos(feld, nx2, ny2))
	{
		hms_turn(hms, HMS_RIGHT);
		return;
	}
	if(c3 == 0 && NULL == search_pos(feld, nx3, ny3))
	{
		hms_turn(hms, HMS_LEFT);
		return;
	}

	feld = feldbegin;
	if(c1 == 0 && NULL == search_last(feld, nx1, ny1))
		return;

	feld = feldbegin;
	if(c2 == 0 && NULL == search_last(feld, nx2, ny2))
	{
		hms_turn(hms, HMS_RIGHT);
		return;
	}
	feld = feldbegin;
	if(c3 == 0 && NULL == search_last(feld, nx3, ny3))
	{
		hms_turn(hms, HMS_LEFT);
		return;
	}

	if(c1 == 0) return;

	random = rand() % 4;

	if((c2 == 0) && (random == 0 || random == 2))
	{
		hms_turn(hms, HMS_RIGHT);
		return;
	}
	if((c3 == 0) && (random == 1 || random == 3))
	{
		hms_turn(hms, HMS_LEFT);
		return;
	}

	if(c2 == 0)
	{
		hms_turn(hms, HMS_RIGHT);
		return;
	}
	if(c3 == 0)
	{
		hms_turn(hms, HMS_LEFT);
		return;
	}

	hms_turn(hms, HMS_RIGHT);
	hms_turn(hms, HMS_RIGHT);

	feld = feldbegin;

	hms_pos(hms, &x, &y);
	if(x == 0 && y == 0) return;

	feld = search_pos(feld, x, y);
	if(feld == NULL) feld = insertpos(feld, x, y);
	feld = search_pos(feld, x, y);
	feld->lock = -1;
}

void hms_ctrl (HAMSTER *hms)
{
	int c_move;
	LISTPTR path, begin;
	POS feld, feldbegin;
	c_move = 0;
	path = (LISTPTR)malloc(sizeof(LISTELEM));
 	feld = (POS)malloc(sizeof(POSELEM));

	/* Start Korrektur, Christian Borgelt, 15.06.1998 */
        /* Da ``malloc'' einen nicht initialisierten Speicherbereich */
        /* zur"uckliefert, mu\3 dieser initialisiert werden. Zwar ist */
        /* er auf vielen Systemen bei der ersten Speicheranforderung */
        /* mit 0 belegt, aber dies ist nicht sicher. Werden hier nicht */
        /* die Nachfolgerzeiger auf NULL gesetzt, kommt es bei einigen */
        /* Systemen, bei denen der Speicher Zufallswerte enth"alt */
        /* (z.B. Sun), beim ersten Zugriff "uber diese Zeiger zu einem */
        /* Programmabsturz. */
	path->next = NULL;
 	feld->next = NULL;
        /* Ende Korrektur,  Christian Borgelt, 15.06.1998 */

	feldbegin = feld;
	begin = path;
	for(;;)
	{
		path = begin->next;
		feld = feldbegin->next;
		check_way(hms, feld);
		path = begin;
		insert(path, hms_dir(hms));
		hms_pos(hms, &lastx, &lasty);
		hms_move(hms);
		moves++;
		c_move++;
		feld = feldbegin;
		add_to_feld(hms, feld);
		if (hms_corn(hms) != 0) c_move=0;
		if (c_move > 60) break;
		hms_take(hms, HMS_MAXLOAD);
		if(hms_load(hms) == HMS_MAXLOAD)
		{
			path=begin->next;
			feld = feldbegin;
			go_home(hms, path, feld);
			feld = feldbegin;
			delete_path(path);
			begin->next = NULL;
		}
	}
	path=begin->next;
	feld = feldbegin;
	go_home(hms, path, feld);
	feld = feldbegin;
}