Click here to Skip to main content
15,892,927 members
Search within:


Articles / Programming Languages / Objective C
 
Article

Specialized Visitor Design for Segregating Traversal (Criteria Based) and Operation

Rate me:
Please Sign up or sign in to vote.
4.67/5 (3 votes)
27 Dec 2012CPOL3 min read 12.4K   73   5   3
Hide the internal data structure's complexity by segregating traversal and operations

Introduction

Software applications in real life often get into a shape where a bad Data Structure choice hinders its scalability. Such designs push lots of internal responsibility to client side. This makes the system more vulnerable and provides many reasons for errors, code duplicity leading to poor performance and instability. While the ideal solution is to fix the root cause and go for big change or re-write but more often, you’d not be in position to do the same. The core data structures should seldom be subject to change, unless you have kept it completely hidden from the outer world.

Here, I am going to present an example where an application was designed based on one common design pattern. It sufficed its purpose then but later as requirements came in, the current design was not able to hold it through.

An improvised design is suggested as a solution to address the same.

Background

Image 1

Image 2

Let's take the above class diagram into consideration. This is a typical Bank's Transaction class hierarchy. Bank's do millions of such transaction on any given day. Maintaining the history/records of these transaction is one of its primary task. Let's assume there is an another class 'TransactionLog' as below for the same.

Image 3

This contains the Data Structure '_transactions: TransactionLogDataSource' where all the transaction details are stored/persisted. Unfortunately, this DS was not thought fully designed and the coder implemented it as follows:

C++
typedef map<string, map<string, Transaction* > > TransactionLogDataSource;

I.e., map<account_id, map<date_of_txn, Transaction*> this basically is map with account_id as key and value is an another map with date of transaction as key and Transaction pointer as its value. This is what I meant with bad Data Structure choice!!!

But its complexity was not of a huge concern because the designer chose to apply 'Visitor Design' Pattern for providing solution like: Total withdraw-ed amount?

Image 4

Client code:

C++
Account* acc1 = new Account();
acc1->setAccountNum("001");
acc1->setBalance(40000.09);
acc1->setPin(1234);

WithDrawal* wd1 = new WithDrawal();
wd1->setFromAccount(acc1);
wd1->setDate("2012");
wd1->setAmount(1070.00);

WithDrawal* wd2 = new WithDrawal();
wd2->setFromAccount(acc1);
wd2->setDate("2011");
wd2->setAmount(167000.00);

WithDrawal* wd3 = new WithDrawal();
wd3->setFromAccount(acc1);
wd3->setDate("2010");
wd3->setAmount(104500.00);

TransactionLog::getInstance()->addTransaction(wd1);
TransactionLog::getInstance()->addTransaction(wd3);
TransactionLog::getInstance()->addTransaction(wd4);

WithdrawalTransactionVisitor* wtVisitorX = new WithdrawalTransactionVisitor();
TransactionLog::getInstance()->accept1(wtVisitorX);
wtVisitorX->printCountAndAmount();

Traversal Logic and call to visitor for operation (algorithm):

C++
void TransactionLog::accept1(TrasactionVisitor* txnVisitor)
{
    cout << "Size of DS: " << _transactions.size() << endl;
    for (TransactionLogDataSource::iterator i=_transactions.begin(); i != _transactions.end(); ++i)
    {
        map<string, Transaction* > m = (*i).second;
        for (map<string, Transaction*>::iterator j=m.begin(); j != m.end(); ++j)
        {
         Transaction* txn = (*j).second;
         txnVisitor->visit(txn);
        }
    }        
}

virtual void WithdrawalTransactionVisitor::visit(Transaction* txn)
{
    if (txn->getType() == 1)
    {
        WithDrawal *wd = dynamic_cast<WithDrawal*>(txn);
        if(wd != NULL)
            _totalAmount += wd->getAmount();
        ++_count;
    }
}

Output:

Image 5

Problem

So far, so good!

