lemon/maps.h
changeset 28 e337bdf46777
parent 25 751cd8f9bb1c
child 29 0cb4ba427bfd
equal deleted inserted replaced
0:a78a92aed4d0 1:6d86b5fda027
   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;