RandomSetter.h
Go to the documentation of this file.
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 namespace Eigen {
14 
19 template<typename Scalar> struct StdMapTraits
20 {
21  typedef int KeyType;
22  typedef std::map<KeyType,Scalar> Type;
23  enum {
25  };
26 
27  static void setInvalidKey(Type&, const KeyType&) {}
28 };
29 
30 #ifdef EIGEN_UNORDERED_MAP_SUPPORT
31 
47 template<typename Scalar> struct StdUnorderedMapTraits
48 {
49  typedef int KeyType;
50  typedef std::unordered_map<KeyType,Scalar> Type;
51  enum {
52  IsSorted = 0
53  };
54 
55  static void setInvalidKey(Type&, const KeyType&) {}
56 };
57 #endif // EIGEN_UNORDERED_MAP_SUPPORT
58 
59 #ifdef _DENSE_HASH_MAP_H_
60 
64 template<typename Scalar> struct GoogleDenseHashMapTraits
65 {
66  typedef int KeyType;
67  typedef google::dense_hash_map<KeyType,Scalar> Type;
68  enum {
69  IsSorted = 0
70  };
71 
72  static void setInvalidKey(Type& map, const KeyType& k)
73  { map.set_empty_key(k); }
74 };
75 #endif
76 
77 #ifdef _SPARSE_HASH_MAP_H_
78 
82 template<typename Scalar> struct GoogleSparseHashMapTraits
83 {
84  typedef int KeyType;
85  typedef google::sparse_hash_map<KeyType,Scalar> Type;
86  enum {
87  IsSorted = 0
88  };
89 
90  static void setInvalidKey(Type&, const KeyType&) {}
91 };
92 #endif
93 
144 template<typename SparseMatrixType,
145  template <typename T> class MapTraits =
146 #if defined _DENSE_HASH_MAP_H_
147  GoogleDenseHashMapTraits
148 #elif defined _HASH_MAP
149  GnuHashMapTraits
150 #else
152 #endif
153  ,int OuterPacketBits = 6>
155 {
156  typedef typename SparseMatrixType::Scalar Scalar;
157  typedef typename SparseMatrixType::Index Index;
158 
160  {
161  ScalarWrapper() : value(0) {}
162  Scalar value;
163  };
164  typedef typename MapTraits<ScalarWrapper>::KeyType KeyType;
166  static const int OuterPacketMask = (1 << OuterPacketBits) - 1;
167  enum {
168  SwapStorage = 1 - MapTraits<ScalarWrapper>::IsSorted,
169  TargetRowMajor = (SparseMatrixType::Flags & RowMajorBit) ? 1 : 0,
170  SetterRowMajor = SwapStorage ? 1-TargetRowMajor : TargetRowMajor
171  };
172 
173  public:
174 
181  inline RandomSetter(SparseMatrixType& target)
182  : mp_target(&target)
183  {
184  const Index outerSize = SwapStorage ? target.innerSize() : target.outerSize();
185  const Index innerSize = SwapStorage ? target.outerSize() : target.innerSize();
186  m_outerPackets = outerSize >> OuterPacketBits;
187  if (outerSize&OuterPacketMask)
188  m_outerPackets += 1;
189  m_hashmaps = new HashMapType[m_outerPackets];
190  // compute number of bits needed to store inner indices
191  Index aux = innerSize - 1;
192  m_keyBitsOffset = 0;
193  while (aux)
194  {
195  ++m_keyBitsOffset;
196  aux = aux >> 1;
197  }
198  KeyType ik = (1<<(OuterPacketBits+m_keyBitsOffset));
199  for (Index k=0; k<m_outerPackets; ++k)
200  MapTraits<ScalarWrapper>::setInvalidKey(m_hashmaps[k],ik);
201 
202  // insert current coeffs
203  for (Index j=0; j<mp_target->outerSize(); ++j)
204  for (typename SparseMatrixType::InnerIterator it(*mp_target,j); it; ++it)
205  (*this)(TargetRowMajor?j:it.index(), TargetRowMajor?it.index():j) = it.value();
206  }
207 
210  {
211  KeyType keyBitsMask = (1<<m_keyBitsOffset)-1;
212  if (!SwapStorage) // also means the map is sorted
213  {
214  mp_target->setZero();
215  mp_target->makeCompressed();
216  mp_target->reserve(nonZeros());
217  Index prevOuter = -1;
218  for (Index k=0; k<m_outerPackets; ++k)
219  {
220  const Index outerOffset = (1<<OuterPacketBits) * k;
221  typename HashMapType::iterator end = m_hashmaps[k].end();
222  for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
223  {
224  const Index outer = (it->first >> m_keyBitsOffset) + outerOffset;
225  const Index inner = it->first & keyBitsMask;
226  if (prevOuter!=outer)
227  {
228  for (Index j=prevOuter+1;j<=outer;++j)
229  mp_target->startVec(j);
230  prevOuter = outer;
231  }
232  mp_target->insertBackByOuterInner(outer, inner) = it->second.value;
233  }
234  }
235  mp_target->finalize();
236  }
237  else
238  {
239  VectorXi positions(mp_target->outerSize());
240  positions.setZero();
241  // pass 1
242  for (Index k=0; k<m_outerPackets; ++k)
243  {
244  typename HashMapType::iterator end = m_hashmaps[k].end();
245  for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
246  {
247  const Index outer = it->first & keyBitsMask;
248  ++positions[outer];
249  }
250  }
251  // prefix sum
252  Index count = 0;
253  for (Index j=0; j<mp_target->outerSize(); ++j)
254  {
255  Index tmp = positions[j];
256  mp_target->outerIndexPtr()[j] = count;
257  positions[j] = count;
258  count += tmp;
259  }
260  mp_target->makeCompressed();
261  mp_target->outerIndexPtr()[mp_target->outerSize()] = count;
262  mp_target->resizeNonZeros(count);
263  // pass 2
264  for (Index k=0; k<m_outerPackets; ++k)
265  {
266  const Index outerOffset = (1<<OuterPacketBits) * k;
267  typename HashMapType::iterator end = m_hashmaps[k].end();
268  for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
269  {
270  const Index inner = (it->first >> m_keyBitsOffset) + outerOffset;
271  const Index outer = it->first & keyBitsMask;
272  // sorted insertion
273  // Note that we have to deal with at most 2^OuterPacketBits unsorted coefficients,
274  // moreover those 2^OuterPacketBits coeffs are likely to be sparse, an so only a
275  // small fraction of them have to be sorted, whence the following simple procedure:
276  Index posStart = mp_target->outerIndexPtr()[outer];
277  Index i = (positions[outer]++) - 1;
278  while ( (i >= posStart) && (mp_target->innerIndexPtr()[i] > inner) )
279  {
280  mp_target->valuePtr()[i+1] = mp_target->valuePtr()[i];
281  mp_target->innerIndexPtr()[i+1] = mp_target->innerIndexPtr()[i];
282  --i;
283  }
284  mp_target->innerIndexPtr()[i+1] = inner;
285  mp_target->valuePtr()[i+1] = it->second.value;
286  }
287  }
288  }
289  delete[] m_hashmaps;
290  }
291 
293  Scalar& operator() (Index row, Index col)
294  {
295  const Index outer = SetterRowMajor ? row : col;
296  const Index inner = SetterRowMajor ? col : row;
297  const Index outerMajor = outer >> OuterPacketBits; // index of the packet/map
298  const Index outerMinor = outer & OuterPacketMask; // index of the inner vector in the packet
299  const KeyType key = (KeyType(outerMinor)<<m_keyBitsOffset) | inner;
300  return m_hashmaps[outerMajor][key].value;
301  }
302 
308  Index nonZeros() const
309  {
310  Index nz = 0;
311  for (Index k=0; k<m_outerPackets; ++k)
312  nz += static_cast<Index>(m_hashmaps[k].size());
313  return nz;
314  }
315 
316 
317  protected:
318 
319  HashMapType* m_hashmaps;
320  SparseMatrixType* mp_target;
322  unsigned char m_keyBitsOffset;
323 };
324 
325 } // end namespace Eigen
326 
327 #endif // EIGEN_RANDOMSETTER_H
MapTraits< ScalarWrapper >::KeyType KeyType
Definition: RandomSetter.h:164
RandomSetter(SparseMatrixType &target)
Definition: RandomSetter.h:181
SparseMatrixType::Index Index
Definition: RandomSetter.h:157
unsigned char m_keyBitsOffset
Definition: RandomSetter.h:322
MapTraits< ScalarWrapper >::Type HashMapType
Definition: RandomSetter.h:165
static void setInvalidKey(Type &, const KeyType &)
Definition: RandomSetter.h:27
iterative scaling algorithm to equilibrate rows and column norms in matrices
Definition: matrix.hpp:471
SparseMatrixType::Scalar Scalar
Definition: RandomSetter.h:156
const unsigned int RowMajorBit
HashMapType * m_hashmaps
Definition: RandomSetter.h:319
Index nonZeros() const
Definition: RandomSetter.h:308
SparseMatrixType * mp_target
Definition: RandomSetter.h:320
RowXpr row(Index i)
Definition: BlockMethods.h:725
The RandomSetter is a wrapper object allowing to set/update a sparse matrix with random access...
Definition: RandomSetter.h:154
ColXpr col(Index i)
Definition: BlockMethods.h:708
std::map< KeyType, Scalar > Type
Definition: RandomSetter.h:22


acado
Author(s): Milan Vukov, Rien Quirynen
autogenerated on Mon Jun 10 2019 12:35:02