Treap

/* Mark Klingberg
 * m2615919
 * 10/4/2013
 *
 * This program implements the probabilistic treap data structure.
 */

import java.util.*;

class Node <AnyType extends Comparable<AnyType>>{

    AnyType data;
    int priority;

    Node<AnyType> left, right;

    Node(AnyType data, int priority, Node<AnyType> left, Node<AnyType> right)
    {
        this.data = data;
        this.priority = priority;
        this.left = left;
        this.right = right;
    }
}

public class treap<AnyType extends Comparable<AnyType>> {

    private Node<AnyType> root = null;
    private LinkedList<Integer> usedProiritiesList = new LinkedList<Integer>(); //used to store already used priorities.
    private int size = 0;

    public void add(AnyType data){

        int priority  = (int)(Math.ceil(Math.random() * Integer.MAX_VALUE));

        while(true){

            //generate random number from 0 to Integer.MAX_VALUE
            priority = (int)Math.ceil(Math.random() * Integer.MAX_VALUE);

            //if priority is not in L
            if(!(usedProiritiesList.contains(priority))){

                //store it in L
                usedProiritiesList.add(priority);
                    break;
            }

            else{
                //Do nothing, priority has already been used. Continue loop and generate a new priority.
            }
        }

        add(data, priority);
    }

    public void add(AnyType data, int priority){

         root = add(root, data, priority);
    }

    public Node<AnyType> add(Node<AnyType> root, AnyType data, int priority){

        //Insert nod BST style:

        if(root == null){
            //new node is added here.
            size++;
            return new Node<AnyType>(data, priority, null, null);
        }

        else if ((data.compareTo(root.data)) < 0)
        {
            //data < root, go left
            root.left = add(root.left, data, priority);

            //Rotate to satisfy heap priority if needed.
            if(root.left.priority < root.priority){

                //swap the nodes

                //set up parent node, prepare it to be the right child of current child node
                Node<AnyType> temp = new Node<AnyType>(root.data, root.priority, root.left.right, root.right);
                //replace values in parent node with that of the child
                root.data = root.left.data;
                root.priority = root.left.priority;
                //replace partent.left with child.left
                root.left = root.left.left;
                //make its right node the parent node that was set up
                root.right = temp;
            }
        }
        else if ((data.compareTo(root.data)) > 0)
        {
            //data > root, go right
            root.right = add(root.right, data, priority);

            //Rotate to satisfy heap priority if needed.
            if(root.right.priority < root.priority){
                //swap the nodes

                //set up parent node, prepare it to be the left child of current child node
                Node<AnyType> temp = new Node<AnyType>(root.data, root.priority, root.left, root.right.left);

                //replace values in parent node with that of the child
                root.data = root.right.data;
                root.priority = root.right.priority;
                //replace partent.right with child.right
                root.right = root.right.right;
                //make its right node the parent node that was set up
                root.left = temp;
            }
        }
        else
        {
            // Stylistically, I have this here to explicitly state that we are
            // disallowing insertion of duplicate values.
        }

        return root;
    }

    public void remove(AnyType data){

        //if this node exists, remove it
        if(contains(data)){

            root = removeNode(root, data);

        }

        else{
            //The treap did not contain data
        }
    }

