home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 6.ddi / MWHC.006 / U2 < prev    next >
Encoding:
Text File  |  1992-06-07  |  12.4 KB  |  414 lines
  1. #ifndef __RWTVSLIST_H__
  2. #define __RWTVSLIST_H__
  3. pragma push_align_members(64);
  4.  
  5. /*
  6.  * RWTValSlist<T>: A non-intrusive singly-linked list of values of type T.
  7.  *
  8.  * $Header:   E:/vcs/rw/tvslist.h_v   1.6   19 Mar 1992 11:26:00   KEFFER  $
  9.  *
  10.  ****************************************************************************
  11.  *
  12.  * Rogue Wave Software, Inc.
  13.  * P.O. Box 2328
  14.  * Corvallis, OR 97339
  15.  *
  16.  * Copyright (C) 1992. This software is subject to copyright 
  17.  * protection under the laws of the United States and other countries.
  18.  *
  19.  ***************************************************************************
  20.  *
  21.  * Stores a *copy* of the inserted item into the collection.
  22.  *
  23.  * Assumes that T has:
  24.  *   - well-defined copy constructor (T::T(const T&) or equiv.);
  25.  *   - well-defined assignment operator (T::operator=(const T&) or equiv.);
  26.  *   - well-defined equality semantics (T::operator==(const T&)).
  27.  *
  28.  * Note that while these are automatically defined for builtin types
  29.  * (such as "int", "double", or any pointer), you may need to provide
  30.  * appropriate operators for your own classes, particularly those with
  31.  * constructors and/or pointers to other objects.
  32.  *
  33.  ***************************************************************************
  34.  *
  35.  * $Log:   E:/vcs/rw/tvslist.h_v  $
  36.  * 
  37.  *    Rev 1.6   19 Mar 1992 11:26:00   KEFFER
  38.  * 
  39.  *    Rev 1.0   02 Mar 1992 16:10:54   KEFFER
  40.  * Initial revision.
  41.  *
  42.  */
  43.  
  44. //$DECLARE_TEMPLATE
  45.  
  46. #include "rw/tislist.h"
  47.  
  48. template <class T> class RWExport RWTValSlistIterator;
  49.  
  50.  
  51. /****************************************************************
  52.  *                                *
  53.  *        Declarations for RWTValSlink<T>            *
  54.  *                                *
  55.  ****************************************************************/
  56.  
  57. /*
  58.  * This is the actual link that is stored in the linked list.
  59.  * It includes data of type "T".
  60.  */
  61. template <class T> struct RWExport RWTValSlink : public RWIsvSlink {
  62.   T        _info;
  63.   RWTValSlink(T a) : _info(a) { }
  64. };
  65.  
  66.  
  67. /****************************************************************
  68.  *                                *
  69.  *        Declarations for RWTValSlist<T>            *
  70.  *                                *
  71.  ****************************************************************/
  72.  
  73. template <class T> class RWExport RWTValSlist : private RWTIsvSlist< RWTValSlink<T> > {
  74.  
  75.   friend class RWExport RWTValSlistIterator<T> ;
  76.  
  77.   // For convenience in what follows:
  78.   typedef RWTValSlink<T>    LINK;
  79.   typedef RWTIsvSlist<LINK>    BASE;
  80.  
  81. protected:    // Member functions
  82.  
  83.   T        peel(LINK* link);    // Extract "_info" out of link; throw away link
  84.  
  85.   // To repackage tester functions for the base class:
  86.   static RWBoolean    eqTestFun(const LINK* link, void* p);
  87.   static RWBoolean    valTestFun(const LINK* link, void* p);
  88.  
  89. public:
  90.  
  91.   RWTValSlist() { }
  92.   RWTValSlist(const RWTValSlist<T>&);
  93.   ~RWTValSlist() { clear(); }
  94.  
  95.   // Operators:
  96.   RWTValSlist&    operator=(const RWTValSlist<T>&);
  97.   T&        operator[](int i)            {return (T&)BASE::at(i)->_info;}
  98.   T        operator[](int i) const            {return BASE::at(i)->_info;}
  99.  
  100.   /********************* Member functions **************************/
  101.   void        append(T a)                {BASE::append(new LINK(a));}
  102.   void        apply(void (*applyFun)(T, void*), void*);
  103.   T&        at(int i)                {return (T&)BASE::at(i)->_info;}
  104.   T        at(int i) const                {return BASE::at(i)->_info;}
  105.   void        clear()                    {BASE::clearAndDestroy();}
  106.   RWBoolean    contains(RWBoolean (*testFun)(T, void*), void*) const;
  107.   RWBoolean    contains(T a) const;
  108.   BASE::entries;
  109.   RWBoolean    find(T a, T& k) const;            // Find first occurrence
  110.   RWBoolean    find(RWBoolean (*testFun)(T, void*), void*, T& k) const;
  111.   T        first() const                {return BASE::first()->_info;}
  112.   T        get()                    {return peel(BASE::get());}
  113.   int        index(T a) const;
  114.   int        index(RWBoolean (*testFun)(T, void*), void*) const;
  115.   void         insert(T a)                {BASE::append(new LINK(a));}
  116.   void        insertAfter(int i, T a)            {BASE::insertAfter(i, new LINK(a));}
  117.   void        insertAt(int i, T a)            {BASE::insertAt(i, new LINK(a));}
  118.   BASE::isEmpty;
  119.   T        last() const                {return BASE::last()->_info;}
  120.   unsigned    occurrencesOf(T a) const;
  121.   unsigned    occurrencesOf(RWBoolean (*testFun)(T, void*), void*) const;
  122.   void        prepend(T a)                {BASE::prepend(new LINK(a));}
  123.   RWBoolean    remove(T a);                    // Remove first occurrence
  124.   RWBoolean    remove(RWBoolean (*testFun)(T, void*), void*);    // Remove first occurrence
  125.   unsigned    removeAll(T a);
  126.   unsigned    removeAll(RWBoolean (*testFun)(T, void*), void*);
  127.   T        removeAt(int i)                {return peel(BASE::removeAt(i));}
  128.   T         removeFirst()                {return peel(BASE::removeFirst());}
  129.   T        removeLast()                {return peel(BASE::removeLast());}
  130. };
  131.  
  132. /****************************************************************
  133.  *                                *
  134.  *        Declarations for RWTValSlistIterator<T>        *
  135.  *                                *
  136.  ****************************************************************/
  137.  
  138. template <class T> class RWExport RWTValSlistIterator : private RWTIsvSlistIterator< RWTValSlink<T> > {
  139.  
  140.   // For convenience in what follows:
  141.   typedef RWTValSlist<T> LIST;
  142.   typedef RWTValSlink<T> LINK;
  143.   typedef RWTIsvSlistIterator<LINK> BASE;
  144.  
  145.   // Disallow postfix increment.  Unless we hide it, some compilers will
  146.   // substitute the prefix increment operator in its place.
  147.   RWBoolean        operator++(int);
  148.  
  149. public:
  150.  
  151.   // Constructor: starts with iterator positioned at last link.
  152.   RWTValSlistIterator(RWTValSlist<T>& s) : RWTIsvSlistIterator<LINK>(s) { }
  153.  
  154.   // Operators:
  155.   RWBoolean    operator++()        {return BASE::operator++();}
  156.   BASE::operator+=;            // Advance iterator n links and test
  157.  
  158.   LIST*        container() const    {return (LIST*)BASE::container();}
  159.   RWBoolean    findNext(T a);
  160.   RWBoolean    findNext(RWBoolean (*testFun)(T, void*), void*);
  161.   void        insertAfterPoint(T a)    {BASE::insertAfterPoint(new LINK(a));}
  162.   T        key() const        {return BASE::key()->_info;}
  163.   RWBoolean     remove();        // Remove item at cursor
  164.   RWBoolean    removeNext(T);
  165.   RWBoolean    removeNext(RWBoolean (*testFun)(T, void*), void*);
  166.   void        reset()            {BASE::reset();}
  167.   void        reset(LIST& s)        {BASE::reset(s);}
  168. };
  169.  
  170.  
  171. //$IMPLEMENT_TEMPLATE
  172.  
  173. #include "rw/tvtestr.h"
  174.  
  175. /****************************************************************
  176.  *                                *
  177.  *        Definitions for RWTValSlist<T>            *
  178.  *                                *
  179.  ****************************************************************/
  180.  
  181. // Used to test for equality with an object.
  182. template <class T> RWBoolean
  183. RWTValSlist<T>::eqTestFun(const RWTValSlink<T>* link, void* p)
  184. {
  185.   RWPRECONDITION(link);
  186.   RWPRECONDITION(p);
  187.   const T* t = (const T*)p;
  188.   return link->_info == *t;
  189. }
  190.   
  191. // Function to wrap a user-supplied tester function such that it
  192. // can be used by the base class
  193. template <class T> RWBoolean
  194. RWTValSlist<T>::valTestFun(const RWTValSlink<T>* link, void* p)
  195. {
  196.   RWPRECONDITION(link);
  197.   RWPRECONDITION(p);
  198.   RWTValTester<T>* c = (RWTValTester<T>*)p;
  199.   return (*c->_testFun)(link->_info, c->_data);
  200. }
  201.   
  202. // Copy constructor:
  203. template <class T> RWTValSlist<T>::RWTValSlist(const RWTValSlist<T>& s)
  204. {
  205.   // Construct an iterator, casting away "constness"
  206.   // (which we promise to honor anyway):
  207.   RWTValSlistIterator<T> next((RWTValSlist<T>&)s);
  208.   while (++next) append(next.key());
  209. }
  210.  
  211. template <class T> RWTValSlist<T>&
  212. RWTValSlist<T>::operator=(const RWTValSlist<T>& s)
  213. {
  214.   if (this!=&s){
  215.     clear();
  216.     // Construct an iterator, casting away "constness"
  217.     // (which we promise to honor anyway):
  218.     RWTValSlistIterator<T> next((RWTValSlist<T>&)s);
  219.     while (++next) append(next.key());
  220.   }
  221.   return *this;
  222. }
  223.  
  224. template <class T> void
  225. RWTValSlist<T>::apply(void (*applyFun)(T, void*), void* a)
  226. {
  227.   RWIsvSlink* link = _lastSlink;
  228.   if (link) {
  229.     do {
  230.       link = link->next();        // Advance to next link
  231.       (*applyFun)(((RWTValSlink<T>*)link)->_info, a);    // Apply the function
  232.     } while (link != _lastSlink);
  233.   }
  234. }
  235.  
  236. template <class T> RWBoolean
  237. RWTValSlist<T>::contains(RWBoolean (*testFun)(T, void*), void* a) const
  238. {
  239.   // Construct an iterator, casting away "constness" (which we promise to honor):
  240.   RWTValSlistIterator<T> iter(*(RWTValSlist<T>*)this);
  241.   return iter.findNext(testFun, a);
  242. }
  243.   
  244. template <class T> RWBoolean
  245. RWTValSlist<T>::contains(T val) const
  246. {
  247.   // Construct an iterator, casting away "constness" (which we promise to honor):
  248.   RWTValSlistIterator<T> iter(*(RWTValSlist<T>*)this);
  249.   return iter.findNext(val);
  250. }
  251.  
  252. template <class T> RWBoolean
  253. RWTValSlist<T>::find(T val, T& k) const
  254. {
  255.   // Construct an iterator, casting away "constness" (which we promise to honor):
  256.   RWTValSlistIterator<T> iter(*(RWTValSlist<T>*)this);
  257.   RWBoolean ret = iter.findNext(val);
  258.   if (ret) k = iter.key();
  259.   return ret;
  260. }
  261.  
  262. template <class T> RWBoolean
  263. RWTValSlist<T>::find(RWBoolean (*testFun)(T, void*), void* a, T& k) const
  264. {
  265.   // Construct an iterator, casting away "constness" (which we promise to honor):
  266.   RWTValSlistIterator<T> iter(*(RWTValSlist<T>*)this);
  267.   RWBoolean ret = iter.findNext(testFun, a);
  268.   if (ret) k = iter.key();
  269.   return ret;
  270. }
  271.  
  272. template <class T> int
  273. RWTValSlist<T>::index(T a) const
  274. {
  275.   return BASE::index(eqTestFun, &a);
  276. }
  277.  
  278. template <class T> int
  279. RWTValSlist<T>::index(RWBoolean (*testFun)(T, void*), void* a) const
  280. {
  281.   RWTValTester<T> capsule(testFun, a);
  282.   return BASE::index(valTestFun, &capsule);
  283. }
  284.  
  285. template <class T> unsigned
  286. RWTValSlist<T>::occurrencesOf(T val) const
  287. {
  288.   unsigned count = 0;
  289.   RWTValSlistIterator<T> iter(*(RWTValSlist<T>*)this);
  290.   while ( iter.findNext(val) ) count++;
  291.   return count;
  292. }
  293.  
  294. template <class T> unsigned
  295. RWTValSlist<T>::occurrencesOf(RWBoolean (*testFun)(T, void*), void* a) const
  296. {
  297.   unsigned count = 0;
  298.   RWTValSlistIterator<T> iter(*(RWTValSlist<T>*)this);
  299.   while ( iter.findNext(testFun, a) ) count++;
  300.   return count;
  301. }
  302.  
  303. template <class T> RWBoolean
  304. RWTValSlist<T>::remove(T val)
  305. {
  306.   RWTValSlistIterator<T> iter(*(RWTValSlist<T>*)this);
  307.   return iter.removeNext(val);
  308. }
  309.  
  310. template <class T> RWBoolean
  311. RWTValSlist<T>::remove(RWBoolean (*testFun)(T, void*), void* a)
  312. {
  313.   RWTValSlistIterator<T> iter(*(RWTValSlist<T>*)this);
  314.   return iter.removeNext(testFun, a);
  315. }
  316.  
  317. template <class T> unsigned
  318. RWTValSlist<T>::removeAll(T val)
  319. {
  320.   unsigned count = 0;
  321.   RWTValSlistIterator<T> iter(*(RWTValSlist<T>*)this);
  322.   while (iter.removeNext(val)) ++count;
  323.   return count;
  324. }
  325.  
  326. template <class T> unsigned
  327. RWTValSlist<T>::removeAll(RWBoolean (*testFun)(T, void*), void* a)
  328. {
  329.   unsigned count = 0;
  330.   RWTValSlistIterator<T> iter(*(RWTValSlist<T>*)this);
  331.   while (iter.removeNext(testFun, a)) ++count;
  332.   return count;
  333. }
  334.  
  335. /****************************************************************
  336.  *                                *
  337.  *        RWTValSlist<T> protected functions        *
  338.  *                                *
  339.  ****************************************************************/
  340.  
  341. /*
  342.  * Extracts the value out of a link then throws the link away:
  343.  */
  344. template <class T> T
  345. RWTValSlist<T>::peel(RWTValSlink<T>* link)
  346. {
  347.   RWPRECONDITION(("RWTValSlist<T>::peel(RWTValSlink<T>*): nil link", link));
  348.   T ret = link->_info;
  349.   delete link;
  350.   return ret;
  351. }
  352.  
  353. /****************************************************************
  354.  *                                *
  355.  *        Definitions for RWTValSlistIterator<T>        *
  356.  *                                *
  357.  ****************************************************************/
  358.  
  359. template <class T> RWBoolean
  360. RWTValSlistIterator<T>::findNext(T target)
  361. {
  362.   while ( ++(*this) ){
  363.     if (key()==target) return TRUE;
  364.   }
  365.   return FALSE;
  366. }
  367.  
  368. template <class T> RWBoolean
  369. RWTValSlistIterator<T>::findNext(RWBoolean (*testFun)(T, void*), void* a)
  370. {
  371.   RWTValTester<T> capsule(testFun, a);
  372.   return BASE::findNext(RWTValSlist<T>::valTestFun, &capsule) != rwnil;
  373. }
  374.  
  375. template <class T> RWBoolean
  376. RWTValSlistIterator<T>::remove()
  377. {
  378.   LINK* link = BASE::remove();
  379.   return link ? (delete link, TRUE) : FALSE;
  380. }
  381.  
  382. template <class T> RWBoolean
  383. RWTValSlistIterator<T>::removeNext(T target)
  384. {
  385.   LINK* cur;
  386.   LINK* prev = BASE::key();
  387.  
  388.   while ( ++(*this) ) {
  389.     cur = BASE::key();
  390.     if (target == cur->_info){            // Is this the victim?
  391.       LINK* rem = (LINK*)BASE::removeRight(prev); // If so, remove it and...
  392. #ifdef RWDEBUG
  393.       assert (rem==cur);
  394. #endif
  395.       delete rem;                // ... delete it.
  396.       return TRUE;
  397.     }
  398.     prev = cur;
  399.   }
  400.   return FALSE;
  401. }
  402.  
  403. template <class T> RWBoolean
  404. RWTValSlistIterator<T>::removeNext(RWBoolean (*testFun)(T, void*), void* a)
  405. {
  406.   RWTValTester<T> capsule(testFun, a);
  407.   LINK* link = BASE::removeNext(LIST::valTestFun, &capsule);
  408.   return link ? (delete link, TRUE) : FALSE;
  409. }
  410.  
  411.  
  412. pragma pop_align_members();
  413. #endif    /* __RWTVSLIST_H__ */
  414.