24 template<
typename T,
class A>
27 template<
typename T,
class A>
30 template<
typename T,
class A>
40 template<
typename T,
class A=std::allocator<T> >
62 typedef typename A::template rebind<Element>::other
Allocator;
82 template<
typename T1,
typename A1>
113 inline void push_back(
const MemberType& item);
119 inline void push_front(
const MemberType& item);
136 inline iterator
begin();
145 inline const_iterator
begin()
const;
171 inline iterator
end();
179 inline const_iterator
end()
const;
186 inline bool empty()
const;
192 inline int size()
const;
212 Element(
const MemberType& item, Element* next_=0);
223 void deleteNext(Element* current);
238 template<
bool watchForTail>
239 void deleteNext(Element* current);
245 void insertAfter(Element* current,
const T& item);
258 Allocator allocator_;
267 template<
typename T,
class A>
277 : current_(item), list_(sllist)
281 : current_(0), list_(0)
285 : current_(other.iterator_.current_), list_(other.iterator_.list_)
294 return current_->item_;
304 return current_==other.current_;
314 return current_==other.current_;
324 return current_==other.iterator_.current_;
332 current_ = current_->next_;
343 list_->insertAfter(current_, v);
354 list_->deleteNext(current_);
367 template<
class T,
class A>
383 : current_(other.current_)
387 : current_(other.current_)
391 : current_(other.iterator_.current_)
400 return current_->item_;
410 return current_==other.current_;
418 current_ = current_->next_;
429 template<
typename T,
class A>
437 : beforeIterator_(beforeIterator), iterator_(_iterator)
441 : beforeIterator_(other.beforeIterator_), iterator_(other.iterator_)
445 : beforeIterator_(), iterator_()
464 return iterator_== other;
475 return iterator_== other;
486 return iterator_== other.iterator_;
513 beforeIterator_.insertAfter(v);
527 beforeIterator_.deleteNext();
541 template<
typename T,
typename A>
542 ostream& operator<<(ostream& os, const Dune::SLList<T,A> sllist)
545 Iterator
end = sllist.end();
546 Iterator current= sllist.begin();
551 os<<*current<<
" ("<<
static_cast<const void*
>(&(*current))<<
")";
554 for(; current !=
end; ++current)
555 os<<
", "<<*current<<
" ("<<static_cast<const void*>(&(*current))<<
")";
565 template<
typename T,
class A>
567 : next_(next), item_(item)
570 template<
typename T,
class A>
575 template<
typename T,
class A>
581 template<
typename T,
class A>
583 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
586 assert(&beforeHead_==tail_);
587 assert(tail_->next_==0);
590 template<
typename T,
class A>
592 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
597 template<
typename T,
class A>
598 template<
typename T1,
class A1>
600 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
605 template<
typename T,
typename A>
608 assert(tail_==&beforeHead_);
611 Iterator iend = other.
end();
612 for(Iterator element=other.
begin(); element != iend; ++element)
615 assert(other.
size()==size());
618 template<
typename T,
class A>
624 template<
typename T,
class A>
627 if(size()!=other.
size())
630 iter != end(); ++iter, ++oiter)
636 template<
typename T,
class A>
639 if(size()==other.
size()) {
641 iter != end(); ++iter, ++oiter)
648 template<
typename T,
class A>
656 template<
typename T,
class A>
659 assert(size_>0 || tail_==&beforeHead_);
660 tail_->next_ = allocator_.allocate(1, 0);
661 assert(size_>0 || tail_==&beforeHead_);
662 tail_ = tail_->next_;
663 ::new (static_cast<void*>(&(tail_->item_)))T(item);
665 assert(tail_->next_==0);
669 template<
typename T,
class A>
675 bool changeTail = (current == tail_);
679 Element* tmp = current->next_;
681 assert(!changeTail || !tmp);
684 current->next_ = allocator_.allocate(1, 0);
687 allocator_.construct(current->next_, Element(item,tmp));
691 if(!current->next_->next_) {
694 tail_ = current->next_;
697 assert(!tail_->next_);
700 template<
typename T,
class A>
703 if(tail_ == &beforeHead_) {
705 beforeHead_.next_ = tail_ = allocator_.allocate(1, 0);
706 ::new(static_cast<void*>(&beforeHead_.next_->item_))T(item);
707 beforeHead_.next_->next_=0;
709 Element* added = allocator_.allocate(1, 0);
710 ::new(static_cast<void*>(&added->item_))T(item);
711 added->next_=beforeHead_.next_;
712 beforeHead_.next_=added;
714 assert(tail_->next_==0);
719 template<
typename T,
class A>
722 this->
template deleteNext<true>(current);
725 template<
typename T,
class A>
726 template<
bool watchForTail>
729 assert(current->next_);
730 Element* next = current->next_;
738 current->next_ = next->next_;
739 allocator_.destroy(next);
740 allocator_.deallocate(next, 1);
742 assert(!watchForTail || &beforeHead_ != tail_ || size_==0);
745 template<
typename T,
class A>
748 deleteNext(&beforeHead_);
751 template<
typename T,
class A>
754 while(beforeHead_.next_ ) {
755 this->
template deleteNext<false>(&beforeHead_);
760 tail_ = &beforeHead_;
763 template<
typename T,
class A>
766 return (&beforeHead_ == tail_);
769 template<
typename T,
class A>
775 template<
typename T,
class A>
778 return iterator(beforeHead_.next_,
this);
781 template<
typename T,
class A>
787 template<
typename T,
class A>
793 template<
typename T,
class A>
800 template<
typename T,
class A>
807 template<
typename T,
class A>
iterator begin()
Get an iterator pointing to the first element in the list.
Definition: sllist.hh:776
SLListConstIterator(const SLListIterator< T, A > &other)
Definition: sllist.hh:382
void increment()
Increment function for the iterator facade.
Definition: sllist.hh:492
SLList< T, A > & operator=(const SLList< T, A > &other)
Assignment operator.
Definition: sllist.hh:649
bool equals(const SLListIterator< T, A > &other) const
Test whether another iterator is equal.
Definition: sllist.hh:473
void clear()
Remove all elements from the list.
Definition: sllist.hh:752
bool empty() const
Check whether the list is empty.
Definition: sllist.hh:764
T & dereference() const
Dereferencing function for the iterator facade.
Definition: sllist.hh:292
SLList()
Constructor.
Definition: sllist.hh:582
bool equals(const SLListConstIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:408
A mutable iterator for the SLList.
Definition: sllist.hh:31
EnableIfInterOperable< T1, T2, bool >::type operator==(const ForwardIteratorFacade< T1, V1, R1, D > &lhs, const ForwardIteratorFacade< T2, V2, R2, D > &rhs)
Checks for equality.
Definition: iteratorfacades.hh:233
SLListIterator< T, A > iterator
The mutable iterator of the list.
Definition: sllist.hh:67
SLListModifyIterator(const SLListModifyIterator< T, A > &other)
Definition: sllist.hh:440
void increment()
Increment function for the iterator facade.
Definition: sllist.hh:416
bool equals(const SLListModifyIterator< T, A > &other) const
Test whether another iterator is equal.
Definition: sllist.hh:484
void insert(const T &v)
Insert an element at the current position.
Definition: sllist.hh:511
ModifyIterator endModify()
Get an iterator capable of deleting and inserting elements.
Definition: sllist.hh:794
bool equals(const SLListIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:312
This file implements iterator facade classes for writing stl conformant iterators.
bool equals(const SLListModifyIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:322
EnableIfInterOperable< T1, T2, bool >::type operator!=(const ForwardIteratorFacade< T1, V1, R1, D > &lhs, const ForwardIteratorFacade< T2, V2, R2, D > &rhs)
Checks for inequality.
Definition: iteratorfacades.hh:255
SLListModifyIterator(SLListIterator< T, A > beforeIterator, SLListIterator< T, A > _iterator)
Definition: sllist.hh:435
SLListIterator(const SLListModifyIterator< T, A > &other)
Definition: sllist.hh:284
void push_back(const MemberType &item)
Add a new entry to the end of the list.
Definition: sllist.hh:657
Dune namespace.
Definition: alignedallocator.hh:9
SLListModifyIterator()
Definition: sllist.hh:444
ModifyIterator beginModify()
Get an iterator capable of deleting and inserting elements.
Definition: sllist.hh:801
bool operator!=(const SLList &sl) const
Definition: sllist.hh:637
A constant iterator for the SLList.
Definition: sllist.hh:28
void deleteNext() const
Delete the entry after the current position.
Definition: sllist.hh:351
T & dereference() const
Dereferencing function for the iterator facade.
Definition: sllist.hh:452
iterator end()
Get an iterator pointing to the end of the list.
Definition: sllist.hh:788
SLListIterator(typename SLList< T, A >::Element *item, SLList< T, A > *sllist)
Definition: sllist.hh:275
SLListModifyIterator< T, A > ModifyIterator
The type of the iterator capable of deletion and insertion.
Definition: sllist.hh:101
bool equals(const SLListConstIterator< T, A > &other) const
Test whether another iterator is equal.
Definition: sllist.hh:462
A single linked list.
Definition: sllist.hh:41
int size() const
Get the number of elements the list contains.
Definition: sllist.hh:770
const T & dereference() const
Dereferencing function for the facade.
Definition: sllist.hh:398
A mutable iterator for the SLList.
Definition: sllist.hh:25
void increment()
Increment function for the iterator facade.
Definition: sllist.hh:330
void push_front(const MemberType &item)
Add a new entry to the beginning of the list.
Definition: sllist.hh:701
SLListConstIterator(typename SLList< T, A >::Element *item)
Definition: sllist.hh:378
A::size_type size_type
The size type.
Definition: sllist.hh:52
A::template rebind< Element >::other Allocator
The allocator to use.
Definition: sllist.hh:62
bool equals(const SLListConstIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:302
bool operator==(const SLList &sl) const
Definition: sllist.hh:625
MemberType item_
The element we hold.
Definition: sllist.hh:210
void pop_front()
Remove the first item in the list.
Definition: sllist.hh:746
T MemberType
The type we store.
Definition: sllist.hh:57
SLListConstIterator()
Definition: sllist.hh:374
Element * next_
The next element in the list.
Definition: sllist.hh:206
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:138
SLListConstIterator(const SLListConstIterator< T, A > &other)
Definition: sllist.hh:386
void insertAfter(const T &v) const
Insert an element in the underlying list after the current position.
Definition: sllist.hh:340
SLListConstIterator(const SLListModifyIterator< T, A > &other)
Definition: sllist.hh:390
SLListIterator()
Definition: sllist.hh:280
~SLList()
Destructor.
Definition: sllist.hh:619
SLListConstIterator< T, A > const_iterator
The constant iterator of the list.
Definition: sllist.hh:72