/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
/* turing.c - a Turing machine simulator.
 * Copyright (C) 1998 The Free Software Foundation
 * Copyright (C) 2001-2002 German Poo-Caaman~o
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>

#include <glib.h>
#include <bonobo/bonobo-i18n.h>
#include "turing.h"

#define BLANK           '_'
#define END_TAG         '\n'
#define COMMENT_TAG     '#'
#define TOKEN_SEPARATOR " "

#define LEFT  'l'
#define RIGHT 'r'

/* An utility for fread_states: exhausts any spaces found in fd. */
static void
read_spaces (FILE * fd)
{
	gint buff;

	while (((buff = fgetc (fd)) != EOF) && isspace (buff));

	ungetc (buff, fd);
}

static turing_tape *
new_cell (void)
{
	turing_tape *temp;

	temp = g_malloc (sizeof (turing_tape));
	temp->value = BLANK;
	temp->next = NULL;
	temp->prev = NULL;

	return temp;
}

static turing_state *
new_state (void)
{
	turing_state *temp;

	temp = g_malloc (sizeof (turing_state));

	temp->index = 0;
	temp->no = temp->read = temp->write = temp->move = temp->new = 0;
	temp->next = NULL;
	temp->comments[0] = '\0';

	return temp;
}

turing *
turing_new (void)
{
	turing *machine;

	machine = g_malloc (sizeof (turing));
	machine->state = 0;
	machine->pos = 0;
	machine->actualtape = machine->tapehead = NULL;
	machine->actualstate = machine->statehead = NULL;

	return machine;
}

static void
turing_free_tape (turing * machine)
{
	turing_tape *temp, *next;

	for (temp = machine->tapehead; temp; temp = next) {
		next = temp->next;
		g_free (temp);
	}

	machine->tapehead = NULL;
}

/* Gets the tape from tape_string. */
void
turing_set_tape (turing * machine, gchar * ptr)
{
	turing_tape *temp, *last;
	gchar buff;

	turing_free_tape (machine);

	last = machine->tapehead = NULL;

	while ((buff = *(ptr++)) != 0) {
		temp = new_cell ();
		temp->value = (buff == ' ') ? BLANK : buff;

		if (last) {
			last->next = temp;
			temp->prev = last;
			last = temp;
		} else
			last = machine->tapehead = temp;
	}
	machine->actualtape = machine->tapehead;
}

gchar *
turing_get_tape (turing * machine)
{
	gchar *buff, *tmpbuff;
	turing_tape *temp;
	gint i;

	i = 1;
	for (temp = machine->tapehead; temp; temp = temp->next)
		i++;

	tmpbuff = buff = g_malloc (sizeof (gchar) * i);

	for (temp = machine->tapehead; temp; temp = temp->next, tmpbuff++)
		*tmpbuff = (temp->value == BLANK) ? ' ' : temp->value;

	*tmpbuff = 0;

	return buff;
}

/* Reads states from file. Supports #comments, empty lines and misc info
 * after the state declaration in the same line. fscanf sucks: discovered the
 * blessings of strtok (thanks to Federico Mena). */
gint
turing_fread_states (turing * machine, gchar * filename)
{
	FILE *fd;
	turing_state *temp, *prev;
	gchar line[1000];
	gchar **tokens /*, **comments */;
	gint count = 0;

	machine->statehead = temp = prev = NULL;

	if ((fd = fopen (filename, "r")) == NULL)
		return -1;

	do {
		read_spaces (fd);

		if (fgets (line, 1000, fd) == NULL)
			break;

		if ((*line == COMMENT_TAG) || (*line == END_TAG))
			continue;

		tokens = g_strsplit (line, TOKEN_SEPARATOR, 6);

		/* We haven't enough columns (data) to build the machine */
		if (tokens[4] == NULL) {
			g_printerr ("gturing: %s\n",
				    N_("Wrong states file format."));
			g_strfreev (tokens);
			return -1;
		}

		if (temp == NULL)
			temp = new_state ();

		/* The line has comments and we clean of garbage */
		if (tokens[5] != NULL) {
			/*comments = g_strsplit (tokens[5], "\n", -1);
			g_stpcpy (temp->comments, comments[0]);
			g_strfreev (comments);*/
			g_stpcpy (temp->comments, g_strchomp (tokens[5]));
		}
		temp->index = ++count;
		temp->no = atoi (tokens[0]);
		temp->read = tokens[1][0];
		temp->write = tokens[2][0];
		temp->move = tokens[3][0];
		temp->new = atoi (tokens[4]);
		g_strfreev (tokens);

		temp->next = machine->statehead;
		machine->statehead = temp;
		temp = NULL;

	} while (temp == NULL);

	/*if (temp != NULL)
	  free (temp); */
	g_free (temp);

	fclose (fd);

	/* The nodes was inserted on reverse order.  So, we reverse the list 
	 * to get the sorted list 
	 */
	temp = machine->statehead;
	while (temp) {
		turing_state *next = temp->next;

		temp->next = prev;
		prev = temp;
		temp = next;
	}
	machine->statehead = prev;

	if (machine->statehead) {
		machine->state = prev->no;
		machine->actualstate = prev;
	}
/*
	if (machine->statehead) {
			for (temp = machine->statehead; temp->next; temp = temp->next)
				;
			machine->state = temp->no;
			machine->actualstate = temp;
	}
*/
	return 0;
}

