dune-common  2.2.1
sllist.hh
Go to the documentation of this file.
1 // $Id: sllist.hh 7077 2013-01-19 10:06:29Z mblatt $
2 #ifndef DUNE_SLLIST_HH
3 #define DUNE_SLLIST_HH
4 
5 #include<memory>
6 #include <cassert>
7 #include"iteratorfacades.hh"
8 #include<ostream>
9 
10 namespace Dune
11 {
23  template<typename T, class A>
24  class SLListIterator;
25 
26  template<typename T, class A>
27  class SLListConstIterator;
28 
29  template<typename T, class A>
30  class SLListModifyIterator;
31 
39  template<typename T, class A=std::allocator<T> >
40  class SLList
41  {
42  struct Element;
43  friend class SLListIterator<T,A>;
44  friend class SLListConstIterator<T,A>;
45 
46  public:
47 
51  typedef typename A::size_type size_type;
52 
56  typedef T MemberType;
57 
61  typedef typename A::template rebind<Element>::other Allocator;
62 
67 
72 
76  SLList();
77 
81  template<typename T1, typename A1>
82  SLList(const SLList<T1,A1>& other);
83 
87  SLList(const SLList<T,A>& other);
88 
94  ~SLList();
95 
101 
105  SLList<T,A>& operator=(const SLList<T,A>& other);
106 
107 
112  inline void push_back(const MemberType& item);
113 
118  inline void push_front(const MemberType& item);
119 
123  inline void pop_front();
124 
126  inline void clear();
127 
135  inline iterator begin();
136 
144  inline const_iterator begin() const;
145 
153  inline ModifyIterator beginModify();
154 
162  inline ModifyIterator endModify();
163 
170  inline iterator end();
171 
178  inline const_iterator end() const;
179 
185  inline bool empty() const;
186 
191  inline int size() const;
192 
193  bool operator==(const SLList& sl) const;
194 
195 
196  bool operator!=(const SLList& sl) const;
197 
198  private:
200  struct Element
201  {
205  Element* next_;
210 
211  Element(const MemberType& item, Element* next_=0);
212 
213  Element();
214 
215  ~Element();
216  };
217 
222  void deleteNext(Element* current);
223 
228  void copyElements(const SLList<T,A>& other);
229 
237  template<bool watchForTail>
238  void deleteNext(Element* current);
244  void insertAfter(Element* current, const T& item);
245 
247  Element beforeHead_;
248 
254  Element* tail_;
255 
257  Allocator allocator_;
258 
260  int size_;
261  };
262 
266  template<typename T, class A>
267  class SLListIterator : public Dune::ForwardIteratorFacade<SLListIterator<T,A>, T, T&, std::size_t>
268  {
269  friend class SLListConstIterator<T,A>;
270  friend class SLListModifyIterator<T,A>;
271  friend class SLList<T,A>;
272 
273  public:
274  inline SLListIterator(typename SLList<T,A>::Element* item,
275  SLList<T,A>* sllist)
276  : current_(item), list_(sllist)
277  {}
278 
279  inline SLListIterator()
280  : current_(0), list_(0)
281  {}
282 
284  : current_(other.iterator_.current_), list_(other.iterator_.list_)
285  {}
286 
291  inline T& dereference() const
292  {
293  return current_->item_;
294  }
295 
301  inline bool equals(const SLListConstIterator<T,A>& other) const
302  {
303  return current_==other.current_;
304  }
305 
311  inline bool equals(const SLListIterator<T,A>& other) const
312  {
313  return current_==other.current_;
314  }
315 
321  inline bool equals(const SLListModifyIterator<T,A>& other) const
322  {
323  return current_==other.iterator_.current_;
324  }
325 
329  inline void increment()
330  {
331  current_ = current_->next_;
332  }
333 
339  inline void insertAfter(const T& v)const
340  {
341  assert(list_ );
342  list_->insertAfter(current_, v);
343  }
344 
350  inline void deleteNext() const
351  {
352  assert(list_);
353  list_->deleteNext(current_);
354  }
355 
356  private:
358  typename SLList<T,A>::Element* current_;
360  SLList<T,A>* list_;
361  };
362 
366  template<class T, class A>
367  class SLListConstIterator : public Dune::ForwardIteratorFacade<SLListConstIterator<T,A>, const T, const T&, std::size_t>
368  {
369  friend class SLListIterator<T,A>;
370  friend class SLList<T,A>;
371 
372  public:
374  : current_(0)
375  {}
376 
378  : current_(item)
379  {}
380 
382  : current_(other.current_)
383  {}
384 
386  : current_(other.current_)
387  {}
388 
390  : current_(other.iterator_.current_)
391  {}
392 
397  inline const T& dereference() const
398  {
399  return current_->item_;
400  }
401 
407  inline bool equals(const SLListConstIterator<T,A>& other) const
408  {
409  return current_==other.current_;
410  }
411 
415  inline void increment()
416  {
417  current_ = current_->next_;
418  }
419 
420  private:
422  typename SLList<T,A>::Element* current_;
423  };
424 
428  template<typename T, class A>
429  class SLListModifyIterator : public Dune::ForwardIteratorFacade<SLListModifyIterator<T,A>, T, T&, std::size_t>
430  {
431  friend class SLListConstIterator<T,A>;
432  friend class SLListIterator<T,A>;
433  public:
435  SLListIterator<T,A> _iterator)
436  : beforeIterator_(beforeIterator), iterator_(_iterator)
437  {}
438 
440  : beforeIterator_(other.beforeIterator_), iterator_(other.iterator_)
441  {}
442 
444  : beforeIterator_(), iterator_()
445  {}
446 
451  inline T& dereference() const
452  {
453  return *iterator_;
454  }
455 
461  inline bool equals(const SLListConstIterator<T,A>& other) const
462  {
463  return iterator_== other;
464  }
465 
466 
472  inline bool equals(const SLListIterator<T,A>& other) const
473  {
474  return iterator_== other;
475  }
476 
477 
483  inline bool equals(const SLListModifyIterator<T,A>& other) const
484  {
485  return iterator_== other.iterator_;
486  }
487 
491  inline void increment()
492  {
493  ++iterator_;
494  ++beforeIterator_;
495  }
496 
510  inline void insert(const T& v)
511  {
512  beforeIterator_.insertAfter(v);
513  ++beforeIterator_;
514  }
515 
523  inline void remove()
524  {
525  ++iterator_;
526  beforeIterator_.deleteNext();
527  }
528 
529  private:
531  SLListIterator<T,A> beforeIterator_;
533  SLListIterator<T,A> iterator_;
534  };
535 }// namespace Dune
536 
537 namespace std
538 {
539 
540  template<typename T, typename A>
541  ostream& operator<<(ostream& os, const Dune::SLList<T,A> sllist)
542  {
543  typedef typename Dune::SLList<T,A>::const_iterator Iterator;
544  Iterator end = sllist.end();
545  Iterator current= sllist.begin();
546 
547  os << "{ ";
548 
549  if(current!=end){
550  os<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
551  ++current;
552 
553  for(; current != end; ++current)
554  os<<", "<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
555  }
556  os<<"} ";
557  return os;
558  }
559 }//namespace std
560 
561 namespace Dune
562 {
563 
564  template<typename T, class A>
565  SLList<T,A>::Element::Element(const MemberType& item, Element* next)
566  : next_(next), item_(item)
567  {}
568 
569  template<typename T, class A>
571  : next_(0), item_()
572  {}
573 
574  template<typename T, class A>
576  {
577  next_=0;
578  }
579 
580  template<typename T, class A>
582  : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
583  {
584  beforeHead_.next_=0;
585  assert(&beforeHead_==tail_);
586  assert(tail_->next_==0);
587  }
588 
589  template<typename T, class A>
591  : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
592  {
593  copyElements(other);
594  }
595 
596  template<typename T, class A>
597  template<typename T1, class A1>
599  : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
600  {
601  copyElements(other);
602  }
603 
604  template<typename T, typename A>
605  void SLList<T,A>::copyElements(const SLList<T,A>& other)
606  {
607  assert(tail_==&beforeHead_);
608  assert(size_==0);
609  typedef typename SLList<T,A>::const_iterator Iterator;
610  Iterator iend = other.end();
611  for(Iterator element=other.begin(); element != iend; ++element)
612  push_back(*element);
613 
614  assert(other.size()==size());
615  }
616 
617  template<typename T, class A>
619  {
620  clear();
621  }
622 
623  template<typename T, class A>
624  bool SLList<T,A>::operator==(const SLList& other) const
625  {
626  if(size()!=other.size())
627  return false;
628  for(const_iterator iter=begin(), oiter=other.begin();
629  iter != end(); ++iter, ++oiter)
630  if(*iter!=*oiter)
631  return false;
632  return true;
633  }
634 
635  template<typename T, class A>
636  bool SLList<T,A>::operator!=(const SLList& other) const
637  {
638  if(size()==other.size()){
639  for(const_iterator iter=begin(), oiter=other.begin();
640  iter != end(); ++iter, ++oiter)
641  if(*iter!=*oiter)
642  return true;
643  return false;
644  }else
645  return true;
646  }
647  template<typename T, class A>
649  {
650  clear();
651  copyElements(other);
652  return *this;
653  }
654 
655  template<typename T, class A>
656  inline void SLList<T,A>::push_back(const MemberType& item)
657  {
658  assert(size_>0 || tail_==&beforeHead_);
659  tail_->next_ = allocator_.allocate(1, 0);
660  assert(size_>0 || tail_==&beforeHead_);
661  tail_ = tail_->next_;
662  ::new (static_cast<void*>(&(tail_->item_))) T(item);
663  tail_->next_=0;
664  assert(tail_->next_==0);
665  ++size_;
666  }
667 
668  template<typename T, class A>
669  inline void SLList<T,A>::insertAfter(Element* current, const T& item)
670  {
671  assert(current);
672 
673 #ifndef NDEBUG
674  bool changeTail = (current == tail_);
675 #endif
676 
677  // Save old next element
678  Element* tmp = current->next_;
679 
680  assert(!changeTail || !tmp);
681 
682  // Allocate space
683  current->next_ = allocator_.allocate(1, 0);
684 
685  // Use copy constructor to initialize memory
686  allocator_.construct(current->next_, Element(item,tmp));
687 
688  //::new(static_cast<void*>(&(current->next_->item_))) T(item);
689 
690  if(!current->next_->next_){
691  // Update tail
692  assert(changeTail);
693  tail_ = current->next_;
694  }
695  ++size_;
696  assert(!tail_->next_);
697  }
698 
699  template<typename T, class A>
700  inline void SLList<T,A>::push_front(const MemberType& item)
701  {
702  if(tail_ == &beforeHead_){
703  // list was empty
704  beforeHead_.next_ = tail_ = allocator_.allocate(1, 0);
705  ::new(static_cast<void*>(&beforeHead_.next_->item_)) T(item);
706  beforeHead_.next_->next_=0;
707  }else{
708  Element* added = allocator_.allocate(1, 0);
709  ::new(static_cast<void*>(&added->item_)) T(item);
710  added->next_=beforeHead_.next_;
711  beforeHead_.next_=added;
712  }
713  assert(tail_->next_==0);
714  ++size_;
715  }
716 
717 
718  template<typename T, class A>
719  inline void SLList<T,A>::deleteNext(Element* current)
720  {
721  this->template deleteNext<true>(current);
722  }
723 
724  template<typename T, class A>
725  template<bool watchForTail>
726  inline void SLList<T,A>::deleteNext(Element* current)
727  {
728  assert(current->next_);
729  Element* next = current->next_;
730 
731  if(watchForTail)
732  if(next == tail_){
733  // deleting last element changes tail!
734  tail_ = current;
735  }
736 
737  current->next_ = next->next_;
738  allocator_.destroy(next);
739  allocator_.deallocate(next, 1);
740  --size_;
741  assert(!watchForTail || &beforeHead_ != tail_ || size_==0);
742  }
743 
744  template<typename T, class A>
746  {
747  deleteNext(&beforeHead_);
748  }
749 
750  template<typename T, class A>
751  inline void SLList<T,A>::clear()
752  {
753  while(beforeHead_.next_ ){
754  this->template deleteNext<false>(&beforeHead_);
755  }
756 
757  assert(size_==0);
758  // update the tail!
759  tail_ = &beforeHead_;
760  }
761 
762  template<typename T, class A>
763  inline bool SLList<T,A>::empty() const
764  {
765  return (&beforeHead_ == tail_);
766  }
767 
768  template<typename T, class A>
769  inline int SLList<T,A>::size() const
770  {
771  return size_;
772  }
773 
774  template<typename T, class A>
776  {
777  return iterator(beforeHead_.next_, this);
778  }
779 
780  template<typename T, class A>
782  {
783  return const_iterator(beforeHead_.next_);
784  }
785 
786  template<typename T, class A>
788  {
789  return iterator();
790  }
791 
792  template<typename T, class A>
794  {
795  return SLListModifyIterator<T,A>(iterator(tail_, this),iterator());
796  }
797 
798 
799  template<typename T, class A>
801  {
802  return SLListModifyIterator<T,A>(iterator(&beforeHead_, this),
803  iterator(beforeHead_.next_, this));
804  }
805 
806  template<typename T, class A>
808  {
809  return const_iterator();
810  }
811 
813 }
814 #endif