#ifndef GENERICTREAP_H
#define GENERICTREAP_H

#include <iostream>
#include "GenericTreapNode.h"

template <typename T>
class Treap {
public:
  // default constructor:
  // POST: *this is an empty tree
  Treap();
	
  // copy constructor
  // POST *this is a copy of other
  Treap(const Treap<T>& other);

  // assignment operator
  // Post: other was assigned to *this
  Treap<T>& operator= (const Treap<T>& other);
	
  // Destructor
  ~Treap();

  // POST: checks whether *this is a binary search tree for its
  //       keys and a heap for its priorities
  bool is_valid() const;
	
  // POST: the tree is empty
  void clear();
	
  // POST: a new TreapNode with the given key is inserted into *this
  void insert(const T& key);
	
  // POST: removes a node with the given key from *this; if no such
  //       node is present, nothing happens
  void remove(const T& key);
	
  // POST: a constant pointer to a node with the given key is returned, 
  //       or 0 if such a node is not present
  const TreapNode<T>* find(const T& key) const;
	
  // POST: const pointer to the root of *this is returned
  const TreapNode<T>* get_root() const;
	
  // POST: *this is written to o in pre-order
  void print_preorder (std::ostream& o) const;
	
  // POST: *this is written to o in post-order
  void print_postorder (std::ostream& o) const;
	
  // POST: *this is written to o in in-order (sorted order)
  void print (std::ostream& o) const;
	
  // POST: height of *this is returned; -1 if *this is empty
  int height() const;
	
  // POST: the number of nodes in *this is returned
  int size() const;

  // POST: returns the key of the median of the sequence represented by *this
  T median() const;

  // PRE: *this is not empty
  // POST: removes the element with the maximum value and returns its key
  T remove_max();

  // POST: pretty-prints *this
  void pretty_print(std::ostream& o) const;

private:
  TreapNode<T>* root_;

  // POST: a pointer to a copy of the subtreap rooted at current is returned
  TreapNode<T>* copy (const TreapNode<T>* current); 

  // POST: the subtreap rooted at current is emptied
  void clear_subtree(TreapNode<T>* current);

  // PRE: current is a pointer in *this
  // POST: a new TreapNode with key and priority is inserted into the subtree 
  //       hanging off current
  void insert (TreapNode<T>*& current, const T& key, int priority);

  // PRE: current is a pointer in *this
  // POST: removes a node with the given key from the subtreap hanging off 
  //       current; if key is not present, nothing happens
  void remove (TreapNode<T>*& current, const T& key);

  // PRE: current is a pointer to a node in *this
  // POST: removes a node with the maximum key from the subtreap hanging off 
  //       current;
  T remove_max (TreapNode<T>*& current);

  // PRE: current is a pointer to a node in *this
  // POST: the root key of the subtree hanging off current is removed
  void remove_root (TreapNode<T>*& current);

  // helper methods, used by the public print methods
  void print (std::ostream& o, const TreapNode<T>* current) const;
  void print_preorder (std::ostream& o, const TreapNode<T>* current) const;
  void print_postorder (std::ostream& o, const TreapNode<T>* current) const;

  // POST: returns size of the subtree hanging off current
  int size (const TreapNode<T>* current) const;

  // PRE: current->right_ != 0
  // POST: a rotation to the left has been performed
  void rotate_left (TreapNode<T>*& current);

  // PRE: current->left_ != 0
  // POST: a rotation to the right has been performed
  void rotate_right (TreapNode<T>*& current);

  // prettyprints one row of the tree
  void print_row (std::ostream& o, double row) const;

  // POST: height of the subtree hanging off current is returned
  int height(const TreapNode<T>* current) const;

  // PRE: current is a pointer to a node in *this
  // POST: checks whether the subtreap hanging off current is a 
  // binary search tree for its keys, and returns the smallest
  // and largest key in min and max
  bool is_binary_search_tree (const TreapNode<T>* current, T& min, T& max) const;

  // PRE: current is a pointer to a node in *this
  // POST: checks whether the subtree hanging off current is a 
  // heap for its priorities
  bool is_heap (const TreapNode<T>* current) const;
};

// POST: t is written to o in in-order (sorted order)
template <typename T>
std::ostream& operator<< (std::ostream& o, const Treap<T>& t);

// IMPLEMENTATION

#include <cassert>
#include <cstdlib>
#include <string>
#include <algorithm>

Treap<int> trepInt;


