25 #ifndef EIGEN_RANDOMSETTER_H
26 #define EIGEN_RANDOMSETTER_H
37 typedef std::map<KeyType,Scalar> Type;
42 static void setInvalidKey(Type&,
const KeyType&) {}
45 #ifdef EIGEN_UNORDERED_MAP_SUPPORT
62 template<
typename Scalar>
struct StdUnorderedMapTraits
65 typedef std::unordered_map<KeyType,Scalar>
Type;
70 static void setInvalidKey(
Type&,
const KeyType&) {}
72 #endif // EIGEN_UNORDERED_MAP_SUPPORT
74 #ifdef _DENSE_HASH_MAP_H_
79 template<
typename Scalar>
struct GoogleDenseHashMapTraits
82 typedef google::dense_hash_map<KeyType,Scalar>
Type;
87 static void setInvalidKey(
Type& map,
const KeyType& k)
88 { map.set_empty_key(k); }
92 #ifdef _SPARSE_HASH_MAP_H_
97 template<
typename Scalar>
struct GoogleSparseHashMapTraits
100 typedef google::sparse_hash_map<KeyType,Scalar>
Type;
105 static void setInvalidKey(
Type&,
const KeyType&) {}
159 template<
typename SparseMatrixType,
160 template <
typename T>
class MapTraits =
161 #if defined _DENSE_HASH_MAP_H_
162 GoogleDenseHashMapTraits
163 #elif defined _HASH_MAP
168 ,
int OuterPacketBits = 6>
171 typedef typename SparseMatrixType::Scalar Scalar;
172 typedef typename SparseMatrixType::Index Index;
176 ScalarWrapper() : value(0) {}
179 typedef typename MapTraits<ScalarWrapper>::KeyType KeyType;
180 typedef typename MapTraits<ScalarWrapper>::Type HashMapType;
181 static const int OuterPacketMask = (1 << OuterPacketBits) - 1;
183 SwapStorage = 1 - MapTraits<ScalarWrapper>::IsSorted,
184 TargetRowMajor = (SparseMatrixType::Flags &
RowMajorBit) ? 1 : 0,
185 SetterRowMajor = SwapStorage ? 1-TargetRowMajor : TargetRowMajor
199 const Index outerSize = SwapStorage ? target.innerSize() : target.outerSize();
200 const Index innerSize = SwapStorage ? target.outerSize() : target.innerSize();
201 m_outerPackets = outerSize >> OuterPacketBits;
202 if (outerSize&OuterPacketMask)
204 m_hashmaps =
new HashMapType[m_outerPackets];
206 Index aux = innerSize - 1;
213 KeyType ik = (1<<(OuterPacketBits+m_keyBitsOffset));
214 for (Index k=0; k<m_outerPackets; ++k)
215 MapTraits<ScalarWrapper>::setInvalidKey(m_hashmaps[k],ik);
218 for (Index j=0; j<mp_target->outerSize(); ++j)
219 for (
typename SparseMatrixType::InnerIterator it(*mp_target,j); it; ++it)
220 (*
this)(TargetRowMajor?j:it.index(), TargetRowMajor?it.index():j) = it.value();
226 KeyType keyBitsMask = (1<<m_keyBitsOffset)-1;
229 mp_target->setZero();
230 mp_target->makeCompressed();
232 Index prevOuter = -1;
233 for (Index k=0; k<m_outerPackets; ++k)
235 const Index outerOffset = (1<<OuterPacketBits) * k;
236 typename HashMapType::iterator end = m_hashmaps[k].end();
237 for (
typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
239 const Index outer = (it->first >> m_keyBitsOffset) + outerOffset;
240 const Index inner = it->first & keyBitsMask;
241 if (prevOuter!=outer)
243 for (Index j=prevOuter+1;j<=outer;++j)
244 mp_target->startVec(j);
247 mp_target->insertBackByOuterInner(outer, inner) = it->second.value;
250 mp_target->finalize();
254 VectorXi positions(mp_target->outerSize());
257 for (Index k=0; k<m_outerPackets; ++k)
259 typename HashMapType::iterator end = m_hashmaps[k].end();
260 for (
typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
262 const Index outer = it->first & keyBitsMask;
268 for (Index j=0; j<mp_target->outerSize(); ++j)
270 Index tmp = positions[j];
271 mp_target->outerIndexPtr()[j] = count;
272 positions[j] = count;
275 mp_target->makeCompressed();
276 mp_target->outerIndexPtr()[mp_target->outerSize()] = count;
277 mp_target->resizeNonZeros(count);
279 for (Index k=0; k<m_outerPackets; ++k)
281 const Index outerOffset = (1<<OuterPacketBits) * k;
282 typename HashMapType::iterator end = m_hashmaps[k].end();
283 for (
typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
285 const Index inner = (it->first >> m_keyBitsOffset) + outerOffset;
286 const Index outer = it->first & keyBitsMask;
291 Index posStart = mp_target->outerIndexPtr()[outer];
292 Index i = (positions[outer]++) - 1;
293 while ( (i >= posStart) && (mp_target->innerIndexPtr()[i] > inner) )
295 mp_target->valuePtr()[i+1] = mp_target->valuePtr()[i];
296 mp_target->innerIndexPtr()[i+1] = mp_target->innerIndexPtr()[i];
299 mp_target->innerIndexPtr()[i+1] = inner;
300 mp_target->valuePtr()[i+1] = it->second.value;
310 const Index outer = SetterRowMajor ? row : col;
311 const Index inner = SetterRowMajor ? col : row;
312 const Index outerMajor = outer >> OuterPacketBits;
313 const Index outerMinor = outer & OuterPacketMask;
314 const KeyType key = (KeyType(outerMinor)<<m_keyBitsOffset) | inner;
315 return m_hashmaps[outerMajor][key].value;
326 for (Index k=0; k<m_outerPackets; ++k)
327 nz += static_cast<Index>(m_hashmaps[k].size());
334 HashMapType* m_hashmaps;
335 SparseMatrixType* mp_target;
336 Index m_outerPackets;
337 unsigned char m_keyBitsOffset;
342 #endif // EIGEN_RANDOMSETTER_H