DUNE PDELab (git)

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// 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
6#ifndef DUNE_COMMON_ARRAYLIST_HH
7#define DUNE_COMMON_ARRAYLIST_HH
8
9#include <array>
10#include <cassert>
11#include <memory>
12#include <vector>
13#include "iteratorfacades.hh"
14
15namespace Dune
16{
17 // forward declaration
18 template<class T, int N, class A>
19 class ArrayListIterator;
20
21 template<class T, int N, class A>
22 class ConstArrayListIterator;
23
60 template<class T, int N=100, class A=std::allocator<T> >
62 {
63 public:
69 typedef T MemberType;
70
74 typedef T value_type;
75
79 typedef T& reference;
80
84 typedef const T& const_reference;
85
89 typedef T* pointer;
90
94 typedef const T* const_pointer;
95
100 constexpr static int chunkSize_ = (N > 0) ? N : 1;
101
106
111
115 typedef std::size_t size_type;
116
120 typedef std::ptrdiff_t difference_type;
121
127
134
140
146
151 inline void push_back(const_reference entry);
152
159
166
171 inline size_type size() const;
172
180 inline void purge();
181
185 inline void clear();
190
191 private:
192
196 using SmartPointerAllocator = typename std::allocator_traits<A>::template rebind_alloc< std::shared_ptr< std::array<MemberType,chunkSize_> > >;
197
201 using ArrayAllocator = typename std::allocator_traits<A>::template rebind_alloc< std::array<MemberType,chunkSize_> >;
202
206 friend class ArrayListIterator<T,N,A>;
207 friend class ConstArrayListIterator<T,N,A>;
208
210 std::vector<std::shared_ptr<std::array<MemberType,chunkSize_> >,
211 SmartPointerAllocator> chunks_;
220 size_type capacity_;
222 size_type size_;
224 size_type start_;
233 inline reference elementAt(size_type i);
234
243 inline const_reference elementAt(size_type i) const;
244 };
245
246
250 template<class T, int N, class A>
251 class ArrayListIterator : public RandomAccessIteratorFacade<ArrayListIterator<T,N,A>,
252 typename A::value_type,
253 typename A::value_type &,
254 typename A::difference_type>
255 {
256
257 friend class ArrayList<T,N,A>;
258 friend class ConstArrayListIterator<T,N,A>;
259 public:
263 typedef typename A::value_type MemberType;
264
265 typedef typename A::difference_type difference_type;
266
267 typedef typename A::size_type size_type;
268
269 using reference = typename A::value_type &;
270
271 using const_reference = typename A::value_type const&;
272
278 constexpr static int chunkSize_ = (N > 0) ? N : 1;
279
280
286 inline bool equals(const ArrayListIterator<MemberType,N,A>& other) const;
287
293 inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
294
298 inline void increment();
299
303 inline void decrement();
304
309 inline reference elementAt(size_type i) const;
310
315 inline reference dereference() const;
316
326 inline void eraseToHere();
327
329 inline size_type position(){return position_;}
330
332 inline void advance(difference_type n);
333
335 inline difference_type distanceTo(const ArrayListIterator<T,N,A>& other) const;
336
338 inline ArrayListIterator() : position_(0), list_(nullptr)
339 {}
340
341 private:
347 inline ArrayListIterator(ArrayList<T,N,A>& arrayList, size_type position);
348
352 size_type position_;
356 ArrayList<T,N,A>* list_;
357 };
358
362 template<class T, int N, class A>
364 : public RandomAccessIteratorFacade<ConstArrayListIterator<T,N,A>,
365 const typename A::value_type,
366 typename A::value_type const&,
367 typename A::difference_type>
368 {
369
370 friend class ArrayList<T,N,A>;
371 friend class ArrayListIterator<T,N,A>;
372
373 public:
377 typedef typename A::value_type MemberType;
378
379 typedef typename A::difference_type difference_type;
380
381 typedef typename A::size_type size_type;
382
383 using reference = typename A::value_type const&;
384
385 using const_reference = typename A::value_type const&;
386
392 constexpr static int chunkSize_ = (N > 0) ? N : 1;
393
399 inline bool equals(const ConstArrayListIterator<MemberType,N,A>& other) const;
400
404 inline void increment();
405
409 inline void decrement();
410
412 inline void advance(difference_type n);
413
415 inline difference_type distanceTo(const ConstArrayListIterator<T,N,A>& other) const;
416
421 inline reference elementAt(size_type i) const;
422
427 inline reference dereference() const;
428
429 inline ConstArrayListIterator() : position_(0), list_(nullptr)
430 {}
431
433
434 private:
435
441 inline ConstArrayListIterator(const ArrayList<T,N,A>& arrayList, size_type position);
442
446 size_type position_;
450 const ArrayList<T,N,A>* list_;
451 };
452
453
454 template<class T, int N, class A>
456 : capacity_(0), size_(0), start_(0)
457 {
458 chunks_.reserve(100);
459 }
460
461 template<class T, int N, class A>
463 capacity_=0;
464 size_=0;
465 start_=0;
466 chunks_.clear();
467 }
468
469 template<class T, int N, class A>
471 {
472 return size_;
473 }
474
475 template<class T, int N, class A>
477 {
478 size_t index=start_+size_;
479 if(index==capacity_)
480 {
481 chunks_.push_back(std::make_shared<std::array<MemberType,chunkSize_> >());
482 capacity_ += chunkSize_;
483 }
484 elementAt(index)=entry;
485 ++size_;
486 }
487
488 template<class T, int N, class A>
490 {
491 return elementAt(start_+i);
492 }
493
494
495 template<class T, int N, class A>
497 {
498 return elementAt(start_+i);
499 }
500
501 template<class T, int N, class A>
503 {
504 return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
505 }
506
507
508 template<class T, int N, class A>
510 {
511 return chunks_[i/chunkSize_]->operator[](i%chunkSize_);
512 }
513
514 template<class T, int N, class A>
516 {
517 return ArrayListIterator<T,N,A>(*this, start_);
518 }
519
520 template<class T, int N, class A>
522 {
523 return ConstArrayListIterator<T,N,A>(*this, start_);
524 }
525
526 template<class T, int N, class A>
528 {
529 return ArrayListIterator<T,N,A>(*this, start_+size_);
530 }
531
532 template<class T, int N, class A>
534 {
535 return ConstArrayListIterator<T,N,A>(*this, start_+size_);
536 }
537
538 template<class T, int N, class A>
540 {
541 // Distance to copy to the left.
542 size_t distance = start_/chunkSize_;
543 if(distance>0) {
544 // Number of chunks with entries in it;
545 size_t chunks = ((start_%chunkSize_ + size_)/chunkSize_ );
546
547 // Copy chunks to the left.
548 std::copy(chunks_.begin()+distance,
549 chunks_.begin()+(distance+chunks), chunks_.begin());
550
551 // Calculate new parameters
552 start_ = start_ % chunkSize_;
553 //capacity += distance * chunkSize_;
554 }
555 }
556
557 template<class T, int N, class A>
558 void ArrayListIterator<T,N,A>::advance(difference_type i)
559 {
560 position_+=i;
561 }
562
563 template<class T, int N, class A>
565 {
566 position_+=i;
567 }
568
569
570 template<class T, int N, class A>
572 {
573 // Makes only sense if we reference a common list
574 assert(list_==(other.list_));
575 return position_==other.position_ ;
576 }
577
578
579 template<class T, int N, class A>
581 {
582 // Makes only sense if we reference a common list
583 assert(list_==(other.list_));
584 return position_==other.position_ ;
585 }
586
587
588 template<class T, int N, class A>
590 {
591 // Makes only sense if we reference a common list
592 assert(list_==(other.list_));
593 return position_==other.position_ ;
594 }
595
596 template<class T, int N, class A>
598 {
599 ++position_;
600 }
601
602 template<class T, int N, class A>
604 {
605 ++position_;
606 }
607
608 template<class T, int N, class A>
610 {
611 --position_;
612 }
613
614 template<class T, int N, class A>
616 {
617 --position_;
618 }
619
620 template<class T, int N, class A>
621 typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::elementAt(size_type i) const
622 {
623 return list_->elementAt(i+position_);
624 }
625
626 template<class T, int N, class A>
627 typename ConstArrayListIterator<T,N,A>::reference ConstArrayListIterator<T,N,A>::elementAt(size_type i) const
628 {
629 return list_->elementAt(i+position_);
630 }
631
632 template<class T, int N, class A>
633 typename ArrayListIterator<T,N,A>::reference ArrayListIterator<T,N,A>::dereference() const
634 {
635 return list_->elementAt(position_);
636 }
637
638 template<class T, int N, class A>
639 typename ConstArrayListIterator<T,N,A>::reference ConstArrayListIterator<T,N,A>::dereference() const
640 {
641 return list_->elementAt(position_);
642 }
643
644 template<class T, int N, class A>
645 typename ArrayListIterator<T,N,A>::difference_type ArrayListIterator<T,N,A>::distanceTo(const ArrayListIterator<T,N,A>& other) const
646 {
647 // Makes only sense if we reference a common list
648 assert(list_==(other.list_));
649 return other.position_ - position_;
650 }
651
652 template<class T, int N, class A>
653 typename ConstArrayListIterator<T,N,A>::difference_type ConstArrayListIterator<T,N,A>::distanceTo(const ConstArrayListIterator<T,N,A>& other) const
654 {
655 // Makes only sense if we reference a common list
656 assert(list_==(other.list_));
657 return other.position_ - position_;
658 }
659
660 template<class T, int N, class A>
662 {
663 list_->size_ -= ++position_ - list_->start_;
664 // chunk number of the new position.
665 size_t posChunkStart = position_ / chunkSize_;
666 // number of chunks to deallocate
667 size_t chunks = (position_ - list_->start_ + list_->start_ % chunkSize_)
668 / chunkSize_;
669 list_->start_ = position_;
670
671 // Deallocate memory not needed any more.
672 for(size_t chunk=0; chunk<chunks; chunk++) {
673 --posChunkStart;
674 list_->chunks_[posChunkStart].reset();
675 }
676
677 // Capacity stays the same as the chunks before us
678 // are still there. They null pointers.
679 assert(list_->start_+list_->size_<=list_->capacity_);
680 }
681
682 template<class T, int N, class A>
684 : position_(position), list_(&arrayList)
685 {}
686
687
688 template<class T, int N, class A>
689 ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayList<T,N,A>& arrayList,
690 size_type position)
691 : position_(position), list_(&arrayList)
692 {}
693
694 template<class T, int N, class A>
695 ConstArrayListIterator<T,N,A>::ConstArrayListIterator(const ArrayListIterator<T,N,A>& other)
696 : position_(other.position_), list_(other.list_)
697 {}
698
699
701}
702#endif
A random access iterator for the Dune::ArrayList class.
Definition: arraylist.hh:255
size_type position()
Definition: arraylist.hh:329
A::value_type MemberType
The member type.
Definition: arraylist.hh:263
ArrayListIterator()
Standard constructor.
Definition: arraylist.hh:338
static constexpr int chunkSize_
The number of elements in one chunk of the list.
Definition: arraylist.hh:278
A dynamically growing random access list.
Definition: arraylist.hh:62
T value_type
Value type for stl compliance.
Definition: arraylist.hh:74
static constexpr int 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:94
ArrayListIterator< MemberType, N, A > iterator
A random access iterator.
Definition: arraylist.hh:105
const T & const_reference
The type of a const reference to the type we store.
Definition: arraylist.hh:84
T & reference
The type of a reference to the type we store.
Definition: arraylist.hh:79
std::size_t size_type
The size type.
Definition: arraylist.hh:115
T MemberType
The member type that is stored.
Definition: arraylist.hh:69
T * pointer
The type of a pointer to the type we store.
Definition: arraylist.hh:89
ConstArrayListIterator< MemberType, N, A > const_iterator
A constant random access iterator.
Definition: arraylist.hh:110
std::ptrdiff_t difference_type
The difference type.
Definition: arraylist.hh:120
A constant random access iterator for the Dune::ArrayList class.
Definition: arraylist.hh:368
static constexpr int chunkSize_
The number of elements in one chunk of the list.
Definition: arraylist.hh:392
A::value_type MemberType
The member type.
Definition: arraylist.hh:377
Base class for stl conformant forward iterators.
Definition: iteratorfacades.hh:435
reference operator[](size_type i)
Get the element at specific position.
Definition: arraylist.hh:489
iterator begin()
Get an iterator that is positioned at the first element.
Definition: arraylist.hh:515
bool equals(const ArrayListIterator< MemberType, N, A > &other) const
Compares two iterators.
Definition: arraylist.hh:571
void increment()
Increment the iterator.
Definition: arraylist.hh:597
size_type size() const
Get the number of elements in the list.
Definition: arraylist.hh:470
void purge()
Purge the list.
Definition: arraylist.hh:539
void decrement()
decrement the iterator.
Definition: arraylist.hh:609
void eraseToHere()
Erase all entries before the current position and the one at the current position.
Definition: arraylist.hh:661
ArrayList()
Constructs an Array list with one chunk.
Definition: arraylist.hh:455
const_iterator begin() const
Get a random access iterator that is positioned at the first element.
Definition: arraylist.hh:521
void increment()
Increment the iterator.
Definition: arraylist.hh:603
reference elementAt(size_type i) const
Get the value of the list at an arbitrary position.
Definition: arraylist.hh:627
iterator end()
Get a random access iterator positioned after the last element.
Definition: arraylist.hh:527
reference dereference() const
Access the element at the current position.
Definition: arraylist.hh:639
const_reference operator[](size_type i) const
Get the element at specific position.
Definition: arraylist.hh:496
void decrement()
decrement the iterator.
Definition: arraylist.hh:615
void advance(difference_type n)
Definition: arraylist.hh:564
const_iterator end() const
Get a random access iterator positioned after the last element.
Definition: arraylist.hh:533
void clear()
Delete all entries from the list.
Definition: arraylist.hh:462
reference elementAt(size_type i) const
Get the value of the list at an arbitrary position.
Definition: arraylist.hh:621
bool equals(const ConstArrayListIterator< MemberType, N, A > &other) const
Compares to iterators.
Definition: arraylist.hh:589
void advance(difference_type n)
Definition: arraylist.hh:558
difference_type distanceTo(const ConstArrayListIterator< T, N, A > &other) const
Definition: arraylist.hh:653
reference dereference() const
Access the element at the current position.
Definition: arraylist.hh:633
void push_back(const_reference entry)
Append an entry to the list.
Definition: arraylist.hh:476
difference_type distanceTo(const ArrayListIterator< T, N, A > &other) const
Definition: arraylist.hh:645
constexpr auto equals(T1 &&t1, T2 &&t2)
Equality comparison.
Definition: hybridutilities.hh:587
constexpr decltype(auto) elementAt(Container &&c, Index &&i)
Get element at given position from container.
Definition: hybridutilities.hh:126
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:416
This file implements iterator facade classes for writing stl conformant iterators.
Dune namespace.
Definition: alignedallocator.hh:13
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 12, 23:30, 2024)