package info3;
/**
 * 
 * Info 3 Blatt 3, Aufgabe 2
 * 
 * @author fieberfn, hatjeki
 *
 * <p>
 * Class that implements a binary search tree. Elements smaller than the one
 * looked at come to the left. If you insert an element already contained it
 * will come to the right. Implemented functions are contains and insert.
 * Contains and insert are implemented with variable parameter lists.
 * </p>
 */

public class BinarySearchTree<T extends Comparable<T>> {
	
	private BinaryTree<T> anchor;

	BinarySearchTree() {
	}
	
	public boolean isEmpty () {
		return anchor == null;
	}
	
	public void insert (T Item) {
		if (anchor == null) {
			anchor = new BinaryTree<T> (Item);
		} else {
			insert(Item, anchor);
		}
	}
	
	public boolean contains (T param) {
		return contains (param, anchor);
	}
	
	public boolean delete (T param) {
		return myDelete (param);
	}
	
	public boolean putInorder () {
		return putInorder(anchor);
	}

	public void insert (T... params) {
		for (T element : params) {
			insert (element);
		}
	}	
	
//	public boolean delTree () {
//		//anchor = null;
//		delTree(anchor);
//		return true;
//	}
	
/*	public java.util.LinkedList contains (T... params) {
		java.util.LinkedList<T> contained = new java.util.LinkedList<T>(); 
		for (T param : params) {
			if (contains (param)) {
				contained.add(param);
			}
		}
		return contained;
	}
*/
	
	public boolean[] contains (T... params) {
		boolean contained[] = new boolean[params.length];
		for (int i = 0; i < params.length; i++) {
			if (contains (params[i])) {
				contained[i] = true;
			}
		}
		return contained;
	}
	
	public boolean[] delete (T... params) {
		boolean deleted[] = new boolean[params.length];
		for (int i = 0; i < params.length; i++) {
			if (delete (params[i])) {
				deleted[i] = true;
			}
		}
		return deleted;
	}
		
	private void insert (T Item, BinaryTree<T> tree) {
		if (Item.compareTo(tree.Item) < 0) {
			if (tree.left == null) {
				tree.left = new BinaryTree<T>(Item);
			} else {
				insert (Item, tree.left);
			}
		} else {
			if (tree.right == null) {
				tree.right = new BinaryTree<T>(Item);
			} else {
				insert (Item, tree.right);
			}
		}
	}
	
	private boolean contains (T param, BinaryTree<T> tree) {
		if (tree != null) {
			if (tree.Item.equals(param)) {
				return true;
			} else if (param.compareTo(tree.Item) < 0) {
				return contains (param, tree.left);
			} else {
				return contains (param, tree.right);
			}
		}
		return false;
	}

	private boolean putInorder (BinaryTree<T> tree) {
		if (anchor != null) {
			if (tree != null) { 
				putInorder(tree.left);
				System.out.print(tree.Item+" ");
				putInorder(tree.right);
			}
			return true;
		} else {
			return false;
		}
	}

	private boolean myDelete (T elem) {
		BinaryTree<T> cursor = anchor;
		BinaryTree<T> parentNode = null;
		BinaryTree<T> successor = null;
		BinaryTree<T> tmpParent = null;
		boolean left  = false;
		
		// durchsuche Baum
		while ((cursor != null) && (!cursor.Item.equals (elem))){
			if (elem.compareTo(cursor.Item) > 0) {
				parentNode = cursor;
				cursor = cursor.right;
				left = false;
			} else {
				parentNode = cursor;
				cursor = cursor.left;
				left = true;
			}
		}
		
		// falls Element nicht im Baum, gebe false zurueck
		if (cursor == null) {
			return false;
		} else {
			// falls Knoten keine Kinder hat, loesche diesen
			if ((cursor.left == null) & (cursor.right == null)) {
				if (parentNode != null) {
					if (left) {
						parentNode.left = null;
					} else {
						parentNode.right = null;
					}
					cursor = null;
				} else {
					anchor = null;
				}
			} else {
				
				// falls nur ein rechter Kindknoten
				if (cursor.left == null) {
					// falls Knoten Wurzel ist
					if (parentNode == null) {
						// setze rechtes Kind als Wurzel
						anchor = cursor.right;	
					} else {
						// ansonsten ueberspringe zu loeschenden Knoten 
						if (left) {
							parentNode.left = cursor.right;
						} else {
							parentNode.right = cursor.right;
						}
					}
					cursor = null;
				} else {
					// falls nur ein linker Kindknoten
					if (cursor.right == null) {
						// falls Knoten Wurzel ist
						if (parentNode == null) {
							// setze linkes Kind als Wurzel
							anchor = cursor.left;	
						} else {
							// ansonsten ueberspringe zu loeschenden Knoten 
							if (left) {
								parentNode.left = cursor.left;
							} else {
								parentNode.right = cursor.left;
							}
						}
						cursor = null;
					} else {
						// falls Knoten zwei Kinder hat, suche Inordernachfolger
						successor = cursor.right;
						tmpParent = null;
						while (successor.left != null) {
							tmpParent = successor;
							successor = successor.left;
						}
						
						if (tmpParent != null) tmpParent.left = null;
						
						// setze Inordernachfolger an Stelle des zu loeschenden Knotens
						if (parentNode == null) {
							anchor = successor;
						} else {
							if (left) {
								parentNode.left = successor;
							} else {
								parentNode.right = successor;
							}
						}

						// haenge linken Teilbaum des zu loeschenden Knotens links
						// an Inordernachfolger
						successor.left = cursor.left;
						
						// haenge rechten Teilbaum des zu loeschenden Knotens rechts
						// an den Inordernachfolgerbaum
					    if (successor != cursor.right) {
					    	tmpParent = successor;
					    	while (tmpParent.right != null) tmpParent = tmpParent.right;
					    	tmpParent.right = cursor.right;
					    }
					    cursor = null;
					}
				}				
			}
			
		}
		
		return true;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		BinarySearchTree<Integer> Baum = new BinarySearchTree<Integer>();
		
		Baum.insert (5);
		Baum.insert (2);
		Baum.insert (3);
		Baum.insert (1);
		Baum.insert (7);
		Baum.insert (6);
		Baum.insert (10);
		Baum.insert (8);
		Baum.insert (9);
		Baum.putInorder ();
		
		System.out.println();
		
		Baum.myDelete (5);
		Baum.putInorder ();
	}
}