dune-istl 3.0-git
basearray.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_ISTL_BASEARRAY_HH
4#define DUNE_ISTL_BASEARRAY_HH
5
6#include "assert.h"
7#include <cmath>
8#include <cstddef>
9#include <memory>
10#include <algorithm>
11
12#include "istlexception.hh"
13#include <dune/common/iteratorfacades.hh>
14
19namespace Dune {
20
43 template<class B, class A=std::allocator<B> >
45 {
46 public:
47
48 //===== type definitions and constants
49
51 typedef B member_type;
52
54 typedef A allocator_type;
55
57 typedef typename A::size_type size_type;
58
59
60 //===== access to components
61
64 {
65#ifdef DUNE_ISTL_WITH_CHECKING
66 if (i>=n) DUNE_THROW(ISTLError,"index out of range");
67#endif
68 return p[i];
69 }
70
72 const B& operator[] (size_type i) const
73 {
74#ifdef DUNE_ISTL_WITH_CHECKING
75 if (i>=n) DUNE_THROW(ISTLError,"index out of range");
76#endif
77 return p[i];
78 }
79
81 template<class T>
83 : public RandomAccessIteratorFacade<RealIterator<T>, T>
84 {
85 public:
87 typedef typename std::remove_const<T>::type ValueType;
88
89 friend class RandomAccessIteratorFacade<RealIterator<const ValueType>, const ValueType>;
90 friend class RandomAccessIteratorFacade<RealIterator<ValueType>, ValueType>;
91 friend class RealIterator<const ValueType>;
92 friend class RealIterator<ValueType>;
93
96 : p(0), i(0)
97 {}
98
99 RealIterator (const B* _p, B* _i) : p(_p), i(_i)
100 { }
101
103 : p(it.p), i(it.i)
104 {}
105
108 {
109 return i-p;
110 }
111
113 bool equals (const RealIterator<ValueType>& other) const
114 {
115 assert(other.p==p);
116 return i==other.i;
117 }
118
120 bool equals (const RealIterator<const ValueType>& other) const
121 {
122 assert(other.p==p);
123 return i==other.i;
124 }
125
126 std::ptrdiff_t distanceTo(const RealIterator& o) const
127 {
128 return o.i-i;
129 }
130
131 private:
133 void increment()
134 {
135 ++i;
136 }
137
139 void decrement()
140 {
141 --i;
142 }
143
144 // Needed for operator[] of the iterator
145 B& elementAt (std::ptrdiff_t offset) const
146 {
147 return *(i+offset);
148 }
149
151 B& dereference () const
152 {
153 return *i;
154 }
155
156 void advance(std::ptrdiff_t d)
157 {
158 i+=d;
159 }
160
161 const B* p;
162 B* i;
163 };
164
167
168
171 {
172 return iterator(p,p);
173 }
174
177 {
178 return iterator(p,p+n);
179 }
180
184 {
185 return iterator(p,p+n-1);
186 }
187
191 {
192 return iterator(p,p-1);
193 }
194
197 {
198 return iterator(p,p+std::min(i,n));
199 }
200
203
206 {
207 return const_iterator(p,p+0);
208 }
209
212 {
213 return const_iterator(p,p+n);
214 }
215
219 {
220 return const_iterator(p,p+n-1);
221 }
222
226 {
227 return const_iterator(p,p-1);
228 }
229
232 {
233 return const_iterator(p,p+std::min(i,n));
234 }
235
236
237 //===== sizes
238
241 {
242 return n;
243 }
244
245 protected:
248 : n(0), p(0)
249 {}
252 : n(n_), p(p_)
253 {}
254 size_type n; // number of elements in array
255 B *p; // pointer to dynamically allocated built-in array
256 };
257
258
259
274 template<class B, class A=std::allocator<B> >
276 {
277 public:
278
279 //===== type definitions and constants
280
282 typedef B member_type;
283
285 typedef A allocator_type;
286
289
292
295
297 typedef typename A::difference_type difference_type;
298
299 //===== constructors and such
300
305
308 : base_array_unmanaged<B,A>(_n ,_p)
309 {}
310
311 //===== window manipulation methods
312
314 void set (size_type _n, B* _p)
315 {
316 this->n = _n;
317 this->p = _p;
318 }
319
322 {
323 this->p += this->n;
324 this->n = newsize;
325 }
326
328 void move (difference_type offset, size_type newsize)
329 {
330 this->p += offset;
331 this->n = newsize;
332 }
333
335 void move (difference_type offset)
336 {
337 this->p += offset;
338 }
339
341 B* getptr ()
342 {
343 return this->p;
344 }
345 };
346
347
348
364 template<class B, class A=std::allocator<B> >
366 {
367 public:
368
369 //===== type definitions and constants
370
372 typedef B member_type;
373
375 typedef A allocator_type;
376
379
382
385
387 typedef typename A::difference_type difference_type;
388
389 //===== constructors and such
390
393 : base_array_unmanaged<B,A>()
394 {}
395
398 : base_array_unmanaged<B,A>(_n, 0)
399 {
400 if (this->n>0) {
401 this->p = allocator_.allocate(this->n);
402 new (this->p)B[this->n];
403 } else
404 {
405 this->n = 0;
406 this->p = 0;
407 }
408 }
409
412 {
413 // allocate memory with same size as a
414 this->n = a.n;
415
416 if (this->n>0) {
417 this->p = allocator_.allocate(this->n);
418 new (this->p)B[this->n];
419 } else
420 {
421 this->n = 0;
422 this->p = 0;
423 }
424
425 // and copy elements
426 for (size_type i=0; i<this->n; i++) this->p[i]=a.p[i];
427 }
428
431 {
432 const base_array& a = static_cast<const base_array&>(_a);
433
434 // allocate memory with same size as a
435 this->n = a.n;
436 if (this->n>0) {
437 this->p = allocator_.allocate(this->n);
438 new (this->p)B[this->n];
439 } else
440 {
441 this->n = 0;
442 this->p = 0;
443 }
444
445 // and copy elements
446 for (size_type i=0; i<this->n; i++) this->p[i]=a.p[i];
447 }
448
449
452 {
453 if (this->n>0) {
454 int i=this->n;
455 while (i)
456 this->p[--i].~B();
457 allocator_.deallocate(this->p,this->n);
458 }
459 }
460
462 void resize (size_type _n)
463 {
464 if (this->n==_n) return;
465
466 if (this->n>0) {
467 int i=this->n;
468 while (i)
469 this->p[--i].~B();
470 allocator_.deallocate(this->p,this->n);
471 }
472 this->n = _n;
473 if (this->n>0) {
474 this->p = allocator_.allocate(this->n);
475 new (this->p)B[this->n];
476 } else
477 {
478 this->n = 0;
479 this->p = 0;
480 }
481 }
482
485 {
486 if (&a!=this) // check if this and a are different objects
487 {
488 // adjust size of array
489 if (this->n!=a.n) // check if size is different
490 {
491 if (this->n>0) {
492 int i=this->n;
493 while (i)
494 this->p[--i].~B();
495 allocator_.deallocate(this->p,this->n); // delete old memory
496 }
497 this->n = a.n;
498 if (this->n>0) {
499 this->p = allocator_.allocate(this->n);
500 new (this->p)B[this->n];
501 } else
502 {
503 this->n = 0;
504 this->p = 0;
505 }
506 }
507 // copy data
508 for (size_type i=0; i<this->n; i++) this->p[i]=a.p[i];
509 }
510 return *this;
511 }
512
515 {
516 return this->operator=(static_cast<const base_array&>(a));
517 }
518
519 protected:
520
522 };
523
524
525
526
546 template<class B, class A=std::allocator<B> >
548 {
549 public:
550
551 //===== type definitions and constants
552
554 typedef B member_type;
555
557 typedef A allocator_type;
558
560 typedef typename A::size_type size_type;
561
562 //===== access to components
563
566 {
567 const size_type* lb = std::lower_bound(j, j+n, i);
568 if (lb == j+n || *lb != i)
569 DUNE_THROW(ISTLError,"index "<<i<<" not in compressed array");
570 return p[lb-j];
571 }
572
574 const B& operator[] (size_type i) const
575 {
576 const size_type* lb = std::lower_bound(j, j+n, i);
577 if (lb == j+n || *lb != i)
578 DUNE_THROW(ISTLError,"index "<<i<<" not in compressed array");
579 return p[lb-j];
580 }
581
583 template<class T>
585 : public BidirectionalIteratorFacade<RealIterator<T>, T>
586 {
587 public:
589 typedef typename std::remove_const<T>::type ValueType;
590
591 friend class BidirectionalIteratorFacade<RealIterator<const ValueType>, const ValueType>;
592 friend class BidirectionalIteratorFacade<RealIterator<ValueType>, ValueType>;
593 friend class RealIterator<const ValueType>;
594 friend class RealIterator<ValueType>;
595
598 : p(0), j(0), i(0)
599 {}
600
603 : p(_p), j(_j), i(_i)
604 { }
605
610 : p(it.p), j(it.j), i(it.i)
611 {}
612
613
615 bool equals (const RealIterator<ValueType>& it) const
616 {
617 assert(p==it.p);
618 return (i)==(it.i);
619 }
620
623 {
624 assert(p==it.p);
625 return (i)==(it.i);
626 }
627
628
631 {
632 return j[i];
633 }
634
637 {
638 return j[i] = k;
639 }
640
649 {
650 return i;
651 }
652
653 private:
655 void increment()
656 {
657 ++i;
658 }
659
661 void decrement()
662 {
663 --i;
664 }
665
667 B& dereference () const
668 {
669 return p[i];
670 }
671
672 B* p;
673 size_type* j;
674 size_type i;
675 };
676
679
682 {
683 return iterator(p,j,0);
684 }
685
688 {
689 return iterator(p,j,n);
690 }
691
695 {
696 return iterator(p,j,n-1);
697 }
698
702 {
703 return iterator(p,j,-1);
704 }
705
708 {
709 const size_type* lb = std::lower_bound(j, j+n, i);
710 return (lb != j+n && *lb == i)
711 ? iterator(p,j,lb-j)
712 : end();
713 }
714
717
720 {
721 return const_iterator(p,j,0);
722 }
723
726 {
727 return const_iterator(p,j,n);
728 }
729
733 {
734 return const_iterator(p,j,n-1);
735 }
736
740 {
741 return const_iterator(p,j,-1);
742 }
743
746 {
747 const size_type* lb = std::lower_bound(j, j+n, i);
748 return (lb != j+n && *lb == i)
749 ? const_iterator(p,j,lb-j)
750 : end();
751 }
752
753 //===== sizes
754
757 {
758 return n;
759 }
760
761 protected:
764 : n(0), p(0), j(0)
765 {}
766
767 size_type n; // number of elements in array
768 B *p; // pointer to dynamically allocated built-in array
769 size_type* j; // the index set
770 };
771
772} // end namespace
773
774#endif
Definition basearray.hh:19
A simple array container for objects of type B.
Definition basearray.hh:45
iterator begin()
begin iterator
Definition basearray.hh:170
RealIterator< B > iterator
iterator type for sequential access
Definition basearray.hh:166
const_iterator find(size_type i) const
random access returning iterator (end if not contained)
Definition basearray.hh:231
const_iterator begin() const
begin const_iterator
Definition basearray.hh:205
size_type n
Definition basearray.hh:254
iterator beforeBegin()
Definition basearray.hh:190
A allocator_type
export the allocator type
Definition basearray.hh:54
B & operator[](size_type i)
random access to blocks
Definition basearray.hh:63
RealIterator< const B > const_iterator
iterator class for sequential access
Definition basearray.hh:202
B member_type
export the type representing the components
Definition basearray.hh:51
const_iterator beforeEnd() const
Definition basearray.hh:218
base_array_unmanaged()
makes empty array
Definition basearray.hh:247
B * p
Definition basearray.hh:255
size_type size() const
number of blocks in the array (are of size 1 here)
Definition basearray.hh:240
const_iterator beforeBegin() const
Definition basearray.hh:225
base_array_unmanaged(size_type n_, B *p_)
make an initialized array
Definition basearray.hh:251
iterator find(size_type i)
random access returning iterator (end if not contained)
Definition basearray.hh:196
const_iterator end() const
end const_iterator
Definition basearray.hh:211
A::size_type size_type
the type for the index access
Definition basearray.hh:57
iterator end()
end iterator
Definition basearray.hh:176
iterator beforeEnd()
Definition basearray.hh:183
Iterator implementation class
Definition basearray.hh:84
RealIterator(const RealIterator< ValueType > &it)
Definition basearray.hh:102
bool equals(const RealIterator< const ValueType > &other) const
equality
Definition basearray.hh:120
size_type index() const
return index
Definition basearray.hh:107
std::ptrdiff_t distanceTo(const RealIterator &o) const
Definition basearray.hh:126
RealIterator()
constructor
Definition basearray.hh:95
std::remove_const< T >::type ValueType
The unqualified value type.
Definition basearray.hh:87
bool equals(const RealIterator< ValueType > &other) const
equality
Definition basearray.hh:113
RealIterator(const B *_p, B *_i)
Definition basearray.hh:99
Extend base_array_unmanaged by functions to manipulate.
Definition basearray.hh:276
void advance(difference_type newsize)
advance pointer by newsize elements and then set size to new size
Definition basearray.hh:321
base_array_unmanaged< B, A >::iterator iterator
make iterators available as types
Definition basearray.hh:288
base_array_unmanaged< B, A >::size_type size_type
The type used for the index access.
Definition basearray.hh:294
void move(difference_type offset, size_type newsize)
increment pointer by offset and set size
Definition basearray.hh:328
A::difference_type difference_type
The type used for the difference between two iterator positions.
Definition basearray.hh:297
B member_type
export the type representing the components
Definition basearray.hh:282
B * getptr()
return the pointer
Definition basearray.hh:341
base_array_window()
makes empty array
Definition basearray.hh:302
base_array_unmanaged< B, A >::const_iterator const_iterator
make iterators available as types
Definition basearray.hh:291
void move(difference_type offset)
increment pointer by offset, leave size
Definition basearray.hh:335
base_array_window(B *_p, size_type _n)
make array from given pointer and size
Definition basearray.hh:307
A allocator_type
export the allocator type
Definition basearray.hh:285
void set(size_type _n, B *_p)
set pointer and length
Definition basearray.hh:314
This container extends base_array_unmanaged by memory management with the usual copy semantics provid...
Definition basearray.hh:366
base_array_unmanaged< B, A >::const_iterator const_iterator
make iterators available as types
Definition basearray.hh:381
base_array & operator=(const base_array &a)
assignment
Definition basearray.hh:484
base_array(const base_array &a)
copy constructor
Definition basearray.hh:411
B member_type
export the type representing the components
Definition basearray.hh:372
base_array_unmanaged< B, A >::iterator iterator
make iterators available as types
Definition basearray.hh:378
void resize(size_type _n)
reallocate array to given size, any data is lost
Definition basearray.hh:462
A allocator_type
export the allocator type
Definition basearray.hh:375
A allocator_
Definition basearray.hh:521
~base_array()
free dynamic memory
Definition basearray.hh:451
base_array_unmanaged< B, A >::size_type size_type
The type used for the index access.
Definition basearray.hh:384
base_array()
makes empty array
Definition basearray.hh:392
base_array(size_type _n)
make array with _n components
Definition basearray.hh:397
base_array(const base_array_unmanaged< B, A > &_a)
construct from base class object
Definition basearray.hh:430
A::difference_type difference_type
The type used for the difference between two iterator positions.
Definition basearray.hh:387
A simple array container with non-consecutive index set.
Definition basearray.hh:548
const_iterator beforeBegin() const
Definition basearray.hh:739
const_iterator end() const
end const_iterator
Definition basearray.hh:725
RealIterator< const B > const_iterator
const_iterator class for sequential access
Definition basearray.hh:716
B * p
Definition basearray.hh:768
RealIterator< B > iterator
The iterator type.
Definition basearray.hh:678
A::size_type size_type
The type used for the index access.
Definition basearray.hh:560
iterator find(size_type i)
random access returning iterator (end if not contained)
Definition basearray.hh:707
iterator beforeBegin()
Definition basearray.hh:701
iterator beforeEnd()
Definition basearray.hh:694
B member_type
export the type representing the components
Definition basearray.hh:554
size_type n
Definition basearray.hh:767
compressed_base_array_unmanaged()
makes empty array
Definition basearray.hh:763
B & operator[](size_type i)
random access to blocks, assumes ascending ordering
Definition basearray.hh:565
size_type size() const
number of blocks in the array (are of size 1 here)
Definition basearray.hh:756
const_iterator find(size_type i) const
random access returning iterator (end if not contained)
Definition basearray.hh:745
A allocator_type
export the allocator type
Definition basearray.hh:557
iterator begin()
begin iterator
Definition basearray.hh:681
size_type * j
Definition basearray.hh:769
const_iterator beforeEnd() const
Definition basearray.hh:732
const_iterator begin() const
begin const_iterator
Definition basearray.hh:719
iterator end()
end iterator
Definition basearray.hh:687
iterator class for sequential access
Definition basearray.hh:586
RealIterator(const RealIterator< ValueType > &it)
Copy constructor from mutable iterator.
Definition basearray.hh:609
bool equals(const RealIterator< ValueType > &it) const
equality
Definition basearray.hh:615
RealIterator()
constructor
Definition basearray.hh:597
RealIterator(B *_p, size_type *_j, size_type _i)
constructor
Definition basearray.hh:602
bool equals(const RealIterator< const ValueType > &it) const
equality
Definition basearray.hh:622
size_type offset() const
offset from the first entry.
Definition basearray.hh:648
void setindex(size_type k)
Set index corresponding to pointer.
Definition basearray.hh:636
std::remove_const< T >::type ValueType
The unqualified value type.
Definition basearray.hh:589
size_type index() const
return index corresponding to pointer
Definition basearray.hh:630
derive error class from the base class in common
Definition istlexception.hh:16