Category : Files from Magazines
Archive   : DDJ8_91.ZIP
Filename : CPPCONT.ASC

_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

#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
#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