import testSortCol.CollectionWithGet;
import datastructures.BinarySearchTree;

public class SplayTree <E extends Comparable<? super E>> extends BinarySearchTree<E> implements CollectionWithGet<E>{
    int no = 0;
    Entry lastEntry;

    public SplayTree(){
        super();
    }

    @Override
    public Entry find( E elem, Entry t ) {
        no++;
        System.out.println("In find for " + no + "th time");
        if ( t == null ){
            System.out.println("Element not found, splaying last used non-null element");
            if (lastEntry != null){
                splay(lastEntry);
            }
            return null;
        }
        else {
            int jfr = elem.compareTo( t.element );

            if ( jfr  < 0 ){
                lastEntry = t;
                return find( elem, t.left );
            }

            else if ( jfr > 0 ){
                lastEntry = t;
                return find( elem, t.right );
            }
            else {
                System.out.println("Element found, splaying");
                splay(t);
                return t;
            }
        }
    }

    private void splay(Entry e){
        Entry parent, gparent;
        if (e != null){
            while (e.parent != null){
                //System.out.println("Parent of e: " + e.parent);
                parent = e.parent;

                if (parent.parent != null){
                    gparent = parent.parent;
                    boolean childIsLeft = isLeft(e);
                    boolean parentIsLeft = isLeft(parent);

                    if (childIsLeft && parentIsLeft){
                        System.out.println("zagzag");
                        zagZag(gparent);
                    }
                    else if (!childIsLeft && parentIsLeft){
                        System.out.println("zigzag");
                        zagZig(gparent);
                        //zigZag according to reverse system
                        //zigZag(gparent);
                    }
                    else if (childIsLeft && !parentIsLeft){
                        System.out.println("zagig");
                        zigZag(gparent);
                        //zagZig(gparent);
                    }
                    else if (!childIsLeft && !parentIsLeft){
                        System.out.println("zigzig");
                        zigZig(gparent);
                    }
                } else {
                    if (isLeft(e)){
                        System.out.println("zag");
                        zag(parent);

                    }
                    else {
                        System.out.println("zig");
                        zig(parent);
                    }
                }
            }
        }
    }

    /**
     * Checks whether an entry is the left or right children of its parent.
     * Throws an IllegalArgumentException if the entry is an orphan.
     * @param e The entry
     * @return True if the entry is the left child, false otherwise.
     */
    private boolean isLeft(Entry e){
        if (e.parent == null){
            throw new IllegalArgumentException("Parent of e = null");
        }
        return (e.parent.left == e);
    }

    /* Rotera 1 steg i högervarv, dvs
        x'                 y'
       / \                / \
      y'  C   -->        A   x'
     / \                    / \
    A   B                  B   C
     */
    private void zag(Entry x ) {
        Entry   y = x.left;
        E    temp = x.element;

        x.element = y.element;
        y.element = temp;
        x.left    = y.left; // Y right?

        if ( x.left != null ){
            x.left.parent   = x;
        }

        y.left    = y.right;
        y.right   = x.right;

        if ( y.right != null ){
            y.right.parent  = y;
        }

        x.right   = y;
    }

    /* Rotera 1 steg i vänstervarv, dvs
        x'                 y'
           / \                / \
      A   y'  -->        x'  C
         / \            / \
        B   C          A   B
     */
    private void zig( Entry x ) {
        Entry  y  = x.right;
        E temp    = x.element;

        x.element = y.element;
        y.element = temp;
        x.right   = y.right;

        if ( x.right != null ){
            x.right.parent  = x;
        }

        y.right   = y.left;
        y.left    = x.left;

        if ( y.left != null ){
            y.left.parent   = y;
        }

        x.left    = y;
    }

    private void zigZig(Entry x){
        Entry y = x.right;
        Entry z = y.right;

        E temp = z.element;
        z.element = x.element;
        x.element = temp;

        Entry tempEntry = y.left;
        y.left = z;  //Switch left/right
        y.right = z.left; // move C
        z.left = x.left; // move A
        x.left = y; //Switch left/right
        x.right = z.right; //move D
        z.right = tempEntry; //move B



    }




















    /*
                x                  z
           / \                / \
          A       y      =>      y   D
             / \            / \
            B   z          x   C
               / \                / \
              C   D      A   B
     */
    /*private void zigZig(Entry x){
                Entry y = x.right;
                Entry z = y.right;
                E e = x.element;
                System.out.println("x = null:" + (x.element == null));
                System.out.println("y = null:" + (y.element == null));
                System.out.println("z = null:" + (z.element == null));
                x.element = z.element;
                z.element = e;

                if (y.left != null){
                        y.left.parent = x;
                }
                x.right = y.left;

                if (z.left != null){
                        z.left.parent = y;
                }
                y.right = z.left;

                z.left = y;
                y.left = x;
        }*/

    /*
               x                  z
          / \                / \
         y       D      =>      A   y
        / \                    / \
       z   C                  B   x
      / \                        / \
     A   B                      C   D
     */
    private void zagZag(Entry x){
        Entry y = x.left;
        Entry z = y.left;

        E temp = x.element;
        x.element = z.element;
        z.element = temp;

        Entry tempEntry = y.right;
        y.right = z;  //Switch left/right
        y.left = z.right; // move C
        z.right = x.right; // move A
        x.right = y; //Switch left/right
        x.left = z.left; //move D
        z.left = tempEntry; //move B




        /*Entry y = x.left;
                Entry z = y.left;
                E e = x.element;
                x.element = z.element;
                z.element = e;

                if (y.right != null){
                        y.right.parent = x;
                }
                x.left = y.right;

                if (z.right != null){
                        z.right.parent = y;
                }
                y.left = z.right;

                z.right = y;
                y.right = x;*/
    }

    /* Rotera 2 steg i vänstervarv, dvs
        x'                  z'
       / \                /   \
      A   y'   -->       x'    y'
         / \            / \   / \
        z   D          A   B C   D
       / \
      B   C
     */
    private void zigZag(Entry x){
        Entry  y  = x.right,
        z  = x.right.left;
        E      e  = x.element;
        x.element = z.element;
        z.element = e;
        y.left    = z.right;

        if ( y.left != null ){
            y.left.parent = y;
        }

        z.right   = z.left;
        z.left    = x.left;

        if ( z.left != null ){
            z.left.parent = z;
        }
        x.left    = z;
        z.parent  = x;
    }

    /* Rotera 2 steg i högervarv, dvs
        x'                  z'
       / \                /   \
      y'  D   -->        y'    x'
     / \                / \   / \
    A   z'             A   B C   D
       / \
      B   C
     */
    private void zagZig(Entry x){
        Entry   y = x.left;
        Entry   z = x.left.right;
        if (x == null){
            System.out.println("x = null in zagzig");
        }
        if (y == null){
            System.out.println("y = null in zagzig");
        }
        if (z == null){
            System.out.println("z = null in zagzig");
        }

        if ((x.element != null) && (z.element != null)){
            E       e = x.element;
            x.element = z.element;
            z.element = e;
        }
        y.right   = z.left;

        if (y.right != null){
            y.right.parent = y;
        }

        z.left    = z.right;
        z.right   = x.right;

        if ( z.right != null ){
            z.right.parent = z;
        }

        x.right   = z;
        z.parent  = x;
    }

    @Override
    public E get(E e) {
        Entry elem = find(e,root);
        if (elem != null){
            return find(e, root).element;
        }
        else{
            return null;
        }
    }



}