/* file:    CompositeVisitor.cpp
 * author:  Robert Keller
 * purpose: Illustrating Composite pattern in C++, with Visitor pattern
 * note:    In-line method definitions are used intentionally for conciseness.
 * RCS: $Id: CompositeVisitor.cpp,v 1.4 2002/03/13 21:17:58 keller Exp keller $
 *
 * description: 
 *
 *   Composite:
 *
 *       An Item can be either 
 *           an Atom, having no apparent sub-strcture, or
 *           a Container, containing a list of (pointers to) Items 
 *       In effect, Item is an abstract class used only to unite the two
 *       concepts of Atom and Container as a single concept.
 *       All Items have names.  There is a method for adding Items to a
 *       container, and one for showing any Item on an ostream.
 *       Atoms are shown as their name, while Containers are shown as the
 *       name, followed by the showing of a list of the contained Items
 *       in brackets and separated by commas.
 *
 *       Note the use of pure virtual methods in the base class Item.
 *       These are methods that must be over-ridden in the derived classes.
 *       The presence of these methods renders the base class Item to be
 *       abstract; it is impossible to create instances of the base class 
 *       alone.  They are only created as a consequence of creating an instance
 *       of one of the derived classes.
 *
 *
 *   Visitor:
 *
 *       An Item can accept a Visitor.  When this is done, the Visitor's
 *       visit method is called on the item.  When a Container is visited,
 *       it will ask the Visitor to visit each contained item.  This is how
 *       we have defined this particular visitor behavior on a Container.
 *       We might define another visitor behavior differently.
 */

#include <string>
#include <list>
#include <iostream>
#include <typeinfo>

class Item;

/**
 * A Visitor is an interface definition for something that visits an Item.
 */

class Visitor   // interface
{
public:

/**
 * Call the vist method of this visitor on the Item.
 *
 *@param item Item on which the visit is performed.
 */

virtual void visit(Item* item, int level) = 0;


/**
 * Destroy the visitor.
 */

virtual ~Visitor() {}
};


/**
 * An Item is the base class for both Atom and Container.
 */

class Item
{
protected:

/**
 * Each Item has a name, regardless of whether it is an Atom or a Container.
 */

   string name;

/**
 * Each Item has a number that is assigned at generation time.
 */

   int itemNumber;

/**
 * The static count of the number of Items is used to generate the Item 
 * numbers.
 */

   static long ItemCount;

public:

    /** 
     * Construct an Item with a given name.
     * Since Item contains a pure virtual method, the constructor cannot be
     * called directly, but only in the context of the constructor of one
     * of the derived classes.
     *
     *@param _name the name of the Item
     */

    Item(string _name)
      : name(_name), 
        itemNumber(++ItemCount)
      {
      }


    /**
     * Accept a Visitor on this item.
     *
     *@param visitor the visitor being accepted
     *@param level the integer level of visitation
     */

    virtual void acceptVisitor(Visitor* visitor, int level) = 0;


    /**
     * Get the name of this item.
     *
     *@return the name of this item
     */

    string getName()
      {
      return name;
      }


    /**
     * Get the number of this item.
     *
     *@return the number of this item
     */

    long getNumber()
      {
      return itemNumber;
      }


    /**
     * Destroy this item.
     *
     */

    virtual ~Item() {}

};  // class Item


/**
 * Initialize static ItemCount.
 */

long Item::ItemCount = 0;


/**
 * An Item is an Item that is not a container for other Items.
 */

class Atom : public Item
{
public:

    /**
     * Construct an Atom with a given name.
     *
     *@param name the name of the Atom
     */

    Atom(string name)
      : Item(name)
      {
      }

    /**
     * Accept a visitor.
     *
     *@param visitor the visitor being accepted
     *@param level the integer level of visitation
     */

    void acceptVisitor(Visitor* visitor, int level)
      {
      visitor->visit(this, level);
      }

};  // class Atom


/**
 * A Container is an Item that contains a list of (pointers to) other Items.
 */

class Container : public Item
{
private:

/**
 * the list of pointers to other Items
 */

list<Item*> items; 

public:

    /**
     * Construct a Container with a given name.
     *
     *@param name the name of the Container
     */

    Container(string name)
      : Item(name)                      
      {
      }


    /**
     * Add an Item to a Container.
     *
     *@param item Item to be added to container
     */

    void add(Item& item)
      {
      items.push_back(&item);
      }


    /**
     * Accept a visitor.
     *
     *@param visitor the visitor being accepted
     *@param level the integer level of visitation
     */

    void acceptVisitor(Visitor* visitor, int level)
      {
      visitor->visit(this, level);


      // Visit each item contained.

      for( list<Item*>::iterator i = items.begin(); i != items.end(); i++ )
        {
        (*i)->acceptVisitor(visitor, level+1);
        }
      }

}; // class Container


/****************************************************************************
 *                       Particular kinds of visitors                       *
 ****************************************************************************/

/**
 * A NameVisitor is a particular kind of visitor.  It prints the name
 * of each item visited on an ostream.
 */

class NameVisitor : public Visitor
{
private:

/**
 * the ostream used for output
 */

ostream& out;

public:

/**
 * Create a NameVisitor.
 * 
 *@param _out the stream on which names are placed
 */

NameVisitor(ostream& _out) : out(_out)
  {
  }

/**
 * Visit an Item.
 *
 *@param pointer to item the Item being visited
 *@param level the integer level of visitation
 */

void visit(Item* item, int level)
  {
  tab(out, 4*level);                                    // tab 4 for each level
  out << "Visiting " << item->getName() << endl;
  }

/**
 * Tab the output some number of spaces
 *
 * 
 */

void tab(ostream& out, int spaces)
  {
  for( int i = 0; i < spaces; i++ )
    {
    out << " ";
    }
  }

};      // NameVisitor