    //moves root to the node where data is. if it is a leaf node it deletes it
    private Node<AnyType> removeNode(Node<AnyType> root, AnyType data){

            if(root.data == data){

                //removing node
                if((root.left==null)&&(root.right==null)){
                    size--;
                    return null;
                }
                else{

                    //node found, needs rotation
                    if((root.left==null)||(root.right==null)){

                        if(root.left==null){

                            //set up parent node that will be rotated
                            Node<AnyType> temp = new Node<AnyType>(root.data, root.priority, root.left, root.right.left);

                            //move former child node to parent node position
                            root.data = root.right.data;
                            root.priority = root.right.priority;
                            root.right = root.right.right;

                            //take former parent node and place as new parent nodes child
                            root.left = temp;

                            root.left = removeNode(root.left, data);
                        }
                            //temp.right == null
                        else{

                            //set up parent node that will be rotated
                            Node<AnyType> temp = new Node<AnyType>(root.data, root.priority, root.left.right, root.right);

                            //move former child node to parent node position
                            root.data = root.left.data;
                            root.priority = root.left.priority;
                            root.left = root.left.left;

                            //take former parent node and place as new parent nodes child
                            root.right = temp;

                            root.right = removeNode(root.right, data);

                        }
                    }
                    //2 child nodes, compare for lowest priority
                    else{

                        if(root.left.priority < root.right.priority){

                            //set up parent node that will be rotated
                            Node<AnyType> temp = new Node<AnyType>(root.data, root.priority, root.left.right, root.right);

                            //move former child node to parent node position
                            root.data = root.left.data;
                            root.priority = root.left.priority;
                            root.left = root.left.left;

                            //take former parent node and place as new parent nodes child
                            root.right = temp;

                            root.right = removeNode(root.right, data);

                        }
                        //temp.right.priority < temp.left.priority
                        else{

                            //set up parent node that will be rotated
                            Node<AnyType> temp = new Node<AnyType>(root.data, root.priority, root.left, root.right.left);

                            //move former child node to parent node position
                            root.data = root.right.data;
                            root.priority = root.right.priority;
                            root.right = root.right.right;

                            //take former parent node and place as new parent nodes child
                            root.left = temp;

                            root.left = removeNode(root.left, data);

                        }
                    }
                }
            }

            //temp > data
            else if(data.compareTo(root.data) < 0){

                root.left = removeNode(root.left, data);
            }
            //temp < data
            else{

                root.right = removeNode(root.right, data);
            }

            return root;
        }

    public boolean contains(AnyType data){

        Node<AnyType> temp = new Node<AnyType>(root.data, root.priority, root.left, root.right);

        while(temp != null){

            if(temp.data == data)
                return true;
            //temp > data
            else if(data.compareTo(temp.data) < 0)
            {
                temp = temp.left;
            }
            //temp < data
            else{
                temp = temp.right;
            }
        }

        return false;
    }

    public int size(){
        return size;
    }

    public int height(){

        return findHeight(root, -1, -1);
    }


    private int findHeight(Node<AnyType> root, int i, int max){

        if ( root != null ){

            ++i;
            if ( i > max )
                max = i;

            //increase i by 1 and check for larger max before traveling to next node
            if(root.left != null){

                max = findHeight(root.left, i, max);
            }
            if(root.right != null){

                max = findHeight(root.right, i, max);
            }

            //decrease i by 1 when backtracking
            i--;

        }

        return max;
    }

    public static double difficultyRating(){

        return 2.0;
    }

    public static double hoursSpent(){

        return 8.0;
    }

    public void inorder()
    {
        System.out.print("In-order Traversal:");
        inorder(root);
        System.out.println();
    }

    private void inorder(Node<AnyType> root)
    {
        if (root == null)
            return;

        inorder(root.left);
        System.out.print(" " + root.data);
        inorder(root.right);
    }

    public static void main(String[] args) {

        treap<String> test = new treap<String>();

        test.add("wl",162283549);
        test.add("nx",911094035);
        test.add("dj",742034874);
        test.add("it",1501123419);
        test.add("rz",938870320);
        test.add("je",1118164710);
        test.add("jq",167394538);
        test.add("mx",684413799);
        test.add("kn",1496528339);
        test.add("cl",376379770);
        test.add("kd",359614604);
        test.add("sx",1524460400);
        test.add("tq",760316997);
        test.add("xg",1752446483);
        test.add("ze",1951832343);
        test.add("md",428940290);
        test.add("bu",274689379);
        test.add("po",1954243111);
        test.add("ym",1298570710);
        test.add("im",573274445);
        test.add("kv",736941912);

        test.inorder();

        test.remove("wl");
        test.remove("nx");
        test.remove("dj");

        test.inorder();

        System.out.println(test.size());
        System.out.println(test.height());

    }

}