Sometime down the line, a new business requirement comes to report the daily withdrawal amount, i.e., day wise list of withdrawn amount for each account in the bank. Now, this is where things get complicated because

C++
TransactionLog::accept1(TrasactionVisitor* txnVisitor)

'accept1(...)' logic will have to be modified to take dates into consideration or add a new version of 'accept(...)' method in 'TransactionLog' for the same. So basically with every new reporting criteria, a new version of 'accept(...)' will be required. And if you see to it, this is all because the traversing criteria has changed not the traversal logic or operation.

Thus the need of hour is to segregate the traversal and operation so that whatever be the traversal criteria, the traversal logic and operation (algorithm) stays untouched.

Solution

Let's have another visitor responsible for traversal strategy as follows:

Image 6

The specialized traversal strategy visitor takes the TransactionLogDataSource, applies the filter criteria (dates) and calls the operations visitor.

Client Code

Construction of specialized traversal strategy visitor for date wise reporting:

C++
TraversalStrategyVisitor_DateBased(string date) : _date(date) {}

There is an additional parameter TraversalStrategyVisitor_DateBased* to TransactionLog::getInstance()->accept(), to do the criteria based traversing and then allow visitor to visit the Transaction* for operation.

C++
WithdrawalTransactionVisitor* wtVisitor = new WithdrawalTransactionVisitor();

TraversalStrategyVisitor_DateBased* tvslVistorDtStrategy = 
             new TraversalStrategyVisitor_DateBased("2012");
TransactionLog::getInstance()->accept(tvslVistorDtStrategy, wtVisitor);
wtVisitor->printCountAndAmount();

void TransactionLog::accept(TraversalStrategyVisitor* trvslVisitor, 
                            TrasactionVisitor* txnVisitor)
{
    trvslVisitor->traverse(_transactions, txnVisitor);
}

Its traversal logic and call to visitor for operation (algorithm):

C++
virtual void TraversalStrategyVisitor_DateBased::traverse(
          TransactionLogDataSource _transactions, TrasactionVisitor* txnVisitor)
{
    for (TransactionLogDataSource::iterator i=_transactions.begin(); i != _transactions.end(); ++i)
    {
                map<string, Transaction* > m = (*i).second;
        for (map<string, Transaction* >::iterator j=m.begin(); j != m.end(); ++j)
        {
            Transaction* txn = (*j).second;

            if (_date == txn->getDate())
                txnVisitor->visit(txn);
        }
    }        
}

With the above approach, the...

C++
void TransactionLog::accept(TraversalStrategyVisitor* trvslVisitor,  TrasactionVisitor* txnVisitor)

...remains intact, i.e., no change in the core-framework classes.

Suppose there comes the need of another reporting criteria, all you need to do is to introduce new specialized traversal strategy visitor class and its implementation for traversal. Everything else remains untouched. Moreover, in case you decide to change the internal data structure for your own good, there will be no changes required on the client side. Well, that's the first take away of Visitor Design Pattern and even approach explained in background supported it.

Complete Client Code

C++
Account* acc1 = new Account();
acc1->setAccountNum("001");
acc1->setBalance(40000.09);
acc1->setPin(1234);

Account* acc2 = new Account();
acc2->setAccountNum("002");
acc2->setBalance(40000.09);
acc2->setPin(1234);

Account* acc3 = new Account();
acc3->setAccountNum("003");
acc3->setBalance(40000.09);
acc3->setPin(1234);

WithDrawal* wd1 = new WithDrawal();
wd1->setFromAccount(acc1);
wd1->setDate("2012");
wd1->setAmount(1070.00);

WithDrawal* wd2 = new WithDrawal();
wd2->setFromAccount(acc1);
wd2->setDate("2011");
wd2->setAmount(167000.00);

WithDrawal* wd3 = new WithDrawal();
wd3->setFromAccount(acc1);
wd3->setDate("2010");
wd3->setAmount(104500.00);

