_GENERIC CONTAINERS IN C++_
by Andrew Davidson


/*
 * Generic list
 *
 * by A. E. Davidson 12/90
 *
 * Overview
 *
 * USES
 * to declare a generic list of class
 * foo items and a generic list of class 
 * bar items
 *
 * #include "genriclt.hh"
 * DeclareList(Foo);
 * DeclareList(Bar);
 *
 * main()
 * {
 * class foo;
 * class bar;
 * GenList(foo) genListOfFoo;
 * GenList(bar) genListOfBar;
 * GenIter
 *
 * REQUIREMENTS / ASSUMPTIONS
 * The generic list does not manage
 * the items memory. It is up to the
 * user to free them
 *
 * the function GenList::RemoveItem()
 * takes a pointer to a member function.
 * this funciton should return true is found
 * else false. GenList::RemoveItem will not 
 * compile on my machine if the member 
 * fuction is inlined. it gives a signal 6 error message
 *
 * NOTES
 * never use new to create a list or an iter!
 *
 *
 */

#include <generic.h>

#ifndef GENERIC_LIST_HH
#define GENERIC_LIST_HH

/*
 * these macro's should be used 
 * any where you need to reffer to
 * the generic list, item, or iter classes
 *
 * PTAMF: Pointer to a Member Function
 */
#define PTAMF(CLASS_TAG)   name2(CLASS_TAG,PTAMF)
#define GenItem(CLASS_TAG) name2(CLASS_TAG,GenItem)
#define GenList(CLASS_TAG) name2(CLASS_TAG,GenList)
#define GenIter(CLASS_TAG) name2(CLASS_TAG,GenIter)

/*----------------------------- class Item ---------------------------*/
/*
 * GenItem(CLASS_TAG) is a private
 * class. It can only be created by
 * be the member functions of GenList(CLASS_TAG)
 * and GenIter(CLASS_TAG)
 */

#define GenItemdeclare(CLASS_TAG) 			     		 \
class GenItem(CLASS_TAG) 						 \
{ 									 \
  GenItem(CLASS_TAG) *next; 					       	 \
  CLASS_TAG &item; 						       	 \
  GenItem(CLASS_TAG)(CLASS_TAG &i) : item(i)				 \
    {next = NULL;} 							 \
  GenItem(CLASS_TAG)(CLASS_TAG &i, GenItem(CLASS_TAG) *n) : item(i) 	 \
    {next = n; } 							 \
  ~GenItem(CLASS_TAG)() 						 \
    {;}					       				 \
  friend GenList(CLASS_TAG); 					       	 \
  friend GenIter(CLASS_TAG); 						 \
}	

/*---------------------------- class List ---------------------------*/	
#define GenListdeclare(CLASS_TAG)	       			  	 \
class GenList(CLASS_TAG)					       	 \
{								       	 \
  GenItem(CLASS_TAG) *hd;					       	 \
 public:							       	 \
  GenList(CLASS_TAG)(GenItem(CLASS_TAG) *n = NULL)			 \
    { hd = n;}     	 						 \
  GenList(CLASS_TAG)(const CLASS_TAG &i) 				 \
    {hd = NULL; insert(i);} 		       				 \
  ~GenList(CLASS_TAG)()							 \
    {Clear();}					 			 \
  void Clear(void)							 \
    {								       	 \
      GenItem(CLASS_TAG) *pt;					       	 \
      while (hd)						       	 \
	{							       	 \
	  pt = hd;						       	 \
	  hd = hd->next;					       	 \
	  delete pt;						       	 \
	}							       	 \
    }							       	       	 \
  GenList(CLASS_TAG)(const GenList(CLASS_TAG) &seq) {hd = seq.hd;} 	 \
  GenList(CLASS_TAG) operator = (const GenList(CLASS_TAG) &other)	 \
    {									 \
      hd = other.hd; 							 \
      return *this;						       	 \
    }									 \
  void insert(CLASS_TAG &i){ hd = new GenItem(CLASS_TAG)(i, hd); } 	 \
  void append(CLASS_TAG &i)						 \
    {									 \
      for (GenItem(CLASS_TAG) *pt = hd; pt && pt ->next; pt = pt->next)	 \
	;								 \
      if (pt) 								 \
	{								 \
	  GenItem(CLASS_TAG) *tmp = new GenItem(CLASS_TAG)(i); 		 \
	  pt->next = tmp;						 \
	}   								 \
      else insert(i);							 \
    } 									 \
									 \
  void removeItem(PTAMF(CLASS_TAG) found, CLASS_TAG &obj)      		 \
    {									 \
      GenItem(CLASS_TAG) *prev, *rem;					 \
      									 \
      prev = NULL;							 \
      rem = hd;								 \
      while( rem && !(obj.*found)(rem->item) )				 \
        {								 \
	  prev = rem;							 \
	  rem = rem->next;						 \
	}								 \
	  if (rem) 		     		 			 \
	    {								 \
	      if (prev)							 \
		prev->next = rem->next;					 \
	      else							 \
		hd = rem->next;						 \
	      delete rem;	       					 \
	    }								 \
    }									 \
  friend GenIter(CLASS_TAG);						 \
}



