Line data Source code
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 {
18 : /**
19 : * \brief This class is a thin wrapper around std::vector. Unlike vector,
20 : * Vector::operator[] provides bound checking when compiled with
21 : * DEBUG=TRUE.
22 : */
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 16886020 : [[nodiscard]] T& operator[] (size_type i) noexcept
34 : {
35 : BL_ASSERT( i < (this->std::vector<T, Allocator>::size()) );
36 16886020 : return this->std::vector<T, Allocator>::operator[](i);
37 : }
38 :
39 18634267 : [[nodiscard]] const T& operator[] (size_type i) const noexcept
40 : {
41 : BL_ASSERT( i < (this->std::vector<T, Allocator>::size()) );
42 18634267 : return this->std::vector<T, Allocator>::operator[](i);
43 : }
44 :
45 : //! get access to the underlying data pointer
46 0 : [[nodiscard]] T* dataPtr () noexcept { return this->data(); }
47 : //! get access to the underlying data pointer
48 : [[nodiscard]] const T* dataPtr () const noexcept { return this->data(); }
49 :
50 2165548 : [[nodiscard]] Long size () const noexcept {return static_cast<Long>(std::vector<T, Allocator>::size());}
51 :
52 : };
53 :
54 : }
55 :
56 : namespace amrex
57 : {
58 : /////////////////////////////////////////////////////////////
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 1034 : [[nodiscard]] Vector<T*> GetVecOfPtrs (const Vector<std::unique_ptr<T> >& a)
71 : {
72 1034 : Vector<T*> r;
73 1034 : r.reserve(a.size());
74 2134 : for (const auto& x : a) { r.push_back(x.get()); }
75 1034 : return r;
76 : }
77 :
78 : /////////////////////////////////////////////////////////////
79 :
80 : template <class T, typename = typename T::FABType>
81 166 : [[nodiscard]] Vector<const T*> GetVecOfConstPtrs (const Vector<T>& a)
82 : {
83 166 : Vector<const T*> r;
84 166 : r.reserve(a.size());
85 735 : for (const auto& x : a) { r.push_back(&x); }
86 166 : return r;
87 : }
88 :
89 : template <class T>
90 1030 : [[nodiscard]] Vector<const T*> GetVecOfConstPtrs (const Vector<std::unique_ptr<T> >& a)
91 : {
92 1030 : Vector<const T*> r;
93 1030 : r.reserve(a.size());
94 2116 : for (const auto& x : a) { r.push_back(x.get()); }
95 1030 : return r;
96 : }
97 :
98 : template <class T, typename = typename T::FABType>
99 0 : [[nodiscard]] Vector<const T*> GetVecOfConstPtrs (const Vector<T*>& a)
100 : {
101 0 : return {a.begin(), a.end()};
102 : }
103 :
104 : /////////////////////////////////////////////////////////////
105 :
106 : template <class T>
107 : [[nodiscard]] Vector<Vector<T*> > GetVecOfVecOfPtrs (const Vector<Vector<std::unique_ptr<T> > >& a)
108 : {
109 : Vector<Vector<T*> > r;
110 : r.reserve(a.size());
111 : for (const auto& x : a) { r.push_back(GetVecOfPtrs(x)); }
112 : return r;
113 : }
114 :
115 : /////////////////////////////////////////////////////////////
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 : {
122 : Vector<std::array<T*, AMREX_SPACEDIM> > r;
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 : {
132 : Vector<std::array<T const*, AMREX_SPACEDIM> > r;
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 : {
142 : Vector<std::array<T const*, AMREX_SPACEDIM> > r;
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 : {
154 : Vector<std::array<T const*, AMREX_SPACEDIM> > r;
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 : {
166 : Vector<std::array<T*, AMREX_SPACEDIM> > r;
167 : r.reserve(a.size());
168 : for (auto &x: a) { r.push_back(GetArrOfPtrs(x)); }
169 : return r;
170 : }
171 : #endif
172 :
173 : /////////////////////////////////////////////////////////////
174 :
175 : template <class T>
176 : void FillNull (Vector<T*>& a)
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 :
187 : /////////////////////////////////////////////////////////////
188 :
189 : template <class T>
190 : void RemoveDuplicates (Vector<T>& vec) {
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>
280 : void RemoveDuplicates (Vector<T>& vec) {
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
|
