Open
Graph Drawing
Framework

 v.2012.05
 

SList.h
Go to the documentation of this file.
00001 /*
00002  * $Revision: 2299 $
00003  * 
00004  * last checkin:
00005  *   $Author: gutwenger $ 
00006  *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
00007  ***************************************************************/
00008  
00045 #ifdef _MSC_VER
00046 #pragma once
00047 #endif
00048 
00049 #ifndef OGDF_SLIST_H
00050 #define OGDF_SLIST_H
00051 
00052 
00053 #include <ogdf/internal/basic/list_templates.h>
00054 
00055 
00056 namespace ogdf {
00057 
00058 
00059 template<class E> class SListPure;
00060 template<class E> class StackPure;
00061 template<class E> class SListIterator;
00062 template<class E> class SListConstIterator;
00063 
00064 
00066 template<class E>
00067 class SListElement {
00068     friend class SListPure<E>;
00069     friend class StackPure<E>;
00070     friend class SListIterator<E>;
00071     friend class SListConstIterator<E>;
00072 
00073     SListElement<E> *m_next; 
00074     E m_x; 
00075 
00077     SListElement() : m_next(0) { }
00079     SListElement(const E &x) : m_next(0), m_x(x) { }
00081     SListElement(const E &x, SListElement<E> *next) :
00082         m_next(next), m_x(x) { }
00083     
00084     OGDF_NEW_DELETE
00085 }; // class SListElement
00086 
00087 
00088 
00090 
00096 template<class E> class SListIterator {
00097     SListElement<E> *m_pX; 
00098 
00099     friend class SListConstIterator<E>;
00100     friend class SListPure<E>;
00101 
00103     operator SListElement<E> *() { return m_pX; }
00105     operator const SListElement<E> *() const { return m_pX; }
00106 
00107 public:
00109     SListIterator() : m_pX(0) { }
00111     SListIterator(SListElement<E> *pX) : m_pX(pX) { }
00113     SListIterator(const SListIterator<E> &it) : m_pX(it.m_pX) { }
00114 
00116     bool valid() const { return m_pX != 0; }
00117 
00119     bool operator==(const SListIterator<E> &it) const {
00120         return m_pX == it.m_pX;
00121     }
00122 
00124     bool operator!=(const SListIterator<E> &it) const {
00125         return m_pX != it.m_pX;
00126     }
00127 
00129     SListIterator<E> succ() const { return m_pX->m_next; }
00130 
00132     E &operator*() const { return m_pX->m_x; }
00133 
00135     SListIterator<E> &operator=(const SListIterator<E> &it) {
00136         m_pX = it.m_pX;
00137         return *this;
00138     }
00139 
00141     SListIterator<E> &operator++() {
00142         m_pX = m_pX->m_next;
00143         return *this;
00144     }
00145 
00147     SListIterator<E> operator++(int) {
00148         SListIterator<E> it = *this;
00149         m_pX = m_pX->m_next;
00150         return it;
00151     }
00152 
00153     OGDF_NEW_DELETE
00154 }; // class SListIterator
00155 
00156 
00157 
00159 
00166 template<class E> class SListConstIterator {
00167     const SListElement<E> *m_pX; 
00168 
00169     friend class SListPure<E>;
00170 
00172     operator const SListElement<E> *() { return m_pX; }
00173 
00174 public:
00176     SListConstIterator() : m_pX(0) { }
00177     
00179     SListConstIterator(const SListElement<E> *pX) : m_pX(pX) { }
00180     
00182     SListConstIterator(const SListIterator<E> &it) : m_pX((const SListElement<E> *)it) { }
00184     SListConstIterator(const SListConstIterator &it) : m_pX(it.m_pX) { }
00185 
00187     bool valid() const { return m_pX != 0; }
00188 
00190     bool operator==(const SListConstIterator<E> &it) const {
00191         return m_pX == it.m_pX;
00192     }
00193 
00195     bool operator!=(const SListConstIterator<E> &it) const {
00196         return m_pX != it.m_pX;
00197     }
00198 
00200     SListConstIterator<E> succ() const { return m_pX->m_next; }
00201 
00203     const E &operator*() const { return m_pX->m_x; }
00204 
00206     SListConstIterator<E> &operator=(const SListConstIterator<E> &it) {
00207         m_pX = it.m_pX;
00208         return *this;
00209     }
00210 
00211 
00213     SListConstIterator<E> &operator++() {
00214         m_pX = m_pX->m_next;
00215         return *this;
00216     }
00217 
00219     SListConstIterator<E> operator++(int) {
00220         SListConstIterator<E> it = *this;
00221         m_pX = m_pX->m_next;
00222         return it;
00223     }
00224 
00225     OGDF_NEW_DELETE
00226 }; // class SListConstIterator
00227 
00228 
00230 
00237 template<class E> class SListPure {
00238     SListElement<E> *m_head; 
00239     SListElement<E> *m_tail; 
00240 
00241 public:
00243     SListPure() : m_head(0), m_tail(0) { }
00244     
00246     SListPure(const SListPure<E> &L) : m_head(0), m_tail(0) {
00247         copy(L);
00248     }
00249 
00250     // destruction
00251     ~SListPure() { clear(); }
00252 
00253     typedef E value_type;
00254     typedef SListElement<E> element_type;
00255     typedef SListConstIterator<E> const_iterator;
00256     typedef SListIterator<E> iterator;
00257 
00259     bool empty() const { return m_head == 0; }
00260 
00262 
00265     int size() const {
00266         int count = 0;
00267         for (SListElement<E> *pX = m_head; pX; pX = pX->m_next)
00268             ++count;
00269         return count;
00270     }
00271 
00273 
00276     SListConstIterator<E> begin() const { return m_head; }
00277 
00279 
00282     SListIterator<E> begin() { return m_head; }
00283 
00285 
00288     SListConstIterator<E> end() const { return SListConstIterator<E>(); }
00289 
00291 
00294     SListIterator<E> end() { return SListIterator<E>(); }
00295 
00297 
00300     SListConstIterator<E> rbegin() const { return m_tail; }
00301 
00303 
00306     SListIterator<E> rbegin() { return m_tail; }
00307 
00308 
00310 
00313     SListConstIterator<E> get(int pos) const {
00314         SListElement<E> *pX;
00315         for(pX = m_head; pX != 0; pX = pX->m_next)
00316             if (pos-- == 0) break;
00317         return pX;
00318     }
00319 
00321 
00324     SListIterator<E> get(int pos) {
00325         SListElement<E> *pX;
00326         for(pX = m_head; pX != 0; pX = pX->m_next)
00327             if (pos-- == 0) break;
00328         return pX;
00329     }
00330 
00332 
00336     int pos(SListConstIterator<E> it) const {
00337         OGDF_ASSERT(it.valid())
00338         int p = 0;
00339         for(SListElement<E> *pX = m_head; pX != 0; pX = pX->m_next, ++p)
00340             if (pX == it) break;
00341         return p;
00342     }
00343 
00344     
00346 
00349     const E &front() const {
00350         OGDF_ASSERT(m_head != 0)
00351         return m_head->m_x;
00352     }
00353 
00355 
00358     E &front() {
00359         OGDF_ASSERT(m_head != 0)
00360         return m_head->m_x;
00361     }
00362 
00364 
00367     const E &back() const {
00368         OGDF_ASSERT(m_tail != 0)
00369         return m_tail->m_x;
00370     }
00371 
00373 
00376     E &back() {
00377         OGDF_ASSERT(m_tail != 0)
00378         return m_tail->m_x;
00379     }
00380 
00382 
00385     SListConstIterator<E> cyclicSucc(SListConstIterator<E> it) const {
00386         const SListElement<E> *pX = it;
00387         return (pX->m_next) ? pX->m_next : m_head;
00388     }
00389 
00391 
00394     SListIterator<E> cyclicSucc(SListIterator<E> it) {
00395         SListElement<E> *pX = it;
00396         return (pX->m_next) ? pX->m_next : m_head;
00397     }
00398 
00400     SListPure<E> &operator=(const SListPure<E> &L) {
00401         clear(); copy(L);
00402         return *this;
00403     }
00404 
00406     SListIterator<E> pushFront(const E &x) {
00407         m_head = OGDF_NEW SListElement<E>(x,m_head);
00408         if (m_tail == 0) m_tail = m_head;
00409         return m_head;
00410     }
00411 
00413     SListIterator<E> pushBack(const E &x) {
00414         SListElement<E> *pNew = OGDF_NEW SListElement<E>(x);
00415         if (m_head == 0)
00416             m_head = m_tail = pNew;
00417         else
00418             m_tail = m_tail->m_next = pNew;
00419         return m_tail;
00420     }
00421 
00423 
00426     SListIterator<E> insertAfter(const E &x, SListIterator<E> itBefore) {
00427         SListElement<E> *pBefore = itBefore;
00428         OGDF_ASSERT(pBefore != 0)
00429         SListElement<E> *pNew = OGDF_NEW SListElement<E>(x,pBefore->m_next);
00430         if (pBefore == m_tail) m_tail = pNew;
00431         return (pBefore->m_next = pNew);
00432     }
00433 
00435 
00438     void popFront() {
00439         OGDF_ASSERT(m_head != 0)
00440         SListElement<E> *pX = m_head;
00441         if ((m_head = m_head->m_next) == 0) m_tail = 0;
00442         delete pX;
00443     }
00444 
00446 
00449     E popFrontRet() {
00450         E el = front(); 
00451         popFront();
00452         return el;
00453     }
00454 
00456 
00459     void delSucc(SListIterator<E> itBefore) {
00460         SListElement<E> *pBefore = itBefore;
00461         OGDF_ASSERT(pBefore != 0)
00462         SListElement<E> *pDel = pBefore->m_next;
00463         OGDF_ASSERT(pDel != 0)
00464         if ((pBefore->m_next = pDel->m_next) == 0) m_tail = pBefore;
00465         delete pDel;
00466     }
00467 
00469     void moveFrontToFront(SListPure<E> &L2) {
00470         OGDF_ASSERT(m_head != 0)
00471         OGDF_ASSERT(this != &L2)
00472         SListElement<E> *pX = m_head;
00473         if ((m_head = m_head->m_next) == 0) m_tail = 0;
00474         pX->m_next = L2.m_head;
00475         L2.m_head = pX;
00476         if (L2.m_tail == 0) L2.m_tail = L2.m_head;
00477     }
00478 
00480     void moveFrontToBack(SListPure<E> &L2) {
00481         OGDF_ASSERT(m_head != 0)
00482         OGDF_ASSERT(this != &L2)
00483         SListElement<E> *pX = m_head;
00484         if ((m_head = m_head->m_next) == 0) m_tail = 0;
00485         pX->m_next = 0;
00486         if (L2.m_head == 0)
00487             L2.m_head = L2.m_tail = pX;
00488         else
00489             L2.m_tail = L2.m_tail->m_next = pX;
00490     }
00491 
00493 
00496     void moveFrontToSucc(SListPure<E> &L2, SListIterator<E> itBefore) {
00497         OGDF_ASSERT(m_head != 0)
00498         OGDF_ASSERT(this != &L2)
00499         SListElement<E> *pBefore = itBefore;
00500         SListElement<E> *pX = m_head;
00501         if ((m_head = m_head->m_next) == 0) m_tail = 0;
00502         pX->m_next = pBefore->m_next;
00503         pBefore->m_next = pX;
00504         if (pBefore == L2.m_tail) L2.m_tail = pX;
00505     }
00506 
00508     void clear() {
00509         if (m_head == 0) return;
00510 
00511 #if (_MSC_VER == 1100)
00512 // workaround for bug in Visual Studio 5.0
00513 
00514         while (!empty())
00515             popFront();
00516 
00517 #else
00518 
00519         if (doDestruction((E*)0)) {
00520             for(SListElement<E> *pX = m_head; pX != 0; pX = pX->m_next)
00521                 pX->m_x.~E();
00522         }
00523         OGDF_ALLOCATOR::deallocateList(sizeof(SListElement<E>),m_head,m_tail);
00524 
00525 #endif
00526 
00527         m_head = m_tail = 0;
00528     }
00529 
00531     void conc(SListPure<E> &L2) {
00532         if (m_head)
00533             m_tail->m_next = L2.m_head;
00534         else
00535             m_head = L2.m_head;
00536         if (L2.m_tail != 0) m_tail = L2.m_tail;
00537         L2.m_head = L2.m_tail = 0;
00538     }
00539 
00541     void reverse() {
00542         SListElement<E> *p, *pNext, *pPred = 0;
00543         for(p = m_head; p; p = pNext) {
00544             pNext = p->m_next;
00545             p->m_next = pPred;
00546             pPred = p;
00547         }
00548         swap(m_head,m_tail);
00549     }
00550 
00552     const SListPure<E> &getListPure() const { return *this; }
00553 
00555     void quicksort() {
00556         ogdf::quicksortTemplate(*this);
00557     }
00558 
00560     template<class COMPARER>
00561     void quicksort(const COMPARER &comp) {
00562         ogdf::quicksortTemplate(*this,comp);
00563     }
00564 
00566 
00573     void bucketSort(int l, int h, BucketFunc<E> &f);
00574 
00576     void bucketSort(BucketFunc<E> &f);
00577 
00579     void permute() {
00580         permute(size());
00581     }
00582 
00584     int search (const E& e) const {
00585         int x = 0;
00586         for(SListConstIterator<E> i = begin(); i.valid(); ++i, ++x)
00587             if(*i == e) return x;
00588         return -1;
00589     }
00590 
00592     template<class COMPARER>
00593     int search (const E& e, const COMPARER &comp) const {
00594         int x = 0;
00595         for(SListConstIterator<E> i = begin(); i.valid(); ++i, ++x)
00596             if(comp.equal(*i,e)) return x;
00597         return -1;
00598     }
00599 
00600 protected:
00601     void copy(const SListPure<E> &L) {
00602         for(SListElement<E> *pX = L.m_head; pX != 0; pX = pX->m_next)
00603             pushBack(pX->m_x);
00604     }
00605 
00606     void permute(const int n);
00607 
00608     OGDF_NEW_DELETE
00609 }; // class SListPure
00610 
00611 
00612 
00614 
00621 template<class E>
00622 class SList : private SListPure<E> {
00623 
00624     int m_count; 
00625 
00626 public:
00628     SList() : m_count(0) { }
00629     
00631     SList(const SList<E> &L) : SListPure<E>(L), m_count(L.m_count) { }
00632 
00633     // destruction
00634     ~SList() { }
00635 
00636     typedef E value_type;
00637     typedef SListElement<E> element_type;
00638     typedef SListConstIterator<E> const_iterator;
00639     typedef SListIterator<E> iterator;
00640 
00642     bool empty() const { return SListPure<E>::empty(); }
00643 
00645     int size() const { return m_count; }
00646 
00648 
00651     const SListConstIterator<E> begin() const { return SListPure<E>::begin(); }
00652 
00654 
00657     SListIterator<E> begin() { return SListPure<E>::begin(); }
00658 
00660 
00663     SListConstIterator<E> end() const { return SListConstIterator<E>(); }
00664 
00666 
00669     SListIterator<E> end() { return SListIterator<E>(); }
00670 
00672 
00675     const SListConstIterator<E> rbegin() const { return SListPure<E>::rbegin(); }
00676 
00678 
00681     SListIterator<E> rbegin() { return SListPure<E>::rbegin(); }
00682 
00683 
00685 
00688     SListConstIterator<E> get(int pos) const {
00689         return SListPure<E>::get(pos);
00690     }
00691 
00693 
00696     SListIterator<E> get(int pos) {
00697         return SListPure<E>::get(pos);
00698     }
00699 
00701 
00705     int pos(SListConstIterator<E> it) const {
00706         return SListPure<E>::pos(it);;
00707     }
00708 
00709     
00711 
00714     const E &front() const { return SListPure<E>::front(); }
00715 
00717 
00720     E &front() { return SListPure<E>::front(); }
00721 
00723 
00726     const E &back() const { return SListPure<E>::back(); }
00727 
00729 
00732     E &back() { return SListPure<E>::back(); }
00733 
00735 
00738     SListConstIterator<E> cyclicSucc(SListConstIterator<E> it) const {
00739         return SListPure<E>::cyclicSucc(it);
00740     }
00741 
00743 
00746     SListIterator<E> cyclicSucc(SListIterator<E> it) {
00747         return SListPure<E>::cyclicSucc(it);
00748     }
00749 
00751     SList<E> &operator=(const SList<E> &L) {
00752         SListPure<E>::operator=(L);
00753         m_count = L.m_count;
00754         return *this;
00755     }
00756 
00758     SListIterator<E> pushFront(const E &x) {
00759         ++m_count;
00760         return SListPure<E>::pushFront(x);
00761     }
00762 
00764     SListIterator<E> pushBack(const E &x) {
00765         ++m_count;
00766         return SListPure<E>::pushBack(x);
00767     }
00768 
00770 
00773     SListIterator<E> insertAfter(const E &x, SListIterator<E> itBefore) {
00774         ++m_count;
00775         return SListPure<E>::insertAfter(x, itBefore);
00776     }
00777 
00779 
00782     void popFront() {
00783         --m_count;
00784         SListPure<E>::popFront();
00785     }
00786 
00788 
00791     E popFrontRet() {
00792         E el = front(); 
00793         popFront();
00794         return el;
00795     }
00796 
00798 
00801     void delSucc(SListIterator<E> itBefore) {
00802         --m_count;
00803         SListPure<E>::delSucc(itBefore);
00804     }
00805 
00807     void moveFrontToFront(SList<E> &L2) {
00808         SListPure<E>::moveFrontToFront(L2);
00809         --m_count; ++L2.m_count;
00810     }
00811 
00813     void moveFrontToBack(SList<E> &L2) {
00814         SListPure<E>::moveFrontToBack(L2);
00815         --m_count; ++L2.m_count;
00816     }
00817 
00819 
00822     void moveFrontToSucc(SList<E> &L2, SListIterator<E> itBefore) {
00823         SListPure<E>::moveFrontToSucc(L2,itBefore);
00824         --m_count; ++L2.m_count;
00825     }
00826 
00828     void clear() {
00829         m_count = 0;
00830         SListPure<E>::clear();
00831     }
00832 
00834     void conc(SList<E> &L2) {
00835         SListPure<E>::conc(L2);
00836         m_count += L2.m_count;
00837         L2.m_count = 0;
00838     }
00839 
00841     void reverse() {
00842         SListPure<E>::reverse();
00843     }
00844 
00846     const SListPure<E> &getListPure() const { return *this; }
00847 
00849     void quicksort() {
00850         ogdf::quicksortTemplate(*this);
00851     }
00852 
00854     template<class COMPARER>
00855     void quicksort(const COMPARER &comp) {
00856         ogdf::quicksortTemplate(*this,comp);
00857     }
00858 
00860 
00867     void bucketSort(int l, int h, BucketFunc<E> &f) {
00868         SListPure<E>::bucketSort(l,h,f);
00869     }
00870 
00872     void bucketSort(BucketFunc<E> &f) {
00873         SListPure<E>::bucketSort(f);
00874     }
00875 
00877     void permute() {
00878         SListPure<E>::permute(m_count);
00879     }
00880 
00882     int search (const E& e) const {
00883         return SListPure<E>::search(e);
00884     }
00885 
00887     template<class COMPARER>
00888     int search (const E& e, const COMPARER &comp) const {
00889         return SListPure<E>::search(e, comp);
00890     }
00891 
00892     OGDF_NEW_DELETE
00893 }; // class SList
00894 
00895 
00896 
00897 
00898 // sorts list L using bucket sort
00899 // computes l and h value
00900 template<class E>
00901 void SListPure<E>::bucketSort(BucketFunc<E> &f)
00902 {
00903     // if less than two elements, nothing to do
00904     if (m_head == m_tail) return;
00905 
00906     int l, h;
00907     l = h = f.getBucket(m_head->m_x);
00908     
00909     SListElement<E> *pX;
00910     for(pX = m_head->m_next; pX; pX = pX->m_next)
00911     {
00912         int i = f.getBucket(pX->m_x);
00913         if (i < l) l = i;
00914         if (i > h) h = i;
00915     }
00916 
00917     bucketSort(l,h,f);
00918 }
00919 
00920     
00921 // sorts list L using bucket sort
00922 template<class E>
00923 void SListPure<E>::bucketSort(int l, int h, BucketFunc<E> &f)
00924 {
00925     // if less than two elements, nothing to do
00926     if (m_head == m_tail) return;
00927 
00928     Array<SListElement<E> *> head(l,h,0), tail(l,h);
00929     
00930     SListElement<E> *pX;
00931     for (pX = m_head; pX; pX = pX->m_next) {
00932         int i = f.getBucket(pX->m_x);
00933         if (head[i])
00934             tail[i] = (tail[i]->m_next = pX);
00935         else
00936             head[i] = tail[i] = pX;
00937     }
00938 
00939     SListElement<E> *pY = 0;
00940     for (int i = l; i <= h; i++) {
00941         pX = head[i];
00942         if (pX) {
00943             if (pY)
00944                 pY->m_next = pX;
00945             else
00946                 m_head = pX;
00947             pY = tail[i];
00948         }
00949     }
00950     
00951     m_tail = pY;
00952     pY->m_next = 0;
00953 }
00954 
00955 
00956 // permutes elements in list randomly; n is the length of the list
00957 template<class E>
00958 void SListPure<E>::permute(const int n)
00959 {
00960     Array<SListElement<E> *> A(n+1);
00961     A[n] = 0;
00962 
00963     int i = 0;
00964     SListElement<E> *pX;
00965     for (pX = m_head; pX; pX = pX->m_next)
00966         A[i++] = pX;
00967 
00968     A.permute(0,n-1);
00969 
00970     for (i = 0; i < n; i++) {
00971         A[i]->m_next = A[i+1];
00972     }
00973 
00974     m_head = A[0];
00975     m_tail = A[n-1];
00976 }
00977 
00978 // prints list to output stream os using delimiter delim
00979 template<class E>
00980 void print(ostream &os, const SListPure<E> &L, char delim = ' ')
00981 {
00982     SListConstIterator<E> pX = L.begin();
00983     if (pX.valid()) {
00984         os << *pX;
00985         for(++pX; pX.valid(); ++pX)
00986             os << delim << *pX;
00987     }
00988 }
00989 
00990 // prints list to output stream os using delimiter delim
00991 template<class E>
00992 void print(ostream &os, const SList<E> &L, char delim = ' ')
00993 {
00994     print(L.getListPure(), delim);
00995 }
00996 
00997 // output operator
00998 template<class E>
00999 ostream &operator<<(ostream &os, const SListPure<E> &L)
01000 {
01001     print(os,L);
01002     return os;
01003 }
01004 
01005 template<class E>
01006 ostream &operator<<(ostream &os, const SList<E> &L)
01007 {
01008     return operator<<(os,L.getListPure());
01009 }
01010 
01011 
01012 // sort array using bucket sort and bucket object f;
01013 // the values of f must be in the interval [min,max]
01014 template<class E>
01015 void bucketSort(Array<E> &a, int min, int max, BucketFunc<E> &f)
01016 {
01017     if (a.low() >= a.high()) return;
01018 
01019     Array<SListPure<E> > bucket(min,max);
01020 
01021     int i;
01022     for(i = a.low(); i <= a.high(); ++i)
01023         bucket[f.getBucket(a[i])].pushBack(a[i]);
01024 
01025     i = a.low();
01026     for(int j = min; j <= max; ++j) {
01027         SListConstIterator<E> it = bucket[j].begin();
01028         for(; it.valid(); ++it)
01029             a[i++] = *it;
01030     }
01031 }
01032 
01033 
01034 
01035 
01036 } // namespace ogdf
01037 
01038 
01039 #endif