dune-istl  2.5.0
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 
45  template<class B, class A=std::allocator<B> >
47  {
48  public:
49 
50  //===== type definitions and constants
51 
53  typedef B member_type;
54 
56  typedef A allocator_type;
57 
59  typedef typename A::size_type size_type;
60 
61 
62  //===== access to components
63 
65  B& operator[] (size_type i)
66  {
67 #ifdef DUNE_ISTL_WITH_CHECKING
68  if (i>=n) DUNE_THROW(ISTLError,"index out of range");
69 #endif
70  return p[i];
71  }
72 
74  const B& operator[] (size_type i) const
75  {
76 #ifdef DUNE_ISTL_WITH_CHECKING
77  if (i>=n) DUNE_THROW(ISTLError,"index out of range");
78 #endif
79  return p[i];
80  }
81 
83  template<class T>
85  : public RandomAccessIteratorFacade<RealIterator<T>, T>
86  {
87  public:
89  typedef typename std::remove_const<T>::type ValueType;
90 
91  friend class RandomAccessIteratorFacade<RealIterator<const ValueType>, const ValueType>;
92  friend class RandomAccessIteratorFacade<RealIterator<ValueType>, ValueType>;
93  friend class RealIterator<const ValueType>;
94  friend class RealIterator<ValueType>;
95 
98  : p(0), i(0)
99  {}
100 
101  RealIterator (const B* _p, B* _i) : p(_p), i(_i)
102  { }
103 
105  : p(it.p), i(it.i)
106  {}
107 
109  size_type index () const
110  {
111  return i-p;
112  }
113 
115  bool equals (const RealIterator<ValueType>& other) const
116  {
117  assert(other.p==p);
118  return i==other.i;
119  }
120 
122  bool equals (const RealIterator<const ValueType>& other) const
123  {
124  assert(other.p==p);
125  return i==other.i;
126  }
127 
128  std::ptrdiff_t distanceTo(const RealIterator& o) const
129  {
130  return o.i-i;
131  }
132 
133  private:
135  void increment()
136  {
137  ++i;
138  }
139 
141  void decrement()
142  {
143  --i;
144  }
145 
146  // Needed for operator[] of the iterator
147  B& elementAt (std::ptrdiff_t offset) const
148  {
149  return *(i+offset);
150  }
151 
153  B& dereference () const
154  {
155  return *i;
156  }
157 
158  void advance(std::ptrdiff_t d)
159  {
160  i+=d;
161  }
162 
163  const B* p;
164  B* i;
165  };
166 
168  typedef RealIterator<B> iterator;
169 
170 
172  iterator begin ()
173  {
174  return iterator(p,p);
175  }
176 
178  iterator end ()
179  {
180  return iterator(p,p+n);
181  }
182 
185  iterator beforeEnd ()
186  {
187  return iterator(p,p+n-1);
188  }
189 
192  iterator beforeBegin ()
193  {
194  return iterator(p,p-1);
195  }
196 
198  iterator find (size_type i)
199  {
200  return iterator(p,p+std::min(i,n));
201  }
202 
204  typedef RealIterator<const B> const_iterator;
205 
207  const_iterator begin () const
208  {
209  return const_iterator(p,p+0);
210  }
211 
213  const_iterator end () const
214  {
215  return const_iterator(p,p+n);
216  }
217 
220  const_iterator beforeEnd () const
221  {
222  return const_iterator(p,p+n-1);
223  }
224 
227  const_iterator beforeBegin () const
228  {
229  return const_iterator(p,p-1);
230  }
231 
233  const_iterator find (size_type i) const
234  {
235  return const_iterator(p,p+std::min(i,n));
236  }
237 
238 
239  //===== sizes
240 
242  size_type size () const
243  {
244  return n;
245  }
246 
247  protected:
250  : n(0), p(0)
251  {}
253  base_array_unmanaged (size_type n_, B* p_)
254  : n(n_), p(p_)
255  {}
256  size_type n; // number of elements in array
257  B *p; // pointer to dynamically allocated built-in array
258  };
259 
260 
261 
277  template<class B, class A=std::allocator<B> >
279  {
280  public:
281 
282  //===== type definitions and constants
283 
285  typedef B member_type;
286 
288  typedef A allocator_type;
289 
292 
295 
298 
300  typedef typename A::difference_type difference_type;
301 
302  //===== constructors and such
303 
306  : base_array_unmanaged<B,A>()
307  { }
308 
310  base_array_window (B* _p, size_type _n)
311  : base_array_unmanaged<B,A>(_n ,_p)
312  {}
313 
314  //===== window manipulation methods
315 
317  void set (size_type _n, B* _p)
318  {
319  this->n = _n;
320  this->p = _p;
321  }
322 
324  void advance (difference_type newsize)
325  {
326  this->p += this->n;
327  this->n = newsize;
328  }
329 
331  void move (difference_type offset, size_type newsize)
332  {
333  this->p += offset;
334  this->n = newsize;
335  }
336 
338  void move (difference_type offset)
339  {
340  this->p += offset;
341  }
342 
344  B* getptr ()
345  {
346  return this->p;
347  }
348  };
349 
350 
351 
368  template<class B, class A=std::allocator<B> >
369  class base_array : public base_array_unmanaged<B,A>
370  {
371  public:
372 
373  //===== type definitions and constants
374 
376  typedef B member_type;
377 
379  typedef A allocator_type;
380 
383 
386 
389 
391  typedef typename A::difference_type difference_type;
392 
393  //===== constructors and such
394 
397  : base_array_unmanaged<B,A>()
398  {}
399 
401  base_array (size_type _n)
402  : base_array_unmanaged<B,A>(_n, 0)
403  {
404  if (this->n>0) {
405  this->p = allocator_.allocate(this->n);
406  new (this->p)B[this->n];
407  } else
408  {
409  this->n = 0;
410  this->p = 0;
411  }
412  }
413 
416  {
417  // allocate memory with same size as a
418  this->n = a.n;
419 
420  if (this->n>0) {
421  this->p = allocator_.allocate(this->n);
422  new (this->p)B[this->n];
423  } else
424  {
425  this->n = 0;
426  this->p = 0;
427  }
428 
429  // and copy elements
430  for (size_type i=0; i<this->n; i++) this->p[i]=a.p[i];
431  }
432 
435  {
436  if (this->n>0) {
437  int i=this->n;
438  while (i)
439  this->p[--i].~B();
440  allocator_.deallocate(this->p,this->n);
441  }
442  }
443 
445  void resize (size_type _n)
446  {
447  if (this->n==_n) return;
448 
449  if (this->n>0) {
450  int i=this->n;
451  while (i)
452  this->p[--i].~B();
453  allocator_.deallocate(this->p,this->n);
454  }
455  this->n = _n;
456  if (this->n>0) {
457  this->p = allocator_.allocate(this->n);
458  new (this->p)B[this->n];
459  } else
460  {
461  this->n = 0;
462  this->p = 0;
463  }
464  }
465 
467  base_array& operator= (const base_array& a)
468  {
469  if (&a!=this) // check if this and a are different objects
470  {
471  // adjust size of array
472  if (this->n!=a.n) // check if size is different
473  {
474  if (this->n>0) {
475  int i=this->n;
476  while (i)
477  this->p[--i].~B();
478  allocator_.deallocate(this->p,this->n); // delete old memory
479  }
480  this->n = a.n;
481  if (this->n>0) {
482  this->p = allocator_.allocate(this->n);
483  new (this->p)B[this->n];
484  } else
485  {
486  this->n = 0;
487  this->p = 0;
488  }
489  }
490  // copy data
491  for (size_type i=0; i<this->n; i++) this->p[i]=a.p[i];
492  }
493  return *this;
494  }
495 
496  protected:
497 
498  A allocator_;
499  };
500 
501 
502 
503 
525  template<class B, class A=std::allocator<B> >
527  {
528  public:
529 
530  //===== type definitions and constants
531 
533  typedef B member_type;
534 
536  typedef A allocator_type;
537 
539  typedef typename A::size_type size_type;
540 
541  //===== access to components
542 
544  B& operator[] (size_type i)
545  {
546  const size_type* lb = std::lower_bound(j, j+n, i);
547  if (lb == j+n || *lb != i)
548  DUNE_THROW(ISTLError,"index "<<i<<" not in compressed array");
549  return p[lb-j];
550  }
551 
553  const B& operator[] (size_type i) const
554  {
555  const size_type* lb = std::lower_bound(j, j+n, i);
556  if (lb == j+n || *lb != i)
557  DUNE_THROW(ISTLError,"index "<<i<<" not in compressed array");
558  return p[lb-j];
559  }
560 
562  template<class T>
564  : public BidirectionalIteratorFacade<RealIterator<T>, T>
565  {
566  public:
568  typedef typename std::remove_const<T>::type ValueType;
569 
570  friend class BidirectionalIteratorFacade<RealIterator<const ValueType>, const ValueType>;
571  friend class BidirectionalIteratorFacade<RealIterator<ValueType>, ValueType>;
572  friend class RealIterator<const ValueType>;
573  friend class RealIterator<ValueType>;
574 
577  : p(0), j(0), i(0)
578  {}
579 
581  RealIterator (B* _p, size_type* _j, size_type _i)
582  : p(_p), j(_j), i(_i)
583  { }
584 
589  : p(it.p), j(it.j), i(it.i)
590  {}
591 
592 
594  bool equals (const RealIterator<ValueType>& it) const
595  {
596  assert(p==it.p);
597  return (i)==(it.i);
598  }
599 
601  bool equals (const RealIterator<const ValueType>& it) const
602  {
603  assert(p==it.p);
604  return (i)==(it.i);
605  }
606 
607 
609  size_type index () const
610  {
611  return j[i];
612  }
613 
615  void setindex (size_type k)
616  {
617  return j[i] = k;
618  }
619 
627  size_type offset () const
628  {
629  return i;
630  }
631 
632  private:
634  void increment()
635  {
636  ++i;
637  }
638 
640  void decrement()
641  {
642  --i;
643  }
644 
646  B& dereference () const
647  {
648  return p[i];
649  }
650 
651  B* p;
652  size_type* j;
653  size_type i;
654  };
655 
658 
660  iterator begin ()
661  {
662  return iterator(p,j,0);
663  }
664 
666  iterator end ()
667  {
668  return iterator(p,j,n);
669  }
670 
673  iterator beforeEnd ()
674  {
675  return iterator(p,j,n-1);
676  }
677 
680  iterator beforeBegin ()
681  {
682  return iterator(p,j,-1);
683  }
684 
686  iterator find (size_type i)
687  {
688  const size_type* lb = std::lower_bound(j, j+n, i);
689  return (lb != j+n && *lb == i)
690  ? iterator(p,j,lb-j)
691  : end();
692  }
693 
696 
698  const_iterator begin () const
699  {
700  return const_iterator(p,j,0);
701  }
702 
704  const_iterator end () const
705  {
706  return const_iterator(p,j,n);
707  }
708 
711  const_iterator beforeEnd () const
712  {
713  return const_iterator(p,j,n-1);
714  }
715 
718  const_iterator beforeBegin () const
719  {
720  return const_iterator(p,j,-1);
721  }
722 
724  const_iterator find (size_type i) const
725  {
726  const size_type* lb = std::lower_bound(j, j+n, i);
727  return (lb != j+n && *lb == i)
728  ? const_iterator(p,j,lb-j)
729  : end();
730  }
731 
732  //===== sizes
733 
735  size_type size () const
736  {
737  return n;
738  }
739 
740  protected:
743  : n(0), p(0), j(0)
744  {}
745 
746  size_type n; // number of elements in array
747  B *p; // pointer to dynamically allocated built-in array
748  size_type* j; // the index set
749  };
750 
751 } // end namespace
752 
753 #endif
base_array()
makes empty array
Definition: basearray.hh:396
std::ptrdiff_t distanceTo(const RealIterator &o) const
Definition: basearray.hh:128
base_array_window()
makes empty array
Definition: basearray.hh:305
iterator beforeBegin()
Definition: basearray.hh:192
base_array_window(B *_p, size_type _n)
make array from given pointer and size
Definition: basearray.hh:310
bool equals(const RealIterator< const ValueType > &it) const
equality
Definition: basearray.hh:601
base_array_unmanaged< B, A >::iterator iterator
make iterators available as types
Definition: basearray.hh:291
size_type n
Definition: basearray.hh:256
size_type offset() const
offset from the first entry.
Definition: basearray.hh:627
A simple array container with non-consecutive index set.
Definition: basearray.hh:526
iterator end()
end iterator
Definition: basearray.hh:178
void advance(difference_type newsize)
advance pointer by newsize elements and then set size to new size
Definition: basearray.hh:324
const_iterator find(size_type i) const
random access returning iterator (end if not contained)
Definition: basearray.hh:233
Iterator implementation class.
Definition: basearray.hh:84
RealIterator(const B *_p, B *_i)
Definition: basearray.hh:101
base_array_unmanaged< B, A >::size_type size_type
The type used for the index access.
Definition: basearray.hh:388
const_iterator begin() const
begin const_iterator
Definition: basearray.hh:207
RealIterator(const RealIterator< ValueType > &it)
Copy constructor from mutable iterator.
Definition: basearray.hh:588
A::size_type size_type
the type for the index access
Definition: basearray.hh:59
B * p
Definition: basearray.hh:747
B member_type
export the type representing the components
Definition: basearray.hh:376
RealIterator< const B > const_iterator
const_iterator class for sequential access
Definition: basearray.hh:695
std::remove_const< T >::type ValueType
The unqualified value type.
Definition: basearray.hh:568
RealIterator< B > iterator
The iterator type.
Definition: basearray.hh:657
const_iterator beforeEnd() const
Definition: basearray.hh:220
This container extends base_array_unmanaged by memory management with the usual copy semantics provid...
Definition: basearray.hh:369
B * getptr()
return the pointer
Definition: basearray.hh:344
RealIterator(const RealIterator< ValueType > &it)
Definition: basearray.hh:104
const_iterator beforeEnd() const
Definition: basearray.hh:711
const_iterator end() const
end const_iterator
Definition: basearray.hh:213
size_type index() const
return index corresponding to pointer
Definition: basearray.hh:609
compressed_base_array_unmanaged()
makes empty array
Definition: basearray.hh:742
RealIterator(B *_p, size_type *_j, size_type _i)
constructor
Definition: basearray.hh:581
base_array_unmanaged< B, A >::iterator iterator
make iterators available as types
Definition: basearray.hh:382
void move(difference_type offset)
increment pointer by offset, leave size
Definition: basearray.hh:338
iterator beforeBegin()
Definition: basearray.hh:680
size_type * j
Definition: basearray.hh:748
RealIterator< const B > const_iterator
iterator class for sequential access
Definition: basearray.hh:204
size_type index() const
return index
Definition: basearray.hh:109
void setindex(size_type k)
Set index corresponding to pointer.
Definition: basearray.hh:615
A allocator_type
export the allocator type
Definition: basearray.hh:56
const_iterator begin() const
begin const_iterator
Definition: basearray.hh:698
bool equals(const RealIterator< ValueType > &it) const
equality
Definition: basearray.hh:594
bool equals(const RealIterator< ValueType > &other) const
equality
Definition: basearray.hh:115
Definition: basearray.hh:19
base_array_unmanaged(size_type n_, B *p_)
make an initialized array
Definition: basearray.hh:253
void move(difference_type offset, size_type newsize)
increment pointer by offset and set size
Definition: basearray.hh:331
iterator begin()
begin iterator
Definition: basearray.hh:660
base_array(const base_array &a)
copy constructor
Definition: basearray.hh:415
B member_type
export the type representing the components
Definition: basearray.hh:533
B * p
Definition: basearray.hh:257
iterator find(size_type i)
random access returning iterator (end if not contained)
Definition: basearray.hh:198
const_iterator beforeBegin() const
Definition: basearray.hh:227
base_array_unmanaged< B, A >::const_iterator const_iterator
make iterators available as types
Definition: basearray.hh:294
iterator beforeEnd()
Definition: basearray.hh:673
~base_array()
free dynamic memory
Definition: basearray.hh:434
iterator begin()
begin iterator
Definition: basearray.hh:172
A::difference_type difference_type
The type used for the difference between two iterator positions.
Definition: basearray.hh:391
base_array_unmanaged< B, A >::size_type size_type
The type used for the index access.
Definition: basearray.hh:297
B & operator[](size_type i)
random access to blocks
Definition: basearray.hh:65
A simple array container for objects of type B.
Definition: basearray.hh:46
const_iterator end() const
end const_iterator
Definition: basearray.hh:704
size_type n
Definition: basearray.hh:746
iterator beforeEnd()
Definition: basearray.hh:185
base_array_unmanaged()
makes empty array
Definition: basearray.hh:249
size_type size() const
number of blocks in the array (are of size 1 here)
Definition: basearray.hh:242
B member_type
export the type representing the components
Definition: basearray.hh:285
base_array_unmanaged< B, A >::const_iterator const_iterator
make iterators available as types
Definition: basearray.hh:385
iterator find(size_type i)
random access returning iterator (end if not contained)
Definition: basearray.hh:686
A::difference_type difference_type
The type used for the difference between two iterator positions.
Definition: basearray.hh:300
RealIterator< B > iterator
iterator type for sequential access
Definition: basearray.hh:168
A::size_type size_type
The type used for the index access.
Definition: basearray.hh:539
void resize(size_type _n)
reallocate array to given size, any data is lost
Definition: basearray.hh:445
size_type size() const
number of blocks in the array (are of size 1 here)
Definition: basearray.hh:735
RealIterator()
constructor
Definition: basearray.hh:576
iterator class for sequential access
Definition: basearray.hh:563
std::remove_const< T >::type ValueType
The unqualified value type.
Definition: basearray.hh:89
RealIterator()
constructor
Definition: basearray.hh:97
bool equals(const RealIterator< const ValueType > &other) const
equality
Definition: basearray.hh:122
derive error class from the base class in common
Definition: istlexception.hh:16
Extend base_array_unmanaged by functions to manipulate.
Definition: basearray.hh:278
iterator end()
end iterator
Definition: basearray.hh:666
B member_type
export the type representing the components
Definition: basearray.hh:53
const_iterator find(size_type i) const
random access returning iterator (end if not contained)
Definition: basearray.hh:724
const_iterator beforeBegin() const
Definition: basearray.hh:718
base_array(size_type _n)
make array with _n components
Definition: basearray.hh:401