package lab1;

import lab1paket.CollectionWithGet;
import datastructures.*;
import lab1paket.*;

/**
 * 
 * @author Ola Ederborn
 * @author Tomas Vestelind
 *
 * @param <E>
 */
public class SplayTree<E extends Comparable<? super E>> extends BinarySearchTree<E>
             implements CollectionWithGet<E>{
	
	public SplayTree(){
		super();
	}
	
	public Entry find(E element, Entry t){
		if(t == null){			
			return t;
		}
		else if (element.compareTo( t.element ) == 0 ){
			splay(t);
			return t;
		}
	    else if (element.compareTo( t.element ) < 0 ){
	    	if(t.left == null){
	    		splay(t);
	    		return null;
	    	}
	    	else
	    		return find( element, t.left );
	    }
		else{
			if(t.right == null){
				splay(t);
				return null;
			}
			else
				return find( element, t.right );
		}
	}
	
	public void splay(Entry t){
		while(t != root)
			switch(findOutSplay(t)){
			case 1:
				zag(t);
				break;
			case 2:
				zig(t);
				break;
			case 3:
				zagzag(t);
				break;
			case 4:
				zigzag(t);
				break;
			case 5:
				zigzig(t);
				break;
			case 6:
				zagzig(t);
				break;
		}
	}
	
	private int findOutSplay(Entry t){
		if(t.parent.parent == null && t.parent.left == t)
			return 1;
		else if(t.parent.parent == null && t.parent.right == t)
			return 2;
		else if(t.parent.parent.left == t.parent && t.parent.left == t)
			return 3;
		else if(t.parent.parent.left == t.parent && t.parent.right == t)
			return 4;
		else if(t.parent.parent.right == t.parent && t.parent.right == t)
			return 5;
		else if(t.parent.parent.right == t.parent && t.parent.left == t)
			return 6;
		else
			return 0;
	}
	
	private void zig(Entry t){
		Entry x,y;
		x = t;
		y = t.parent;
		
		y.right = x.left;
		if(y.right != null)
			y.right.parent = y;
		
		x.left = y;
		y.parent = x;
		x.parent = null;
		
		root = x;
	}
	
	private void zag(Entry t){
		Entry x,y;
		x = t;
		y = t.parent;
		
		y.left = x.right;
		if(y.left != null)
			y.left.parent = y;
		
		x.right = y;
		y.parent = x;
		x.parent = null;
		
		root = x;
	}
	
	private void zigzig(Entry t){
		Entry x,y,z;
		x = t;
		y = t.parent;
		z = t.parent.parent;
		
		if(z.parent != null){
			if(z.parent.left == z)
				z.parent.left = x;
			else if(z.parent.right == z)
				z.parent.right = x;
		}
		else
			root = x;
		
		x.parent = z.parent;
		z.right = y.left;
		z.parent = y;
		if(z.right != null)
			z.right.parent = z;
		
		y.left = z;
		y.right = x.left;
		if(y.right != null)
			y.right.parent = y;
		
		y.parent = x;
		x.left = y;
	}
	
	private void zagzag(Entry t){
		Entry x,y,z;
		x = t;
		y = t.parent;
		z = t.parent.parent;
		
		if(z.parent != null){
			if(z.parent.left == z)
				z.parent.left = x;
			else if(z.parent.right == z)
				z.parent.right = x;
		}
		else
			root = x;
		
		x.parent = z.parent;
		z.left = y.right;
		z.parent = y;
		if(z.left != null)
			z.left.parent = z;
		
		y.right = z;
		y.left = x.right;
		if(y.left != null)
			y.left.parent = y;
		
		y.parent = x;
		x.right = y;
	}
	
	private void zagzig(Entry t){
		Entry x,y,z;
		x = t;
		y = t.parent;
		z = t.parent.parent;
		
		if(z.parent != null){
			if(z.parent.left == z)
				z.parent.left = x;
			else if(z.parent.right == z)
				z.parent.right = x;
		}
		else
			root = x;
		
		z.right = x.left;
		if(z.right != null)
			z.right.parent = z;
		
		y.left = x.right;
		if(y.left != null)
			y.left.parent = y;
		
		x.parent = z.parent;
		x.left = z;
		x.right = y;
		y.parent = x;
		z.parent = x;
	}
	
	private void zigzag(Entry t){
		Entry x,y,z;
		x = t;
		y = t.parent;
		z = t.parent.parent;
		
		if(z.parent != null){
			if(z.parent.left == z)
				z.parent.left = x;
			else if(z.parent.right == z)
				z.parent.right = x;
		}
		else
			root = x;
		
		z.left = x.right;
		if(z.left != null)
			z.left.parent = z;
		
		y.right = x.left;
		if(y.right != null)
			y.right.parent = y;
		
		x.parent = z.parent;
		x.right = z;
		x.left = y;
		y.parent = x;
		z.parent = x;
	}
	
	public boolean contains( E elem ) {
        return find( elem, root ) != null;
	}
	
	public E get(E element){
		Entry t;
		t = find(element, root);
		if(t == null)
			return null;
		else
			return t.element;
	}
}