// Purpose.  Iterator design pattern

// Take traversal-of-a-collection functionality out of the collection and
// promote it to "full object status".  This simplifies the collection, allows
// many traversals to be active simultaneously, and decouples collection algo-
// rithms from collection data structures.

// "Every 'container-like' class must have an iterator." [Lakos]  It may seem
// like a violation of encapsulation for a Stack class to allow its users to
// access its contents directly, but John Lakos' argument is that the designer
// of a class inevitably leaves something out.  Later, when users need addi-
// tional functionality, if an iterator was originally provided, they can add
// functionality with "open for extension, closed for modification".  Without
// an iterator, their only recourse is to invasively customize production 
// code.  Below, the orginal Stack class did not include an equality operator,
// but it did include an iterator.  As a result, the equality operator could
// be readily retrofitted.

// 1. Design an "iterator" class for the "container" class
// 2. Add a createIterator() member to the container class
// 3. Clients ask the container object to create an iterator object
// 4. Clients use the first(), isDone(), next(), and currentItem() protocol

#include <iostream>
using namespace std;

class Stack {
   int items[10];
   int sp;
public:
   friend class StackIter;
   Stack()             { sp = -1; }
   void push( int in ) { items[++sp] = in; }
   int  pop()          { return items[sp--]; }
   bool isEmpty()      { return (sp == -1); }
   StackIter* createIterator() const;      // 2. Add a createIterator() member
};

class StackIter {                          // 1. Design an "iterator" class
   const Stack* stk;
   int index;
public:
   StackIter( const Stack* s ) { stk = s; }
   void first()                { index = 0; }
   void next()                 { index++; }
   bool isDone()               { return index == stk->sp+1; }
   int  currentItem()          { return stk->items[index]; }
};

StackIter* Stack::createIterator() const { return new StackIter( this ); }

bool operator==( const Stack& l, const Stack& r ) {
   // 3. Clients ask the container object to create an iterator object
   StackIter* itl = l.createIterator();
   StackIter* itr = r.createIterator();
   // 4. Clients use the first(), isDone(), next(), and currentItem() protocol
   for (itl->first(), itr->first(); ! itl->isDone(); itl->next(), itr->next())
      if (itl->currentItem() != itr->currentItem()) break;
   bool ans = itl->isDone() && itr->isDone();
   delete itl;   delete itr;
   return ans;
}

void main( void ) {
   Stack  s1;
   for (int i=1; i < 5; i++) s1.push(i);
   Stack  s2( s1 ), s3( s1 ), s4( s1 ), s5( s1 );
   s3.pop();       s5.pop();
   s4.push( 2 );   s5.push( 9 );
   cout << "1 == 2 is "<< (s1 == s2) << endl;
   cout << "1 == 3 is "<< (s1 == s3) << endl;
   cout << "1 == 4 is "<< (s1 == s4) << endl;
   cout << "1 == 5 is "<< (s1 == s5) << endl;
}

// 1 == 2 is 1
// 1 == 3 is 0
// 1 == 4 is 0
// 1 == 5 is 0




// Purpose.  Iterator using operators instead of methods
//
// Discussion.  John Lakos suggests the GOF and STL iterator interfaces are:
// error-prone (possibility of misspelling method names), clumsy, and require
// too much typing.  This design uses nothing but "intuitive" operators.
// Notice also that no createIterator() was specified.  The user creates these
// iterators as local variables, and no clean-up is necessary.

#include <iostream>
using namespace std;

class Stack {
   int items[10];
   int sp;
public:
   friend class StackIter;
   Stack()             { sp = -1; }
   void push( int in ) { items[++sp] = in; }
   int  pop()          { return items[sp--]; }
   bool isEmpty()      { return (sp == -1); }
};

class StackIter {
   const Stack& stk;
   int index;
public:
   StackIter( const Stack& s ) : stk( s ) { index = 0; }
   void operator++() { index++; }
   bool operator()() { return index != stk.sp+1; }
   int  operator*()  { return stk.items[index]; }
};

bool operator==( const Stack& l, const Stack& r ) {
   StackIter itl( l ), itr( r );
   for ( ; itl(); ++itl, ++itr)
      if (*itl != *itr) break;
   return ! itl() && ! itr();
}

