RandomSetter.h
00001 // This file is part of Eigen, a lightweight C++ template library
00002 // for linear algebra.
00003 //
00004 // Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr>
00005 //
00006 // Eigen is free software; you can redistribute it and/or
00007 // modify it under the terms of the GNU Lesser General Public
00008 // License as published by the Free Software Foundation; either
00009 // version 3 of the License, or (at your option) any later version.
00010 //
00011 // Alternatively, you can redistribute it and/or
00012 // modify it under the terms of the GNU General Public License as
00013 // published by the Free Software Foundation; either version 2 of
00014 // the License, or (at your option) any later version.
00015 //
00016 // Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
00017 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00018 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
00019 // GNU General Public License for more details.
00020 //
00021 // You should have received a copy of the GNU Lesser General Public
00022 // License and a copy of the GNU General Public License along with
00023 // Eigen. If not, see <http://www.gnu.org/licenses/>.
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       // compute number of bits needed to store inner indices
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       // insert current coeffs
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) // also means the map is sorted
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         // pass 1
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         // prefix sum
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         // pass 2
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             // sorted insertion
00288             // Note that we have to deal with at most 2^OuterPacketBits unsorted coefficients,
00289             // moreover those 2^OuterPacketBits coeffs are likely to be sparse, an so only a
00290             // small fraction of them have to be sorted, whence the following simple procedure:
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; // index of the packet/map
00313       const Index outerMinor = outer & OuterPacketMask;  // index of the inner vector in the packet
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 } // end namespace Eigen
00341 
00342 #endif // EIGEN_RANDOMSETTER_H