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 */