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

#include <pthread.h>

#include "springer.h"

int main(int argc, char *argv[])
{
	if(argc < 3)
	{
		fprintf(stderr, "Usage: %s <Höhe> <Breite> [<Threads>]", argv[0]);
		exit(1);
	}
	if(argc == 3)
	{
		struct springer_zustand *zustand = initialisiere_zustand((unsigned int)atoi(argv[1]), (unsigned long)atoi(argv[2]));
		sprung(zustand, 1, 0, 0);
	}
	else if(argc == 4)
	{
		//TODO: Implement multithreading
	}
	else
	{
		fprintf(stderr, "Usage: %s <Höhe> <Breite> <Threads>", argv[0]);
		exit(1);
	}

	return 0;
}

struct springer_ausgabe *kopiere_ausgabe(struct springer_ausgabe *ausgabe)
{
	struct springer_ausgabe *neue_ausgabe = malloc(sizeof(struct springer_ausgabe));
	neue_ausgabe->numlen = ausgabe->numlen; neue_ausgabe->zeilenlaenge = ausgabe->zeilenlaenge;
	neue_ausgabe->formatstring = ausgabe->formatstring;
	neue_ausgabe->feld = malloc(strlen(ausgabe->feld) + 1);
	return neue_ausgabe;
}

struct springer_zustand *kopiere_zustand(struct springer_zustand *zustand)
{
	struct springer_zustand *neuer_zustand = malloc(sizeof(struct springer_zustand));
	neuer_zustand->hoehe = zustand->hoehe; neuer_zustand->breite = zustand->breite;
	neuer_zustand->ausgabe = kopiere_ausgabe(zustand->ausgabe);
	neuer_zustand->feld = malloc(sizeof(unsigned long int) * zustand->hoehe * zustand->breite);
	memcpy(neuer_zustand->feld, zustand->feld, sizeof(unsigned long int) * zustand->hoehe * zustand->breite);
	return neuer_zustand;
}

struct springer_thread *initialisiere_thread(struct springer_zustand *zustand, unsigned long int nr, unsigned int x, unsigned int y)
{
	struct springer_thread *thread;
	thread->zustand = kopiere_zustand(zustand);
	thread->nr = nr;
	thread->x = x;
	thread->y = y;
	return thread;
}

struct springer_ausgabe *initialisiere_ausgabe(unsigned int breite, unsigned int hoehe)
{
	struct springer_ausgabe *ausgabe = malloc(sizeof(struct springer_ausgabe));
	if(ausgabe == NULL)
	{
		perror("Konnte den Speicher für die Augabe nicht allokieren.");
		exit(1);
	}

	//Länge der Ausgabe der größten möglichen Nummer.
	char tmpstr[100];
	sprintf(tmpstr, "%ld", (unsigned long int)hoehe * breite);
	ausgabe->numlen = strlen(tmpstr);

	ausgabe->zeilenlaenge = (ausgabe->numlen + 1) * breite + 2;

	ausgabe->feld = malloc(ausgabe->zeilenlaenge * (1 + hoehe * 2));
	if(ausgabe->feld == NULL)
	{
		perror("Konnte den Speicher für das Schachbrett der Ausgabe nicht allokieren.");
		exit(1);
	}

	sprintf(tmpstr, "%%%dld", ausgabe->numlen);
	//printf("%%%dld", zustand->ausgabe->numlen);
	ausgabe->formatstring = malloc(strlen(tmpstr) + 1);
	if(ausgabe->formatstring == NULL)
	{
		perror("Konnte den Speicher für den Formatstring der Ausgabe nicht allokieren.");
		exit(1);
	}
	memcpy(ausgabe->formatstring, &tmpstr, strlen(tmpstr) + 1);
	//printf("numlen: %d\nzeilenlaenge: %d\n", numlen, zustand->ausgabe->zeilenlaenge);

	char *runner = ausgabe->feld;
	unsigned int x, y, i;
	*runner++ = '+';
	for(x = 0; x < breite; x++)
	{
		for(i = 0; i < ausgabe->numlen; i++)
		{
			*runner++ = '-';
		}
		*runner++ = '+';
	}
	*runner++ = '\n';
	for(y = 0; y < hoehe; y++)
	{
		*runner++ = '|';
		for(x = 0; x < breite; x++)
		{
			for(i = 0; i < ausgabe->numlen; i++)
			{
				*runner++ = ' ';
			}
			*runner++ = '|';
		}
		*runner++ = '\n';
		*runner++ = '+';
		for(x = 0; x < breite; x++)
		{
			for(i = 0; i < ausgabe->numlen; i++)
			{
				*runner++ = '-';
			}
			*runner++ = '+';
		}
		*runner++ = '\n';
	}
	*runner = (char) 0;
	//printf("%s\n", zustand->ausgabe->feld);
	return ausgabe;
}

