26 template<
typename T,
class A>
29 template<
typename T,
class A>
30 class SLListConstIterator;
32 template<
typename T,
class A>
33 class SLListModifyIterator;
42 template<
typename T,
class A=std::allocator<T> >
64 using Allocator =
typename std::allocator_traits<A>::template rebind_alloc<Element>;
84 template<
typename T1,
typename A1>
225 void deleteNext(Element* current);
240 template<
bool watchForTail>
241 void deleteNext(Element* current);
247 void insertAfter(Element* current,
const T& item);
269 template<
typename T,
class A>
279 : current_(item), list_(sllist)
283 : current_(0), list_(0)
287 : current_(other.iterator_.current_), list_(other.iterator_.list_)
296 return current_->item_;
306 return current_==other.current_;
316 return current_==other.current_;
326 return current_==other.iterator_.current_;
334 current_ = current_->next_;
345 list_->insertAfter(current_, v);
356 list_->deleteNext(current_);
369 template<
class T,
class A>
385 : current_(other.current_)
389 : current_(other.iterator_.current_)
398 return current_->item_;
408 return current_==other.current_;
416 current_ = current_->next_;
427 template<
typename T,
class A>
435 : beforeIterator_(beforeIterator), iterator_(_iterator)
439 : beforeIterator_(), iterator_()
458 return iterator_== other;
469 return iterator_== other;
480 return iterator_== other.iterator_;
507 beforeIterator_.insertAfter(v);
521 beforeIterator_.deleteNext();
531 template<
typename T,
typename A>
535 Iterator end = sllist.
end();
536 Iterator current= sllist.
begin();
541 os<<*current<<
" ("<<
static_cast<const void*
>(&(*current))<<
")";
544 for(; current != end; ++current)
545 os<<
", "<<*current<<
" ("<<
static_cast<const void*
>(&(*current))<<
")";
551 template<
typename T,
class A>
553 : next_(next), item_(item)
556 template<
typename T,
class A>
561 template<
typename T,
class A>
567 template<
typename T,
class A>
569 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
572 assert(&beforeHead_==tail_);
573 assert(tail_->next_==0);
576 template<
typename T,
class A>
578 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
583 template<
typename T,
class A>
584 template<
typename T1,
class A1>
586 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
591 template<
typename T,
typename A>
594 assert(tail_==&beforeHead_);
597 Iterator iend = other.
end();
598 for(Iterator element=other.
begin(); element != iend; ++element)
601 assert(other.
size()==size());
604 template<
typename T,
class A>
610 template<
typename T,
class A>
613 if(size()!=other.
size())
616 iter != end(); ++iter, ++oiter)
622 template<
typename T,
class A>
625 if(size()==other.
size()) {
627 iter != end(); ++iter, ++oiter)
634 template<
typename T,
class A>
642 template<
typename T,
class A>
645 assert(size_>0 || tail_==&beforeHead_);
646 tail_->next_ = allocator_.allocate(1);
647 assert(size_>0 || tail_==&beforeHead_);
648 tail_ = tail_->next_;
649 ::new (
static_cast<void*
>(&(tail_->item_)))T(item);
651 assert(tail_->next_==0);
655 template<
typename T,
class A>
661 bool changeTail = (current == tail_);
665 Element* tmp = current->next_;
667 assert(!changeTail || !tmp);
670 current->next_ = allocator_.allocate(1);
673 std::allocator_traits<Allocator>::construct(allocator_, current->next_, Element(item,tmp));
677 if(!current->next_->next_) {
680 tail_ = current->next_;
683 assert(!tail_->next_);
686 template<
typename T,
class A>
689 if(tail_ == &beforeHead_) {
691 beforeHead_.next_ = tail_ = allocator_.allocate(1, 0);
692 ::new(
static_cast<void*
>(&beforeHead_.next_->item_))T(item);
693 beforeHead_.next_->next_=0;
695 Element* added = allocator_.allocate(1, 0);
696 ::new(
static_cast<void*
>(&added->item_))T(item);
697 added->next_=beforeHead_.next_;
698 beforeHead_.next_=added;
700 assert(tail_->next_==0);
705 template<
typename T,
class A>
708 this->
template deleteNext<true>(current);
711 template<
typename T,
class A>
712 template<
bool watchForTail>
713 inline void SLList<T,A>::deleteNext(Element* current)
715 assert(current->next_);
716 Element* next = current->next_;
724 current->next_ = next->next_;
725 std::allocator_traits<Allocator>::destroy(allocator_, next);
726 allocator_.deallocate(next, 1);
728 assert(!watchForTail || &beforeHead_ != tail_ || size_==0);
731 template<
typename T,
class A>
734 deleteNext(&beforeHead_);
737 template<
typename T,
class A>
740 while(beforeHead_.next_ ) {
741 this->
template deleteNext<false>(&beforeHead_);
746 tail_ = &beforeHead_;
749 template<
typename T,
class A>
752 return (&beforeHead_ == tail_);
755 template<
typename T,
class A>
761 template<
typename T,
class A>
764 return iterator(beforeHead_.next_,
this);
767 template<
typename T,
class A>
773 template<
typename T,
class A>
779 template<
typename T,
class A>
786 template<
typename T,
class A>
793 template<
typename T,
class A>
This file implements iterator facade classes for writing stl conformant iterators.
void push_front(const MemberType &item)
Add a new entry to the beginning of the list.
Definition sllist.hh:687
bool equals(const SLListConstIterator< T, A > &other) const
Equality test for the iterator facade.
Definition sllist.hh:406
void push_back(const MemberType &item)
Add a new entry to the end of the list.
Definition sllist.hh:643
ModifyIterator endModify()
Get an iterator capable of deleting and inserting elements.
Definition sllist.hh:780
SLListModifyIterator()
Definition sllist.hh:438
Element()
Definition sllist.hh:557
T & dereference() const
Dereferencing function for the iterator facade.
Definition sllist.hh:294
bool operator!=(const SLList &sl) const
Definition sllist.hh:623
MemberType item_
The element we hold.
Definition sllist.hh:212
SLListConstIterator(typename SLList< T, A >::Element *item)
Definition sllist.hh:380
typename std::allocator_traits< A >::template rebind_alloc< Element > Allocator
The allocator to use.
Definition sllist.hh:64
void insertAfter(const T &v) const
Insert an element in the underlying list after the current position.
Definition sllist.hh:342
SLListIterator< T, A > iterator
The mutable iterator of the list.
Definition sllist.hh:69
SLListConstIterator(const SLListModifyIterator< T, A > &other)
Definition sllist.hh:388
SLListIterator()
Definition sllist.hh:282
~Element()
Definition sllist.hh:562
bool operator==(const SLList &sl) const
Definition sllist.hh:611
void deleteNext() const
Delete the entry after the current position.
Definition sllist.hh:353
SLList(const SLList< T, A > &other)
Copy constructor.
Definition sllist.hh:577
bool equals(const SLListModifyIterator< T, A > &other) const
Equality test for the iterator facade.
Definition sllist.hh:324
T & dereference() const
Dereferencing function for the iterator facade.
Definition sllist.hh:446
int size() const
Get the number of elements the list contains.
Definition sllist.hh:756
const_iterator begin() const
Get an iterator pointing to the first element in the list.
Definition sllist.hh:768
iterator end()
Get an iterator pointing to the end of the list.
Definition sllist.hh:774
void clear()
Remove all elements from the list.
Definition sllist.hh:738
SLList(const SLList< T1, A1 > &other)
Copy constructor with type conversion.
Definition sllist.hh:585
T MemberType
The type we store.
Definition sllist.hh:59
bool equals(const SLListModifyIterator< T, A > &other) const
Test whether another iterator is equal.
Definition sllist.hh:478
ModifyIterator beginModify()
Get an iterator capable of deleting and inserting elements.
Definition sllist.hh:787
SLList< T, A > & operator=(const SLList< T, A > &other)
Assignment operator.
Definition sllist.hh:635
SLListConstIterator(const SLListIterator< T, A > &other)
Definition sllist.hh:384
SLListConstIterator< T, A > const_iterator
The constant iterator of the list.
Definition sllist.hh:74
bool empty() const
Check whether the list is empty.
Definition sllist.hh:750
SLListConstIterator()
Definition sllist.hh:376
bool equals(const SLListConstIterator< T, A > &other) const
Equality test for the iterator facade.
Definition sllist.hh:304
bool equals(const SLListConstIterator< T, A > &other) const
Test whether another iterator is equal.
Definition sllist.hh:456
SLListModifyIterator< T, A > ModifyIterator
The type of the iterator capable of deletion and insertion.
Definition sllist.hh:103
const_iterator end() const
Get an iterator pointing to the end of the list.
Definition sllist.hh:794
SLList()
Constructor.
Definition sllist.hh:568
void insert(const T &v)
Insert an element at the current position.
Definition sllist.hh:505
SLListIterator(typename SLList< T, A >::Element *item, SLList< T, A > *sllist)
Definition sllist.hh:277
SLListModifyIterator(SLListIterator< T, A > beforeIterator, SLListIterator< T, A > _iterator)
Definition sllist.hh:433
void pop_front()
Remove the first item in the list.
Definition sllist.hh:732
void increment()
Increment function for the iterator facade.
Definition sllist.hh:332
SLListIterator(const SLListModifyIterator< T, A > &other)
Definition sllist.hh:286
A::size_type size_type
The size type.
Definition sllist.hh:54
void remove()
Delete the entry at the current position.
Definition sllist.hh:518
const T & dereference() const
Dereferencing function for the facade.
Definition sllist.hh:396
Element * next_
The next element in the list.
Definition sllist.hh:208
void increment()
Increment function for the iterator facade.
Definition sllist.hh:486
void increment()
Increment function for the iterator facade.
Definition sllist.hh:414
~SLList()
Destructor.
Definition sllist.hh:605
bool equals(const SLListIterator< T, A > &other) const
Test whether another iterator is equal.
Definition sllist.hh:467
iterator begin()
Get an iterator pointing to the first element in the list.
Definition sllist.hh:762
bool equals(const SLListIterator< T, A > &other) const
Equality test for the iterator facade.
Definition sllist.hh:314
std::ostream & operator<<(std::ostream &s, const bigunsignedint< k > &x)
Definition bigunsignedint.hh:278
Dune namespace.
Definition alignedallocator.hh:13
Base class for stl conformant forward iterators.
Definition iteratorfacades.hh:141
A mutable iterator for the SLList.
Definition sllist.hh:271
A constant iterator for the SLList.
Definition sllist.hh:371
A mutable iterator for the SLList.
Definition sllist.hh:429
A single linked list.
Definition sllist.hh:44