MFEM  v3.3
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, 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 
18 #include <iostream>
19 #include <cstdlib>
20 #include <cstring>
21 #include <algorithm>
22 
23 namespace mfem
24 {
25 
26 /// Base class for array container.
27 class BaseArray
28 {
29 protected:
30  /// Pointer to data
31  void *data;
32  /// Size of the array
33  int size;
34  /// Size of the allocated memory
35  int allocsize;
36  /** Increment of allocated memory on overflow,
37  inc = 0 doubles the array */
38  int inc;
39 
40  BaseArray() { }
41  /// Creates array of asize elements of size elementsize
42  BaseArray(int asize, int ainc, int elmentsize);
43  /// Free the allocated memory
44  ~BaseArray();
45  /** Increases the allocsize of the array to be at least minsize.
46  The current content of the array is copied to the newly allocated
47  space. minsize must be > abs(allocsize). */
48  void GrowSize(int minsize, int elementsize);
49 };
50 
51 template <class T>
52 class Array;
53 
54 template <class T>
55 void Swap(Array<T> &, Array<T> &);
56 
57 /**
58  Abstract data type Array.
59 
60  Array<T> is an automatically increasing array containing elements of the
61  generic type T. The allocated size may be larger then the logical size
62  of the array.
63  The elements can be accessed by the [] operator, the range is 0 to size-1.
64 */
65 template <class T>
66 class Array : public BaseArray
67 {
68 public:
69  friend void Swap<T>(Array<T> &, Array<T> &);
70 
71  /// Creates array of asize elements
72  explicit inline Array(int asize = 0, int ainc = 0)
73  : BaseArray(asize, ainc, sizeof (T)) { }
74 
75  /** Creates array using an existing c-array of asize elements;
76  allocsize is set to -asize to indicate that the data will not
77  be deleted. */
78  inline Array(T *_data, int asize, int ainc = 0)
79  { data = _data; size = asize; allocsize = -asize; inc = ainc; }
80 
81  /// Destructor
82  inline ~Array() { }
83 
84  /// Return the data as 'T *'
85  inline operator T *() { return (T *)data; }
86 
87  /// Return the data as 'const T *'
88  inline operator const T *() const { return (const T *)data; }
89 
90  /// Returns the data
91  inline T *GetData() { return (T *)data; }
92  /// Returns the data
93  inline const T *GetData() const { return (T *)data; }
94 
95  /// Return true if the data will be deleted by the array
96  inline bool OwnsData() const { return (allocsize > 0); }
97 
98  /// Changes the ownership of the data
99  inline void StealData(T **p)
100  { *p = (T*)data; data = 0; size = allocsize = 0; }
101 
102  /// NULL-ifies the data
103  inline void LoseData() { data = 0; size = allocsize = 0; }
104 
105  /// Make the Array own the data
106  void MakeDataOwner() { allocsize = abs(allocsize); }
107 
108  /// Logical size of the array
109  inline int Size() const { return size; }
110 
111  /// Change logical size of the array, keep existing entries
112  inline void SetSize(int nsize);
113 
114  /// Same as SetSize(int) plus initialize new entries with 'initval'
115  inline void SetSize(int nsize, const T &initval);
116 
117  /** Maximum number of entries the array can store without allocating more
118  memory. */
119  inline int Capacity() const { return abs(allocsize); }
120 
121  /// Ensures that the allocated size is at least the given size.
122  inline void Reserve(int capacity)
123  { if (capacity > abs(allocsize)) { GrowSize(capacity, sizeof(T)); } }
124 
125  /// Access element
126  inline T & operator[](int i);
127 
128  /// Access const element
129  inline const T &operator[](int i) const;
130 
131  /// Append element to array, resize if necessary
132  inline int Append(const T & el);
133 
134  /// Append another array to this array, resize if necessary
135  inline int Append(const Array<T> &els);
136 
137  /// Prepend an element to the array, resize if necessary
138  inline int Prepend(const T &el);
139 
140  /// Return the last element in the array
141  inline T &Last();
142  inline const T &Last() const;
143 
144  /// Append element when it is not yet in the array, return index
145  inline int Union(const T & el);
146 
147  /// Return the first index where 'el' is found; return -1 if not found
148  inline int Find(const T &el) const;
149 
150  /// Delete the last entry
151  inline void DeleteLast() { if (size > 0) { size--; } }
152 
153  /// Delete the first 'el' entry
154  inline void DeleteFirst(const T &el);
155 
156  /// Delete whole array
157  inline void DeleteAll();
158 
159  /// Create a copy of the current array
160  inline void Copy(Array &copy) const
161  {
162  copy.SetSize(Size());
163  memcpy(copy.GetData(), data, Size()*sizeof(T));
164  }
165 
166  /// Make this Array a reference to a pointer
167  inline void MakeRef(T *, int);
168 
169  /// Make this Array a reference to 'master'
170  inline void MakeRef(const Array &master);
171 
172  inline void GetSubArray(int offset, int sa_size, Array<T> &sa);
173 
174  /// Prints array to stream with width elements per row
175  void Print(std::ostream &out = std::cout, int width = 4);
176 
177  /** @brief Save the Array to the stream @a out using the format @a fmt.
178  The format @a fmt can be:
179 
180  0 - write the size followed by all entries
181  1 - write only the entries
182  */
183  void Save(std::ostream &out, int fmt = 0) const;
184 
185  /** @brief Read an Array from the stream @a in using format @a fmt.
186  The format @a fmt can be:
187 
188  0 - read the size then the entries
189  1 - read Size() entries
190  */
191  void Load(std::istream &in, int fmt = 0);
192 
193  /** @brief Set the Array size to @a new_size and read that many entries from
194  the stream @a in. */
195  void Load(int new_size, std::istream &in)
196  { SetSize(new_size); Load(in, 1); }
197 
198  /** @brief Find the maximal element in the array, using the comparison
199  operator `<` for class T. */
200  T Max() const;
201 
202  /** @brief Find the minimal element in the array, using the comparison
203  operator `<` for class T. */
204  T Min() const;
205 
206  /// Sorts the array. This requires operator< to be defined for T.
207  void Sort() { std::sort((T*) data, (T*) data + size); }
208 
209  /// Sorts the array using the supplied comparison function object.
210  template<class Compare>
211  void Sort(Compare cmp) { std::sort((T*) data, (T*) data + size, cmp); }
212 
213  /** Removes duplicities from a sorted array. This requires operator== to be
214  defined for T. */
215  void Unique()
216  {
217  T* end = std::unique((T*) data, (T*) data + size);
218  SetSize(end - (T*) data);
219  }
220 
221  /// return true if the array is sorted.
222  int IsSorted();
223 
224  /// Partial Sum
225  void PartialSum();
226 
227  /// Sum all entries
228  T Sum();
229 
230  inline void operator=(const T &a);
231 
232  /// Copy data from a pointer. Size() elements are copied.
233  inline void Assign(const T *);
234 
235  // STL-like begin/end
236  inline T* begin() const { return (T*) data; }
237  inline T* end() const { return (T*) data + size; }
238 
239  long MemoryUsage() const { return Capacity() * sizeof(T); }
240 
241 private:
242  /// Array copy is not supported
244  /// Array copy is not supported
245  Array(const Array<T> &);
246 };
247 
248 template <class T>
249 inline bool operator==(const Array<T> &LHS, const Array<T> &RHS)
250 {
251  if ( LHS.Size() != RHS.Size() ) { return false; }
252  for (int i=0; i<LHS.Size(); i++)
253  if ( LHS[i] != RHS[i] ) { return false; }
254  return true;
255 }
256 
257 template <class T>
258 inline bool operator!=(const Array<T> &LHS, const Array<T> &RHS)
259 {
260  return !( LHS == RHS );
261 }
262 
263 template <class T>
264 class Array2D;
265 
266 template <class T>
267 void Swap(Array2D<T> &, Array2D<T> &);
268 
269 template <class T>
270 class Array2D
271 {
272 private:
273  friend void Swap<T>(Array2D<T> &, Array2D<T> &);
274 
275  Array<T> array1d;
276  int N;
277 
278 public:
279  Array2D() { N = 0; }
280  Array2D(int m, int n) : array1d(m*n) { N = n; }
281 
282  void SetSize(int m, int n) { array1d.SetSize(m*n); N = n; }
283 
284  int NumRows() const { return array1d.Size()/N; }
285  int NumCols() const { return N; }
286 
287  inline const T &operator()(int i, int j) const;
288  inline T &operator()(int i, int j);
289 
290  inline const T *operator[](int i) const;
291  inline T *operator[](int i);
292 
293  const T *operator()(int i) const { return (*this)[i]; }
294  T *operator()(int i) { return (*this)[i]; }
295 
296  const T *GetRow(int i) const { return (*this)[i]; }
297  T *GetRow(int i) { return (*this)[i]; }
298 
299  void Copy(Array2D &copy) const
300  { copy.N = N; array1d.Copy(copy.array1d); }
301 
302  inline void operator=(const T &a)
303  { array1d = a; }
304 
305  /// Make this Array a reference to 'master'
306  inline void MakeRef(const Array2D &master)
307  { N = master.N; array1d.MakeRef(master.array1d);}
308 };
309 
310 
311 template <class T>
312 class Array3D
313 {
314 private:
315  Array<T> array1d;
316  int N2, N3;
317 
318 public:
319  Array3D() { N2 = N3 = 0; }
320  Array3D(int n1, int n2, int n3)
321  : array1d(n1*n2*n3) { N2 = n2; N3 = n3; }
322 
323  void SetSize(int n1, int n2, int n3)
324  { array1d.SetSize(n1*n2*n3); N2 = n2; N3 = n3; }
325 
326  inline const T &operator()(int i, int j, int k) const;
327  inline T &operator()(int i, int j, int k);
328 };
329 
330 
331 template <class T>
332 inline void Swap(T &a, T &b)
333 {
334  T c = a;
335  a = b;
336  b = c;
337 }
338 
339 template <class T>
340 inline void Swap(Array<T> &a, Array<T> &b)
341 {
342  Swap(a.data, b.data);
343  Swap(a.size, b.size);
344  Swap(a.allocsize, b.allocsize);
345  Swap(a.inc, b.inc);
346 }
347 
348 template <class T>
349 inline void Array<T>::SetSize(int nsize)
350 {
351  MFEM_ASSERT( nsize>=0, "Size must be non-negative. It is " << nsize );
352  if (nsize > abs(allocsize))
353  {
354  GrowSize(nsize, sizeof(T));
355  }
356  size = nsize;
357 }
358 
359 template <class T>
360 inline void Array<T>::SetSize(int nsize, const T &initval)
361 {
362  MFEM_ASSERT( nsize>=0, "Size must be non-negative. It is " << nsize );
363  if (nsize > size)
364  {
365  if (nsize > abs(allocsize))
366  {
367  GrowSize(nsize, sizeof(T));
368  }
369  for (int i = size; i < nsize; i++)
370  {
371  ((T*)data)[i] = initval;
372  }
373  }
374  size = nsize;
375 }
376 
377 template <class T>
378 inline T &Array<T>::operator[](int i)
379 {
380  MFEM_ASSERT( i>=0 && i<size,
381  "Access element " << i << " of array, size = " << size );
382  return ((T*)data)[i];
383 }
384 
385 template <class T>
386 inline const T &Array<T>::operator[](int i) const
387 {
388  MFEM_ASSERT( i>=0 && i<size,
389  "Access element " << i << " of array, size = " << size );
390  return ((T*)data)[i];
391 }
392 
393 template <class T>
394 inline int Array<T>::Append(const T &el)
395 {
396  SetSize(size+1);
397  ((T*)data)[size-1] = el;
398  return size;
399 }
400 
401 template <class T>
402 inline int Array<T>::Append(const Array<T> & els)
403 {
404  int old_size = size;
405 
406  SetSize(size + els.Size());
407  for (int i = 0; i < els.Size(); i++)
408  {
409  ((T*)data)[old_size+i] = els[i];
410  }
411  return size;
412 }
413 
414 
415 template <class T>
416 inline int Array<T>::Prepend(const T &el)
417 {
418  SetSize(size+1);
419  for (int i = size-1; i > 0; i--)
420  {
421  ((T*)data)[i] = ((T*)data)[i-1];
422  }
423  ((T*)data)[0] = el;
424  return size;
425 }
426 
427 
428 template <class T>
429 inline T &Array<T>::Last()
430 {
431  MFEM_ASSERT(size > 0, "Array size is zero: " << size);
432  return ((T*)data)[size-1];
433 }
434 
435 template <class T>
436 inline const T &Array<T>::Last() const
437 {
438  MFEM_ASSERT(size > 0, "Array size is zero: " << size);
439  return ((T*)data)[size-1];
440 }
441 
442 template <class T>
443 inline int Array<T>::Union(const T &el)
444 {
445  int i = 0;
446  while ((i < size) && (((T*)data)[i] != el)) { i++; }
447  if (i == size)
448  {
449  Append(el);
450  }
451  return i;
452 }
453 
454 template <class T>
455 inline int Array<T>::Find(const T &el) const
456 {
457  for (int i = 0; i < size; i++)
458  if (((T*)data)[i] == el)
459  {
460  return i;
461  }
462  return -1;
463 }
464 
465 template <class T>
466 inline void Array<T>::DeleteFirst(const T &el)
467 {
468  for (int i = 0; i < size; i++)
469  if (((T*)data)[i] == el)
470  {
471  for (i++; i < size; i++)
472  {
473  ((T*)data)[i-1] = ((T*)data)[i];
474  }
475  size--;
476  return;
477  }
478 }
479 
480 template <class T>
481 inline void Array<T>::DeleteAll()
482 {
483  if (allocsize > 0)
484  {
485  delete [] (char*)data;
486  }
487  data = NULL;
488  size = allocsize = 0;
489 }
490 
491 template <class T>
492 inline void Array<T>::MakeRef(T *p, int s)
493 {
494  if (allocsize > 0)
495  {
496  delete [] (char*)data;
497  }
498  data = p;
499  size = s;
500  allocsize = -s;
501 }
502 
503 template <class T>
504 inline void Array<T>::MakeRef(const Array &master)
505 {
506  if (allocsize > 0)
507  {
508  delete [] (char*)data;
509  }
510  data = master.data;
511  size = master.size;
512  allocsize = -abs(master.allocsize);
513  inc = master.inc;
514 }
515 
516 template <class T>
517 inline void Array<T>::GetSubArray(int offset, int sa_size, Array<T> &sa)
518 {
519  sa.SetSize(sa_size);
520  for (int i = 0; i < sa_size; i++)
521  {
522  sa[i] = (*this)[offset+i];
523  }
524 }
525 
526 template <class T>
527 inline void Array<T>::operator=(const T &a)
528 {
529  for (int i = 0; i < size; i++)
530  {
531  ((T*)data)[i] = a;
532  }
533 }
534 
535 template <class T>
536 inline void Array<T>::Assign(const T *p)
537 {
538  memcpy(data, p, Size()*sizeof(T));
539 }
540 
541 
542 template <class T>
543 inline const T &Array2D<T>::operator()(int i, int j) const
544 {
545  MFEM_ASSERT( i>=0 && i< array1d.Size()/N && j>=0 && j<N,
546  "Array2D: invalid access of element (" << i << ',' << j
547  << ") in array of size (" << array1d.Size()/N << ',' << N
548  << ")." );
549  return array1d[i*N+j];
550 }
551 
552 template <class T>
553 inline T &Array2D<T>::operator()(int i, int j)
554 {
555  MFEM_ASSERT( i>=0 && i< array1d.Size()/N && j>=0 && j<N,
556  "Array2D: invalid access of element (" << i << ',' << j
557  << ") in array of size (" << array1d.Size()/N << ',' << N
558  << ")." );
559  return array1d[i*N+j];
560 }
561 
562 template <class T>
563 inline const T *Array2D<T>::operator[](int i) const
564 {
565  MFEM_ASSERT( i>=0 && i< array1d.Size()/N,
566  "Array2D: invalid access of row " << i << " in array with "
567  << array1d.Size()/N << " rows.");
568  return &array1d[i*N];
569 }
570 
571 template <class T>
572 inline T *Array2D<T>::operator[](int i)
573 {
574  MFEM_ASSERT( i>=0 && i< array1d.Size()/N,
575  "Array2D: invalid access of row " << i << " in array with "
576  << array1d.Size()/N << " rows.");
577  return &array1d[i*N];
578 }
579 
580 
581 template <class T>
582 inline void Swap(Array2D<T> &a, Array2D<T> &b)
583 {
584  Swap(a.array1d, b.array1d);
585  Swap(a.N, b.N);
586 }
587 
588 
589 template <class T>
590 inline const T &Array3D<T>::operator()(int i, int j, int k) const
591 {
592  MFEM_ASSERT(i >= 0 && i < array1d.Size() / N2 / N3 && j >= 0 && j < N2
593  && k >= 0 && k < N3,
594  "Array3D: invalid access of element ("
595  << i << ',' << j << ',' << k << ") in array of size ("
596  << array1d.Size() / N2 / N3 << ',' << N2 << ',' << N3 << ").");
597  return array1d[(i*N2+j)*N3+k];
598 }
599 
600 template <class T>
601 inline T &Array3D<T>::operator()(int i, int j, int k)
602 {
603  MFEM_ASSERT(i >= 0 && i < array1d.Size() / N2 / N3 && j >= 0 && j < N2
604  && k >= 0 && k < N3,
605  "Array3D: invalid access of element ("
606  << i << ',' << j << ',' << k << ") in array of size ("
607  << array1d.Size() / N2 / N3 << ',' << N2 << ',' << N3 << ").");
608  return array1d[(i*N2+j)*N3+k];
609 }
610 
611 }
612 
613 #endif
int Size() const
Logical size of the array.
Definition: array.hpp:109
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:93
void Unique()
Definition: array.hpp:215
int NumCols() const
Definition: array.hpp:285
~BaseArray()
Free the allocated memory.
Definition: array.cpp:35
const T * operator()(int i) const
Definition: array.hpp:293
void * data
Pointer to data.
Definition: array.hpp:31
Array(T *_data, int asize, int ainc=0)
Definition: array.hpp:78
T * GetRow(int i)
Definition: array.hpp:297
Base class for array container.
Definition: array.hpp:27
void Copy(Array &copy) const
Create a copy of the current array.
Definition: array.hpp:160
T * GetData()
Returns the data.
Definition: array.hpp:91
T * operator()(int i)
Definition: array.hpp:294
void operator=(const T &a)
Definition: array.hpp:302
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:80
void Sort(Compare cmp)
Sorts the array using the supplied comparison function object.
Definition: array.hpp:211
void operator=(const T &a)
Definition: array.hpp:527
T Sum()
Sum all entries.
Definition: array.cpp:151
void MakeRef(const Array2D &master)
Make this Array a reference to &#39;master&#39;.
Definition: array.hpp:306
T * end() const
Definition: array.hpp:237
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:195
T * begin() const
Definition: array.hpp:236
void DeleteFirst(const T &el)
Delete the first &#39;el&#39; entry.
Definition: array.hpp:466
void SetSize(int n1, int n2, int n3)
Definition: array.hpp:323
T Min() const
Find the minimal element in the array, using the comparison operator &lt; for class T.
Definition: array.cpp:123
void DeleteAll()
Delete whole array.
Definition: array.hpp:481
void GrowSize(int minsize, int elementsize)
Definition: array.cpp:43
~Array()
Destructor.
Definition: array.hpp:82
void GetSubArray(int offset, int sa_size, Array< T > &sa)
Definition: array.hpp:517
int size
Size of the array.
Definition: array.hpp:33
void SetSize(int m, int n)
Definition: array.hpp:282
void Copy(Array2D &copy) const
Definition: array.hpp:299
bool OwnsData() const
Return true if the data will be deleted by the array.
Definition: array.hpp:96
const T & operator()(int i, int j) const
Definition: array.hpp:543
const T * GetData() const
Returns the data.
Definition: array.hpp:93
int Append(const T &el)
Append element to array, resize if necessary.
Definition: array.hpp:394
T & operator[](int i)
Access element.
Definition: array.hpp:378
void LoseData()
NULL-ifies the data.
Definition: array.hpp:103
T Max() const
Find the maximal element in the array, using the comparison operator &lt; for class T.
Definition: array.cpp:108
void MakeDataOwner()
Make the Array own the data.
Definition: array.hpp:106
void Reserve(int capacity)
Ensures that the allocated size is at least the given size.
Definition: array.hpp:122
bool operator!=(const Array< T > &LHS, const Array< T > &RHS)
Definition: array.hpp:258
void Assign(const T *)
Copy data from a pointer. Size() elements are copied.
Definition: array.hpp:536
long MemoryUsage() const
Definition: array.hpp:239
void Sort()
Sorts the array. This requires operator&lt; to be defined for T.
Definition: array.hpp:207
int allocsize
Size of the allocated memory.
Definition: array.hpp:35
void StealData(T **p)
Changes the ownership of the data.
Definition: array.hpp:99
int Union(const T &el)
Append element when it is not yet in the array, return index.
Definition: array.hpp:443
void Print(std::ostream &out=std::cout, int width=4)
Prints array to stream with width elements per row.
Definition: array.cpp:63
void Swap(Array< T > &, Array< T > &)
Definition: array.hpp:340
bool operator==(const Array< T > &LHS, const Array< T > &RHS)
Definition: array.hpp:249
int IsSorted()
return true if the array is sorted.
Definition: array.cpp:163
int Find(const T &el) const
Return the first index where &#39;el&#39; is found; return -1 if not found.
Definition: array.hpp:455
void SetSize(int nsize)
Change logical size of the array, keep existing entries.
Definition: array.hpp:349
const T * operator[](int i) const
Definition: array.hpp:563
void PartialSum()
Partial Sum.
Definition: array.cpp:139
void DeleteLast()
Delete the last entry.
Definition: array.hpp:151
Array2D(int m, int n)
Definition: array.hpp:280
int Capacity() const
Definition: array.hpp:119
T & Last()
Return the last element in the array.
Definition: array.hpp:429
void MakeRef(T *, int)
Make this Array a reference to a pointer.
Definition: array.hpp:492
const T & operator()(int i, int j, int k) const
Definition: array.hpp:590
Array3D(int n1, int n2, int n3)
Definition: array.hpp:320
Array(int asize=0, int ainc=0)
Creates array of asize elements.
Definition: array.hpp:72
const T * GetRow(int i) const
Definition: array.hpp:296
int NumRows() const
Definition: array.hpp:284
int Prepend(const T &el)
Prepend an element to the array, resize if necessary.
Definition: array.hpp:416