//  avl_tree.h

#ifndef _AVL_TREE_H_
#define _AVL_TREE_H_

#include <string>

using std::string;

class AVL_Tree
{
protected:
    //  Represents a node in the AVL tree.
    struct Node
    {
        //  The word to store within the tree
        string data;     
        //  Pointer to the left subtree, null if it has no subtree
        Node *left;      
        //  Pointer to the right subtree, null if it has no subtree
        Node *right;
        //  The number of times the word has been inserted into the tree
        int frequency;
        //  The height of the node
        int height;
        //  The constructor creates a leaf node with a given value
        Node(const string& s): 
            data(s), 
            left(0), 
            right(0), 
            frequency(0), 
            height(0)
        {}
    };

    //  The root of the tree
    Node *root;


    //  Frees up the space held by the AVL subtree pointed to by p.
    void dispose(Node *p);

    //  Returns a deep copy of the AVL subtree pointed to by p.
    Node *copy(Node *p) const;

    //  Returns true if the AVL subtree pointed to by p is identical 
    //  in value to the AVL subtree pointed to by q.
    bool equals(Node *p, Node *q) const;

    //  Inserts a word into the AVL subtree pointed to by p.
    //  If the word is already present in the tree, the 
    //  corresponding node's frequency is updated. The insertion 
    //  maintains the AVL tree's height balanced property.  
    //  Maintains the AVL properties of the tree.
    //  A client does not call this protected method directly;
    //  instead, clients use the public method insert which calls
    //  this method to do the work.
    //  p points to an AVL subtree.
    //  s is the word to insert.
    //  Returns a possibly new pointer to the subtree.
    Node *insert(Node *p, const string& s);

    //  Returns the number of times the given word appears in 
    //  the subtree pointed to by p; that is, the word's frequency.  
    //  The contents of the tree are unaffected.
    //  A client does not call this protected method directly;
    //  instead, clients use the public method frequency which 
    //  calls this method to do the work.
    //  p points to an AVL subtree.
    //  s is the word to find.
    //  Returns the frequency of s in p; returns 0 if the word 
    //  is not present in the tree.
    int frequency(Node *p, const string& s) const;

    //  Returns the height of the node in
    //  the AVL subtree pointed to by p.
    //  The contents of the tree are unaffected.
    //  A client does not call this protected method;
    //  the method is a helper method for several other protected
    //  methods.
    //  p points to an AVL subtree.
    //  Returns the height of p; returns -1 if p is null.
    int height(Node *p) const;

    //  Rotate binary tree node with left child.
    //  Update heights, then set root.
    //  This protected method is a helper method for
    //  the protected insert method; therefore, clients do
    //  use this method.
    Node *rotate_with_left_child(Node *p);

    //  Double rotate binary tree node: first left child with
    //  its right child and then p with its with its new left
    //  child.
    //  Update heights, then set root.
    //  This protected method is a helper method for
    //  the protected insert method; therefore, clients do
    //  use this method.
    Node *double_rotate_with_left_child(Node *p);


    //  Rotate binary tree node with right child.
    //  Update heights, then set root.
    //  This protected method is a helper method for
    //  the protected insert method; therefore, clients do
    //  use this method.
    Node *rotate_with_right_child(Node *p);

    //  Double rotate binary tree node: first right child with
    //  its left child and then p with its with its new right
    //  child.
    //  Update heights, then set root.
    //  This protected method is a helper method for
    //  the protected insert method; therefore, clients do
    //  use this method.
    Node *double_rotate_with_right_child(Node *p);

    //  Draws the structure of the tree.
    //  A client does not call this protected method directly;
    //  instead, clients use the public method draw which 
    //  calls this method to do the work.
    void draw(Node *p, char link, int depth) const;

public:
    //  Constructor makes an empty AVL tree
    AVL_Tree(): root(0) {}

    //  Copy constructor makes an exact deep copy from an existing
    //  AVL tree.  The space held by this tree is properly
    //  deallocated.
    AVL_Tree(const AVL_Tree& other)
    {
        if ( this != &other )  //  Prevent self copy
        {
            //  Clean up existing tree
            dispose(root);
            root = copy(other.root);
        }
    }

    //  Destructor properly deallocates space held by this AVL
    //  tree.
    ~AVL_Tree()
    {
        dispose(root);
    }

    //  Assignment operator makes an exact deep copy from an
    //  existing AVL tree.  The space held by this tree is
    //  properly deallocated.
    AVL_Tree& operator=(const AVL_Tree& other)
    {
        if ( this != &other )  //  Prevent self copy
        {
            //  Clean up existing tree
            dispose(root);
            root = copy(other.root);
        }
        return *this;
    }

    //  Determines if one AVL tree is an exact copy of another.
    bool operator==(const AVL_Tree& other) const
    {
        return equals(root, other.root);
    }

    //  Inserts a word into the AVL tree.  If the word is already
    //  present in the tree, the corresponding node's frequency
    //  is updated.  The insertion maintains the AVL tree's height
    //  balanced property.  
    //  Calls the protected method insert to do the work.
    //  The parameter 'word' is the word to insert into the tree.
    void insert(const string& word)
    {
        //  Insert word into the subtree pointed to by root (that
        //  is the whole tree); the root is at depth zero.
        root = insert(root, word);
    }

    //  Returns the number of times the given word appears in 
    //  the tree; that is, the word's frequency.  
    //  Returns 0 if the word is not present in the tree.
    //  Calls the protected method frequency to do the work.
    //  The parameter 'word' is the word to seek.
    int frequency(const string& word) const
    {
        //  Compute the frequency of the word found in the subtree
        //  pointed to by root (that is, the whole tree)
        return frequency(root, word);
    }

    //  Draws the structure of the tree
    void draw() const
    {
        draw(root, '-', 0);
    }

    //  Returns the height of the AVL tree.
    //  Returns -1 if the tree is empty.
    //  The protected method height does the work.
    int height() const
    {
        return height(root);
    }
};

#endif