// Purpose.  Iterator design pattern lab
//
// Problem.  The BST class can traverse itself, but, the client of the BST
// cannot stop the traversal at will and interject application-specific
// functionality.  An Iterator class is a "partner" to a "container-like"
// class that provides the level of access and control that a client might
// need, while still maintaining the encapsulation of the original class.
// John Lakos has asserted that the interface of a "container-like" class
// is not "necessary and sufficient" until an Iterator capability is provided.
//
// Assignment.
// o Declare a class Iterator
// o The public interface of class Iterator should consist of -
//      Iterator( BST* );
//      void first();
//      void next();
//      int isDone();
//      Node& currentItem();
// o Make class Iterator a friend of class BST
// o Add the following method to class BST
//      Iterator* createIterator();
// o Add the following to the end of main() -
//      create an Iterator object
//      in a for loop, traverse the BST by using Iterator's first(), next(),
//         isDone(), and currentItem() methods
//      in a second for loop, traverse the BST again
//      deallocate the Iterator object
// o The BST::createIterator() implementation needs to create and return an
//   "appropriately initialized" instance of class Iterator
// o The school solution private data members of class Iterator are:
//      BST*    bst;
//      Node**  list;
//      int     nextNode;
// o A strategy for the Iterator::first() implementation is -
//      create a dynamic array of type Node* whose size is equal to the number
//         of nodes in the BST
//      traverse the BST, copying each Node* into the dynamic array (the array
//         will now "mirror" the BST)
//      initialize a "next array element" data member to 0
// o Traversing the BST to initialize the dynamic array could be implemented
//   by defining a recursive function that looks a lot like the current
//   BST::traverse(Node*) method.  The school solution implementation defines
//   the following private utility method -
//      void buildList( Node* current ) {
//         if (current->left != 0) buildList( current->left );
//         list[nextNode++] = current;
//         if (current->right != 0) buildList( current->right );
//      }
// o Iterator::next() simply increments the "next array element" data member
// o Iterator::currentItem() uses the "next array element" data member to
//   index into the dynamic array and then returns the dereferenced pointer
// o Iterator::isDone() needs an implementation
// o The dynamic array created in Iterator::first() needs to be deallocated if
//   a second call to Iterator::first() is made

#include <iostream.h>
#include <stdlib.h>
#include <time.h>

struct Node {
   int value;  Node* left;  Node* right;
   Node() { left = right = 0; }
   friend ostream& operator<< ( ostream& os, Node& n ) { return os << n.value; }
};

class BST {
private:
   Node*  root;
   int    size;
public:
   BST() {
      root = 0;
   }
   void add( int in ) {
      if (root == 0) {
         root = new Node;
         root->value = in;
         size = 1;
         return;
      }
      add( in, root );
   }
   void traverse() { traverse( root ); }
private:
   void add( int in, Node* current ) {
      if (in < current->value)
         if (current->left == 0) {
            current->left = new Node();
            current->left->value = in;
            size++;
         }
         else add( in, current->left );
      else
         if (current->right == 0) {
            current->right = new Node();
            current->right->value = in;
            size++;
         }
         else add( in, current->right );
   }
   void traverse( Node* current ) {
      if (current->left != 0) traverse( current->left );
      cout << current->value << "  ";
      if (current->right != 0) traverse( current->right );
   }
};

void main( void ) {
   BST     bst;
   time_t  t;
   srand((unsigned) time(&t));

   cout << "original:  ";
   for (int i=0, val; i < 15; i++) {
      val = rand() % 49 + 1;
      cout << val << "  ";
      bst.add( val );
   }
   cout << "\ntraverse:  ";
   bst.traverse();
   cout << endl;
}

// original:  11  43  7  2  22  3  25  40  41  36  32  11  24  11  37
// traverse:  2  3  7  11  11  11  22  24  25  32  36  37  40  41  43
// Iterator:  2  3  7  11  11  11  22  24  25  32  36  37  40  41  43
// Iterator:  2  3  7  11  11  11  22  24  25  32  36  37  40  41  43