Dune Core Modules (unstable)

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// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
4// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
5#ifndef DUNE_SLLIST_HH
6#define DUNE_SLLIST_HH
7
8#include <memory>
9#include <cassert>
10#include "iteratorfacades.hh"
11#include <ostream>
12
13namespace Dune
14{
26 template<typename T, class A>
27 class SLListIterator;
28
29 template<typename T, class A>
30 class SLListConstIterator;
31
32 template<typename T, class A>
33 class SLListModifyIterator;
34
42 template<typename T, class A=std::allocator<T> >
43 class SLList
44 {
45 struct Element;
46 friend class SLListIterator<T,A>;
47 friend class SLListConstIterator<T,A>;
48
49 public:
50
54 typedef typename A::size_type size_type;
55
59 typedef T MemberType;
60
64 using Allocator = typename std::allocator_traits<A>::template rebind_alloc<Element>;
65
70
75
80
84 template<typename T1, typename A1>
85 SLList(const SLList<T1,A1>& other);
86
90 SLList(const SLList<T,A>& other);
91
98
104
109
110
115 inline void push_back(const MemberType& item);
116
121 inline void push_front(const MemberType& item);
122
126 inline void pop_front();
127
129 inline void clear();
130
138 inline iterator begin();
139
147 inline const_iterator begin() const;
148
157
166
173 inline iterator end();
174
181 inline const_iterator end() const;
182
188 inline bool empty() const;
189
194 inline int size() const;
195
196 bool operator==(const SLList& sl) const;
197
198
199 bool operator!=(const SLList& sl) const;
200
201 private:
203 struct Element
204 {
208 Element* next_;
213
214 Element(const MemberType& item, Element* next_=0);
215
216 Element();
217
218 ~Element();
219 };
220
225 void deleteNext(Element* current);
226
231 void copyElements(const SLList<T,A>& other);
232
240 template<bool watchForTail>
241 void deleteNext(Element* current);
247 void insertAfter(Element* current, const T& item);
248
250 Element beforeHead_;
251
257 Element* tail_;
258
260 Allocator allocator_;
261
263 int size_;
264 };
265
269 template<typename T, class A>
270 class SLListIterator : public Dune::ForwardIteratorFacade<SLListIterator<T,A>, T, T&, std::size_t>
271 {
272 friend class SLListConstIterator<T,A>;
273 friend class SLListModifyIterator<T,A>;
274 friend class SLList<T,A>;
275
276 public:
277 inline SLListIterator(typename SLList<T,A>::Element* item,
278 SLList<T,A>* sllist)
279 : current_(item), list_(sllist)
280 {}
281
282 inline SLListIterator()
283 : current_(0), list_(0)
284 {}
285
286 inline SLListIterator(const SLListModifyIterator<T,A>& other)
287 : current_(other.iterator_.current_), list_(other.iterator_.list_)
288 {}
289
294 inline T& dereference() const
295 {
296 return current_->item_;
297 }
298
304 inline bool equals(const SLListConstIterator<T,A>& other) const
305 {
306 return current_==other.current_;
307 }
308
314 inline bool equals(const SLListIterator<T,A>& other) const
315 {
316 return current_==other.current_;
317 }
318
324 inline bool equals(const SLListModifyIterator<T,A>& other) const
325 {
326 return current_==other.iterator_.current_;
327 }
328
332 inline void increment()
333 {
334 current_ = current_->next_;
335 }
336
342 inline void insertAfter(const T& v) const
343 {
344 assert(list_ );
345 list_->insertAfter(current_, v);
346 }
347
353 inline void deleteNext() const
354 {
355 assert(list_);
356 list_->deleteNext(current_);
357 }
358
359 private:
361 typename SLList<T,A>::Element* current_;
363 SLList<T,A>* list_;
364 };
365
369 template<class T, class A>
370 class SLListConstIterator : public Dune::ForwardIteratorFacade<SLListConstIterator<T,A>, const T, const T&, std::size_t>
371 {
372 friend class SLListIterator<T,A>;
373 friend class SLList<T,A>;
374
375 public:
376 inline SLListConstIterator()
377 : current_(0)
378 {}
379
380 inline SLListConstIterator(typename SLList<T,A>::Element* item)
381 : current_(item)
382 {}
383
384 inline SLListConstIterator(const SLListIterator<T,A>& other)
385 : current_(other.current_)
386 {}
387
389 : current_(other.iterator_.current_)
390 {}
391
396 inline const T& dereference() const
397 {
398 return current_->item_;
399 }
400
406 inline bool equals(const SLListConstIterator<T,A>& other) const
407 {
408 return current_==other.current_;
409 }
410
414 inline void increment()
415 {
416 current_ = current_->next_;
417 }
418
419 private:
421 typename SLList<T,A>::Element* current_;
422 };
423
427 template<typename T, class A>
428 class SLListModifyIterator : public Dune::ForwardIteratorFacade<SLListModifyIterator<T,A>, T, T&, std::size_t>
429 {
430 friend class SLListConstIterator<T,A>;
431 friend class SLListIterator<T,A>;
432 public:
433 inline SLListModifyIterator(SLListIterator<T,A> beforeIterator,
434 SLListIterator<T,A> _iterator)
435 : beforeIterator_(beforeIterator), iterator_(_iterator)
436 {}
437
438 inline SLListModifyIterator()
439 : beforeIterator_(), iterator_()
440 {}
441
446 inline T& dereference() const
447 {
448 return *iterator_;
449 }
450
456 inline bool equals(const SLListConstIterator<T,A>& other) const
457 {
458 return iterator_== other;
459 }
460
461
467 inline bool equals(const SLListIterator<T,A>& other) const
468 {
469 return iterator_== other;
470 }
471
472
478 inline bool equals(const SLListModifyIterator<T,A>& other) const
479 {
480 return iterator_== other.iterator_;
481 }
482
486 inline void increment()
487 {
488 ++iterator_;
489 ++beforeIterator_;
490 }
491
505 inline void insert(const T& v)
506 {
507 beforeIterator_.insertAfter(v);
508 ++beforeIterator_;
509 }
510
518 inline void remove()
519 {
520 ++iterator_;
521 beforeIterator_.deleteNext();
522 }
523
524 private:
526 SLListIterator<T,A> beforeIterator_;
528 SLListIterator<T,A> iterator_;
529 };
530
531 template<typename T, typename A>
532 std::ostream& operator<<(std::ostream& os, const SLList<T,A>& sllist)
533 {
534 typedef typename SLList<T,A>::const_iterator Iterator;
535 Iterator end = sllist.end();
536 Iterator current= sllist.begin();
537
538 os << "{ ";
539
540 if(current!=end) {
541 os<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
542 ++current;
543
544 for(; current != end; ++current)
545 os<<", "<<*current<<" ("<<static_cast<const void*>(&(*current))<<")";
546 }
547 os<<"} ";
548 return os;
549 }
550
551 template<typename T, class A>
552 SLList<T,A>::Element::Element(const MemberType& item, Element* next)
553 : next_(next), item_(item)
554 {}
555
556 template<typename T, class A>
557 SLList<T,A>::Element::Element()
558 : next_(0), item_()
559 {}
560
561 template<typename T, class A>
562 SLList<T,A>::Element::~Element()
563 {
564 next_=0;
565 }
566
567 template<typename T, class A>
569 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
570 {
571 beforeHead_.next_=0;
572 assert(&beforeHead_==tail_);
573 assert(tail_->next_==0);
574 }
575
576 template<typename T, class A>
578 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
579 {
580 copyElements(other);
581 }
582
583 template<typename T, class A>
584 template<typename T1, class A1>
586 : beforeHead_(), tail_(&beforeHead_), allocator_(), size_(0)
587 {
588 copyElements(other);
589 }
590
591 template<typename T, typename A>
592 void SLList<T,A>::copyElements(const SLList<T,A>& other)
593 {
594 assert(tail_==&beforeHead_);
595 assert(size_==0);
596 typedef typename SLList<T,A>::const_iterator Iterator;
597 Iterator iend = other.end();
598 for(Iterator element=other.begin(); element != iend; ++element)
599 push_back(*element);
600
601 assert(other.size()==size());
602 }
603
604 template<typename T, class A>
606 {
607 clear();
608 }
609
610 template<typename T, class A>
611 bool SLList<T,A>::operator==(const SLList& other) const
612 {
613 if(size()!=other.size())
614 return false;
615 for(const_iterator iter=begin(), oiter=other.begin();
616 iter != end(); ++iter, ++oiter)
617 if(*iter!=*oiter)
618 return false;
619 return true;
620 }
621
622 template<typename T, class A>
623 bool SLList<T,A>::operator!=(const SLList& other) const
624 {
625 if(size()==other.size()) {
626 for(const_iterator iter=begin(), oiter=other.begin();
627 iter != end(); ++iter, ++oiter)
628 if(*iter!=*oiter)
629 return true;
630 return false;
631 }else
632 return true;
633 }
634 template<typename T, class A>
636 {
637 clear();
638 copyElements(other);
639 return *this;
640 }
641
642 template<typename T, class A>
643 inline void SLList<T,A>::push_back(const MemberType& item)
644 {
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);
650 tail_->next_=0;
651 assert(tail_->next_==0);
652 ++size_;
653 }
654
655 template<typename T, class A>
656 inline void SLList<T,A>::insertAfter(Element* current, const T& item)
657 {
658 assert(current);
659
660#ifndef NDEBUG
661 bool changeTail = (current == tail_);
662#endif
663
664 // Save old next element
665 Element* tmp = current->next_;
666
667 assert(!changeTail || !tmp);
668
669 // Allocate space
670 current->next_ = allocator_.allocate(1);
671
672 // Use copy constructor to initialize memory
673 std::allocator_traits<Allocator>::construct(allocator_, current->next_, Element(item,tmp));
674
675 //::new(static_cast<void*>(&(current->next_->item_))) T(item);
676
677 if(!current->next_->next_) {
678 // Update tail
679 assert(changeTail);
680 tail_ = current->next_;
681 }
682 ++size_;
683 assert(!tail_->next_);
684 }
685
686 template<typename T, class A>
687 inline void SLList<T,A>::push_front(const MemberType& item)
688 {
689 if(tail_ == &beforeHead_) {
690 // list was empty
691 beforeHead_.next_ = tail_ = allocator_.allocate(1, 0);
692 ::new(static_cast<void*>(&beforeHead_.next_->item_))T(item);
693 beforeHead_.next_->next_=0;
694 }else{
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;
699 }
700 assert(tail_->next_==0);
701 ++size_;
702 }
703
704
705 template<typename T, class A>
706 inline void SLList<T,A>::deleteNext(Element* current)
707 {
708 this->template deleteNext<true>(current);
709 }
710
711 template<typename T, class A>
712 template<bool watchForTail>
713 inline void SLList<T,A>::deleteNext(Element* current)
714 {
715 assert(current->next_);
716 Element* next = current->next_;
717
718 if(watchForTail)
719 if(next == tail_) {
720 // deleting last element changes tail!
721 tail_ = current;
722 }
723
724 current->next_ = next->next_;
725 std::allocator_traits<Allocator>::destroy(allocator_, next);
726 allocator_.deallocate(next, 1);
727 --size_;
728 assert(!watchForTail || &beforeHead_ != tail_ || size_==0);
729 }
730
731 template<typename T, class A>
733 {
734 deleteNext(&beforeHead_);
735 }
736
737 template<typename T, class A>
738 inline void SLList<T,A>::clear()
739 {
740 while(beforeHead_.next_ ) {
741 this->template deleteNext<false>(&beforeHead_);
742 }
743
744 assert(size_==0);
745 // update the tail!
746 tail_ = &beforeHead_;
747 }
748
749 template<typename T, class A>
750 inline bool SLList<T,A>::empty() const
751 {
752 return (&beforeHead_ == tail_);
753 }
754
755 template<typename T, class A>
756 inline int SLList<T,A>::size() const
757 {
758 return size_;
759 }
760
761 template<typename T, class A>
763 {
764 return iterator(beforeHead_.next_, this);
765 }
766
767 template<typename T, class A>
769 {
770 return const_iterator(beforeHead_.next_);
771 }
772
773 template<typename T, class A>
775 {
776 return iterator();
777 }
778
779 template<typename T, class A>
781 {
782 return SLListModifyIterator<T,A>(iterator(tail_, this),iterator());
783 }
784
785
786 template<typename T, class A>
788 {
789 return SLListModifyIterator<T,A>(iterator(&beforeHead_, this),
790 iterator(beforeHead_.next_, this));
791 }
792
793 template<typename T, class A>
795 {
796 return const_iterator();
797 }
798
800}
801#endif
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:142
A constant iterator for the SLList.
Definition: sllist.hh:371
A mutable iterator for the SLList.
Definition: sllist.hh:271
A mutable iterator for the SLList.
Definition: sllist.hh:429
A single linked list.
Definition: sllist.hh:44
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
T & dereference() const
Dereferencing function for the iterator facade.
Definition: sllist.hh:294
MemberType item_
The element we hold.
Definition: sllist.hh:212
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
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< 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
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
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
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
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:238
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:260
This file implements iterator facade classes for writing stl conformant iterators.
Dune namespace.
Definition: alignedallocator.hh:13
constexpr std::integer_sequence< T, II..., T(IN)> push_back(std::integer_sequence< T, II... >, std::integral_constant< T, IN >={})
Append an index IN to the back of the sequence.
Definition: integersequence.hh:69
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 11, 23:29, 2024)