// -----------------------------------------------------------------------
//
// Binary search tree template classes
// File: BinSearchTree/bstree.h
//
// -----------------------------------------------------------------------

#ifndef _BSTREE_H
#define _BSTREE_H

#include <assert.h>
#include "queStack.h"
#include <algo.h>
typedef unsigned int UINT;

// -----------------------------------------------------------------------

// forward declarations

template <class T> class BTree;
template <class T> class BTreeIterator;
template <class T> class PreorderIterator;
template <class T> class InorderIterator;
template <class T> class PostorderIterator;
template <class T> class LevelIterator;

// -----------------------------------------------------------------------

template <class T>
class BTnode
{
  friend class BTree<T>;
  friend class BTreeIterator<T>;
  friend class PreorderIterator<T>;
  friend class InorderIterator<T>;
  friend class PostorderIterator<T>;
  friend class LevelIterator<T>;

  friend ostream& operator<< (ostream&, const BTree<T>&);

  T		data;		// all members
  BTnode<T>	*le;		// are private
  BTnode<T>	*ri;

  // constructors

  BTnode () {}
  BTnode (const T& t, BTnode<T> *l, BTnode<T> *r) : data(t) { le=l; ri=r; }
};

// -----------------------------------------------------------------------

template <class T>
class BTree
{
    friend class BTreeIterator<T>;
    friend class PreorderIterator<T>;
    friend class InorderIterator<T>;
    friend class PostorderIterator<T>;
    friend class LevelIterator<T>;

    BTnode<T>	*LEAF;	// sentinel, LEAF->ri is also the root pointer

    UINT	 size;	// number of nodes
    UINT	 ht;	// height of tree

    // ------------------------------------------------------------------

    typedef BTreeIterator<T> *iterptr;
    list< iterptr > iterlist;

    // ------------------------------------------------------------------

    int		 depth;

    void doEmpty    (BTnode<T>*);	// recursive aux. functions
    void redoHeight (BTnode<T>*, UINT);
    void prePrint   (BTnode<T>*);

  public:

    BTree ();			// constructor
   ~BTree ();			// destructor

    T& operator[] (const BTreeIterator<T>& it)	// return "curr" element
      { return it.curr->data; }			// pointed to by iterator

    void    insert  (const T&);		// insert in sorted tree
    bool remove  (const T&);		// remove first instance

    bool search  (const T&);
    bool isEmpty () { return bool(LEAF->ri==LEAF); }

    UINT    nNodes  () { return size; }
    UINT    height  () { return ht; }

    void makeEmpty ();
    void print     () { prePrint(LEAF->ri); }
};

// -----------------------------------------------------------------------

template <class T>		// Base class for all iterator classes
class BTreeIterator
{
    friend class BTree<T>;

  protected:

    stack_queue<list<BTnode<T>*> > stque;
    BTree<T>		*tree;
    BTnode<T>		*curr;

  public:

    BTreeIterator (BTree<T>&);
    virtual ~BTreeIterator ();

    void reset ();

    bool atEnd () { return bool (curr==tree->LEAF); }

    virtual BTreeIterator<T>& operator++ () = 0;

    operator== (const BTreeIterator<T>& it) { return (curr==it.curr); }
};

// -----------------------------------------------------------------------

template <class T>
class PreorderIterator : public BTreeIterator<T>
{
  public:

    PreorderIterator (BTree<T>& bt) : BTreeIterator<T>(bt) { reset(); }

    BTreeIterator<T>& operator++ ();
};

// -----------------------------------------------------------------------

template <class T>
class InorderIterator : public BTreeIterator<T>
{
  public:

    InorderIterator (BTree<T>& bt) : BTreeIterator<T>(bt) { reset(); }

    BTreeIterator<T>& operator++ ();
};

// -----------------------------------------------------------------------

template <class T>
class PostorderIterator : public BTreeIterator<T>
{
  public:

