MFEM  v3.4
Finite element discretization library
array.hpp
Go to the documentation of this file.
1 // Copyright (c) 2010, Lawrence Livermore National Security, LLC. Produced at
2 // the Lawrence Livermore National Laboratory. LLNL-CODE-443211. All Rights
3 // reserved. See file COPYRIGHT for details.
4 //
5 // This file is part of the MFEM library. For more information and source code
6 // availability see http://mfem.org.
7 //
8 // MFEM is free software; you can redistribute it and/or modify it under the
9 // terms of the GNU Lesser General Public License (as published by the Free
10 // Software Foundation) version 2.1 dated February 1999.
11 
12 #ifndef MFEM_ARRAY
13 #define MFEM_ARRAY
14 
15 #include "../config/config.hpp"
16 #include "error.hpp"
17 #include "globals.hpp"
18 
19 #include <iostream>
20 #include <cstdlib>
21 #include <cstring>
22 #include <algorithm>
23 
24 namespace mfem
25 {
26 
27 /// Base class for array container.
28 class BaseArray
29 {
30 protected:
31  /// Pointer to data
32  void *data;
33  /// Size of the array
34  int size;
35  /// Size of the allocated memory
36  int allocsize;
37  /** Increment of allocated memory on overflow,
38  inc = 0 doubles the array */
39  int inc;
40 
41  BaseArray() { }
42  /// Creates array of asize elements of size elementsize
43  BaseArray(int asize, int ainc, int elmentsize);
44  /// Free the allocated memory
45  ~BaseArray();
46  /** Increases the allocsize of the array to be at least minsize.
47  The current content of the array is copied to the newly allocated
48  space. minsize must be > abs(allocsize). */
49  void GrowSize(int minsize, int elementsize);
50 };
51 
52 template <class T>
53 class Array;
54 
55 template <class T>
56 void Swap(Array<T> &, Array<T> &);
57 
58 /**
59  Abstract data type Array.
60 
61  Array<T> is an automatically increasing array containing elements of the
62  generic type T. The allocated size may be larger then the logical size
63  of the array.
64  The elements can be accessed by the [] operator, the range is 0 to size-1.
65 */
66 template <class T>
67 class Array : public BaseArray
68 {
69 public:
70  friend void Swap<T>(Array<T> &, Array<T> &);
71 
72  /// Creates array of asize elements
73  explicit inline Array(int asize = 0, int ainc = 0)
74  : BaseArray(asize, ainc, sizeof (T)) { }
75 
76  /** Creates array using an existing c-array of asize elements;
77  allocsize is set to -asize to indicate that the data will not
78  be deleted. */
79  inline Array(T *_data, int asize, int ainc = 0)
80  { data = _data; size = asize; allocsize = -asize; inc = ainc; }
81 
82  /// Copy constructor: deep copy
83  Array(const Array<T> &src)
84  : BaseArray(src.size, 0, sizeof(T))
85  { std::memcpy(data, src.data, size*sizeof(T)); }
86 
87  /// Copy constructor (deep copy) from an Array of convertable type
88  template <typename CT>
89  Array(const Array<CT> &src)
90  : BaseArray(src.Size(), 0, sizeof(T))
91  { for (int i = 0; i < size; i++) { (*this)[i] = T(src[i]); } }
92 
93  /// Destructor
94  inline ~Array() { }
95 
96  /// Assignment operator: deep copy
97  Array<T> &operator=(const Array<T> &src) { src.Copy(*this); return *this; }
98 
99  /// Assignment operator (deep copy) from an Array of convertable type
100  template <typename CT>
102  {
103  SetSize(src.Size());
104  for (int i = 0; i < size; i++) { (*this)[i] = T(src[i]); }
105  return *this;
106  }
107 
108  /// Return the data as 'T *'
109  inline operator T *() { return (T *)data; }
110 
111  /// Return the data as 'const T *'
112  inline operator const T *() const { return (const T *)data; }
113 
114  /// Returns the data
115  inline T *GetData() { return (T *)data; }
116  /// Returns the data
117  inline const T *GetData() const { return (T *)data; }
118 
119  /// Return true if the data will be deleted by the array
120  inline bool OwnsData() const { return (allocsize > 0); }
121 
122  /// Changes the ownership of the data
123  inline void StealData(T **p)
124  { *p = (T*)data; data = 0; size = allocsize = 0; }
125 
126  /// NULL-ifies the data
127  inline void LoseData() { data = 0; size = allocsize = 0; }
128 
129  /// Make the Array own the data
130  void MakeDataOwner() { allocsize = abs(allocsize); }
131 
132  /// Logical size of the array
133  inline int Size() const { return size; }
134 
135  /// Change logical size of the array, keep existing entries
136  inline void SetSize(int nsize);
137 
138  /// Same as SetSize(int) plus initialize new entries with 'initval'
139  inline void SetSize(int nsize, const T &initval);
140 
141  /** Maximum number of entries the array can store without allocating more
142  memory. */
143  inline int Capacity() const { return abs(allocsize); }
144 
145  /// Ensures that the allocated size is at least the given size.
146  inline void Reserve(int capacity)
147  { if (capacity > abs(allocsize)) { GrowSize(capacity, sizeof(T)); } }
148 
149  /// Access element
150  inline T & operator[](int i);
151 
152  /// Access const element
153  inline const T &operator[](int i) const;
154 
155  /// Append element to array, resize if necessary
156  inline int Append(const T & el);
157 
158  /// Append another array to this array, resize if necessary
159  inline int Append(const T *els, int nels);
160 
161  /// Append another array to this array, resize if necessary
162  inline int Append(const Array<T> &els) { return Append(els, els.Size()); }
163 
164  /// Prepend an element to the array, resize if necessary
165  inline int Prepend(const T &el);
166 
167  /// Return the last element in the array
168  inline T &Last();
169  inline const T &Last() const;
170 
171  /// Append element when it is not yet in the array, return index
172  inline int Union(const T & el);
173 
174  /// Return the first index where 'el' is found; return -1 if not found
175  inline int Find(const T &el) const;
176 
177  /// Do bisection search for 'el' in a sorted array; return -1 if not found.
178  inline int FindSorted(const T &el) const;
179 
180  /// Delete the last entry
181  inline void DeleteLast() { if (size > 0) { size--; } }
182 
183  /// Delete the first 'el' entry
184  inline void DeleteFirst(const T &el);
185 
186  /// Delete whole array
187  inline void DeleteAll();
188 
189  /// Create a copy of the current array
190  inline void Copy(Array &copy) const
191  {
192  copy.SetSize(Size());
193  std::memcpy(copy.GetData(), data, Size()*sizeof(T));
194  }
195 
196  /// Make this Array a reference to a pointer
197  inline void MakeRef(T *, int);
198 
199  /// Make this Array a reference to 'master'
200  inline void MakeRef(const Array &master);
201 
202  inline void GetSubArray(int offset, int sa_size, Array<T> &sa);
203 
204  /// Prints array to stream with width elements per row
205  void Print(std::ostream &out = mfem::out, int width = 4) const;
206 
207  /** @brief Save the Array to the stream @a out using the format @a fmt.
208  The format @a fmt can be:
209 
210  0 - write the size followed by all entries
211  1 - write only the entries
212  */
213  void Save(std::ostream &out, int fmt = 0) const;
214 
215  /** @brief Read an Array from the stream @a in using format @a fmt.
216  The format @a fmt can be:
217 
218  0 - read the size then the entries
219  1 - read Size() entries
220  */
221  void Load(std::istream &in, int fmt = 0);
222 
223  /** @brief Set the Array size to @a new_size and read that many entries from
224  the stream @a in. */
225  void Load(int new_size, std::istream &in)
226  { SetSize(new_size); Load(in, 1); }
227 
228  /** @brief Find the maximal element in the array, using the comparison
229  operator `<` for class T. */
230  T Max() const;
231 
232  /** @brief Find the minimal element in the array, using the comparison
233  operator `<` for class T. */
234  T Min() const;
235 
236  /// Sorts the array. This requires operator< to be defined for T.
237  void Sort() { std::sort((T*) data, (T*) data + size); }
238 
239  /// Sorts the array using the supplied comparison function object.
240  template<class Compare>
241  void Sort(Compare cmp) { std::sort((T*) data, (T*) data + size, cmp); }
242 
243  /** Removes duplicities from a sorted array. This requires operator== to be
244  defined for T. */
245  void Unique()
246  {
247  T* end = std::unique((T*) data, (T*) data + size);
248  SetSize(end - (T*) data);
249  }
250 
251  /// return true if the array is sorted.
252  int IsSorted();
253 
254  /// Partial Sum
255  void PartialSum();
256 
257  /// Sum all entries
258  T Sum();
259 
260  inline void operator=(const T &a);
261 
262  /// Copy data from a pointer. Size() elements are copied.
263  inline void Assign(const T *);
264 
265  // STL-like begin/end
266  inline T* begin() const { return (T*) data; }
267  inline T* end() const { return (T*) data + size; }
268 
269  long MemoryUsage() const { return Capacity() * sizeof(T); }
270 };
271 
272 template <class T>
273 inline bool operator==(const Array<T> &LHS, const Array<T> &RHS)
274 {
275  if ( LHS.Size() != RHS.Size() ) { return false; }
276  for (int i=0; i<LHS.Size(); i++)
277  if ( LHS[i] != RHS[i] ) { return false; }
278  return true;
279 }
280 
281 template <class T>
282 inline bool operator!=(const Array<T> &LHS, const Array<T> &RHS)
283 {
284  return !( LHS == RHS );
285 }
286 
287 
288 template <class T>
289 class Array2D;
290 
291 template <class T>
292 void Swap(Array2D<T> &, Array2D<T> &);
293 
294 /// Dynamic 2D array using row-major layout
295 template <class T>
296 class Array2D
297 {
298 private:
299  friend void Swap<T>(Array2D<T> &, Array2D<T> &);
300 
301  Array<T> array1d;
302  int M, N; // number of rows and columns
303 
304 public:
305  Array2D() { M = N = 0; }
306  Array2D(int m, int n) : array1d(m*n) { M = m; N = n; }
307 
308  void SetSize(int m, int n) { array1d.SetSize(m*n); M = m; N = n; }
309 
310  int NumRows() const { return M; }
311  int NumCols() const { return N; }
312 
313  inline const T &operator()(int i, int j) const;
314  inline T &operator()(int i, int j);
315 
316  inline const T *operator[](int i) const;
317  inline T *operator[](int i);
318 
319  const T *operator()(int i) const { return (*this)[i]; }
320  T *operator()(int i) { return (*this)[i]; }
321 
322  const T *GetRow(int i) const { return (*this)[i]; }
323  T *GetRow(int i) { return (*this)[i]; }
324 
325  /// Extract a copy of the @a i-th row into the Array @a sa.
326  void GetRow(int i, Array<T> &sa) const
327  {
328  sa.SetSize(N);
329  sa.Assign(GetRow(i));
330  }
331 
332  /** @brief Save the Array2D to the stream @a out using the format @a fmt.
333  The format @a fmt can be:
334 
335  0 - write the number of rows and columns, followed by all entries
336  1 - write only the entries, using row-major layout
337  */
338  void Save(std::ostream &out, int fmt = 0) const
339  {
340  if (fmt == 0) { out << NumRows() << ' ' << NumCols() << '\n'; }
341  array1d.Save(out, 1);
342  }
343 
344  /** @brief Read an Array2D from the stream @a in using format @a fmt.
345  The format @a fmt can be:
346 
347  0 - read the number of rows and columns, then the entries
348  1 - read NumRows() x NumCols() entries, using row-major layout
349  */
350  void Load(std::istream &in, int fmt = 0)
351  {
352  if (fmt == 0) { in >> M >> N; array1d.SetSize(M*N); }
353  array1d.Load(in, 1);
354  }
355 
356  /// Read an Array2D from a file
357  void Load(const char *filename, int fmt = 0);
358 
359  /** @brief Set the Array2D dimensions to @a new_size0 x @a new_size1 and read
360  that many entries from the stream @a in. */
361  void Load(int new_size0,int new_size1, std::istream &in)
362  { SetSize(new_size0,new_size1); Load(in, 1); }
363 
364  void Copy(Array2D &copy) const
365  { copy.M = M; copy.N = N; array1d.Copy(copy.array1d); }
366 
367  inline void operator=(const T &a)
368  { array1d = a; }
369 
370  /// Make this Array a reference to 'master'
371  inline void MakeRef(const Array2D &master)
372  { M = master.M; N = master.N; array1d.MakeRef(master.array1d); }
373 
374  /// Delete all dynamically allocated memory, reseting all dimentions to zero.
375  inline void DeleteAll() { M = 0; N = 0; array1d.DeleteAll(); }
376 
377  /// Prints array to stream with width elements per row
378  void Print(std::ostream &out = mfem::out, int width = 4);
379 };
380 
381 
382 template <class T>
383 class Array3D
384 {
385 private:
386  Array<T> array1d;
387  int N2, N3;
388 
389 public:
390  Array3D() { N2 = N3 = 0; }
391  Array3D(int n1, int n2, int n3)
392  : array1d(n1*n2*n3) { N2 = n2; N3 = n3; }
393 
394  void SetSize(int n1, int n2, int n3)
395  { array1d.SetSize(n1*n2*n3); N2 = n2; N3 = n3; }
396 
397  inline const T &operator()(int i, int j, int k) const;
398  inline T &operator()(int i, int j, int k);
399 };
400 
401 
402 /** A container for items of type T. Dynamically grows as items are added.
403  * Each item is accessible by its index. Items are allocated in larger chunks
404  * (blocks), so the 'Append' method is very fast on average.
405  */
406 template<typename T>
408 {
409 public:
410  BlockArray(int block_size = 16*1024);
411  BlockArray(const BlockArray<T> &other); // deep copy
412  ~BlockArray();
413 
414  /// Allocate and construct a new item in the array, return its index.
415  int Append();
416 
417  /// Allocate and copy-construct a new item in the array, return its index.
418  int Append(const T &item);
419 
420  /// Access item of the array.
421  inline T& At(int index)
422  {
423  CheckIndex(index);
424  return blocks[index >> shift][index & mask];
425  }
426  inline const T& At(int index) const
427  {
428  CheckIndex(index);
429  return blocks[index >> shift][index & mask];
430  }
431 
432  /// Access item of the array.
433  inline T& operator[](int index) { return At(index); }
434  inline const T& operator[](int index) const { return At(index); }
435 
436  /// Return the number of items actually stored.
437  int Size() const { return size; }
438 
439  /// Return the current capacity of the BlockArray.
440  int Capacity() const { return blocks.Size()*(mask+1); }
441 
442  void Swap(BlockArray<T> &other);
443 
444  long MemoryUsage() const;
445 
446 protected:
447  template <typename cA, typename cT>
449  {
450  public:
451  cT& operator*() const { return *ptr; }
452  cT* operator->() const { return ptr; }
453 
454  bool good() const { return !stop; }
455  int index() const { return (ptr - ref); }
456 
457  protected:
458  cA *array;
459  cT *ptr, *b_end, *ref;
461  bool stop;
462 
466  : array(a), ptr(a->blocks[0]), ref(ptr), stop(false)
467  {
468  b_end_idx = std::min(a->size, a->mask+1);
469  b_end = ptr + b_end_idx;
470  }
471 
472  void next()
473  {
474  MFEM_ASSERT(!stop, "invalid use");
475  if (++ptr == b_end)
476  {
477  if (b_end_idx < array->size)
478  {
479  ptr = &array->At(b_end_idx);
480  ref = ptr - b_end_idx;
481  b_end_idx = std::min(array->size, (b_end_idx|array->mask) + 1);
482  b_end = &array->At(b_end_idx-1) + 1;
483  }
484  else
485  {
486  MFEM_ASSERT(b_end_idx == array->size, "invalid use");
487  stop = true;
488  }
489  }
490  }
491  };
492 
493 public:
494  class iterator : public iterator_base<BlockArray, T>
495  {
496  protected:
497  friend class BlockArray;
499 
500  iterator() { }
501  iterator(bool stop) : base(stop) { }
502  iterator(BlockArray *a) : base(a) { }
503 
504  public:
505  iterator &operator++() { base::next(); return *this; }
506 
507  bool operator==(const iterator &other) const { return base::stop; }
508  bool operator!=(const iterator &other) const { return !base::stop; }
509  };
510 
511  class const_iterator : public iterator_base<const BlockArray, const T>
512  {
513  protected:
514  friend class BlockArray;
516 
519  const_iterator(const BlockArray *a) : base(a) { }
520 
521  public:
522  const_iterator &operator++() { base::next(); return *this; }
523 
524  bool operator==(const const_iterator &other) const { return base::stop; }
525  bool operator!=(const const_iterator &other) const { return !base::stop; }
526  };
527 
528  iterator begin() { return size ? iterator(this) : iterator(true); }
529  iterator end() { return iterator(); }
530 
531  const_iterator cbegin() const
532  { return size ? const_iterator(this) : const_iterator(true); }
533  const_iterator cend() const { return const_iterator(); }
534 
535 protected:
537  int size, shift, mask;
538 
539  int Alloc();
540 
541  inline void CheckIndex(int index) const
542  {
543  MFEM_ASSERT(index >= 0 && index < size,
544  "Out of bounds access: " << index << ", size = " << size);
545  }
546 };
547 
548 
549 /// inlines ///
550 
551 template <class T>
552 inline void Swap(T &a, T &b)
553 {
554  T c = a;
555  a = b;
556  b = c;
557 }
558 
559 template <class T>
560 inline void Swap(Array<T> &a, Array<T> &b)
561 {
562  Swap(a.data, b.data);
563  Swap(a.size, b.size);
564  Swap(a.allocsize, b.allocsize);
565  Swap(a.inc, b.inc);
566 }
567 
568 template <class T>
569 inline void Array<T>::SetSize(int nsize)
570 {
571  MFEM_ASSERT( nsize>=0, "Size must be non-negative. It is " << nsize );
572  if (nsize > abs(allocsize))
573  {
574  GrowSize(nsize, sizeof(T));
575  }
576  size = nsize;
577 }
578 
579 template <class T>
580 inline void Array<T>::SetSize(int nsize, const T &initval)
581 {
582  MFEM_ASSERT( nsize>=0, "Size must be non-negative. It is " << nsize );
583  if (nsize > size)
584  {
585  if (nsize > abs(allocsize))
586  {
587  GrowSize(nsize, sizeof(T));
588  }
589  for (int i = size; i < nsize; i++)
590  {
591  ((T*)data)[i] = initval;
592  }
593  }
594  size = nsize;
595 }
596 
597 template <class T>
598 inline T &Array<T>::operator[](int i)
599 {
600  MFEM_ASSERT( i>=0 && i<size,
601  "Access element " << i << " of array, size = " << size );
602  return ((T*)data)[i];
603 }
604 
605 template <class T>
606 inline const T &Array<T>::operator[](int i) const
607 {
608  MFEM_ASSERT( i>=0 && i<size,
609  "Access element " << i << " of array, size = " << size );
610  return ((T*)data)[i];
611 }
612 
613 template <class T>
614 inline int Array<T>::Append(const T &el)
615 {
616  SetSize(size+1);
617  ((T*)data)[size-1] = el;
618  return size;
619 }
620 
621 template <class T>
622 inline int Array<T>::Append(const T *els, int nels)
623 {
624  const int old_size = size;
625 
626  SetSize(size + nels);
627  for (int i = 0; i < nels; i++)
628  {
629  ((T*)data)[old_size+i] = els[i];
630  }
631  return size;
632 }
633 
634 template <class T>
635 inline int Array<T>::Prepend(const T &el)
636 {
637  SetSize(size+1);
638  for (int i = size-1; i > 0; i--)
639  {
640  ((T*)data)[i] = ((T*)data)[i-1];
641  }
642  ((T*)data)[0] = el;
643  return size;
644 }
645 
646 template <class T>
647 inline T &Array<T>::Last()
648 {
649  MFEM_ASSERT(size > 0, "Array size is zero: " << size);
650  return ((T*)data)[size-1];
651 }
652 
653 template <class T>
654 inline const T &Array<T>::Last() const
655 {
656  MFEM_ASSERT(size > 0, "Array size is zero: " << size);
657  return ((T*)data)[size-1];
658 }
659 
660 template <class T>
661 inline int Array<T>::Union(const T &el)
662 {
663  int i = 0;
664  while ((i < size) && (((T*)data)[i] != el)) { i++; }
665  if (i == size)
666  {
667  Append(el);
668  }
669  return i;
670 }
671 
672 template <class T>
673 inline int Array<T>::Find(const T &el) const
674 {
675  for (int i = 0; i < size; i++)
676  {
677  if (((T*)data)[i] == el) { return i; }
678  }
679  return -1;
680 }
681 
682 template <class T>
683 inline int Array<T>::FindSorted(const T &el) const
684 {
685  const T *begin = (const T*) data, *end = begin + size;
686  const T* first = std::lower_bound(begin, end, el);
687  if (first == end || !(*first == el)) { return -1; }
688  return first - begin;
689 }
690 
691 template <class T>
692 inline void Array<T>::DeleteFirst(const T &el)
693 {
694  for (int i = 0; i < size; i++)
695  {
696  if (((T*)data)[i] == el)
697  {
698  for (i++; i < size; i++)
699  {
700  ((T*)data)[i-1] = ((T*)data)[i];
701  }
702  size--;
703  return;
704  }
705  }
706 }
707 
708 template <class T>
709 inline void Array<T>::DeleteAll()
710 {
711  if (allocsize > 0)
712  {
713  delete [] (char*)data;
714  }
715  data = NULL;
716  size = allocsize = 0;
717 }
718 
719 template <class T>
720 inline void Array<T>::MakeRef(T *p, int s)
721 {
722  if (allocsize > 0)
723  {
724  delete [] (char*)data;
725  }
726  data = p;
727  size = s;
728  allocsize = -s;
729 }
730 
731 template <class T>
732 inline void Array<T>::MakeRef(const Array &master)
733 {
734  if (allocsize > 0)
735  {
736  delete [] (char*)data;
737  }
738  data = master.data;
739  size = master.size;
740  allocsize = -abs(master.allocsize);
741  inc = master.inc;
742 }
743 
744 template <class T>
745 inline void Array<T>::GetSubArray(int offset, int sa_size, Array<T> &sa)
746 {
747  sa.SetSize(sa_size);
748  for (int i = 0; i < sa_size; i++)
749  {
750  sa[i] = (*this)[offset+i];
751  }
752 }
753 
754 template <class T>
755 inline void Array<T>::operator=(const T &a)
756 {
757  for (int i = 0; i < size; i++)
758  {
759  ((T*)data)[i] = a;
760  }
761 }
762 
763 template <class T>
764 inline void Array<T>::Assign(const T *p)
765 {
766  memcpy(data, p, Size()*sizeof(T));
767 }
768 
769 
770 template <class T>
771 inline const T &Array2D<T>::operator()(int i, int j) const
772 {
773  MFEM_ASSERT( i>=0 && i< array1d.Size()/N && j>=0 && j<N,
774  "Array2D: invalid access of element (" << i << ',' << j
775  << ") in array of size (" << array1d.Size()/N << ',' << N
776  << ")." );
777  return array1d[i*N+j];
778 }
779 
780 template <class T>
781 inline T &Array2D<T>::operator()(int i, int j)
782 {
783  MFEM_ASSERT( i>=0 && i< array1d.Size()/N && j>=0 && j<N,
784  "Array2D: invalid access of element (" << i << ',' << j
785  << ") in array of size (" << array1d.Size()/N << ',' << N
786  << ")." );
787  return array1d[i*N+j];
788 }
789 
790 template <class T>
791 inline const T *Array2D<T>::operator[](int i) const
792 {
793  MFEM_ASSERT( i>=0 && i< array1d.Size()/N,
794  "Array2D: invalid access of row " << i << " in array with "
795  << array1d.Size()/N << " rows.");
796  return &array1d[i*N];
797 }
798 
799 template <class T>
800 inline T *Array2D<T>::operator[](int i)
801 {
802  MFEM_ASSERT( i>=0 && i< array1d.Size()/N,
803  "Array2D: invalid access of row " << i << " in array with "
804  << array1d.Size()/N << " rows.");
805  return &array1d[i*N];
806 }
807 
808 
809 template <class T>
810 inline void Swap(Array2D<T> &a, Array2D<T> &b)
811 {
812  Swap(a.array1d, b.array1d);
813  Swap(a.N, b.N);
814 }
815 
816 
817 template <class T>
818 inline const T &Array3D<T>::operator()(int i, int j, int k) const
819 {
820  MFEM_ASSERT(i >= 0 && i < array1d.Size() / N2 / N3 && j >= 0 && j < N2
821  && k >= 0 && k < N3,
822  "Array3D: invalid access of element ("
823  << i << ',' << j << ',' << k << ") in array of size ("
824  << array1d.Size() / N2 / N3 << ',' << N2 << ',' << N3 << ").");
825  return array1d[(i*N2+j)*N3+k];
826 }
827 
828 template <class T>
829 inline T &Array3D<T>::operator()(int i, int j, int k)
830 {
831  MFEM_ASSERT(i >= 0 && i < array1d.Size() / N2 / N3 && j >= 0 && j < N2
832  && k >= 0 && k < N3,
833  "Array3D: invalid access of element ("
834  << i << ',' << j << ',' << k << ") in array of size ("
835  << array1d.Size() / N2 / N3 << ',' << N2 << ',' << N3 << ").");
836  return array1d[(i*N2+j)*N3+k];
837 }
838 
839 
840 template<typename T>
842 {
843  mask = block_size-1;
844  MFEM_VERIFY(!(block_size & mask), "block_size must be a power of two.");
845 
846  size = shift = 0;
847  while ((1 << shift) < block_size) { shift++; }
848 }
849 
850 template<typename T>
852 {
853  blocks.SetSize(other.blocks.Size());
854 
855  size = other.size;
856  shift = other.shift;
857  mask = other.mask;
858 
859  int bsize = mask+1;
860  for (int i = 0; i < blocks.Size(); i++)
861  {
862  blocks[i] = (T*) new char[bsize * sizeof(T)];
863  }
864 
865  // copy all items
866  for (int i = 0; i < size; i++)
867  {
868  new (&At(i)) T(other[i]);
869  }
870 }
871 
872 template<typename T>
874 {
875  int bsize = mask+1;
876  if (size >= blocks.Size() * bsize)
877  {
878  T* new_block = (T*) new char[bsize * sizeof(T)];
879  blocks.Append(new_block);
880  }
881  return size++;
882 }
883 
884 template<typename T>
886 {
887  int index = Alloc();
888  new (&At(index)) T();
889  return index;
890 }
891 
892 template<typename T>
893 int BlockArray<T>::Append(const T &item)
894 {
895  int index = Alloc();
896  new (&At(index)) T(item);
897  return index;
898 }
899 
900 template<typename T>
902 {
903  mfem::Swap(blocks, other.blocks);
904  std::swap(size, other.size);
905  std::swap(shift, other.shift);
906  std::swap(mask, other.mask);
907 }
908 
909 template<typename T>
911 {
912  return blocks.Size()*(mask+1)*sizeof(T) +
913  blocks.MemoryUsage();
914 }
915 
916 template<typename T>
918 {
919  int bsize = size & mask;
920  for (int i = blocks.Size(); i != 0; )
921  {
922  T *block = blocks[--i];
923  for (int j = bsize; j != 0; )
924  {
925  block[--j].~T();
926  }
927  delete [] (char*) block;
928  bsize = mask+1;
929  }
930 }
931 
932 } // namespace mfem
933 
934 #endif
T Min() const
Find the minimal element in the array, using the comparison operator < for class T.
Definition: array.cpp:124
const T * GetData() const
Returns the data.
Definition: array.hpp:117
int Size() const
Return the number of items actually stored.
Definition: array.hpp:437
const_iterator(const BlockArray *a)
Definition: array.hpp:519
void Load(std::istream &in, int fmt=0)
Read an Array from the stream in using format fmt. The format fmt can be:
Definition: array.cpp:94
void Unique()
Definition: array.hpp:245
T * end() const
Definition: array.hpp:267
~BaseArray()
Free the allocated memory.
Definition: array.cpp:36
iterator_base< const BlockArray, const T > base
Definition: array.hpp:515
bool operator==(const iterator &other) const
Definition: array.hpp:507
void Save(std::ostream &out, int fmt=0) const
Save the Array2D to the stream out using the format fmt. The format fmt can be:
Definition: array.hpp:338
void * data
Pointer to data.
Definition: array.hpp:32
Array(T *_data, int asize, int ainc=0)
Definition: array.hpp:79
T * GetRow(int i)
Definition: array.hpp:323
void Load(std::istream &in, int fmt=0)
Read an Array2D from the stream in using format fmt. The format fmt can be:
Definition: array.hpp:350
void Copy(Array2D &copy) const
Definition: array.hpp:364
Base class for array container.
Definition: array.hpp:28
T * GetData()
Returns the data.
Definition: array.hpp:115
T * operator()(int i)
Definition: array.hpp:320
T * begin() const
Definition: array.hpp:266
T Max() const
Find the maximal element in the array, using the comparison operator < for class T.
Definition: array.cpp:109
void operator=(const T &a)
Definition: array.hpp:367
bool OwnsData() const
Return true if the data will be deleted by the array.
Definition: array.hpp:120
void Sort(Compare cmp)
Sorts the array using the supplied comparison function object.
Definition: array.hpp:241
T Sum()
Sum all entries.
Definition: array.cpp:152
Array(const Array< T > &src)
Copy constructor: deep copy.
Definition: array.hpp:83
void GetRow(int i, Array< T > &sa) const
Extract a copy of the i-th row into the Array sa.
Definition: array.hpp:326
void MakeRef(const Array2D &master)
Make this Array a reference to &#39;master&#39;.
Definition: array.hpp:371
iterator & operator++()
Definition: array.hpp:505
void Load(int new_size, std::istream &in)
Set the Array size to new_size and read that many entries from the stream in.
Definition: array.hpp:225
const_iterator cend() const
Definition: array.hpp:533
void DeleteFirst(const T &el)
Delete the first &#39;el&#39; entry.
Definition: array.hpp:692
T & operator[](int index)
Access item of the array.
Definition: array.hpp:433
void SetSize(int n1, int n2, int n3)
Definition: array.hpp:394
iterator(BlockArray *a)
Definition: array.hpp:502
void DeleteAll()
Delete whole array.
Definition: array.hpp:709
void GrowSize(int minsize, int elementsize)
Definition: array.cpp:44
int Append(const Array< T > &els)
Append another array to this array, resize if necessary.
Definition: array.hpp:162
iterator begin()
Definition: array.hpp:528
~Array()
Destructor.
Definition: array.hpp:94
long MemoryUsage() const
Definition: array.hpp:269
void GetSubArray(int offset, int sa_size, Array< T > &sa)
Definition: array.hpp:745
int size
Size of the array.
Definition: array.hpp:34
void SetSize(int m, int n)
Definition: array.hpp:308
int NumRows() const
Definition: array.hpp:310
const T & operator[](int index) const
Definition: array.hpp:434
void Save(std::ostream &out, int fmt=0) const
Save the Array to the stream out using the format fmt. The format fmt can be:
Definition: array.cpp:81
int Append(const T &el)
Append element to array, resize if necessary.
Definition: array.hpp:614
T & operator[](int i)
Access element.
Definition: array.hpp:598
int Capacity() const
Return the current capacity of the BlockArray.
Definition: array.hpp:440
int Find(const T &el) const
Return the first index where &#39;el&#39; is found; return -1 if not found.
Definition: array.hpp:673
void LoseData()
NULL-ifies the data.
Definition: array.hpp:127
void CheckIndex(int index) const
Definition: array.hpp:541
void MakeDataOwner()
Make the Array own the data.
Definition: array.hpp:130
void Reserve(int capacity)
Ensures that the allocated size is at least the given size.
Definition: array.hpp:146
bool operator!=(const Array< T > &LHS, const Array< T > &RHS)
Definition: array.hpp:282
void Assign(const T *)
Copy data from a pointer. Size() elements are copied.
Definition: array.hpp:764
void Print(std::ostream &out=mfem::out, int width=4) const
Prints array to stream with width elements per row.
Definition: array.cpp:64
void Sort()
Sorts the array. This requires operator< to be defined for T.
Definition: array.hpp:237
int allocsize
Size of the allocated memory.
Definition: array.hpp:36
void StealData(T **p)
Changes the ownership of the data.
Definition: array.hpp:123
int FindSorted(const T &el) const
Do bisection search for &#39;el&#39; in a sorted array; return -1 if not found.
Definition: array.hpp:683
const T * operator[](int i) const
Definition: array.hpp:791
int Union(const T &el)
Append element when it is not yet in the array, return index.
Definition: array.hpp:661
Dynamic 2D array using row-major layout.
Definition: array.hpp:289
void Print(std::ostream &out=mfem::out, int width=4)
Prints array to stream with width elements per row.
Definition: array.cpp:192
void Swap(Array< T > &, Array< T > &)
Definition: array.hpp:560
bool operator==(const Array< T > &LHS, const Array< T > &RHS)
Definition: array.hpp:273
long MemoryUsage() const
Definition: array.hpp:910
bool operator==(const const_iterator &other) const
Definition: array.hpp:524
int IsSorted()
return true if the array is sorted.
Definition: array.cpp:164
BlockArray(int block_size=16 *1024)
Definition: array.hpp:841
void SetSize(int nsize)
Change logical size of the array, keep existing entries.
Definition: array.hpp:569
void PartialSum()
Partial Sum.
Definition: array.cpp:140
int Capacity() const
Definition: array.hpp:143
void DeleteLast()
Delete the last entry.
Definition: array.hpp:181
Array2D(int m, int n)
Definition: array.hpp:306
Array< T > & operator=(const Array< CT > &src)
Assignment operator (deep copy) from an Array of convertable type.
Definition: array.hpp:101
const_iterator cbegin() const
Definition: array.hpp:531
bool operator!=(const const_iterator &other) const
Definition: array.hpp:525
int NumCols() const
Definition: array.hpp:311
Array< T * > blocks
Definition: array.hpp:536
void Copy(Array &copy) const
Create a copy of the current array.
Definition: array.hpp:190
bool operator!=(const iterator &other) const
Definition: array.hpp:508
const T & operator()(int i, int j, int k) const
Definition: array.hpp:818
int Size() const
Logical size of the array.
Definition: array.hpp:133
const_iterator & operator++()
Definition: array.hpp:522
const T & At(int index) const
Definition: array.hpp:426
T & Last()
Return the last element in the array.
Definition: array.hpp:647
iterator_base< BlockArray, T > base
Definition: array.hpp:498
void MakeRef(T *, int)
Make this Array a reference to a pointer.
Definition: array.hpp:720
iterator end()
Definition: array.hpp:529
Array< T > & operator=(const Array< T > &src)
Assignment operator: deep copy.
Definition: array.hpp:97
const T & operator()(int i, int j) const
Definition: array.hpp:771
Array(const Array< CT > &src)
Copy constructor (deep copy) from an Array of convertable type.
Definition: array.hpp:89
void DeleteAll()
Delete all dynamically allocated memory, reseting all dimentions to zero.
Definition: array.hpp:375
Array3D(int n1, int n2, int n3)
Definition: array.hpp:391
const T * GetRow(int i) const
Definition: array.hpp:322
OutStream out(std::cout)
Global stream used by the library for standard output. Initially it uses the same std::streambuf as s...
Definition: globals.hpp:64
Array(int asize=0, int ainc=0)
Creates array of asize elements.
Definition: array.hpp:73
T & At(int index)
Access item of the array.
Definition: array.hpp:421
int Prepend(const T &el)
Prepend an element to the array, resize if necessary.
Definition: array.hpp:635
int Append()
Allocate and construct a new item in the array, return its index.
Definition: array.hpp:885
void Load(int new_size0, int new_size1, std::istream &in)
Set the Array2D dimensions to new_size0 x new_size1 and read that many entries from the stream in...
Definition: array.hpp:361
void Swap(BlockArray< T > &other)
Definition: array.hpp:901
const T * operator()(int i) const
Definition: array.hpp:319