/**
 * A SizeVisitor is a particular kind of visitor.  It computes the number
 * of Items, including any contained items.
 */

class SizeVisitor : public Visitor
{
private:

/** 
 * accumulated size
 */

long& count;

public:

/**
 * Create a SizeVisitor
 *
 *@param _count a reference to a variable in which the size will be 
 *       accumulated.
 */

SizeVisitor(long& _count) : count(_count)
  {
  }


/**
 * Visit an Item.
 *
 *@param pointer to item the Item being visited
 *@param level the integer level of visitation
 */

void visit(Item* item, int level)
  {
  count++;
  }
};      // SizeVisitor


/**
 * An AtomCountVisitor is a particular kind of visitor.  
 * It computes the number of Atoms in the Item.
 */

class AtomCountVisitor : public Visitor
{
private:

/** 
 * accumulated atom count
 */

long& count;

public:

/**
 * Create an AtomCountVisitor
 *
 *@param _count a reference to a variable in which the atom count will be 
 *       accumulated.
 */

AtomCountVisitor(long& _count) : count(_count)
  {
  }

/**
 * Visit an Item.  Count the item if it is an Atom, otherwise don't
 * count it.
 *
 *@param item the Item being visited
 *@param level the integer level of visitation
 */

void visit(Item* item, int level)
  {
  if( typeid(*item) == typeid(Atom) )
    {
    count++;
    }
  }
};      // AtomCountVisitor



// Define PredicateType as used in SearchVisitor

typedef bool (*PredicateType)(Item* arg);

/**
 * A SearchVisitor is a particular kind of visitor.  It tries to find an
 * Item satisfying a given predicate, and if so, sets the found argument
 * to that Item.  If there is more than one such Item, the last one
 * will be returned.
 */

class SearchVisitor : public Visitor
{
private:

/**
 * the predicate to be applied to each item searched
 */

PredicateType predicate;

/**
 * pointer to the found Item, if any
 */

long& found;

public:

/**
 * Create a SearchVisitor given a predicate of type PredicateType
 * and a reference to a pointer variable for the Item found.
 */

SearchVisitor(PredicateType _predicate, long& itemNumber)
  : predicate(_predicate),
    found(itemNumber)
  {
  }

/**
 * Visit the item.  If the predicate is true, set found to the item.
 * Otherwise, leave found unchanged.
 *
 *@param item the Item to be visited
 *@param level the integer level of visitation
 */

void visit(Item* item, int level)
  {
  if( (*predicate)(item) )
    {
    found = item->getNumber();
    }
  }
};      // SearchVisitor


/**
 * a sample predicate to be used in search
 */

bool watermelonTest(Item* item)
  {
  return item->getName() == "watermelon";
  }


/**
 * A test procedure that applies a number of different Visitors to 
 * a Container.
 */

void test(string name, Container container, ostream& out)
  {
  long count;

  // Visit container using a NameVisitor, which will print out the elements
  // of the Item.

  container.acceptVisitor(new NameVisitor(out), 0);


  // Visit container using a SizeVisitor, which will indicate the total
  // number of Atoms and Containers.

  count = 0;
  container.acceptVisitor(new SizeVisitor(count), 0);

  out << "size of " << name << " = " << count << endl;

  // Visit container using a AtomCountVisitor, which will indicate the total
  // number of Atoms.

  count = 0;
  container.acceptVisitor(new AtomCountVisitor(count), 0);

  out << "number of atoms of " << name << " = " << count << endl;


  // Visit container using a SearchVisitor, which will search for an Item
  // with name "watermelon".

  long found = 0;

  container.acceptVisitor(new SearchVisitor(watermelonTest, found), 0);

  if( found == 0 )
    {
    out << "watermelon not found" << endl;
    }
  else
    {
    out << "watermelon found at Item " << found << endl;
    }

  out << endl;
  }


/**
 * a test program that creates a number of containers and applies various
 * Visitors to each
 */

int main()
{
// Create a container named "cart", which contains an apple, a banana, and
// another apple.

Container cart("cart");

Atom apple("apple");
Atom banana("banana");

cart.add(apple);
cart.add(banana);
cart.add(apple);

test("cart", cart, cout);


// Create a container named "wagon", which contains a watermelon and a pumpkin.

Container wagon("wagon");

Atom watermelon("watermelon");
Atom pumpkin("pumpkin");

wagon.add(watermelon);
wagon.add(pumpkin);

test("wagon", wagon, cout);


// Create a container named "train", which contains the cart and wagon
// created above

Container train("train");

train.add(cart);
train.add(wagon);

test("train", train, cout);
}

/* sample output

Visiting cart
    Visiting apple
    Visiting banana
    Visiting apple
size of cart = 4
number of atoms of cart = 3
watermelon not found

Visiting wagon
    Visiting watermelon
    Visiting pumpkin
size of wagon = 3
number of atoms of wagon = 2
watermelon found at Item 5

Visiting train
    Visiting cart
        Visiting apple
        Visiting banana
        Visiting apple
    Visiting wagon
        Visiting watermelon
        Visiting pumpkin
size of train = 8
number of atoms of train = 5
watermelon found at Item 5

*/

/*
 * $Log: CompositeVisitor.cpp,v $
 * Revision 1.4  2002/03/13 21:17:58  keller
 * improved documentation
 *
 * Revision 1.3  2002/03/13 21:10:33  keller
 * added Log lines at end
 *
 */