/*------------------------------- class Iter ---------------------------*/
  /* 
   * interate over entire list 
   * CLASS_TAG *operator()()
   */
  
#define GenIterdeclare(CLASS_TAG) 					\
class GenIter(CLASS_TAG) 						\
{  									\
  GenItem(CLASS_TAG) *current;						\
 public: 								\
  GenIter(CLASS_TAG)(GenList(CLASS_TAG) &ilist)				\
    { current = ilist.hd; }						\
  GenIter(CLASS_TAG)(GenIter(CLASS_TAG) &other)				\
    { current = other.current; }   	  				\
  ~GenIter(CLASS_TAG)() 						\
    {;} 								\
  GenIter(CLASS_TAG) operator = (GenList(CLASS_TAG) &ilist) 		\
    { current = ilist.hd; return *this; } 				\
   CLASS_TAG *operator()() 						\
    {									\
      if (current) 							\
	{ 								\
	  GenItem(CLASS_TAG) *tmp = current; 				\
	  current = current->next; 					\
	  return &tmp->item; 						\
	} 								\
      return NULL; 							\
    }									\
} 
				

/*
 * macro that create all the generic types
 * provided for ease of uses
 *
 * for some unknown reason my compiler can't handle a 
 * function prameter that is a pointer to a member function
 * It can deal with it if the pointer is declared using 
 * a typedef
 */
#define DeclareList(CLASS_TAG) 	\
  typedef int (CLASS_TAG::*PTAMF(CLASS_TAG))(CLASS_TAG &); \
  class GenList(CLASS_TAG); 	\
  class GenIter(CLASS_TAG); 	\
  declare(GenItem,CLASS_TAG); 	\
  declare(GenList,CLASS_TAG);	\
  declare(GenIter,CLASS_TAG)

#endif




[LISTING TWO]


/*
 * test1.cc
 *
 * by A. E. Davidson
 *
 * Provides a driver to test the generic list
 */

#include <stream.h>
#include "coin.hh"
#include "genericl.hh"

/*
 * use the declare macros to 
 * allow creation of list of desired types
 */

DeclareList(coin);

/*
 * proto typing function using the generic list
 * stuff must be done after DeclareList()
 */
void displayAndTotal(GenIter(coin) next_coin);
     
main()
{
  /*--- create some coins -------*/
  coin c1 = penny;
  coin c2 = nickel;
  coin c3 = dime;
  coin c4 = quarter;

  /*------ create a list of coins -----*/
  GenList(coin) list_of_coins;
  list_of_coins.append(c1);
  list_of_coins.append(c2);
  list_of_coins.append(c3);
  list_of_coins.append(c4);

  /*------- display the list of coins and there total ------*/
  displayAndTotal(list_of_coins);

  /*-------------- remove one of the coins --------------*/
  cout << "\n\n list after removing coin c2 \n";
  list_of_coins.removeItem(&coin::found, c2);
  displayAndTotal(list_of_coins);
  

  /*
   * rember: c2 has been removed from the list but it still exists
   */
  cout << "\n\n coin c2 still exists, it was only removed from the list \n";
  cout << "coin: " << c2;


#ifdef NEVER 

  /* 
   * this is example shows a design flaw
   * with the generic list assignment operator
   *
   * if you delete an object but do not remove it 
   * from the list first you will get a core dump.
   * The list will contain a dangling reference
   *
   * this is becuase I chose to implement the
   * the list using references instead of copying
   * the objects. See the discusion at the end of the
   * article
   */
  coin *c5 = new coin(quarter);

  list_of_coins.append(*c5);
  delete c5;
  displayAndTotal(list_of_coins);

#endif  
}

