dune-istl  2.2.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_BASEARRAY_HH
4 #define DUNE_BASEARRAY_HH
5 
6 #include "assert.h"
7 #include<cmath>
8 #include<complex>
9 #include<cstddef>
10 #include<memory>
11 
12 #include "istlexception.hh"
13 #include <dune/common/iteratorfacades.hh>
14 
19 namespace Dune {
20 
39  template<class B, class A=std::allocator<B> >
41  {
42  public:
43 
44  //===== type definitions and constants
45 
47  typedef B member_type;
48 
50  typedef A allocator_type;
51 
53  typedef typename A::size_type size_type;
54 
55 
56  //===== access to components
57 
60  {
61 #ifdef DUNE_ISTL_WITH_CHECKING
62  if (i>=n) DUNE_THROW(ISTLError,"index out of range");
63 #endif
64  return p[i];
65  }
66 
68  const B& operator[] (size_type i) const
69  {
70 #ifdef DUNE_ISTL_WITH_CHECKING
71  if (i>=n) DUNE_THROW(ISTLError,"index out of range");
72 #endif
73  return p[i];
74  }
75 
77  template<class T>
78  class RealIterator
79  : public RandomAccessIteratorFacade<RealIterator<T>, T>
80  {
81  public:
83  typedef typename remove_const<T>::type ValueType;
84 
85  friend class RandomAccessIteratorFacade<RealIterator<const ValueType>, const ValueType>;
86  friend class RandomAccessIteratorFacade<RealIterator<ValueType>, ValueType>;
87  friend class RealIterator<const ValueType>;
88  friend class RealIterator<ValueType>;
89 
92  : p(0), i(0)
93  {}
94 
95  RealIterator (const B* _p, B* _i) : p(_p), i(_i)
96  { }
97 
99  : p(it.p), i(it.i)
100  {}
101 
103  size_type index () const
104  {
105  return i-p;
106  }
107 
109  bool equals (const RealIterator<ValueType>& other) const
110  {
111  assert(other.p==p);
112  return i==other.i;
113  }
114 
116  bool equals (const RealIterator<const ValueType>& other) const
117  {
118  assert(other.p==p);
119  return i==other.i;
120  }
121 
122  std::ptrdiff_t distanceTo(const RealIterator& o) const
123  {
124  return o.i-i;
125  }
126 
127  private:
129  void increment()
130  {
131  ++i;
132  }
133 
135  void decrement()
136  {
137  --i;
138  }
139 
141  B& dereference () const
142  {
143  return *i;
144  }
145 
146  void advance(std::ptrdiff_t d)
147  {
148  i+=d;
149  }
150 
151  const B* p;
152  B* i;
153  };
154 
156  typedef RealIterator<B> iterator;
157 
158 
161  {
162  return iterator(p,p);
163  }
164 
167  {
168  return iterator(p,p+n);
169  }
170 
174  {
175  return iterator(p,p+n-1);
176  }
177 
181  {
182  return iterator(p,p-1);
183  }
184 
187  {
188  if (i<n)
189  return iterator(p,p+i);
190  else
191  return iterator(p,p+n);
192  }
193 
195  typedef RealIterator<const B> const_iterator;
196 
199  {
200  return const_iterator(p,p+0);
201  }
202 
205  {
206  return const_iterator(p,p+n);
207  }
208 
212  {
213  return const_iterator(p,p+n-1);
214  }
215 
219  {
220  return const_iterator(p,p-1);
221  }
222 
225  {
226  if (i<n)
227  return const_iterator(p,p+i);
228  else
229  return const_iterator(p,p+n);
230  }
231 
232 
233  //===== sizes
234 
236  size_type size () const
237  {
238  return n;
239  }
240 
241  protected:
244  : n(0), p(0)
245  {}
248  : n(n_), p(p_)
249  {}
250  size_type n; // number of elements in array
251  B *p; // pointer to dynamically allocated built-in array
252  };
253 
254 
255 
270  template<class B, class A=std::allocator<B> >
272  {
273  public:
274 
275  //===== type definitions and constants
276 
278  typedef B member_type;
279 
281  typedef A allocator_type;
282 
285 
288 
291 
293  typedef typename A::difference_type difference_type;
294 
295  //===== constructors and such
296 
299  : base_array_unmanaged<B,A>()
300  { }
301 
304  : base_array_unmanaged<B,A>(_n ,_p)
305  {}
306 
307  //===== window manipulation methods
308 
310  void set (size_type _n, B* _p)
311  {
312  this->n = _n;
313  this->p = _p;
314  }
315 
317  void advance (difference_type newsize)
318  {
319  this->p += this->n;
320  this->n = newsize;
321  }
322 
324  void move (difference_type offset, size_type newsize)
325  {
326  this->p += offset;
327  this->n = newsize;
328  }
329 
331  void move (difference_type offset)
332  {
333  this->p += offset;
334  }
335 
337  B* getptr ()
338  {
339  return this->p;
340  }
341  };
342 
343 
344 
360  template<class B, class A=std::allocator<B> >
361  class base_array : public base_array_unmanaged<B,A>
362  {
363  public:
364 
365  //===== type definitions and constants
366 
368  typedef B member_type;
369 
371  typedef A allocator_type;
372 
375 
378 
381 
383  typedef typename A::difference_type difference_type;
384 
385  //===== constructors and such
386 
389  : base_array_unmanaged<B,A>()
390  {}
391 
394  : base_array_unmanaged<B,A>(_n, 0)
395  {
396  if (this->n>0) {
397  this->p = allocator_.allocate(this->n);
398  new (this->p) B[this->n];
399  } else
400  {
401  this->n = 0;
402  this->p = 0;
403  }
404  }
405 
408  {
409  // allocate memory with same size as a
410  this->n = a.n;
411 
412  if (this->n>0) {
413  this->p = allocator_.allocate(this->n);
414  new (this->p) B[this->n];
415  } else
416  {
417  this->n = 0;
418  this->p = 0;
419  }
420 
421  // and copy elements
422  for (size_type i=0; i<this->n; i++) this->p[i]=a.p[i];
423  }
424 
427  {
428  const base_array& a = static_cast<const base_array&>(_a);
429 
430  // allocate memory with same size as a
431  this->n = a.n;
432  if (this->n>0) {
433  this->p = allocator_.allocate(this->n);
434  new (this->p) B[this->n];
435  } else
436  {
437  this->n = 0;
438  this->p = 0;
439  }
440 
441  // and copy elements
442  for (size_type i=0; i<this->n; i++) this->p[i]=a.p[i];
443  }
444 
445 
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  }
456 
458  void resize (size_type _n)
459  {
460  if (this->n==_n) return;
461 
462  if (this->n>0) {
463  int i=this->n;
464  while (i)
465  this->p[--i].~B();
466  allocator_.deallocate(this->p,this->n);
467  }
468  this->n = _n;
469  if (this->n>0) {
470  this->p = allocator_.allocate(this->n);
471  new (this->p) B[this->n];
472  } else
473  {
474  this->n = 0;
475  this->p = 0;
476  }
477  }
478 
481  {
482  if (&a!=this) // check if this and a are different objects
483  {
484  // adjust size of array
485  if (this->n!=a.n) // check if size is different
486  {
487  if (this->n>0) {
488  int i=this->n;
489  while (i)
490  this->p[--i].~B();
491  allocator_.deallocate(this->p,this->n); // delete old memory
492  }
493  this->n = a.n;
494  if (this->n>0) {
495  this->p = allocator_.allocate(this->n);
496  new (this->p) B[this->n];
497  } else
498  {
499  this->n = 0;
500  this->p = 0;
501  }
502  }
503  // copy data
504  for (size_type i=0; i<this->n; i++) this->p[i]=a.p[i];
505  }
506  return *this;
507  }
508 
511  {
512  return this->operator=(static_cast<const base_array&>(a));
513  }
514 
515  protected:
516 
518  };
519 
520 
521 
522 
542  template<class B, class A=std::allocator<B> >
544  {
545  public:
546 
547  //===== type definitions and constants
548 
550  typedef B member_type;
551 
553  typedef A allocator_type;
554 
556  typedef typename A::size_type size_type;
557 
558  //===== access to components
559 
562  {
563  size_type l=0, r=n-1;
564  while (l<r)
565  {
566  size_type q = (l+r)/2;
567  if (i <= j[q]) r=q;
568  else l = q+1;
569  }
570  if (j[l]!=i){
571  DUNE_THROW(ISTLError,"index "<<i<<" not in compressed array");
572  }
573  return p[l];
574  }
575 
577  const B& operator[] (size_type i) const
578  {
579  size_type l=0, r=n-1;
580  while (l<r)
581  {
582  size_type q = (l+r)/2;
583  if (i <= j[q]) r=q;
584  else l = q+1;
585  }
586  if (j[l]!=i){
587  DUNE_THROW(ISTLError,"index "<<i<<" not in compressed array");
588  }
589  return p[l];
590  }
591 
593  template<class T>
595  : public BidirectionalIteratorFacade<RealIterator<T>, T>
596  {
597  public:
600 
601  friend class BidirectionalIteratorFacade<RealIterator<const ValueType>, const ValueType>;
602  friend class BidirectionalIteratorFacade<RealIterator<ValueType>, ValueType>;
603  friend class RealIterator<const ValueType>;
604  friend class RealIterator<ValueType>;
605 
608  : p(0), j(0), i(0)
609  {}
610 
612  RealIterator (B* _p, size_type* _j, size_type _i)
613  : p(_p), j(_j), i(_i)
614  { }
615 
620  : p(it.p), j(it.j), i(it.i)
621  {}
622 
623 
625  bool equals (const RealIterator<ValueType>& it) const
626  {
627  assert(p==it.p);
628  return (i)==(it.i);
629  }
630 
632  bool equals (const RealIterator<const ValueType>& it) const
633  {
634  assert(p==it.p);
635  return (i)==(it.i);
636  }
637 
638 
640  size_type index () const
641  {
642  return j[i];
643  }
644 
647  {
648  return j[i] = k;
649  }
650 
658  size_type offset () const
659  {
660  return i;
661  }
662 
663  private:
665  void increment()
666  {
667  ++i;
668  }
669 
671  void decrement()
672  {
673  --i;
674  }
675 
677  B& dereference () const
678  {
679  return p[i];
680  }
681 
682  B* p;
683  size_type* j;
684  size_type i;
685  };
686 
689 
692  {
693  return iterator(p,j,0);
694  }
695 
698  {
699  return iterator(p,j,n);
700  }
701 
705  {
706  return iterator(p,j,n-1);
707  }
708 
712  {
713  return iterator(p,j,-1);
714  }
715 
718  {
719  size_type l=0, r=n-1;
720  while (l<r)
721  {
722  size_type q = (l+r)/2;
723  if (i <= j[q]) r=q;
724  else l = q+1;
725  }
726 
727  if (n && i==j[l])
728  return iterator(p,j,l);
729  else
730  return iterator(p,j,n);
731  }
732 
735 
738  {
739  return const_iterator(p,j,0);
740  }
741 
744  {
745  return const_iterator(p,j,n);
746  }
747 
751  {
752  return const_iterator(p,j,n-1);
753  }
754 
758  {
759  return const_iterator(p,j,-1);
760  }
761 
764  {
765  size_type l=0, r=n-1;
766  while (l<r)
767  {
768  size_type q = (l+r)/2;
769  if (i <= j[q]) r=q;
770  else l = q+1;
771  }
772 
773  if (n && i==j[l])
774  return const_iterator(p,j,l);
775  else
776  return const_iterator(p,j,n);
777  }
778 
779  //===== sizes
780 
782  size_type size () const
783  {
784  return n;
785  }
786 
787  protected:
790  : n(0), p(0), j(0)
791  {}
792 
793  size_type n; // number of elements in array
794  B *p; // pointer to dynamically allocated built-in array
795  size_type* j; // the index set
796  };
797 
798 } // end namespace
799 
800 #endif