// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): SUNY Stony Brook students

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#ifndef RedBlackTree_h
#define RedBlackTree_h

#include <iostream.h>
#include <LINK/basic/Container.h>
#include <LINK/basic/Iterator.h>

enum Color { _BLACK, _RED} ;

template <class Key, class Item> class RedBlackTree;


template <class Key, class Item>
class RedBlackTreeNode: public ContainerNode {
    friend class RedBlackTree<Key,Item>;
public:
    RedBlackTreeNode(): key(0), item(0), left(0),
                        right(0), parent(0), color(_BLACK) { }
    RedBlackTreeNode(Key key, Item item): 
                        key(key), item(item), left(0),
                        right(0), parent(0), color(_BLACK) { }
    virtual ~RedBlackTreeNode() { } 
    //Item   info()   {return item;}
    //Key    key()    {return key;}
   // Color  color()  {return color;}

//private:
    RedBlackTreeNode<Key,Item>*        left; //left child
    RedBlackTreeNode<Key,Item>*        right;//right child
    RedBlackTreeNode<Key,Item>*        parent; //parent
    Key                                key;  //keys 
    Item                               item; //information in this node
    Color                              color; //red or black
};


template <class Key, class Item> 
class RedBlackTree: public Dictionary<Key,Item> {
//  friend ostream&  operator<<(ostream& s, RedBlackTree<Key,Item>& tree);
//  friend istream&  operator>>(istream& s, RedBlackTree<Key,Item>& tree);

public:
    RedBlackTree();
    virtual ~RedBlackTree();

    RedBlackTree<Key, Item>& 
                        operator=(const RedBlackTree<Key, Item>& tree);
    int                 size() const    { return _count; 		}
    int                 height() const;
    int                 bheight() const;
    Bool                emptyQ() const  { return _count ? FALSE : TRUE; }
    Bool                fullQ() const   { return FALSE; 		}
    Bool                memberQ(const Item& e) const;
    Bool                sortedQ() const { return TRUE;			}
    DataType            type() const    { return REDBLACKTREE; 		}
    ContainerNode*      insert(Key passed_key, Item passed_item);
    void                remove(RedBlackTreeNode<Key,Item>* passed_node);
    void                remove(Item passed_item);

    RedBlackTreeNode<Key,Item>* 
                        search(const Key& passed_key) const;
    RedBlackTreeNode<Key,Item>* 
                        searchItem(const Item& passed_item) const;
    RedBlackTreeNode<Key,Item>* 
                        getNode(int index) const;
    RedBlackTreeNode<Key,Item>* 
                        successor(RedBlackTreeNode<Key,Item>* x) const;
    RedBlackTreeNode<Key,Item>* 
                        predecessor(RedBlackTreeNode<Key,Item>* x) const;    


    void                inorderWalk(ostream& os) const;
    void                preorderWalk(ostream& os) const;
    void                postorderWalk(ostream& os) const;
 
    void                clear();
    ostream&            print(ostream& os);
    ContainerNode*      minimum() const;
    Item                min() const  { return info(minimum()); }
    ContainerNode*      maximum() const;
    Item                max() const  { return info(minimum()); }
    Item                extractMin();
    Item                extractMax();
    Item                get() { return extractMin();}
    void                changeKey(RedBlackTreeNode<Key,Item>* node, Key k);
    void                merge(RedBlackTree<Key, Item>& tree);
    void                scramble();
    ostream&                display(ostream& os) const;
 
private:
    int                 iterate(Iterator<Item>& i, Item& item) const;

    int _count;
    RedBlackTreeNode<Key,Item>* _root;
    RedBlackTreeNode<Key,Item>* NIL;
    int treeHeight(RedBlackTreeNode<Key,Item>* x) const;
    int treeBHeight(RedBlackTreeNode<Key,Item>* x) const;
    RedBlackTreeNode<Key,Item>* 
         treeMinimum(RedBlackTreeNode<Key,Item>* x) const;
    RedBlackTreeNode<Key,Item>*
         treeMaximum(RedBlackTreeNode<Key,Item>* x) const;
    RedBlackTreeNode<Key,Item>*
         treeSearch(RedBlackTreeNode<Key,Item>* x, const Key& k) const;
    RedBlackTreeNode<Key,Item>*
         treeSearchItem(RedBlackTreeNode<Key,Item>* x, const Item& item) const;
    void treeInsert(RedBlackTreeNode<Key,Item>* node);
    void treeKill(RedBlackTreeNode<Key,Item>* x);
    void inorderTreeWalk(ostream& os, RedBlackTreeNode<Key,Item>* x) const;
    void preorderTreeWalk(ostream& os, RedBlackTreeNode<Key,Item>* x) const; 
    void postorderTreeWalk(ostream& os, RedBlackTreeNode<Key,Item>* x) const;  
    void treeIterate(RedBlackTreeNode<Key,Item>* x,
                     RedBlackTreeNode<Key,Item>*& node,
                     int& index) const;
    void       leftRotate(RedBlackTreeNode<Key,Item>* x);
    void       rightRotate(RedBlackTreeNode<Key,Item>* x);
    void       removeFixup(RedBlackTreeNode<Key,Item>* x);
};

#ifdef DEFINE_TEMPLATE
#include <LINK/basic/RedBlackTree.cc>
#endif


#endif