/** @file  RedBlackTree.h
    @brief M.A. Weiss (1999) implementation of red-black search trees.

    Mark Allen Weiss, 1999.
    <I>Data Structures and Algorithm Analysis in C++, 2/e.</I>
    Addison-Wesley, ISBN 0-201-36122-1.
*/
        #ifndef RED_BLACK_TREE_H_
        #define RED_BLACK_TREE_H_

        #include "dsexceptions.h"
        #include <iostream>       // For NULL

        // Node and forward declaration because g++ does
        // not understand nested classes.
        template <class Comparable>
        class RedBlackTree;

        /**
         * Implements a Red-Black search tree node.
         * Note that all "matching" is based on the compares method.
         * @author Mark Allen Weiss (http://www.cs.fiu.edu/~weiss/)
         */
        template <class Comparable>
        class RedBlackNode
        {
            Comparable    element;  /**< element to store in a node */
            RedBlackNode *left;     /**< RedBlackNode pointer to left subtree */
            RedBlackNode *right;    /**< RedBlackNode pointer to right subtree */
            int           color;    /**< internal color information */

            /**
             * Construct a node.
             * @param theElement item to store in the node
             * @param lt RedBlackNode pointer to left subtree
             * @param rt RedBlackNode pointer to right subtree
             * @param c initial color information for the node (default is RedBlackTree<Comparable>::BLACK)
             */
            // c = 1 should be c = RedBlackTree<Comparable>::BLACK
            // But Visual 5.0 does not comprehend it.
            RedBlackNode( const Comparable & theElement = Comparable( ),
                              RedBlackNode *lt = NULL, RedBlackNode *rt = NULL,
                              int c = 1 )
              : element( theElement ), left( lt ), right( rt ), color( c ) { }
            friend class RedBlackTree<Comparable>;
        };

        // Red-black tree class
        //
        // CONSTRUCTION: with negative infinity object also
        //               used to signal failed finds
        //
        // ******************PUBLIC OPERATIONS*********************
        // void insert( x )       --> Insert x
        // void remove( x )       --> Remove x (unimplemented)
        // Comparable find( x )   --> Return item that matches x
        // Comparable findMin( )  --> Return smallest item
        // Comparable findMax( )  --> Return largest item
        // boolean isEmpty( )     --> Return true if empty; else false
        // void makeEmpty( )      --> Remove all items
        // void printTree( )      --> Print tree in sorted order

        /**
         * Implements a Red-Black search tree.
         * Note that all "matching" is based on the compares method.
         * @author Mark Allen Weiss (http://www.cs.fiu.edu/~weiss/)
         */
        template <class Comparable>
        class RedBlackTree
        {
          public:
            /**
             * Construct the tree.
             * @param negInf "negative infinity" indicator
             */
            explicit RedBlackTree( const Comparable & negInf );
            /**
             * Copy constructor.
             * @param rhs RedBlackTree object to copy from
             */
            RedBlackTree( const RedBlackTree & rhs );
            /**
             * Destructor for the tree.
             */
            ~RedBlackTree( );

            /**
             * Find the smallest item in the tree.
             * Return smallest item or ITEM_NOT_FOUND if empty.
             */
            const Comparable & findMin( ) const;
            /**
             * Find the largest item in the tree.
             * Return the largest item of ITEM_NOT_FOUND if empty.
             */
            const Comparable & findMax( ) const;
            /**
             * Find item x in the tree.
             * @param x item to look for
             * @return the matching item or ITEM_NOT_FOUND if not found.
             */
            const Comparable & find( const Comparable & x ) const;
            /**
             * Test if the tree is logically empty.
             * @return true if empty, false otherwise.
             */
            bool isEmpty( ) const;
            /**
             * Print the AVL tree contents in sorted order.
             */
            void printTree( ) const;

            /**
             * Make the tree logically empty.
             */
            void makeEmpty( );
            /**
             * Insert x into the tree; duplicates are ignored.
             * @param x item to be inserted
             */
            void insert( const Comparable & x );
            /**
             * Remove x from the tree. Nothing is done if x is not found.
             * @param x item to be removed
             */
            void remove( const Comparable & x );

            /**
             * An emun to define valid RedBlackNode node colors
             */
            enum { 
                   RED,   /**< enum node color RED */
                   BLACK  /**< enum node color BLACK */
            };

            /**
             * Deep copy.
             */
            const RedBlackTree & operator=( const RedBlackTree & rhs );

          private:
            RedBlackNode<Comparable> *header;   // The tree header (contains negInf)
            const Comparable ITEM_NOT_FOUND;
            RedBlackNode<Comparable> *nullNode;

                // Used in insert routine and its helpers (logically static)
            RedBlackNode<Comparable> *current;
            RedBlackNode<Comparable> *parent;
            RedBlackNode<Comparable> *grand;
            RedBlackNode<Comparable> *great;

                // Usual recursive stuff
            void reclaimMemory( RedBlackNode<Comparable> *t ) const;
            void printTree( RedBlackNode<Comparable> *t ) const;
            RedBlackNode<Comparable> * clone( RedBlackNode<Comparable> * t ) const;

                // Red-black tree manipulations
            void handleReorient( const Comparable & item );
            RedBlackNode<Comparable> * rotate( const Comparable & item,
                                        RedBlackNode<Comparable> *parent ) const;
            void rotateWithLeftChild( RedBlackNode<Comparable> * & k2 ) const;
            void rotateWithRightChild( RedBlackNode<Comparable> * & k1 ) const;
        };

        #include "RedBlackTree.cpp"
        #endif