public class SplayWithGet<E extends Comparable<? super E>> extends BinarySearchTree<E> implements CollectionWithGet<E> {

    /**
     * Global variable which contains the value of the last compareTo call when finding elements in the tree.
     * It is used to lower the amount of calls to compareTo.
     */
    private int jfr;

    /**
     * Retrieves the given element and put the element as root by rotating the nodes.
     * Returns null if the element doesn't exist in the tree.
     * @param element       The element of interest
     * @return              The element of interest
     */
    @Override

    public E get(E element) {
        if (element == null) {
            throw new NullPointerException("Tada nullpointer");
        }

        if(root == null){return null;}
        Entry entry = find(element, root);


        if(entry == null){return null;}
        splay(entry);


        if(entry != root) {
            if (entry == entry.parent.left) {
                zig(entry.parent);
                entry = entry.parent;
            } else if (entry == entry.parent.right) {
                zag(entry.parent);
                entry = entry.parent;
            }
        }

        if(jfr == 0){
            return entry.element;
        } else {
            return null;
        }
    }

    /**
     * Rotates the nodes until entry is root or one level beneath root
     * @param entry
     */
    protected void splay(Entry entry){
        while (entry.parent != null && entry.parent.parent != null) {
            Entry parent = entry.parent;
            Entry grandparent = parent.parent;

            if (parent.left == entry) {
                if (grandparent.left == parent) {
                    zigzig(entry);
                    entry = grandparent;
                } else if (grandparent.right == parent) {
                    zagzig(grandparent);
                    entry = grandparent;
                }
            } else if (parent.right == entry) {
                if (grandparent.left == parent) {
                    zigzag(grandparent);
                    entry = grandparent;
                } else if (grandparent.right == parent) {
                    zagzag(entry);
                    entry = grandparent;
                }
            }
        }
    }


    /**
     * searches the tree for the given element and returns it if it is found. If
     * the element is not found it will return the closest element.
     * @param elem
     * @param t
     * @return
     */
    protected Entry find( E elem, Entry t ) {
        if ( t == null )
            return null;
        else {
            jfr = elem.compareTo( t.element );
            if ( jfr  < 0 ) {
                if (t.left == null)
                    return t;
                return find(elem, t.left);
            }else if ( jfr > 0 ) {
                if (t.right == null)
                    return t;
                return find(elem, t.right);
            }else
                return t;
        }
    }  //   find

// ========== ========== ========== ==========

    /* Rotera 1 steg i hogervarv, dvs
              x'                 y'
             / \                / \
            y'  C   -->        A   x'
           / \                    / \
          A   B                  B   C
    */
    private void zig (Entry x ){
        Entry y = x.left;
        E temp = x.element;
        x.element = y.element;
        y.element = temp;
        x.left = y.left;
        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;

    } //   rotateRight
    // ========== ========== ========== ==========

    /* Rotera 1 steg i vanstervarv, dvs
              x'                 y'
             / \                / \
            A   y'  -->        x'  C
               / \            / \
              B   C          A   B
    */
    private void zag (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;
    } //   rotateLeft
    // ========== ========== ========== ==========

    /* Rotera 2 steg i hogervarv, dvs
              x'                  z'
             / \                /   \
            y'  D   -->        y'    x'
           / \                / \   / \
          A   z'             A   B C   D
             / \
            B   C
    */
    private void zigzag (Entry x ){
        Entry y = x.left,
                z = x.left.right;
        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;
    }  //  doubleRotateRight
    // ========== ========== ========== ==========

    /* Rotera 2 steg i vanstervarv, dvs
               x'                  z'
              / \                /   \
             A   y'   -->       x'    y'
                / \            / \   / \
               z   D          A   B C   D
              / \
             B   C
     */
    private void zagzig (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;
    } //  doubleRotateLeft

    private void zigzig (Entry x){
        zig(x.parent.parent);
        zig(x.parent);
    }

    private void zagzag (Entry x){
        zag(x.parent.parent);
        zag(x.parent);
    }
}