    PostorderIterator (BTree<T>& bt) : BTreeIterator<T>(bt) { reset(); }

    BTreeIterator<T>& operator++ ();
};

// -----------------------------------------------------------------------

template <class T>
class LevelIterator : public BTreeIterator<T>
{
  public:

    LevelIterator (BTree<T>& bt) : BTreeIterator<T>(bt) { reset(); }

    BTreeIterator<T>& operator++ ();
};

// -----------------------------------------------------------------------

template <class T>
void BTree<T>::doEmpty (BTnode<T> *s)
{
  if (s == LEAF) return;

  doEmpty (s->le);	// recursively deletes each node
  doEmpty (s->ri);	// in a POSTORDER traversal

  delete s;
}

// ----------------------------------------------------------------------

template <class T>
void BTree<T>::redoHeight (BTnode<T> *s, UINT d)
{
  if (s == LEAF) return;

  redoHeight (s->le, d+1);	// recursively re-computes
  redoHeight (s->ri, d+1);	// the height of the tree

  if (d > ht) ht = d;
}

// ----------------------------------------------------------------------

template <class T>			// prints the tree in
void BTree<T>::prePrint (BTnode<T> *s)	// PREORDER
{
  if (s == LEAF) return;

  ++depth;

  cout << depth << "\t" << s->data << "\t--->\t";

  if (s->le == LEAF)
    cout << "<LEAF>" << "\t";
  else
    cout << s->le->data << "\t";

  if (s->ri == LEAF)
    cout << "<LEAF>" << endl;
  else
    cout << s->ri->data << endl;

  prePrint (s->le);
  prePrint (s->ri);

  --depth;
}

// ----------------------------------------------------------------------

template <class T>		// constructor
BTree<T>::BTree ()
{
  LEAF = new BTnode<T>;
  LEAF->le = LEAF;
  LEAF->ri = LEAF;	// "root" pointer
  size = ht = 0;
  depth = -1;
}

// ----------------------------------------------------------------------

template <class T>		// destructor
BTree<T>::~BTree ()
{
  doEmpty (LEAF->ri);

  delete LEAF;

  // reset iterators referring to this tree
  list<iterptr>::iterator p;
  for(p = iterlist.begin(); p != iterlist.end(); p++)
  {
    (*p)->curr = NULL;
    (*p)->tree = NULL;
  }
}

// ----------------------------------------------------------------------

template <class T>			// inserts "tval" into the
void BTree<T>::insert (const T& tval)	// sorted binary tree
{					// LEAF is used as sentinel
  BTnode<T> *p = LEAF;
  BTnode<T> *c = LEAF->ri;
  LEAF->data = tval;
  UINT h = 0;

  while (c != LEAF)
  {
    p = c;
    c = (tval < c->data) ? c->le : c->ri;
    ++h;
  }

  c = new BTnode<T>(tval, LEAF, LEAF);
  assert (c);

  if (tval < p->data)
    p->le = c;
  else
    p->ri = c;

  // reset all iterators

  list<iterptr>::iterator it;
  for (it=iterlist.begin(); it!=iterlist.end(); it++)
    (*it)->reset ();

  ++size;
  if (h > ht) ht = h;	// adjust height
}

// ----------------------------------------------------------------------

template <class T>			  // removes the first instance
bool BTree<T>::remove (const T& tval)  // of "tval"
{
  BTnode<T> *p = LEAF;
  BTnode<T> *c = LEAF->ri;
  LEAF->data = tval;

  while (tval != c->data)
  {
    p = c;
    c = (tval < c->data) ? c->le : c->ri;
  }

  if (c == LEAF) return false;		// not found

  BTnode<T> *t = c;

  if (t->ri == LEAF)			// case #1
  {
    c = c->le;
  }
  else if (t->ri->le == LEAF)		// case #2
  {
    c = c->ri;
    c->le = t->le;
  }
  else					// case #3
  {
    BTnode<T> *q = c->ri;

    while (q->le->le != LEAF)
      q = q->le;

    c = q->le;
    q->le = c->ri;
    c->le = t->le;
    c->ri = t->ri;
  }

  if (tval < p->data)
    p->le = c;
  else
    p->ri = c;

  delete t;

  // reset all iterators

  list<iterptr>::iterator it;
  for (it=iterlist.begin(); it!=iterlist.end(); it++)
    (*it)->reset ();

  ht = 0;
  redoHeight (LEAF->ri, 0);
  --size;

  return true;
}

