#ifndef _AVL_TREE_H_
#define _AVL_TREE_H_

#include <algorithm> //ONLY used for max
#include <string>
//#define AUDIT
class Comparable
{
private:
	std::string word;
	unsigned int count;
public:
	Comparable(std::string value)
	{
		word=value;
		count = 1;
	}
	unsigned int getCount(void)
	{ return count; }
	std::string getWord(void)
	{ return word; }
	bool operator<( const Comparable& rhs ) const
	{
		return this->word < rhs.word;
	}
	bool operator>( const Comparable& rhs ) const
	{
		return this->word > rhs.word;
	}
	void operator++( void )
	{
		count++;
	}
	void operator++(int num)
	{
		count++;
	}

};
//Base AVL code from the textbook
//Functionality additions and modifications by me.
struct AvlNode
{
public:
    Comparable element;
    AvlNode   *left;
    AvlNode   *right;
    int       height;

    AvlNode( const Comparable & theElement, AvlNode *lt,
                                            AvlNode *rt, int h = 0 )
      : element( theElement ), left( lt ), right( rt ), height( h ) { }
};

//Part c
void printLinearContents( AvlNode* & t , std::string prefix = "" , unsigned int depth = 0);
//Part d
void printBinaryTreeContents( AvlNode* & t, std::string prefix = " ", unsigned int depth = 0 );

//part e
void printBreadthFirst( AvlNode* & t );

//part g
void audit ( std::string trail );

void rotateWithRightChild( AvlNode * & k2 );
void rotateWithLeftChild( AvlNode * & k2 );
void doubleWithRightChild( AvlNode * & k3 );
void doubleWithLeftChild( AvlNode * & k3 );

int height( AvlNode *t );
//F
void insert( Comparable & x, AvlNode * & t );
void remove( Comparable & x, AvlNode * & t );
void checkBalance( AvlNode  * & t );
void rebalanceLeft( AvlNode * & t);
void rebalanceRight( AvlNode *& t );
AvlNode * &findMin(AvlNode *& t);
//void delete();
#endif