23 #define LEMON_MAP_UTILS_H |
23 #define LEMON_MAP_UTILS_H |
24 |
24 |
25 #include <map> |
25 #include <map> |
26 #include <vector> |
26 #include <vector> |
27 |
27 |
|
28 #include <lemon/graph_utils.h> |
|
29 |
28 namespace lemon { |
30 namespace lemon { |
29 |
31 |
30 /// \addtogroup mutils |
32 /// \addtogroup mutils |
31 /// @{ |
33 /// @{ |
|
34 |
|
35 |
|
36 template <typename Map, typename Enable = void> |
|
37 struct ReferenceMapTraits { |
|
38 typedef typename Map::Value Value; |
|
39 typedef typename Map::Value& Reference; |
|
40 typedef const typename Map::Value& ConstReference; |
|
41 typedef typename Map::Value* Pointer; |
|
42 typedef const typename Map::Value* ConstPointer; |
|
43 }; |
|
44 |
|
45 template <typename Map> |
|
46 struct ReferenceMapTraits< |
|
47 Map, |
|
48 typename enable_if<typename Map::FullTypeTag, void>::type |
|
49 > { |
|
50 typedef typename Map::Value Value; |
|
51 typedef typename Map::Reference Reference; |
|
52 typedef typename Map::ConstReference ConstReference; |
|
53 typedef typename Map::Pointer Pointer; |
|
54 typedef typename Map::ConstPointer ConstPointer; |
|
55 }; |
32 |
56 |
33 /// \brief General inversable map type. |
57 /// \brief General inversable map type. |
34 |
58 |
35 /// This type provides simple inversable map functions. |
59 /// This type provides simple inversable map functions. |
36 /// The InversableMap wraps an arbitrary ReadWriteMap |
60 /// The InversableMap wraps an arbitrary ReadWriteMap |
37 /// and if a key is setted to a new value then store it |
61 /// and if a key is setted to a new value then store it |
38 /// in the inverse map. |
62 /// in the inverse map. |
39 /// \param _Graph The graph type. |
63 /// \param _Graph The graph type. |
40 /// \param _Map The map to extend with inversable functionality. |
64 /// \param _Map The map to extend with inversable functionality. |
41 template < |
65 template < |
42 typename _Graph, |
66 typename _Graph, |
43 typename _Map |
67 typename _Item, |
|
68 typename _Value, |
|
69 typename _Map |
|
70 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value> |
44 > |
71 > |
45 class InversableMap : protected _Map { |
72 class InversableMap : protected _Map { |
46 |
73 |
47 public: |
74 public: |
|
75 |
|
76 typedef _Map Map; |
48 typedef _Graph Graph; |
77 typedef _Graph Graph; |
49 |
78 /// The key type of InversableMap (Node, Edge, UndirEdge). |
50 typedef _Map Map; |
|
51 /// The key type of InversableMap (Node, Edge, UndirEdge). |
|
52 typedef typename _Map::Key Key; |
79 typedef typename _Map::Key Key; |
53 /// The value type of the InversableMap. |
80 /// The value type of the InversableMap. |
54 typedef typename _Map::Value Value; |
81 typedef typename _Map::Value Value; |
|
82 |
55 typedef std::map<Value, Key> InverseMap; |
83 typedef std::map<Value, Key> InverseMap; |
56 |
84 |
57 typedef typename _Map::ConstReference ConstReference; |
85 typedef typename _Map::ConstReference ConstReference; |
58 |
86 |
59 /// \brief Constructor. |
87 /// \brief Constructor. |
62 /// |
90 /// |
63 InversableMap(const Graph& graph) : Map(graph) {} |
91 InversableMap(const Graph& graph) : Map(graph) {} |
64 |
92 |
65 /// \brief The setter function of the map. |
93 /// \brief The setter function of the map. |
66 /// |
94 /// |
67 /// It sets the map and the inverse map to given key-value pair. |
95 |
68 void set(const Key& key, const Value& val) { |
96 void set(const Key& key, const Value& val) { |
69 Value oldval = Map::operator[](key); |
97 Value oldval = Map::operator[](key); |
70 typename InverseMap::iterator it = invMap.find(oldval); |
98 typename InverseMap::iterator it = invMap.find(oldval); |
71 if (it != invMap.end() && it->second == key) { |
99 if (it != invMap.end() && it->second == key) { |
72 invMap.erase(it); |
100 invMap.erase(it); |