#ifndef TREAP_H
#define TREAP_H
#include
#include "TreapNode.h"
class Treap {
public:
// default constructor:
// POST: *this is an empty tree
Treap();
// copy constructor
// POST *this is a copy of other
Treap(const Treap& other);
// assignment operator
// Post: other was assigned to *this
Treap& operator= (const Treap& 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(int key);
// POST: removes a node with the given key from *this; if no such
// node is present, nothing happens
void remove(const int 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* find(int key) const;
// POST: const pointer to the root of *this is returned
const TreapNode* 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: pretty-prints *this
void pretty_print(std::ostream& o) const;
private:
TreapNode* root_;
// POST: a pointer to a copy of the subtreap rooted at current is returned
TreapNode* copy (const TreapNode* current);
// POST: the subtreap rooted at current is emptied
void clear_subtree(TreapNode* 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*& current, int key, int priority);
// helper methods, used by the public print methods
void print (std::ostream& o, const TreapNode* current) const;
void print_preorder (std::ostream& o, const TreapNode* current) const;
void print_postorder (std::ostream& o, const TreapNode* current) const;
// PRE: current->right_ != 0
// POST: a rotation to the left has been performed
void rotate_left (TreapNode*& current);
// PRE: current->left_ != 0
// POST: a rotation to the right has been performed
void rotate_right (TreapNode*& current);
// 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* current, int& min, int& max) const;
// POST: checks whether the subtree hanging off current is a
// heap for its priorities
bool is_heap (const TreapNode* current) const;
};
// POST: t is written to o in in-order (sorted order)
std::ostream& operator<< (std::ostream& o, const Treap& t);
#endif