// 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 #include #include 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: 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 ); 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(); }