package gp;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * A Generic GP tree implementation.
 * 
 * @author mkron
 *
 */
public abstract class GPTree {
	public static int MODE_FULL = 0;
	public static int MODE_GROW = 1;

	public Random ran = new Random();
	// schonmal was von Javadoc für public Felder gehört?? Ihr könnt doch
	// Schnittstellen nicht unkommentiert lassen.
	public int arity; // Stelligkeit des Knotens aha!
	protected int type; // Knotentyp . Schon mal was von Enums gehört...
	public int height; // Hoehe des Baumes
	public int nodeCount; // Knotenanzahl in diesem Baum
	public GPTree up, left, right; // Zeiger auf Eltern- und Unterknoten

	/**
	 * Constructor with tree initialization.
	 * 
	 * @param rand
	 * @param parent
	 * @param h
	 *            maximum height of the tree
	 * @param mode
	 *            0 is "full", 1 is "grow"
	 */
	public GPTree(GPTree parent, int h, int mode) {
		initRandomTree(parent, h, mode);
		if (!this.isValid()) {
			System.err.println("Error, invalid initialization!");
		}
	}

	/**
	 * Copy constructor
	 * 
	 * @param tree
	 *            the other tree
	 */
	public GPTree(GPTree tree) {
		/*
		 * Dieser Konstruktor erzeugt mit Hilfe von copyTree() eine tiefe Kopie
		 * des Baumes tree.
		 */
		if (!tree.isValid()) {
			throw new RuntimeException("not valid tree to copy");
		}
		this.arity = tree.arity;
		this.type = tree.type;
		this.height = tree.height;
		this.nodeCount = tree.nodeCount;
		this.up = tree.up;
		if (tree.left != null) {
			left = copyTree(tree.left);
			left.up = this;
		}
		if (tree.right != null) {
			right = copyTree(tree.right);
			right.up = this;
		}
		if (!this.isValid()) {
			throw new RuntimeException("after copy no valid tree");
		}
	}

	/**
	 * Random tree initialization.
	 * 
	 * @param parent
	 * @param maxH
	 *            maximum height of the new tree
	 * @param mode
	 *            0 is "full", 1 is "grow"
	 */
	public void initRandomTree(GPTree parent, int maxH, int mode) {
		/*
		 * Erzeugen Sie mit Hilfe von makeRandomSubtree() einen zufaelligen
		 * Baum. Verwenden Sie nicht direkt rekursiv den Konstruktor von GPTree,
		 * da sonst abgeleitete Typen mit dem Typ GPTree vermischt werden kann.
		 */
		// :-D :-D whooo das kommentar ist der hammer, da hat einer Vererbung
		// und Typen einfach nicht verstanden

		this.up = parent;
		makeRandomSubtree(maxH, mode);

	}

	private int getFunctionCount() {
		return getTermCount() + getUnaryCount() + getBinaryCount();
	}

	// ************* abstract methods
	// these two are abstract so that the subtypes can return the right type
	// they should again use GPTree's (copy) constructor!

	// na wie wärs den mit Javadoc ???
	public abstract GPTree makeRandomSubtree(int h, int mode);

	public abstract GPTree copyTree(GPTree tree);

	public abstract double evalTreeAt(Object o);

	public abstract int getTermCount(); // return number of terminals

	public abstract int getUnaryCount(); // return number of unary functions //
											// Toller Javadoc, so als
											// Kommentar...

	public abstract int getBinaryCount(); // return number of binary functions

	public abstract String getTermSymbol(int i); // return String for a terminal

	public abstract String getUnarySymbol(int i); // return String for a unary
													// function

	public abstract String getBinarySymbol(int i); // return String for a binary
													// function

	// ************* abstract methods end

	@Override
	public String toString() {
		/*
		 * Stellt den Baum durch eine Zeichenkette dar.
		 */
		switch (arity) {
		case 0:
			return getTermSymbol(type);
		case 1:
			return getUnarySymbol(type) + "(" + left.toString() + ")";
		case 2:
			return getBinarySymbol(type) + "(" + left.toString() + ","
					+ right.toString() + ")";
		}
		System.err.println("Invalid arity in GPTree!"); // Exceptions ? **
		return "";
	}

	// Hilfsfunktion zum Testen des Baumes auf Konsistenz
	private boolean isValid() {
		if (getFunctionCount() == 0) {
			return true; // assume correctness for an empty function set
		}
		switch (arity) {
		case 0:
			boolean a = ((left == null) && (right == null) && (height == 0) && (nodeCount == 1));
			if (!a) {
				System.out.println(a + "case 0");
				System.out.println(left);
				System.out.println(right);
				System.out.println(height);
				System.out.println(nodeCount);
				System.out.println("_________");
			}
			return a;
		case 1:
			boolean b = ((left != null)
					&& (right == null)
					&& (height == (left.height + 1))
					/* && (nodeCount == (left.nodeCount + 1)) */&& left
							.isValid() && (left.up == this));
			if (!b) {
				System.out.println(b + "case1");
				System.out.println("left" + left);
				System.out.println("right " + right);
				System.out
						.println("height " + height + " " + (left.height + 1));
				System.out.println("nodecount " + nodeCount + " "
						+ (left.nodeCount + 1));
				System.out.println("parent " + (left.up == this));
				System.out.println("_________");
			}
			return b;
		case 2:
			boolean c = ((left != null) && (right != null)
					&& (height == (Math.max(left.height, right.height) + 1))
					/* && (nodeCount == (left.nodeCount + right.nodeCount + 1)) */
					&& left.isValid() && right.isValid() && (left.up == this) && (right.up == this));
			if (!c) {
				System.out.println(c + "case2");
				System.out.println("left" + left);
				System.out.println("right " + right);
				System.out.println("height " + height + " "
						+ (Math.max(left.height, right.height) + 1));
				System.out.println("nodecount " + nodeCount + " "
						+ (left.nodeCount + right.nodeCount + 1));
				System.out.println("parent " + (left.up == this));
				System.out.println("_________");
			}
			return c;
		}
		return false;
	}