WithDrawal* wd4 = new WithDrawal();
wd4->setFromAccount(acc2);
wd4->setDate("2012");
wd4->setAmount(7000.00);

WithDrawal* wd5 = new WithDrawal();
wd5->setFromAccount(acc2);
wd5->setDate("2011");
wd5->setAmount(167000.00);

WithDrawal* wd6 = new WithDrawal();
wd6->setFromAccount(acc2);
wd6->setDate("2010");
wd6->setAmount(104500.00);

WithDrawal* wd7 = new WithDrawal();
wd7->setFromAccount(acc3);
wd7->setDate("2012");
wd7->setAmount(5000.00);

WithDrawal* wd8 = new WithDrawal();
wd8->setFromAccount(acc3);
wd8->setDate("2011");
wd8->setAmount(167000.00);

WithDrawal* wd9 = new WithDrawal();
wd9->setFromAccount(acc3);
wd9->setDate("2010");
wd9->setAmount(104500.00);    

TransactionLog::getInstance()->addTransaction(wd1);
TransactionLog::getInstance()->addTransaction(wd2);
TransactionLog::getInstance()->addTransaction(wd3);
TransactionLog::getInstance()->addTransaction(wd4);
TransactionLog::getInstance()->addTransaction(wd5);
TransactionLog::getInstance()->addTransaction(wd6);
TransactionLog::getInstance()->addTransaction(wd7);
TransactionLog::getInstance()->addTransaction(wd8);
TransactionLog::getInstance()->addTransaction(wd9);

std::cout << endl << endl << std::endl;
WithdrawalTransactionVisitor* wtVisitor = new WithdrawalTransactionVisitor();    
TraversalStrategyVisitor_DateBased* tvslVistorDtStrategy = 
          new TraversalStrategyVisitor_DateBased("2012");
TransactionLog::getInstance()->accept(tvslVistorDtStrategy, wtVisitor);
cout << "For the date: 2012" << std::endl;
wtVisitor->printCountAndAmount();

std::cout << endl << endl << std::endl;
WithdrawalTransactionVisitor* wtVisitor1 = new WithdrawalTransactionVisitor();
TraversalStrategyVisitor_DateBased* tvslVistorDtStrategy1 = 
           new TraversalStrategyVisitor_DateBased("2011");
TransactionLog::getInstance()->accept(tvslVistorDtStrategy1, wtVisitor1);
cout << "For the date: 2011" << std::endl;
wtVisitor1->printCountAndAmount();

std::cout << endl << endl << std::endl;
WithdrawalTransactionVisitor* wtVisitor2 = new WithdrawalTransactionVisitor();
TraversalStrategyVisitor_DateBased* tvslVistorDtStrategy2 = 
          new TraversalStrategyVisitor_DateBased("2010");
TransactionLog::getInstance()->accept(tvslVistorDtStrategy2, wtVisitor2);
cout << "For the date: 2010" << std::endl;
wtVisitor2->printCountAndAmount();

Output:

Image 7

History

  • 27th December, 2012: Initial release

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Mitendra Anand
Architect
India India
My name is Mitendra Anand and my work is focused around application development which includes a lot of prototyping of new solutions.

While I have a background in C++/VC++ programming, my daily work is mostly spent in C++, Sybase, SQL, Unix/Windows.

Comments and Discussions

 
First Prev Next
QuestionYour example visitor pattern is not the visitor pattern I know... Pin
Andreas Gieriet27-Dec-12 12:50
professionalAndreas Gieriet27-Dec-12 12:50 
Hello Mitendra Anand,

If your data structure claims to implement the visitor pattern, then I think your example visitor pattern (the accept1 implementation) is not the visitor pattern as described by GoF[^] or as described in http://en.wikipedia.org/wiki/Visitor_pattern[^].