void main( void ) {
   Stack  s1;   int  i;
   for (i=1; i < 5; i++) s1.push(i);
   Stack  s2( s1 ), s3( s1 ), s4( s1 ), s5( s1 );
   s3.pop();       s5.pop();
   s4.push( 2 );   s5.push( 9 );
   cout << "1 == 2 is "<< (s1 == s2) << endl;
   cout << "1 == 3 is "<< (s1 == s3) << endl;
   cout << "1 == 4 is "<< (s1 == s4) << endl;
   cout << "1 == 5 is "<< (s1 == s5) << endl;
}

// 1 == 2 is 1
// 1 == 3 is 0
// 1 == 4 is 0
// 1 == 5 is 0




// Purpose.  Iterator using the Java interface
//
// Discussion.  Java's standard collection classes have a much leaner inter-
// face.  Their next() methods combine the next() and currentItem() methods.

#include <iostream>
using namespace std;

class Stack {
   int items[10];
   int sp;
public:
   friend class StackIter;
   Stack()             { sp = -1; }
   void push( int in ) { items[++sp] = in; }
   int  pop()          { return items[sp--]; }
   bool isEmpty()      { return (sp == -1); }
   StackIter* iterator() const;
};

class StackIter {
   const Stack* stk;
   int index;
public:
   StackIter( const Stack* s ) { stk = s;  index = 0; }
   int  next()                 { return stk->items[index++]; }
   bool hasNext()              { return index != stk->sp+1; }
};

StackIter* Stack::iterator() const { return new StackIter( this ); }

bool operator==( const Stack& l, const Stack& r ) {
   StackIter* itl = l.iterator();
   StackIter* itr = r.iterator();
   while (itl->hasNext())
      if (itl->next() != itr->next()) {
         delete itl;   delete itr;
         return false;
      }
   bool ans = (! itl->hasNext()) && ( ! itr->hasNext());
   delete itl;   delete itr;
   return ans;
}

void main( void ) {
   Stack  s1;   int  i;
   for (i=1; i < 5; i++) s1.push(i);
   Stack  s2( s1 ), s3( s1 ), s4( s1 ), s5( s1 );
   s3.pop();       s5.pop();
   s4.push( 2 );   s5.push( 9 );
   cout << "1 == 2 is "<< (s1 == s2) << endl;
   cout << "1 == 3 is "<< (s1 == s3) << endl;
   cout << "1 == 4 is "<< (s1 == s4) << endl;
   cout << "1 == 5 is "<< (s1 == s5) << endl;
}

// 1 == 2 is 1
// 1 == 3 is 0
// 1 == 4 is 0
// 1 == 5 is 0




// Purpose.  Simple implementation of an Iterator (uses parallel dynamic array)
//
// Discussion.  Instead of having to write an involved stack-like solution to
// handle step-wise recursive descent, use a little extra memory to maintain a
// sequential representation of the original hierarchical data.  The replicated
// data are not Node objects, they are lightweight pointers.  The array is
// initialized using a recursive method similar to traverse(Node*).

#include <iostream>
#include <ctime>
using namespace std;

class BST {
   friend class Iterator;
   struct Node {
      Node( int );
      int value;
      Node* left;
      Node* rite;
   };
   Node* root;
   int   size;
   void add( Node**, int );
   void traverse( Node* );
public:
   BST() { root = 0;  size = 0; }
   void add( int );
   void traverse();
   Iterator* createIterator() const;
};

class Iterator {
   const BST* tree;
   BST::Node** array;
   int index;
   void populateArray( BST::Node* current ) {
      if (current->left) populateArray( current->left );
      array[index++] = current;
      if (current->rite) populateArray( current->rite );
   }
public:
   Iterator( const BST* s ) {
      tree = s;
      array = 0;  index = 0;
   }
   ~Iterator() { delete [] array; }
   void first() {
      delete [] array;
      array = new BST::Node*[tree->size];
      index = 0;
      populateArray( tree->root );
      index = 0;
   }
   void next()              { index++; }
   bool isDone()            { return index == tree->size; }
   BST::Node* currentItem() { return array[index]; }
};

void main( void ) {
   srand( time( 0 ) );
   BST  tree;
   for (int i=0; i < 20; i++) tree.add( rand() % 20 + 1 );
   cout << "traverse: ";
   tree.traverse();
   cout << "\niterator: ";
   Iterator* it = tree.createIterator();
   for (it->first(); ! it->isDone(); it->next())
      cout << it->currentItem()->value << ' ';
   cout << "\niterator: ";
   for (it->first(); ! it->isDone(); it->next())
      cout << it->currentItem()->value << ' ';
   cout << '\n';
}

