home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 6.ddi / MWHC.006 / M2 < prev    next >
Encoding:
Text File  |  1992-06-07  |  12.1 KB  |  403 lines
  1. #ifndef __RWTVDLIST_H__
  2. #define __RWTVDLIST_H__
  3. pragma push_align_members(64);
  4.  
  5. /*
  6.  * RWTValDlist<T>: A non-intrusive doubly-linked list of values of type T.
  7.  *
  8.  * $Header:   E:/vcs/rw/tvdlist.h_v   1.5   19 Mar 1992 11:26:02   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/tvdlist.h_v  $
  36.  * 
  37.  *    Rev 1.5   19 Mar 1992 11:26:02   KEFFER
  38.  * 
  39.  *    Rev 1.0   02 Mar 1992 16:10:52   KEFFER
  40.  * Initial revision.
  41.  *
  42.  */
  43.  
  44. //$DECLARE_TEMPLATE
  45.  
  46. #include "rw/tidlist.h"
  47.  
  48. template <class T> class RWExport RWTValDlistIterator;
  49.  
  50.  
  51. /****************************************************************
  52.  *                                *
  53.  *        Declarations for RWTValDlink<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 RWTValDlink : public RWIsvDlink {
  62.   T        _info;
  63.   RWTValDlink(T a) : _info(a) { }
  64. };
  65.  
  66.  
  67. /****************************************************************
  68.  *                                *
  69.  *        Declarations for RWTValDlist<T>            *
  70.  *                                *
  71.  ****************************************************************/
  72.  
  73. template <class T> class RWExport RWTValDlist : private RWTIsvDlist< RWTValDlink<T> > {
  74.  
  75.   friend class RWExport RWTValDlistIterator<T> ;
  76.  
  77.   // For convenience in what follows:
  78.   typedef RWTValDlink<T>    LINK;
  79.   typedef RWTIsvDlist<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.   RWTValDlist() { }
  92.   RWTValDlist(const RWTValDlist<T>&);
  93.   ~RWTValDlist() { clear(); }
  94.  
  95.   // Operators:
  96.   RWTValDlist&    operator=(const RWTValDlist<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 RWTValDlistIterator<T>        *
  135.  *                                *
  136.  ****************************************************************/
  137.  
  138. template <class T> class RWExport RWTValDlistIterator : private RWTIsvDlistIterator< RWTValDlink<T> > {
  139.  
  140.   // For convenience in what follows:
  141.   typedef RWTValDlist<T> LIST;
  142.   typedef RWTValDlink<T> LINK;
  143.   typedef RWTIsvDlistIterator<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.   RWTValDlistIterator(RWTValDlist<T>& s) : RWTIsvDlistIterator<LINK>(s) { }
  153.  
  154.   // Operators:
  155.   RWBoolean    operator++()        {return BASE::operator++();}
  156.   BASE::operator+=;            // Advance iterator n links and test
  157.   BASE::operator--;
  158.  
  159.   LIST*        container() const    {return (LIST*)BASE::container();}
  160.   RWBoolean    findNext(T a);
  161.   RWBoolean    findNext(RWBoolean (*testFun)(T, void*), void*);
  162.   void        insertAfterPoint(T a)    {BASE::insertAfterPoint(new LINK(a));}
  163.   T        key() const        {return BASE::key()->_info;}
  164.   RWBoolean    remove();        // Remove item at cursor
  165.   RWBoolean    removeNext(T);
  166.   RWBoolean    removeNext(RWBoolean (*testFun)(T, void*), void*);
  167.   void        reset()            {BASE::reset();}
  168.   void        reset(LIST& s)        {BASE::reset(s);}
  169. };
  170.  
  171.  
  172. //$IMPLEMENT_TEMPLATE
  173.  
  174. #include "rw/tvtestr.h"
  175.  
  176. /****************************************************************
  177.  *                                *
  178.  *        Definitions for RWTValDlist<T>            *
  179.  *                                *
  180.  ****************************************************************/
  181.  
  182. // Used to test for equality with an object.
  183. template <class T> RWBoolean
  184. RWTValDlist<T>::eqTestFun(const RWTValDlink<T>* link, void* p)
  185. {
  186.   RWPRECONDITION(link);
  187.   RWPRECONDITION(p);
  188.   const T* t = (const T*)p;
  189.   return link->_info == *t;
  190. }
  191.   
  192. // Function to wrap a user-supplied tester function such that it
  193. // can be used by the base class
  194. template <class T> RWBoolean
  195. RWTValDlist<T>::valTestFun(const RWTValDlink<T>* link, void* p)
  196. {
  197.   RWPRECONDITION(link);
  198.   RWPRECONDITION(p);
  199.   RWTValTester<T>* c = (RWTValTester<T>*)p;
  200.   return (*c->_testFun)(link->_info, c->_data);
  201. }
  202.   
  203. // Copy constructor:
  204. template <class T> RWTValDlist<T>::RWTValDlist(const RWTValDlist<T>& s)
  205. {
  206.   // Construct an iterator, casting away "constness"
  207.   // (which we promise to honor anyway):
  208.   RWTValDlistIterator<T> next((RWTValDlist<T>&)s);
  209.   while (++next) append(next.key());
  210. }
  211.  
  212. template <class T> RWTValDlist<T>&
  213. RWTValDlist<T>::operator=(const RWTValDlist<T>& s)
  214. {
  215.   if (this!=&s){
  216.     clear();
  217.     // Construct an iterator, casting away "constness"
  218.     // (which we promise to honor anyway):
  219.     RWTValDlistIterator<T> next((RWTValDlist<T>&)s);
  220.     while (++next) append(next.key());
  221.   }
  222.   return *this;
  223. }
  224.  
  225. template <class T> void
  226. RWTValDlist<T>::apply(void (*applyFun)(T, void*), void* a)
  227. {
  228.   RWIsvDlink* link = _lastDlink;
  229.   if (link) {
  230.     do {
  231.       link = link->next();        // Advance to next link
  232.       (*applyFun)(((RWTValDlink<T>*)link)->_info, a);    // Apply the function
  233.     } while (link != _lastDlink);
  234.   }
  235. }
  236.  
  237. template <class T> RWBoolean
  238. RWTValDlist<T>::contains(RWBoolean (*testFun)(T, void*), void* a) const
  239. {
  240.   // Construct an iterator, casting away "constness" (which we promise to honor):
  241.   RWTValDlistIterator<T> iter(*(RWTValDlist<T>*)this);
  242.   return iter.findNext(testFun, a);
  243. }
  244.   
  245. template <class T> RWBoolean
  246. RWTValDlist<T>::contains(T val) const
  247. {
  248.   // Construct an iterator, casting away "constness" (which we promise to honor):
  249.   RWTValDlistIterator<T> iter(*(RWTValDlist<T>*)this);
  250.   return iter.findNext(val);
  251. }
  252.  
  253. template <class T> RWBoolean
  254. RWTValDlist<T>::find(T val, T& k) const
  255. {
  256.   // Construct an iterator, casting away "constness" (which we promise to honor):
  257.   RWTValDlistIterator<T> iter(*(RWTValDlist<T>*)this);
  258.   RWBoolean ret = iter.findNext(val);
  259.   if (ret) k = iter.key();
  260.   return ret;
  261. }
  262.  
  263. template <class T> RWBoolean
  264. RWTValDlist<T>::find(RWBoolean (*testFun)(T, void*), void* a, T& k) const
  265. {
  266.   // Construct an iterator, casting away "constness" (which we promise to honor):
  267.   RWTValDlistIterator<T> iter(*(RWTValDlist<T>*)this);
  268.   RWBoolean ret = iter.findNext(testFun, a);
  269.   if (ret) k = iter.key();
  270.   return ret;
  271. }
  272.  
  273. template <class T> int
  274. RWTValDlist<T>::index(T a) const
  275. {
  276.   return BASE::index(eqTestFun, &a);
  277. }
  278.  
  279. template <class T> int
  280. RWTValDlist<T>::index(RWBoolean (*testFun)(T, void*), void* a) const
  281. {
  282.   RWTValTester<T> capsule(testFun, a);
  283.   return BASE::index(valTestFun, &capsule);
  284. }
  285.  
  286. template <class T> unsigned
  287. RWTValDlist<T>::occurrencesOf(T val) const
  288. {
  289.   unsigned count = 0;
  290.   RWTValDlistIterator<T> iter(*(RWTValDlist<T>*)this);
  291.   while ( iter.findNext(val) ) count++;
  292.   return count;
  293. }
  294.  
  295. template <class T> unsigned
  296. RWTValDlist<T>::occurrencesOf(RWBoolean (*testFun)(T, void*), void* a) const
  297. {
  298.   unsigned count = 0;
  299.   RWTValDlistIterator<T> iter(*(RWTValDlist<T>*)this);
  300.   while ( iter.findNext(testFun, a) ) count++;
  301.   return count;
  302. }
  303.  
  304. template <class T> RWBoolean
  305. RWTValDlist<T>::remove(T val)
  306. {
  307.   RWTValDlistIterator<T> iter(*(RWTValDlist<T>*)this);
  308.   return iter.removeNext(val);
  309. }
  310.  
  311. template <class T> RWBoolean
  312. RWTValDlist<T>::remove(RWBoolean (*testFun)(T, void*), void* a)
  313. {
  314.   RWTValDlistIterator<T> iter(*(RWTValDlist<T>*)this);
  315.   return iter.removeNext(testFun, a);
  316. }
  317.  
  318. template <class T> unsigned
  319. RWTValDlist<T>::removeAll(T val)
  320. {
  321.   unsigned count = 0;
  322.   RWTValDlistIterator<T> iter(*(RWTValDlist<T>*)this);
  323.   while (iter.removeNext(val)) ++count;
  324.   return count;
  325. }
  326.  
  327. template <class T> unsigned
  328. RWTValDlist<T>::removeAll(RWBoolean (*testFun)(T, void*), void* a)
  329. {
  330.   unsigned count = 0;
  331.   RWTValDlistIterator<T> iter(*(RWTValDlist<T>*)this);
  332.   while (iter.removeNext(testFun, a)) ++count;
  333.   return count;
  334. }
  335.  
  336. /****************************************************************
  337.  *                                *
  338.  *        RWTValDlist<T> protected functions        *
  339.  *                                *
  340.  ****************************************************************/
  341.  
  342. /*
  343.  * Extracts the value out of a link then throws the link away:
  344.  */
  345. template <class T> T
  346. RWTValDlist<T>::peel(RWTValDlink<T>* link)
  347. {
  348.   RWPRECONDITION(("RWTValDlist<T>::peel(RWTValDlink<T>*): nil link", link));
  349.   T ret = link->_info;
  350.   delete link;
  351.   return ret;
  352. }
  353.  
  354. /****************************************************************
  355.  *                                *
  356.  *        Definitions for RWTValDlistIterator<T>        *
  357.  *                                *
  358.  ****************************************************************/
  359.  
  360. template <class T> RWBoolean
  361. RWTValDlistIterator<T>::findNext(T target)
  362. {
  363.   while ( ++(*this) ){
  364.     if (key()==target) return TRUE;
  365.   }
  366.   return FALSE;
  367. }
  368.  
  369. template <class T> RWBoolean
  370. RWTValDlistIterator<T>::findNext(RWBoolean (*testFun)(T, void*), void* a)
  371. {
  372.   RWTValTester<T> capsule(testFun, a);
  373.   return BASE::findNext(RWTValDlist<T>::valTestFun, &capsule) != rwnil;
  374. }
  375.  
  376. template <class T> RWBoolean
  377. RWTValDlistIterator<T>::remove()
  378. {
  379.   LINK* link = BASE::remove();
  380.   return link ? (delete link, TRUE) : FALSE;
  381. }
  382.  
  383. template <class T> RWBoolean
  384. RWTValDlistIterator<T>::removeNext(T target)
  385. {
  386.   while (++(*this)) {
  387.     if (key()==target) return remove();
  388.   }
  389.   return FALSE;
  390. }
  391.  
  392. template <class T> RWBoolean
  393. RWTValDlistIterator<T>::removeNext(RWBoolean (*testFun)(T, void*), void* a)
  394. {
  395.   RWTValTester<T> capsule(testFun, a);
  396.   LINK* link = BASE::removeNext(LIST::valTestFun, &capsule);
  397.   return link ? (delete link, TRUE) : FALSE;
  398. }
  399.  
  400.  
  401. pragma pop_align_members();
  402. #endif    /* __RWTVDLIST_H__ */
  403.