26 #include <lemon/bits/alteration_notifier.h> |
26 #include <lemon/bits/alteration_notifier.h> |
27 |
27 |
28 #include <lemon/concept_check.h> |
28 #include <lemon/concept_check.h> |
29 #include <lemon/concepts/maps.h> |
29 #include <lemon/concepts/maps.h> |
30 |
30 |
31 ///\ingroup graphbits |
31 //\ingroup graphbits |
32 /// |
32 // |
33 ///\file |
33 //\file |
34 ///\brief Vector based graph maps. |
34 //\brief Vector based graph maps. |
35 namespace lemon { |
35 namespace lemon { |
36 |
36 |
37 /// \ingroup graphbits |
37 // \ingroup graphbits |
38 /// |
38 // |
39 /// \brief Graph map based on the std::vector storage. |
39 // \brief Graph map based on the std::vector storage. |
40 /// |
40 // |
41 /// The VectorMap template class is graph map structure what |
41 // The VectorMap template class is graph map structure what |
42 /// automatically updates the map when a key is added to or erased from |
42 // automatically updates the map when a key is added to or erased from |
43 /// the map. This map type uses the std::vector to store the values. |
43 // the map. This map type uses the std::vector to store the values. |
44 /// |
44 // |
45 /// \tparam _Graph The graph this map is attached to. |
45 // \tparam _Graph The graph this map is attached to. |
46 /// \tparam _Item The item type of the graph items. |
46 // \tparam _Item The item type of the graph items. |
47 /// \tparam _Value The value type of the map. |
47 // \tparam _Value The value type of the map. |
48 template <typename _Graph, typename _Item, typename _Value> |
48 template <typename _Graph, typename _Item, typename _Value> |
49 class VectorMap |
49 class VectorMap |
50 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { |
50 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { |
51 private: |
51 private: |
52 |
52 |
53 /// The container type of the map. |
53 // The container type of the map. |
54 typedef std::vector<_Value> Container; |
54 typedef std::vector<_Value> Container; |
55 |
55 |
56 public: |
56 public: |
57 |
57 |
58 /// The graph type of the map. |
58 // The graph type of the map. |
59 typedef _Graph Graph; |
59 typedef _Graph Graph; |
60 /// The item type of the map. |
60 // The item type of the map. |
61 typedef _Item Item; |
61 typedef _Item Item; |
62 /// The reference map tag. |
62 // The reference map tag. |
63 typedef True ReferenceMapTag; |
63 typedef True ReferenceMapTag; |
64 |
64 |
65 /// The key type of the map. |
65 // The key type of the map. |
66 typedef _Item Key; |
66 typedef _Item Key; |
67 /// The value type of the map. |
67 // The value type of the map. |
68 typedef _Value Value; |
68 typedef _Value Value; |
69 |
69 |
70 /// The notifier type. |
70 // The notifier type. |
71 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; |
71 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; |
72 |
72 |
73 /// The map type. |
73 // The map type. |
74 typedef VectorMap Map; |
74 typedef VectorMap Map; |
75 /// The base class of the map. |
75 // The base class of the map. |
76 typedef typename Notifier::ObserverBase Parent; |
76 typedef typename Notifier::ObserverBase Parent; |
77 |
77 |
78 /// The reference type of the map; |
78 // The reference type of the map; |
79 typedef typename Container::reference Reference; |
79 typedef typename Container::reference Reference; |
80 /// The const reference type of the map; |
80 // The const reference type of the map; |
81 typedef typename Container::const_reference ConstReference; |
81 typedef typename Container::const_reference ConstReference; |
82 |
82 |
83 |
83 |
84 /// \brief Constructor to attach the new map into the notifier. |
84 // \brief Constructor to attach the new map into the notifier. |
85 /// |
85 // |
86 /// It constructs a map and attachs it into the notifier. |
86 // It constructs a map and attachs it into the notifier. |
87 /// It adds all the items of the graph to the map. |
87 // It adds all the items of the graph to the map. |
88 VectorMap(const Graph& graph) { |
88 VectorMap(const Graph& graph) { |
89 Parent::attach(graph.notifier(Item())); |
89 Parent::attach(graph.notifier(Item())); |
90 container.resize(Parent::notifier()->maxId() + 1); |
90 container.resize(Parent::notifier()->maxId() + 1); |
91 } |
91 } |
92 |
92 |
93 /// \brief Constructor uses given value to initialize the map. |
93 // \brief Constructor uses given value to initialize the map. |
94 /// |
94 // |
95 /// It constructs a map uses a given value to initialize the map. |
95 // It constructs a map uses a given value to initialize the map. |
96 /// It adds all the items of the graph to the map. |
96 // It adds all the items of the graph to the map. |
97 VectorMap(const Graph& graph, const Value& value) { |
97 VectorMap(const Graph& graph, const Value& value) { |
98 Parent::attach(graph.notifier(Item())); |
98 Parent::attach(graph.notifier(Item())); |
99 container.resize(Parent::notifier()->maxId() + 1, value); |
99 container.resize(Parent::notifier()->maxId() + 1, value); |
100 } |
100 } |
101 |
101 |
102 private: |
102 private: |
103 /// \brief Copy constructor |
103 // \brief Copy constructor |
104 /// |
104 // |
105 /// Copy constructor. |
105 // Copy constructor. |
106 VectorMap(const VectorMap& _copy) : Parent() { |
106 VectorMap(const VectorMap& _copy) : Parent() { |
107 if (_copy.attached()) { |
107 if (_copy.attached()) { |
108 Parent::attach(*_copy.notifier()); |
108 Parent::attach(*_copy.notifier()); |
109 container = _copy.container; |
109 container = _copy.container; |
110 } |
110 } |
111 } |
111 } |
112 |
112 |
113 /// \brief Assign operator. |
113 // \brief Assign operator. |
114 /// |
114 // |
115 /// This operator assigns for each item in the map the |
115 // This operator assigns for each item in the map the |
116 /// value mapped to the same item in the copied map. |
116 // value mapped to the same item in the copied map. |
117 /// The parameter map should be indiced with the same |
117 // The parameter map should be indiced with the same |
118 /// itemset because this assign operator does not change |
118 // itemset because this assign operator does not change |
119 /// the container of the map. |
119 // the container of the map. |
120 VectorMap& operator=(const VectorMap& cmap) { |
120 VectorMap& operator=(const VectorMap& cmap) { |
121 return operator=<VectorMap>(cmap); |
121 return operator=<VectorMap>(cmap); |
122 } |
122 } |
123 |
123 |
124 |
124 |
125 /// \brief Template assign operator. |
125 // \brief Template assign operator. |
126 /// |
126 // |
127 /// The given parameter should be conform to the ReadMap |
127 // The given parameter should be conform to the ReadMap |
128 /// concecpt and could be indiced by the current item set of |
128 // concecpt and could be indiced by the current item set of |
129 /// the NodeMap. In this case the value for each item |
129 // the NodeMap. In this case the value for each item |
130 /// is assigned by the value of the given ReadMap. |
130 // is assigned by the value of the given ReadMap. |
131 template <typename CMap> |
131 template <typename CMap> |
132 VectorMap& operator=(const CMap& cmap) { |
132 VectorMap& operator=(const CMap& cmap) { |
133 checkConcept<concepts::ReadMap<Key, _Value>, CMap>(); |
133 checkConcept<concepts::ReadMap<Key, _Value>, CMap>(); |
134 const typename Parent::Notifier* nf = Parent::notifier(); |
134 const typename Parent::Notifier* nf = Parent::notifier(); |
135 Item it; |
135 Item it; |
139 return *this; |
139 return *this; |
140 } |
140 } |
141 |
141 |
142 public: |
142 public: |
143 |
143 |
144 /// \brief The subcript operator. |
144 // \brief The subcript operator. |
145 /// |
145 // |
146 /// The subscript operator. The map can be subscripted by the |
146 // The subscript operator. The map can be subscripted by the |
147 /// actual items of the graph. |
147 // actual items of the graph. |
148 Reference operator[](const Key& key) { |
148 Reference operator[](const Key& key) { |
149 return container[Parent::notifier()->id(key)]; |
149 return container[Parent::notifier()->id(key)]; |
150 } |
150 } |
151 |
151 |
152 /// \brief The const subcript operator. |
152 // \brief The const subcript operator. |
153 /// |
153 // |
154 /// The const subscript operator. The map can be subscripted by the |
154 // The const subscript operator. The map can be subscripted by the |
155 /// actual items of the graph. |
155 // actual items of the graph. |
156 ConstReference operator[](const Key& key) const { |
156 ConstReference operator[](const Key& key) const { |
157 return container[Parent::notifier()->id(key)]; |
157 return container[Parent::notifier()->id(key)]; |
158 } |
158 } |
159 |
159 |
160 |
160 |
161 /// \brief The setter function of the map. |
161 // \brief The setter function of the map. |
162 /// |
162 // |
163 /// It the same as operator[](key) = value expression. |
163 // It the same as operator[](key) = value expression. |
164 void set(const Key& key, const Value& value) { |
164 void set(const Key& key, const Value& value) { |
165 (*this)[key] = value; |
165 (*this)[key] = value; |
166 } |
166 } |
167 |
167 |
168 protected: |
168 protected: |
169 |
169 |
170 /// \brief Adds a new key to the map. |
170 // \brief Adds a new key to the map. |
171 /// |
171 // |
172 /// It adds a new key to the map. It called by the observer notifier |
172 // It adds a new key to the map. It called by the observer notifier |
173 /// and it overrides the add() member function of the observer base. |
173 // and it overrides the add() member function of the observer base. |
174 virtual void add(const Key& key) { |
174 virtual void add(const Key& key) { |
175 int id = Parent::notifier()->id(key); |
175 int id = Parent::notifier()->id(key); |
176 if (id >= int(container.size())) { |
176 if (id >= int(container.size())) { |
177 container.resize(id + 1); |
177 container.resize(id + 1); |
178 } |
178 } |
179 } |
179 } |
180 |
180 |
181 /// \brief Adds more new keys to the map. |
181 // \brief Adds more new keys to the map. |
182 /// |
182 // |
183 /// It adds more new keys to the map. It called by the observer notifier |
183 // It adds more new keys to the map. It called by the observer notifier |
184 /// and it overrides the add() member function of the observer base. |
184 // and it overrides the add() member function of the observer base. |
185 virtual void add(const std::vector<Key>& keys) { |
185 virtual void add(const std::vector<Key>& keys) { |
186 int max = container.size() - 1; |
186 int max = container.size() - 1; |
187 for (int i = 0; i < int(keys.size()); ++i) { |
187 for (int i = 0; i < int(keys.size()); ++i) { |
188 int id = Parent::notifier()->id(keys[i]); |
188 int id = Parent::notifier()->id(keys[i]); |
189 if (id >= max) { |
189 if (id >= max) { |
191 } |
191 } |
192 } |
192 } |
193 container.resize(max + 1); |
193 container.resize(max + 1); |
194 } |
194 } |
195 |
195 |
196 /// \brief Erase a key from the map. |
196 // \brief Erase a key from the map. |
197 /// |
197 // |
198 /// Erase a key from the map. It called by the observer notifier |
198 // Erase a key from the map. It called by the observer notifier |
199 /// and it overrides the erase() member function of the observer base. |
199 // and it overrides the erase() member function of the observer base. |
200 virtual void erase(const Key& key) { |
200 virtual void erase(const Key& key) { |
201 container[Parent::notifier()->id(key)] = Value(); |
201 container[Parent::notifier()->id(key)] = Value(); |
202 } |
202 } |
203 |
203 |
204 /// \brief Erase more keys from the map. |
204 // \brief Erase more keys from the map. |
205 /// |
205 // |
206 /// Erase more keys from the map. It called by the observer notifier |
206 // Erase more keys from the map. It called by the observer notifier |
207 /// and it overrides the erase() member function of the observer base. |
207 // and it overrides the erase() member function of the observer base. |
208 virtual void erase(const std::vector<Key>& keys) { |
208 virtual void erase(const std::vector<Key>& keys) { |
209 for (int i = 0; i < int(keys.size()); ++i) { |
209 for (int i = 0; i < int(keys.size()); ++i) { |
210 container[Parent::notifier()->id(keys[i])] = Value(); |
210 container[Parent::notifier()->id(keys[i])] = Value(); |
211 } |
211 } |
212 } |
212 } |
213 |
213 |
214 /// \brief Buildes the map. |
214 // \brief Buildes the map. |
215 /// |
215 // |
216 /// It buildes the map. It called by the observer notifier |
216 // It buildes the map. It called by the observer notifier |
217 /// and it overrides the build() member function of the observer base. |
217 // and it overrides the build() member function of the observer base. |
218 virtual void build() { |
218 virtual void build() { |
219 int size = Parent::notifier()->maxId() + 1; |
219 int size = Parent::notifier()->maxId() + 1; |
220 container.reserve(size); |
220 container.reserve(size); |
221 container.resize(size); |
221 container.resize(size); |
222 } |
222 } |
223 |
223 |
224 /// \brief Clear the map. |
224 // \brief Clear the map. |
225 /// |
225 // |
226 /// It erase all items from the map. It called by the observer notifier |
226 // It erase all items from the map. It called by the observer notifier |
227 /// and it overrides the clear() member function of the observer base. |
227 // and it overrides the clear() member function of the observer base. |
228 virtual void clear() { |
228 virtual void clear() { |
229 container.clear(); |
229 container.clear(); |
230 } |
230 } |
231 |
231 |
232 private: |
232 private: |