Changeset 946:c94ef40a22ce in lemon-0.x for src/lemon/vector_map.h
- Timestamp:
- 10/28/04 00:38:50 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/vector_map.h
r937 r946 19 19 20 20 #include <vector> 21 22 #include <lemon/map_iterator.h> 23 #include <lemon/ map_bits.h>21 #include <algorithm> 22 23 #include <lemon/alteration_observer_registry.h> 24 24 25 25 ///\ingroup graphmaps … … 32 32 /// @{ 33 33 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. 39 * 40 * \param MapRegistry The MapRegistry that the maps will belong to. 41 * \param Value The value type of the map. 42 * 43 * \author Balazs Dezso 44 */ 45 46 template <typename MapRegistry, typename Value> 47 class VectorMap : public MapRegistry::MapBase { 48 template <typename MR, typename T> friend class VectorMap; 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. 39 /// 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. 43 /// 44 /// \author Balazs Dezso 45 46 47 template <typename _Graph, 48 typename _Item, 49 typename _IdMap, 50 typename _Value> 51 class VectorMap : public AlterationObserverRegistry<_Item>::ObserverBase { 49 52 public: 50 53 51 /// The graph type of the maps. 52 typedef typename MapRegistry::Graph Graph; 53 /// The key type of the maps. 54 typedef typename MapRegistry::KeyType KeyType; 55 /// The iterator to iterate on the keys. 56 typedef typename MapRegistry::KeyIt KeyIt; 54 /// The graph type of the map. 55 typedef _Graph Graph; 56 /// The key type of the map. 57 typedef _Item KeyType; 58 /// The id map type of the map. 59 typedef _IdMap IdMap; 60 /// The registry type of the map. 61 typedef AlterationObserverRegistry<_Item> Registry; 62 /// The value type of the map. 63 typedef _Value Value; 57 64 58 65 /// The map type. 59 66 typedef VectorMap Map; 60 /// The MapBase of the Map which implements the core regisitry function.61 typedef typename MapRegistry::MapBase MapBase;67 /// The base class of the map. 68 typedef typename Registry::ObserverBase Parent; 62 69 63 70 private: … … 67 74 68 75 public: 69 70 76 71 77 /// The value type of the map. … … 83 89 typedef typename Container::const_pointer ConstPointerType; 84 90 85 /// Constructor to attach the new map into a registry. 86 87 /** Constructor to attach the new map into a registry. 88 * It adds all the nodes or edges of the graph to the map. 91 /// Constructor to attach the new map into the registry. 92 93 /// It construates a map and attachs it into the registry. 94 /// It adds all the items of the graph to the map. 95 96 VectorMap(const Graph& _g, Registry& _r) : graph(&_g) { 97 attach(_r); 98 build(); 99 } 100 101 /// Constructor uses given value to initialize the map. 102 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. 105 106 VectorMap(const Graph& g, Registry& r, const Value& v) : graph(&g) { 107 attach(r); 108 container.resize(IdMap(*graph).maxId() + 1, v); 109 } 110 111 VectorMap(const VectorMap& copy) : graph(copy.getGraph()) { 112 if (copy.attached()) { 113 attach(*copy.getRegistry()); 114 container = copy.container; 115 } 116 } 117 118 119 /** Assign operator to copy a map of the same map type. 89 120 */ 90 VectorMap(const Graph& g, MapRegistry& r) 91 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {} 92 93 /// Constructor uses given value to initialize the map. 94 95 /** Constructor uses given value to initialize the map. 96 * It adds all the nodes or edges of the graph to the map. 97 */ 98 VectorMap(const Graph& g, MapRegistry& r, const Value& v) 99 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {} 100 101 /// Assign operator to copy a map of an other map type. 102 103 /** Assign operator to copy a map of an other map type. 104 * This map's value type must be assignable by the other 105 * map type's value type. 106 */ 107 template <typename TT> 108 VectorMap(const VectorMap<MapRegistry, TT>& c) 109 : MapBase(c), container(c.container.size()) { 110 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { 111 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); 112 container[id] = c.container[id]; 113 } 114 } 115 116 /// Assign operator to copy a map of an other map type. 117 118 /** Assign operator to copy a map of an other map type. 119 * This map's value type must be assignable by the other 120 * map type's value type. 121 */ 122 template <typename TT> 123 VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) { 124 if (MapBase::getGraph() != c.getGraph()) { 125 MapBase::operator=(c); 126 container.resize(c.container.size()); 127 } 128 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) { 129 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it); 130 container[id] = c.container[id]; 131 } 121 VectorMap& operator=(const VectorMap& copy) { 122 if (© == this) return *this; 123 124 if (graph != copy.graph) { 125 if (attached()) { 126 detach(); 127 } 128 if (copy.attached()) { 129 attach(*copy.getRegistry()); 130 } 131 } 132 container = copy.container; 133 132 134 return *this; 133 135 } 134 136 137 138 virtual ~VectorMap() { 139 if (attached()) { 140 detach(); 141 } 142 } 143 144 const Graph* getGraph() const { 145 return graph; 146 } 147 135 148 /// The subcript operator. 136 149 137 /** 138 * The subscript operator. The map can be subscripted by the 139 * actual keys of the graph. 140 */ 150 /// The subscript operator. The map can be subscripted by the 151 /// actual items of the graph. 152 141 153 ReferenceType operator[](const KeyType& key) { 142 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key); 143 return container[id]; 154 return container[IdMap(*graph)[key]]; 144 155 } 145 156 146 157 /// The const subcript operator. 147 158 148 /** 149 * The const subscript operator. The map can be subscripted by the 150 * actual keys of the graph. 151 */ 159 /// The const subscript operator. The map can be subscripted by the 160 /// actual items of the graph. 161 152 162 ConstReferenceType operator[](const KeyType& key) const { 153 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);154 return container[id];155 } 156 157 /// Setter function of the map.158 159 / ** Setter function of the map. Equivalent with map[key] = val.160 * This is a compatibility feature with the not dereferable maps.161 */162 void set(const KeyType& key, const ValueType& val ) {163 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);164 container[id] = val;165 } 163 return container[IdMap(*graph)[key]]; 164 } 165 166 167 /// The setter function of the map. 168 169 /// It the same as operator[](key) = value expression. 170 /// 171 172 void set(const KeyType& key, const ValueType& value) { 173 (*this)[key] = value; 174 } 175 166 176 /// Adds a new key to the map. 167 177 168 /** Adds a new key to the map. It called by the map registry 169 * and it overrides the \ref MapRegistry::MapBase MapBase's 170 * add() member function. 171 */ 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 172 181 void add(const KeyType& key) { 173 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);182 int id = IdMap(*graph)[key]; 174 183 if (id >= (int)container.size()) { 175 184 container.resize(id + 1); … … 179 188 /// Erases a key from the map. 180 189 181 /** Erase a key from the map. It called by the map registry 182 * and it overrides the \ref MapRegistry::MapBase MapBase's 183 * erase() member function. 184 */ 190 /// Erase a key from the map. It called by the observer registry 191 /// and it overrides the erase() member function of the observer base. 185 192 void erase(const KeyType& key) {} 186 193 187 /// Makes empty the map. 188 189 /** Makes empty the map. It called by the map registry 190 * and it overrides the \ref MapRegistry::MapBase MapBase's 191 * clear() member function. 192 */ 193 194 /// Buildes the map. 195 196 /// It buildes the map. It called by the observer registry 197 /// and it overrides the build() member function of the observer base. 198 199 void build() { 200 container.resize(IdMap(*graph).maxId() + 1); 201 } 202 203 /// Clear the map. 204 205 /// It erase all items from the map. It called by the observer registry 206 /// and it overrides the clear() member function of the observer base. 194 207 void clear() { 195 208 container.clear(); 196 209 } 197 210 198 /// The stl compatible pair iterator of the map.199 typedef MapIterator<VectorMap> Iterator;200 /// The stl compatible const pair iterator of the map.201 typedef MapConstIterator<VectorMap> ConstIterator;202 203 /** Returns the begin iterator of the map.204 */205 Iterator begin() {206 return Iterator(*this, KeyIt(*MapBase::getGraph()));207 }208 209 /** Returns the end iterator of the map.210 */211 Iterator end() {212 return Iterator(*this, INVALID);213 }214 215 /** Returns the begin ConstIterator of the map.216 */217 ConstIterator begin() const {218 return ConstIterator(*this, KeyIt(*MapBase::getGraph()));219 }220 221 /** Returns the end const_iterator of the map.222 */223 ConstIterator end() const {224 return ConstIterator(*this, INVALID);225 }226 227 /// The KeySet of the Map.228 typedef MapConstKeySet<VectorMap> ConstKeySet;229 230 /// KeySet getter function.231 ConstKeySet keySet() const {232 return ConstKeySet(*this);233 }234 235 /// The ConstValueSet of the Map.236 typedef MapConstValueSet<VectorMap> ConstValueSet;237 238 /// ConstValueSet getter function.239 ConstValueSet valueSet() const {240 return ConstValueSet(*this);241 }242 243 /// The ValueSet of the Map.244 typedef MapValueSet<VectorMap> ValueSet;245 246 /// ValueSet getter function.247 ValueSet valueSet() {248 return ValueSet(*this);249 }250 251 252 211 private: 253 212 254 213 Container container; 255 214 const Graph *graph; 215 216 }; 217 218 219 template <typename _Base> 220 class VectorMappableGraphExtender : public _Base { 256 221 public: 257 // STL compatibility typedefs. 258 typedef Iterator iterator; 259 typedef ConstIterator const_iterator; 260 typedef typename Iterator::PairValueType value_type; 261 typedef typename Iterator::KeyType key_type; 262 typedef typename Iterator::ValueType data_type; 263 typedef typename Iterator::PairReferenceType reference; 264 typedef typename Iterator::PairPointerType pointer; 265 typedef typename ConstIterator::PairReferenceType const_reference; 266 typedef typename ConstIterator::PairPointerType const_pointer; 267 typedef int difference_type; 222 223 typedef VectorMappableGraphExtender<_Base> Graph; 224 typedef _Base Parent; 225 226 typedef typename Parent::Node Node; 227 typedef typename Parent::NodeIt NodeIt; 228 typedef typename Parent::NodeIdMap NodeIdMap; 229 typedef typename Parent::NodeObserverRegistry NodeObserverRegistry; 230 231 typedef typename Parent::Edge Edge; 232 typedef typename Parent::EdgeIt EdgeIt; 233 typedef typename Parent::EdgeIdMap EdgeIdMap; 234 typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry; 235 236 237 238 template <typename _Value> 239 class NodeMap : public VectorMap<Graph, Node, NodeIdMap, _Value> { 240 public: 241 typedef VectorMappableGraphExtender<_Base> Graph; 242 243 typedef typename Graph::Node Node; 244 typedef typename Graph::NodeIdMap NodeIdMap; 245 246 typedef VectorMap<Graph, Node, NodeIdMap, _Value> Parent; 247 248 typedef typename Parent::Graph Graph; 249 typedef typename Parent::Value Value; 250 251 NodeMap(const Graph& g) 252 : Parent(g, g.getNodeObserverRegistry()) {} 253 NodeMap(const Graph& g, const Value& v) 254 : Parent(g, g.getNodeObserverRegistry(), v) {} 255 256 }; 257 258 template <typename _Value> 259 class EdgeMap : public VectorMap<Graph, Edge, EdgeIdMap, _Value> { 260 public: 261 typedef VectorMappableGraphExtender<_Base> Graph; 262 263 typedef typename Graph::Edge Edge; 264 typedef typename Graph::EdgeIdMap EdgeIdMap; 265 266 typedef VectorMap<Graph, Edge, EdgeIdMap, _Value> Parent; 267 268 typedef typename Parent::Graph Graph; 269 typedef typename Parent::Value Value; 270 271 EdgeMap(const Graph& g) 272 : Parent(g, g.getEdgeObserverRegistry()) {} 273 EdgeMap(const Graph& g, const Value& v) 274 : Parent(g, g.getEdgeObserverRegistry(), v) {} 275 276 }; 277 268 278 }; 269 279
Note: See TracChangeset
for help on using the changeset viewer.