#ifndef BST_H
#define BST_H
/** Binary Search Tree - Interface
 *
 *  Dale Haverstock
 *  2002-04
 */

#include <iostream>
#include <string>
#include <utility>
#include <vector>

typedef int KeyType;
typedef int ValueType;

struct BSTnode;
class  BSTiterator;

class BST
{
  public:
    typedef BSTiterator iterator;

    BST() : _root(0) {}

    BSTnode*    find(KeyType);
    BSTnode     min();
    bool        empty();
    BSTnode&    insert(KeyType, ValueType);
    BSTnode&    getNode(KeyType);
    void        delete_node(KeyType);
    int         size();

    BSTiterator begin();
    BSTiterator end();
    void        showTree1();
    void        showTree2();

  private:
    std::vector<std::pair<KeyType, ValueType>* > data_in_vector();
    int                                          count(BSTnode*);

    BSTnode* _root;
                                           // utility functions
    void       showTree1(BSTnode*, int, char);
};

//============================================================================
class  BSTiterator
{
    friend class list;
 
  public:
    BSTiterator(BSTnode* cur);                        // constructor
 
    BSTiterator&  operator++();                       // pre increment
    BSTiterator   operator++(int);                    // post increment
    ValueType&    operator*();                        // dereference
    bool          operator!=(BSTiterator) const;      // not equals
 
    BSTnode*      get_address()             const;    // debugging
  private:
    BSTnode*      _cur;

    BSTnode*      successor(BSTnode*);
};

//============================================================================
                                                        // BSTnode
struct BSTnode
{
    BSTnode(BSTnode* left, BSTnode* right,
                 BSTnode* parent, std::pair<KeyType, ValueType> item)
        : _left(left), _right(right), _parent(parent), _item(item) {}

    KeyType   getKey()                 { return _item.first;   }
    ValueType getValue()               { return _item.second;  }
 // void      setKey(KeyType key)      { _item.first = key;    }
 // void      setValue(ValueType value){ _item.second = value; }
 // bool operator<(const BSTnode& rhs) { return _item.second < rhs._item.second;}

    BSTnode*                      _left;
    BSTnode*                      _right;
    BSTnode*                      _parent;
    std::pair<KeyType, ValueType> _item;
};

std::ostream& operator<< (std::ostream&, const BSTnode&);     // helper

#endif