// Jedes Programm sollte zu Beginn einen Kommentarblock enthalten,
// in dem angegeben wird, wie das Programm heißt, wer es wann geschrieben hat
// ggf. letzte Änderungen / Änderungshistorie, was das Programm tut, und welche
// Ideen dahinter stecken ... dazu bieten sich die C-Kommentare an, die
// die auskommentierten Zeilen in /* und */ einschließen
/*****************************************************************************
 * Lösen von Umfüllproblemen
 * Autor: TEL11Gr1
 * Datum: WS 11/12
 *
 * Aufgabe: Ziel ist aus einer Eingabe von 3 Gefäßgrößen (z.B. 8, 5 und 3 Einheiten)
 * und einer Startkonfiguration/füllung (z.B. (8,0,0)) und einer Zielsetzung
 * (z.B. (4,4,0)) einen Weg zu finden, durch reines Umfüllen (ggf. Wegleeren) von Gefäßinhalten
 * die Zielkonfiguration zu erreichen und auszugeben. Nebenziel: das Ganze mit
 * möglichst wenig Umfüllvorgängen.
 * 
 * Vorgehen: Bestimme aus der Startkonfiguration iterativ alle möglichen Folgekonfigurationen
 * bis entweder das Ziel gefunden wurde oder keine weiteren Konfigurationen mehr erreichbar sind.
 *
 * Hilfreich, um eine Programmstruktur festzulegen sind entweder Diagramme wie in der VL
 * oder Pseudocode (eher als Gedankenstütze), hier als Bsp. in Pseudocode:
 *
 * Kapazitäten/Start/Ziel eingeben
 * Menge von Konfigurationen initialisieren
 * solange noch nicht alle Konfigurationen auf mögliche Folgekonfigurationen untersucht wurden
 *   wähle eine solche aus
 *   und füge die möglichen Folgekonfigurationen zu einer Menge der Konfigurationen hinzu
 * bis keine solchen Konfigurationen mehr vorliegen oder das Ziel gefunden wurde
 * Lösungsweg ausgeben
 *
 * Fortsetzung der Ideenführung: zum Ausgeben des Lösungswegs müssen wir rückwärts
 * den Baum der möglichen Konfigurationen wieder aufsteigen können. Dazu merken wir
 * uns in jeder Konfiguration, von welcher Konfiguration diese erreicht wurde.
 *
 * Um den Aufwand beim Call-by-Value bei zusammengesetzten Datentypen
 * zu vermeiden, können diese auch besser als Referenz übergeben werden.
 * Man sollte aber darauf achten, bei nur lesendem Zugriff das vorangestellte
 * const nicht zu vergessen!
 *
 ****************************************************************************/

/*
/*
auszukommentieren
*/ // Kommentar ist bereits hier zu Ende ...
//*/ (nur zur Sicherheit auskommentiert)
#include<iostream>
using namespace std;

//typedef int Datentyp[3]; // Datentyp ist für den Compiler von nun an ein Typ für ein
// Array aus 3 int-Werten
// aufgrund der Problematik Array als Parameter (s.u.) verstecken wir das Array in einem struct
struct Datentyp
{
	int arr[3];
};
// Datentyp ist nun ein Typ (ein Kästchen), der ein Array mit 3 int-Werten enthält

bool operator ==(const Datentyp & a, const Datentyp & b)
{
	return ((a.arr[0] == b.arr[0]) && (a.arr[1] == b.arr[1]) && (a.arr[2] == b.arr[2]));
	// wertet sich genau dann zu wahr aus, wenn jede der drei Elemente jeweils gleich sind
}

// Ausgabe für selbstdefinierte Datentypen ... (nehmen Sie das einfach als Kochrezept)
ostream& operator << (ostream& os, const Datentyp & a)
// wir werden hier für den Parameter os das cout benutzen
{
	os << '(' << a.arr[0] << ',' << a.arr[1] << ',' << a.arr[2] << ')';
	return os; // muss hier noch über return zurückgegeben werden, damit
	// im Anschluss noch andere Werte mit << ... folgen können
}

// analog Eingabe für selbstdefinierte Datentypen
istream& operator >> (istream& is, Datentyp & a)
// wir werden hier für den Parameter is das cin benutzen
{
	is >> a.arr[0] >> a.arr[1] >> a.arr[2];
	return is; // muss hier noch über return zurückgegeben werden, damit
	// im Anschluss noch andere Werte mit >> ... folgen können
}


