MFEM  v4.6.0
Finite element discretization library
array.hpp
Go to the documentation of this file.
1 // Copyright (c) 2010-2023, Lawrence Livermore National Security, LLC. Produced
2 // at the Lawrence Livermore National Laboratory. All Rights reserved. See files
3 // LICENSE and NOTICE for details. LLNL-CODE-806117.
4 //
5 // This file is part of the MFEM library. For more information and source code
6 // availability visit https://mfem.org.
7 //
8 // MFEM is free software; you can redistribute it and/or modify it under the
9 // terms of the BSD-3 license. We welcome feedback and contributions, see file
10 // CONTRIBUTING.md for details.
11 
12 #ifndef MFEM_ARRAY
13 #define MFEM_ARRAY
14 
15 #include "../config/config.hpp"
16 #include "mem_manager.hpp"
17 #include "device.hpp"
18 #include "error.hpp"
19 #include "globals.hpp"
20 
21 #include <iostream>
22 #include <cstdlib>
23 #include <cstring>
24 #include <algorithm>
25 #include <type_traits>
26 
27 namespace mfem
28 {
29 
30 template <class T>
31 class Array;
32 
33 template <class T>
34 void Swap(Array<T> &, Array<T> &);
35 
36 /**
37  Abstract data type Array.
38 
39  Array<T> is an automatically increasing array containing elements of the
40  generic type T, which must be a trivial type, see `std::is_trivial`. The
41  allocated size may be larger then the logical size of the array. The elements
42  can be accessed by the [] operator, the range is 0 to size-1.
43 */
44 template <class T>
45 class Array
46 {
47 protected:
48  /// Pointer to data
50  /// Size of the array
51  int size;
52 
53  inline void GrowSize(int minsize);
54 
55  static inline void TypeAssert()
56  {
57  static_assert(std::is_trivial<T>::value, "type T must be trivial");
58  }
59 
60 public:
61  friend void Swap<T>(Array<T> &, Array<T> &);
62 
63  /// Creates an empty array
64  inline Array() : size(0) { data.Reset(); }
65 
66  /// Creates an empty array with a given MemoryType
67  inline Array(MemoryType mt) : size(0) { data.Reset(mt); }
68 
69  /// Creates array of @a asize elements
70  explicit inline Array(int asize)
71  : size(asize) { asize > 0 ? data.New(asize) : data.Reset(); }
72 
73  /// Creates array of @a asize elements with a given MemoryType
74  inline Array(int asize, MemoryType mt)
75  : size(asize) { asize > 0 ? data.New(asize, mt) : data.Reset(mt); }
76 
77  /** @brief Creates array using an existing c-array of asize elements;
78  allocsize is set to -asize to indicate that the data will not
79  be deleted. */
80  inline Array(T *data_, int asize)
81  { data.Wrap(data_, asize, false); size = asize; }
82 
83  /// Copy constructor: deep copy from @a src
84  /** This method supports source arrays using any MemoryType. */
85  inline Array(const Array &src);
86 
87  /// Copy constructor (deep copy) from 'src', an Array of convertible type.
88  template <typename CT>
89  inline Array(const Array<CT> &src);
90 
91  /// Deep copy from a braced init-list of convertible type
92  template <typename CT, int N>
93  explicit inline Array(const CT (&values)[N]);
94 
95  /// Move constructor ("steals" data from 'src')
96  inline Array(Array<T> &&src) { Swap(src, *this); }
97 
98  /// Destructor
99  inline ~Array() { TypeAssert(); data.Delete(); }
100 
101  /// Assignment operator: deep copy from 'src'.
102  Array<T> &operator=(const Array<T> &src) { src.Copy(*this); return *this; }
103 
104  /// Assignment operator (deep copy) from @a src, an Array of convertible type.
105  template <typename CT>
106  inline Array &operator=(const Array<CT> &src);
107 
108  /// Return the data as 'T *'
109  inline operator T *() { return data; }
110 
111  /// Return the data as 'const T *'
112  inline operator const T *() const { return data; }
113 
114  /// Returns the data
115  inline T *GetData() { return data; }
116  /// Returns the data
117  inline const T *GetData() const { return data; }
118 
119  /// Return a reference to the Memory object used by the Array.
120  Memory<T> &GetMemory() { return data; }
121 
122  /// Return a reference to the Memory object used by the Array, const version.
123  const Memory<T> &GetMemory() const { return data; }
124 
125  /// Return the device flag of the Memory object used by the Array
126  bool UseDevice() const { return data.UseDevice(); }
127 
128  /// Return true if the data will be deleted by the array
129  inline bool OwnsData() const { return data.OwnsHostPtr(); }
130 
131  /// Changes the ownership of the data
132  inline void StealData(T **p) { *p = data; data.Reset(); size = 0; }
133 
134  /// NULL-ifies the data
135  inline void LoseData() { data.Reset(); size = 0; }
136 
137  /// Make the Array own the data
138  void MakeDataOwner() const { data.SetHostPtrOwner(true); }
139 
140  /// Return the logical size of the array.
141  inline int Size() const { return size; }
142 
143  /// Change the logical size of the array, keep existing entries.
144  inline void SetSize(int nsize);
145 
146  /// Same as SetSize(int) plus initialize new entries with 'initval'.
147  inline void SetSize(int nsize, const T &initval);
148 
149  /** @brief Resize the array to size @a nsize using MemoryType @a mt. Note
150  that unlike the other versions of SetSize(), the current content of the
151  array is not preserved. */
152  inline void SetSize(int nsize, MemoryType mt);
153 
154  /** Maximum number of entries the array can store without allocating more
155  memory. */
156  inline int Capacity() const { return data.Capacity(); }
157 
158  /// Ensures that the allocated size is at least the given size.
159  inline void Reserve(int capacity)
160  { if (capacity > Capacity()) { GrowSize(capacity); } }
161 
162  /// Reference access to the ith element.
163  inline T & operator[](int i);
164 
165  /// Const reference access to the ith element.
166  inline const T &operator[](int i) const;
167 
168  /// Append element 'el' to array, resize if necessary.
169  inline int Append(const T & el);
170 
171  /// Append another array to this array, resize if necessary.
172  inline int Append(const T *els, int nels);
173 
174  /// Append another array to this array, resize if necessary.
175  inline int Append(const Array<T> &els) { return Append(els, els.Size()); }
176 
177  /// Prepend an 'el' to the array, resize if necessary.
178  inline int Prepend(const T &el);
179 
180  /// Return the last element in the array.
181  inline T &Last();
182 
183  /// Return the last element in the array.
184  inline const T &Last() const;
185 
186  /// Append element when it is not yet in the array, return index.
187  inline int Union(const T & el);
188 
189  /// Return the first index where 'el' is found; return -1 if not found.
190  inline int Find(const T &el) const;
191 
192  /// Do bisection search for 'el' in a sorted array; return -1 if not found.
193  inline int FindSorted(const T &el) const;
194 
195  /// Delete the last entry of the array.
196  inline void DeleteLast() { if (size > 0) { size--; } }
197 
198  /// Delete the first entry with value == 'el'.
199  inline void DeleteFirst(const T &el);
200 
201  /// Delete the whole array.
202  inline void DeleteAll();
203 
204 
205  /// Create a copy of the internal array to the provided @a copy.
206  inline void Copy(Array &copy) const;
207 
208  /// Make this Array a reference to a pointer.
209  inline void MakeRef(T *, int);
210 
211  /// Make this Array a reference to 'master'.
212  inline void MakeRef(const Array &master);
213 
214 
215  /// Copy sub array starting from @a offset out to the provided @a sa.
216  inline void GetSubArray(int offset, int sa_size, Array<T> &sa) const;
217 
218  /// Prints array to stream with width elements per row.
219  void Print(std::ostream &out = mfem::out, int width = 4) const;
220 
221  /** @brief Save the Array to the stream @a out using the format @a fmt.
222  The format @a fmt can be:
223 
224  0 - write the size followed by all entries
225  1 - write only the entries
226  */
227  void Save(std::ostream &out, int fmt = 0) const;
228 
229  /** @brief Read an Array from the stream @a in using format @a fmt.
230  The format @a fmt can be:
231 
232  0 - read the size then the entries
233  1 - read Size() entries
234  */
235  void Load(std::istream &in, int fmt = 0);
236 
237  /** @brief Set the Array size to @a new_size and read that many entries from
238  the stream @a in. */
239  void Load(int new_size, std::istream &in)
240  { SetSize(new_size); Load(in, 1); }
241 
242  /** @brief Find the maximal element in the array, using the comparison
243  operator `<` for class T. */
244  T Max() const;
245 
246  /** @brief Find the minimal element in the array, using the comparison
247  operator `<` for class T. */
248  T Min() const;
249 
250  /// Sorts the array in ascending order. This requires operator< to be defined for T.
251  void Sort() { std::sort((T*)data, data + size); }
252 
253  /// Sorts the array in ascending order using the supplied comparison function object.
254  template<class Compare>
255  void Sort(Compare cmp) { std::sort((T*)data, data + size, cmp); }
256 
257  /** @brief Removes duplicities from a sorted array. This requires
258  operator== to be defined for T. */
259  void Unique()
260  {
261  T* end = std::unique((T*)data, data + size);
262  SetSize(end - data);
263  }
264 
265  /// Return 1 if the array is sorted from lowest to highest. Otherwise return 0.
266  int IsSorted();
267 
268  /// Fill the entries of the array with the cumulative sum of the entries.
269  void PartialSum();
270 
271  /// Return the sum of all the array entries using the '+'' operator for class 'T'.
272  T Sum();
273 
274  /// Set all entries of the array to the provided constant.
275  inline void operator=(const T &a);
276 
277  /// Copy data from a pointer. 'Size()' elements are copied.
278  inline void Assign(const T *);
279 
280  /// STL-like copyTo @a dest from begin to end.
281  template <typename U>
282  inline void CopyTo(U *dest) { std::copy(begin(), end(), dest); }
283 
284  /** @brief Copy from @a src into this array. Copies enough entries to
285  fill the Capacity size of this array. Careful this does not update
286  the Size to match this Capacity after this.*/
287  template <typename U>
288  inline void CopyFrom(const U *src)
289  { std::memcpy(begin(), src, MemoryUsage()); }
290 
291  /// STL-like begin. Returns pointer to the first element of the array.
292  inline T* begin() { return data; }
293 
294  /// STL-like end. Returns pointer after the last element of the array.
295  inline T* end() { return data + size; }
296 
297  /// STL-like begin. Returns const pointer to the first element of the array.
298  inline const T* begin() const { return data; }
299 
300  /// STL-like end. Returns const pointer after the last element of the array.
301  inline const T* end() const { return data + size; }
302 
303  /// Returns the number of bytes allocated for the array including any reserve.
304  std::size_t MemoryUsage() const { return Capacity() * sizeof(T); }
305 
306  /// Shortcut for mfem::Read(a.GetMemory(), a.Size(), on_dev).
307  const T *Read(bool on_dev = true) const
308  { return mfem::Read(data, size, on_dev); }
309 
310  /// Shortcut for mfem::Read(a.GetMemory(), a.Size(), false).
311  const T *HostRead() const
312  { return mfem::Read(data, size, false); }
313 
314  /// Shortcut for mfem::Write(a.GetMemory(), a.Size(), on_dev).
315  T *Write(bool on_dev = true)
316  { return mfem::Write(data, size, on_dev); }
317 
318  /// Shortcut for mfem::Write(a.GetMemory(), a.Size(), false).
320  { return mfem::Write(data, size, false); }
321 
322  /// Shortcut for mfem::ReadWrite(a.GetMemory(), a.Size(), on_dev).
323  T *ReadWrite(bool on_dev = true)
324  { return mfem::ReadWrite(data, size, on_dev); }
325 
326  /// Shortcut for mfem::ReadWrite(a.GetMemory(), a.Size(), false).
328  { return mfem::ReadWrite(data, size, false); }
329 };
330 
331 template <class T>
332 inline bool operator==(const Array<T> &LHS, const Array<T> &RHS)
333 {
334  if ( LHS.Size() != RHS.Size() ) { return false; }
335  for (int i=0; i<LHS.Size(); i++)
336  {
337  if ( LHS[i] != RHS[i] ) { return false; }
338  }
339  return true;
340 }
341 
342 template <class T>
343 inline bool operator!=(const Array<T> &LHS, const Array<T> &RHS)
344 {
345  return !( LHS == RHS );
346 }
347 
348 
349 /// Utility function similar to std::as_const in c++17.
350 template <typename T> const T &AsConst(const T &a) { return a; }
351 
352 
353 template <class T>
354 class Array2D;
355 
356 template <class T>
357 void Swap(Array2D<T> &, Array2D<T> &);
358 
359 /// Dynamic 2D array using row-major layout
360 template <class T>
361 class Array2D
362 {
363 private:
364  friend void Swap<T>(Array2D<T> &, Array2D<T> &);
365 
366  Array<T> array1d;
367  int M, N; // number of rows and columns
368 
369 public:
370  Array2D() { M = N = 0; }
371  Array2D(int m, int n) : array1d(m*n) { M = m; N = n; }
372 
373  Array2D(const Array2D &) = default;
374 
375  void SetSize(int m, int n) { array1d.SetSize(m*n); M = m; N = n; }
376 
377  int NumRows() const { return M; }
378  int NumCols() const { return N; }
379 
380  inline const T &operator()(int i, int j) const;
381  inline T &operator()(int i, int j);
382 
383  inline const T *operator[](int i) const;
384  inline T *operator[](int i);
385 
386  const T *operator()(int i) const { return (*this)[i]; }
387  T *operator()(int i) { return (*this)[i]; }
388 
389  const T *GetRow(int i) const { return (*this)[i]; }
390  T *GetRow(int i) { return (*this)[i]; }
391 
392  /// Extract a copy of the @a i-th row into the Array @a sa.
393  void GetRow(int i, Array<T> &sa) const
394  {
395  sa.SetSize(N);
396  sa.Assign(GetRow(i));
397  }
398 
399  /** @brief Save the Array2D to the stream @a out using the format @a fmt.
400  The format @a fmt can be:
401 
402  0 - write the number of rows and columns, followed by all entries
403  1 - write only the entries, using row-major layout
404  */
405  void Save(std::ostream &os, int fmt = 0) const
406  {
407  if (fmt == 0) { os << NumRows() << ' ' << NumCols() << '\n'; }
408  array1d.Save(os, 1);
409  }
410 
411  /** @brief Read an Array2D from the stream @a in using format @a fmt.
412  The format @a fmt can be:
413 
414  0 - read the number of rows and columns, then the entries
415  1 - read NumRows() x NumCols() entries, using row-major layout
416  */
417  void Load(std::istream &in, int fmt = 0)
418  {
419  if (fmt == 0) { in >> M >> N; array1d.SetSize(M*N); }
420  array1d.Load(in, 1);
421  }
422 
423  /// Read an Array2D from a file
424  void Load(const char *filename, int fmt = 0);
425 
426  /** @brief Set the Array2D dimensions to @a new_size0 x @a new_size1 and read
427  that many entries from the stream @a in. */
428  void Load(int new_size0,int new_size1, std::istream &in)
429  { SetSize(new_size0,new_size1); Load(in, 1); }
430 
431  void Copy(Array2D &copy) const
432  { copy.M = M; copy.N = N; array1d.Copy(copy.array1d); }
433 
434  inline void operator=(const T &a)
435  { array1d = a; }
436 
437  inline Array2D& operator=(const Array2D &a) = default;
438 
439  /// Make this Array a reference to 'master'
440  inline void MakeRef(const Array2D &master)
441  { M = master.M; N = master.N; array1d.MakeRef(master.array1d); }
442 
443  /// Delete all dynamically allocated memory, resetting all dimensions to zero.
444  inline void DeleteAll() { M = 0; N = 0; array1d.DeleteAll(); }
445 
446  /// Prints array to stream with width elements per row
447  void Print(std::ostream &out = mfem::out, int width = 4);
448 };
449 
450 
451 template <class T>
452 class Array3D
453 {
454 private:
455  Array<T> array1d;
456  int N2, N3;
457 
458 public:
459  Array3D() { N2 = N3 = 0; }
460  Array3D(int n1, int n2, int n3)
461  : array1d(n1*n2*n3) { N2 = n2; N3 = n3; }
462 
463  void SetSize(int n1, int n2, int n3)
464  { array1d.SetSize(n1*n2*n3); N2 = n2; N3 = n3; }
465 
466  inline const T &operator()(int i, int j, int k) const;
467  inline T &operator()(int i, int j, int k);
468 
469  inline void operator=(const T &a)
470  { array1d = a; }
471 };
472 
473 
474 /** A container for items of type T. Dynamically grows as items are added.
475  * Each item is accessible by its index. Items are allocated in larger chunks
476  * (blocks), so the 'Append' method is very fast on average.
477  */
478 template<typename T>
480 {
481 public:
482  BlockArray(int block_size = 16*1024);
483  BlockArray(const BlockArray<T> &other); // deep copy
484  BlockArray& operator=(const BlockArray&) = delete; // not supported
486 
487  /// Allocate and construct a new item in the array, return its index.
488  int Append();
489 
490  /// Allocate and copy-construct a new item in the array, return its index.
491  int Append(const T &item);
492 
493  /// Access item of the array.
494  inline T& At(int index)
495  {
496  CheckIndex(index);
497  return blocks[index >> shift][index & mask];
498  }
499  inline const T& At(int index) const
500  {
501  CheckIndex(index);
502  return blocks[index >> shift][index & mask];
503  }
504 
505  /// Access item of the array.
506  inline T& operator[](int index) { return At(index); }
507  inline const T& operator[](int index) const { return At(index); }
508 
509  /// Return the number of items actually stored.
510  int Size() const { return size; }
511 
512  /// Return the current capacity of the BlockArray.
513  int Capacity() const { return blocks.Size()*(mask+1); }
514 
515  /// Destroy all items, set size to zero.
516  void DeleteAll() { Destroy(); blocks.DeleteAll(); size = 0; }
517 
518  void Swap(BlockArray<T> &other);
519 
520  std::size_t MemoryUsage() const;
521 
522 protected:
523  template <typename cA, typename cT>
525  {
526  public:
527  cT& operator*() const { return *ptr; }
528  cT* operator->() const { return ptr; }
529 
530  bool good() const { return !stop; }
531  int index() const { return (ptr - ref); }
532 
533  protected:
534  cA *array;
535  cT *ptr, *b_end, *ref;
537  bool stop;
538 
542  : array(a), ptr(a->blocks[0]), ref(ptr), stop(false)
543  {
544  b_end_idx = std::min(a->size, a->mask+1);
545  b_end = ptr + b_end_idx;
546  }
547 
548  void next()
549  {
550  MFEM_ASSERT(!stop, "invalid use");
551  if (++ptr == b_end)
552  {
553  if (b_end_idx < array->size)
554  {
555  ptr = &array->At(b_end_idx);
556  ref = ptr - b_end_idx;
557  b_end_idx = std::min(array->size, (b_end_idx|array->mask) + 1);
558  b_end = &array->At(b_end_idx-1) + 1;
559  }
560  else
561  {
562  MFEM_ASSERT(b_end_idx == array->size, "invalid use");
563  stop = true;
564  }
565  }
566  }
567  };
568 
569 public:
570  class iterator : public iterator_base<BlockArray, T>
571  {
572  protected:
573  friend class BlockArray;
575 
576  iterator() { }
577  iterator(bool stop) : base(stop) { }
579 
580  public:
581  iterator &operator++() { base::next(); return *this; }
582 
583  bool operator==(const iterator &other) const { return base::stop; }
584  bool operator!=(const iterator &other) const { return !base::stop; }
585  };
586 
587  class const_iterator : public iterator_base<const BlockArray, const T>
588  {
589  protected:
590  friend class BlockArray;
592 
596 
597  public:
598  const_iterator &operator++() { base::next(); return *this; }
599 
600  bool operator==(const const_iterator &other) const { return base::stop; }
601  bool operator!=(const const_iterator &other) const { return !base::stop; }
602  };
603 
604  iterator begin() { return size ? iterator(this) : iterator(true); }
605  iterator end() { return iterator(); }
606 
607  const_iterator cbegin() const
608  { return size ? const_iterator(this) : const_iterator(true); }
609  const_iterator cend() const { return const_iterator(); }
610 
611 protected:
613  int size, shift, mask;
614 
615  int Alloc();
616 
617  inline void CheckIndex(int index) const
618  {
619  MFEM_ASSERT(index >= 0 && index < size,
620  "Out of bounds access: " << index << ", size = " << size);
621  }
622 
623  void Destroy();
624 };
625 
626 
627 /// inlines ///
628 
629 template <class T>
630 inline void Swap(T &a, T &b)
631 {
632  T c = a;
633  a = b;
634  b = c;
635 }
636 
637 template <class T>
638 inline void Swap(Array<T> &a, Array<T> &b)
639 {
640  Swap(a.data, b.data);
641  Swap(a.size, b.size);
642 }
643 
644 template <class T>
645 inline Array<T>::Array(const Array &src)
646  : size(src.Size())
647 {
648  size > 0 ? data.New(size, src.data.GetMemoryType()) : data.Reset();
649  data.CopyFrom(src.data, size);
650  data.UseDevice(src.data.UseDevice());
651 }
652 
653 template <typename T> template <typename CT>
654 inline Array<T>::Array(const Array<CT> &src)
655  : size(src.Size())
656 {
657  size > 0 ? data.New(size) : data.Reset();
658  for (int i = 0; i < size; i++) { (*this)[i] = T(src[i]); }
659 }
660 
661 template <typename T> template <typename CT, int N>
662 inline Array<T>::Array(const CT (&values)[N]) : Array(N)
663 {
664  for (int i = 0; i < size; i++) { (*this)[i] = T(values[i]); }
665 }
666 
667 template <class T>
668 inline void Array<T>::GrowSize(int minsize)
669 {
670  const int nsize = std::max(minsize, 2 * data.Capacity());
671  Memory<T> p(nsize, data.GetMemoryType());
672  p.CopyFrom(data, size);
673  p.UseDevice(data.UseDevice());
674  data.Delete();
675  data = p;
676 }
677 
678 template <typename T> template <typename CT>
680 {
681  SetSize(src.Size());
682  for (int i = 0; i < size; i++) { (*this)[i] = T(src[i]); }
683  return *this;
684 }
685 
686 template <class T>
687 inline void Array<T>::SetSize(int nsize)
688 {
689  MFEM_ASSERT( nsize>=0, "Size must be non-negative. It is " << nsize );
690  if (nsize > Capacity())
691  {
692  GrowSize(nsize);
693  }
694  size = nsize;
695 }
696 
697 template <class T>
698 inline void Array<T>::SetSize(int nsize, const T &initval)
699 {
700  MFEM_ASSERT( nsize>=0, "Size must be non-negative. It is " << nsize );
701  if (nsize > size)
702  {
703  if (nsize > Capacity())
704  {
705  GrowSize(nsize);
706  }
707  for (int i = size; i < nsize; i++)
708  {
709  data[i] = initval;
710  }
711  }
712  size = nsize;
713 }
714 
715 template <class T>
716 inline void Array<T>::SetSize(int nsize, MemoryType mt)
717 {
718  MFEM_ASSERT(nsize >= 0, "invalid new size: " << nsize);
719  if (mt == data.GetMemoryType())
720  {
721  if (nsize <= Capacity())
722  {
723  size = nsize;
724  return;
725  }
726  }
727  const bool use_dev = data.UseDevice();
728  data.Delete();
729  if (nsize > 0)
730  {
731  data.New(nsize, mt);
732  size = nsize;
733  }
734  else
735  {
736  data.Reset();
737  size = 0;
738  }
739  data.UseDevice(use_dev);
740 }
741 
742 template <class T>
743 inline T &Array<T>::operator[](int i)
744 {
745  MFEM_ASSERT( i>=0 && i<size,
746  "Access element " << i << " of array, size = " << size );
747  return data[i];
748 }
749 
750 template <class T>
751 inline const T &Array<T>::operator[](int i) const
752 {
753  MFEM_ASSERT( i>=0 && i<size,
754  "Access element " << i << " of array, size = " << size );
755  return data[i];
756 }
757 
758 template <class T>
759 inline int Array<T>::Append(const T &el)
760 {
761  SetSize(size+1);
762  data[size-1] = el;
763  return size;
764 }
765 
766 template <class T>
767 inline int Array<T>::Append(const T *els, int nels)
768 {
769  const int old_size = size;
770 
771  SetSize(size + nels);
772  for (int i = 0; i < nels; i++)
773  {
774  data[old_size+i] = els[i];
775  }
776  return size;
777 }
778 
779 template <class T>
780 inline int Array<T>::Prepend(const T &el)
781 {
782  SetSize(size+1);
783  for (int i = size-1; i > 0; i--)
784  {
785  data[i] = data[i-1];
786  }
787  data[0] = el;
788  return size;
789 }
790 
791 template <class T>
792 inline T &Array<T>::Last()
793 {
794  MFEM_ASSERT(size > 0, "Array size is zero: " << size);
795  return data[size-1];
796 }
797 
798 template <class T>
799 inline const T &Array<T>::Last() const
800 {
801  MFEM_ASSERT(size > 0, "Array size is zero: " << size);
802  return data[size-1];
803 }
804 
805 template <class T>
806 inline int Array<T>::Union(const T &el)
807 {
808  int i = 0;
809  while ((i < size) && (data[i] != el)) { i++; }
810  if (i == size)
811  {
812  Append(el);
813  }
814  return i;
815 }
816 
817 template <class T>
818 inline int Array<T>::Find(const T &el) const
819 {
820  for (int i = 0; i < size; i++)
821  {
822  if (data[i] == el) { return i; }
823  }
824  return -1;
825 }
826 
827 template <class T>
828 inline int Array<T>::FindSorted(const T &el) const
829 {
830  const T *begin = data, *end = begin + size;
831  const T* first = std::lower_bound(begin, end, el);
832  if (first == end || !(*first == el)) { return -1; }
833  return first - begin;
834 }
835 
836 template <class T>
837 inline void Array<T>::DeleteFirst(const T &el)
838 {
839  for (int i = 0; i < size; i++)
840  {
841  if (data[i] == el)
842  {
843  for (i++; i < size; i++)
844  {
845  data[i-1] = data[i];
846  }
847  size--;
848  return;
849  }
850  }
851 }
852 
853 template <class T>
854 inline void Array<T>::DeleteAll()
855 {
856  const bool use_dev = data.UseDevice();
857  data.Delete();
858  data.Reset();
859  size = 0;
860  data.UseDevice(use_dev);
861 }
862 
863 template <typename T>
864 inline void Array<T>::Copy(Array &copy) const
865 {
866  copy.SetSize(Size(), data.GetMemoryType());
867  data.CopyTo(copy.data, Size());
868  copy.data.UseDevice(data.UseDevice());
869 }
870 
871 template <class T>
872 inline void Array<T>::MakeRef(T *p, int s)
873 {
874  data.Delete();
875  data.Wrap(p, s, false);
876  size = s;
877 }
878 
879 template <class T>
880 inline void Array<T>::MakeRef(const Array &master)
881 {
882  data.Delete();
883  size = master.size;
884  data.MakeAlias(master.GetMemory(), 0, size);
885 }
886 
887 template <class T>
888 inline void Array<T>::GetSubArray(int offset, int sa_size, Array<T> &sa) const
889 {
890  sa.SetSize(sa_size);
891  for (int i = 0; i < sa_size; i++)
892  {
893  sa[i] = (*this)[offset+i];
894  }
895 }
896 
897 template <class T>
898 inline void Array<T>::operator=(const T &a)
899 {
900  for (int i = 0; i < size; i++)
901  {
902  data[i] = a;
903  }
904 }
905 
906 template <class T>
907 inline void Array<T>::Assign(const T *p)
908 {
909  data.CopyFromHost(p, Size());
910 }
911 
912 
913 template <class T>
914 inline const T &Array2D<T>::operator()(int i, int j) const
915 {
916  MFEM_ASSERT( i>=0 && i< array1d.Size()/N && j>=0 && j<N,
917  "Array2D: invalid access of element (" << i << ',' << j
918  << ") in array of size (" << array1d.Size()/N << ',' << N
919  << ")." );
920  return array1d[i*N+j];
921 }
922 
923 template <class T>
924 inline T &Array2D<T>::operator()(int i, int j)
925 {
926  MFEM_ASSERT( i>=0 && i< array1d.Size()/N && j>=0 && j<N,
927  "Array2D: invalid access of element (" << i << ',' << j
928  << ") in array of size (" << array1d.Size()/N << ',' << N
929  << ")." );
930  return array1d[i*N+j];
931 }
932 
933 template <class T>
934 inline const T *Array2D<T>::operator[](int i) const
935 {
936  MFEM_ASSERT( i>=0 && i< array1d.Size()/N,
937  "Array2D: invalid access of row " << i << " in array with "
938  << array1d.Size()/N << " rows.");
939  return &array1d[i*N];
940 }
941 
942 template <class T>
943 inline T *Array2D<T>::operator[](int i)
944 {
945  MFEM_ASSERT( i>=0 && i< array1d.Size()/N,
946  "Array2D: invalid access of row " << i << " in array with "
947  << array1d.Size()/N << " rows.");
948  return &array1d[i*N];
949 }
950 
951 
952 template <class T>
953 inline void Swap(Array2D<T> &a, Array2D<T> &b)
954 {
955  Swap(a.array1d, b.array1d);
956  Swap(a.N, b.N);
957 }
958 
959 
960 template <class T>
961 inline const T &Array3D<T>::operator()(int i, int j, int k) const
962 {
963  MFEM_ASSERT(i >= 0 && i < array1d.Size() / N2 / N3 && j >= 0 && j < N2
964  && k >= 0 && k < N3,
965  "Array3D: invalid access of element ("
966  << i << ',' << j << ',' << k << ") in array of size ("
967  << array1d.Size() / N2 / N3 << ',' << N2 << ',' << N3 << ").");
968  return array1d[(i*N2+j)*N3+k];
969 }
970 
971 template <class T>
972 inline T &Array3D<T>::operator()(int i, int j, int k)
973 {
974  MFEM_ASSERT(i >= 0 && i < array1d.Size() / N2 / N3 && j >= 0 && j < N2
975  && k >= 0 && k < N3,
976  "Array3D: invalid access of element ("
977  << i << ',' << j << ',' << k << ") in array of size ("
978  << array1d.Size() / N2 / N3 << ',' << N2 << ',' << N3 << ").");
979  return array1d[(i*N2+j)*N3+k];
980 }
981 
982 
983 template<typename T>
985 {
986  mask = block_size-1;
987  MFEM_VERIFY(!(block_size & mask), "block_size must be a power of two.");
988 
989  size = shift = 0;
990  while ((1 << shift) < block_size) { shift++; }
991 }
992 
993 template<typename T>
995 {
996  blocks.SetSize(other.blocks.Size());
997 
998  size = other.size;
999  shift = other.shift;
1000  mask = other.mask;
1001 
1002  int bsize = mask+1;
1003  for (int i = 0; i < blocks.Size(); i++)
1004  {
1005  blocks[i] = (T*) new char[bsize * sizeof(T)];
1006  }
1007 
1008  // copy all items
1009  for (int i = 0; i < size; i++)
1010  {
1011  new (&At(i)) T(other[i]);
1012  }
1013 }
1014 
1015 template<typename T>
1017 {
1018  int bsize = mask+1;
1019  if (size >= blocks.Size() * bsize)
1020  {
1021  T* new_block = (T*) new char[bsize * sizeof(T)];
1022  blocks.Append(new_block);
1023  }
1024  return size++;
1025 }
1026 
1027 template<typename T>
1029 {
1030  int index = Alloc();
1031  new (&At(index)) T();
1032  return index;
1033 }
1034 
1035 template<typename T>
1036 int BlockArray<T>::Append(const T &item)
1037 {
1038  int index = Alloc();
1039  new (&At(index)) T(item);
1040  return index;
1041 }
1042 
1043 template<typename T>
1045 {
1046  mfem::Swap(blocks, other.blocks);
1047  std::swap(size, other.size);
1048  std::swap(shift, other.shift);
1049  std::swap(mask, other.mask);
1050 }
1051 
1052 template<typename T>
1053 std::size_t BlockArray<T>::MemoryUsage() const
1054 {
1055  return (mask+1)*sizeof(T)*blocks.Size() + blocks.MemoryUsage();
1056 }
1057 
1058 template<typename T>
1060 {
1061  int bsize = size & mask;
1062  for (int i = blocks.Size(); i != 0; )
1063  {
1064  T *block = blocks[--i];
1065  for (int j = bsize; j != 0; )
1066  {
1067  block[--j].~T();
1068  }
1069  delete [] (char*) block;
1070  bsize = mask+1;
1071  }
1072 }
1073 
1074 } // namespace mfem
1075 
1076 #endif
const T * Read(bool on_dev=true) const
Shortcut for mfem::Read(a.GetMemory(), a.Size(), on_dev).
Definition: array.hpp:307
T Min() const
Find the minimal element in the array, using the comparison operator < for class T.
Definition: array.cpp:85
T * HostReadWrite()
Shortcut for mfem::ReadWrite(a.GetMemory(), a.Size(), false).
Definition: array.hpp:327
int Size() const
Return the number of items actually stored.
Definition: array.hpp:510
const_iterator(const BlockArray *a)
Definition: array.hpp:595
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:53
friend void Swap(Array< T > &, Array< T > &)
Definition: array.hpp:638
void Unique()
Removes duplicities from a sorted array. This requires operator== to be defined for T...
Definition: array.hpp:259
Memory< T > & GetMemory()
Return a reference to the Memory object used by the Array.
Definition: array.hpp:120
T * end()
STL-like end. Returns pointer after the last element of the array.
Definition: array.hpp:295
Array(int asize, MemoryType mt)
Creates array of asize elements with a given MemoryType.
Definition: array.hpp:74
iterator_base< const BlockArray, const T > base
Definition: array.hpp:591
bool operator==(const iterator &other) const
Definition: array.hpp:583
void Delete()
Delete the owned pointers and reset the Memory object.
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:417
int size
Size of the array.
Definition: array.hpp:51
void Copy(Array2D &copy) const
Definition: array.hpp:431
T * GetData()
Returns the data.
Definition: array.hpp:115
static void TypeAssert()
Definition: array.hpp:55
T * Write(Memory< T > &mem, int size, bool on_dev=true)
Get a pointer for write access to mem with the mfem::Device&#39;s DeviceMemoryClass, if on_dev = true...
Definition: device.hpp:336
T Max() const
Find the maximal element in the array, using the comparison operator < for class T.
Definition: array.cpp:68
void operator=(const T &a)
Definition: array.hpp:434
bool OwnsData() const
Return true if the data will be deleted by the array.
Definition: array.hpp:129
Array(int asize)
Creates array of asize elements.
Definition: array.hpp:70
void Sort(Compare cmp)
Sorts the array in ascending order using the supplied comparison function object. ...
Definition: array.hpp:255
void operator=(const T &a)
Definition: array.hpp:469
T Sum()
Return the sum of all the array entries using the &#39;+&#39;&#39; operator for class &#39;T&#39;.
Definition: array.cpp:115
void GetRow(int i, Array< T > &sa) const
Extract a copy of the i-th row into the Array sa.
Definition: array.hpp:393
std::size_t MemoryUsage() const
Definition: array.hpp:1053
void MakeRef(const Array2D &master)
Make this Array a reference to &#39;master&#39;.
Definition: array.hpp:440
void CopyFrom(const Memory &src, int size)
Copy size entries from src to *this.
iterator & operator++()
Definition: array.hpp:581
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:239
const_iterator cend() const
Definition: array.hpp:609
void DeleteFirst(const T &el)
Delete the first entry with value == &#39;el&#39;.
Definition: array.hpp:837
T & operator[](int index)
Access item of the array.
Definition: array.hpp:506
void SetSize(int n1, int n2, int n3)
Definition: array.hpp:463
Array(Array< T > &&src)
Move constructor ("steals" data from &#39;src&#39;)
Definition: array.hpp:96
iterator(BlockArray *a)
Definition: array.hpp:578
const Memory< T > & GetMemory() const
Return a reference to the Memory object used by the Array, const version.
Definition: array.hpp:123
void DeleteAll()
Delete the whole array.
Definition: array.hpp:854
int Append(const Array< T > &els)
Append another array to this array, resize if necessary.
Definition: array.hpp:175
void CopyTo(U *dest)
STL-like copyTo dest from begin to end.
Definition: array.hpp:282
iterator begin()
Definition: array.hpp:604
~Array()
Destructor.
Definition: array.hpp:99
void MakeDataOwner() const
Make the Array own the data.
Definition: array.hpp:138
void Wrap(T *ptr, int size, bool own)
Wrap an externally allocated host pointer, ptr with the current host memory type returned by MemoryMa...
void SetSize(int m, int n)
Definition: array.hpp:375
int NumRows() const
Definition: array.hpp:377
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:40
void CopyFromHost(const T *src, int size)
Copy size entries from the host pointer src to *this.
int Append(const T &el)
Append element &#39;el&#39; to array, resize if necessary.
Definition: array.hpp:759
void DeleteAll()
Destroy all items, set size to zero.
Definition: array.hpp:516
T & operator[](int i)
Reference access to the ith element.
Definition: array.hpp:743
int Capacity() const
Return the current capacity of the BlockArray.
Definition: array.hpp:513
double b
Definition: lissajous.cpp:42
int Find(const T &el) const
Return the first index where &#39;el&#39; is found; return -1 if not found.
Definition: array.hpp:818
void LoseData()
NULL-ifies the data.
Definition: array.hpp:135
BlockArray & operator=(const BlockArray &)=delete
void Save(std::ostream &os, int fmt=0) const
Save the Array2D to the stream out using the format fmt. The format fmt can be:
Definition: array.hpp:405
void CheckIndex(int index) const
Definition: array.hpp:617
void Reserve(int capacity)
Ensures that the allocated size is at least the given size.
Definition: array.hpp:159
void CopyFrom(const U *src)
Copy from src into this array. Copies enough entries to fill the Capacity size of this array...
Definition: array.hpp:288
bool operator!=(const Array< T > &LHS, const Array< T > &RHS)
Definition: array.hpp:343
T * begin()
STL-like begin. Returns pointer to the first element of the array.
Definition: array.hpp:292
void Assign(const T *)
Copy data from a pointer. &#39;Size()&#39; elements are copied.
Definition: array.hpp:907
bool UseDevice() const
Return the device flag of the Memory object used by the Array.
Definition: array.hpp:126
void Print(std::ostream &out=mfem::out, int width=4) const
Prints array to stream with width elements per row.
Definition: array.cpp:23
void Sort()
Sorts the array in ascending order. This requires operator< to be defined for T.
Definition: array.hpp:251
int Capacity() const
Return the size of the allocated memory.
void StealData(T **p)
Changes the ownership of the data.
Definition: array.hpp:132
void GetSubArray(int offset, int sa_size, Array< T > &sa) const
Copy sub array starting from offset out to the provided sa.
Definition: array.hpp:888
const T * Read(const Memory< T > &mem, int size, bool on_dev=true)
Get a pointer for read access to mem with the mfem::Device&#39;s DeviceMemoryClass, if on_dev = true...
Definition: device.hpp:319
const T * HostRead() const
Shortcut for mfem::Read(a.GetMemory(), a.Size(), false).
Definition: array.hpp:311
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:828
const T * operator[](int i) const
Definition: array.hpp:934
void Reset()
Reset the memory to be empty, ensuring that Delete() will be a no-op.
int Union(const T &el)
Append element when it is not yet in the array, return index.
Definition: array.hpp:806
Dynamic 2D array using row-major layout.
Definition: array.hpp:354
Memory< T > data
Pointer to data.
Definition: array.hpp:49
void Destroy()
Definition: array.hpp:1059
void Print(std::ostream &out=mfem::out, int width=4)
Prints array to stream with width elements per row.
Definition: array.cpp:155
void Swap(Array< T > &, Array< T > &)
Definition: array.hpp:638
bool operator==(const Array< T > &LHS, const Array< T > &RHS)
Definition: array.hpp:332
void GrowSize(int minsize)
Definition: array.hpp:668
bool operator==(const const_iterator &other) const
Definition: array.hpp:600
int IsSorted()
Return 1 if the array is sorted from lowest to highest. Otherwise return 0.
Definition: array.cpp:127
Array(T *data_, int asize)
Creates array using an existing c-array of asize elements; allocsize is set to -asize to indicate tha...
Definition: array.hpp:80
BlockArray(int block_size=16 *1024)
Definition: array.hpp:984
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:66
MemoryType
Memory types supported by MFEM.
Definition: mem_manager.hpp:31
void SetSize(int nsize)
Change the logical size of the array, keep existing entries.
Definition: array.hpp:687
void PartialSum()
Fill the entries of the array with the cumulative sum of the entries.
Definition: array.cpp:103
int Capacity() const
Definition: array.hpp:156
T * ReadWrite(bool on_dev=true)
Shortcut for mfem::ReadWrite(a.GetMemory(), a.Size(), on_dev).
Definition: array.hpp:323
void DeleteLast()
Delete the last entry of the array.
Definition: array.hpp:196
Array2D(int m, int n)
Definition: array.hpp:371
void MakeAlias(const Memory &base, int offset, int size)
Create a memory object that points inside the memory object base.
const_iterator cbegin() const
Definition: array.hpp:607
Array(MemoryType mt)
Creates an empty array with a given MemoryType.
Definition: array.hpp:67
T * HostWrite()
Shortcut for mfem::Write(a.GetMemory(), a.Size(), false).
Definition: array.hpp:319
lvalue_t & Assign(lvalue_t &a, const rvalue_t &b)
Definition: tassign.hpp:137
double a
Definition: lissajous.cpp:41
T * ReadWrite(Memory< T > &mem, int size, bool on_dev=true)
Get a pointer for read+write access to mem with the mfem::Device&#39;s DeviceMemoryClass, if on_dev = true, or the mfem::Device&#39;s HostMemoryClass, otherwise.
Definition: device.hpp:353
bool operator!=(const const_iterator &other) const
Definition: array.hpp:601
void New(int size)
Allocate host memory for size entries with the current host memory type returned by MemoryManager::Ge...
int NumCols() const
Definition: array.hpp:378
Array()
Creates an empty array.
Definition: array.hpp:64
Array< T * > blocks
Definition: array.hpp:612
int index(int i, int j, int nx, int ny)
Definition: life.cpp:235
void Copy(Array &copy) const
Create a copy of the internal array to the provided copy.
Definition: array.hpp:864
bool operator!=(const iterator &other) const
Definition: array.hpp:584
Class used by MFEM to store pointers to host and/or device memory.
const T & operator()(int i, int j, int k) const
Definition: array.hpp:961
void Swap(T &a, T &b)
inlines ///
Definition: array.hpp:630
int Size() const
Return the logical size of the array.
Definition: array.hpp:141
const_iterator & operator++()
Definition: array.hpp:598
T & Last()
Return the last element in the array.
Definition: array.hpp:792
void CopyTo(Memory &dest, int size) const
Copy size entries from *this to dest.
std::size_t MemoryUsage() const
Returns the number of bytes allocated for the array including any reserve.
Definition: array.hpp:304
iterator_base< BlockArray, T > base
Definition: array.hpp:574
T * Write(bool on_dev=true)
Shortcut for mfem::Write(a.GetMemory(), a.Size(), on_dev).
Definition: array.hpp:315
void MakeRef(T *, int)
Make this Array a reference to a pointer.
Definition: array.hpp:872
iterator end()
Definition: array.hpp:605
Array< T > & operator=(const Array< T > &src)
Assignment operator: deep copy from &#39;src&#39;.
Definition: array.hpp:102
const T & operator()(int i, int j) const
Definition: array.hpp:914
bool UseDevice() const
Read the internal device flag.
RefCoord s[3]
void DeleteAll()
Delete all dynamically allocated memory, resetting all dimensions to zero.
Definition: array.hpp:444
Array3D(int n1, int n2, int n3)
Definition: array.hpp:460
const T * GetRow(int i) const
Definition: array.hpp:389
T & At(int index)
Access item of the array.
Definition: array.hpp:494
const T & AsConst(const T &a)
Utility function similar to std::as_const in c++17.
Definition: array.hpp:350
MemoryType GetMemoryType() const
Return a MemoryType that is currently valid. If both the host and the device pointers are currently v...
int Prepend(const T &el)
Prepend an &#39;el&#39; to the array, resize if necessary.
Definition: array.hpp:780
int Append()
Allocate and construct a new item in the array, return its index.
Definition: array.hpp:1028
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:428
void Swap(BlockArray< T > &other)
Definition: array.hpp:1044