// Purpose.  Iterator design pattern demo
// 
// Discussion.  Iterator provides: abstractoin of the access and traversal
// functionality so that the aggregate remains lean, access to the
// aggregate's contents without exposing its internal details, multiple
// simultaneous traversals, and a uniform traversal interface.  Either:
// the aggregate's interface must be powerful enough to support the
// implementation of the Iterator efficiently, or, the Iterator and the
// aggregate are tightly coupled.  For the later case, the Iterator is
// either:  "internal" to the aggregate, or it is a friend, or it uses an
// intermediary Memento to save the traversal state normally handled
// automatically by internal recursive traversal.  In this example, the
// aggregate's interface does so much of the work, that the Iterator
// is a very thin layer between the aggregate and the client.  In fact,
// the Iterator is so loosely coupled that the aggregate's
// createForwardIterator() method is probably not necessary.  The Iterator
// interface is the one specified in the GOF book (p265 and p290) and the
// STL specification.

#include <iostream.h>

class Node;
class Iterator;

class BinaryTree {
public:
	BinaryTree()          { _head = NULL; _count = 0; }
	int       getCount()  { return _count; }
	void      add( int );
	Node*     first();
	Node*     last();
	Node*     next( Node* );
	Node*     previous( Node* );
	Iterator* createForwardIterator();
	Iterator* createBackwardIterator();
private:
	Node*  _head;
	int    _count;
	void   _add( Node*, int );
};

#include "BinaryTree.C"


class Iterator {
public:
	Iterator( BinaryTree* in )  { _tree = in; }
	virtual void  first()       = 0;
	virtual void  next()        = 0;
	virtual Node* currentItem() = 0;
	        bool  isDone()      { return _count > _tree->getCount(); }
protected:
	BinaryTree*  _tree;
	Node*        _current;
	int          _count;
};

class ForwardIterator : public Iterator {
public:
	ForwardIterator( BinaryTree* in ) : Iterator(in) { }
	void first() {
		_current = _tree->first();
		_count = 1; }
	void next() {
		_current = _tree->next( _current );
		_count++;}
	Node* currentItem() { return _current; }
};

class BackwardIterator : public Iterator {
public:
	BackwardIterator( BinaryTree* in ) : Iterator(in) { }
	void first() {
		_current = _tree->last();
		_count = 1; }
	void next() {
		_current = _tree->previous( _current );
		_count++;}
	Node* currentItem() { return _current; }
};


Iterator* BinaryTree::createForwardIterator() {
	 return new ForwardIterator( this ); }
Iterator* BinaryTree::createBackwardIterator() {
	return new BackwardIterator( this ); }


main()
{
	BinaryTree tree;
	tree.add(10);	tree.add(5);	tree.add(15);	tree.add(3);
	tree.add(11);	tree.add(7);	tree.add(19);	tree.add(1);
	tree.add(12);	tree.add(2);	tree.add(0);	tree.add(18);
	tree.add(4);	tree.add(14);	tree.add(6);	tree.add(16);
	tree.add(9);	tree.add(13);	tree.add(8);	tree.add(17);

	Iterator*  forward1 = tree.createForwardIterator();
	Iterator*  forward2 = tree.createForwardIterator();
	Iterator*  backward = tree.createBackwardIterator();

	for (forward1->first(), forward2->first(), backward->first();
			! forward1->isDone();
			forward1->next(), forward2->next(), backward->next())
		cout << forward1->currentItem()->getValue() << "\t" <<
			backward->currentItem()->getValue() << "\t" <<
			forward2->currentItem()->getValue() << endl;
	cout << endl;

	delete forward1;
	delete forward2;
	delete backward;
}

// 0       19      0					10      9       10
// 1       18      1					11      8       11
// 2       17      2					12      7       12
// 3       16      3					13      6       13
// 4       15      4					14      5       14
// 5       14      5					15      4       15
// 6       13      6					16      3       16
// 7       12      7					17      2       17
// 8       11      8					18      1       18
// 9       10      9					19      0       19