struct Mengentyp
{
	Datentyp content[100];
	int vorgaenger[100]; // zum Merken: content[x] wurde über die Konfiguration vorgaenger[x] hinzugefügt
	int nrOfValues;
};

// Auftretenes Problem: wird ein Array als Parameter übergeben, dann übergibt C/C++
// nur einen Verweis auf den entsprechenden Speicherbereich. Dies führt ggf. zu
// Problemen bei der Deklaration der Variablen/Parameter (Stichwort const)

// Abhilfe bei Arrays: man verstecke das Array in einem struct (wie oben)

void addToSet(const Datentyp & value, Mengentyp & set)
// es wird davon ausgegangen, dass value noch nicht in set vorhanden ist
{
	set.content[set.nrOfValues]=value;
	set.nrOfValues++; // erhöht den Wert der Variablen nrOfValues um 1
	// Problematik, dass das set nur 100 Werte umfassen darf, wird hier zunächst ausgeblendet
}

bool isInSet(const Datentyp & value, const Mengentyp & set) // testet, ob Wert value in der Menge set ist
{
	int index = 0;
	for ( ; index < set.nrOfValues; index = index+1)
	{
		if (value == set.content[index]) // der Vergleich von zwei selbst definierten
			// Datentypen ist C/C++ nicht bekannt (kann es auch nicht sein)
			// wir müssen dem Compiler mitteilen, was wir hier unter == verstehen wollen (s.o.)
		{
			return true;
		}
	}
	return false;
}

void printSet(const Mengentyp & set) // gibt die Werte der Menge set aus
{
	if (set.nrOfValues == 0)
	{
		cout << "Die Menge ist leer" << endl;
	}
	else
	{
		cout << "Die Menge umfasst die Werte " << set.content[0];
		int index;
		for (index=1; index < set.nrOfValues; index = index+1)
		{
			cout << ", " << set.content[index];
		}
		cout << endl;
	}
}

// Hilfsfunktionen zur Erstellung der Folgekonfigurationen

// Variante 1:
// Datentyp fuellAinBum(const Datentyp konfig, const Datentyp kapaz, const int gef1, const int gef2)
// Ablauf wäre dann: folgeKonf = fuellAinBum(ausgangsKonf,kapaz,0,2); // 0 und 2 nur als Beispiel

// Variante 2:
// void fuellAinBum(const int gef1, const int gef2, const int kap2, int & zgef1, int & zgef2)
// Ablauf wäre dann: fuellAinBum(ausK[0],ausK[2],kapaz[2],zielK[0],zielK[2]);

// Variante 3:
void fuellAinBum(int & gef1, int & gef2, const int kap2)
// Idee: erst Kopie erstellen und dann die Kopie verändern
// Ablauf wäre dann: zielK = ausK; fuellAinBum(zielK[0],zielK[2],kapaz[2]);
{
	if (gef1+gef2 <= kap2) // passt der Inhalt beider Gefäße in das zweite hinein?
	{
		gef2 = gef1 + gef2;
		gef1 = 0;
	}
	else // sonst wird das zweite Gefäß komplett gefüllt
	{
		gef1 = gef1 - (kap2 - gef2);
		gef2 = kap2;
	}
}