Whenever I employ the visitor pattern, I use it as double dispatching visitor pattern: each element class has an accept method that only calls the visit of the respective visitor. The respective visit method (not the element's accept method) provides the traversing and operation code. BTW: The pattern also demands to never call any other visit method directly, but only via accept again.

In your example, you have the accept1 instead of the visit method doing the traversing - which seems to motivate you suggesting your solution, right?

I think, your code is overkill. If you apply the proper double dispatch visitor pattern, you are fine off - no need to add a separate traversing strategy. Each derived visitor can implement it's traversing (even though, I've seen little variablility in traversing in all my projects so far - more common is variations in operation).

If you want to add variable traversing strategy to a given visitor (without deriving from that visitor), you may add that strategy implementation to the constructor of a concrete "walk" visitor and have the respective visit methods deal with that without passing that strategy to all accept methods (that's all about visitors: they keep a state over all access to all elements while keeping the element interface untouched).

The visitors I've seen have a common interface for all elements, namely:
C++
class IVisitor;

class IAcceptingElement
{
  public:
    virtual void accept(IVisitor& v) = 0;
};

The elements and the visitors:

C++
#include "IVisitor.h"
...
class Element: public IAcceptingElement
{
  public:
   ...
   void accept(IVisitor& v) { v.visitElement(*this); }
   ...
};

class List: public IAcceptingElement
{
  public:
   ...
   void accept(IVisitor& v) { v.visitList(*this); }
   ...
};


C++
class Element;
class List;

class IVisitor
{
  public:
    virtual void visitElement(Element& item) = 0;
    virtual void visitList(List& item) = 0;
    ...
};


C++
class WalkVisitor: public IVisitor
{
  protected:
    bool _done;

    WalkVisitor(): _done(false) { }
  public:
    // no operation yet
    void visitElement(Element& item) { }
    // traverse as needed...
    void visitList(List& item)
    {
       for(auto it = item.begin(); !_done && (it != item.end()); ++it) (*it).accept(*this);
    }
    ...
};


C++
class GetElementsVisitor: public WalkVisitor
{
    private:
      Predicate<Element> _cutoff;
      Container<Element> _elements;
    public:
      GetElementsVisitor(Predicate<Element>& cutoff, Container<Element>& elements)
      : _cutoff(cutoff), _elements(elements) { }
      // do operation
      void visitElement(Element& item)
      {
          if (_cutoff(item)) done = true;
          else if (!done) _elements.add(item);
      }
    ...
};


Finally using the visitors:
C++
...
// get all elements before the cutoff condition below
CutOffFunctor cutoff(/* some cutoff condition */);
Container<Element> elements;
GetElementsVisitor v(cutoff, elements);
data.accept(v);
// do something with the collected elements...
...


Summary: I suggest you re-visit Wink | ;-) the visitor pattern again (namely: all elements have the same accept interface, the accept always looks the same, the traversing and operations are in the visit methods). The benefit: regular structure, freedom to implement any traversing and operation by simply override the respective visitor method(s), it's an established pattern that your successors know (hopefully Wink | ;-) ).

Cheers
Andi

PS: Anyone is of course free to have "his" visitor pattern applied (or invented), but I think it's easier to stick on the established visitor approach to ease life for your successors who have to maintain that code.
AnswerRe: Your example visitor pattern is not the visitor pattern I know... Pin
Mitendra Anand28-Dec-12 1:47
Mitendra Anand28-Dec-12 1:47 
GeneralRe: Your example visitor pattern is not the visitor pattern I know... Pin
Andreas Gieriet28-Dec-12 4:03
professionalAndreas Gieriet28-Dec-12 4:03 
Last Visit: 31-Dec-99 18:00     Last Update: 6-May-24 23:52Refresh1

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink
Advertise
Privacy
Cookies
Terms of Use
Layout: fixed | fluid

Posted 27 Dec 2012

Article Copyright 2012 by Mitendra Anand
Everything else Copyright © CodeProject, 1999-2024

Web01 2.8:2024-04-02:1