Block-Structured AMR Software Framework
AMReX_Vector.H
Go to the documentation of this file.
1 #ifndef AMREX_VECTOR_H_
2 #define AMREX_VECTOR_H_
3 #include <AMReX_Config.H>
4 
5 #include <AMReX_BLassert.H>
6 #include <AMReX_Extension.H>
7 #include <AMReX_INT.H>
8 #ifdef AMREX_SPACEDIM
9 #include <AMReX_Array.H>
10 #include <AMReX_TypeTraits.H>
11 #endif
12 
13 #include <algorithm>
14 #include <memory>
15 #include <vector>
16 
17 namespace amrex {
23 template <class T, class Allocator=std::allocator<T> >
24 class Vector
25  :
26  public std::vector<T, Allocator>
27 {
28 public:
29 
30  using std::vector<T, Allocator>::vector;
31  using typename std::vector<T, Allocator>::size_type;
32 
33  [[nodiscard]] T& operator[] (size_type i) noexcept
34  {
36  return this->std::vector<T, Allocator>::operator[](i);
37  }
38 
39  [[nodiscard]] const T& operator[] (size_type i) const noexcept
40  {
42  return this->std::vector<T, Allocator>::operator[](i);
43  }
44 
46  [[nodiscard]] T* dataPtr () noexcept { return this->data(); }
48  [[nodiscard]] const T* dataPtr () const noexcept { return this->data(); }
49 
50  [[nodiscard]] Long size () const noexcept {return static_cast<Long>(std::vector<T, Allocator>::size());}
51 
52 };
53 
54 }
55 
56 namespace amrex
57 {
59 
60  template <class T, typename = typename T::FABType>
61  [[nodiscard]] Vector<T*> GetVecOfPtrs (Vector<T>& a)
62  {
63  Vector<T*> r;
64  r.reserve(a.size());
65  for (auto& x : a) { r.push_back(&x); }
66  return r;
67  }
68 
69  template <class T>
70  [[nodiscard]] Vector<T*> GetVecOfPtrs (const Vector<std::unique_ptr<T> >& a)
71  {
72  Vector<T*> r;
73  r.reserve(a.size());
74  for (const auto& x : a) { r.push_back(x.get()); }
75  return r;
76  }
77 
79 
80  template <class T, typename = typename T::FABType>
81  [[nodiscard]] Vector<const T*> GetVecOfConstPtrs (const Vector<T>& a)
82  {
84  r.reserve(a.size());
85  for (const auto& x : a) { r.push_back(&x); }
86  return r;
87  }
88 
89  template <class T>
90  [[nodiscard]] Vector<const T*> GetVecOfConstPtrs (const Vector<std::unique_ptr<T> >& a)
91  {
93  r.reserve(a.size());
94  for (const auto& x : a) { r.push_back(x.get()); }
95  return r;
96  }
97 
98  template <class T, typename = typename T::FABType>
100  {
101  return {a.begin(), a.end()};
102  }
103 
105 
106  template <class T>
107  [[nodiscard]] Vector<Vector<T*> > GetVecOfVecOfPtrs (const Vector<Vector<std::unique_ptr<T> > >& a)
108  {
110  r.reserve(a.size());
111  for (const auto& x : a) { r.push_back(GetVecOfPtrs(x)); }
112  return r;
113  }
114 
116 
117 #ifdef AMREX_SPACEDIM
118  template <class T>
119  [[nodiscard]] Vector<std::array<T*,AMREX_SPACEDIM> >
120  GetVecOfArrOfPtrs (const Vector<std::array<std::unique_ptr<T>,AMREX_SPACEDIM> >& a)
121  {
123  r.reserve(a.size());
124  for (const auto& x : a) { r.push_back(GetArrOfPtrs(x)); }
125  return r;
126  }
127 
128  template <class T>
129  [[nodiscard]] Vector<std::array<T const*,AMREX_SPACEDIM> >
130  GetVecOfArrOfPtrsConst (const Vector<std::array<std::unique_ptr<T>,AMREX_SPACEDIM> >& a)
131  {
133  r.reserve(a.size());
134  for (const auto& x : a) { r.push_back(GetArrOfConstPtrs(x)); }
135  return r;
136  }
137 
138  template <class T>
139  [[nodiscard]] Vector<std::array<T const*,AMREX_SPACEDIM> >
140  GetVecOfArrOfConstPtrs (const Vector<std::array<std::unique_ptr<T>,AMREX_SPACEDIM> >& a)
141  {
143  r.reserve(a.size());
144  for (const auto& x : a) { r.push_back(GetArrOfConstPtrs(x)); }
145  return r;
146  }
147 
148  template <class T, std::enable_if_t<IsFabArray<T>::value ||
149  IsBaseFab<T>::value,
150  int> = 0 >
151  [[nodiscard]] Vector<std::array<T const*,AMREX_SPACEDIM> >
152  GetVecOfArrOfConstPtrs (const Vector<std::array<T,AMREX_SPACEDIM> >& a)
153  {
155  r.reserve(a.size());
156  for (const auto& x : a) { r.push_back(GetArrOfConstPtrs(x)); }
157  return r;
158  }
159 
160  template <class T, std::enable_if_t<IsFabArray<T>::value ||
161  IsBaseFab<T>::value,
162  int> = 0 >
163  [[nodiscard]] Vector<std::array<T*, AMREX_SPACEDIM> >
164  GetVecOfArrOfPtrs(Vector<std::array<T, AMREX_SPACEDIM> >& a)
165  {
167  r.reserve(a.size());
168  for (auto &x: a) { r.push_back(GetArrOfPtrs(x)); }
169  return r;
170  }
171 #endif
172 
174 
175  template <class T>
177  {
178  std::for_each(a.begin(), a.end(), [](T*& p) { p = nullptr; });
179  }
180 
181  template <class T>
182  void FillNull (Vector<std::unique_ptr<T> >& a)
183  {
184  std::for_each(a.begin(), a.end(), [](std::unique_ptr<T>& p) { p.reset(); });
185  }
186 
188 
189  template <class T>
191  std::sort(vec.begin(), vec.end());
192  auto it = std::unique(vec.begin(), vec.end());
193  vec.erase(it, vec.end());
194  }
195 
196  namespace detail {
197  template <class T, class H>
198  std::size_t removeDupDoit (Vector<T>& vec, std::size_t start, std::size_t stop)
199  {
200  std::size_t N = stop-start;
201  if (N < 2) { return stop; }
202 
203  T* const data = vec.data() + start;
204  T const sentinel = data[0]; // duplicates will be set to sentinel and removed later
205  H const hasher;
206  for (std::size_t i = 1; i < N; ) {
207  if (data[i] == sentinel) {
208  ++i;
209  continue;
210  }
211 
212  std::size_t const hash = hasher(data[i]) % N;
213  if (i == hash) { // data[i] in correct hash position
214  ++i;
215  continue;
216  }
217 
218  if (data[i] == data[hash]) {
219  data[i] = sentinel; // because it's a duplicate
220  ++i;
221  continue;
222  }
223 
224  if (data[hash] == sentinel) {
225  std::swap(data[hash], data[i]);
226  // after swap, new data[i] holds sentinel
227  // newdata[hash] in correct hash poitiion
228  ++i;
229  continue;
230  }
231 
232  std::size_t const hashhash = hasher(data[hash]) % N;
233  if (hashhash != hash) { // data[hash] not in correct has poision, thus will yield it's position
234  std::swap(data[i], data[hash]);
235  // after swap, new data[hash] in correct hash position
236  // new data[i] not sure
237  if (hash < i) { // we have seen new data[i]
238  ++i;
239  } // else next iteration we will work on data[i]
240  } else { // data[hash] in correct hash position, but data[i] is not because of hash collision
241  ++i;
242  }
243  }
244 
245  // Now there are three types for data[i]
246  // (1) sentinel
247  // (2) data[i] != sentinel and hash(data[i]) == i
248  // (3) data[i] != sentinel and hash(data[i]) != i because of hash collision
249  // All type 2s are unique, and all sentinels except one can be removed.
250  // We will move all type 2s to the beginning, all sentinels to the end.
251  // This will leave all type 3s in the middle. Then we will work on the middle
252  // part plus one sentinel.
253 
254  std::size_t swapPos = 0;
255  for (std::size_t i = 0; i < N; ++i) {
256  // move type 2 to the beginning pointed to by swapPos
257  if (data[i] != sentinel && i == hasher(data[i]) % N) {
258  std::swap(data[i], data[swapPos++]);
259  }
260  }
261 
262  // Now we have moved all type 2 elements to the beginning, [0,swapPos)
263 
264  std::size_t sentinelPos = N;
265  for (std::size_t i = swapPos; i < sentinelPos; ) {
266  // move type 1 to the end
267  if(data[i] == sentinel) {
268  std::swap(data[i], data[--sentinelPos]);
269  } else {
270  ++i;
271  }
272  }
273 
274  // recursively work on the middle part
275  return detail::removeDupDoit<T,H>(vec, start+swapPos, start+sentinelPos+1);
276  }
277  }
278 
279  template <class T, class H>
281  // https://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an-array
282  std::size_t pos = detail::removeDupDoit<T,H>(vec, 0, vec.size());
283  vec.erase(vec.begin()+pos, vec.end());
284  }
285 }
286 
287 #endif
#define BL_ASSERT(EX)
Definition: AMReX_BLassert.H:39
This class is a thin wrapper around std::vector. Unlike vector, Vector::operator[] provides bound che...
Definition: AMReX_Vector.H:27
T & operator[](size_type i) noexcept
Definition: AMReX_Vector.H:33
const T * dataPtr() const noexcept
get access to the underlying data pointer
Definition: AMReX_Vector.H:48
Long size() const noexcept
Definition: AMReX_Vector.H:50
T * dataPtr() noexcept
get access to the underlying data pointer
Definition: AMReX_Vector.H:46
AMREX_GPU_HOST_DEVICE Long size(T const &b) noexcept
integer version
Definition: AMReX_GpuRange.H:26
AMREX_GPU_HOST_DEVICE AMREX_FORCE_INLINE void swap(T &a, T &b) noexcept
Definition: AMReX_algoim_K.H:113
std::size_t removeDupDoit(Vector< T > &vec, std::size_t start, std::size_t stop)
Definition: AMReX_Vector.H:198
Definition: AMReX_Amr.cpp:49
std::array< T const *, AMREX_SPACEDIM > GetArrOfConstPtrs(const std::array< T, AMREX_SPACEDIM > &a) noexcept
Definition: AMReX_Array.H:864
Vector< const T * > GetVecOfConstPtrs(const Vector< T > &a)
Definition: AMReX_Vector.H:81
std::array< T *, AMREX_SPACEDIM > GetArrOfPtrs(std::array< T, AMREX_SPACEDIM > &a) noexcept
Definition: AMReX_Array.H:852
Vector< T * > GetVecOfPtrs(Vector< T > &a)
Definition: AMReX_Vector.H:61
Vector< Vector< T * > > GetVecOfVecOfPtrs(const Vector< Vector< std::unique_ptr< T > > > &a)
Definition: AMReX_Vector.H:107
void FillNull(Vector< T * > &a)
Definition: AMReX_Vector.H:176
Vector< std::array< T *, AMREX_SPACEDIM > > GetVecOfArrOfPtrs(const Vector< std::array< std::unique_ptr< T >, AMREX_SPACEDIM > > &a)
Definition: AMReX_Vector.H:120
Vector< std::array< T const *, AMREX_SPACEDIM > > GetVecOfArrOfConstPtrs(const Vector< std::array< std::unique_ptr< T >, AMREX_SPACEDIM > > &a)
Definition: AMReX_Vector.H:140
void RemoveDuplicates(Vector< T > &vec)
Definition: AMReX_Vector.H:190
Vector< std::array< T const *, AMREX_SPACEDIM > > GetVecOfArrOfPtrsConst(const Vector< std::array< std::unique_ptr< T >, AMREX_SPACEDIM > > &a)
Definition: AMReX_Vector.H:130
Definition: AMReX_FabArrayCommI.H:841