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