// ----------------------------------------------------------------------

template <class T>
bool BTree<T>::search (const T& tval)
{
  BTnode<T> *p = LEAF->ri;
  LEAF->data = tval;

  while (tval != p->data)
    p = (tval < p->data) ? p->le : p->ri;

  if (p == LEAF) return false;

  return true;
}

// ----------------------------------------------------------------------

template <class T>
void BTree<T>::makeEmpty ()
{
  doEmpty (LEAF->ri);

  // reset all iterators

  list<iterptr>::iterator p;
  for (p=iterlist.begin(); p!=iterlist.end(); p++)
  {
    (*p)->stque.makeEmpty();
    (*p)->curr = LEAF;
  }

  size = 0;
  ht = 0;
}

// ----------------------------------------------------------------------

template <class T>
BTreeIterator<T>::BTreeIterator (BTree<T>& t) : tree(&t)
{
  (t.iterlist).push_front(this);
}

// ----------------------------------------------------------------------

template <class T>
BTreeIterator<T>::~BTreeIterator ()
{
  stque.makeEmpty ();

  // find iterator record

  list< BTree<T>::iterptr >::iterator p = find(tree->iterlist.begin(),
                                               tree->iterlist.end(),
                                               this);
  tree->iterlist.erase(p);

}

// ----------------------------------------------------------------------

template <class T>
void BTreeIterator<T>::reset ()
{
  curr = tree->LEAF;
  stque.makeEmpty ();
  ++(*this); // operator++ ();
}

// ----------------------------------------------------------------------

template <class T>
BTreeIterator<T>& PreorderIterator<T>::operator++ ()
{
  if (curr->ri != tree->LEAF) stque.push (curr->ri);
  if (curr->le != tree->LEAF) stque.push (curr->le);

  if (stque.isEmpty ())
    curr = tree->LEAF;
  else
    curr = stque.pop ();

  return *this;
}

// ----------------------------------------------------------------------

template <class T>
BTreeIterator<T>& InorderIterator<T>::operator++ ()
{
  BTnode<T> *p = curr->ri;
  while (p != tree->LEAF)
  {
    stque.push (p);
    p=p->le;
  }

  if (stque.isEmpty ())
    curr = tree->LEAF;
  else
    curr = stque.pop ();

  return *this;
}

// ----------------------------------------------------------------------

template <class T>
BTreeIterator<T>& PostorderIterator<T>::operator++ ()
{
  BTnode<T> *p = tree->LEAF;

  if (!stque.isEmpty ())
    p = stque.pop ();

  if (p->ri!=tree->LEAF && curr!=p->ri)
  {
    stque.push (p);
    p = p->ri;

    while (p!=tree->LEAF)
    {
      stque.push (p);

      if (p->le!=tree->LEAF)
        p = p->le;
      else
        p = p->ri;
    }
    p = stque.pop ();
  }

  curr = p;

  return *this;
}

// ----------------------------------------------------------------------

template <class T>
BTreeIterator<T>& LevelIterator<T>::operator++ ()
{
  if (curr->le != tree->LEAF) stque.append (curr->le);
  if (curr->ri != tree->LEAF) stque.append (curr->ri);

  if (stque.isEmpty ())
    curr = tree->LEAF;
  else
    curr = stque.pop ();

  return *this;
}

// ----------------------------------------------------------------------

#endif