dune-common  2.3.1
sllist.hh
Go to the documentation of this file.
1 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 // vi: set et ts=4 sw=2 sts=2:
3 // $Id$
4 #ifndef DUNE_SLLIST_HH
5 #define DUNE_SLLIST_HH
6 
7 #include <memory>
8 #include <cassert>
9 #include "iteratorfacades.hh"
10 #include <ostream>
11 
12 namespace Dune
13 {
25  template<typename T, class A>
27 
28  template<typename T, class A>
30 
31  template<typename T, class A>
33 
41  template<typename T, class A=std::allocator<T> >
42  class SLList
43  {
44  struct Element;
45  friend class SLListIterator<T,A>;
46  friend class SLListConstIterator<T,A>;
47 
48  public:
49 
53  typedef typename A::size_type size_type;
54 
58  typedef T MemberType;
59 
63  typedef typename A::template rebind<Element>::other Allocator;
64 
69 
74 
78  SLList();
79 
83  template<typename T1, typename A1>
84  SLList(const SLList<T1,A1>& other);
85 
89  SLList(const SLList<T,A>& other);
90 
96  ~SLList();
97 
103 
107  SLList<T,A>& operator=(const SLList<T,A>& other);
108 
109 
114  inline void push_back(const MemberType& item);
115 
120  inline void push_front(const MemberType& item);
121 
125  inline void pop_front();
126 
128  inline void clear();
129 
137  inline iterator begin();
138 
146  inline const_iterator begin() const;
147 
155  inline ModifyIterator beginModify();
156 
164  inline ModifyIterator endModify();
165 
172  inline iterator end();
173 
180  inline const_iterator end() const;
181 
187  inline bool empty() const;
188 
193  inline int size() const;
194 
195  bool operator==(const SLList& sl) const;
196 
197 
198  bool operator!=(const SLList& sl) const;
199 
200  private:
202  struct Element
203  {
207  Element* next_;
211  MemberType item_;
212 
213  Element(const MemberType& item, Element* next_=0);
214 
215  Element();
216 
217  ~Element();
218  };
219 
224  void deleteNext(Element* current);
225 
230  void copyElements(const SLList<T,A>& other);
231 
239  template<bool watchForTail>
240  void deleteNext(Element* current);
246  void insertAfter(Element* current, const T& item);
247 
249  Element beforeHead_;
250 
256  Element* tail_;
257 
259  Allocator allocator_;
260 
262  int size_;
263  };
264 
268  template<typename T, class A>
269  class SLListIterator : public Dune::ForwardIteratorFacade<SLListIterator<T,A>, T, T&, std::size_t>
270  {
271  friend class SLListConstIterator<T,A>;
272  friend class SLListModifyIterator<T,A>;
273  friend class SLList<T,A>;
274 
275  public:
276  inline SLListIterator(typename SLList<T,A>::Element* item,
277  SLList<T,A>* sllist)
278  : current_(item), list_(sllist)
279  {}
280 
281  inline SLListIterator()
282  : current_(0), list_(0)
283  {}
284 
286  : current_(other.iterator_.current_), list_(other.iterator_.list_)
287  {}
288 
293  inline T& dereference() const
294  {
295  return current_->item_;
296  }
297 
303  inline bool equals(const SLListConstIterator<T,A>& other) const
304  {
305  return current_==other.current_;
306  }
307 
313  inline bool equals(const SLListIterator<T,A>& other) const
314  {
315  return current_==other.current_;
316  }
317 
323  inline bool equals(const SLListModifyIterator<T,A>& other) const
324  {
325  return current_==other.iterator_.current_;
326  }
327 
331  inline void increment()
332  {
333  current_ = current_->next_;
334  }
335 
341  inline void insertAfter(const T& v) const
342  {
343  assert(list_ );
344  list_->insertAfter(current_, v);
345  }
346 
352  inline void deleteNext() const
353  {
354  assert(list_);
355  list_->deleteNext(current_);
356  }
357 
358  private:
360  typename SLList<T,A>::Element* current_;
362  SLList<T,A>* list_;
363  };
364 
368  template<class T, class A>
369  class SLListConstIterator : public Dune::ForwardIteratorFacade<SLListConstIterator<T,A>, const T, const T&, std::size_t>
370  {
371  friend class SLListIterator<T,A>;
372  friend class SLList<T,A>;
373 
374  public:
376  : current_(0)
377  {}
378 
380  : current_(item)
381  {}
382 
384  : current_(other.current_)
385  {}
386 
388  : current_(other.current_)
389  {}
390 
392  : current_(other.iterator_.current_)
393  {}
394 
399  inline const T& dereference() const
400  {
401  return current_->item_;
402  }
403 
409  inline bool equals(const SLListConstIterator<T,A>& other) const
410  {
411  return current_==other.current_;
412  }
413 
417  inline void increment()
418  {
419  current_ = current_->next_;
420  }
421 
422  private:
424  typename SLList<T,A>::Element* current_;
425  };
426 
430  template<typename T, class A>
431  class SLListModifyIterator : public Dune::ForwardIteratorFacade<SLListModifyIterator<T,A>, T, T&, std::size_t>
432  {
433  friend class SLListConstIterator<T,A>;
434  friend class SLListIterator<T,A>;
435  public:
437  SLListIterator<T,A> _iterator)
438  : beforeIterator_(beforeIterator), iterator_(_iterator)
439  {}
440 
442  : beforeIterator_(other.beforeIterator_), iterator_(other.iterator_)
443  {}
444 
446  : beforeIterator_(), iterator_()
447  {}
448 
453  inline T& dereference() const
454  {
455  return *iterator_;
456  }
457 
463  inline bool equals(const SLListConstIterator<T,A>& other) const
464  {
465  return iterator_== other;
466  }
467 
468 
474  inline bool equals(const SLListIterator<T,A>& other) const
475  {
476  return iterator_== other;
477  }
478 
479 
485  inline bool equals(const SLListModifyIterator<T,A>& other) const
486  {
487  return iterator_== other.iterator_;
488  }
489 
493  inline void increment()
494  {
495  ++iterator_;
496  ++beforeIterator_;
497  }
498 
512  inline void insert(const T& v)
513  {
514  beforeIterator_.insertAfter(v);
515  ++beforeIterator_;
516  }
517 
525  inline void remove()
526  {
527  ++iterator_;
528  beforeIterator_.deleteNext();
529  }
530 
531  private:
533  SLListIterator<T,A> beforeIterator_;
535  SLListIterator<T,A> iterator_;
536  };
537 } // namespace Dune
538 
539 namespace std
540 {
541 
542  template<typename T, typename A>
543  ostream& operator<<(ostream& os, const Dune::SLList<T,A> sllist)
544  {
545  typedef typename Dune::SLList<T,A>::const_iterator Iterator;
546  Iterator end = sllist.end();
547  Iterator current= sllist.begin();
548 
549  os << "{ ";
550 
551  if(current!=end) {
552  os<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
553  ++current;
554 
555  for(; current != end; ++current)
556  os<<", "<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
557  }
558  os<<"} ";
559  return os;
560  }
561 } //namespace std
562 
563 namespace Dune
564 {
565 
566  template<typename T, class A>
567  SLList<T,A>::Element::Element(const MemberType& item, Element* next)
568  : next_(next), item_(item)
569  {}
570 
571  template<typename T, class A>
573  : next_(0), item_()
574  {}
575 
576  template<typename T, class A>
578  {
579  next_=0;
580  }
581 
582  template<typename T, class A>
584  : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
585  {
586  beforeHead_.next_=0;
587  assert(&beforeHead_==tail_);
588  assert(tail_->next_==0);
589  }
590 
591  template<typename T, class A>
593  : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
594  {
595  copyElements(other);
596  }
597 
598  template<typename T, class A>
599  template<typename T1, class A1>
601  : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
602  {
603  copyElements(other);
604  }
605 
606  template<typename T, typename A>
607  void SLList<T,A>::copyElements(const SLList<T,A>& other)
608  {
609  assert(tail_==&beforeHead_);
610  assert(size_==0);
611  typedef typename SLList<T,A>::const_iterator Iterator;
612  Iterator iend = other.end();
613  for(Iterator element=other.begin(); element != iend; ++element)
614  push_back(*element);
615 
616  assert(other.size()==size());
617  }
618 
619  template<typename T, class A>
621  {
622  clear();
623  }
624 
625  template<typename T, class A>
626  bool SLList<T,A>::operator==(const SLList& other) const
627  {
628  if(size()!=other.size())
629  return false;
630  for(const_iterator iter=begin(), oiter=other.begin();
631  iter != end(); ++iter, ++oiter)
632  if(*iter!=*oiter)
633  return false;
634  return true;
635  }
636 
637  template<typename T, class A>
638  bool SLList<T,A>::operator!=(const SLList& other) const
639  {
640  if(size()==other.size()) {
641  for(const_iterator iter=begin(), oiter=other.begin();
642  iter != end(); ++iter, ++oiter)
643  if(*iter!=*oiter)
644  return true;
645  return false;
646  }else
647  return true;
648  }
649  template<typename T, class A>
651  {
652  clear();
653  copyElements(other);
654  return *this;
655  }
656 
657  template<typename T, class A>
658  inline void SLList<T,A>::push_back(const MemberType& item)
659  {
660  assert(size_>0 || tail_==&beforeHead_);
661  tail_->next_ = allocator_.allocate(1, 0);
662  assert(size_>0 || tail_==&beforeHead_);
663  tail_ = tail_->next_;
664  ::new (static_cast<void*>(&(tail_->item_)))T(item);
665  tail_->next_=0;
666  assert(tail_->next_==0);
667  ++size_;
668  }
669 
670  template<typename T, class A>
671  inline void SLList<T,A>::insertAfter(Element* current, const T& item)
672  {
673  assert(current);
674 
675 #ifndef NDEBUG
676  bool changeTail = (current == tail_);
677 #endif
678 
679  // Save old next element
680  Element* tmp = current->next_;
681 
682  assert(!changeTail || !tmp);
683 
684  // Allocate space
685  current->next_ = allocator_.allocate(1, 0);
686 
687  // Use copy constructor to initialize memory
688  allocator_.construct(current->next_, Element(item,tmp));
689 
690  //::new(static_cast<void*>(&(current->next_->item_))) T(item);
691 
692  if(!current->next_->next_) {
693  // Update tail
694  assert(changeTail);
695  tail_ = current->next_;
696  }
697  ++size_;
698  assert(!tail_->next_);
699  }
700 
701  template<typename T, class A>
702  inline void SLList<T,A>::push_front(const MemberType& item)
703  {
704  if(tail_ == &beforeHead_) {
705  // list was empty
706  beforeHead_.next_ = tail_ = allocator_.allocate(1, 0);
707  ::new(static_cast<void*>(&beforeHead_.next_->item_))T(item);
708  beforeHead_.next_->next_=0;
709  }else{
710  Element* added = allocator_.allocate(1, 0);
711  ::new(static_cast<void*>(&added->item_))T(item);
712  added->next_=beforeHead_.next_;
713  beforeHead_.next_=added;
714  }
715  assert(tail_->next_==0);
716  ++size_;
717  }
718 
719 
720  template<typename T, class A>
721  inline void SLList<T,A>::deleteNext(Element* current)
722  {
723  this->template deleteNext<true>(current);
724  }
725 
726  template<typename T, class A>
727  template<bool watchForTail>
728  inline void SLList<T,A>::deleteNext(Element* current)
729  {
730  assert(current->next_);
731  Element* next = current->next_;
732 
733  if(watchForTail)
734  if(next == tail_) {
735  // deleting last element changes tail!
736  tail_ = current;
737  }
738 
739  current->next_ = next->next_;
740  allocator_.destroy(next);
741  allocator_.deallocate(next, 1);
742  --size_;
743  assert(!watchForTail || &beforeHead_ != tail_ || size_==0);
744  }
745 
746  template<typename T, class A>
748  {
749  deleteNext(&beforeHead_);
750  }
751 
752  template<typename T, class A>
753  inline void SLList<T,A>::clear()
754  {
755  while(beforeHead_.next_ ) {
756  this->template deleteNext<false>(&beforeHead_);
757  }
758 
759  assert(size_==0);
760  // update the tail!
761  tail_ = &beforeHead_;
762  }
763 
764  template<typename T, class A>
765  inline bool SLList<T,A>::empty() const
766  {
767  return (&beforeHead_ == tail_);
768  }
769 
770  template<typename T, class A>
771  inline int SLList<T,A>::size() const
772  {
773  return size_;
774  }
775 
776  template<typename T, class A>
778  {
779  return iterator(beforeHead_.next_, this);
780  }
781 
782  template<typename T, class A>
784  {
785  return const_iterator(beforeHead_.next_);
786  }
787 
788  template<typename T, class A>
790  {
791  return iterator();
792  }
793 
794  template<typename T, class A>
796  {
797  return SLListModifyIterator<T,A>(iterator(tail_, this),iterator());
798  }
799 
800 
801  template<typename T, class A>
803  {
804  return SLListModifyIterator<T,A>(iterator(&beforeHead_, this),
805  iterator(beforeHead_.next_, this));
806  }
807 
808  template<typename T, class A>
810  {
811  return const_iterator();
812  }
813 
815 }
816 #endif
bool equals(const SLListConstIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:409
SLListConstIterator(const SLListIterator< T, A > &other)
Definition: sllist.hh:383
void push_front(const MemberType &item)
Add a new entry to the beginning of the list.
Definition: sllist.hh:702
bool equals(const SLListConstIterator< T, A > &other) const
Test whether another iterator is equal.
Definition: sllist.hh:463
Dune namespace.
Definition: alignment.hh:13
SLListModifyIterator(const SLListModifyIterator< T, A > &other)
Definition: sllist.hh:441
iterator begin()
Get an iterator pointing to the first element in the list.
Definition: sllist.hh:777
SLList()
Constructor.
Definition: sllist.hh:583
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:136
bool equals(const SLListIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:313
ModifyIterator beginModify()
Get an iterator capable of deleting and inserting elements.
Definition: sllist.hh:802
bool equals(const SLListIterator< T, A > &other) const
Test whether another iterator is equal.
Definition: sllist.hh:474
T & dereference() const
Dereferencing function for the iterator facade.
Definition: sllist.hh:293
std::size_t size_
The size of the buffer.
Definition: variablesizecommunicator.hh:132
void insert(const T &v)
Insert an element at the current position.
Definition: sllist.hh:512
~SLList()
Destructor.
Definition: sllist.hh:620
ModifyIterator endModify()
Get an iterator capable of deleting and inserting elements.
Definition: sllist.hh:795
SLListModifyIterator()
Definition: sllist.hh:445
bool operator!=(const SLList &sl) const
Definition: sllist.hh:638
Get the N-th element of a tuple.
Definition: tuples.hh:457
A single linked list.
Definition: sllist.hh:42
void insertAfter(const T &v) const
Insert an element in the underlying list after the current position.
Definition: sllist.hh:341
bool equals(const SLListModifyIterator< T, A > &other) const
Test whether another iterator is equal.
Definition: sllist.hh:485
SLListIterator< T, A > iterator
The mutable iterator of the list.
Definition: sllist.hh:68
SLListIterator(typename SLList< T, A >::Element *item, SLList< T, A > *sllist)
Definition: sllist.hh:276
int size() const
Get the number of elements the list contains.
Definition: sllist.hh:771
void increment()
Increment function for the iterator facade.
Definition: sllist.hh:331
void pop_front()
Remove the first item in the list.
Definition: sllist.hh:747
STL namespace.
SLListModifyIterator< T, A > ModifyIterator
The type of the iterator capable of deletion and insertion.
Definition: sllist.hh:102
bool equals(const SLListConstIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:303
SLListModifyIterator(SLListIterator< T, A > beforeIterator, SLListIterator< T, A > _iterator)
Definition: sllist.hh:436
T & dereference() const
Dereferencing function for the iterator facade.
Definition: sllist.hh:453
SLListIterator(const SLListModifyIterator< T, A > &other)
Definition: sllist.hh:285
SLList< T, A > & operator=(const SLList< T, A > &other)
Assignment operator.
Definition: sllist.hh:650
bool equals(const SLListModifyIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:323
MemberType item_
The element we hold.
Definition: sllist.hh:211
bool operator==(const SLList &sl) const
Definition: sllist.hh:626
void increment()
Increment function for the iterator facade.
Definition: sllist.hh:417
const T & dereference() const
Dereferencing function for the facade.
Definition: sllist.hh:399
SLListConstIterator< T, A > const_iterator
The constant iterator of the list.
Definition: sllist.hh:73
A mutable iterator for the SLList.
Definition: sllist.hh:26
SLListConstIterator(typename SLList< T, A >::Element *item)
Definition: sllist.hh:379
bool empty() const
Check whether the list is empty.
Definition: sllist.hh:765
void increment()
Increment function for the iterator facade.
Definition: sllist.hh:493
SLListIterator()
Definition: sllist.hh:281
void push_back(const MemberType &item)
Add a new entry to the end of the list.
Definition: sllist.hh:658
SLListConstIterator()
Definition: sllist.hh:375
iterator end()
Get an iterator pointing to the end of the list.
Definition: sllist.hh:789
Element * next_
The next element in the list.
Definition: sllist.hh:207
This file implements iterator facade classes for writing stl conformant iterators.
SLListConstIterator(const SLListConstIterator< T, A > &other)
Definition: sllist.hh:387
void deleteNext() const
Delete the entry after the current position.
Definition: sllist.hh:352
T MemberType
The type we store.
Definition: sllist.hh:58
SLListConstIterator(const SLListModifyIterator< T, A > &other)
Definition: sllist.hh:391
A mutable iterator for the SLList.
Definition: sllist.hh:32
A::size_type size_type
The size type.
Definition: sllist.hh:53
void clear()
Remove all elements from the list.
Definition: sllist.hh:753
A::template rebind< Element >::other Allocator
The allocator to use.
Definition: sllist.hh:63
A constant iterator for the SLList.
Definition: sllist.hh:29