home *** CD-ROM | disk | FTP | other *** search
/ Computer Select (Limited Edition) / Computer Select.iso / dobbs / v16n08 / cppcont.asc < prev    next >
Encoding:
Text File  |  1991-07-23  |  15.3 KB  |  668 lines
  1. _GENERIC CONTAINERS IN C++_
  2. by Andrew Davidson
  3.  
  4.  
  5. /*
  6.  * Generic list
  7.  *
  8.  * by A. E. Davidson 12/90
  9.  *
  10.  * Overview
  11.  *
  12.  * USES
  13.  * to declare a generic list of class
  14.  * foo items and a generic list of class 
  15.  * bar items
  16.  *
  17.  * #include "genriclt.hh"
  18.  * DeclareList(Foo);
  19.  * DeclareList(Bar);
  20.  *
  21.  * main()
  22.  * {
  23.  * class foo;
  24.  * class bar;
  25.  * GenList(foo) genListOfFoo;
  26.  * GenList(bar) genListOfBar;
  27.  * GenIter
  28.  *
  29.  * REQUIREMENTS / ASSUMPTIONS
  30.  * The generic list does not manage
  31.  * the items memory. It is up to the
  32.  * user to free them
  33.  *
  34.  * the function GenList::RemoveItem()
  35.  * takes a pointer to a member function.
  36.  * this funciton should return true is found
  37.  * else false. GenList::RemoveItem will not 
  38.  * compile on my machine if the member 
  39.  * fuction is inlined. it gives a signal 6 error message
  40.  *
  41.  * NOTES
  42.  * never use new to create a list or an iter!
  43.  *
  44.  *
  45.  */
  46.  
  47. #include <generic.h>
  48.  
  49. #ifndef GENERIC_LIST_HH
  50. #define GENERIC_LIST_HH
  51.  
  52. /*
  53.  * these macro's should be used 
  54.  * any where you need to reffer to
  55.  * the generic list, item, or iter classes
  56.  *
  57.  * PTAMF: Pointer to a Member Function
  58.  */
  59. #define PTAMF(CLASS_TAG)   name2(CLASS_TAG,PTAMF)
  60. #define GenItem(CLASS_TAG) name2(CLASS_TAG,GenItem)
  61. #define GenList(CLASS_TAG) name2(CLASS_TAG,GenList)
  62. #define GenIter(CLASS_TAG) name2(CLASS_TAG,GenIter)
  63.  
  64. /*----------------------------- class Item ---------------------------*/
  65. /*
  66.  * GenItem(CLASS_TAG) is a private
  67.  * class. It can only be created by
  68.  * be the member functions of GenList(CLASS_TAG)
  69.  * and GenIter(CLASS_TAG)
  70.  */
  71.  
  72. #define GenItemdeclare(CLASS_TAG)                           \
  73. class GenItem(CLASS_TAG)                          \
  74. {                                      \
  75.   GenItem(CLASS_TAG) *next;                                 \
  76.   CLASS_TAG &item;                                     \
  77.   GenItem(CLASS_TAG)(CLASS_TAG &i) : item(i)                 \
  78.     {next = NULL;}                              \
  79.   GenItem(CLASS_TAG)(CLASS_TAG &i, GenItem(CLASS_TAG) *n) : item(i)      \
  80.     {next = n; }                              \
  81.   ~GenItem(CLASS_TAG)()                          \
  82.     {;}                                            \
  83.   friend GenList(CLASS_TAG);                                 \
  84.   friend GenIter(CLASS_TAG);                          \
  85. }    
  86.  
  87. /*---------------------------- class List ---------------------------*/    
  88. #define GenListdeclare(CLASS_TAG)                              \
  89. class GenList(CLASS_TAG)                                \
  90. {                                            \
  91.   GenItem(CLASS_TAG) *hd;                                \
  92.  public:                                        \
  93.   GenList(CLASS_TAG)(GenItem(CLASS_TAG) *n = NULL)             \
  94.     { hd = n;}                                   \
  95.   GenList(CLASS_TAG)(const CLASS_TAG &i)                  \
  96.     {hd = NULL; insert(i);}                                 \
  97.   ~GenList(CLASS_TAG)()                             \
  98.     {Clear();}                                  \
  99.   void Clear(void)                             \
  100.     {                                            \
  101.       GenItem(CLASS_TAG) *pt;                                \
  102.       while (hd)                                    \
  103.     {                                        \
  104.       pt = hd;                                    \
  105.       hd = hd->next;                                \
  106.       delete pt;                                    \
  107.     }                                        \
  108.     }                                                   \
  109.   GenList(CLASS_TAG)(const GenList(CLASS_TAG) &seq) {hd = seq.hd;}      \
  110.   GenList(CLASS_TAG) operator = (const GenList(CLASS_TAG) &other)     \
  111.     {                                     \
  112.       hd = other.hd;                              \
  113.       return *this;                                    \
  114.     }                                     \
  115.   void insert(CLASS_TAG &i){ hd = new GenItem(CLASS_TAG)(i, hd); }      \
  116.   void append(CLASS_TAG &i)                         \
  117.     {                                     \
  118.       for (GenItem(CLASS_TAG) *pt = hd; pt && pt ->next; pt = pt->next)     \
  119.     ;                                 \
  120.       if (pt)                                  \
  121.     {                                 \
  122.       GenItem(CLASS_TAG) *tmp = new GenItem(CLASS_TAG)(i);          \
  123.       pt->next = tmp;                         \
  124.     }                                    \
  125.       else insert(i);                             \
  126.     }                                      \
  127.                                      \
  128.   void removeItem(PTAMF(CLASS_TAG) found, CLASS_TAG &obj)               \
  129.     {                                     \
  130.       GenItem(CLASS_TAG) *prev, *rem;                     \
  131.                                            \
  132.       prev = NULL;                             \
  133.       rem = hd;                                 \
  134.       while( rem && !(obj.*found)(rem->item) )                 \
  135.         {                                 \
  136.       prev = rem;                             \
  137.       rem = rem->next;                         \
  138.     }                                 \
  139.       if (rem)                                    \
  140.         {                                 \
  141.           if (prev)                             \
  142.         prev->next = rem->next;                     \
  143.           else                             \
  144.         hd = rem->next;                         \
  145.           delete rem;                                \
  146.         }                                 \
  147.     }                                     \
  148.   friend GenIter(CLASS_TAG);                         \
  149. }
  150.  
  151.  
  152.  
  153. /*------------------------------- class Iter ---------------------------*/
  154.   /* 
  155.    * interate over entire list 
  156.    * CLASS_TAG *operator()()
  157.    */
  158.   
  159. #define GenIterdeclare(CLASS_TAG)                     \
  160. class GenIter(CLASS_TAG)                         \
  161. {                                      \
  162.   GenItem(CLASS_TAG) *current;                        \
  163.  public:                                 \
  164.   GenIter(CLASS_TAG)(GenList(CLASS_TAG) &ilist)                \
  165.     { current = ilist.hd; }                        \
  166.   GenIter(CLASS_TAG)(GenIter(CLASS_TAG) &other)                \
  167.     { current = other.current; }                         \
  168.   ~GenIter(CLASS_TAG)()                         \
  169.     {;}                                 \
  170.   GenIter(CLASS_TAG) operator = (GenList(CLASS_TAG) &ilist)         \
  171.     { current = ilist.hd; return *this; }                 \
  172.    CLASS_TAG *operator()()                         \
  173.     {                                    \
  174.       if (current)                             \
  175.     {                                 \
  176.       GenItem(CLASS_TAG) *tmp = current;                 \
  177.       current = current->next;                     \
  178.       return &tmp->item;                         \
  179.     }                                 \
  180.       return NULL;                             \
  181.     }                                    \
  182. } 
  183.                 
  184.  
  185. /*
  186.  * macro that create all the generic types
  187.  * provided for ease of uses
  188.  *
  189.  * for some unknown reason my compiler can't handle a 
  190.  * function prameter that is a pointer to a member function
  191.  * It can deal with it if the pointer is declared using 
  192.  * a typedef
  193.  */
  194. #define DeclareList(CLASS_TAG)     \
  195.   typedef int (CLASS_TAG::*PTAMF(CLASS_TAG))(CLASS_TAG &); \
  196.   class GenList(CLASS_TAG);     \
  197.   class GenIter(CLASS_TAG);     \
  198.   declare(GenItem,CLASS_TAG);     \
  199.   declare(GenList,CLASS_TAG);    \
  200.   declare(GenIter,CLASS_TAG)
  201.  
  202. #endif
  203.  
  204.  
  205.  
  206.  
  207. [LISTING TWO]
  208.  
  209.  
  210. /*
  211.  * test1.cc
  212.  *
  213.  * by A. E. Davidson
  214.  *
  215.  * Provides a driver to test the generic list
  216.  */
  217.  
  218. #include <stream.h>
  219. #include "coin.hh"
  220. #include "genericl.hh"
  221.  
  222. /*
  223.  * use the declare macros to 
  224.  * allow creation of list of desired types
  225.  */
  226.  
  227. DeclareList(coin);
  228.  
  229. /*
  230.  * proto typing function using the generic list
  231.  * stuff must be done after DeclareList()
  232.  */
  233. void displayAndTotal(GenIter(coin) next_coin);
  234.      
  235. main()
  236. {
  237.   /*--- create some coins -------*/
  238.   coin c1 = penny;
  239.   coin c2 = nickel;
  240.   coin c3 = dime;
  241.   coin c4 = quarter;
  242.  
  243.   /*------ create a list of coins -----*/
  244.   GenList(coin) list_of_coins;
  245.   list_of_coins.append(c1);
  246.   list_of_coins.append(c2);
  247.   list_of_coins.append(c3);
  248.   list_of_coins.append(c4);
  249.  
  250.   /*------- display the list of coins and there total ------*/
  251.   displayAndTotal(list_of_coins);
  252.  
  253.   /*-------------- remove one of the coins --------------*/
  254.   cout << "\n\n list after removing coin c2 \n";
  255.   list_of_coins.removeItem(&coin::found, c2);
  256.   displayAndTotal(list_of_coins);
  257.   
  258.  
  259.   /*
  260.    * rember: c2 has been removed from the list but it still exists
  261.    */
  262.   cout << "\n\n coin c2 still exists, it was only removed from the list \n";
  263.   cout << "coin: " << c2;
  264.  
  265.  
  266. #ifdef NEVER 
  267.  
  268.   /* 
  269.    * this is example shows a design flaw
  270.    * with the generic list assignment operator
  271.    *
  272.    * if you delete an object but do not remove it 
  273.    * from the list first you will get a core dump.
  274.    * The list will contain a dangling reference
  275.    *
  276.    * this is becuase I chose to implement the
  277.    * the list using references instead of copying
  278.    * the objects. See the discusion at the end of the
  279.    * article
  280.    */
  281.   coin *c5 = new coin(quarter);
  282.  
  283.   list_of_coins.append(*c5);
  284.   delete c5;
  285.   displayAndTotal(list_of_coins);
  286.  
  287. #endif  
  288. }
  289.  
  290. /*
  291.  * this function illustrates
  292.  * how to use the GenIter class
  293.  *
  294.  * notice that the parmeter list expect
  295.  * an inter object, but I always pass a list
  296.  * object
  297.  */
  298. void displayAndTotal(GenIter(coin) next_coin)
  299. {
  300.   double total = 0.0;
  301.   coin *tmp;
  302.   
  303.   while ((tmp = next_coin()))
  304.     {
  305.       /* 
  306.        * coins know how to convert themselves to doubles
  307.        */
  308.       total += *tmp;
  309.       /*
  310.        * coins also know how to display themselves
  311.        */
  312.       cout << "coin: " << *tmp << "\ttotal: " << total <<"\n";
  313.     }
  314. }
  315.  
  316.  
  317. [LSITING THREE]
  318.  
  319. /*
  320.  * coin class
  321.  *
  322.  * by A. E. Davidson
  323.  *
  324.  * USES
  325.  * provides a simple class that can be 
  326.  * used to illistrate the operation of
  327.  * the generic list
  328.  *
  329.  * a coin may be a penny, nickel, dime, or quarter
  330.  */
  331.  
  332. #ifndef COIN_HH
  333. #define COIN_HH
  334.  
  335. enum coin_type {penny, nickel, dime, quarter}; 
  336.  
  337.  
  338. class coin 
  339. {
  340.   coin_type unit;
  341.   double    amount;
  342.   
  343.  public:
  344.   coin()
  345.     {unit = penny; amount = 0.01;} 
  346.   coin( coin_type type);
  347.   coin(const coin &other)
  348.     {unit = other.unit; amount = other.amount;} 
  349.   ~coin(){;}
  350.   coin& operator = (const coin &other)
  351.     { unit = other.unit; amount = other.amount;} 
  352.   friend ostream& operator << (ostream &os, coin &c);
  353.   operator double () 
  354.     {return amount;} 
  355.  
  356.   /*
  357.    * this function is intended to be
  358.    * used with GenList(CLASS_TAG)::removeItem()
  359.    * I get a compile error if I try to inline this 
  360.    * function
  361.    */
  362.   int found(const coin &other);
  363. };
  364.  
  365.  
  366. #endif
  367.  
  368.  
  369. [LISTING FOUR]
  370.  
  371.  
  372. #include "stream.h"
  373. #include "coin.hh"
  374.  
  375. char *coin_name[] = {"penny", "nickel", "dime", "quarter"} ; 
  376.  
  377. /*
  378.  * convenient look up table
  379.  * keeps from having to duplicate case statements any
  380.  * time you need to work with unit data member
  381.  */
  382. static struct 
  383. {
  384.   coin_type  kind;
  385.   double     amount;
  386. } table [] =
  387.     {
  388.       {penny,   0.01},
  389.       {nickel,  0.05},
  390.       {dime,    0.10},
  391.       {quarter, 0.25},
  392.       {quarter, 0.0},        /* end of the table */
  393.     };
  394.  
  395. coin::coin(coin_type type)
  396. {
  397.   unit = type;
  398.   for (int i = 0; table[i].amount != 0.0 && unit != table[i].kind; i++)
  399.     ;
  400.   amount = table[i].amount;
  401. }
  402.  
  403.  
  404. ostream& operator << (ostream &os, coin &c)
  405. {
  406.   os << coin_name[c.unit];
  407.   return os;
  408. }
  409.  
  410.  
  411. int coin::found(const coin &other)
  412. {
  413.   return (unit == other.unit);
  414. }
  415.  
  416.   
  417.  
  418. [LISTING FIVE]
  419.  
  420.  
  421. /*
  422.  * this is the output from CPP
  423.  * g++ -E test1.cc
  424.  *
  425.  * I reformated the output to make it 
  426.  * easier to read
  427.  */
  428.  
  429. typedef int (coin::*  coinPTAMF   )(coin &); 
  430. class coinGenList   ; 
  431. class coinGenIter   ;  
  432.       
  433. class coinGenItem    
  434. { 
  435.   coinGenItem    *next; 
  436.   coin &item; 
  437.  
  438.   coinGenItem   (coin &i) : item(i)    
  439.     {next = 0 ;} 
  440.   coinGenItem   (coin &i, coinGenItem    *n) : item(i) 
  441.     {next = n; } ~coinGenItem   () 
  442.       {;}    
  443.   friend coinGenList   ; 
  444.   friend coinGenIter   ; 
  445. }     ;        
  446.  
  447. class coinGenList       
  448. {    
  449.   coinGenItem    *hd;    
  450.  
  451.  public:    
  452.   coinGenList   (coinGenItem    *n = 0 )    
  453.     { hd = n;} 
  454.   coinGenList   (const coin &i) 
  455.     {hd = 0 ; insert(i);} 
  456.   ~coinGenList   ()    
  457.     {Clear();}    
  458.   void Clear(void)    
  459.     {    
  460.       coinGenItem    *pt;    
  461.  
  462.       while (hd)    
  463.     {    
  464.       pt = hd;    
  465.       hd = hd->next;    
  466.       delete pt;    
  467.     }    
  468.     }    
  469.   coinGenList   (const coinGenList    &seq) 
  470.     {hd = seq.hd;} 
  471.   coinGenList    operator = (const coinGenList    &other)    
  472.     {    hd = other.hd; return *this;    }    
  473.   void insert(coin &i)
  474.     { hd = new coinGenItem   (i, hd); } 
  475.   void append(coin &i)    
  476.     {    
  477.       for (coinGenItem    *pt = hd; pt && pt ->next; pt = pt->next)    
  478.     ;    
  479.       if (pt) 
  480.     {    
  481.       coinGenItem    *tmp = new coinGenItem   (i); 
  482.       pt->next = tmp;    
  483.     } 
  484.       else 
  485.     insert(i);    
  486.     } 
  487.   void removeItem(  coinPTAMF    found, coin &obj) 
  488.     {    
  489.       coinGenItem    *prev, *rem;    
  490.  
  491.       prev = 0 ;    
  492.       rem = hd;    
  493.       while( rem && !(obj.*found)(rem->item) )    
  494.     {    
  495.       prev = rem;    
  496.       rem = rem->next;    
  497.     }    
  498.       if (rem) 
  499.     {    
  500.       if (prev)    
  501.         prev->next = rem->next;    
  502.       else    
  503.         hd = rem->next;    
  504.       delete rem;    
  505.     }    
  506.     }    
  507.   friend coinGenIter   ;    
  508. }  ;           
  509.  
  510. class coinGenIter    
  511. { 
  512.   coinGenItem    *current;    
  513.  
  514.  public: 
  515.   coinGenIter   (coinGenList    &ilist)    
  516.     { current = ilist.hd; }    
  517.   coinGenIter   (coinGenIter    &other)    
  518.     { current = other.current; } 
  519.   ~coinGenIter   () {;} 
  520.   coinGenIter    operator = (coinGenList    &ilist) 
  521.     { current = ilist.hd; return *this; } 
  522.   coin *operator()() 
  523.     {    
  524.       if (current) 
  525.     { 
  526.       coinGenItem    *tmp = current; 
  527.       current = current->next; 
  528.       return &tmp->item; 
  529.     } return 0 ; 
  530.     }    
  531. }   ;
  532.  
  533.  
  534.  
  535.  
  536.  
  537. void displayAndTotal(coinGenIter    next_coin);
  538.      
  539. main()
  540. {
  541.    
  542.   coin c1 = penny;
  543.   coin c2 = nickel;
  544.   coin c3 = dime;
  545.   coin c4 = quarter;
  546.  
  547.    
  548.   coinGenList    list_of_coins;
  549.   list_of_coins.append(c1);
  550.   list_of_coins.append(c2);
  551.   list_of_coins.append(c3);
  552.   list_of_coins.append(c4);
  553.  
  554.    
  555.   displayAndTotal(list_of_coins);
  556.  
  557.    
  558.   cout << "\n\n list after removing coin c2 \n";
  559.   list_of_coins.removeItem(&coin::found, c2);
  560.   displayAndTotal(list_of_coins);
  561.   
  562.  
  563.    
  564.  
  565.  
  566.   cout << "\n\n coin c2 still exists, it was only removed from the list \n";
  567.   cout << "coin: " << c2;
  568.  
  569.  
  570. # 78 "test1.cc"
  571.  
  572. }
  573.  
  574.  
  575.  
  576.  
  577.  
  578.  
  579.  
  580.  
  581.  
  582. void displayAndTotal(coinGenIter    next_coin)
  583. {
  584.   double total = 0.0;
  585.   coin *tmp;
  586.   
  587.   while ((tmp = next_coin()))
  588.     {
  589.        
  590.  
  591.  
  592.       total += *tmp;
  593.        
  594.  
  595.  
  596.       cout << "coin: " << *tmp << "\ttotal: " << total <<"\n";
  597.     }
  598. }
  599.  
  600.  
  601.  
  602.  
  603.  
  604.  
  605.  
  606. [MAKEFILE]
  607.  
  608. CC=     g++
  609. OBJS=    coin.o test1.o
  610. SRCS = coin.cc test1.cc
  611. LIBS=     -lg++ -lm
  612. INCLUDE= -I/n/catserv/usr1/tools/sun4/usr/local/lib/g++-include
  613.  
  614. .SUFFIXES: .cc
  615.  
  616. .cc.o: 
  617.     $(CC) -c -g $<
  618.  
  619. coinTest : $(OBJS) coin.hh genericlt.hh
  620.     $(CC) -o $@ -g $(OBJS) $(LIBS)
  621.  
  622. clean :
  623.     rm -f coinTest *.o
  624.  
  625.  
  626. #
  627. # notes
  628. #
  629.  
  630. #
  631. #  $@ the name of the current target
  632. #
  633.  
  634. #
  635. # $< the name of a dependency file, derived as if selected
  636. # for use with an implicit rule
  637. #
  638.  
  639. depend : 
  640.     makedepend -- $(CFLAGS) -- $(INCLUDE) -- $(SRCS)
  641. # DO NOT DELETE THIS LINE -- make depend depends on it.
  642.  
  643. coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stream.h
  644. coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/ostream.h
  645. coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/File.h
  646. coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/builtin.h
  647. coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stddef.h
  648. coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/std.h
  649. coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stdio.h
  650. coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/math.h
  651. coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/values.h
  652. coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/streambuf.h
  653. coin.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/istream.h
  654. coin.o: coin.hh
  655. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stream.h
  656. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/ostream.h
  657. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/File.h
  658. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/builtin.h
  659. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stddef.h
  660. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/std.h
  661. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/stdio.h
  662. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/math.h
  663. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/values.h
  664. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/streambuf.h
  665. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/istream.h
  666. test1.o: coin.hh genericlt.hh
  667. test1.o: /n/catserv/usr1/tools/sun4/usr/local/lib/g++-include/generic.h
  668.