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

//#include "springer.h" START
struct springer_ausgabe
{
	int zeilenlaenge, numlen;
	char *feld, *formatstring;
};

struct springer_zustand
{
	int hoehe, breite;
	long *feld;
	struct springer_ausgabe *ausgabe;
};

void ausgabe(struct springer_zustand *zustand);
struct springer_zustand *initialisiere(int breite, int hoehe);
void sprung(struct springer_zustand *zustand, int nr, int x, int y);
//#include "springer.h" ENDE

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(atoi(argv[1]), 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_zustand *initialisiere(int breite, int hoehe)
{
	struct springer_zustand *zustand = malloc(sizeof(struct springer_zustand));
	if(zustand == NULL)
	{
		perror("Konnte den Speicher für den Zustand nicht allokieren.");
		exit(1);
	}

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

	zustand->feld = malloc(sizeof(long) * hoehe * breite);
	if(zustand->feld == NULL)
	{
		perror("Konnte den Speicher für das Schachbrett nicht allokieren.");
		exit(1);
	}


	zustand->ausgabe = malloc(sizeof(struct springer_ausgabe));
	if(zustand->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", (long int)hoehe * breite);
	zustand->ausgabe->numlen = strlen(tmpstr);

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

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

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

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

	return zustand;
}

void sprung(struct springer_zustand *zustand, int nr, int x, 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;
}

int anzahl = 1;
void ausgabe(struct springer_zustand *zustand)
{
	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|%10d\n%s\n", anzahl++, zustand->ausgabe->feld);
}