00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #ifndef EIGEN_RANDOMSETTER_H
00026 #define EIGEN_RANDOMSETTER_H
00027
00028 namespace Eigen {
00029
00034 template<typename Scalar> struct StdMapTraits
00035 {
00036 typedef int KeyType;
00037 typedef std::map<KeyType,Scalar> Type;
00038 enum {
00039 IsSorted = 1
00040 };
00041
00042 static void setInvalidKey(Type&, const KeyType&) {}
00043 };
00044
00045 #ifdef EIGEN_UNORDERED_MAP_SUPPORT
00046
00062 template<typename Scalar> struct StdUnorderedMapTraits
00063 {
00064 typedef int KeyType;
00065 typedef std::unordered_map<KeyType,Scalar> Type;
00066 enum {
00067 IsSorted = 0
00068 };
00069
00070 static void setInvalidKey(Type&, const KeyType&) {}
00071 };
00072 #endif // EIGEN_UNORDERED_MAP_SUPPORT
00073
00074 #ifdef _DENSE_HASH_MAP_H_
00075
00079 template<typename Scalar> struct GoogleDenseHashMapTraits
00080 {
00081 typedef int KeyType;
00082 typedef google::dense_hash_map<KeyType,Scalar> Type;
00083 enum {
00084 IsSorted = 0
00085 };
00086
00087 static void setInvalidKey(Type& map, const KeyType& k)
00088 { map.set_empty_key(k); }
00089 };
00090 #endif
00091
00092 #ifdef _SPARSE_HASH_MAP_H_
00093
00097 template<typename Scalar> struct GoogleSparseHashMapTraits
00098 {
00099 typedef int KeyType;
00100 typedef google::sparse_hash_map<KeyType,Scalar> Type;
00101 enum {
00102 IsSorted = 0
00103 };
00104
00105 static void setInvalidKey(Type&, const KeyType&) {}
00106 };
00107 #endif
00108
00159 template<typename SparseMatrixType,
00160 template <typename T> class MapTraits =
00161 #if defined _DENSE_HASH_MAP_H_
00162 GoogleDenseHashMapTraits
00163 #elif defined _HASH_MAP
00164 GnuHashMapTraits
00165 #else
00166 StdMapTraits
00167 #endif
00168 ,int OuterPacketBits = 6>
00169 class RandomSetter
00170 {
00171 typedef typename SparseMatrixType::Scalar Scalar;
00172 typedef typename SparseMatrixType::Index Index;
00173
00174 struct ScalarWrapper
00175 {
00176 ScalarWrapper() : value(0) {}
00177 Scalar value;
00178 };
00179 typedef typename MapTraits<ScalarWrapper>::KeyType KeyType;
00180 typedef typename MapTraits<ScalarWrapper>::Type HashMapType;
00181 static const int OuterPacketMask = (1 << OuterPacketBits) - 1;
00182 enum {
00183 SwapStorage = 1 - MapTraits<ScalarWrapper>::IsSorted,
00184 TargetRowMajor = (SparseMatrixType::Flags & RowMajorBit) ? 1 : 0,
00185 SetterRowMajor = SwapStorage ? 1-TargetRowMajor : TargetRowMajor
00186 };
00187
00188 public:
00189
00196 inline RandomSetter(SparseMatrixType& target)
00197 : mp_target(&target)
00198 {
00199 const Index outerSize = SwapStorage ? target.innerSize() : target.outerSize();
00200 const Index innerSize = SwapStorage ? target.outerSize() : target.innerSize();
00201 m_outerPackets = outerSize >> OuterPacketBits;
00202 if (outerSize&OuterPacketMask)
00203 m_outerPackets += 1;
00204 m_hashmaps = new HashMapType[m_outerPackets];
00205
00206 Index aux = innerSize - 1;
00207 m_keyBitsOffset = 0;
00208 while (aux)
00209 {
00210 ++m_keyBitsOffset;
00211 aux = aux >> 1;
00212 }
00213 KeyType ik = (1<<(OuterPacketBits+m_keyBitsOffset));
00214 for (Index k=0; k<m_outerPackets; ++k)
00215 MapTraits<ScalarWrapper>::setInvalidKey(m_hashmaps[k],ik);
00216
00217
00218 for (Index j=0; j<mp_target->outerSize(); ++j)
00219 for (typename SparseMatrixType::InnerIterator it(*mp_target,j); it; ++it)
00220 (*this)(TargetRowMajor?j:it.index(), TargetRowMajor?it.index():j) = it.value();
00221 }
00222
00224 ~RandomSetter()
00225 {
00226 KeyType keyBitsMask = (1<<m_keyBitsOffset)-1;
00227 if (!SwapStorage)
00228 {
00229 mp_target->setZero();
00230 mp_target->makeCompressed();
00231 mp_target->reserve(nonZeros());
00232 Index prevOuter = -1;
00233 for (Index k=0; k<m_outerPackets; ++k)
00234 {
00235 const Index outerOffset = (1<<OuterPacketBits) * k;
00236 typename HashMapType::iterator end = m_hashmaps[k].end();
00237 for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
00238 {
00239 const Index outer = (it->first >> m_keyBitsOffset) + outerOffset;
00240 const Index inner = it->first & keyBitsMask;
00241 if (prevOuter!=outer)
00242 {
00243 for (Index j=prevOuter+1;j<=outer;++j)
00244 mp_target->startVec(j);
00245 prevOuter = outer;
00246 }
00247 mp_target->insertBackByOuterInner(outer, inner) = it->second.value;
00248 }
00249 }
00250 mp_target->finalize();
00251 }
00252 else
00253 {
00254 VectorXi positions(mp_target->outerSize());
00255 positions.setZero();
00256
00257 for (Index k=0; k<m_outerPackets; ++k)
00258 {
00259 typename HashMapType::iterator end = m_hashmaps[k].end();
00260 for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
00261 {
00262 const Index outer = it->first & keyBitsMask;
00263 ++positions[outer];
00264 }
00265 }
00266
00267 Index count = 0;
00268 for (Index j=0; j<mp_target->outerSize(); ++j)
00269 {
00270 Index tmp = positions[j];
00271 mp_target->outerIndexPtr()[j] = count;
00272 positions[j] = count;
00273 count += tmp;
00274 }
00275 mp_target->makeCompressed();
00276 mp_target->outerIndexPtr()[mp_target->outerSize()] = count;
00277 mp_target->resizeNonZeros(count);
00278
00279 for (Index k=0; k<m_outerPackets; ++k)
00280 {
00281 const Index outerOffset = (1<<OuterPacketBits) * k;
00282 typename HashMapType::iterator end = m_hashmaps[k].end();
00283 for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
00284 {
00285 const Index inner = (it->first >> m_keyBitsOffset) + outerOffset;
00286 const Index outer = it->first & keyBitsMask;
00287
00288
00289
00290
00291 Index posStart = mp_target->outerIndexPtr()[outer];
00292 Index i = (positions[outer]++) - 1;
00293 while ( (i >= posStart) && (mp_target->innerIndexPtr()[i] > inner) )
00294 {
00295 mp_target->valuePtr()[i+1] = mp_target->valuePtr()[i];
00296 mp_target->innerIndexPtr()[i+1] = mp_target->innerIndexPtr()[i];
00297 --i;
00298 }
00299 mp_target->innerIndexPtr()[i+1] = inner;
00300 mp_target->valuePtr()[i+1] = it->second.value;
00301 }
00302 }
00303 }
00304 delete[] m_hashmaps;
00305 }
00306
00308 Scalar& operator() (Index row, Index col)
00309 {
00310 const Index outer = SetterRowMajor ? row : col;
00311 const Index inner = SetterRowMajor ? col : row;
00312 const Index outerMajor = outer >> OuterPacketBits;
00313 const Index outerMinor = outer & OuterPacketMask;
00314 const KeyType key = (KeyType(outerMinor)<<m_keyBitsOffset) | inner;
00315 return m_hashmaps[outerMajor][key].value;
00316 }
00317
00323 Index nonZeros() const
00324 {
00325 Index nz = 0;
00326 for (Index k=0; k<m_outerPackets; ++k)
00327 nz += static_cast<Index>(m_hashmaps[k].size());
00328 return nz;
00329 }
00330
00331
00332 protected:
00333
00334 HashMapType* m_hashmaps;
00335 SparseMatrixType* mp_target;
00336 Index m_outerPackets;
00337 unsigned char m_keyBitsOffset;
00338 };
00339
00340 }
00341
00342 #endif // EIGEN_RANDOMSETTER_H