equal
deleted
inserted
replaced
245 /// \brief Map for storing values for the range \c [0..size-1] range keys |
245 /// \brief Map for storing values for the range \c [0..size-1] range keys |
246 /// |
246 /// |
247 /// The current map has the \c [0..size-1] keyset and the values |
247 /// The current map has the \c [0..size-1] keyset and the values |
248 /// are stored in a \c std::vector<T> container. It can be used with |
248 /// are stored in a \c std::vector<T> container. It can be used with |
249 /// some data structures, for example \c UnionFind, \c BinHeap, when |
249 /// some data structures, for example \c UnionFind, \c BinHeap, when |
250 /// the used items are small integer numbers. |
250 /// the used items are small integer numbers. |
|
251 /// |
|
252 /// \todo Revise its name |
251 template <typename T> |
253 template <typename T> |
252 class IntegerMap { |
254 class IntegerMap { |
253 |
255 |
254 template <typename T1> |
256 template <typename T1> |
255 friend class IntegerMap; |
257 friend class IntegerMap; |
344 inline IdentityMap<T> identityMap() { |
346 inline IdentityMap<T> identityMap() { |
345 return IdentityMap<T>(); |
347 return IdentityMap<T>(); |
346 } |
348 } |
347 |
349 |
348 |
350 |
349 ///Convert the \c Value of a map to another type. |
351 ///\brief Convert the \c Value of a map to another type using |
350 |
352 ///the default conversion. |
|
353 /// |
351 ///This \c concepts::ReadMap "read only map" |
354 ///This \c concepts::ReadMap "read only map" |
352 ///converts the \c Value of a maps to type \c T. |
355 ///converts the \c Value of a maps to type \c T. |
353 ///Its \c Key is inherited from \c M. |
356 ///Its \c Key is inherited from \c M. |
354 template <typename M, typename T> |
357 template <typename M, typename T> |
355 class ConvertMap : public MapBase<typename M::Key, T> { |
358 class ConvertMap : public MapBase<typename M::Key, T> { |
366 ConvertMap(const M &_m) : m(_m) {}; |
369 ConvertMap(const M &_m) : m(_m) {}; |
367 |
370 |
368 /// \brief The subscript operator. |
371 /// \brief The subscript operator. |
369 /// |
372 /// |
370 /// The subscript operator. |
373 /// The subscript operator. |
371 /// \param k The key |
|
372 /// \return The target of the arc |
|
373 Value operator[](const Key& k) const {return m[k];} |
374 Value operator[](const Key& k) const {return m[k];} |
374 }; |
375 }; |
375 |
376 |
376 ///Returns an \c ConvertMap class |
377 ///Returns an \c ConvertMap class |
377 |
378 |
386 |
387 |
387 ///This \c concepts::ReadMap "read only map" returns the simple |
388 ///This \c concepts::ReadMap "read only map" returns the simple |
388 ///wrapping of the given map. Sometimes the reference maps cannot be |
389 ///wrapping of the given map. Sometimes the reference maps cannot be |
389 ///combined with simple read maps. This map adaptor wraps the given |
390 ///combined with simple read maps. This map adaptor wraps the given |
390 ///map to simple read map. |
391 ///map to simple read map. |
|
392 /// |
|
393 /// \todo Revise the misleading name |
391 template<typename M> |
394 template<typename M> |
392 class SimpleMap : public MapBase<typename M::Key, typename M::Value> { |
395 class SimpleMap : public MapBase<typename M::Key, typename M::Value> { |
393 const M& m; |
396 const M& m; |
394 |
397 |
395 public: |
398 public: |
403 Value operator[](Key k) const {return m[k];} |
406 Value operator[](Key k) const {return m[k];} |
404 }; |
407 }; |
405 |
408 |
406 ///Simple writeable wrapping of the map |
409 ///Simple writeable wrapping of the map |
407 |
410 |
408 ///This \c concepts::ReadMap "read only map" returns the simple |
411 ///This \c concepts::WriteMap "write map" returns the simple |
409 ///wrapping of the given map. Sometimes the reference maps cannot be |
412 ///wrapping of the given map. Sometimes the reference maps cannot be |
410 ///combined with simple read-write maps. This map adaptor wraps the |
413 ///combined with simple read-write maps. This map adaptor wraps the |
411 ///given map to simple read-write map. |
414 ///given map to simple read-write map. |
|
415 /// |
|
416 /// \todo Revise the misleading name |
412 template<typename M> |
417 template<typename M> |
413 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> { |
418 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> { |
414 M& m; |
419 M& m; |
415 |
420 |
416 public: |
421 public: |
491 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; |
496 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; |
492 ///\e |
497 ///\e |
493 Value operator[](Key k) const {return m[k] + v;} |
498 Value operator[](Key k) const {return m[k] + v;} |
494 }; |
499 }; |
495 |
500 |
496 ///Shift a map with a constant. |
501 ///Shift a map with a constant. This map is also writable. |
497 |
502 |
498 ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the |
503 ///This \c concepts::ReadWriteMap "read-write map" returns the sum of the |
499 ///given map and a constant value. It makes also possible to write the map. |
504 ///given map and a constant value. It makes also possible to write the map. |
500 ///Its \c Key and \c Value is inherited from \c M. |
505 ///Its \c Key and \c Value is inherited from \c M. |
501 /// |
506 /// |
547 |
552 |
548 ///This \c concepts::ReadMap "read only map" returns the difference |
553 ///This \c concepts::ReadMap "read only map" returns the difference |
549 ///of the values of the two |
554 ///of the values of the two |
550 ///given maps. Its \c Key and \c Value will be inherited from \c M1. |
555 ///given maps. Its \c Key and \c Value will be inherited from \c M1. |
551 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. |
556 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. |
552 |
557 /// |
|
558 /// \todo Revise the misleading name |
553 template<typename M1, typename M2> |
559 template<typename M1, typename M2> |
554 class SubMap : public MapBase<typename M1::Key, typename M1::Value> { |
560 class SubMap : public MapBase<typename M1::Key, typename M1::Value> { |
555 const M1& m1; |
561 const M1& m1; |
556 const M2& m2; |
562 const M2& m2; |
557 public: |
563 public: |
639 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; |
645 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; |
640 /// \e |
646 /// \e |
641 Value operator[](Key k) const {return v * m[k];} |
647 Value operator[](Key k) const {return v * m[k];} |
642 }; |
648 }; |
643 |
649 |
644 ///Scales a maps with a constant. |
650 ///Scales a maps with a constant (ReadWrite version). |
645 |
651 |
646 ///This \c concepts::ReadWriteMap "read-write map" returns the value of the |
652 ///This \c concepts::ReadWriteMap "read-write map" returns the value of the |
647 ///given map multiplied from the left side with a constant value. It can |
653 ///given map multiplied from the left side with a constant value. It can |
648 ///be used as write map also if the given multiplier is not zero. |
654 ///be used as write map also if the given multiplier is not zero. |
649 ///Its \c Key and \c Value is inherited from \c M. |
655 ///Its \c Key and \c Value is inherited from \c M. |
856 NegMap(const M &_m) : m(_m) {}; |
862 NegMap(const M &_m) : m(_m) {}; |
857 /// \e |
863 /// \e |
858 Value operator[](Key k) const {return -m[k];} |
864 Value operator[](Key k) const {return -m[k];} |
859 }; |
865 }; |
860 |
866 |
861 ///Negative value of a map |
867 ///Negative value of a map (ReadWrite version) |
862 |
868 |
863 ///This \c concepts::ReadWriteMap "read-write map" returns the negative |
869 ///This \c concepts::ReadWriteMap "read-write map" returns the negative |
864 ///value of the value returned by the |
870 ///value of the value returned by the |
865 ///given map. Its \c Key and \c Value will be inherited from \c M. |
871 ///given map. Its \c Key and \c Value will be inherited from \c M. |
866 ///The unary \c - operator must be defined for \c Value, of course. |
872 ///The unary \c - operator must be defined for \c Value, of course. |
903 ///given map. Its \c Key and \c Value will be inherited |
909 ///given map. Its \c Key and \c Value will be inherited |
904 ///from <tt>M</tt>. <tt>Value</tt> |
910 ///from <tt>M</tt>. <tt>Value</tt> |
905 ///must be comparable to <tt>0</tt> and the unary <tt>-</tt> |
911 ///must be comparable to <tt>0</tt> and the unary <tt>-</tt> |
906 ///operator must be defined for it, of course. |
912 ///operator must be defined for it, of course. |
907 /// |
913 /// |
908 ///\bug We need a unified way to handle the situation below: |
|
909 ///\code |
|
910 /// struct _UnConvertible {}; |
|
911 /// template<class A> inline A t_abs(A a) {return _UnConvertible();} |
|
912 /// template<> inline int t_abs<>(int n) {return abs(n);} |
|
913 /// template<> inline long int t_abs<>(long int n) {return labs(n);} |
|
914 /// template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);} |
|
915 /// template<> inline float t_abs<>(float n) {return fabsf(n);} |
|
916 /// template<> inline double t_abs<>(double n) {return fabs(n);} |
|
917 /// template<> inline long double t_abs<>(long double n) {return fabsl(n);} |
|
918 ///\endcode |
|
919 |
|
920 |
914 |
921 template<typename M> |
915 template<typename M> |
922 class AbsMap : public MapBase<typename M::Key, typename M::Value> { |
916 class AbsMap : public MapBase<typename M::Key, typename M::Value> { |
923 const M& m; |
917 const M& m; |
924 public: |
918 public: |
1039 ///parameters and each read request will be passed just to the |
1033 ///parameters and each read request will be passed just to the |
1040 ///first map. This class is the just readable map type of the ForkWriteMap. |
1034 ///first map. This class is the just readable map type of the ForkWriteMap. |
1041 /// |
1035 /// |
1042 ///The \c Key and \c Value will be inherited from \c M1. |
1036 ///The \c Key and \c Value will be inherited from \c M1. |
1043 ///The \c Key and \c Value of M2 must be convertible from those of \c M1. |
1037 ///The \c Key and \c Value of M2 must be convertible from those of \c M1. |
|
1038 /// |
|
1039 /// \todo Why is it needed? |
1044 template<typename M1, typename M2> |
1040 template<typename M1, typename M2> |
1045 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> { |
1041 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> { |
1046 const M1& m1; |
1042 const M1& m1; |
1047 const M2& m2; |
1043 const M2& m2; |
1048 public: |
1044 public: |
1122 NotMap(const M &_m) : m(_m) {}; |
1118 NotMap(const M &_m) : m(_m) {}; |
1123 ///\e |
1119 ///\e |
1124 Value operator[](Key k) const {return !m[k];} |
1120 Value operator[](Key k) const {return !m[k];} |
1125 }; |
1121 }; |
1126 |
1122 |
1127 ///Logical 'not' of a map with writing possibility |
1123 ///Logical 'not' of a map (ReadWrie version) |
1128 |
1124 |
1129 ///This bool \c concepts::ReadWriteMap "read-write map" returns the |
1125 ///This bool \c concepts::ReadWriteMap "read-write map" returns the |
1130 ///logical negation of value returned by the given map. When it is set, |
1126 ///logical negation of value returned by the given map. When it is set, |
1131 ///the opposite value is set to the original map. |
1127 ///the opposite value is set to the original map. |
1132 ///Its \c Key and will be inherited from \c M, |
1128 ///Its \c Key and will be inherited from \c M, |
1185 }; |
1181 }; |
1186 |
1182 |
1187 } |
1183 } |
1188 |
1184 |
1189 |
1185 |
1190 /// \brief Writable bool map for store each true assigned elements. |
1186 /// \brief Writable bool map for logging each true assigned elements |
1191 /// |
1187 /// |
1192 /// Writable bool map to store each true assigned elements. It will |
1188 /// Writable bool map for logging each true assigned elements, i.e it |
1193 /// copies all the keys set to true to the given iterator. |
1189 /// copies all the keys set to true to the given iterator. |
1194 /// |
1190 /// |
1195 /// \note The container of the iterator should contain space |
1191 /// \note The container of the iterator should contain space |
1196 /// for each element. |
1192 /// for each element. |
1197 /// |
1193 /// |
1198 /// The next example shows how can you write the nodes directly |
1194 /// The following example shows how you can write the edges found by the Prim |
|
1195 /// algorithm directly |
1199 /// to the standard output. |
1196 /// to the standard output. |
1200 ///\code |
1197 ///\code |
1201 /// typedef IdMap<Graph, Edge> EdgeIdMap; |
1198 /// typedef IdMap<Graph, Edge> EdgeIdMap; |
1202 /// EdgeIdMap edgeId(graph); |
1199 /// EdgeIdMap edgeId(graph); |
1203 /// |
1200 /// |
1207 /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor> |
1204 /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor> |
1208 /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor); |
1205 /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor); |
1209 /// |
1206 /// |
1210 /// prim(graph, cost, writerMap); |
1207 /// prim(graph, cost, writerMap); |
1211 ///\endcode |
1208 ///\endcode |
|
1209 /// |
|
1210 ///\todo Revise the name of this class and the relates ones. |
1212 template <typename _Iterator, |
1211 template <typename _Iterator, |
1213 typename _Functor = |
1212 typename _Functor = |
1214 _maps_bits::Identity<typename _maps_bits:: |
1213 _maps_bits::Identity<typename _maps_bits:: |
1215 IteratorTraits<_Iterator>::Value> > |
1214 IteratorTraits<_Iterator>::Value> > |
1216 class StoreBoolMap { |
1215 class StoreBoolMap { |
1224 |
1223 |
1225 /// Constructor |
1224 /// Constructor |
1226 StoreBoolMap(Iterator it, const Functor& functor = Functor()) |
1225 StoreBoolMap(Iterator it, const Functor& functor = Functor()) |
1227 : _begin(it), _end(it), _functor(functor) {} |
1226 : _begin(it), _end(it), _functor(functor) {} |
1228 |
1227 |
1229 /// Gives back the given iterator set for the first time. |
1228 /// Gives back the given iterator set for the first key |
1230 Iterator begin() const { |
1229 Iterator begin() const { |
1231 return _begin; |
1230 return _begin; |
1232 } |
1231 } |
1233 |
1232 |
1234 /// Gives back the iterator after the last set operation. |
1233 /// Gives back the the 'after the last' iterator |
1235 Iterator end() const { |
1234 Iterator end() const { |
1236 return _end; |
1235 return _end; |
1237 } |
1236 } |
1238 |
1237 |
1239 /// Setter function of the map |
1238 /// Setter function of the map |
1247 Iterator _begin; |
1246 Iterator _begin; |
1248 mutable Iterator _end; |
1247 mutable Iterator _end; |
1249 Functor _functor; |
1248 Functor _functor; |
1250 }; |
1249 }; |
1251 |
1250 |
1252 /// \brief Writable bool map for store each true assigned elements in |
1251 /// \brief Writable bool map for logging each true assigned elements in |
1253 /// a back insertable container. |
1252 /// a back insertable container |
1254 /// |
1253 /// |
1255 /// Writable bool map for store each true assigned elements in a back |
1254 /// Writable bool map for logging each true assigned elements by pushing |
1256 /// insertable container. It will push back all the keys set to true into |
1255 /// back them into a back insertable container. |
1257 /// the container. It can be used to retrieve the items into a standard |
1256 /// It can be used to retrieve the items into a standard |
1258 /// container. The next example shows how can you store the undirected |
1257 /// container. The next example shows how you can store the |
1259 /// arcs in a vector with prim algorithm. |
1258 /// edges found by the Prim algorithm in a vector. |
1260 /// |
1259 /// |
1261 ///\code |
1260 ///\code |
1262 /// vector<Edge> span_tree_edges; |
1261 /// vector<Edge> span_tree_edges; |
1263 /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges); |
1262 /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges); |
1264 /// prim(graph, cost, inserter_map); |
1263 /// prim(graph, cost, inserter_map); |
1286 private: |
1285 private: |
1287 Container& container; |
1286 Container& container; |
1288 Functor functor; |
1287 Functor functor; |
1289 }; |
1288 }; |
1290 |
1289 |
1291 /// \brief Writable bool map for store each true assigned elements in |
1290 /// \brief Writable bool map for storing each true assignments in |
1292 /// a front insertable container. |
1291 /// a front insertable container. |
1293 /// |
1292 /// |
1294 /// Writable bool map for store each true assigned elements in a front |
1293 /// Writable bool map for storing each true assignment in a front |
1295 /// insertable container. It will push front all the keys set to \c true into |
1294 /// insertable container. It will push front all the keys set to \c true into |
1296 /// the container. For example see the BackInserterBoolMap. |
1295 /// the container. For example see the BackInserterBoolMap. |
1297 template <typename Container, |
1296 template <typename Container, |
1298 typename Functor = |
1297 typename Functor = |
1299 _maps_bits::Identity<typename Container::value_type> > |
1298 _maps_bits::Identity<typename Container::value_type> > |
1317 private: |
1316 private: |
1318 Container& container; |
1317 Container& container; |
1319 Functor functor; |
1318 Functor functor; |
1320 }; |
1319 }; |
1321 |
1320 |
1322 /// \brief Writable bool map for store each true assigned elements in |
1321 /// \brief Writable bool map for storing each true assigned elements in |
1323 /// an insertable container. |
1322 /// an insertable container. |
1324 /// |
1323 /// |
1325 /// Writable bool map for store each true assigned elements in an |
1324 /// Writable bool map for storing each true assigned elements in an |
1326 /// insertable container. It will insert all the keys set to \c true into |
1325 /// insertable container. It will insert all the keys set to \c true into |
1327 /// the container. If you want to store the cut arcs of the strongly |
1326 /// the container. |
|
1327 /// |
|
1328 /// For example, if you want to store the cut arcs of the strongly |
1328 /// connected components in a set you can use the next code: |
1329 /// connected components in a set you can use the next code: |
1329 /// |
1330 /// |
1330 ///\code |
1331 ///\code |
1331 /// set<Arc> cut_arcs; |
1332 /// set<Arc> cut_arcs; |
1332 /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs); |
1333 /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs); |
1367 /// |
1368 /// |
1368 /// Writable bool map to fill the elements set to \c true with a given value. |
1369 /// Writable bool map to fill the elements set to \c true with a given value. |
1369 /// The value can set |
1370 /// The value can set |
1370 /// the container. |
1371 /// the container. |
1371 /// |
1372 /// |
1372 /// The next code finds the connected components of the undirected digraph |
1373 /// The following code finds the connected components of a graph |
1373 /// and stores it in the \c comp map: |
1374 /// and stores it in the \c comp map: |
1374 ///\code |
1375 ///\code |
1375 /// typedef Graph::NodeMap<int> ComponentMap; |
1376 /// typedef Graph::NodeMap<int> ComponentMap; |
1376 /// ComponentMap comp(graph); |
1377 /// ComponentMap comp(graph); |
1377 /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap; |
1378 /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap; |
1415 /// Sets the current fill value |
1416 /// Sets the current fill value |
1416 void fillValue(const typename Map::Value& _fill) { |
1417 void fillValue(const typename Map::Value& _fill) { |
1417 fill = _fill; |
1418 fill = _fill; |
1418 } |
1419 } |
1419 |
1420 |
1420 /// Setter function of the map |
1421 /// Set function of the map |
1421 void set(const Key& key, Value value) { |
1422 void set(const Key& key, Value value) { |
1422 if (value) { |
1423 if (value) { |
1423 map.set(key, fill); |
1424 map.set(key, fill); |
1424 } |
1425 } |
1425 } |
1426 } |
1428 Map& map; |
1429 Map& map; |
1429 typename Map::Value fill; |
1430 typename Map::Value fill; |
1430 }; |
1431 }; |
1431 |
1432 |
1432 |
1433 |
1433 /// \brief Writable bool map which stores for each true assigned elements |
1434 /// \brief Writable bool map which stores the sequence number of |
1434 /// the setting order number. |
1435 /// true assignments. |
1435 /// |
1436 /// |
1436 /// Writable bool map which stores for each true assigned elements |
1437 /// Writable bool map which stores for each true assigned elements |
1437 /// the setting order number. It make easy to calculate the leaving |
1438 /// the sequence number of this setting. |
|
1439 /// It makes it easy to calculate the leaving |
1438 /// order of the nodes in the \c Dfs algorithm. |
1440 /// order of the nodes in the \c Dfs algorithm. |
1439 /// |
1441 /// |
1440 ///\code |
1442 ///\code |
1441 /// typedef Digraph::NodeMap<int> OrderMap; |
1443 /// typedef Digraph::NodeMap<int> OrderMap; |
1442 /// OrderMap order(digraph); |
1444 /// OrderMap order(digraph); |
1451 /// dfs.start(); |
1453 /// dfs.start(); |
1452 /// } |
1454 /// } |
1453 /// } |
1455 /// } |
1454 ///\endcode |
1456 ///\endcode |
1455 /// |
1457 /// |
1456 /// The discovering order can be stored a little harder because the |
1458 /// The storing of the discovering order is more difficult because the |
1457 /// ReachedMap should be readable in the dfs algorithm but the setting |
1459 /// ReachedMap should be readable in the dfs algorithm but the setting |
1458 /// order map is not readable. Now we should use the fork map: |
1460 /// order map is not readable. Thus we must use the fork map: |
1459 /// |
1461 /// |
1460 ///\code |
1462 ///\code |
1461 /// typedef Digraph::NodeMap<int> OrderMap; |
1463 /// typedef Digraph::NodeMap<int> OrderMap; |
1462 /// OrderMap order(digraph); |
1464 /// OrderMap order(digraph); |
1463 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap; |
1465 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap; |