template <typename T>
Treap<T>::Treap()
  : root_(0)
{}

template <typename T>
Treap<T>::Treap(const Treap<T>& other) 
  : root_(0)
{
  root_ = copy (other.root_);
}

template <typename T>
TreapNode<T>* Treap<T>::copy (const TreapNode<T>* current) {
  if (current != 0) {
    return new TreapNode<T> (current->get_key(), 
			  current->get_priority(), 
			  copy(current->get_left()), 
			  copy(current->get_right()));
  } else
    return 0;
}	

template <typename T>
Treap<T>& Treap<T>::operator= (const Treap<T>& other)
{
 if (root_ != other.root_) { //check for self-assignment
    clear();
    root_ = copy (other.root_);
  }
  return *this;
}

template <typename T>
Treap<T>::~Treap()
{
  clear();
}	

template <typename T>
void Treap<T>::clear()
{
  clear_subtree(root_);	
  root_ = 0;
}

template <typename T>
void Treap<T>::clear_subtree(TreapNode<T>* current)
{
  if (current != 0) {	
    clear_subtree(current->left_);
    clear_subtree(current->right_);
    delete current;
  }
}

template <typename T>
void Treap<T>::insert(const T& key)
{
  insert (root_, key, std::rand());
}

template <typename T>
void Treap<T>::insert (TreapNode<T>*& current, const T& key, const int priority) 
{
  if (current == 0) 
    current = new TreapNode<T> (key, priority);
  else 
    if (key < current->key_) {
      insert (current->left_, key, priority);
      if (priority > current->get_priority()) 
	rotate_right (current);
    }
    else {
      insert (current->right_, key, priority);
      if (priority > current->get_priority()) 
	rotate_left (current);
    }
}

template <typename T>
void Treap<T>::rotate_left (TreapNode<T>*& current) 
{
  assert (current->right_ != 0);
  TreapNode<T>* old_current = current;
  current = current->right_;
  old_current->right_ = current->left_;
  current->left_ = old_current;
}

template <typename T>
void Treap<T>::rotate_right (TreapNode<T>*& current) 
{
  assert (current->left_ != 0);
  TreapNode<T>* old_current = current;
  current = current->left_;
  old_current->left_ = current->right_;
  current->right_ = old_current;
}

template <typename T>
void Treap<T>::remove(const T& key)
{
  remove (root_, key);
}

template <typename T>
void Treap<T>::remove(TreapNode<T>*& current, const T& key)
{
  if (current == 0) 
    return;
  if (key < current->key_) 
    return remove (current->left_, key);
  if (key > current->key_)
    return remove (current->right_, key);
  assert (key == current->key_);
  remove_root (current);
}

template <typename T>
void Treap<T>::remove_root (TreapNode<T>*& current) 
{
  assert (current != 0);
  if (current->left_ != 0 && 
      (current->right_ == 0 || current->left_->priority_ > current->right_->priority_)) {
    rotate_right (current);
    return remove_root (current->right_);
  }
  if (current->right_ != 0 && 
      (current->left_ == 0 || current->right_->priority_ >= current->left_->priority_)) {
    rotate_left (current);
    return remove_root (current->left_);
  }
  // now we have a leaf
  assert (current->left_ == 0 && current->right_ == 0);
  delete current;
  current = 0;
}

template <typename T>
const TreapNode<T>* Treap<T>::find(const T& key) const 
{
  const TreapNode<T>* current = root_;
  while (current != 0 && current->get_key() != key)
    if (key < current->get_key())
      current = current->get_left();
    else
      current = current->get_right();
  return current;
}


// This method is not very efficient but the issue is only the function size() that is O(n) where n is the number of the nodes in the list. One can do this in O(1) by storing the size of the tree rooted on the node as a field of the node.
// PRE: *this is not an empty tree
// returns the median of the sequnce stored in *this
template <typename T>
T Treap<T>::median() const 
{
  assert(root_ != 0);
  const int medianPos = size() / 2;
  const TreapNode<T>* current = root_;
  // smaller than current
  int smaller = size(current->get_left());
  while (smaller != medianPos) {
    if (smaller < medianPos) {
      current = current->get_right();
      assert(current != 0);
      smaller += size(current->get_left()) + 1;
    } else {
      current = current->get_left();			
      assert(current != 0);
      smaller = smaller - size(current->get_right())	- 1;
    }
  }
  return current->get_key();
}

