2 * src/lemon/vector_map.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_VECTOR_MAP_H
18 #define LEMON_VECTOR_MAP_H
23 #include <lemon/alteration_observer_registry.h>
27 ///\brief Vector based graph maps.
31 /// \addtogroup graphmaps
34 /// The VectorMap template class is graph map structure what
35 /// automatically updates the map when a key is added to or erased from
36 /// the map. This map factory uses the allocators to implement
37 /// the container functionality. This map factory
38 /// uses the std::vector to implement the container function.
40 /// \param Registry The AlterationObserverRegistry that will notify this map.
41 /// \param IdMap The IdMap type of the graph items.
42 /// \param Value The value type of the map.
44 /// \author Balazs Dezso
47 template <typename _Graph,
51 class VectorMap : public AlterationObserverRegistry<_Item>::ObserverBase {
54 /// The graph type of the map.
56 /// The key type of the map.
57 typedef _Item KeyType;
58 /// The id map type of the map.
60 /// The registry type of the map.
61 typedef AlterationObserverRegistry<_Item> Registry;
62 /// The value type of the map.
66 typedef VectorMap Map;
67 /// The base class of the map.
68 typedef typename Registry::ObserverBase Parent;
72 /// The container type of the map.
73 typedef std::vector<Value> Container;
77 /// The value type of the map.
78 typedef Value ValueType;
79 /// The reference type of the map;
80 typedef typename Container::reference ReferenceType;
81 /// The pointer type of the map;
82 typedef typename Container::pointer PointerType;
84 /// The const value type of the map.
85 typedef const Value ConstValueType;
86 /// The const reference type of the map;
87 typedef typename Container::const_reference ConstReferenceType;
88 /// The pointer type of the map;
89 typedef typename Container::const_pointer ConstPointerType;
91 /// Constructor to attach the new map into the registry.
93 /// It construates a map and attachs it into the registry.
94 /// It adds all the items of the graph to the map.
96 VectorMap(const Graph& _g, Registry& _r) : graph(&_g) {
101 /// Constructor uses given value to initialize the map.
103 /// It construates a map uses a given value to initialize the map.
104 /// It adds all the items of the graph to the map.
106 VectorMap(const Graph& g, Registry& r, const Value& v) : graph(&g) {
108 container.resize(IdMap(*graph).maxId() + 1, v);
111 VectorMap(const VectorMap& copy) : graph(copy.getGraph()) {
112 if (copy.attached()) {
113 attach(*copy.getRegistry());
114 container = copy.container;
118 using Parent::attach;
119 using Parent::detach;
120 using Parent::attached;
122 /** Assign operator to copy a map of the same map type.
124 VectorMap& operator=(const VectorMap& copy) {
125 if (© == this) return *this;
127 if (graph != copy.graph) {
131 if (copy.attached()) {
132 attach(*copy.getRegistry());
135 container = copy.container;
141 virtual ~VectorMap() {
147 const Graph* getGraph() const {
151 /// The subcript operator.
153 /// The subscript operator. The map can be subscripted by the
154 /// actual items of the graph.
156 ReferenceType operator[](const KeyType& key) {
157 return container[IdMap(*graph)[key]];
160 /// The const subcript operator.
162 /// The const subscript operator. The map can be subscripted by the
163 /// actual items of the graph.
165 ConstReferenceType operator[](const KeyType& key) const {
166 return container[IdMap(*graph)[key]];
170 /// The setter function of the map.
172 /// It the same as operator[](key) = value expression.
175 void set(const KeyType& key, const ValueType& value) {
176 (*this)[key] = value;
179 /// Adds a new key to the map.
181 /// It adds a new key to the map. It called by the observer registry
182 /// and it overrides the add() member function of the observer base.
184 void add(const KeyType& key) {
185 int id = IdMap(*graph)[key];
186 if (id >= (int)container.size()) {
187 container.resize(id + 1);
191 /// Erases a key from the map.
193 /// Erase a key from the map. It called by the observer registry
194 /// and it overrides the erase() member function of the observer base.
195 void erase(const KeyType&) {}
199 /// It buildes the map. It called by the observer registry
200 /// and it overrides the build() member function of the observer base.
203 container.resize(IdMap(*graph).maxId() + 1);
208 /// It erase all items from the map. It called by the observer registry
209 /// and it overrides the clear() member function of the observer base.
222 template <typename _Base>
223 class VectorMappableGraphExtender : public _Base {
226 typedef VectorMappableGraphExtender<_Base> Graph;
227 typedef _Base Parent;
229 typedef typename Parent::Node Node;
230 typedef typename Parent::NodeIt NodeIt;
231 typedef typename Parent::NodeIdMap NodeIdMap;
232 typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
234 typedef typename Parent::Edge Edge;
235 typedef typename Parent::EdgeIt EdgeIt;
236 typedef typename Parent::EdgeIdMap EdgeIdMap;
237 typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
241 template <typename _Value>
242 class NodeMap : public VectorMap<Graph, Node, NodeIdMap, _Value> {
244 typedef VectorMappableGraphExtender<_Base> Graph;
246 typedef typename Graph::Node Node;
247 typedef typename Graph::NodeIdMap NodeIdMap;
249 typedef VectorMap<Graph, Node, NodeIdMap, _Value> Parent;
251 //typedef typename Parent::Graph Graph;
252 typedef typename Parent::Value Value;
254 NodeMap(const Graph& g)
255 : Parent(g, g.getNodeObserverRegistry()) {}
256 NodeMap(const Graph& g, const Value& v)
257 : Parent(g, g.getNodeObserverRegistry(), v) {}
261 template <typename _Value>
262 class EdgeMap : public VectorMap<Graph, Edge, EdgeIdMap, _Value> {
264 typedef VectorMappableGraphExtender<_Base> Graph;
266 typedef typename Graph::Edge Edge;
267 typedef typename Graph::EdgeIdMap EdgeIdMap;
269 typedef VectorMap<Graph, Edge, EdgeIdMap, _Value> Parent;
271 //typedef typename Parent::Graph Graph;
272 typedef typename Parent::Value Value;
274 EdgeMap(const Graph& g)
275 : Parent(g, g.getEdgeObserverRegistry()) {}
276 EdgeMap(const Graph& g, const Value& v)
277 : Parent(g, g.getEdgeObserverRegistry(), v) {}