/*
 * this function illustrates
 * how to use the GenIter class
 *
 * notice that the parmeter list expect
 * an inter object, but I always pass a list
 * object
 */
void displayAndTotal(GenIter(coin) next_coin)
{
  double total = 0.0;
  coin *tmp;
  
  while ((tmp = next_coin()))
    {
      /* 
       * coins know how to convert themselves to doubles
       */
      total += *tmp;
      /*
       * coins also know how to display themselves
       */
      cout << "coin: " << *tmp << "\ttotal: " << total <<"\n";
    }
}


[LSITING THREE]

/*
 * coin class
 *
 * by A. E. Davidson
 *
 * USES
 * provides a simple class that can be 
 * used to illistrate the operation of
 * the generic list
 *
 * a coin may be a penny, nickel, dime, or quarter
 */

#ifndef COIN_HH
#define COIN_HH

enum coin_type {penny, nickel, dime, quarter}; 


class coin 
{
  coin_type unit;
  double    amount;
  
 public:
  coin()
    {unit = penny; amount = 0.01;} 
  coin( coin_type type);
  coin(const coin &other)
    {unit = other.unit; amount = other.amount;} 
  ~coin(){;}
  coin& operator = (const coin &other)
    { unit = other.unit; amount = other.amount;} 
  friend ostream& operator << (ostream &os, coin &c);
  operator double () 
    {return amount;} 

  /*
   * this function is intended to be
   * used with GenList(CLASS_TAG)::removeItem()
   * I get a compile error if I try to inline this 
   * function
   */
  int found(const coin &other);
};


#endif


[LISTING FOUR]


#include "stream.h"
#include "coin.hh"

char *coin_name[] = {"penny", "nickel", "dime", "quarter"} ; 

/*
 * convenient look up table
 * keeps from having to duplicate case statements any
 * time you need to work with unit data member
 */
static struct 
{
  coin_type  kind;
  double     amount;
} table [] =
    {
      {penny,   0.01},
      {nickel,  0.05},
      {dime,    0.10},
      {quarter, 0.25},
      {quarter, 0.0},		/* end of the table */
    };
 
coin::coin(coin_type type)
{
  unit = type;
  for (int i = 0; table[i].amount != 0.0 && unit != table[i].kind; i++)
    ;
  amount = table[i].amount;
}


ostream& operator << (ostream &os, coin &c)
{
  os << coin_name[c.unit];
  return os;
}


int coin::found(const coin &other)
{
  return (unit == other.unit);
}

  

[LISTING FIVE]


/*
 * this is the output from CPP
 * g++ -E test1.cc
 *
 * I reformated the output to make it 
 * easier to read
 */

typedef int (coin::*  coinPTAMF   )(coin &); 
class coinGenList   ; 
class coinGenIter   ;  
      
class coinGenItem    
{ 
  coinGenItem    *next; 
  coin &item; 

  coinGenItem   (coin &i) : item(i)	
    {next = 0 ;} 
  coinGenItem   (coin &i, coinGenItem    *n) : item(i) 
    {next = n; } ~coinGenItem   () 
      {;}	
  friend coinGenList   ; 
  friend coinGenIter   ; 
}	 ;        

class coinGenList   	
{	
  coinGenItem    *hd;	