// traverse: 1 2 3 7 8 9 9 10 11 11 13 14 14 14 15 17 18 19 19 20
// iterator: 1 2 3 7 8 9 9 10 11 11 13 14 14 14 15 17 18 19 19 20
// iterator: 1 2 3 7 8 9 9 10 11 11 13 14 14 14 15 17 18 19 19 20


BST::Node::Node( int v ) { value = v;  left = rite = 0; }

void BST::add( Node** n, int v ) {
   if ( ! *n)                 { *n = new Node( v );  size++; }
   else if (v <= (*n)->value) add( &((*n)->left), v );
   else                       add( &((*n)->rite), v );
}

void BST::add( int v ) { add( &root, v ); }
void BST::traverse() { traverse( root ); }

void BST::traverse( Node* n ) {
   if (n->left) traverse( n->left );
   cout << n->value << ' ';
   if (n->rite) traverse( n->rite );
}

Iterator* BST::createIterator() const { return new Iterator( this ); }




// Purpose.  Fairly reusable iterator for step-wise recursive descent
//
// Discussion.  The Composite/Component/Leaf code is one of the previous
// Composite demos.  Methods added were: Component::outputValue() and
// Composite::createIterator().

#include <iostream>
#include <vector>
using namespace std;

class Component { public:
   virtual void traverse() = 0;
   virtual void outputValue() { }
};

class Leaf : public Component {
   int value;
public:
   Leaf( int val ) { value = val; }
   /*virtual*/ void traverse() { cout << value << ' '; }
   /*virtual*/ void outputValue() { traverse(); }
};

class Composite : public Component {
   vector<Component*> children;
public:
   friend class Iterator;
   void add( Component* ele ) { children.push_back( ele ); }
   /*virtual*/ void traverse() {
      for (int i=0; i < children.size(); i++)
         children[i]->traverse();
   }
   Iterator* createIterator();
};

class Memento {
public:
   struct MgrIdx {
      MgrIdx( Composite* m=0, int i=0 ) { mgr = m;  idx = i; }
      Composite* mgr;
      int        idx;
   };
   void initialize( Composite* root ) {
      vec.resize( 0 );
      vec.push_back( MgrIdx( root, 0 ) );
   }
   bool isEmpty()         { return vec.size() == 0; }
   void push( MgrIdx ds ) { vec.push_back( ds ); }
   MgrIdx top()           { return vec.back(); }
   MgrIdx pop() {
      MgrIdx ds = vec.back();
      vec.pop_back();
      return ds;
   }
private:
   vector<MgrIdx> vec;
};

// Dependencies on actual class playing the role of "Composite":
//    Composite class name, children attribute name
class Iterator {
   Composite* root;
   Memento    memento;
   bool       done;
public:
   Iterator( Composite* rooot ) { root = rooot; }
   void first() {
      memento.initialize( root );
      done = false;
   }
   void next() {
      Memento::MgrIdx ds = memento.pop();
      ds.idx++;
      // if (and while) you are at end-of-composite, go up
      while (ds.idx == ds.mgr->children.size()) {
         if (memento.isEmpty()) { done = true;  return; }
         ds = memento.pop();
         ds.idx++;
      }
      memento.push( ds );
      Composite* compo;
      if (compo = dynamic_cast<Composite*>(ds.mgr->children[ds.idx]))
         memento.push( Memento::MgrIdx( compo, 0 ) );
   }
   Component* currentItem() {
      Memento::MgrIdx ds = memento.top();
      return ds.mgr->children[ds.idx];
   }
   bool isDone() { return done; }
};

Iterator* Composite::createIterator() { return new Iterator( this ); }

void main( void ) {
   Composite containers[4];
   for (int i=0; i < 4; i++)
      for (int j=0; j < 3; j++)
         containers[i].add( new Leaf( i * 3 + j ) );
   for (i=1; i < 4; i++) containers[0].add( &(containers[i]) );
   cout << "traverse: ";
   containers[0].traverse();

   Iterator* it = containers[0].createIterator();
   cout << "\niterator: ";
   for (it->first(); ! it->isDone(); it->next())
      it->currentItem()->outputValue();
   cout << '\n';
   cout << "iterator: ";
   for (it->first(); ! it->isDone(); it->next())
      it->currentItem()->outputValue();
   cout << '\n';
   delete it;
}

// traverse: 0 1 2 3 4 5 6 7 8 9 10 11
// iterator: 0 1 2 3 4 5 6 7 8 9 10 11
// iterator: 0 1 2 3 4 5 6 7 8 9 10 11