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();
	public int arity; // Stelligkeit des Knotens aha!
	public 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.
		 */
		this.arity = tree.arity;
		this.type = tree.type;
		this.height = tree.height;
		this.nodeCount = tree.nodeCount;
		if (left != null) {
			left = copyTree(left);
			left.up = this;
		}
		if (right != null) {
			right = copyTree(right);
			right.up = this;
		}
	}

	/**
	 * 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
		if (maxH > 0) {
			parent = makeRandomSubtree(maxH, mode);// TODO 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!
	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

	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:
			return ((left == null) && (right == null) && (height == 0) && (nodeCount == 1));
		case 1:
			return ((left != null) && (right == null)
					&& (height == (left.height + 1))
					&& (nodeCount == (left.nodeCount + 1)) && left.isValid() && (left.up == this));
		case 2:
			return ((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));
		}
		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.
		 */
		GPTree os = findSubtree(ran.nextInt(nodeCount) + 1);
		GPTree ts = findSubtree(ran.nextInt(nodeCount) + 1);
		if (os.up.left.equals(os)) {
			os.up.left = ts;
		} else {
			os.up.right = ts;
		}
		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;
	}

	/**
	 * @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) {
			int index = ran.nextInt(nodeCount) + 1;// arraybaum index statet mit
													// 1
			GPTree sub = findSubtree(index);
			GPTree ne = makeRandomSubtree(h, mode);
			ne.up = sub.up;
			if (sub.up.left.equals(sub)) {
				ne.up.left = ne;
			} else {
				ne.up.right = ne;
			}
			sub.up = null;

		}
	}

	/**
	 * @param index
	 *            starts at 1
	 * @return the GPTree at this index
	 */
	private GPTree findSubtree(int index) {
		int cIndex = index;
		List<Integer> path = new ArrayList<Integer>(); // geht sicher
														// besser hab
														// ich mir
														// gerade selbst
														// so gedacht
		path.add(0, cIndex);
		while (cIndex < 2) {
			cIndex = cIndex / 2;
			path.add(0, cIndex);
		}
		GPTree aimNode = this;
		for (int i : path) {
			if ((i % 2) == 0) {
				aimNode = aimNode.left;
			} else {
				aimNode = aimNode.right;
			}
		}
		return aimNode;
	}
}