00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #ifndef OFLIST_H
00031 #define OFLIST_H
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048 #include "dcmtk/config/osconfig.h"
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
00058
00059
00060
00061
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
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
00091 #include <sys/types.h>
00092 #endif
00093 END_EXTERN_C
00094
00095
00096
00097
00098
00099
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 OFListLinkBase(const OFListLinkBase&);
00111 OFListLinkBase& operator=(const OFListLinkBase&);
00112 };
00113
00114
00115
00116
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 OFListBase(const OFListBase&);
00139 OFListBase& operator=(const OFListBase&);
00140 };
00141
00142
00143
00144
00145
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 OFListLink(const OFListLink<T>&);
00155 OFListLink<T>& operator=(const OFListLink<T>&);
00156 };
00157
00158
00159
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
00377
00382 void pop_front() { erase(begin()); }
00383
00387 void push_back(const T& x) { insert(end(), OFconst_cast(T&, x)); }
00388
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
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
00529
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
00563
00564
00565
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576
00577
00578
00579
00580
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590
00591
00592
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00603
00604
00605
00606
00607
00608
00609
00610
00611
00612
00613
00614
00615
00616
00617
00618
00619
00620
00621
00622
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
00635
00636
00637
00638
00639
00640
00641
00642
00643
00644
00645
00646
00647
00648
00649
00650
00651
00652
00653
00654
00655
00656
00657
00658
00659