/* [tbstree.h] Class definitions for Binary Search Trees
   This tree will work with any data type substituted for T
     as long as that data type has:
           assignment/copy constructor
           ==, <, > and << operators defined for it


--*/


/* [tbstree.h] Class definitions for Binary Search Trees
   This tree will work with any data type substituted for TData
     as long as that data type has:
           assignment/copy constructor
           ==, <, > and << operators defined for it

---*/

#ifndef _TPL_BSTREE_H
#define _TPL_BSTREE_H

template <class TData>
class BSearchTree {
 public:

   class TNode {
     public:
     TData   d;
     TNode * lp,
           * rp;
     TNode(void) {
        lp = rp = NULL;
        }
     TNode(const TData & x) {
        lp = rp = NULL;
        d = x;
        }
     };

   typedef TNode * TNp;     // a type name for general use

   BSearchTree(void){
    // constructor automatically called by new
      root = NULL;
      }
   ~BSearchTree(void){
      if (root!=NULL)
         rdel(root);
      root = NULL;
      }
   void clrtree(void){
    // removes all nodes from tree
     if (root != NULL)
         rdel(root);
      root = NULL;
      }

   TNp current(void) {
    // returns value of cur pointer
      return cur;
      }

   TNp parent(void) {
    // returns value of parent (prior)  pointer
      return pri;
      }

   bool search(const TData & x) {
     // searches tree for x.  Leaves pri and cur set.
     // Returns true if found and false if not found
     pri = NULL;
     cur = root;
     while (cur != NULL) {
       if (x == cur->d)
          return true;
       pri = cur;
       if (x < cur->d)
          cur = cur->lp;
         else
          cur = cur->rp;
       }
     return false;
     }

   bool insert(const TData & x) {
     // inserts x into the tree,
     //   returns true if done, false if there is problem
     int
       found = search(x);
     if (found)
         return false;     // No Duplicates allowed
     cur = new TNode(x);   // use cur since we know it's NULL from search
     if (cur == NULL)
        return false;      // not enough memory
     if (pri==NULL) {
        root = cur;
        return true;       // First Node on Tree
        }
     if (x<pri->d)
        pri->lp = cur;
       else
        pri->rp = cur;
     return true;
     }

private:
   void linkup(TNp nu) {
    // used by tdelete
     if (pri == NULL) {
        root = nu;
        return;
        }
     if (pri->lp == cur)
       pri->lp = nu;
     if (pri->rp == cur)
       pri->rp = nu;
     }
   void findswap(TNp & npri, TNp & ncur) {
    // used by tdelete
     npri = cur;
     ncur = cur->lp;
     while (ncur->rp != NULL) {
       npri = ncur;
       ncur = ncur->rp;
       }
     }
public:
   bool tdelete(const TData & x) {
     // deletes x from tree.
     // Returns true if deleted, false if not found
     bool
       found = search(x);
     if (!found) return false;
     TNp nc,
         np;
     if (cur->lp != NULL && cur->rp != NULL) {
        findswap(np,nc);
        cur->d = nc->d;
        cur = nc;
        pri = np;
        }
     if (cur->lp != NULL || cur->rp != NULL) {
        if (cur->lp != NULL)
           linkup(cur->lp);
          else
           linkup(cur->rp);
        }
     if (cur->lp == NULL && cur->rp == NULL)
        linkup(NULL);
     delete cur;
     cur = NULL;
     return true;
     }

   void rtprt(TNp cp, ostream & out) {
     // used by operator <<
      if (cp->lp != NULL)
          rtprt(cp->lp,out);
      out << cp->d/* << " | "*/;
      if (cp->rp != NULL)
          rtprt(cp->rp,out);
      }

   void print(ostream & out){
     if (root == NULL)
        cout << "tree is empty ";
       else
        rtprt(root,out);
     cout << endl;
     }

   void rtrav(TNp cp, void (*wrk) (TNp c) ) {
     // used by operator <<
      if (cp->lp != NULL)
          rtrav(cp->lp,wrk);
      (*wrk) (cp);
      if (cp->rp != NULL)
          rtrav(cp->rp,wrk);
      }


   void traverse(void (*wrk) (TNp c) ) {
    // a general traverse function
    //   the argument is a void function that takes
    //        a BinSearchTree<T>::TNp as argument

     if (root == NULL)
        cout << "tree is empty ";
       else
        rtrav(root,wrk);
     cout << endl;
     }

private:
   TNp                      // hidden
     root,                  // root of tree
     cur,                   // cursor pointing to last accessed node
     pri;                   // previous pointer points to
                            //    parent of last accessed node

   void rdel(TNp c) {
     // recursive post order traverse to delete tree
     if (c->lp != NULL)
        rdel(c->lp);
     if (c->rp != NULL)
        rdel(c->rp);
     delete c;
     }

  };

template <class TData>
ostream& operator<<(ostream & out, BSearchTree<TData> & t) {
     t.print(out);
     return out;
     }



#endif