// Implementation of Treap class (Randomized Binary Search Tree)
#include "TreapSkeleton.h"
#include <cassert>
#include <cstdlib>
#include <string>
#include <algorithm>

Treap::Treap()
  : root_(0)
{}

Treap::Treap(const Treap& other) 
  : root_(0)
{
  root_ = copy (other.root_);
}

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

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

Treap::~Treap()
{
  clear();
}	

void Treap::clear()
{
  clear_subtree(root_);	
  root_ = 0;
}

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

void Treap::insert(const int key)
{
  insert (root_, key, std::rand());
}

void Treap::insert (TreapNode*& current, const int key, const int priority) 
{
  if (current == 0) 
    current = new TreapNode (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);
    }
}

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

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

void Treap::remove(const int key)
{
  // your code goes here
}

const TreapNode* Treap::find(const int key) const 
{
  const TreapNode* 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;
}

int Treap::height() const
{
  return 0;
  // your code goes here
}

int Treap::size() const
{						
  return 0;
  // your code goes here
}

const TreapNode* Treap::get_root() const 
{
  return root_;
}

void Treap::print_preorder(std::ostream& o) const 
{
  print_preorder(o, root_);
}

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

void Treap::print_postorder(std::ostream& o) const 
{
  print_postorder(o, root_);
}

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

void Treap::print(std::ostream& o) const 
{	
  print(o, root_);
}

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

void Treap::pretty_print (std::ostream& o) const
{
  // your code goes here
}

bool Treap::is_valid () const {
  int min, max;
  return (root_ == 0 || is_binary_search_tree (root_, min, max) && is_heap(root_));
}

bool Treap::is_binary_search_tree (const TreapNode* current, int& min, int& max) const {
  assert (current != 0);
  min = max = current->get_key(); 
  int min_r = max;
  int 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);
}

bool Treap::is_heap (const TreapNode* 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;
}

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