treap.java

package homework;
import java.util.Random;
import java.util.Stack;
/**
 * @param <E>
 */
//Bharddwaj Vemulapalli
//CS284
//I pledge my honor that I have abided by the Stevens Honor System.
public class treap<E extends Comparable<E>>{
    private static class Node<E> {

        public E data; // key for the search
        public int priority; // random heap priority
        public Node <E> left; public Node <E> right;

        public Node(E data, int priority){
            if(data == null){
                throw new IllegalArgumentException();
            }
            else{
                this.data = data;
                this.priority = priority;
                this.left = null;
                this.right = null;
            }

        }
        public Node<E> rotateRight(){
//            Node<E> temp = new Node<>(this.data,this.priority);
//            if(this.right!= null){
//                this.data = this.left.data;
//                this.priority = this.left.priority;
//
//                this.left.data = temp.right.data;
//                this.left.priority = temp.right.priority;
//
//                this.right.data = temp.data;
//                this.right.priority = temp.priority;
//            }
//            else {
//                this.data = this.left.data;
//                this.priority = this.left.priority;
//                this.left.data = temp.data;
//                this.left.priority = temp.priority;
//            }
            Node<E> b = this.left;
            this.left = b.right;
            b.right = this;
            return b;
        }
        public Node<E> rotateLeft(){
//            Node<E> temp = new Node<>(this.data,this.priority);
//            if(this.left!= null){
//                this.data = this.right.data;
//                this.priority = this.right.priority;
//
//                this.left.data = temp.data;
//                this.left.priority = temp.priority;
//
//                this.right.data = temp.left.data;
//                this.right.priority = temp.left.priority;
//            }
//            else{
//                this.data = this.right.data;
//                this.priority = this.right.priority;
//                this.right.data = temp.data;
//                this.right.priority = temp.priority;
//            }
            Node<E> b = this.right;
            this.right = b.left;
            b.left = this;
            return b;
        }
        public String toString(){
            return "(key=" + data + ", priority=" + priority + ")";
        }
    }

    private Random priorityGenerator;
    private Node <E> root;
    public Node<E> getRoot(){
        return this.root;
    }
    public treap(){
        priorityGenerator = new Random();
        this.root = null;
    }
    public treap(long seed){
        priorityGenerator = new Random(seed);
        this.root = null;
    }
    boolean add(E key){
        return add(key,this.priorityGenerator.nextInt());
    }

    /**
     * Inserts the node into the Treap
     * @param key   the key value
     * @param priority  the priority
     * @return true after inserting into the treap
     */
    boolean add(E key, int priority){
        Node<E> itemNode = new Node<>(key,priority);
        if(find(key)){
            return false;
        }
        else {
            if(root == null){
                root = itemNode;
                return true;
            }
            else{
                Node<E> current = root;
                Stack<Node<E>> s = new Stack<>();
                boolean right = false; //so we know whether to add to the right or left
                while(current != null){
                    int i = current.data.compareTo(key);
                    if (i==0) {
                        //this means that there is a duplicate
                        return false;
                    }
                    if (i<0) {
                        //if key is greater go on the right
                        s.push(current);
                        right = true;
                        current = current.right;
                    } else {
                        //otherwise go on the left
                        s.push(current);
                        right = false;
                        current = current.left;
                    }

                }
                //now we know that current is null
                if(right){
                    s.peek().right = itemNode;
                    //s.push(itemNode);
                }
                else{
                    s.peek().left = itemNode;
                    //s.push(itemNode);
                }
                //Now we begin the process of sorting the treap based on priority
                Node<E> curr = itemNode;
                if(curr.priority < s.peek().priority){
                    //do nothing
                    return true;
                }
                //System.out.println("hello: " + s.size());
                else{
                    Node<E> temp = curr;
                    curr = s.pop();
                    while(s.size() != 0) {

                        // System.out.println("Current: " + curr);
                        //System.out.println("Previous: " + prev);
                        if(temp.priority < curr.priority){
                            //do nothing
                            return true;
                        }
                        else if (curr.right == temp&& temp.priority > curr.priority) {
                            curr = curr.rotateLeft();



                        } else if (curr.left == temp && temp.priority > curr.priority) {
                            curr = curr.rotateRight();

                        }
                        if (s.size() > 0) {

                            curr = s.pop();
                        }
                    }

                }


            } return true;

        }}

    boolean delete(E key){
        return true;
    }
    private boolean find(Node<E> root, E key){
        if(root == null){
            return false;
        }
        else if(root.data == key){
              return true;
          }
        else{
            return find(root.left,key) || find(root.right,key);
        }

    }
    public boolean find(E key){
        return find(root,key);
    }
    private StringBuilder toString(Node<E> current, int n) {
        StringBuilder b = new StringBuilder();
        for (int i=0; i<n; i++) {
            b.append("-");
        }
        if (current==null) {
            return b.append("null\n");
        } else {
            b.append(current.toString()+"\n");
            b.append(toString(current.left,n+1));
            b.append(toString(current.right,n+1));
            return b;
        }
    }
    public String toString() {
        return toString(root,1).toString();

    }
    public static void main(String args []){
        treap testTree = new treap<Integer>();

        testTree.add(4,19);
        testTree.add(2,31);
        testTree.add(6,70);
        testTree.add(1,84);
        testTree.add(3,12);
        testTree.add(5,83);
        testTree.add(7,26);
        System.out.println(testTree);
        System.out.println(testTree.getRoot());
    }
}