template <typename T>
T Treap<T>::remove_max()
{
  assert (root_ != 0);
  return remove_max (root_);
}

template <typename T>
T Treap<T>::remove_max(TreapNode<T>*& current)
{
  assert (current != 0);
  if (current->get_right() != 0) 
    return remove_max (current->right_);
  else {
    T result = current->get_key();
    remove_root (current);
    return result;
  }
}

template <typename T>
int Treap<T>::height() const
{
  return height(root_);
}

template <typename T>
int Treap<T>::height(const TreapNode<T>* current) const
{
  if (current == 0)
    return -1;
  else
    return 1 + std::max(height(current->get_left()), height(current->get_right()));
}

template <typename T>
int Treap<T>::size() const
{
  return size(root_);
}

template <typename T>
int Treap<T>::size(const TreapNode<T>* current) const 
{
  if (current == 0)
    return 0;
  return 1 + size(current->get_left()) + size(current->get_right());
}

template <typename T>
const TreapNode<T>* Treap<T>::get_root() const 
{
  return root_;
}

template <typename T>
void Treap<T>::print_preorder(std::ostream& o) const 
{
  print_preorder(o, root_);
}

template <typename T>
void Treap<T>::print_preorder(std::ostream& o, const TreapNode<T>* current) const 
{
  if (current != 0) {
    o << current->get_key() << " ";
    print_preorder(o, current->get_left());
    print_preorder(o, current->get_right());
  }
}

template <typename T>
void Treap<T>::print_postorder(std::ostream& o) const 
{
  print_postorder(o, root_);
}

template <typename T>
void Treap<T>::print_postorder(std::ostream& o, const TreapNode<T>* current) const {
  if (current != 0) {
    print_postorder(o, current->get_left());
    print_postorder(o, current->get_right());
    o << current->get_key() << " ";
  }
}

template <typename T>
void Treap<T>::print(std::ostream& o) const 
{	
  print(o, root_);
}

template <typename T>
void Treap<T>::print(std::ostream& o, const TreapNode<T>* current) const
{
  if (current != 0) {
    print(o, current->get_left());
    o << current->get_key() << " ";
    print(o, current->get_right());
  }
}

template <typename T>
void Treap<T>::pretty_print (std::ostream& o) const
{
  for (double row = 0; row < size(); row+=0.5) {
    print_row (o, row); o << std::endl;
  }
}

template <typename T>
void Treap<T>::print_row (std::ostream& o, double row) const {
  char last = 'x';
  const TreapNode<T>* current = root_;
  while (current != 0) {
    if (row < size(current->get_right())) { // 'r'
      if (last == 'l') 
	o << "|   ";
      else
	o << "    ";
      last = 'r';
      current = current->get_right();
      continue;
    }
    if (row > size(current->get_right())) { // 'l'
      if (last == 'r') 
	o << "|   ";
      else
	o << "    ";
      last = 'l';
      row = row - size(current->get_right()) - 1;
      current = current->get_left();
      continue;
    }
    assert (row == size(current->get_right()));
    o << " --(" << current->get_key() << ")";
    break;
  }
}

template <typename T>
bool Treap<T>::is_valid () const {
  T min, max;
  return (root_ == 0 || (is_binary_search_tree (root_, min, max) && is_heap(root_)));
}

template <typename T>
bool Treap<T>::is_binary_search_tree (const TreapNode<T>* current, T& min, T& max) const {
  assert (current != 0);
  min = max = current->get_key(); 
  T min_r = max;
  T max_l = min;
  bool ok_l = true;
  bool ok_r = true;
  if (current->get_left() != 0) 
    ok_l = is_binary_search_tree (current->get_left(), min, max_l);
  if (current->get_right() != 0) 
    ok_r = is_binary_search_tree (current->get_right(), min_r, max);
  return (ok_l && ok_r && max_l <= current->get_key() && current->get_key() <= min_r);
}

template <typename T>
bool Treap<T>::is_heap (const TreapNode<T>* current) const {
  assert (current != 0);
  if (current->get_left() != 0)
    if (!is_heap (current->get_left()) || current->get_priority() < current->get_left()->get_priority())
      return false;
  if (current->get_right() != 0)
    if (!is_heap (current->get_right()) || current->get_priority() < current->get_right()->get_priority())
      return false;
  return true;
}

template <typename T>
std::ostream& operator<< (std::ostream& o, const Treap<T>& tree) {
  tree.print(o);
  return o;
}

#endif