 public:	
  coinGenList   (coinGenItem    *n = 0 )	
    { hd = n;} 
  coinGenList   (const coin &i) 
    {hd = 0 ; insert(i);} 
  ~coinGenList   ()	
    {Clear();}	
  void Clear(void)	
    {	
      coinGenItem    *pt;	

      while (hd)	
	{	
	  pt = hd;	
	  hd = hd->next;	
	  delete pt;	
	}	
    }	
  coinGenList   (const coinGenList    &seq) 
    {hd = seq.hd;} 
  coinGenList    operator = (const coinGenList    &other)	
    {	hd = other.hd; return *this;	}	
  void insert(coin &i)
    { hd = new coinGenItem   (i, hd); } 
  void append(coin &i)	
    {	
      for (coinGenItem    *pt = hd; pt && pt ->next; pt = pt->next)	
	;	
      if (pt) 
	{	
	  coinGenItem    *tmp = new coinGenItem   (i); 
	  pt->next = tmp;	
	} 
      else 
	insert(i);	
    } 
  void removeItem(  coinPTAMF    found, coin &obj) 
    {	
      coinGenItem    *prev, *rem;	

      prev = 0 ;	
      rem = hd;	
      while( rem && !(obj.*found)(rem->item) )	
	{	
	  prev = rem;	
	  rem = rem->next;	
	}	
      if (rem) 
	{	
	  if (prev)	
	    prev->next = rem->next;	
	  else	
	    hd = rem->next;	
	  delete rem;	
	}	
    }	
  friend coinGenIter   ;	
}  ;	       

class coinGenIter    
{ 
  coinGenItem    *current;	

 public: 
  coinGenIter   (coinGenList    &ilist)	
    { current = ilist.hd; }	
  coinGenIter   (coinGenIter    &other)	
    { current = other.current; } 
  ~coinGenIter   () {;} 
  coinGenIter    operator = (coinGenList    &ilist) 
    { current = ilist.hd; return *this; } 
  coin *operator()() 
    {	
      if (current) 
	{ 
	  coinGenItem    *tmp = current; 
	  current = current->next; 
	  return &tmp->item; 
	} return 0 ; 
    }	
}   ;

 



void displayAndTotal(coinGenIter    next_coin);
     
main()
{
   
  coin c1 = penny;
  coin c2 = nickel;
  coin c3 = dime;
  coin c4 = quarter;

   
  coinGenList    list_of_coins;
  list_of_coins.append(c1);
  list_of_coins.append(c2);
  list_of_coins.append(c3);
  list_of_coins.append(c4);

   
  displayAndTotal(list_of_coins);

   
  cout << "\n\n list after removing coin c2 \n";
  list_of_coins.removeItem(&coin::found, c2);
  displayAndTotal(list_of_coins);
  

   


  cout << "\n\n coin c2 still exists, it was only removed from the list \n";
  cout << "coin: " << c2;


# 78 "test1.cc"

}

 







void displayAndTotal(coinGenIter    next_coin)
{
  double total = 0.0;
  coin *tmp;
  
  while ((tmp = next_coin()))
    {
       


      total += *tmp;
       


      cout << "coin: " << *tmp << "\ttotal: " << total <<"\n";
    }
}







[MAKEFILE]

CC= 	g++
OBJS=	coin.o test1.o
SRCS = coin.cc test1.cc
LIBS= 	-lg++ -lm
INCLUDE= -I/n/catserv/usr1/tools/sun4/usr/local/lib/g++-include

.SUFFIXES: .cc

.cc.o: 
	$(CC) -c -g $<

coinTest : $(OBJS) coin.hh genericlt.hh
	$(CC) -o $@ -g $(OBJS) $(LIBS)

clean :
	rm -f coinTest *.o


#
# notes
#

#
#  $@ the name of the current target
#

#
# $< the name of a dependency file, derived as if selected
# for use with an implicit rule
#

depend : 
	makedepend -- $(CFLAGS) -- $(INCLUDE) -- $(SRCS)
# DO NOT DELETE THIS LINE -- make depend depends on it.

coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stream.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/ostream.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/File.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/builtin.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stddef.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/std.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stdio.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/math.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/values.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/streambuf.h
coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/istream.h
coin.o: coin.hh
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stream.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/ostream.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/File.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/builtin.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stddef.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/std.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stdio.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/math.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/values.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/streambuf.h
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/istream.h
test1.o: coin.hh genericlt.hh
test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/generic.h