// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): ??

// 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 BinarySearchTree_h
#define BinarySearchTree_h

#include <LINK/basic/Container.h>

template <class Key, class Item> class BinarySearchTree;


template <class Key, class Item>
class BinarySearchTreeNode: public ContainerNode {
    friend class BinarySearchTree<Key, Item>;
public:
    BinarySearchTreeNode() : key(0), item(0), left(0), 
                             right(0), parent(0) { }
    BinarySearchTreeNode(Key key, Item item) :
                             key(key), item(item), left(0),
                             right(0), parent(0) { } 
   // Item   info()   {return item;}
    //Key    key()    {return key;}
    //int    height() {return height;}
    
//private:
    BinarySearchTreeNode<Key, Item>*   left; //left child 
    BinarySearchTreeNode<Key, Item>*   right;//right child
    BinarySearchTreeNode<Key, Item>*   parent; //parent
    Key                                key;  //keys
    Item                               item; //information in this node
   // int                                height;
};


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

public:
    BinarySearchTree();
    virtual ~BinarySearchTree();
    
    BinarySearchTree<Key, Item>&   
                        operator=(const BinarySearchTree<Key, Item>& tree);
    int                 size() const    { return _count; 		}
    int                 height() 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 BINARYSEARCHTREE;	}
    ContainerNode*      insert(Key passed_key, Item passed_item);
    void                remove(BinarySearchTreeNode<Key,Item>* passed_node);
    void                remove(Item passed_item);
    BinarySearchTreeNode<Key,Item>*  search(const Key& passed_key) const;
    BinarySearchTreeNode<Key,Item>*  searchItem(const Item& passed_item) const;
    BinarySearchTreeNode<Key,Item>*  getNode(int index) const;
    BinarySearchTreeNode<Key,Item>*  
               successor(BinarySearchTreeNode<Key,Item>* x) const;
    BinarySearchTreeNode<Key,Item>* 
               predecessor(BinarySearchTreeNode<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(BinarySearchTreeNode<Key,Item>* node, Key k); 
    void                merge(BinarySearchTree<Key,Item> &T);
    void                scramble() ;
    ostream&                display(ostream& os) const;

private:
    int                 iterate(Iterator<Item>& i, Item& item) const;
    int _count;
    BinarySearchTreeNode<Key,Item>* _root;
    int  treeHeight(BinarySearchTreeNode<Key,Item>* x) const;
    BinarySearchTreeNode<Key,Item>* 
         treeMinimum(BinarySearchTreeNode<Key,Item>* x) const;
    BinarySearchTreeNode<Key,Item>* 
         treeMaximum(BinarySearchTreeNode<Key,Item>* x) const;
    BinarySearchTreeNode<Key,Item>*
         treeSearch(BinarySearchTreeNode<Key,Item>* x, const Key& k) const;
    BinarySearchTreeNode<Key,Item>*
         treeSearchItem(BinarySearchTreeNode<Key,Item>* x, 
                        const Item& item) const;
    void treeKill(BinarySearchTreeNode<Key,Item>* x);
    void inorderTreeWalk(ostream&os, BinarySearchTreeNode<Key,Item>* x) const;
    void preorderTreeWalk(ostream&os, BinarySearchTreeNode<Key,Item>* x) const;
    void postorderTreeWalk(ostream&os, BinarySearchTreeNode<Key,Item>* x) const;
    void treeIterate(BinarySearchTreeNode<Key,Item>* x,
                     BinarySearchTreeNode<Key,Item>*& node,
                     int& index) const; 
};


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


#endif