// Purpose.?Composite, Builder, Iterator, Memento, Visitor demo
//
// Discussion.?Composite is a fairly fundamental pattern - it uses, or is
// used by, many other patterns.?Iterator can be used to traverse a
// Composite [GOF, p173].?Visitor can be used to apply an operation over
// an object structure defined by Composite [GOF, p344].?Builder often
// builds a Composite [GOF, p106].?Iterator can use Memento to capture
// the state of an iteration [GOF, p271].
//
// Input (composit.dat):
//  ?a 1 2 b 6 d 13 14 15 d 7 8 b 3 4 5 c 9 10 11
//  ? e 16 17 g 20 g 18 e 12 f 19 f c a
//
// In-memory structures:
//  ?a: 1 2?^b 3 4 5? ^c
//  ?b: 6? ^d 7 8
//  ?c: 9?10?11?^e?12? ^f
//  ?d:?13? 14?15
//  ? e:?16?17?^g?18
//  ?f:?19
//  ?g:? 20
//
// Output:
//  ? 1 2 6 13 14 15 7 8 3 4 5 9 10 11 16 17 20 18 12 19
//  ?a 1 2 b 6 d 13 14 15 7 8 3 4 5 c 9 10 11 e 16 17 g 20 18 12 f 19
//  ? composites = 7.?primitives = 20.?total value = 210.?average value = 10

#include <stdio.h>
#include <iostream.h>
#include <fstream.h>

class Composite;
class Primitive;

class Visitor {
public:
virtual void visit( Composite* ) = 0;
virtual void visit( Primitive* ) = 0;
};

class ListVisitor : public Visitor {
public:
/* virtual */ void visit( Composite* );
/* virtual */ void visit( Primitive* );
};

class TotalVisitor : public Visitor {
public:
TotalVisitor() { totalComposites = totalPrimitives = totalValue = 0; }
/* virtual */ void visit( Composite* c ) { totalComposites++; }
/* virtual */ void visit( Primitive* );
void reportTotals()?{
    ? cout << "composites = " << totalComposites
<< ".?primitives = " << totalPrimitives
<< ".?total value = " << totalValue
<< ".?average value = " << totalValue / totalPrimitives << endl; }
private:
int? totalComposites;
int?totalPrimitives;
int? totalValue;
};

class Iterator;

class Component {
public:
enum ComponentType { PrimitiveT, CompositeT };
virtual void traverse() = 0;
virtual void add( Component* )?{ }
virtual ComponentType getType() = 0;
virtual void accept( Visitor& ) = 0;
};

class Primitive : public Component {
public:
Primitive( int _value ) { value_ = _value; }
void traverse() { cout << value_ << " "; }
ComponentType getType() { return PrimitiveT; }
int getValue()                        ?{ return value_; }
/* virtual */ void accept( Visitor& v ) { v.visit( this ); }
private:
int  ? value_;
};

class Composite : public Component {
public:
friend Iterator;
Composite( char _name ) { name_ = _name;?index_ = 0; }
void add( Component* ele )            ?{ children_[index_++] = ele; }
ComponentType getType() { return CompositeT; }
void printName()                      ?{ cout << name_ << " "; }
/* virtual */ void accept( Visitor& v ) { v.visit( this ); }
void traverse();
Iterator*? createIterator();
private:
? ?/span>char      ?name_;
int index_;
Component*? children_[99];
};

void Composite::traverse() {
for (int i=0; i < index_; i++)
    ?children_[i]->traverse(); }

/* virtual */ void ListVisitor::visit( Composite* c ) { c->printName(); }
/* virtual */ void ListVisitor::visit( Primitive* p ) { p->traverse(); }
/* virtual */ void TotalVisitor::visit( Primitive* p ) {
totalPrimitives++;
totalValue += p->getValue(); }

