//From http://darcsden.com/avakar/divine/browse/hoard/heaplayers/experimental/treap.h
#ifndef _TREAP_H_
#define _TREAP_H_

#include <cassert>
#include <cstdlib>
#include <climits>

// A Cartesian tree.
// adapted from treap code by Bobby Blumofe

template<class KEY, class VALUE>
class Treap {

public:

    class Node {   // A node in the treap.
        friend class Treap;

        unsigned int priority; //   The priority.
        KEY key;      //   The key.
        VALUE value;  //   The value.
        Node* parent; //   Pointer to parent.
        Node* left;   //   Pointer to left child.
        Node* right;  //   Pointer to right child.

    public:
        // Construct node.
        Node(void) :
                left(NULL), right(NULL){
        }

        Node(unsigned int priority_, KEY key_, VALUE value_, Node* parent_) :
                priority(priority_), key(key_), value(value_), parent(parent_), left(NULL), right(NULL){
        }

        KEY getKey(void) const{
            return key;
        }

        VALUE getValue(void) const{
            return value;
        }
    };

    Node* tmp_node;

    // Construct an empty treap.
    Treap(void);

    // Destructor.
    ~Treap(void);

    // Return value of key or 0 if not found.
    // Return a matching node (or NULL if not found).
    Node* lookup(KEY key) const{
        return lookup_(key);
    }

    // Return a matching node (or NULL if not found).
    Node* lookupGreater(KEY key) const{
        return lookupGreater_(key);
    }

    // Set the given key to have the given value.
    void insert(Node* n, KEY key, VALUE value, unsigned int priority);

    // Remove entry with given key.
    // Remove entry.
    Node* remove(Node* node){
#if 0
        // Search for node with given key.
        Node* node = lookup_ (key);
#endif

        // If not found, then do nothing.
        if(!node)
            return NULL;

        // While node is not a leaf...
        while(node->left || node->right){

            // If left child only, rotate right.
            if(!node->right)
                rotateRight(node);

                // If right child only, rotate left.
            else if(!node->left)
                rotateLeft(node);

                // If both children,
            else{
                if(node->left->priority < node->right->priority)
                    rotateRight(node);
                else
                    rotateLeft(node);
            }
        }

        // Clip off node.
        Node* parent = node->parent;
        if(!parent){
            assert(root == node);
            root = 0;
        }else{
            if(parent->left == node)
                parent->left = 0;
            else
                parent->right = 0;
        }

        // Check treap properties.
        // assert (heapProperty (root, INT_MIN));
        // assert (bstProperty (root, INT_MIN, INT_MAX));

#if 0
        delete node;
        return NULL;
#else
        // Return the removed node.

        return node;
#endif
    }

private:

    Node* root;  // Pointer to root node of treap.

    Node* split(KEY key);

    void unsplit(Node* tree);

    // Disable copy and assignment.
    Treap(const Treap& treap){
        tmp_node = new Node();
    }

    Treap& operator=(const Treap& treap){
        return *this;
    }

    // Check treap properties.
    int heapProperty(Node* node, int lbound) const;

    int bstProperty(Node* node, int lbound, int ubound) const;

    void insert_(Node* n, KEY key, unsigned int priority);

    // Delete treap rooted at given node.
    void deleteTreap(Node* node);

    // Return node with given key or NULL if not found.
    Node* lookup_(KEY key) const;

    Node* lookupGreater_(KEY key) const;

    Node* lookupGeq(KEY key, Node* root) const;

    // Perform rotations.
    void rotateLeft(Node* node);

    void rotateRight(Node* node);
};

// Construct an empty treap.
template<class KEY, class VALUE>
Treap<KEY, VALUE>::Treap(void) :
        root(0){
}

// Destructor.
template<class KEY, class VALUE>
Treap<KEY, VALUE>::~Treap(void){
    deleteTreap(root);
}

// Delete treap rooted at given node.
template<class KEY, class VALUE>
void Treap<KEY, VALUE>::deleteTreap(Node* node){
    // If empty, nothing to do.
    if(!node)
        return;

    // Delete left and right subtreaps.
    deleteTreap(node->left);
    deleteTreap(node->right);

    // Delete root node.
    delete node;
}

// Test heap property in subtreap rooted at node.
template<class KEY, class VALUE>
int Treap<KEY, VALUE>::heapProperty(Node* node, int lbound) const{
    // Empty treap satisfies.
    if(!node)
        return 1;

    // Check priority.
    if(node->priority < lbound)
        return 0;

    // Check left subtreap.
    if(!heapProperty(node->left, node->priority))
        return 0;

    // Check right subtreap.
    if(!heapProperty(node->right, node->priority))
        return 0;

    // All tests passed.
    return 1;
}

// Test bst property in subtreap rooted at node.
template<class KEY, class VALUE>
int Treap<KEY, VALUE>::bstProperty(Node* node, int lbound, int ubound) const{
    // Empty treap satisfies.
    if(!node)
        return 1;

    // Check key in range.
    if(node->key < lbound || node->key > ubound)
        return 0;

    // Check left subtreap.
    if(!bstProperty(node->left, lbound, node->key))
        return 0;

    // Check right subtreap.
    if(!bstProperty(node->right, node->key, ubound))
        return 0;

    // All tests passed.
    return 1;
}

