Dune Core Modules (2.8.0)

arraylist.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
4#ifndef DUNE_COMMON_ARRAYLIST_HH
5#define DUNE_COMMON_ARRAYLIST_HH
6
7#include <array>
8#include <cassert>
9#include <memory>
10#include <vector>
11#include "iteratorfacades.hh"
12
13namespace Dune
14{
15 // forward declaration
16 template<class T, int N, class A>
17 class ArrayListIterator;
18
19 template<class T, int N, class A>
20 class ConstArrayListIterator;
21
58 template<class T, int N=100, class A=std::allocator<T> >
60 {
61 public:
67 typedef T MemberType;
68
72 typedef T value_type;
73
77 typedef T& reference;
78
82 typedef const T& const_reference;
83
87 typedef T* pointer;
88
92 typedef const T* const_pointer;
93
94 enum
95 {
100 chunkSize_ = (N > 0) ? N : 1
101 };
102
107
112
116 typedef std::size_t size_type;
117
121 typedef std::ptrdiff_t difference_type;
122
128
135
141
147
152 inline void push_back(const_reference entry);
153
160
167
172 inline size_type size() const;
173
181 inline void purge();
182
186 inline void clear();
191
192 private:
193
197 using SmartPointerAllocator = typename std::allocator_traits<A>::template rebind_alloc< std::shared_ptr< std::array<MemberType,chunkSize_> > >;
198
202 using ArrayAllocator = typename std::allocator_traits<A>::template rebind_alloc< std::array<MemberType,chunkSize_> >;
203
207 friend class ArrayListIterator<T,N,A>;
208 friend class ConstArrayListIterator<T,N,A>;
209
211 std::vector<std::shared_ptr<std::array<MemberType,chunkSize_> >,
212 SmartPointerAllocator> chunks_;
221 size_type capacity_;
223 size_type size_;
225 size_type start_;
234 inline reference elementAt(size_type i);
235
244 inline const_reference elementAt(size_type i) const;
245 };
246
247
251 template<class T, int N, class A>
252 class ArrayListIterator : public RandomAccessIteratorFacade<ArrayListIterator<T,N,A>,
253 typename A::value_type,
254 typename A::value_type &,
255 typename A::difference_type>
256 {
257
258 friend class ArrayList<T,N,A>;
259 friend class ConstArrayListIterator<T,N,A>;
260 public:
264 typedef typename A::value_type MemberType;
265
266 typedef typename A::difference_type difference_type;
267
268 typedef typename A::size_type size_type;
269
270 using reference = typename A::value_type &;
271
272 using const_reference = typename A::value_type const&;
273
274 enum
275 {
281 chunkSize_ = (N > 0) ? N : 1
282 };
283
284
290 inline bool equals(const ArrayListIterator<MemberType,N,A>& other) const;
291
297 inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
298
302 inline void increment();
303
307 inline void decrement();
308
313 inline reference elementAt(size_type i) const;
314
319 inline reference dereference() const;
320
332 inline void eraseToHere();
333
335 inline size_type position(){return position_;}
336
338 inline void advance(difference_type n);
339
341 inline difference_type distanceTo(const ArrayListIterator<T,N,A>& other) const;
342
345
347 inline ArrayListIterator() : position_(0), list_(nullptr)
348 {}
349
350 private:
356 inline ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position);
357
361 size_type position_;
365 ArrayList<T,N,A>* list_;
366 };
367
371 template<class T, int N, class A>
373 : public RandomAccessIteratorFacade<ConstArrayListIterator<T,N,A>,
374 const typename A::value_type,
375 typename A::value_type const&,
376 typename A::difference_type>
377 {
378
379 friend class ArrayList<T,N,A>;
380 friend class ArrayListIterator<T,N,A>;
381
382 public:
386 typedef typename A::value_type MemberType;
387
388 typedef typename A::difference_type difference_type;
389
390 typedef typename A::size_type size_type;
391
392 using reference = typename A::value_type &;
393
394 using const_reference = typename A::value_type const&;
395
396 enum
397 {
403 chunkSize_ = (N > 0) ? N : 1
404 };
405
411 inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
412
416 inline void increment();
417
421 inline void decrement();
422
424 inline void advance(difference_type n);
425
427 inline difference_type distanceTo(const ConstArrayListIterator<T,N,A>& other) const;
428
433 inline const_reference elementAt(size_type i) const;
434
439 inline const_reference dereference() const;
440
441 inline const ConstArrayListIterator<T,N,A>& operator=(const ConstArrayListIterator<T,N,A>& other);
442
443 inline ConstArrayListIterator() : position_(0), list_(nullptr)
444 {}
445
447
448 private:
449
455 inline ConstArrayListIterator(const ArrayList<T,N,A>& arrayList, size_type position);
456
460 size_type position_;
464 const ArrayList<T,N,A>* list_;
465 };
466
467
468 template<class T, int N, class A>
470 : capacity_(0), size_(0), start_(0)
471 {
472 chunks_.reserve(100);
473 }
474
475 template<class T, int N, class A>
477 capacity_=0;
478 size_=0;
479 start_=0;
480 chunks_.clear();
481 }
482
483 template<class T, int N, class A>
485 {
486 return size_;
487 }
488
489 template<class T, int N, class A>
491 {
492 size_t index=start_+size_;
493 if(index==capacity_)
494 {
495 chunks_.push_back(std::make_shared<std::array<MemberType,chunkSize_> >());
496 capacity_ += chunkSize_;
497 }
498 elementAt(index)=entry;
499 ++size_;
500 }
501
502 template<class T, int N, class A>
504 {
505 return elementAt(start_+i);
506 }
507
508
509 template<class T, int N, class A>
511 {
512 return elementAt(start_+i);
513 }
514
515 template<class T, int N, class A>
517 {
518 return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
519 }
520
521
522 template<class T, int N, class A>
524 {
525 return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
526 }
527
528 template<class T, int N, class A>
530 {
531 return ArrayListIterator<T,N,A>(*this, start_);
532 }
533
534 template<class T, int N, class A>
536 {
537 return ConstArrayListIterator<T,N,A>(*this, start_);
538 }
539
540 template<class T, int N, class A>
542 {
543 return ArrayListIterator<T,N,A>(*this, start_+size_);
544 }
545
546 template<class T, int N, class A>
548 {
549 return ConstArrayListIterator<T,N,A>(*this, start_+size_);
550 }
551
552 template<class T, int N, class A>
554 {
555 // Distance to copy to the left.
556 size_t distance = start_/chunkSize_;
557 if(distance>0) {
558 // Number of chunks with entries in it;
559 size_t chunks = ((start_%chunkSize_ + size_)/chunkSize_ );
560
561 // Copy chunks to the left.
562 std::copy(chunks_.begin()+distance,
563 chunks_.begin()+(distance+chunks), chunks_.begin());
564
565 // Calculate new parameters
566 start_ = start_ % chunkSize_;
567 //capacity += distance * chunkSize_;
568 }
569 }
570
571 template<class T, int N, class A>
572 void ArrayListIterator<T,N,A>::advance(difference_type i)
573 {
574 position_+=i;
575 }
576
577 template<class T, int N, class A>
579 {
580 position_+=i;
581 }
582
583
584 template<class T, int N, class A>
586 {
587 // Makes only sense if we reference a common list
588 assert(list_==(other.list_));
589 return position_==other.position_ ;
590 }
591
592
593 template<class T, int N, class A>
595 {
596 // Makes only sense if we reference a common list
597 assert(list_==(other.list_));
598 return position_==other.position_ ;
599 }
600
601
602 template<class T, int N, class A>
604 {
605 // Makes only sense if we reference a common list
606 assert(list_==(other.list_));
607 return position_==other.position_ ;
608 }
609
610 template<class T, int N, class A>
612 {
613 ++position_;
614 }
615
616 template<class T, int N, class A>
618 {
619 ++position_;
620 }
621
622 template<class T, int N, class A>
624 {
625 --position_;
626 }
627
628 template<class T, int N, class A>
630 {
631 --position_;
632 }
633
634 template<class T, int N, class A>
635 typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::elementAt(size_type i) const
636 {
637 return list_->elementAt(i+position_);
638 }
639
640 template<class T, int N, class A>
641 typename ConstArrayListIterator<T,N,A>::const_reference ConstArrayListIterator<T,N,A>::elementAt(size_type i) const
642 {
643 return list_->elementAt(i+position_);
644 }
645
646 template<class T, int N, class A>
647 typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::dereference() const
648 {
649 return list_->elementAt(position_);
650 }
651
652 template<class T, int N, class A>
653 typename ConstArrayListIterator<T,N,A>::const_reference ConstArrayListIterator<T,N,A>::dereference() const
654 {
655 return list_->elementAt(position_);
656 }
657
658 template<class T, int N, class A>
659 typename ArrayListIterator<T,N,A>::difference_type ArrayListIterator<T,N,A>::distanceTo(const ArrayListIterator<T,N,A>& other) const
660 {
661 // Makes only sense if we reference a common list
662 assert(list_==(other.list_));
663 return other.position_ - position_;
664 }
665
666 template<class T, int N, class A>
667 typename ConstArrayListIterator<T,N,A>::difference_type ConstArrayListIterator<T,N,A>::distanceTo(const ConstArrayListIterator<T,N,A>& other) const
668 {
669 // Makes only sense if we reference a common list
670 assert(list_==(other.list_));
671 return other.position_ - position_;
672 }
673
674 template<class T, int N, class A>
676 {
677 position_=other.position_;
678 list_=other.list_;
679 return *this;
680 }
681
682 template<class T, int N, class A>
684 {
685 position_=other.position_;
686 list_=other.list_;
687 return *this;
688 }
689
690 template<class T, int N, class A>
692 {
693 list_->size_ -= ++position_ - list_->start_;
694 // chunk number of the new position.
695 size_t posChunkStart = position_ / chunkSize_;
696 // number of chunks to deallocate
697 size_t chunks = (position_ - list_->start_ + list_->start_ % chunkSize_)
698 / chunkSize_;
699 list_->start_ = position_;
700
701 // Deallocate memory not needed any more.
702 for(size_t chunk=0; chunk<chunks; chunk++) {
703 --posChunkStart;
704 list_->chunks_[posChunkStart].reset();
705 }
706
707 // Capacity stays the same as the chunks before us
708 // are still there. They null pointers.
709 assert(list_->start_+list_->size_<=list_->capacity_);
710 }
711
712 template<class T, int N, class A>
714 : position_(position), list_(&arrayList)
715 {}
716
717
718 template<class T, int N, class A>
719 ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayList<T,N,A>& arrayList,
720 size_type position)
721 : position_(position), list_(&arrayList)
722 {}
723
724 template<class T, int N, class A>
725 ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayListIterator<T,N,A>& other)
726 : position_(other.position_), list_(other.list_)
727 {}
728
729
731}
732#endif
A random access iterator for the Dune::ArrayList class.
Definition: arraylist.hh:256
@ chunkSize_
The number of elements in one chunk of the list.
Definition: arraylist.hh:281
size_type position()
Definition: arraylist.hh:335
A::value_type MemberType
The member type.
Definition: arraylist.hh:264
ArrayListIterator()
Standard constructor.
Definition: arraylist.hh:347
A dynamically growing random access list.
Definition: arraylist.hh:60
T value_type
Value type for stl compliance.
Definition: arraylist.hh:72
@ chunkSize_
The number of elements in one chunk of the list. This has to be at least one. The default is 100.
Definition: arraylist.hh:100
const T * const_pointer
The type of a const pointer to the type we store.
Definition: arraylist.hh:92
ArrayListIterator< MemberType, N, A > iterator
A random access iterator.
Definition: arraylist.hh:106
const T & const_reference
The type of a const reference to the type we store.
Definition: arraylist.hh:82
T & reference
The type of a reference to the type we store.
Definition: arraylist.hh:77
std::size_t size_type
The size type.
Definition: arraylist.hh:116
T MemberType
The member type that is stored.
Definition: arraylist.hh:67
T * pointer
The type of a pointer to the type we store.
Definition: arraylist.hh:87
ConstArrayListIterator< MemberType, N, A > const_iterator
A constant random access iterator.
Definition: arraylist.hh:111
std::ptrdiff_t difference_type
The difference type.
Definition: arraylist.hh:121
A constant random access iterator for the Dune::ArrayList class.
Definition: arraylist.hh:377
@ chunkSize_
The number of elements in one chunk of the list.
Definition: arraylist.hh:403
A::value_type MemberType
The member type.
Definition: arraylist.hh:386
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:432
reference operator[](size_type i)
Get the element at specific position.
Definition: arraylist.hh:503
iterator begin()
Get an iterator that is positioned at the first element.
Definition: arraylist.hh:529
bool equals(const ArrayListIterator< MemberType, N, A > &other) const
Comares two iterators.
Definition: arraylist.hh:585
void increment()
Increment the iterator.
Definition: arraylist.hh:611
size_type size() const
Get the number of elements in the list.
Definition: arraylist.hh:484
void purge()
Purge the list.
Definition: arraylist.hh:553
void decrement()
decrement the iterator.
Definition: arraylist.hh:623
void eraseToHere()
Erase all entries before the current position and the one at the current position.
Definition: arraylist.hh:691
ArrayList()
Constructs an Array list with one chunk.
Definition: arraylist.hh:469
const_iterator begin() const
Get a random access iterator that is positioned at the first element.
Definition: arraylist.hh:535
void increment()
Increment the iterator.
Definition: arraylist.hh:617
iterator end()
Get a random access iterator positioned after the last element.
Definition: arraylist.hh:541
const_reference elementAt(size_type i) const
Get the value of the list at an arbitrary position.
Definition: arraylist.hh:641
const_reference operator[](size_type i) const
Get the element at specific position.
Definition: arraylist.hh:510
void decrement()
decrement the iterator.
Definition: arraylist.hh:629
void advance(difference_type n)
Definition: arraylist.hh:578
const_iterator end() const
Get a random access iterator positioned after the last element.
Definition: arraylist.hh:547
const_reference dereference() const
Access the element at the current position.
Definition: arraylist.hh:653
void clear()
Delete all entries from the list.
Definition: arraylist.hh:476
reference elementAt(size_type i) const
Get the value of the list at an arbitrary position.
Definition: arraylist.hh:635
bool equals(const ConstArrayListIterator< MemberType, N, A > &other) const
Comares to iterators.
Definition: arraylist.hh:603
void advance(difference_type n)
Definition: arraylist.hh:572
ArrayListIterator< T, N, A > & operator=(const ArrayListIterator< T, N, A > &other)
Definition: arraylist.hh:675
difference_type distanceTo(const ConstArrayListIterator< T, N, A > &other) const
Definition: arraylist.hh:667
reference dereference() const
Access the element at the current position.
Definition: arraylist.hh:647
void push_back(const_reference entry)
Append an entry to the list.
Definition: arraylist.hh:490
difference_type distanceTo(const ArrayListIterator< T, N, A > &other) const
Definition: arraylist.hh:659
constexpr auto equals(T1 &&t1, T2 &&t2)
Equality comparison.
Definition: hybridutilities.hh:400
constexpr decltype(auto) elementAt(Container &&c, Index &&i)
Get element at given position from container.
Definition: hybridutilities.hh:133
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
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)