Please, help us to better know about our user community by answering the following short survey: https://forms.gle/wpyrxWi18ox9Z5ae9
 
Loading...
Searching...
No Matches
RandomSetter.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9
10#ifndef EIGEN_RANDOMSETTER_H
11#define EIGEN_RANDOMSETTER_H
12
13#if defined(EIGEN_GOOGLEHASH_SUPPORT)
14// Ensure the ::google namespace exists, required for checking existence of
15// ::google::dense_hash_map and ::google::sparse_hash_map.
16namespace google {}
17#endif
18
19namespace Eigen {
20
25template<typename Scalar> struct StdMapTraits
26{
27 typedef int KeyType;
28 typedef std::map<KeyType,Scalar> Type;
29 enum {
30 IsSorted = 1
31 };
32
33 static void setInvalidKey(Type&, const KeyType&) {}
34};
35
36#ifdef EIGEN_UNORDERED_MAP_SUPPORT
53template<typename Scalar> struct StdUnorderedMapTraits
54{
55 typedef int KeyType;
56 typedef std::unordered_map<KeyType,Scalar> Type;
57 enum {
58 IsSorted = 0
59 };
60
61 static void setInvalidKey(Type&, const KeyType&) {}
62};
63#endif // EIGEN_UNORDERED_MAP_SUPPORT
64
65#if defined(EIGEN_GOOGLEHASH_SUPPORT)
66
67namespace google {
68
69// Namespace work-around, since sometimes dense_hash_map and sparse_hash_map
70// are in the global namespace, and other times they are under ::google.
71using namespace ::google;
72
73template<typename KeyType, typename Scalar>
74struct DenseHashMap {
75 typedef dense_hash_map<KeyType, Scalar> type;
76};
77
78template<typename KeyType, typename Scalar>
79struct SparseHashMap {
80 typedef sparse_hash_map<KeyType, Scalar> type;
81};
82
83} // namespace google
84
89template<typename Scalar> struct GoogleDenseHashMapTraits
90{
91 typedef int KeyType;
92 typedef typename google::DenseHashMap<KeyType,Scalar>::type Type;
93 enum {
94 IsSorted = 0
95 };
96
97 static void setInvalidKey(Type& map, const KeyType& k)
98 { map.set_empty_key(k); }
99};
100
105template<typename Scalar> struct GoogleSparseHashMapTraits
106{
107 typedef int KeyType;
108 typedef typename google::SparseHashMap<KeyType,Scalar>::type Type;
109 enum {
110 IsSorted = 0
111 };
112
113 static void setInvalidKey(Type&, const KeyType&) {}
114};
115#endif
116
166template<typename SparseMatrixType,
167 template <typename T> class MapTraits =
168#if defined(EIGEN_GOOGLEHASH_SUPPORT)
169 GoogleDenseHashMapTraits
170#elif defined(_HASH_MAP)
171 GnuHashMapTraits
172#else
173 StdMapTraits
174#endif
175 ,int OuterPacketBits = 6>
177{
178 typedef typename SparseMatrixType::Scalar Scalar;
179 typedef typename SparseMatrixType::StorageIndex StorageIndex;
180
181 struct ScalarWrapper
182 {
183 ScalarWrapper() : value(0) {}
184 Scalar value;
185 };
186 typedef typename MapTraits<ScalarWrapper>::KeyType KeyType;
187 typedef typename MapTraits<ScalarWrapper>::Type HashMapType;
188 static const int OuterPacketMask = (1 << OuterPacketBits) - 1;
189 enum {
190 SwapStorage = 1 - MapTraits<ScalarWrapper>::IsSorted,
191 TargetRowMajor = (SparseMatrixType::Flags & RowMajorBit) ? 1 : 0,
192 SetterRowMajor = SwapStorage ? 1-TargetRowMajor : TargetRowMajor
193 };
194
195 public:
196
203 inline RandomSetter(SparseMatrixType& target)
204 : mp_target(&target)
205 {
206 const Index outerSize = SwapStorage ? target.innerSize() : target.outerSize();
207 const Index innerSize = SwapStorage ? target.outerSize() : target.innerSize();
208 m_outerPackets = outerSize >> OuterPacketBits;
209 if (outerSize&OuterPacketMask)
210 m_outerPackets += 1;
211 m_hashmaps = new HashMapType[m_outerPackets];
212 // compute number of bits needed to store inner indices
213 Index aux = innerSize - 1;
214 m_keyBitsOffset = 0;
215 while (aux)
216 {
217 ++m_keyBitsOffset;
218 aux = aux >> 1;
219 }
220 KeyType ik = (1<<(OuterPacketBits+m_keyBitsOffset));
221 for (Index k=0; k<m_outerPackets; ++k)
222 MapTraits<ScalarWrapper>::setInvalidKey(m_hashmaps[k],ik);
223
224 // insert current coeffs
225 for (Index j=0; j<mp_target->outerSize(); ++j)
226 for (typename SparseMatrixType::InnerIterator it(*mp_target,j); it; ++it)
227 (*this)(TargetRowMajor?j:it.index(), TargetRowMajor?it.index():j) = it.value();
228 }
229
232 {
233 KeyType keyBitsMask = (1<<m_keyBitsOffset)-1;
234 if (!SwapStorage) // also means the map is sorted
235 {
236 mp_target->setZero();
237 mp_target->makeCompressed();
238 mp_target->reserve(nonZeros());
239 Index prevOuter = -1;
240 for (Index k=0; k<m_outerPackets; ++k)
241 {
242 const Index outerOffset = (1<<OuterPacketBits) * k;
243 typename HashMapType::iterator end = m_hashmaps[k].end();
244 for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
245 {
246 const Index outer = (it->first >> m_keyBitsOffset) + outerOffset;
247 const Index inner = it->first & keyBitsMask;
248 if (prevOuter!=outer)
249 {
250 for (Index j=prevOuter+1;j<=outer;++j)
251 mp_target->startVec(j);
252 prevOuter = outer;
253 }
254 mp_target->insertBackByOuterInner(outer, inner) = it->second.value;
255 }
256 }
257 mp_target->finalize();
258 }
259 else
260 {
261 VectorXi positions(mp_target->outerSize());
262 positions.setZero();
263 // pass 1
264 for (Index k=0; k<m_outerPackets; ++k)
265 {
266 typename HashMapType::iterator end = m_hashmaps[k].end();
267 for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
268 {
269 const Index outer = it->first & keyBitsMask;
270 ++positions[outer];
271 }
272 }
273 // prefix sum
274 StorageIndex count = 0;
275 for (Index j=0; j<mp_target->outerSize(); ++j)
276 {
277 StorageIndex tmp = positions[j];
278 mp_target->outerIndexPtr()[j] = count;
279 positions[j] = count;
280 count += tmp;
281 }
282 mp_target->makeCompressed();
283 mp_target->outerIndexPtr()[mp_target->outerSize()] = count;
284 mp_target->resizeNonZeros(count);
285 // pass 2
286 for (Index k=0; k<m_outerPackets; ++k)
287 {
288 const Index outerOffset = (1<<OuterPacketBits) * k;
289 typename HashMapType::iterator end = m_hashmaps[k].end();
290 for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
291 {
292 const Index inner = (it->first >> m_keyBitsOffset) + outerOffset;
293 const Index outer = it->first & keyBitsMask;
294 // sorted insertion
295 // Note that we have to deal with at most 2^OuterPacketBits unsorted coefficients,
296 // moreover those 2^OuterPacketBits coeffs are likely to be sparse, an so only a
297 // small fraction of them have to be sorted, whence the following simple procedure:
298 Index posStart = mp_target->outerIndexPtr()[outer];
299 Index i = (positions[outer]++) - 1;
300 while ( (i >= posStart) && (mp_target->innerIndexPtr()[i] > inner) )
301 {
302 mp_target->valuePtr()[i+1] = mp_target->valuePtr()[i];
303 mp_target->innerIndexPtr()[i+1] = mp_target->innerIndexPtr()[i];
304 --i;
305 }
306 mp_target->innerIndexPtr()[i+1] = internal::convert_index<StorageIndex>(inner);
307 mp_target->valuePtr()[i+1] = it->second.value;
308 }
309 }
310 }
311 delete[] m_hashmaps;
312 }
313
315 Scalar& operator() (Index row, Index col)
316 {
317 const Index outer = SetterRowMajor ? row : col;
318 const Index inner = SetterRowMajor ? col : row;
319 const Index outerMajor = outer >> OuterPacketBits; // index of the packet/map
320 const Index outerMinor = outer & OuterPacketMask; // index of the inner vector in the packet
321 const KeyType key = internal::convert_index<KeyType>((outerMinor<<m_keyBitsOffset) | inner);
322 return m_hashmaps[outerMajor][key].value;
323 }
324
331 {
332 Index nz = 0;
333 for (Index k=0; k<m_outerPackets; ++k)
334 nz += static_cast<Index>(m_hashmaps[k].size());
335 return nz;
336 }
337
338
339 protected:
340
341 HashMapType* m_hashmaps;
342 SparseMatrixType* mp_target;
343 Index m_outerPackets;
344 unsigned char m_keyBitsOffset;
345};
346
347} // end namespace Eigen
348
349#endif // EIGEN_RANDOMSETTER_H
The RandomSetter is a wrapper object allowing to set/update a sparse matrix with random access.
Definition: RandomSetter.h:177
~RandomSetter()
Definition: RandomSetter.h:231
RandomSetter(SparseMatrixType &target)
Definition: RandomSetter.h:203
Scalar & operator()(Index row, Index col)
Definition: RandomSetter.h:315
Index nonZeros() const
Definition: RandomSetter.h:330
const unsigned int RowMajorBit
Namespace containing all symbols from the Eigen library.
EIGEN_DEFAULT_DENSE_INDEX_TYPE Index
Definition: RandomSetter.h:26