extern gint
turing_fwrite_states (turing_state * state, gchar * filename,
		      gchar * comment)
{
	FILE *fd;
	gchar *c, *c2, *comment2;
	turing_state *s;

	if ((fd = fopen (filename, "w")) == NULL)
		return -1;

	if (comment) {
		c2 = comment2 = strdup (comment);

		while ((c = strchr (c2, '\n'))) {
			*c = 0;
			fprintf (fd, "#%s\n", c2);
			c2 = c + 1;
		}

		if (*c2)
			fprintf (fd, "#%s\n", c2);

		g_free (comment2);
	}

	for (s = state; s; s = s->next) {
		gchar buff[1096];
		
		g_snprintf (buff, 1096, "%d %c %c %c %d %s", s->no, s->read,
			  s->write, s->move, s->new, s->comments);
		g_strchomp (buff);
		g_snprintf (buff, 1096, "%s\n", buff);
		fprintf (fd, buff);
		g_print ("%d: %s", s->index, buff);
	}
	
	fclose (fd);

	return 0;
}

gchar *
turing_fread_comments (gchar * filename)
{
	gint c;
	gint size;
	gchar line[1000];
	gchar *ret, *tmp;
	FILE *fd;

	if ((fd = fopen (filename, "r")) == NULL)
		return NULL;

	ret = g_malloc (1);
	*ret = 0;
	size = 1;

	while ((c = fgetc (fd)) != EOF) {

		fgets (line, 1000, fd);

		if (c == '#') {
			ret = realloc (ret, size + strlen (line));
			tmp = ret + size - 1;
			size += strlen (line);
			strcpy (tmp, line);
		}
	}

	return ret;
}

/* Search the next state to execute depending on what we are reading and the
 * state field of the turing *machine. */
static turing_state *
turing_search_state (turing * machine)
{
	turing_state *temp;

	for (temp = machine->actualstate; temp; temp = temp->next)
		if (temp->no == machine->state)
			return temp;

	return NULL;
}

/* Moves the tape. If we try to get out of the range of the list, we create a
 * new cell with a blank in it (giving the impression that it is infinite. */
static void
turing_move_tape (turing * machine)
{
	if (tolower (machine->actualstate->move == LEFT))
		(machine->pos > 0) ? machine->pos-- : 0;
	else
		machine->pos++;

	if (tolower (machine->actualstate->move == LEFT)) {
		if (machine->actualtape->prev == NULL) {
			machine->pos = 0;
			machine->actualtape->prev = new_cell ();
			machine->actualtape->prev->next =
			    machine->actualtape;
			machine->tapehead = machine->actualtape->prev;
		}
		machine->actualtape = machine->actualtape->prev;
	} else {
		if (machine->actualtape->next == NULL) {
			machine->actualtape->next = new_cell ();
			machine->actualtape->next->prev =
			    machine->actualtape;
		}
		machine->actualtape = machine->actualtape->next;
	}
}

/* Runs the next state to execute. */
int
turing_run_state (turing * machine)
{
	machine->actualstate = machine->statehead;

	while (machine->actualstate &&
	       ((machine->actualstate->no != machine->state) ||
		(machine->actualstate->read !=
		 machine->actualtape->value))) {
		machine->actualstate = machine->actualstate->next;
		machine->actualstate = turing_search_state (machine);
	}

	if (machine->actualstate) {
		machine->actualtape->value = machine->actualstate->write;
		turing_move_tape (machine);
		machine->state = machine->actualstate->new;
		return 1;
	}

	return 0;
}

/* add or modify a state to the list.
 * Returns the position where the state was added/modified. 
 * flag is true if an insertion was made. */
extern void
turing_set_state (turing * machine, turing_state state)
{
	turing_state *temp, *node, *last;

	node = last = NULL;
	for (temp = machine->statehead; temp;
	     last = temp, temp = temp->next)
/*		if (temp->no == state.no) {
			if (!node)
				node = last;
*/
		if (temp->index == state.index) {
			if (!node)
				node = last;
			/*if (temp->read == state.read) {*/
				temp->read = state.read;
				temp->write = state.write;
				temp->move = state.move;
				temp->new = state.new;
				strncpy (temp->comments, state.comments,
					 1024);
				break;
			/*}*/
		}

	if (!temp) {		/* Values were not substituted: insert new state. */
		temp = g_malloc (sizeof (turing_state));

		*temp = state;
		if (!node) {	/* A completly new state number. Add at the bottom. */
			temp->next = machine->statehead;
			machine->statehead = temp;
			return;
		}

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

	return;
}