//void findeFolgeKonfVonA(const Datentyp ausK, const Datentyp kapaz, Mengentyp & set)
void findeFolgeKonfVonA(const int idxAusK, const Datentyp & kapaz, Mengentyp & set)
// da wir zum Finden des Lösungswegs an dieser Stelle auch wissen sollten, an
// welchem Index das Element ausK steht, wird hier der Index übergeben
// Die Ausgangskonfiguration kann dann über set.content[idxAusK] ermittelt werden
{
	Datentyp ausK = set.content[idxAusK];
    Datentyp zielK;
	zielK = ausK; fuellAinBum(zielK.arr[0], zielK.arr[1], kapaz.arr[1]);
	if (!isInSet(zielK, set))
	{
		set.vorgaenger[set.nrOfValues] = idxAusK; // erst den Vorgaenger setzen,
		// damit die set.nrOfValues noch den richtigen Wert hat
		addToSet(zielK, set);
	}
	zielK = ausK; fuellAinBum(zielK.arr[0], zielK.arr[2], kapaz.arr[2]);
	if (!isInSet(zielK, set))
	{
		set.vorgaenger[set.nrOfValues] = idxAusK;
		addToSet(zielK, set);
	}
	zielK = ausK; fuellAinBum(zielK.arr[1], zielK.arr[0], kapaz.arr[0]);
	if (!isInSet(zielK, set))
	{
		set.vorgaenger[set.nrOfValues] = idxAusK;
		addToSet(zielK, set);
	}
	zielK = ausK; fuellAinBum(zielK.arr[1], zielK.arr[2], kapaz.arr[2]);
	if (!isInSet(zielK, set))
	{
		set.vorgaenger[set.nrOfValues] = idxAusK;
		addToSet(zielK, set);
	}
	zielK = ausK; fuellAinBum(zielK.arr[2], zielK.arr[0], kapaz.arr[0]);
	if (!isInSet(zielK, set))
	{
		set.vorgaenger[set.nrOfValues] = idxAusK;
		addToSet(zielK, set);
	}
	zielK = ausK; fuellAinBum(zielK.arr[2], zielK.arr[1], kapaz.arr[1]);
	if (!isInSet(zielK, set))
	{
		set.vorgaenger[set.nrOfValues] = idxAusK;
		addToSet(zielK, set);
	}
	// Selbst überlegen, ob die Aufzählung der 6 Fälle so sinnvoll ist, oder ob man
	// besser mit for-Schleifen die Fälle aufzählt (und damit die if (!isInSet(.,.))
	// Abfrage nur einmal programmiert)

	// hier noch 3 Fälle, bei denen der Inhalt weggekippt wird -> selbst programmieren
}

int main(void)
{
	// wird nicht mehr gebraucht: Datentyp value; // einzulesener Wert
	Mengentyp set; // Menge mit maximal 100 Werte vom Typ Datentyp
	set.nrOfValues = 0; // zur Sicherheit, damit Funktionen wie printSet ein
	// definiertes Verhalten zeigen
	Datentyp kapaz; // Kapazitäten der drei Gefäße
	Datentyp start; // Startkonfiguration
	Datentyp ziel; // Zielkonfiguration

	int aktIdx; // Index, mit dem die aktuelle Konfiguration angesprochen wird

	// Kapaz./Start/Ziel einlesen
	cout << "Gib ein 3er-Tupel für die Kapazitaeten ein: ";
	cin >> kapaz; // wir benutzen jetzt unseren eigenen >>-Operator
	// vorher: cin >> kapaz.arr[0] >> kapaz.arr[1] >> kapaz.arr[2];

	cout << "Gib ein 3er-Tupel für die Startkonfiguration ein: ";
	cin >> start;

	cout << "Gib ein 3er-Tupel für die Zielkonfiguration ein: ";
	cin >> ziel;

	// Mengenverwaltung initialisieren
    set.content[0] = start;
	set.nrOfValues = 1;

	// was noch fehlt: gegenüber dem eigentlich Ansatz nochmal etwas vereinfacht:
	/* wiederhole
     *   wähle eine Konfigurationen aus, die noch nicht auf mögliche Folgekonfigurationen untersucht wurde
     *   und füge die möglichen Folgekonfigurationen zu einer Menge der Konfigurationen hinzu
     * bis keine solchen Konfigurationen mehr vorliegen
	 * teste, ob das Ziel gefunden wurde
     * Lösungsweg ausgeben
	 */

	aktIdx = 0;
	do // wir müssen in die Schleife in jeden Fall mind. 1 mal rein
	{
		findeFolgeKonfVonA(aktIdx, kapaz, set); // ohne Lösungsweg war der erste Parameter set.content[aktIdx]
		aktIdx++; // hochsetzen für den nächsten Durchlauf
	} while (aktIdx < set.nrOfValues); // solange noch Konfigurationen nicht betrachtet wurden
    printSet(set);
    if (isInSet(ziel,set))
	{
		cout << "Juchhu!" << endl;
		// aktIdx = ... // finde den Index der Zielkonfiguration in set
		// vermutlich ist das Ziel relativ weit hinten in der Menge set
		aktIdx = set.nrOfValues-1;
		while (!(ziel == set.content[aktIdx]))
		{
			aktIdx--; // ein angehängtes -- zieht eins von der Variable ab
		}
		// jetzt steht an set.content[aktIdx] unsere Zielkonfiguration
		while (aktIdx > 0)
		{
			cout << "Der Vorgänger von " << set.content[aktIdx]
				 << " ist " << set.content[set.vorgaenger[aktIdx]] << endl;
			aktIdx = set.vorgaenger[aktIdx];
		}
	}
	else
	{
		cout << "Das war nix!" << endl;
	}
	return 0;
}