	/**
	 * Perform a GP crossover between two binary trees.
	 * 
	 * @param otherTree
	 *            the crossover partner
	 * @param h
	 *            the maximal height
	 */
	public void crossover(GPTree otherTree, int h) {
		/*
		 * Crossover zwischen den Baeumen this und tree wird ausgefuehrt.
		 * 
		 * Hinweis: wählen Sie zuerst zwei zufällige Teilbäume von this und
		 * otherTree. Dabei kann eine Vorstellung der Numerierung der
		 * Unterknoten helfen.
		 * 
		 * ist die maximale höhe der teilbäume gemeint? nichtmal gescheite
		 * javadoc gibts..
		 */

		if (!this.isValid()) {

			throw new RuntimeException("  this  not valid before crossover");
		}
		if (!otherTree.isValid()) {

			throw new RuntimeException("  othertree not valid before crossover");
		}

		List<GPTree> thisTrees = new ArrayList<GPTree>();
		List<GPTree> otherTrees = new ArrayList<GPTree>();
		getAllTreesSameOrLower(this, h, thisTrees);
		GPTree ts = null;
		GPTree os = null;
		if ((thisTrees.size() > 0)) {
			ts = thisTrees.get(ran.nextInt(thisTrees.size()));
		} else {
			return;
		}
		getAllTreesSameHight(otherTree, ts.height, otherTrees);
		if ((otherTrees.size() > 0)) {
			os = otherTrees.get(ran.nextInt(otherTrees.size()));
		} else {
			return;
		}
		if (os.up != null) {
			os.up.nodeCount -= os.nodeCount;
			os.up.nodeCount += ts.nodeCount;

			if (os.up.left.equals(os)) {
				os.up.left = ts;
			} else {
				os.up.right = ts;
			}
		}
		if (ts.up != null) {
			ts.up.nodeCount -= ts.nodeCount;
			ts.up.nodeCount += os.nodeCount; // todo notecount der eltern
												// anpassen --> das wird jetzt
												// echt zu viel code für die
												// paar punkte . Wir ignorieren
												// jetzt einfach den nodecount
												// bei der prüfung braucht man
												// eh nie
			if (ts.up.left.equals(ts)) {
				ts.up.left = os;
			} else {
				ts.up.right = os;
			}
		}
		GPTree op = os.up;
		os.up = ts.up;
		ts.up = op;
		if (!this.isValid()) {
			throw new RuntimeException("this is not valid after crossover");
		}
		if (!otherTree.isValid()) {
			throw new RuntimeException(
					"other tree is not valid after crossover");
		}

	}

	private void getAllTreesSameOrLower(GPTree start, int h, List<GPTree> result) {
		if (start.height >= 0) {
			if (start.height <= h) {
				result.add(start);
			}
			if (start.left != null) {
				getAllTreesSameOrLower(start.left, h, result);
			}
			if (start.right != null) {
				getAllTreesSameOrLower(start.right, h, result);
			}
		}
	};

	private void getAllTreesSameHight(GPTree start, int h, List<GPTree> result) {
		if (start.height >= h) {
			if (start.height == h) {
				result.add(start);
				return;
			}
			if (start.left != null) {
				getAllTreesSameHight(start.left, h, result);
			}
			if (start.right != null) {
				getAllTreesSameHight(start.right, h, result);
			}
		}
	};

	/**
	 * @param pMut
	 *            propability of mutation
	 * @param h
	 *            hight of the random subtree
	 * @param mode
	 *            0 is "full", 1 is "grow"
	 */
	public void mutate(double pMut, int h, int mode) {
		/*
		 * Der Baum wird mit einer Wahrscheinlichkeit von pMut mutiert und an
		 * einer zufaelligen Stelle durch einen zufaelligen Baum ersetzt.
		 */

		// Wie ist das zu verstehen? eine zufällige Stelle dieses Teilbaums?

		if (ran.nextDouble() <= pMut) {
			GPTree sub = null;
			GPTree ne = null;
			List<GPTree> treesOfSameHight = new ArrayList<GPTree>();
			getAllTreesSameHight(this, h, treesOfSameHight);
			if (treesOfSameHight.size() <= 0) {
				return;
			}
			sub = treesOfSameHight.get(ran.nextInt(treesOfSameHight.size()));
			ne = makeRandomSubtree(h, mode); // es wird immer nur ein Baum mit
												// wieder der gleichen höhe
												// erstellt wie der vorherige
			// Hier funktioniert unser code nicht da makeRandom subtree nur this
			// ändert und wir ja hier nicht auf subtypen casten können.
			// So und hier geben wir es auf die Aufgabe zu lösen, mit der
			// Hoffnung dass ihr uns nie wieder so schlecht kommentierten und so
			// häufig gegen Java-Spezifikationen verstoßenden Code gebt wie
			// diesen.

			ne.up = sub.up;
			if (ne.up != null) {
				sub.up.nodeCount -= sub.nodeCount;
				sub.up.nodeCount += ne.nodeCount;
				if (sub.up.left.equals(sub)) {
					sub.up.left = ne;
				} else {
					sub.up.right = ne;
				}
				sub.up = null;
			}

		}
		if (!this.isValid()) {
			System.err.println(this.toString() + "   not valid mutation");
			throw new RuntimeException("");
		}
	}

}