struct springer_zustand *initialisiere_zustand(unsigned int breite, unsigned int hoehe)
{
	struct springer_zustand *zustand = malloc(sizeof(struct springer_zustand));
	if(zustand == NULL)
	{
		perror("Zustand");
		exit(1);
	}

	zustand->hoehe = hoehe; zustand->breite = breite;

	zustand->feld = malloc(sizeof(unsigned long int) * hoehe * breite);
	if(zustand->feld == NULL)
	{
		perror("Schachbrett");
		exit(1);
	}

	zustand->ausgabe = initialisiere_ausgabe(breite, hoehe);

	return zustand;
}

void zerstoere_ausgabe(struct springer_ausgabe *ausgabe)
{
	free(ausgabe->feld);
	free(ausgabe);
}

void zerstoere_zustand(struct springer_zustand *zustand)
{
	zerstoere_ausgabe(zustand->ausgabe);
	free(zustand->feld);
	free(zustand);
}

void zerstoere_thread(struct springer_thread *thread)
{
	zerstoere_zustand(thread->zustand);
	free(thread);
}

void starte_thread(struct springer_zustand *zustand, unsigned long int nr, unsigned int x, unsigned int y)
{
	struct springer_thread *thread = initialisiere_thread(zustand, nr, x, y);
	//TODO: pthread starten!
}

void gestarteter_thread(struct springer_thread *thread)
{
	//TODO: Inkrementiere Anzahl der Threads.
	thread_sprung(thread->zustand, thread->nr, thread->x, thread->y);
	zerstoere_thread(thread);
	//TODO: Dekrementiere Anzahl der Threads.
}

void thread_sprung(struct springer_zustand *zustand, unsigned long int nr, unsigned int x, unsigned int y)
{
	if(x < 0 || x >= zustand->breite || y < 0 || y >= zustand->hoehe)
	{
		return;
	}

	if(zustand->feld[x + (y * zustand->breite)] > 0)
	{
		return;
	}

	zustand->feld[x + (y * zustand->breite)] = nr;

	if(nr == zustand->hoehe * zustand->breite)
	{
		ausgabe(zustand);
	}
	else
	{
		sprung(zustand, nr + 1, x + 2, y + 1);
		sprung(zustand, nr + 1, x + 2, y - 1);
		sprung(zustand, nr + 1, x + 1, y + 2);
		sprung(zustand, nr + 1, x + 1, y - 2);
		sprung(zustand, nr + 1, x - 2, y + 1);
		sprung(zustand, nr + 1, x - 2, y - 1);
		sprung(zustand, nr + 1, x - 1, y + 2);
		sprung(zustand, nr + 1, x - 1, y - 2);
	}

	zustand->feld[x + (y * zustand->breite)] = 0;
}

void sprung(struct springer_zustand *zustand, unsigned long int nr, unsigned int x, unsigned int y)
{
	if(x < 0 || x >= zustand->breite || y < 0 || y >= zustand->hoehe)
	{
		return;
	}

	if(zustand->feld[x + (y * zustand->breite)] > 0)
	{
		return;
	}

	zustand->feld[x + (y * zustand->breite)] = nr;

	if(nr == zustand->hoehe * zustand->breite)
	{
		ausgabe(zustand);
	}
	else
	{
		sprung(zustand, nr + 1, x + 2, y + 1);
		sprung(zustand, nr + 1, x + 2, y - 1);
		sprung(zustand, nr + 1, x + 1, y + 2);
		sprung(zustand, nr + 1, x + 1, y - 2);
		sprung(zustand, nr + 1, x - 2, y + 1);
		sprung(zustand, nr + 1, x - 2, y - 1);
		sprung(zustand, nr + 1, x - 1, y + 2);
		sprung(zustand, nr + 1, x - 1, y - 2);
	}

	zustand->feld[x + (y * zustand->breite)] = 0;
}

unsigned long int anzahl = 1;
void ausgabe(struct springer_zustand *zustand)
{
	unsigned int x, y;
	char tmpstr[100];
	for(y = 0; y < zustand->hoehe; y++)
	{
		for(x = 0; x < zustand->breite; x++)
		{
			sprintf(tmpstr, zustand->ausgabe->formatstring, zustand->feld[x + (y * zustand->breite)]);
			memcpy(zustand->ausgabe->feld + ((2 * y + 1) * zustand->ausgabe->zeilenlaenge) + ((1 + zustand->ausgabe->numlen) * x) + 1, &tmpstr, strlen(tmpstr));
		}
	}
	printf("\n+----------\n|%10ld\n%s\n", anzahl++, zustand->ausgabe->feld);
}