ofstd/include/dcmtk/ofstd/oflist.h

00001 /*
00002  *
00003  *  Copyright (C) 1997-2010, OFFIS e.V.
00004  *  All rights reserved.  See COPYRIGHT file for details.
00005  *
00006  *  This software and supporting documentation were developed by
00007  *
00008  *    OFFIS e.V.
00009  *    R&D Division Health
00010  *    Escherweg 2
00011  *    D-26121 Oldenburg, Germany
00012  *
00013  *
00014  *  Module:  ofstd
00015  *
00016  *  Author:  Andreas Barth
00017  *
00018  *  Purpose:
00019  *          Defines a template list class with interfaces similar to the C++ Standard
00020  *
00021  *  Last Update:      $Author: joergr $
00022  *  Update Date:      $Date: 2010-10-14 13:15:50 $
00023  *  CVS/RCS Revision: $Revision: 1.26 $
00024  *  Status:           $State: Exp $
00025  *
00026  *  CVS/RCS Log at end of file
00027  *
00028  */
00029 
00030 #ifndef OFLIST_H
00031 #define OFLIST_H
00032 
00033 // Usage (only non standard):
00034 //   OFListInsert(InputIterator_type, T_type, c, pos, first, last)
00035 //                      Inserts the elements of type T in
00036 //                      range [first, last) into list c,
00037 //   OFListRemoveIf(Predicate_Type, T_type, c, pred)
00038 //                      Erases all elements of type T in the list referred by
00039 //                      an iterator i where pred(*i) == true.
00040 //                      Predicate_Type is the function type of pred
00041 //
00042 // Additional Remarks:
00043 //   In some template functions one template parameter is another function.
00044 //   Some compilers  cannot determine automatically the type of template
00045 //   function parameters, so you must give  them a hint casting
00046 //   the parameter function to the correct type (e.g. NeXT gcc 2.5.8)
00047 
00048 #include "dcmtk/config/osconfig.h"    /* make sure OS specific configuration is included first */
00049 #include "dcmtk/ofstd/oftypes.h"
00050 #include "dcmtk/ofstd/ofcast.h"
00051 
00052 #ifndef HAVE_CLASS_TEMPLATE
00053 #error Your C++ compiler cannot handle class templates:
00054 #endif
00055 
00056 #if defined(HAVE_STL) || defined(HAVE_STL_LIST)
00057 // It is possible to use the standard template library list class since the
00058 // interface is nearly identical.
00059 // Important: If you want to use the standard template library (STL), no
00060 // variable within a namespace using a class of the STL shall have a name
00061 // of one class of the STL
00062 #include <list>
00063 
00064 #ifdef HAVE_STD_NAMESPACE
00065 #define OFList std::list
00066 #define OFListIterator(x) std::list< x >::iterator
00067 #define OFListConstIterator(x) std::list< x >::const_iterator
00068 #else
00069 #define OFList list
00070 #define OFListIterator(x) list< x >::iterator
00071 #define OFListConstIterator(x) list< x >::const_iterator
00072 #endif
00073 
00074 #define OFListInsert(InputIterator, T, c, pos, first, last) (c).insert((pos), (first), (last))
00075 #define OFListRemoveIf(Predicate, T, c, pred) (c).remove_if((pred))
00076 
00077 // workaround for "implicit typename" warning on gcc 3.x
00078 #define OFLIST_TYPENAME OFTypename
00079 
00080 #else
00081 
00082 #define INCLUDE_CASSERT
00083 #define INCLUDE_CSTDDEF
00084 #include "dcmtk/ofstd/ofstdinc.h"
00085 
00086 #define OFLIST_TYPENAME
00087 
00088 BEGIN_EXTERN_C
00089 #ifdef HAVE_SYS_TYPES_H
00090 /* needed e.g. on Solaris for definition of size_t */
00091 #include <sys/types.h>
00092 #endif
00093 END_EXTERN_C
00094 
00095 // OFListLinkBase, OFListLink and OFListBase are classes for internal
00096 // use only and shall not be used.
00097 
00098 /* non-template double linked list. Base class fo OFListLink.
00099  * Implicitly used by OFList, should not be called by users.
00100  */
00101 struct OFListLinkBase
00102 {
00103     OFListLinkBase * next;
00104     OFListLinkBase * prev;
00105     OFBool dummy;
00106     OFListLinkBase(): next(NULL), prev(NULL), dummy(OFFalse) { }
00107     virtual ~OFListLinkBase() {}
00108 
00109   private:
00110     /* undefined */ OFListLinkBase(const OFListLinkBase&);
00111     /* undefined */ OFListLinkBase& operator=(const OFListLinkBase&);
00112 };
00113 
00114 
00115 /* non-template list. Base class fo OFList.
00116  * Implicitly used by OFList, should not be called by users.
00117  */
00118 class OFListBase
00119 {
00120 protected:
00121     OFListLinkBase * afterLast;
00122     size_t listSize;
00123     void base_recalcListSize();
00124 public:
00125     OFListBase();
00126     virtual ~OFListBase();
00127     OFListLinkBase * base_begin() const { return afterLast->next; }
00128     OFListLinkBase * base_end() const { return afterLast; }
00129     OFBool base_empty() const { return afterLast == afterLast->next; }
00130     size_t base_size() const { return listSize; }
00131     OFListLinkBase * base_insert(OFListLinkBase * pos, OFListLinkBase * newElem);
00132     OFListLinkBase * base_erase(OFListLinkBase * pos);
00133     void base_splice(OFListLinkBase * pos,
00134                 OFListLinkBase * begin, OFListLinkBase * end);
00135     void base_clear();
00136 
00137   private:
00138     /* undefined */ OFListBase(const OFListBase&);
00139     /* undefined */ OFListBase& operator=(const OFListBase&);
00140 };
00141 
00142 
00143 
00144 /* template class for double linked list entries.
00145  * Implicitly used by OFList, should not be called by users.
00146  */
00147 template <class T>
00148 struct OFListLink : public OFListLinkBase
00149 {
00150     T info;
00151     OFListLink(const T& i) : OFListLinkBase(), info(i)  { }
00152     virtual ~OFListLink() {}
00153   private:
00154     /* undefined */ OFListLink(const OFListLink<T>&);
00155     /* undefined */ OFListLink<T>& operator=(const OFListLink<T>&);
00156 };
00157 
00158 
00159 // Definition of OFList and OFIterator
00160 
00161 template <class T> class OFList;
00162 
00163 
00170 template <class T>
00171 class OFIterator
00172 {
00173     friend class OFList<T>;
00174 protected:
00175 
00177     OFListLinkBase * node;
00178 
00182     OFIterator(OFListLinkBase * x) : node(x) { }
00183 public:
00184 
00189     OFIterator() : node(NULL)  { }
00190 
00193     OFIterator(const OFIterator<T>& x) : node(x.node) { };
00194 
00197     OFIterator<T>& operator=(const OFIterator<T>& x)
00198     {
00199         node = x.node;
00200         return *this;
00201     }
00202 
00208     OFBool operator==(const OFIterator<T>& x) const { return node == x.node; }
00209 
00215     OFBool operator!=(const OFIterator<T>& x) const { return node != x.node; }
00216 
00221     T& operator*() const
00222     {
00223         assert(!node->dummy);
00224         return (OFstatic_cast(OFListLink<T> *,node))->info;
00225     }
00226 
00231     T* operator->() const
00232     {
00233         return &(**this);
00234     }
00235 
00241     OFIterator<T>& operator++()
00242     {
00243         node = node->next;
00244         return *this;
00245     }
00246 
00253     OFIterator<T> operator++(int)
00254     {
00255         OFIterator<T> tmp(*this);
00256         node = node->next;
00257         return tmp;
00258     }
00259 
00265     OFIterator<T>& operator--()
00266     {
00267         node = node->prev;
00268         return *this;
00269     }
00270 
00277     OFIterator<T> operator--(int)
00278     {
00279         OFIterator<T> tmp(*this);
00280         node = node->prev;
00281         return tmp;
00282     }
00283 };
00284 
00285 
00289 template <class T>
00290 class OFList : private OFListBase
00291 {
00292 public:
00298     OFIterator<T> insert(OFIterator<T> position, const T& x)
00299     {
00300       return OFIterator<T>(OFListBase::base_insert(position.node, new OFListLink<T>(x)));
00301     }
00302 
00303 private:
00304 
00308     void copy(const OFList<T>& oldList)
00309     {
00310         OFIterator<T> vfirst(oldList.begin());
00311         OFIterator<T> vend(oldList.end());
00312         OFIterator<T> vpos(this->end());
00313         while (vfirst != vend)
00314         {
00315             insert(vpos, *vfirst);
00316             ++vfirst;
00317         }
00318     }
00319 
00323     void recalcListSize() { OFListBase::base_recalcListSize(); }
00324 
00325 public:
00326 
00329     OFList() : OFListBase() { }
00330 
00333     OFList(const OFList<T>& oldList):OFListBase()
00334     {
00335         copy(oldList);
00336     }
00337 
00342     OFIterator<T> begin() const { return OFIterator<T>(OFListBase::base_begin()); }
00343 
00348     OFIterator<T> end() const { return OFIterator<T>(OFListBase::base_end()); }
00349 
00353     OFBool empty() const { return OFListBase::base_empty(); }
00354 
00358     size_t size() const { return OFListBase::base_size(); }
00359 
00364     T& front() { return *begin(); }
00365 
00370     T& back() { return *(--end()); }
00371 
00375     void push_front(const T& x) { insert(begin(), OFconst_cast(T&, x)); }
00376     /* const cast away to keep some old compilers happy */
00377 
00382     void pop_front() { erase(begin()); }
00383 
00387     void push_back(const T& x) { insert(end(), OFconst_cast(T&, x)); }
00388     /* const cast away to keep some old compilers happy */
00389 
00394     void pop_back() { erase(--end()); }
00395 
00401     void insert(OFIterator<T> position, size_t n, const T& x)
00402     {
00403       while(n--) OFListBase::base_insert(position.node, new OFListLink<T>(x));
00404     }
00405 
00410     OFIterator<T> erase(OFIterator<T> position)
00411     {
00412       return OFIterator<T>(OFListBase::base_erase(position.node));
00413     }
00414 
00421     OFIterator<T> erase(OFIterator<T> position, OFIterator<T> last)
00422     {
00423       while (position != last) position = erase(position);
00424       return last;
00425     }
00426 
00430     void clear() { OFListBase::base_clear(); }
00431 
00437     void splice(OFIterator<T> position, OFList<T>& x)
00438     {
00439       splice(position, x, x.begin(), x.end());
00440     }
00441 
00447     void splice(OFIterator<T> position, OFList<T>& x, OFIterator<T> i)
00448     {
00449       OFIterator<T> change(i);
00450       ++i;
00451       splice(position, x, change, i);
00452     }
00453 
00461     void splice(OFIterator<T> position, OFList<T>& x,
00462                 OFIterator<T> first, OFIterator<T> last)
00463     {
00464       OFListBase::base_splice(position.node, first.node, last.node);
00465       x.recalcListSize();
00466     }
00467 
00472     void remove(const T& value)
00473     {
00474       OFIterator<T> first = begin();
00475       OFIterator<T> last = end();
00476       while(first != last)
00477       {
00478         if (*first == value) first = erase(first);
00479         else ++first;
00480       }
00481     }
00482 
00483 private:
00484 
00487     OFList<T>& operator=(const OFList<T>& arg);
00488 };
00489 
00490 
00491 #ifdef HAVE_FUNCTION_TEMPLATE
00492 
00493 #define OFListInsert(InputIterator, T, c, pos, first, last) OF_ListInsert((c), (pos), (first), (last))
00494 
00495 #define OFListRemoveIf(Predicate, T, c, pred) OF_ListRemoveIf((c), (pred))
00496 
00497 #elif defined(HAVE_STATIC_TEMPLATE_METHOD)
00498 
00499 #define OFListInsert(InputIterator, T, c, pos, first, last) OF_ListInsertClass<InputIterator, T>::OF_ListInsert((c), (pos), (first), (last))
00500 
00501 #define OFListRemoveIf(Predicate, T, c, pred) OF_ListRemoveIfClass<Predicate, T>::OF_ListRemoveIf((c), (pred))
00502 
00503 #else
00504 #error Your C++ Compiler is not capable of compiling this code
00505 #endif
00506 
00507 // Insert the elements in range [first, last) into list
00508 template <class InputIterator, class T>
00509 #if defined(HAVE_STATIC_TEMPLATE_METHOD) && !defined(HAVE_FUNCTION_TEMPLATE)
00510 class OF_ListInsertClass
00511 {
00512 public:
00513 static
00514 #endif
00515 void OF_ListInsert(OFList<T>& c, OFIterator<T> position,
00516                   InputIterator first, InputIterator last)
00517 {
00518     while(first != last)
00519     {
00520         c.insert(position, *first);
00521         ++first;
00522     }
00523 }
00524 #if defined(HAVE_STATIC_TEMPLATE_METHOD) && !defined(HAVE_FUNCTION_TEMPLATE)
00525 };
00526 #endif
00527 
00528 // Erases all elements in the list referred by an iterator i where
00529 // pred(*i) == true
00530 template <class Predicate, class T>
00531 #if defined(HAVE_STATIC_TEMPLATE_METHOD) && !defined(HAVE_FUNCTION_TEMPLATE)
00532 class OF_ListRemoveIfClass
00533 {
00534 public:
00535 static
00536 #endif
00537 void OF_ListRemoveIf(OFList<T>& c, Predicate pred)
00538 {
00539     OFIterator<T> first = c.begin();
00540     OFIterator<T> last = c.end();
00541     while (first != last)
00542     {
00543         if (pred(*first))
00544             first = c.erase(first);
00545         else
00546             ++first;
00547     }
00548 }
00549 
00550 #if defined(HAVE_STATIC_TEMPLATE_METHOD) && !defined(HAVE_FUNCTION_TEMPLATE)
00551 };
00552 #endif
00553 
00554 #define OFListIterator(x) OFIterator< x >
00555 #define OFListConstIterator(x) OFIterator< x >
00556 
00557 #endif
00558 
00559 #endif
00560 
00561 /*
00562 ** CVS/RCS Log:
00563 ** $Log: oflist.h,v $
00564 ** Revision 1.26  2010-10-14 13:15:50  joergr
00565 ** Updated copyright header. Added reference to COPYRIGHT file.
00566 **
00567 ** Revision 1.25  2010-05-07 11:13:42  uli
00568 ** Use OFTypename for OFLIST_TYPENAME.
00569 **
00570 ** Revision 1.24  2009-08-19 11:55:45  meichel
00571 ** Added additional includes needed for Sun Studio 11 on Solaris.
00572 **
00573 ** Revision 1.23  2009-08-19 10:44:36  joergr
00574 ** Added missing dereference operator.
00575 **
00576 ** Revision 1.22  2005/12/08 16:05:58  meichel
00577 ** Changed include path schema for all DCMTK header files
00578 **
00579 ** Revision 1.21  2004/04/14 11:44:48  joergr
00580 ** Replaced non-Unix newline characters.
00581 **
00582 ** Revision 1.20  2003/08/07 11:44:55  joergr
00583 ** Slightly modified header comments to conform to doxygen syntax.
00584 **
00585 ** Revision 1.19  2003/07/11 13:46:14  joergr
00586 ** Added workaround to get rid of "implicit typename" warnings on gcc 3.x
00587 ** (introduced macro OFLIST_TYPENAME).
00588 **
00589 ** Revision 1.18  2003/07/09 13:57:43  meichel
00590 ** Adapted type casts to new-style typecast operators defined in ofcast.h
00591 **
00592 ** Revision 1.17  2003/06/12 15:20:30  joergr
00593 ** Slightly modified macro definitions to avoid potential parser errors (added
00594 ** space character after '<' and before '>').
00595 **
00596 ** Revision 1.16  2003/06/12 13:21:54  joergr
00597 ** Introduced macro OFListConstIterator() to support STL const_iterators.
00598 **
00599 ** Revision 1.15  2003/06/03 10:20:00  meichel
00600 ** OFList now explicitly defined as std::list if std namespace present
00601 **
00602 ** Revision 1.14  2002/11/27 11:23:05  meichel
00603 ** Adapted module ofstd to use of new header file ofstdinc.h
00604 **
00605 ** Revision 1.13  2001/08/23 16:05:52  meichel
00606 ** Added private undefined copy assignment operators to avoid gcc warnings
00607 **
00608 ** Revision 1.12  2001/06/01 15:51:34  meichel
00609 ** Updated copyright header
00610 **
00611 ** Revision 1.11  2000/10/10 12:01:21  meichel
00612 ** Created/updated doc++ comments
00613 **
00614 ** Revision 1.10  2000/03/08 16:36:02  meichel
00615 ** Updated copyright header.
00616 **
00617 ** Revision 1.9  1998/11/27 12:42:51  joergr
00618 ** Added copyright message to source files and changed CVS header.
00619 **
00620 ** Revision 1.8  1998/07/02 07:47:02  meichel
00621 ** Some code purifications to avoid gcc 2.8.1 -Weffc++ warnings.
00622 **
00623 ** Revision 1.7  1998/06/29 12:09:23  meichel
00624 ** Removed some name clashes (e.g. local variable with same
00625 **   name as class member) to improve maintainability.
00626 **   Applied some code purifications proposed by the gcc 2.8.1 -Weffc++ option.
00627 **
00628 ** Revision 1.6  1998/02/06 15:07:38  meichel
00629 ** Removed many minor problems (name clashes, unreached code)
00630 **   reported by Sun CC4 with "+w" or Sun CC2.
00631 **
00632 ** Revision 1.5  1997/11/10 16:31:19  meichel
00633 ** Corrected bug possibly causing a memory leak in OFList.
00634 **   Added virtual destructors to classes OFListLinkBase and OFListLink.
00635 **
00636 ** Revision 1.4  1997/09/11 15:43:15  hewett
00637 ** Minor changes to eliminate warnings when compiled under the
00638 ** Signus GnuWin32 envionment.  Changed order of initialisers
00639 ** for OFListLink and OFStackLink.  Make ~OFLisBase and ~OFStackBase
00640 ** virtual destructors.
00641 **
00642 ** Revision 1.3  1997/07/24 13:11:00  andreas
00643 ** - Removed Warnings from SUN CC 2.0.1
00644 **
00645 ** Revision 1.2  1997/07/07 07:34:18  andreas
00646 ** - Corrected destructor for OFListBase, now the dummy element is
00647 **   deleted.
00648 **
00649 ** Revision 1.1  1997/07/02 11:51:14  andreas
00650 ** - Preliminary release of the OFFIS Standard Library.
00651 **   In the future this library shall contain a subset of the
00652 **   ANSI C++ Library (Version 3) that works on a lot of different
00653 **   compilers. Additionally this library shall include classes and
00654 **   functions that are often used. All classes and functions begin
00655 **   with OF... This library is independent of the DICOM development and
00656 **   shall contain no DICOM specific stuff.
00657 **
00658 **
00659 */


Generated on 6 Jan 2011 for OFFIS DCMTK Version 3.6.0 by Doxygen 1.5.1