// Perform a left rotation.
template<class KEY, class VALUE>
void Treap<KEY, VALUE>::rotateLeft(Node* node){
    // Get right child.
    Node* right = node->right;
    assert(right);

    // Give node right's left child.
    node->right = right->left;

    // Adjust parent pointers.
    if(right->left)
        right->left->parent = node;
    right->parent = node->parent;

    // If node is root, change root.
    if(!node->parent){
        assert(root == node);
        root = right;
    }

        // Link node parent to right.
    else{
        if(node->parent->left == node)
            node->parent->left = right;
        else
            node->parent->right = right;
    }

    // Put node to left of right.
    right->left = node;
    node->parent = right;
}

// Perform a right rotation.
template<class KEY, class VALUE>
void Treap<KEY, VALUE>::rotateRight(Node* node){
    // Get left child.
    Node* left = node->left;
    assert(left);

    // Give node left's right child.
    node->left = left->right;

    // Adjust parent pointers.
    if(left->right)
        left->right->parent = node;
    left->parent = node->parent;

    // If node is root, change root.
    if(!node->parent){
        assert(root == node);
        root = left;
    }

        // Link node parent to left.
    else{
        if(node->parent->left == node)
            node->parent->left = left;
        else
            node->parent->right = left;
    }

    // Put node to right of left.
    left->right = node;
    node->parent = left;
}

// Return node with given key or 0 if not found.
template<class KEY, class VALUE>
typename Treap<KEY, VALUE>::Node* Treap<KEY, VALUE>::lookup_(KEY key) const{
    // Start at the root.
    Node* node = root;

    // While subtreap rooted at node not empty...
    while(node){

        // If found, then return value.
        if(key == node->key)
            return node;

            // Otherwise, search left or right subtreap.
        else if(key < node->key)
            node = node->left;
        else
            node = node->right;
    }

    // Return.
    return node;
}

template<class KEY, class VALUE>
typename Treap<KEY, VALUE>::Node* Treap<KEY, VALUE>::lookupGreater_(KEY key) const{
    return lookupGeq(key, root);
}

// Return node with greater or equal key or 0 if not found.
template<class KEY, class VALUE>
typename Treap<KEY, VALUE>::Node* Treap<KEY, VALUE>::lookupGeq(KEY key, Node* rt) const{
    Node* bestSoFar = NULL;

    // Start at the root.
    Node* node = rt;

    // While subtreap rooted at node not empty...
    while(node){

        // If exact match found, then return value.
        if(key == node->key)
            return node;

        // Move right -- this node is too small.
        if(node->key < key)
            node = node->right;

            // Otherwise, this one's pretty good;
            // look for a better match.
        else{
            if((bestSoFar == NULL) || (bestSoFar->key > node->key))
                bestSoFar = node;
            node = node->left;
        }
    }

    // Return.
    return bestSoFar;
}

template<class KEY, class VALUE>
typename Treap<KEY, VALUE>::Node* Treap<KEY, VALUE>::split(KEY key){

    insert(tmp_node, key, tmp_node->getValue(), std::numeric_limits<unsigned int>::max());
    assert(root == tmp_node);
    assert(tmp_node->parent == NULL);
    tmp_node->left->parent = NULL;
    tmp_node->right->parent = NULL;

    root = tmp_node->right;
    Node* ret = tmp_node->left;

    tmp_node->left = NULL;
    tmp_node->right = NULL;
    return ret;
}

// Set the given key to have the given value.
template<class KEY, class VALUE>
void Treap<KEY, VALUE>::insert(Treap<KEY, VALUE>::Node* n, KEY key, VALUE value, unsigned int priority){

    //  print();

    // 0 is not a valid value.
    assert(value != 0);

    // Start at the root.
    Node* parent = 0;
    Node* node = root;

    // While subtreap rooted at node not empty...
    while(node){

#if 0
        // If found, then update value and done.
        if (key == node->key) {
            node->value = value;
            return;
        }
#endif

        // Otherwise, search left or right subtreap.
        parent = node;

        if(key < node->key)
            node = node->left;
        else
            node = node->right;
    }

    // Not found, so create new node.
    // EDB was
    // node = new Node (lrand48(), key, value, parent);
    node = new(n) Node(priority, key, value, parent);
    // node = new Node (priority, key, value, parent);

    // If the treap was empty, then new node is root.
    if(!parent)
        root = node;

        // Otherwise, add node as left or right child.
    else if(key < parent->key)
        parent->left = node;
    else
        parent->right = node;

    // While heap property not satisfied...
    while(parent && parent->priority > node->priority){

        // Perform rotation.
        if(parent->left == node)
            rotateRight(parent);
        else
            rotateLeft(parent);

        // Move up.
        parent = node->parent;
    }

    // print();

    // Check treap properties.
    // assert (heapProperty (root, INT_MIN));
    // assert (bstProperty (root, INT_MIN, INT_MAX));
}

#endif // _TREAP_H_
