GRAPH_TYPEDEFS and UNDIRGRAPH_TYPEDEFS macros added to graph_utils.h.
2 * lemon/vector_map.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, 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/utility.h>
24 #include <lemon/bits/map_iterator.h>
25 #include <lemon/bits/alteration_notifier.h>
26 #include <lemon/concept_check.h>
27 #include <lemon/concept/maps.h>
29 /// \ingroup graphmapfactory
32 ///\brief Vector based graph maps.
36 /// \ingroup graphmapfactory
38 /// \brief Graph map based on the std::vector storage.
40 /// The VectorMap template class is graph map structure what
41 /// automatically updates the map when a key is added to or erased from
42 /// the map. This map factory uses the allocators to implement
43 /// the container functionality. This map factory
44 /// uses the std::vector to implement the container function.
46 /// \param Registry The AlterationNotifier that will notify this map.
47 /// \param Item The item type of the graph items.
48 /// \param Value The value type of the map.
50 /// \author Balazs Dezso
57 class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
60 /// The container type of the map.
61 typedef std::vector<_Value> Container;
65 /// The graph type of the map.
67 /// The reference map tag.
68 typedef True ReferenceMapTag;
70 /// The key type of the map.
72 /// The value type of the map.
75 typedef AlterationNotifier<_Item> Registry;
78 typedef VectorMap Map;
79 /// The base class of the map.
80 typedef typename Registry::ObserverBase Parent;
82 /// The reference type of the map;
83 typedef typename Container::reference Reference;
84 /// The pointer type of the map;
85 typedef typename Container::pointer Pointer;
87 /// The const value type of the map.
88 typedef const Value ConstValue;
89 /// The const reference type of the map;
90 typedef typename Container::const_reference ConstReference;
91 /// The pointer type of the map;
92 typedef typename Container::const_pointer ConstPointer;
95 /// \brief Constructor to attach the new map into the registry.
97 /// It constructs a map and attachs it into the registry.
98 /// It adds all the items of the graph to the map.
99 VectorMap(const Graph& _g) : graph(&_g) {
100 attach(_g.getNotifier(_Item()));
104 /// \brief Constructor uses given value to initialize the map.
106 /// It constructs a map uses a given value to initialize the map.
107 /// It adds all the items of the graph to the map.
108 VectorMap(const Graph& _g, const Value& _v) : graph(&_g) {
109 attach(_g.getNotifier(_Item()));
110 container.resize(graph->maxId(_Item()) + 1, _v);
113 /// \brief Copy constructor
115 /// Copy constructor.
116 VectorMap(const VectorMap& _copy)
117 : Parent(), graph(_copy.getGraph()) {
118 if (_copy.attached()) {
119 attach(*_copy.getRegistry());
120 container = _copy.container;
124 /// \brief Destrcutor
127 virtual ~VectorMap() {
136 VectorMap& operator=(const VectorMap&);
140 using Parent::attach;
141 using Parent::detach;
142 using Parent::attached;
144 const Graph* getGraph() const {
150 /// \brief The subcript operator.
152 /// The subscript operator. The map can be subscripted by the
153 /// actual items of the graph.
154 Reference operator[](const Key& key) {
155 return container[graph->id(key)];
158 /// \brief The const subcript operator.
160 /// The const subscript operator. The map can be subscripted by the
161 /// actual items of the graph.
162 ConstReference operator[](const Key& key) const {
163 return container[graph->id(key)];
167 /// \brief The setter function of the map.
169 /// It the same as operator[](key) = value expression.
170 void set(const Key& key, const Value& value) {
171 (*this)[key] = value;
176 /// \brief Adds a new key to the map.
178 /// It adds a new key to the map. It called by the observer registry
179 /// and it overrides the add() member function of the observer base.
180 virtual void add(const Key& key) {
181 int id = graph->id(key);
182 if (id >= (int)container.size()) {
183 container.resize(id + 1);
187 /// \brief Erase a key from the map.
189 /// Erase a key from the map. It called by the observer registry
190 /// and it overrides the erase() member function of the observer base.
191 virtual void erase(const Key&) {}
193 /// \brief Buildes the map.
195 /// It buildes the map. It called by the observer registry
196 /// and it overrides the build() member function of the observer base.
197 virtual void build() {
198 container.resize(graph->maxId(_Item()) + 1);
201 /// \brief Clear the map.
203 /// It erase all items from the map. It called by the observer registry
204 /// and it overrides the clear() member function of the observer base.
205 virtual void clear() {