class Memento {
public:
void initialize( Composite* _root ) {
    ? compArr_[0] = _root;
    ? indxArr_[0] = -1;
    ? index_ = 0; }
void pushCurrent( Composite* _composite, int _index ) {
    ?compArr_[index_+1] = _composite;
    ?indxArr_[++index_] = _index; }
int popCurrent() {
    ?if (index_ == 0) return 1;
    ?index_--;
    ?return 0; }
void getAndIncrement( Composite** _composite, int* _index ) {
    ? *_composite = compArr_[index_];
    ?*_index = indxArr_[index_];
    ?(*_index)++;
    ? indxArr_[index_]++; }
private:
Composite*? compArr_[10];
int indxArr_[10];
int index_;
};

class Iterator {
public:
Iterator( Composite* _root ) {
    ?root_ = _root;
    ?isDone_= 0; }
Component* first() {
    ?isDone_= 0;
    ?memento_.initialize( root_ );
    ?return root_; }
Component* next() {
    ?Composite* comp;
    ?int      ?indx;
    ? memento_.getAndIncrement( &comp, &indx );
    ?// if (and while) you are at end-of-composite, go back up
    ? while (indx == comp->index_)
    ?{
int ret = memento_.popCurrent();
if (ret) {
          ? isDone_ = 1;
          ? return 0; }
memento_.getAndIncrement( &comp, &indx );
    ?}
    ?if (comp->children_[indx]->getType() == Component::CompositeT)
memento_.pushCurrent( (Composite*) comp->children_[indx], -1 );
    ?return comp->children_[indx]; }
int isDone() { return isDone_; }
private:
Composite*? root_;
Memento memento_;
int isDone_;
};

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

class Builder;

class Reader {
public:
Reader( Builder* _builder ) {
    ? builder_ = _builder;
    ? nextSlot_ = 0; }
void construct();
private:
Builder*?builder_;
char    ? compNames_[20];
int nextSlot_;
int isLower_( char ch ) {
    ?if ((ch >= 'a') && (ch <= 'z')) return 1;
    ?else return 0; }
int findName_( char ch ) {
    ?for (int i=0; i < nextSlot_; i++)
if (compNames_[i] == ch) return 1;
    ? compNames_[nextSlot_++] = ch;
    ? return 0; }
};

class Builder {
public:
/**/ Builder() { nextSlot_ = 0; }
void buildComposite( char _name ) {
    ?// cout << _name << " at level " << nextSlot_ << endl;
    ? stack_[nextSlot_] = new Composite( _name );
    ?if (nextSlot_)
stack_[nextSlot_ - 1]->add( stack_[nextSlot_] );
    ? nextSlot_++; }
void buildPrimitive( int _value ) {
    ? stack_[nextSlot_ - 1]->add( new Primitive( _value ) ); }
void closeComposite()?{ nextSlot_--; }
Composite* getResult() { return stack_[0]; }
private:
Composite* stack_[20];
int      ?nextSlot_;
};

void Reader::construct() {
char    ?buf[20];
int value;
ifstream? inFile( "composit.dat", ios::in );

while ( inFile >> buf )
{
    ?if (isLower_( buf[0] ))
if (findName_( buf[0] ))
          ?builder_->closeComposite();
else
          ?builder_->buildComposite( buf[0] );
    ?else
    ?{
sscanf( buf, "%d", &value );
builder_->buildPrimitive( value );
    ?}
}
}

void main( void ) {
Builder builder;
Reader      ?reader( &builder );
Composite*  ?root;
Iterator* it;
ListVisitor listV;
TotalVisitor?totalV;

reader.construct();
root = builder.getResult();

// Composite can traverse itself, but Composite nodes get "lost"
root->traverse(); cout << endl;

// If you don't want Composite nodes "lost", use an Iterator for traversal
it = root->createIterator();
for (Component* c = it->first(); ! it->isDone(); c = it->next())
    ?c->accept( listV );
?/span>?cout << endl;

// Visitors can be designed to accumulate state over a Composite
for (c = it->first(); ! it->isDone(); c = it->next())
    ? c->accept( totalV );
totalV.reportTotals();
}

// ListVisitor replaces the following code:
// for (Component* c = it->first(); ! it->isDone(); c = it->next()) {
//  ?if (c->getType() == Component::PrimitiveT)
// ((Primitive*) c)->traverse();
//  ?else
// ((Composite*) c)->printName(); }