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 
19 namespace 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 
63  B& operator[] (size_type i)
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 
107  size_type index () const
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 
166  typedef RealIterator<B> iterator;
167 
168 
170  iterator begin ()
171  {
172  return iterator(p,p);
173  }
174 
176  iterator end ()
177  {
178  return iterator(p,p+n);
179  }
180 
183  iterator beforeEnd ()
184  {
185  return iterator(p,p+n-1);
186  }
187 
190  iterator beforeBegin ()
191  {
192  return iterator(p,p-1);
193  }
194 
196  iterator find (size_type i)
197  {
198  return iterator(p,p+std::min(i,n));
199  }
200 
202  typedef RealIterator<const B> const_iterator;
203 
205  const_iterator begin () const
206  {
207  return const_iterator(p,p+0);
208  }
209 
211  const_iterator end () const
212  {
213  return const_iterator(p,p+n);
214  }
215 
218  const_iterator beforeEnd () const
219  {
220  return const_iterator(p,p+n-1);
221  }
222 
225  const_iterator beforeBegin () const
226  {
227  return const_iterator(p,p-1);
228  }
229 
231  const_iterator find (size_type i) const
232  {
233  return const_iterator(p,p+std::min(i,n));
234  }
235 
236 
237  //===== sizes
238 
240  size_type size () const
241  {
242  return n;
243  }
244 
245  protected:
248  : n(0), p(0)
249  {}
251  base_array_unmanaged (size_type n_, B* p_)
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 
303  : base_array_unmanaged<B,A>()
304  { }
305 
307  base_array_window (B* _p, size_type _n)
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 
321  void advance (difference_type newsize)
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> >
365  class base_array : public base_array_unmanaged<B,A>
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 
397  base_array (size_type _n)
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 
484  base_array& operator= (const base_array& a)
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 
514  base_array& operator= (const base_array_unmanaged<B,A>& a)
515  {
516  return this->operator=(static_cast<const base_array&>(a));
517  }
518 
519  protected:
520 
521  A allocator_;
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 
565  B& operator[] (size_type i)
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 
602  RealIterator (B* _p, size_type* _j, size_type _i)
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 
622  bool equals (const RealIterator<const ValueType>& it) const
623  {
624  assert(p==it.p);
625  return (i)==(it.i);
626  }
627 
628 
630  size_type index () const
631  {
632  return j[i];
633  }
634 
636  void setindex (size_type k)
637  {
638  return j[i] = k;
639  }
640 
648  size_type offset () const
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 
681  iterator begin ()
682  {
683  return iterator(p,j,0);
684  }
685 
687  iterator end ()
688  {
689  return iterator(p,j,n);
690  }
691 
694  iterator beforeEnd ()
695  {
696  return iterator(p,j,n-1);
697  }
698 
701  iterator beforeBegin ()
702  {
703  return iterator(p,j,-1);
704  }
705 
707  iterator find (size_type i)
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 
719  const_iterator begin () const
720  {
721  return const_iterator(p,j,0);
722  }
723 
725  const_iterator end () const
726  {
727  return const_iterator(p,j,n);
728  }
729 
732  const_iterator beforeEnd () const
733  {
734  return const_iterator(p,j,n-1);
735  }
736 
739  const_iterator beforeBegin () const
740  {
741  return const_iterator(p,j,-1);
742  }
743 
745  const_iterator find (size_type i) const
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 
756  size_type size () const
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
base_array()
makes empty array
Definition: basearray.hh:392
std::ptrdiff_t distanceTo(const RealIterator &o) const
Definition: basearray.hh:126
base_array_window()
makes empty array
Definition: basearray.hh:302
iterator beforeBegin()
Definition: basearray.hh:190
base_array_window(B *_p, size_type _n)
make array from given pointer and size
Definition: basearray.hh:307
bool equals(const RealIterator< const ValueType > &it) const
equality
Definition: basearray.hh:622
base_array_unmanaged< B, A >::iterator iterator
make iterators available as types
Definition: basearray.hh:288
size_type n
Definition: basearray.hh:254
size_type offset() const
offset from the first entry.
Definition: basearray.hh:648
A simple array container with non-consecutive index set.
Definition: basearray.hh:547
iterator end()
end iterator
Definition: basearray.hh:176
void advance(difference_type newsize)
advance pointer by newsize elements and then set size to new size
Definition: basearray.hh:321
const_iterator find(size_type i) const
random access returning iterator (end if not contained)
Definition: basearray.hh:231
Iterator implementation class.
Definition: basearray.hh:82
RealIterator(const B *_p, B *_i)
Definition: basearray.hh:99
base_array_unmanaged< B, A >::size_type size_type
The type used for the index access.
Definition: basearray.hh:384
const_iterator begin() const
begin const_iterator
Definition: basearray.hh:205
RealIterator(const RealIterator< ValueType > &it)
Copy constructor from mutable iterator.
Definition: basearray.hh:609
A::size_type size_type
the type for the index access
Definition: basearray.hh:57
B * p
Definition: basearray.hh:768
B member_type
export the type representing the components
Definition: basearray.hh:372
RealIterator< const B > const_iterator
const_iterator class for sequential access
Definition: basearray.hh:716
std::remove_const< T >::type ValueType
The unqualified value type.
Definition: basearray.hh:589
RealIterator< B > iterator
The iterator type.
Definition: basearray.hh:678
const_iterator beforeEnd() const
Definition: basearray.hh:218
This container extends base_array_unmanaged by memory management with the usual copy semantics provid...
Definition: basearray.hh:365
B * getptr()
return the pointer
Definition: basearray.hh:341
RealIterator(const RealIterator< ValueType > &it)
Definition: basearray.hh:102
const_iterator beforeEnd() const
Definition: basearray.hh:732
const_iterator end() const
end const_iterator
Definition: basearray.hh:211
size_type index() const
return index corresponding to pointer
Definition: basearray.hh:630
compressed_base_array_unmanaged()
makes empty array
Definition: basearray.hh:763
RealIterator(B *_p, size_type *_j, size_type _i)
constructor
Definition: basearray.hh:602
base_array_unmanaged< B, A >::iterator iterator
make iterators available as types
Definition: basearray.hh:378
void move(difference_type offset)
increment pointer by offset, leave size
Definition: basearray.hh:335
iterator beforeBegin()
Definition: basearray.hh:701
size_type * j
Definition: basearray.hh:769
RealIterator< const B > const_iterator
iterator class for sequential access
Definition: basearray.hh:202
size_type index() const
return index
Definition: basearray.hh:107
void setindex(size_type k)
Set index corresponding to pointer.
Definition: basearray.hh:636
A allocator_type
export the allocator type
Definition: basearray.hh:54
base_array(const base_array_unmanaged< B, A > &_a)
construct from base class object
Definition: basearray.hh:430
const_iterator begin() const
begin const_iterator
Definition: basearray.hh:719
bool equals(const RealIterator< ValueType > &it) const
equality
Definition: basearray.hh:615
bool equals(const RealIterator< ValueType > &other) const
equality
Definition: basearray.hh:113
Definition: basearray.hh:19
base_array_unmanaged(size_type n_, B *p_)
make an initialized array
Definition: basearray.hh:251
void move(difference_type offset, size_type newsize)
increment pointer by offset and set size
Definition: basearray.hh:328
iterator begin()
begin iterator
Definition: basearray.hh:681
base_array(const base_array &a)
copy constructor
Definition: basearray.hh:411
B member_type
export the type representing the components
Definition: basearray.hh:554
B * p
Definition: basearray.hh:255
iterator find(size_type i)
random access returning iterator (end if not contained)
Definition: basearray.hh:196
const_iterator beforeBegin() const
Definition: basearray.hh:225
base_array_unmanaged< B, A >::const_iterator const_iterator
make iterators available as types
Definition: basearray.hh:291
iterator beforeEnd()
Definition: basearray.hh:694
~base_array()
free dynamic memory
Definition: basearray.hh:451
iterator begin()
begin iterator
Definition: basearray.hh:170
A::difference_type difference_type
The type used for the difference between two iterator positions.
Definition: basearray.hh:387
base_array_unmanaged< B, A >::size_type size_type
The type used for the index access.
Definition: basearray.hh:294
B & operator[](size_type i)
random access to blocks
Definition: basearray.hh:63
A simple array container for objects of type B.
Definition: basearray.hh:44
const_iterator end() const
end const_iterator
Definition: basearray.hh:725
size_type n
Definition: basearray.hh:767
iterator beforeEnd()
Definition: basearray.hh:183
base_array_unmanaged()
makes empty array
Definition: basearray.hh:247
size_type size() const
number of blocks in the array (are of size 1 here)
Definition: basearray.hh:240
B member_type
export the type representing the components
Definition: basearray.hh:282
base_array_unmanaged< B, A >::const_iterator const_iterator
make iterators available as types
Definition: basearray.hh:381
iterator find(size_type i)
random access returning iterator (end if not contained)
Definition: basearray.hh:707
A::difference_type difference_type
The type used for the difference between two iterator positions.
Definition: basearray.hh:297
RealIterator< B > iterator
iterator type for sequential access
Definition: basearray.hh:166
A::size_type size_type
The type used for the index access.
Definition: basearray.hh:560
void resize(size_type _n)
reallocate array to given size, any data is lost
Definition: basearray.hh:462
size_type size() const
number of blocks in the array (are of size 1 here)
Definition: basearray.hh:756
RealIterator()
constructor
Definition: basearray.hh:597
iterator class for sequential access
Definition: basearray.hh:584
std::remove_const< T >::type ValueType
The unqualified value type.
Definition: basearray.hh:87
RealIterator()
constructor
Definition: basearray.hh:95
bool equals(const RealIterator< const ValueType > &other) const
equality
Definition: basearray.hh:120
derive error class from the base class in common
Definition: istlexception.hh:16
Extend base_array_unmanaged by functions to manipulate.
Definition: basearray.hh:275
iterator end()
end iterator
Definition: basearray.hh:687
B member_type
export the type representing the components
Definition: basearray.hh:51
const_iterator find(size_type i) const
random access returning iterator (end if not contained)
Definition: basearray.hh:745
const_iterator beforeBegin() const
Definition: basearray.hh:739
base_array(size_type _n)
make array with _n components
Definition: basearray.hh:397