Bug fix in the symmetric maps.
Faster map initialization.
Iterators and Containers STL compatible.
1.1 --- a/src/hugo/Makefile.am Mon Sep 13 18:00:26 2004 +0000
1.2 +++ b/src/hugo/Makefile.am Mon Sep 13 20:05:13 2004 +0000
1.3 @@ -17,6 +17,7 @@
1.4 map_defines.h \
1.5 map_iterator.h \
1.6 map_registry.h \
1.7 + map_bits.h \
1.8 maps.h \
1.9 mincostflows.h \
1.10 minlengthpaths.h \
2.1 --- a/src/hugo/array_map.h Mon Sep 13 18:00:26 2004 +0000
2.2 +++ b/src/hugo/array_map.h Mon Sep 13 20:05:13 2004 +0000
2.3 @@ -5,6 +5,7 @@
2.4 #include <memory>
2.5
2.6 #include <hugo/map_iterator.h>
2.7 +#include <hugo/map_bits.h>
2.8
2.9 ///\ingroup graphmaps
2.10 ///\file
2.11 @@ -71,7 +72,7 @@
2.12 ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
2.13 allocate_memory();
2.14 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.15 - int id = MapBase::getGraph()->id(it);
2.16 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
2.17 allocator.construct(&(values[id]), Value());
2.18 }
2.19 }
2.20 @@ -82,7 +83,7 @@
2.21 : MapBase(g, r) {
2.22 allocate_memory();
2.23 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.24 - int id = MapBase::getGraph()->id(it);
2.25 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
2.26 allocator.construct(&(values[id]), v);
2.27 }
2.28 }
2.29 @@ -94,7 +95,7 @@
2.30 if (capacity == 0) return;
2.31 values = allocator.allocate(capacity);
2.32 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.33 - int id = MapBase::getGraph()->id(it);
2.34 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
2.35 allocator.construct(&(values[id]), copy.values[id]);
2.36 }
2.37 }
2.38 @@ -123,7 +124,7 @@
2.39 if (capacity == 0) return *this;
2.40 values = allocator.allocate(capacity);
2.41 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.42 - int id = MapBase::getGraph()->id(it);
2.43 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
2.44 allocator.construct(&(values[id]), copy.values[id]);
2.45 }
2.46 return *this;
2.47 @@ -132,9 +133,10 @@
2.48 /** Assign operator to copy a map an other map type.
2.49 */
2.50 template <typename CMap> ArrayMap& operator=(const CMap& copy) {
2.51 - if (MapBase::getGraph()) {
2.52 + if (capacity != 0) {
2.53 MapBase::destroy();
2.54 - }
2.55 + allocator.deallocate(values, capacity);
2.56 + }
2.57 MapBase::operator=(copy);
2.58 if (MapBase::getGraph()) {
2.59 allocate_memory();
2.60 @@ -160,7 +162,7 @@
2.61 * actual keys of the graph.
2.62 */
2.63 ReferenceType operator[](const KeyType& key) {
2.64 - int id = MapBase::getGraph()->id(key);
2.65 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
2.66 return values[id];
2.67 }
2.68
2.69 @@ -169,7 +171,7 @@
2.70 * actual keys of the graph.
2.71 */
2.72 ConstReferenceType operator[](const KeyType& key) const {
2.73 - int id = MapBase::getGraph()->id(key);
2.74 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
2.75 return values[id];
2.76 }
2.77
2.78 @@ -177,14 +179,14 @@
2.79 * This is a compatibility feature with the not dereferable maps.
2.80 */
2.81 void set(const KeyType& key, const ValueType& val) {
2.82 - int id = MapBase::getGraph()->id(key);
2.83 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
2.84 values[id] = val;
2.85 }
2.86
2.87 /** Add a new key to the map. It called by the map registry.
2.88 */
2.89 void add(const KeyType& key) {
2.90 - int id = MapBase::getGraph()->id(key);
2.91 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
2.92 if (id >= capacity) {
2.93 int new_capacity = (capacity == 0 ? 1 : capacity);
2.94 while (new_capacity <= id) {
2.95 @@ -192,7 +194,7 @@
2.96 }
2.97 Value* new_values = allocator.allocate(new_capacity);;
2.98 for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.99 - int jd = MapBase::getGraph()->id(it);
2.100 + int jd = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
2.101 if (id != jd) {
2.102 allocator.construct(&(new_values[jd]), values[jd]);
2.103 allocator.destroy(&(values[jd]));
2.104 @@ -208,7 +210,7 @@
2.105 /** Erase a key from the map. It called by the map registry.
2.106 */
2.107 void erase(const KeyType& key) {
2.108 - int id = MapBase::getGraph()->id(key);
2.109 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
2.110 allocator.destroy(&(values[id]));
2.111 }
2.112
2.113 @@ -278,13 +280,7 @@
2.114 private:
2.115
2.116 void allocate_memory() {
2.117 - int max_id = -1;
2.118 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
2.119 - int id = MapBase::getGraph()->id(it);
2.120 - if (id > max_id) {
2.121 - max_id = id;
2.122 - }
2.123 - }
2.124 + int max_id = KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph());
2.125 if (max_id == -1) {
2.126 capacity = 0;
2.127 values = 0;
2.128 @@ -300,6 +296,19 @@
2.129 int capacity;
2.130 Value* values;
2.131 Allocator allocator;
2.132 +
2.133 + public:
2.134 + // STL compatibility typedefs.
2.135 + typedef Iterator iterator;
2.136 + typedef ConstIterator const_iterator;
2.137 + typedef typename Iterator::PairValueType value_type;
2.138 + typedef typename Iterator::KeyType key_type;
2.139 + typedef typename Iterator::ValueType data_type;
2.140 + typedef typename Iterator::PairReferenceType reference;
2.141 + typedef typename Iterator::PairPointerType pointer;
2.142 + typedef typename ConstIterator::PairReferenceType const_reference;
2.143 + typedef typename ConstIterator::PairPointerType const_pointer;
2.144 + typedef int difference_type;
2.145 };
2.146
2.147 /// @}
3.1 --- a/src/hugo/graph_wrapper.h Mon Sep 13 18:00:26 2004 +0000
3.2 +++ b/src/hugo/graph_wrapper.h Mon Sep 13 20:05:13 2004 +0000
3.3 @@ -1388,7 +1388,7 @@
3.4
3.5 void erase(const Edge& e) const {
3.6 Node n=tail(e);
3.7 - typename Graph::OutEdgeIt f(*graph, n);
3.8 + typename Graph::OutEdgeIt f(*Parent::graph, n);
3.9 ++f;
3.10 first_out_edges->set(n, f);
3.11 }
4.1 --- a/src/hugo/list_graph.h Mon Sep 13 18:00:26 2004 +0000
4.2 +++ b/src/hugo/list_graph.h Mon Sep 13 20:05:13 2004 +0000
4.3 @@ -1114,7 +1114,10 @@
4.4
4.5 OutEdgeIt(const EdgeSet& _G,const Node v) :
4.6 Edge(_G.nodes[v].first_out), G(&_G) { }
4.7 - OutEdgeIt &operator++() { n = G->edges[n].next_out; return *this; }
4.8 + OutEdgeIt &operator++() {
4.9 + Edge::n = G->edges[Edge::n].next_out;
4.10 + return *this;
4.11 + }
4.12 };
4.13
4.14 class InEdgeIt : public Edge {
4.15 @@ -1126,7 +1129,10 @@
4.16 InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
4.17 InEdgeIt(const EdgeSet& _G,Node v)
4.18 : Edge(_G.nodes[v].first_in), G(&_G) { }
4.19 - InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
4.20 + InEdgeIt &operator++() {
4.21 + Edge::n = G->edges[Edge::n].next_in;
4.22 + return *this;
4.23 + }
4.24 };
4.25
4.26 };
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/hugo/map_bits.h Mon Sep 13 20:05:13 2004 +0000
5.3 @@ -0,0 +1,52 @@
5.4 +// -*- c++ -*-
5.5 +#ifndef MAP_BITS_H
5.6 +#define MAP_BITS_H
5.7 +
5.8 +///\ingroup graphmaps
5.9 +///\file
5.10 +///\brief Some utils to help implement maps.
5.11 +
5.12 +namespace hugo {
5.13 +
5.14 +
5.15 + /// \addtogroup graphmaps
5.16 + /// @{
5.17 +
5.18 + /// Helper class to get information about the key type.
5.19 + template <typename Graph, typename KeyIt>
5.20 + struct KeyInfo {};
5.21 +
5.22 + template <typename Graph>
5.23 + struct KeyInfo<Graph, typename Graph::NodeIt> {
5.24 + static int maxId(const Graph& graph) {
5.25 + return graph.maxNodeId();
5.26 + }
5.27 + static int id(const Graph& graph, const typename Graph::Node& node) {
5.28 + return graph.id(node);
5.29 + }
5.30 + };
5.31 +
5.32 + template <typename Graph>
5.33 + struct KeyInfo<Graph, typename Graph::EdgeIt> {
5.34 + static int maxId(const Graph& graph) {
5.35 + return graph.maxEdgeId();
5.36 + }
5.37 + static int id(const Graph& graph, const typename Graph::Edge& edge) {
5.38 + return graph.id(edge);
5.39 + }
5.40 + };
5.41 +
5.42 + template <typename Graph>
5.43 + struct KeyInfo<Graph, typename Graph::SymEdgeIt> {
5.44 + static int maxId(const Graph& graph) {
5.45 + return graph.maxEdgeId() >> 1;
5.46 + }
5.47 + static int id(const Graph& graph, const typename Graph::Edge& edge) {
5.48 + return graph.id(edge) >> 1;
5.49 + }
5.50 + };
5.51 +
5.52 + /// @}
5.53 +}
5.54 +
5.55 +#endif
6.1 --- a/src/hugo/map_defines.h Mon Sep 13 18:00:26 2004 +0000
6.2 +++ b/src/hugo/map_defines.h Mon Sep 13 20:05:13 2004 +0000
6.3 @@ -96,7 +96,7 @@
6.4 #define CREATE_SYM_EDGE_MAP_REGISTRY \
6.5 typedef SymEdgeIt<Graph, Edge, EdgeIt> SymEdgeIt; \
6.6 typedef MapRegistry<Graph, Edge, SymEdgeIt> SymEdgeMapRegistry; \
6.7 -mutable EdgeMapRegistry sym_edge_maps;
6.8 +mutable SymEdgeMapRegistry sym_edge_maps;
6.9
6.10
6.11 /** Creates a map from a template map. The import method is
7.1 --- a/src/hugo/map_iterator.h Mon Sep 13 18:00:26 2004 +0000
7.2 +++ b/src/hugo/map_iterator.h Mon Sep 13 20:05:13 2004 +0000
7.3 @@ -2,6 +2,8 @@
7.4 #ifndef MAP_ITERATOR_H
7.5 #define MAP_ITERATOR_H
7.6
7.7 +#include <iterator>
7.8 +
7.9 #include <hugo/extended_pair.h>
7.10
7.11 ///\ingroup graphmaps
7.12 @@ -22,6 +24,7 @@
7.13 class MapIteratorBase {
7.14
7.15 public:
7.16 +
7.17 /// The key type of the iterator.
7.18 typedef typename Map::KeyType KeyType;
7.19 /// The iterator to iterate on the keys.
7.20 @@ -79,8 +82,12 @@
7.21
7.22 friend class MapConstIterator<Map>;
7.23
7.24 +
7.25 public:
7.26
7.27 + /// The iterator base class.
7.28 + typedef MapIteratorBase<Map> Base;
7.29 +
7.30 /// The key type of the iterator.
7.31 typedef typename Map::KeyType KeyType;
7.32 /// The iterator to iterate on the keys.
7.33 @@ -102,6 +109,10 @@
7.34
7.35 public:
7.36
7.37 + /// The value type of the iterator.
7.38 + typedef extended_pair<KeyType, const KeyType&,
7.39 + ValueType, const ValueType&> PairValueType;
7.40 +
7.41 /// The reference type of the iterator.
7.42 typedef extended_pair<const KeyType&, const KeyType&,
7.43 ReferenceType, ReferenceType> PairReferenceType;
7.44 @@ -111,12 +122,11 @@
7.45
7.46 /// Constructor to initalize the iterators returned
7.47 /// by the begin() and end().
7.48 - MapIterator(Map& pmap, const KeyIt& pit)
7.49 - : MapIteratorBase<Map>(pit), map(&pmap) {}
7.50 + MapIterator(Map& pmap, const KeyIt& pit) : Base(pit), map(&pmap) {}
7.51
7.52 /// Dereference operator for the iterator.
7.53 PairReferenceType operator*() {
7.54 - return PairReferenceType(it, (*map)[it]);
7.55 + return PairReferenceType(Base::it, (*map)[Base::it]);
7.56 }
7.57
7.58 /// The pointer type of the iterator.
7.59 @@ -132,24 +142,32 @@
7.60
7.61 /// Arrow operator for the iterator.
7.62 PairPointerType operator->() {
7.63 - return PairPointerType(it, ((*map)[it]));
7.64 + return PairPointerType(Base::it, ((*map)[Base::it]));
7.65 }
7.66
7.67 /// The pre increment operator of the iterator.
7.68 MapIterator& operator++() {
7.69 - increment();
7.70 + Base::increment();
7.71 return *this;
7.72 }
7.73
7.74 /// The post increment operator of the iterator.
7.75 MapIterator operator++(int) {
7.76 - MapIterator tmp(it);
7.77 - increment();
7.78 + MapIterator tmp(*this);
7.79 + Base::increment();
7.80 return tmp;
7.81 }
7.82
7.83 private:
7.84 Map* map;
7.85 +
7.86 + public:
7.87 + // STL compatibility typedefs.
7.88 + typedef std::forward_iterator_tag iterator_category;
7.89 + typedef int difference_type;
7.90 + typedef PairValueType value_type;
7.91 + typedef PairReferenceType reference;
7.92 + typedef PairPointerType pointer;
7.93 };
7.94
7.95 /** Compatible iterator with the stl maps' iterators.
7.96 @@ -160,6 +178,9 @@
7.97
7.98 public:
7.99
7.100 + /// The iterator base class.
7.101 + typedef MapIteratorBase<Map> Base;
7.102 +
7.103 /// The key type of the iterator.
7.104 typedef typename Map::KeyType KeyType;
7.105 /// The iterator to iterate on the keys.
7.106 @@ -187,21 +208,25 @@
7.107 /// Constructor to initalize the the iterators returned
7.108 /// by the begin() and end().
7.109 MapConstIterator(const Map& pmap, const KeyIt& pit)
7.110 - : MapIteratorBase<Map>(pit), map(&pmap) {}
7.111 + : Base(pit), map(&pmap) {}
7.112
7.113 /// Constructor to create const iterator from a non const.
7.114 MapConstIterator(const MapIterator<Map>& pit) {
7.115 - it = pit.it;
7.116 + Base::it = pit.Base::it;
7.117 map = pit.map;
7.118 }
7.119
7.120 + /// The value type of the iterator.
7.121 + typedef extended_pair<KeyType, const KeyType&,
7.122 + ValueType, const ValueType&> PairValueType;
7.123 +
7.124 /// The reference type of map.
7.125 typedef extended_pair<const KeyType&, const KeyType&,
7.126 ConstReferenceType, ConstReferenceType> PairReferenceType;
7.127
7.128 /// Dereference operator for the iterator.
7.129 PairReferenceType operator*() {
7.130 - return PairReferenceType(it, (*map)[it]);
7.131 + return PairReferenceType(Base::it, (*map)[Base::it]);
7.132 }
7.133
7.134 /// The pointer type of the iterator.
7.135 @@ -217,24 +242,32 @@
7.136
7.137 /// Arrow operator for the iterator.
7.138 PairPointerType operator->() {
7.139 - return PairPointerType(it, ((*map)[it]));
7.140 + return PairPointerType(Base::it, (*map)[Base::it]);
7.141 }
7.142
7.143 /// The pre increment operator of the iterator.
7.144 MapConstIterator& operator++() {
7.145 - increment();
7.146 + Base::increment();
7.147 return *this;
7.148 }
7.149
7.150 /// The post increment operator of the iterator.
7.151 MapConstIterator operator++(int) {
7.152 - MapConstIterator<Map> tmp(it);
7.153 - increment();
7.154 + MapConstIterator tmp(*this);
7.155 + Base::increment();
7.156 return tmp;
7.157 }
7.158
7.159 private:
7.160 const Map* map;
7.161 +
7.162 + public:
7.163 + // STL compatibility typedefs.
7.164 + typedef std::input_iterator_tag iterator_category;
7.165 + typedef int difference_type;
7.166 + typedef PairValueType value_type;
7.167 + typedef PairReferenceType reference;
7.168 + typedef PairPointerType pointer;
7.169 };
7.170
7.171 /** The class makes the KeyIt to an stl compatible iterator
7.172 @@ -245,6 +278,9 @@
7.173
7.174 public:
7.175
7.176 + /// The iterator base class.
7.177 + typedef MapIteratorBase<Map> Base;
7.178 +
7.179 /// The key type of the iterator.
7.180 typedef typename Map::KeyType KeyType;
7.181 /// The iterator to iterate on the keys.
7.182 @@ -256,29 +292,40 @@
7.183 MapKeyIterator() {}
7.184
7.185 /// KeyIt initialized iterator.
7.186 - MapKeyIterator(const KeyIt& pit) : MapIteratorBase<Map>(pit) {}
7.187 + MapKeyIterator(const KeyIt& pit) : Base(pit) {}
7.188
7.189 /// The pre increment operator of the iterator.
7.190 MapKeyIterator& operator++() {
7.191 - increment();
7.192 + Base::increment();
7.193 return *this;
7.194 }
7.195
7.196 /// The post increment operator of the iterator.
7.197 MapKeyIterator operator++(int) {
7.198 MapKeyIterator tmp(*this);
7.199 - increment();
7.200 + Base::increment();
7.201 return tmp;
7.202 }
7.203
7.204 /// The dereferencing operator of the iterator.
7.205 KeyType operator*() const {
7.206 - return static_cast<KeyType>(it);
7.207 + return static_cast<KeyType>(Base::it);
7.208 }
7.209 +
7.210 + public:
7.211 + // STL compatibility typedefs.
7.212 + typedef std::input_iterator_tag iterator_category;
7.213 + typedef int difference_type;
7.214 + typedef KeyType value_type;
7.215 + typedef const KeyType& reference;
7.216 + typedef const KeyType* pointer;
7.217 };
7.218
7.219 template <typename Map> class MapConstValueIterator;
7.220
7.221 + /** MapValueIterator creates an stl compatible iterator
7.222 + * for the values.
7.223 + */
7.224 template <typename Map>
7.225 class MapValueIterator : public MapIteratorBase<Map> {
7.226
7.227 @@ -286,6 +333,9 @@
7.228
7.229 public:
7.230
7.231 + /// The iterator base class.
7.232 + typedef MapIteratorBase<Map> Base;
7.233 +
7.234 /// The key type of the iterator.
7.235 typedef typename Map::KeyType KeyType;
7.236 /// The iterator to iterate on the keys.
7.237 @@ -317,25 +367,25 @@
7.238
7.239 /// Map and KeyIt initialized iterator.
7.240 MapValueIterator(Map& pmap, const KeyIt& pit)
7.241 - : MapIteratorBase<Map>(pit), map(&pmap) {}
7.242 + : Base(pit), map(&pmap) {}
7.243
7.244
7.245 /// The pre increment operator of the iterator.
7.246 MapValueIterator& operator++() {
7.247 - increment();
7.248 + Base::increment();
7.249 return *this;
7.250 }
7.251
7.252 /// The post increment operator of the iterator.
7.253 MapValueIterator operator++(int) {
7.254 MapValueIterator tmp(*this);
7.255 - increment();
7.256 + Base::increment();
7.257 return tmp;
7.258 }
7.259
7.260 /// The dereferencing operator of the iterator.
7.261 ReferenceType operator*() const {
7.262 - return (*map)[it];
7.263 + return (*map)[Base::it];
7.264 }
7.265
7.266 /// The arrow operator of the iterator.
7.267 @@ -343,20 +393,32 @@
7.268 return &(operator*());
7.269 }
7.270
7.271 + public:
7.272 + // STL compatibility typedefs.
7.273 + typedef std::forward_iterator_tag iterator_category;
7.274 + typedef int difference_type;
7.275 + typedef ValueType value_type;
7.276 + typedef ReferenceType reference;
7.277 + typedef PointerType pointer;
7.278 };
7.279
7.280 + /** MapValueIterator creates an stl compatible iterator
7.281 + * for the const values.
7.282 + */
7.283
7.284 template <typename Map>
7.285 class MapConstValueIterator : public MapIteratorBase<Map> {
7.286
7.287 public:
7.288
7.289 + /// The iterator base class.
7.290 + typedef MapIteratorBase<Map> Base;
7.291 +
7.292 /// The key type of the iterator.
7.293 typedef typename Map::KeyType KeyType;
7.294 /// The iterator to iterate on the keys.
7.295 typedef typename Map::KeyIt KeyIt;
7.296
7.297 -
7.298 /// The value type of the iterator.
7.299 typedef typename Map::ValueType ValueType;
7.300 /// The reference type of the iterator.
7.301 @@ -382,30 +444,30 @@
7.302
7.303 /// Constructor to create const iterator from a non const.
7.304 MapConstValueIterator(const MapValueIterator<Map>& pit) {
7.305 - it = pit.it;
7.306 + Base::it = pit.Base::it;
7.307 map = pit.map;
7.308 }
7.309
7.310 /// Map and KeyIt initialized iterator.
7.311 MapConstValueIterator(const Map& pmap, const KeyIt& pit)
7.312 - : MapIteratorBase<Map>(pit), map(&pmap) {}
7.313 + : Base(pit), map(&pmap) {}
7.314
7.315 /// The pre increment operator of the iterator.
7.316 MapConstValueIterator& operator++() {
7.317 - increment();
7.318 + Base::increment();
7.319 return *this;
7.320 }
7.321
7.322 /// The post increment operator of the iterator.
7.323 MapConstValueIterator operator++(int) {
7.324 MapConstValueIterator tmp(*this);
7.325 - increment();
7.326 + Base::increment();
7.327 return tmp;
7.328 }
7.329
7.330 /// The dereferencing operator of the iterator.
7.331 ConstReferenceType operator*() const {
7.332 - return (*map)[it];
7.333 + return (*map)[Base::it];
7.334 }
7.335
7.336 /// The arrow operator of the iterator.
7.337 @@ -413,6 +475,13 @@
7.338 return &(operator*());
7.339 }
7.340
7.341 + public:
7.342 + // STL compatibility typedefs.
7.343 + typedef std::input_iterator_tag iterator_category;
7.344 + typedef int difference_type;
7.345 + typedef ValueType value_type;
7.346 + typedef ConstReferenceType reference;
7.347 + typedef ConstPointerType pointer;
7.348 };
7.349
7.350
7.351 @@ -431,6 +500,21 @@
7.352 /// The iterator to iterate on the keys.
7.353 typedef typename Map::KeyIt KeyIt;
7.354
7.355 +
7.356 + /// The value type of the iterator.
7.357 + typedef typename Map::ValueType ValueType;
7.358 + /// The reference type of the iterator.
7.359 + typedef typename Map::ReferenceType ReferenceType;
7.360 + /// The pointer type of the iterator.
7.361 + typedef typename Map::PointerType PointerType;
7.362 +
7.363 + /// The const value type of the iterator.
7.364 + typedef typename Map::ConstValueType ConstValueType;
7.365 + /// The const reference type of the iterator.
7.366 + typedef typename Map::ConstReferenceType ConstReferenceType;
7.367 + /// The pointer type of the iterator.
7.368 + typedef typename Map::ConstPointerType ConstPointerType;
7.369 +
7.370 /// The map initialized const key set.
7.371 MapConstKeySet(const Map& pmap) : map(&pmap) {}
7.372
7.373 @@ -446,6 +530,14 @@
7.374 ConstIterator end() const {
7.375 return ConstIterator(KeyIt(INVALID));
7.376 }
7.377 +
7.378 + public:
7.379 + // STL compatibility typedefs.
7.380 + typedef ValueType value_type;
7.381 + typedef ConstIterator const_iterator;
7.382 + typedef ConstReferenceType const_reference;
7.383 + typedef ConstPointerType const_pointer;
7.384 + typedef int difference_type;
7.385 };
7.386
7.387 /** This class makes from a map an iteratable set
7.388 @@ -464,6 +556,21 @@
7.389 /// The iterator to iterate on the keys.
7.390 typedef typename Map::KeyIt KeyIt;
7.391
7.392 +
7.393 + /// The value type of the iterator.
7.394 + typedef typename Map::ValueType ValueType;
7.395 + /// The reference type of the iterator.
7.396 + typedef typename Map::ReferenceType ReferenceType;
7.397 + /// The pointer type of the iterator.
7.398 + typedef typename Map::PointerType PointerType;
7.399 +
7.400 + /// The const value type of the iterator.
7.401 + typedef typename Map::ConstValueType ConstValueType;
7.402 + /// The const reference type of the iterator.
7.403 + typedef typename Map::ConstReferenceType ConstReferenceType;
7.404 + /// The pointer type of the iterator.
7.405 + typedef typename Map::ConstPointerType ConstPointerType;
7.406 +
7.407 /// The map initialized const value set.
7.408 MapConstValueSet(const Map& pmap) : map(&pmap) {}
7.409
7.410 @@ -479,6 +586,14 @@
7.411 ConstIterator end() const {
7.412 return ConstIterator(*map, KeyIt(INVALID));
7.413 }
7.414 +
7.415 + public:
7.416 + // STL compatibility typedefs.
7.417 + typedef ValueType value_type;
7.418 + typedef ConstIterator const_iterator;
7.419 + typedef ConstReferenceType const_reference;
7.420 + typedef ConstPointerType const_pointer;
7.421 + typedef int difference_type;
7.422 };
7.423
7.424
7.425 @@ -498,6 +613,21 @@
7.426 /// The iterator to iterate on the keys.
7.427 typedef typename Map::KeyIt KeyIt;
7.428
7.429 +
7.430 + /// The value type of the iterator.
7.431 + typedef typename Map::ValueType ValueType;
7.432 + /// The reference type of the iterator.
7.433 + typedef typename Map::ReferenceType ReferenceType;
7.434 + /// The pointer type of the iterator.
7.435 + typedef typename Map::PointerType PointerType;
7.436 +
7.437 + /// The const value type of the iterator.
7.438 + typedef typename Map::ConstValueType ConstValueType;
7.439 + /// The const reference type of the iterator.
7.440 + typedef typename Map::ConstReferenceType ConstReferenceType;
7.441 + /// The pointer type of the iterator.
7.442 + typedef typename Map::ConstPointerType ConstPointerType;
7.443 +
7.444 /// The map initialized value set.
7.445 MapValueSet(Map& pmap) : map(&pmap) {}
7.446
7.447 @@ -527,6 +657,17 @@
7.448 return Iterator(*map, KeyIt(INVALID));
7.449 }
7.450
7.451 + public:
7.452 + // STL compatibility typedefs.
7.453 + typedef ValueType value_type;
7.454 + typedef Iterator iterator;
7.455 + typedef ConstIterator const_iterator;
7.456 + typedef ReferenceType reference;
7.457 + typedef ConstReferenceType const_reference;
7.458 + typedef PointerType pointer;
7.459 + typedef ConstPointerType const_pointer;
7.460 + typedef int difference_type;
7.461 +
7.462 };
7.463
7.464 /// @}
8.1 --- a/src/hugo/sym_map.h Mon Sep 13 18:00:26 2004 +0000
8.2 +++ b/src/hugo/sym_map.h Mon Sep 13 20:05:13 2004 +0000
8.3 @@ -17,6 +17,7 @@
8.4 * has different parity.
8.5 */
8.6
8.7 +
8.8 template <typename Graph, typename Edge, typename EdgeIt>
8.9 class SymEdgeIt : public EdgeIt {
8.10 public:
8.11 @@ -30,7 +31,7 @@
8.12 */
8.13 SymEdgeIt(const Graph& graph)
8.14 : EdgeIt(graph) {
8.15 - while ( (n & 1) && n != -1) {
8.16 + while ( (EdgeIt::n & 1) && EdgeIt::n != -1) {
8.17 EdgeIt::operator++();
8.18 }
8.19 }
8.20 @@ -44,7 +45,7 @@
8.21 */
8.22 SymEdgeIt(const Graph& graph, const Edge& edge)
8.23 : EdgeIt(graph, edge) {
8.24 - while ( (n & 1) && n != -1) {
8.25 + while ( (EdgeIt::n & 1) && EdgeIt::n != -1) {
8.26 EdgeIt::operator++();
8.27 }
8.28 }
8.29 @@ -53,7 +54,7 @@
8.30 */
8.31 SymEdgeIt& operator++() {
8.32 EdgeIt::operator++();
8.33 - while ( (n & 1) && n != -1) {
8.34 + while ( (EdgeIt::n & 1) && EdgeIt::n != -1) {
8.35 EdgeIt::operator++();
8.36 }
8.37 return *this;
8.38 @@ -121,32 +122,6 @@
8.39 return *this;
8.40 }
8.41
8.42 - /**
8.43 - * The subscript operator. The map can be subscripted by the
8.44 - * actual keys of the graph.
8.45 - */
8.46 - typename MapImpl::ReferenceType operator[](const KeyType& key) {
8.47 - int id = MapImpl::getGraph()->id(key);
8.48 - return MapImpl::operator[](id >> 1);
8.49 - }
8.50 -
8.51 - /**
8.52 - * The const subscript operator. The map can be subscripted by the
8.53 - * actual keys of the graph.
8.54 - */
8.55 - typename MapImpl::ConstReferenceType operator[](const KeyType& key) const {
8.56 - int id = MapImpl::getGraph()->id(key);
8.57 - return MapImpl::operator[](id >> 1);
8.58 - }
8.59 -
8.60 - /** Setter function of the map. Equivalent with map[key] = val.
8.61 - * This is a compatibility feature with the not dereferable maps.
8.62 - */
8.63 - void set(const KeyType& key, const typename MapImpl::ValueType& val) {
8.64 - int id = MapImpl::getGraph()->id(key);
8.65 - MapImpl::operator[](id >> 1) = val;
8.66 - }
8.67 -
8.68 /** Add a new key to the map. It called by the map registry.
8.69 */
8.70 void add(const KeyType& key) {
9.1 --- a/src/hugo/vector_map.h Mon Sep 13 18:00:26 2004 +0000
9.2 +++ b/src/hugo/vector_map.h Mon Sep 13 20:05:13 2004 +0000
9.3 @@ -5,6 +5,7 @@
9.4 #include <vector>
9.5
9.6 #include <hugo/map_iterator.h>
9.7 +#include <hugo/map_bits.h>
9.8
9.9 ///\ingroup graphmaps
9.10 ///\file
9.11 @@ -73,32 +74,20 @@
9.12
9.13 /** Graph and Registry initialized map constructor.
9.14 */
9.15 - VectorMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
9.16 - init();
9.17 - }
9.18 + VectorMap(const Graph& g, MapRegistry& r)
9.19 + : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
9.20
9.21 /** Constructor to use default value to initialize the map.
9.22 */
9.23 VectorMap(const Graph& g, MapRegistry& r, const Value& v)
9.24 - : MapBase(g, r) {
9.25 - for (KeyIt it(*getGraph()); it != INVALID; ++it) {
9.26 - int id = getGraph()->id(it);
9.27 - if (id >= (int)container.size()) {
9.28 - container.resize(id + 1);
9.29 - }
9.30 - set(it, v);
9.31 - }
9.32 - }
9.33 + : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {}
9.34
9.35 /** Constructor to copy a map of an other map type.
9.36 */
9.37 template <typename CMap> VectorMap(const CMap& copy) : MapBase(copy) {
9.38 - if (getGraph()) {
9.39 - for (KeyIt it(*getGraph()); it != INVALID; ++it) {
9.40 - int id = getGraph()->id(it);
9.41 - if (id >= (int)container.size()) {
9.42 - container.resize(id + 1);
9.43 - }
9.44 + if (MapBase::getGraph()) {
9.45 + container.resize(KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph())+1);
9.46 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
9.47 set(it, copy[it]);
9.48 }
9.49 }
9.50 @@ -107,16 +96,11 @@
9.51 /** Assign operator to copy a map an other map type.
9.52 */
9.53 template <typename CMap> VectorMap& operator=(const CMap& copy) {
9.54 - if (getGraph()) {
9.55 - destroy();
9.56 - }
9.57 + container.clear();
9.58 this->MapBase::operator=(copy);
9.59 - if (getGraph()) {
9.60 - for (KeyIt it(*getGraph()); it != INVALID; ++it) {
9.61 - int id = getGraph()->id(it);
9.62 - if (id >= (int)container.size()) {
9.63 - container.resize(id + 1);
9.64 - }
9.65 + if (MapBase::getGraph()) {
9.66 + container.resize(KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph())+1);
9.67 + for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
9.68 set(it, copy[it]);
9.69 }
9.70 }
9.71 @@ -133,7 +117,7 @@
9.72 * actual keys of the graph.
9.73 */
9.74 ReferenceType operator[](const KeyType& key) {
9.75 - int id = getGraph()->id(key);
9.76 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
9.77 return container[id];
9.78 }
9.79
9.80 @@ -142,7 +126,7 @@
9.81 * actual keys of the graph.
9.82 */
9.83 ConstReferenceType operator[](const KeyType& key) const {
9.84 - int id = getGraph()->id(key);
9.85 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
9.86 return container[id];
9.87 }
9.88
9.89 @@ -150,14 +134,14 @@
9.90 * This is a compatibility feature with the not dereferable maps.
9.91 */
9.92 void set(const KeyType& key, const ValueType& val) {
9.93 - int id = getGraph()->id(key);
9.94 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
9.95 container[id] = val;
9.96 }
9.97
9.98 /** Add a new key to the map. It called by the map registry.
9.99 */
9.100 void add(const KeyType& key) {
9.101 - int id = getGraph()->id(key);
9.102 + int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
9.103 if (id >= (int)container.size()) {
9.104 container.resize(id + 1);
9.105 }
9.106 @@ -231,7 +215,18 @@
9.107
9.108 Container container;
9.109
9.110 -
9.111 + public:
9.112 + // STL compatibility typedefs.
9.113 + typedef Iterator iterator;
9.114 + typedef ConstIterator const_iterator;
9.115 + typedef typename Iterator::PairValueType value_type;
9.116 + typedef typename Iterator::KeyType key_type;
9.117 + typedef typename Iterator::ValueType data_type;
9.118 + typedef typename Iterator::PairReferenceType reference;
9.119 + typedef typename Iterator::PairPointerType pointer;
9.120 + typedef typename ConstIterator::PairReferenceType const_reference;
9.121 + typedef typename ConstIterator::PairPointerType const_pointer;
9.122 + typedef int difference_type;
9.123 };
9.124
9.125 /// @}
10.1 --- a/src/test/test_tools.h Mon Sep 13 18:00:26 2004 +0000
10.2 +++ b/src/test/test_tools.h Mon Sep 13 20:05:13 2004 +0000
10.3 @@ -1,3 +1,4 @@
10.4 +// -*- c++ -*-
10.5 #ifndef HUGO_TEST_TEST_TOOLS_H
10.6 #define HUGO_TEST_TEST_TOOLS_H
10.7