// Arne Andersson tree implementation
// By: Nick Cash
// Computer Science III

// For more information on this data type please visit Wikipedia

// Note: This implementation is a string to integer map

// inclusion guard
#ifndef INC_AA_TREE_H
#define INC_AA_TREE_H

class cAATree
{
    public:
                // Format for each node in the tree
                struct cNode
                {
                              // our data
                              unsigned int count;
                              std::string  key;

                              // data for the tree algorithm
                              cNode* Left;
                              cNode* Right;
                              cNode* Parent;
                              int    level;
                };

                // Constructors
                cAATree();
               ~cAATree();
                
                // Public functions
                int          Lookup(const std::string &);
                void         Print();
                unsigned int TotalNodes();

    private:
                // Private functions
                void   Skew(cNode*); // Right rotation
                bool   Split(cNode*); // Conditional left rotation
                void   Rebalance(cNode*); // Rebalance the tree from new node
                
                cNode* Insert(cNode*,cNode*); // Recursive insertion
                void   PrintNode(cNode*); // Recursive printing
                unsigned int CountNode(cNode*); // Recursive counting
                
                // Private data
                cNode* Root; // The start node of the tree
};

#endif // INC_AA_TREE_H