// file:    uml5.cc
// author:  keller
// purpose: Illustration of recursion
//
// RCS: $Id: uml5.cc,v 1.2 2000/02/08 06:00:50 keller Exp $
//
// An Item is either an Atom, or a Container containing a list of Items.
// Any item can be in a container more than once, or in different containers
// at the same time.

/* UML diagram:

		    ----------------------------
		    |           Item           |
		    ----------------------------
	(inheritance)  /_\        /_\        | *
			|          |         |
			|          |         |
			|          |        /\
			|          |        \/  (aggregation)
	   -----------------   --------------------
	   |     Atom      |   |    Container     |
	   -----------------   --------------------

*/

// The 'count' of an item is defined to be 1 for an atom, and 
//     the sum of the counts of the contained items otherwise.
//     If the same Item occurs more than once, it is counted multiple times.

#include <iostream>

// The base class

class Item
{
protected:

    char *name;

public:

    // construct an Item, copying name into it

    Item(char *name)
      {
      this->name = strcpy(new char[strlen(name)+1], name);
      }


    // return the count of the item, as defined above (pure virtual method)

    virtual int count() const = 0;


    // show the Item on an ostream (pure virtual method)

    virtual ostream &show(ostream &out) const = 0;


    // destroy the item

    virtual ~Item() 
      {
      delete [] name;
      }

};  // class Item



// ItemCells are used to construct an open linked-list of Items

class ItemCell
{
private:

    Item &item;        // the first item in a list represented by this cell
    ItemCell *next;    // the next cell in the list, i.e. the rest of the items
    
public:
    
    // construct an ItemCell based on a first Item and next ItemCell

    ItemCell(Item &newItem, ItemCell *next)
      : item(newItem)
      {
      this->next = next;
      }


    // return the first Item

    Item &first() const
      {
      return item;
      }


    // return the rest of the Items (as a list)

    ItemCell *rest() const
      {
      return next;
      }

};  // class ItemCell



// Atom is an Item that cannot contain others

class Atom : public Item
{
public:

    // construct an Atom

    Atom(char *name)
      : Item(name)
      {
      }


    // return the count

    int count() const
      {
      return 1;
      }


    // show the Atom on an ostream

    ostream &show(ostream &out) const
      {
      return out << name;
      }
};  // class Atom



// Container is an Item that can contain other Items

class Container : public Item
{
private:

    ItemCell* items;                                    // list of Items

public:

    // construct a Container with a given name

    Container(char *name)
      : Item(name)                      
      {
      items = 0;                                        // empty list
      }


    // add an Item to a Container

    void add(Item &item)
      {
      items = new ItemCell(item, items);
      }


    // return the count

    int count() const
      {
      int total = 0;
      ItemCell *L = items;

      while( L != 0 )
        {
        total += L->first().count();
        L = L -> rest();
        }

      return total;
      }


    // show the Container on an ostream

    ostream &show(ostream &out) const
      {
      out << name << ":(";
      show1(items, out);
      return out << ")";
      }

    // auxiliary function to show oldest Item first (i.e. in reverse order)

    void show1(ItemCell *L, ostream & out) const
      {
      if( L != 0 )
        {
	if( L-> rest() != 0 )
	  {
	  show1(L->rest(), out);
	  out << " ";
	  }

        L->first().show(out);
        }
      }    


};  // class Container


// Test procedure, shows item name, contents, and count

void test(Item &item)
  {
  item.show(cout); cout << ", count = " << item.count() << endl << endl;
  }


// Test program

main(int argc, char **argv)
  {
  Container c1("c1");

  Atom a1("a1"), a2("a2"), a3("a3");

  c1.add(a1);
  c1.add(a2);
  c1.add(a3);

  test(c1);

  Container c2("c2");
  
  c2.add(a1);
  c2.add(c1);
  c2.add(a2);

  test(c2);

  Container c3("c3");
  
  c3.add(c2);
  c3.add(a1);
  c3.add(c2);

  test(c3);

  Container c4("c4");

  test(c4);
  }

/* output:

c1:(a1 a2 a3), count = 3

c2:(a1 c1:(a1 a2 a3) a2), count = 5

c3:(c2:(a1 c1:(a1 a2 a3) a2) a1 c2:(a1 c1:(a1 a2 a3) a2)), count = 11

c4:(), count = 0

*/