00001
00002
00003 #ifndef DUNE_SLLIST_HH
00004 #define DUNE_SLLIST_HH
00005
00006 #include <memory>
00007 #include <cassert>
00008 #include "iteratorfacades.hh"
00009 #include <ostream>
00010
00011 namespace Dune
00012 {
00024 template<typename T, class A>
00025 class SLListIterator;
00026
00027 template<typename T, class A>
00028 class SLListConstIterator;
00029
00030 template<typename T, class A>
00031 class SLListModifyIterator;
00032
00040 template<typename T, class A=std::allocator<T> >
00041 class SLList
00042 {
00043 struct Element;
00044 friend class SLListIterator<T,A>;
00045 friend class SLListConstIterator<T,A>;
00046
00047 public:
00048
00052 typedef typename A::size_type size_type;
00053
00057 typedef T MemberType;
00058
00062 typedef typename A::template rebind<Element>::other Allocator;
00063
00067 typedef SLListIterator<T,A> iterator;
00068
00072 typedef SLListConstIterator<T,A> const_iterator;
00073
00077 SLList();
00078
00082 template<typename T1, typename A1>
00083 SLList(const SLList<T1,A1>& other);
00084
00088 SLList(const SLList<T,A>& other);
00089
00095 ~SLList();
00096
00101 typedef SLListModifyIterator<T,A> ModifyIterator;
00102
00106 SLList<T,A>& operator=(const SLList<T,A>& other);
00107
00108
00113 inline void push_back(const MemberType& item);
00114
00119 inline void push_front(const MemberType& item);
00120
00124 inline void pop_front();
00125
00127 inline void clear();
00128
00136 inline iterator begin();
00137
00145 inline const_iterator begin() const;
00146
00154 inline ModifyIterator beginModify();
00155
00163 inline ModifyIterator endModify();
00164
00171 inline iterator end();
00172
00179 inline const_iterator end() const;
00180
00186 inline bool empty() const;
00187
00192 inline int size() const;
00193
00194 bool operator==(const SLList& sl) const;
00195
00196
00197 bool operator!=(const SLList& sl) const;
00198
00199 private:
00201 struct Element
00202 {
00206 Element* next_;
00210 MemberType item_;
00211
00212 Element(const MemberType& item, Element* next_=0);
00213
00214 Element();
00215
00216 ~Element();
00217 };
00218
00223 void deleteNext(Element* current);
00224
00229 void copyElements(const SLList<T,A>& other);
00230
00238 template<bool watchForTail>
00239 void deleteNext(Element* current);
00245 void insertAfter(Element* current, const T& item);
00246
00248 Element beforeHead_;
00249
00255 Element* tail_;
00256
00258 Allocator allocator_;
00259
00261 int size_;
00262 };
00263
00267 template<typename T, class A>
00268 class SLListIterator : public Dune::ForwardIteratorFacade<SLListIterator<T,A>, T, T&, std::size_t>
00269 {
00270 friend class SLListConstIterator<T,A>;
00271 friend class SLListModifyIterator<T,A>;
00272 friend class SLList<T,A>;
00273
00274 public:
00275 inline SLListIterator(typename SLList<T,A>::Element* item,
00276 SLList<T,A>* sllist)
00277 : current_(item), list_(sllist)
00278 {}
00279
00280 inline SLListIterator()
00281 : current_(0), list_(0)
00282 {}
00283
00284 inline SLListIterator(const SLListModifyIterator<T,A>& other)
00285 : current_(other.iterator_.current_), list_(other.iterator_.list_)
00286 {}
00287
00292 inline T& dereference() const
00293 {
00294 return current_->item_;
00295 }
00296
00302 inline bool equals(const SLListConstIterator<T,A>& other) const
00303 {
00304 return current_==other.current_;
00305 }
00306
00312 inline bool equals(const SLListIterator<T,A>& other) const
00313 {
00314 return current_==other.current_;
00315 }
00316
00322 inline bool equals(const SLListModifyIterator<T,A>& other) const
00323 {
00324 return current_==other.iterator_.current_;
00325 }
00326
00330 inline void increment()
00331 {
00332 current_ = current_->next_;
00333 }
00334
00340 inline void insertAfter(const T& v) const
00341 {
00342 assert(list_ );
00343 list_->insertAfter(current_, v);
00344 }
00345
00351 inline void deleteNext() const
00352 {
00353 assert(list_);
00354 list_->deleteNext(current_);
00355 }
00356
00357 private:
00359 typename SLList<T,A>::Element* current_;
00361 SLList<T,A>* list_;
00362 };
00363
00367 template<class T, class A>
00368 class SLListConstIterator : public Dune::ForwardIteratorFacade<SLListConstIterator<T,A>, const T, const T&, std::size_t>
00369 {
00370 friend class SLListIterator<T,A>;
00371 friend class SLList<T,A>;
00372
00373 public:
00374 inline SLListConstIterator()
00375 : current_(0)
00376 {}
00377
00378 inline SLListConstIterator(typename SLList<T,A>::Element* item)
00379 : current_(item)
00380 {}
00381
00382 inline SLListConstIterator(const SLListIterator<T,A>& other)
00383 : current_(other.current_)
00384 {}
00385
00386 inline SLListConstIterator(const SLListConstIterator<T,A>& other)
00387 : current_(other.current_)
00388 {}
00389
00390 inline SLListConstIterator(const SLListModifyIterator<T,A>& other)
00391 : current_(other.iterator_.current_)
00392 {}
00393
00398 inline const T& dereference() const
00399 {
00400 return current_->item_;
00401 }
00402
00408 inline bool equals(const SLListConstIterator<T,A>& other) const
00409 {
00410 return current_==other.current_;
00411 }
00412
00416 inline void increment()
00417 {
00418 current_ = current_->next_;
00419 }
00420
00421 private:
00423 typename SLList<T,A>::Element* current_;
00424 };
00425
00429 template<typename T, class A>
00430 class SLListModifyIterator : public Dune::ForwardIteratorFacade<SLListModifyIterator<T,A>, T, T&, std::size_t>
00431 {
00432 friend class SLListConstIterator<T,A>;
00433 friend class SLListIterator<T,A>;
00434 public:
00435 inline SLListModifyIterator(SLListIterator<T,A> beforeIterator,
00436 SLListIterator<T,A> _iterator)
00437 : beforeIterator_(beforeIterator), iterator_(_iterator)
00438 {}
00439
00440 inline SLListModifyIterator(const SLListModifyIterator<T,A>& other)
00441 : beforeIterator_(other.beforeIterator_), iterator_(other.iterator_)
00442 {}
00443
00444 inline SLListModifyIterator()
00445 : beforeIterator_(), iterator_()
00446 {}
00447
00452 inline T& dereference() const
00453 {
00454 return *iterator_;
00455 }
00456
00462 inline bool equals(const SLListConstIterator<T,A>& other) const
00463 {
00464 return iterator_== other;
00465 }
00466
00467
00473 inline bool equals(const SLListIterator<T,A>& other) const
00474 {
00475 return iterator_== other;
00476 }
00477
00478
00484 inline bool equals(const SLListModifyIterator<T,A>& other) const
00485 {
00486 return iterator_== other.iterator_;
00487 }
00488
00492 inline void increment()
00493 {
00494 ++iterator_;
00495 ++beforeIterator_;
00496 }
00497
00511 inline void insert(const T& v)
00512 {
00513 beforeIterator_.insertAfter(v);
00514 ++beforeIterator_;
00515 }
00516
00524 inline void remove()
00525 {
00526 ++iterator_;
00527 beforeIterator_.deleteNext();
00528 }
00529
00530 private:
00532 SLListIterator<T,A> beforeIterator_;
00534 SLListIterator<T,A> iterator_;
00535 };
00536 }
00537
00538 namespace std
00539 {
00540
00541 template<typename T, typename A>
00542 ostream& operator<<(ostream& os, const Dune::SLList<T,A> sllist)
00543 {
00544 typedef typename Dune::SLList<T,A>::const_iterator Iterator;
00545 Iterator end = sllist.end();
00546 Iterator current= sllist.begin();
00547
00548 os << "{ ";
00549
00550 if(current!=end) {
00551 os<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
00552 ++current;
00553
00554 for(; current != end; ++current)
00555 os<<", "<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
00556 }
00557 os<<"} ";
00558 return os;
00559 }
00560 }
00561
00562 namespace Dune
00563 {
00564
00565 template<typename T, class A>
00566 SLList<T,A>::Element::Element(const MemberType& item, Element* next)
00567 : next_(next), item_(item)
00568 {}
00569
00570 template<typename T, class A>
00571 SLList<T,A>::Element::Element()
00572 : next_(0), item_()
00573 {}
00574
00575 template<typename T, class A>
00576 SLList<T,A>::Element::~Element()
00577 {
00578 next_=0;
00579 }
00580
00581 template<typename T, class A>
00582 SLList<T,A>::SLList()
00583 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
00584 {
00585 beforeHead_.next_=0;
00586 assert(&beforeHead_==tail_);
00587 assert(tail_->next_==0);
00588 }
00589
00590 template<typename T, class A>
00591 SLList<T,A>::SLList(const SLList<T,A>& other)
00592 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
00593 {
00594 copyElements(other);
00595 }
00596
00597 template<typename T, class A>
00598 template<typename T1, class A1>
00599 SLList<T,A>::SLList(const SLList<T1,A1>& other)
00600 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
00601 {
00602 copyElements(other);
00603 }
00604
00605 template<typename T, typename A>
00606 void SLList<T,A>::copyElements(const SLList<T,A>& other)
00607 {
00608 assert(tail_==&beforeHead_);
00609 assert(size_==0);
00610 typedef typename SLList<T,A>::const_iterator Iterator;
00611 Iterator iend = other.end();
00612 for(Iterator element=other.begin(); element != iend; ++element)
00613 push_back(*element);
00614
00615 assert(other.size()==size());
00616 }
00617
00618 template<typename T, class A>
00619 SLList<T,A>::~SLList()
00620 {
00621 clear();
00622 }
00623
00624 template<typename T, class A>
00625 bool SLList<T,A>::operator==(const SLList& other) const
00626 {
00627 if(size()!=other.size())
00628 return false;
00629 for(const_iterator iter=begin(), oiter=other.begin();
00630 iter != end(); ++iter, ++oiter)
00631 if(*iter!=*oiter)
00632 return false;
00633 return true;
00634 }
00635
00636 template<typename T, class A>
00637 bool SLList<T,A>::operator!=(const SLList& other) const
00638 {
00639 if(size()==other.size()) {
00640 for(const_iterator iter=begin(), oiter=other.begin();
00641 iter != end(); ++iter, ++oiter)
00642 if(*iter!=*oiter)
00643 return true;
00644 return false;
00645 }else
00646 return true;
00647 }
00648 template<typename T, class A>
00649 SLList<T,A>& SLList<T,A>::operator=(const SLList<T,A>& other)
00650 {
00651 clear();
00652 copyElements(other);
00653 return *this;
00654 }
00655
00656 template<typename T, class A>
00657 inline void SLList<T,A>::push_back(const MemberType& item)
00658 {
00659 assert(size_>0 || tail_==&beforeHead_);
00660 tail_->next_ = allocator_.allocate(1, 0);
00661 assert(size_>0 || tail_==&beforeHead_);
00662 tail_ = tail_->next_;
00663 ::new (static_cast<void*>(&(tail_->item_)))T(item);
00664 tail_->next_=0;
00665 assert(tail_->next_==0);
00666 ++size_;
00667 }
00668
00669 template<typename T, class A>
00670 inline void SLList<T,A>::insertAfter(Element* current, const T& item)
00671 {
00672 assert(current);
00673
00674 #ifndef NDEBUG
00675 bool changeTail = (current == tail_);
00676 #endif
00677
00678
00679 Element* tmp = current->next_;
00680
00681 assert(!changeTail || !tmp);
00682
00683
00684 current->next_ = allocator_.allocate(1, 0);
00685
00686
00687 allocator_.construct(current->next_, Element(item,tmp));
00688
00689
00690
00691 if(!current->next_->next_) {
00692
00693 assert(changeTail);
00694 tail_ = current->next_;
00695 }
00696 ++size_;
00697 assert(!tail_->next_);
00698 }
00699
00700 template<typename T, class A>
00701 inline void SLList<T,A>::push_front(const MemberType& item)
00702 {
00703 if(tail_ == &beforeHead_) {
00704
00705 beforeHead_.next_ = tail_ = allocator_.allocate(1, 0);
00706 ::new(static_cast<void*>(&beforeHead_.next_->item_))T(item);
00707 beforeHead_.next_->next_=0;
00708 }else{
00709 Element* added = allocator_.allocate(1, 0);
00710 ::new(static_cast<void*>(&added->item_))T(item);
00711 added->next_=beforeHead_.next_;
00712 beforeHead_.next_=added;
00713 }
00714 assert(tail_->next_==0);
00715 ++size_;
00716 }
00717
00718
00719 template<typename T, class A>
00720 inline void SLList<T,A>::deleteNext(Element* current)
00721 {
00722 this->template deleteNext<true>(current);
00723 }
00724
00725 template<typename T, class A>
00726 template<bool watchForTail>
00727 inline void SLList<T,A>::deleteNext(Element* current)
00728 {
00729 assert(current->next_);
00730 Element* next = current->next_;
00731
00732 if(watchForTail)
00733 if(next == tail_) {
00734
00735 tail_ = current;
00736 }
00737
00738 current->next_ = next->next_;
00739 allocator_.destroy(next);
00740 allocator_.deallocate(next, 1);
00741 --size_;
00742 assert(!watchForTail || &beforeHead_ != tail_ || size_==0);
00743 }
00744
00745 template<typename T, class A>
00746 inline void SLList<T,A>::pop_front()
00747 {
00748 deleteNext(&beforeHead_);
00749 }
00750
00751 template<typename T, class A>
00752 inline void SLList<T,A>::clear()
00753 {
00754 while(beforeHead_.next_ ) {
00755 this->template deleteNext<false>(&beforeHead_);
00756 }
00757
00758 assert(size_==0);
00759
00760 tail_ = &beforeHead_;
00761 }
00762
00763 template<typename T, class A>
00764 inline bool SLList<T,A>::empty() const
00765 {
00766 return (&beforeHead_ == tail_);
00767 }
00768
00769 template<typename T, class A>
00770 inline int SLList<T,A>::size() const
00771 {
00772 return size_;
00773 }
00774
00775 template<typename T, class A>
00776 inline SLListIterator<T,A> SLList<T,A>::begin()
00777 {
00778 return iterator(beforeHead_.next_, this);
00779 }
00780
00781 template<typename T, class A>
00782 inline SLListConstIterator<T,A> SLList<T,A>::begin() const
00783 {
00784 return const_iterator(beforeHead_.next_);
00785 }
00786
00787 template<typename T, class A>
00788 inline SLListIterator<T,A> SLList<T,A>::end()
00789 {
00790 return iterator();
00791 }
00792
00793 template<typename T, class A>
00794 inline SLListModifyIterator<T,A> SLList<T,A>::endModify()
00795 {
00796 return SLListModifyIterator<T,A>(iterator(tail_, this),iterator());
00797 }
00798
00799
00800 template<typename T, class A>
00801 inline SLListModifyIterator<T,A> SLList<T,A>::beginModify()
00802 {
00803 return SLListModifyIterator<T,A>(iterator(&beforeHead_, this),
00804 iterator(beforeHead_.next_, this));
00805 }
00806
00807 template<typename T, class A>
00808 inline SLListConstIterator<T,A> SLList<T,A>::end() const
00809 {
00810 return const_iterator();
00811 }
00812
00814 }
00815 #endif