Dune Core Modules (2.8.0)

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#ifndef DUNE_SLLIST_HH
4#define DUNE_SLLIST_HH
5
6#include <memory>
7#include <cassert>
8#include "iteratorfacades.hh"
9#include <ostream>
10
11namespace Dune
12{
24 template<typename T, class A>
25 class SLListIterator;
26
27 template<typename T, class A>
28 class SLListConstIterator;
29
30 template<typename T, class A>
31 class SLListModifyIterator;
32
40 template<typename T, class A=std::allocator<T> >
41 class SLList
42 {
43 struct Element;
44 friend class SLListIterator<T,A>;
45 friend class SLListConstIterator<T,A>;
46
47 public:
48
52 typedef typename A::size_type size_type;
53
57 typedef T MemberType;
58
62 using Allocator = typename std::allocator_traits<A>::template rebind_alloc<Element>;
63
68
73
78
82 template<typename T1, typename A1>
83 SLList(const SLList<T1,A1>& other);
84
88 SLList(const SLList<T,A>& other);
89
96
102
107
108
113 inline void push_back(const MemberType& item);
114
119 inline void push_front(const MemberType& item);
120
124 inline void pop_front();
125
127 inline void clear();
128
136 inline iterator begin();
137
145 inline const_iterator begin() const;
146
155
164
171 inline iterator end();
172
179 inline const_iterator end() const;
180
186 inline bool empty() const;
187
192 inline int size() const;
193
194 bool operator==(const SLList& sl) const;
195
196
197 bool operator!=(const SLList& sl) const;
198
199 private:
201 struct Element
202 {
206 Element* next_;
211
212 Element(const MemberType& item, Element* next_=0);
213
214 Element();
215
216 ~Element();
217 };
218
223 void deleteNext(Element* current);
224
229 void copyElements(const SLList<T,A>& other);
230
238 template<bool watchForTail>
239 void deleteNext(Element* current);
245 void insertAfter(Element* current, const T& item);
246
248 Element beforeHead_;
249
255 Element* tail_;
256
258 Allocator allocator_;
259
261 int size_;
262 };
263
267 template<typename T, class A>
268 class SLListIterator : public Dune::ForwardIteratorFacade<SLListIterator<T,A>, T, T&, std::size_t>
269 {
270 friend class SLListConstIterator<T,A>;
271 friend class SLListModifyIterator<T,A>;
272 friend class SLList<T,A>;
273
274 public:
275 inline SLListIterator(typename SLList<T,A>::Element* item,
276 SLList<T,A>* sllist)
277 : current_(item), list_(sllist)
278 {}
279
280 inline SLListIterator()
281 : current_(0), list_(0)
282 {}
283
284 inline SLListIterator(const SLListModifyIterator<T,A>& other)
285 : current_(other.iterator_.current_), list_(other.iterator_.list_)
286 {}
287
292 inline T& dereference() const
293 {
294 return current_->item_;
295 }
296
302 inline bool equals(const SLListConstIterator<T,A>& other) const
303 {
304 return current_==other.current_;
305 }
306
312 inline bool equals(const SLListIterator<T,A>& other) const
313 {
314 return current_==other.current_;
315 }
316
322 inline bool equals(const SLListModifyIterator<T,A>& other) const
323 {
324 return current_==other.iterator_.current_;
325 }
326
330 inline void increment()
331 {
332 current_ = current_->next_;
333 }
334
340 inline void insertAfter(const T& v) const
341 {
342 assert(list_ );
343 list_->insertAfter(current_, v);
344 }
345
351 inline void deleteNext() const
352 {
353 assert(list_);
354 list_->deleteNext(current_);
355 }
356
357 private:
359 typename SLList<T,A>::Element* current_;
361 SLList<T,A>* list_;
362 };
363
367 template<class T, class A>
368 class SLListConstIterator : public Dune::ForwardIteratorFacade<SLListConstIterator<T,A>, const T, const T&, std::size_t>
369 {
370 friend class SLListIterator<T,A>;
371 friend class SLList<T,A>;
372
373 public:
374 inline SLListConstIterator()
375 : current_(0)
376 {}
377
378 inline SLListConstIterator(typename SLList<T,A>::Element* item)
379 : current_(item)
380 {}
381
382 inline SLListConstIterator(const SLListIterator<T,A>& other)
383 : current_(other.current_)
384 {}
385
387 : current_(other.current_)
388 {}
389
391 : current_(other.iterator_.current_)
392 {}
393
398 inline const T& dereference() const
399 {
400 return current_->item_;
401 }
402
408 inline bool equals(const SLListConstIterator<T,A>& other) const
409 {
410 return current_==other.current_;
411 }
412
416 inline void increment()
417 {
418 current_ = current_->next_;
419 }
420
421 private:
423 typename SLList<T,A>::Element* current_;
424 };
425
429 template<typename T, class A>
430 class SLListModifyIterator : public Dune::ForwardIteratorFacade<SLListModifyIterator<T,A>, T, T&, std::size_t>
431 {
432 friend class SLListConstIterator<T,A>;
433 friend class SLListIterator<T,A>;
434 public:
435 inline SLListModifyIterator(SLListIterator<T,A> beforeIterator,
436 SLListIterator<T,A> _iterator)
437 : beforeIterator_(beforeIterator), iterator_(_iterator)
438 {}
439
441 : beforeIterator_(other.beforeIterator_), iterator_(other.iterator_)
442 {}
443
444 inline SLListModifyIterator()
445 : beforeIterator_(), iterator_()
446 {}
447
452 inline T& dereference() const
453 {
454 return *iterator_;
455 }
456
462 inline bool equals(const SLListConstIterator<T,A>& other) const
463 {
464 return iterator_== other;
465 }
466
467
473 inline bool equals(const SLListIterator<T,A>& other) const
474 {
475 return iterator_== other;
476 }
477
478
484 inline bool equals(const SLListModifyIterator<T,A>& other) const
485 {
486 return iterator_== other.iterator_;
487 }
488
492 inline void increment()
493 {
494 ++iterator_;
495 ++beforeIterator_;
496 }
497
511 inline void insert(const T& v)
512 {
513 beforeIterator_.insertAfter(v);
514 ++beforeIterator_;
515 }
516
524 inline void remove()
525 {
526 ++iterator_;
527 beforeIterator_.deleteNext();
528 }
529
530 private:
532 SLListIterator<T,A> beforeIterator_;
534 SLListIterator<T,A> iterator_;
535 };
536
537 template<typename T, typename A>
538 std::ostream& operator<<(std::ostream& os, const SLList<T,A>& sllist)
539 {
540 typedef typename SLList<T,A>::const_iterator Iterator;
541 Iterator end = sllist.end();
542 Iterator current= sllist.begin();
543
544 os << "{ ";
545
546 if(current!=end) {
547 os<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
548 ++current;
549
550 for(; current != end; ++current)
551 os<<", "<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
552 }
553 os<<"} ";
554 return os;
555 }
556
557 template<typename T, class A>
558 SLList<T,A>::Element::Element(const MemberType& item, Element* next)
559 : next_(next), item_(item)
560 {}
561
562 template<typename T, class A>
563 SLList<T,A>::Element::Element()
564 : next_(0), item_()
565 {}
566
567 template<typename T, class A>
568 SLList<T,A>::Element::~Element()
569 {
570 next_=0;
571 }
572
573 template<typename T, class A>
575 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
576 {
577 beforeHead_.next_=0;
578 assert(&beforeHead_==tail_);
579 assert(tail_->next_==0);
580 }
581
582 template<typename T, class A>
584 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
585 {
586 copyElements(other);
587 }
588
589 template<typename T, class A>
590 template<typename T1, class A1>
592 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
593 {
594 copyElements(other);
595 }
596
597 template<typename T, typename A>
598 void SLList<T,A>::copyElements(const SLList<T,A>& other)
599 {
600 assert(tail_==&beforeHead_);
601 assert(size_==0);
602 typedef typename SLList<T,A>::const_iterator Iterator;
603 Iterator iend = other.end();
604 for(Iterator element=other.begin(); element != iend; ++element)
605 push_back(*element);
606
607 assert(other.size()==size());
608 }
609
610 template<typename T, class A>
612 {
613 clear();
614 }
615
616 template<typename T, class A>
617 bool SLList<T,A>::operator==(const SLList& other) const
618 {
619 if(size()!=other.size())
620 return false;
621 for(const_iterator iter=begin(), oiter=other.begin();
622 iter != end(); ++iter, ++oiter)
623 if(*iter!=*oiter)
624 return false;
625 return true;
626 }
627
628 template<typename T, class A>
629 bool SLList<T,A>::operator!=(const SLList& other) const
630 {
631 if(size()==other.size()) {
632 for(const_iterator iter=begin(), oiter=other.begin();
633 iter != end(); ++iter, ++oiter)
634 if(*iter!=*oiter)
635 return true;
636 return false;
637 }else
638 return true;
639 }
640 template<typename T, class A>
642 {
643 clear();
644 copyElements(other);
645 return *this;
646 }
647
648 template<typename T, class A>
649 inline void SLList<T,A>::push_back(const MemberType& item)
650 {
651 assert(size_>0 || tail_==&beforeHead_);
652 tail_->next_ = allocator_.allocate(1);
653 assert(size_>0 || tail_==&beforeHead_);
654 tail_ = tail_->next_;
655 ::new (static_cast<void*>(&(tail_->item_)))T(item);
656 tail_->next_=0;
657 assert(tail_->next_==0);
658 ++size_;
659 }
660
661 template<typename T, class A>
662 inline void SLList<T,A>::insertAfter(Element* current, const T& item)
663 {
664 assert(current);
665
666#ifndef NDEBUG
667 bool changeTail = (current == tail_);
668#endif
669
670 // Save old next element
671 Element* tmp = current->next_;
672
673 assert(!changeTail || !tmp);
674
675 // Allocate space
676 current->next_ = allocator_.allocate(1);
677
678 // Use copy constructor to initialize memory
679 std::allocator_traits<Allocator>::construct(allocator_, current->next_, Element(item,tmp));
680
681 //::new(static_cast<void*>(&(current->next_->item_))) T(item);
682
683 if(!current->next_->next_) {
684 // Update tail
685 assert(changeTail);
686 tail_ = current->next_;
687 }
688 ++size_;
689 assert(!tail_->next_);
690 }
691
692 template<typename T, class A>
693 inline void SLList<T,A>::push_front(const MemberType& item)
694 {
695 if(tail_ == &beforeHead_) {
696 // list was empty
697 beforeHead_.next_ = tail_ = allocator_.allocate(1, 0);
698 ::new(static_cast<void*>(&beforeHead_.next_->item_))T(item);
699 beforeHead_.next_->next_=0;
700 }else{
701 Element* added = allocator_.allocate(1, 0);
702 ::new(static_cast<void*>(&added->item_))T(item);
703 added->next_=beforeHead_.next_;
704 beforeHead_.next_=added;
705 }
706 assert(tail_->next_==0);
707 ++size_;
708 }
709
710
711 template<typename T, class A>
712 inline void SLList<T,A>::deleteNext(Element* current)
713 {
714 this->template deleteNext<true>(current);
715 }
716
717 template<typename T, class A>
718 template<bool watchForTail>
719 inline void SLList<T,A>::deleteNext(Element* current)
720 {
721 assert(current->next_);
722 Element* next = current->next_;
723
724 if(watchForTail)
725 if(next == tail_) {
726 // deleting last element changes tail!
727 tail_ = current;
728 }
729
730 current->next_ = next->next_;
731 std::allocator_traits<Allocator>::destroy(allocator_, next);
732 allocator_.deallocate(next, 1);
733 --size_;
734 assert(!watchForTail || &beforeHead_ != tail_ || size_==0);
735 }
736
737 template<typename T, class A>
739 {
740 deleteNext(&beforeHead_);
741 }
742
743 template<typename T, class A>
744 inline void SLList<T,A>::clear()
745 {
746 while(beforeHead_.next_ ) {
747 this->template deleteNext<false>(&beforeHead_);
748 }
749
750 assert(size_==0);
751 // update the tail!
752 tail_ = &beforeHead_;
753 }
754
755 template<typename T, class A>
756 inline bool SLList<T,A>::empty() const
757 {
758 return (&beforeHead_ == tail_);
759 }
760
761 template<typename T, class A>
762 inline int SLList<T,A>::size() const
763 {
764 return size_;
765 }
766
767 template<typename T, class A>
769 {
770 return iterator(beforeHead_.next_, this);
771 }
772
773 template<typename T, class A>
775 {
776 return const_iterator(beforeHead_.next_);
777 }
778
779 template<typename T, class A>
781 {
782 return iterator();
783 }
784
785 template<typename T, class A>
787 {
788 return SLListModifyIterator<T,A>(iterator(tail_, this),iterator());
789 }
790
791
792 template<typename T, class A>
794 {
795 return SLListModifyIterator<T,A>(iterator(&beforeHead_, this),
796 iterator(beforeHead_.next_, this));
797 }
798
799 template<typename T, class A>
801 {
802 return const_iterator();
803 }
804
806}
807#endif
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:139
A constant iterator for the SLList.
Definition: sllist.hh:369
A mutable iterator for the SLList.
Definition: sllist.hh:269
A mutable iterator for the SLList.
Definition: sllist.hh:431
A single linked list.
Definition: sllist.hh:42
void push_front(const MemberType &item)
Add a new entry to the beginning of the list.
Definition: sllist.hh:693
bool equals(const SLListConstIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:408
void push_back(const MemberType &item)
Add a new entry to the end of the list.
Definition: sllist.hh:649
ModifyIterator endModify()
Get an iterator capable of deleting and inserting elements.
Definition: sllist.hh:786
T & dereference() const
Dereferencing function for the iterator facade.
Definition: sllist.hh:292
MemberType item_
The element we hold.
Definition: sllist.hh:210
typename std::allocator_traits< A >::template rebind_alloc< Element > Allocator
The allocator to use.
Definition: sllist.hh:62
void insertAfter(const T &v) const
Insert an element in the underlying list after the current position.
Definition: sllist.hh:340
SLListIterator< T, A > iterator
The mutable iterator of the list.
Definition: sllist.hh:67
void deleteNext() const
Delete the entry after the current position.
Definition: sllist.hh:351
SLList(const SLList< T, A > &other)
Copy constructor.
Definition: sllist.hh:583
bool equals(const SLListModifyIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:322
T & dereference() const
Dereferencing function for the iterator facade.
Definition: sllist.hh:452
int size() const
Get the number of elements the list contains.
Definition: sllist.hh:762
const_iterator begin() const
Get an iterator pointing to the first element in the list.
Definition: sllist.hh:774
iterator end()
Get an iterator pointing to the end of the list.
Definition: sllist.hh:780
void clear()
Remove all elements from the list.
Definition: sllist.hh:744
SLList(const SLList< T1, A1 > &other)
Copy constructor with type conversion.
Definition: sllist.hh:591
T MemberType
The type we store.
Definition: sllist.hh:57
bool equals(const SLListModifyIterator< T, A > &other) const
Test whether another iterator is equal.
Definition: sllist.hh:484
ModifyIterator beginModify()
Get an iterator capable of deleting and inserting elements.
Definition: sllist.hh:793
SLList< T, A > & operator=(const SLList< T, A > &other)
Assignment operator.
Definition: sllist.hh:641
SLListConstIterator< T, A > const_iterator
The constant iterator of the list.
Definition: sllist.hh:72
bool empty() const
Check whether the list is empty.
Definition: sllist.hh:756
bool equals(const SLListConstIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:302
bool equals(const SLListConstIterator< T, A > &other) const
Test whether another iterator is equal.
Definition: sllist.hh:462
SLListModifyIterator< T, A > ModifyIterator
The type of the iterator capable of deletion and insertion.
Definition: sllist.hh:101
const_iterator end() const
Get an iterator pointing to the end of the list.
Definition: sllist.hh:800
SLList()
Constructor.
Definition: sllist.hh:574
void insert(const T &v)
Insert an element at the current position.
Definition: sllist.hh:511
void pop_front()
Remove the first item in the list.
Definition: sllist.hh:738
void increment()
Increment function for the iterator facade.
Definition: sllist.hh:330
A::size_type size_type
The size type.
Definition: sllist.hh:52
void remove()
Delete the entry at the current position.
Definition: sllist.hh:524
const T & dereference() const
Dereferencing function for the facade.
Definition: sllist.hh:398
Element * next_
The next element in the list.
Definition: sllist.hh:206
void increment()
Increment function for the iterator facade.
Definition: sllist.hh:492
void increment()
Increment function for the iterator facade.
Definition: sllist.hh:416
~SLList()
Destructor.
Definition: sllist.hh:611
bool equals(const SLListIterator< T, A > &other) const
Test whether another iterator is equal.
Definition: sllist.hh:473
iterator begin()
Get an iterator pointing to the first element in the list.
Definition: sllist.hh:768
bool equals(const SLListIterator< T, A > &other) const
Equality test for the iterator facade.
Definition: sllist.hh:312
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:235
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:257
constexpr HybridTreePath< T..., std::size_t > push_back(const HybridTreePath< T... > &tp, std::size_t i)
Appends a run time index to a HybridTreePath.
Definition: treepath.hh:278
constexpr HybridTreePath< std::size_t, T... > push_front(const HybridTreePath< T... > &tp, std::size_t element)
Prepends a run time index to a HybridTreePath.
Definition: treepath.hh:309
This file implements iterator facade classes for writing stl conformant iterators.
Dune namespace.
Definition: alignedallocator.hh:11
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 12, 23:30, 2024)