#ifndef RED_BLACK_TREE_H
#define RED_BLACK_TREE_H

#include <iostream> 
using namespace std;

// Red-black tree class


template <typename Comparable>
class RedBlackTree
{
  public:
    /**
     * Construct the tree.
     * negInf is a value less than or equal to all others.
     */
    explicit RedBlackTree( const Comparable & negInf );

    RedBlackTree( const RedBlackTree & rhs );

    RedBlackTree( RedBlackTree && rhs );

    ~RedBlackTree( );
    
    RedBlackTree & operator=( const RedBlackTree & rhs );

    bool contains( const Comparable & x ) const;

    bool isEmpty( ) const;

    void printTree( ) const;

    void makeEmpty( );

    void insert( const Comparable & x );

    void remove( const Comparable & x );

  private:
    enum { RED, BLACK };
    
    struct RedBlackNode
    {
        Comparable    element;
        RedBlackNode *left;
        RedBlackNode *right;
        int           color;

        RedBlackNode( const Comparable & theElement = Comparable{ },
                            RedBlackNode *lt = nullptr, RedBlackNode *rt = nullptr,
                            int c = BLACK )
          : element{ theElement }, left{ lt }, right{ rt }, color{ c } { }
        
    }

    RedBlackNode *header;   // The tree header (contains negInf)
    RedBlackNode *nullNode;

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

        // Usual recursive stuff
    void reclaimMemory( RedBlackNode *t );

    void printTree( RedBlackNode *t ) const;

    RedBlackNode * clone( RedBlackNode * t ) const;

    void handleReorient( const Comparable & item );

    RedBlackNode * rotate( const Comparable & item, RedBlackNode *theParent );

    void rotateWithLeftChild( RedBlackNode * & k2 );

    void rotateWithRightChild( RedBlackNode * & k1 );
};

#endif