1.1 --- a/src/lemon/array_map.h Mon Oct 25 13:29:46 2004 +0000
1.2 +++ b/src/lemon/array_map.h Wed Oct 27 22:38:50 2004 +0000
1.3 @@ -20,7 +20,6 @@
1.4 #include <memory>
1.5
1.6 #include <lemon/map_iterator.h>
1.7 -#include <lemon/map_bits.h>
1.8
1.9 ///\ingroup graphmaps
1.10 ///\file
1.11 @@ -42,22 +41,32 @@
1.12 * will belong to and the ValueType.
1.13 */
1.14
1.15 - template <typename MapRegistry, typename Value>
1.16 - class ArrayMap : public MapRegistry::MapBase {
1.17 + template <typename _Graph,
1.18 + typename _Item,
1.19 + typename _ItemIt,
1.20 + typename _IdMap,
1.21 + typename _Value>
1.22 + class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase {
1.23
1.24 - template <typename MR, typename V> friend class ArrayMap;
1.25 -
1.26 public:
1.27
1.28 /// The graph type of the maps.
1.29 - typedef typename MapRegistry::Graph Graph;
1.30 + typedef _Graph Graph;
1.31 /// The key type of the maps.
1.32 - typedef typename MapRegistry::KeyType KeyType;
1.33 + typedef _Item KeyType;
1.34 +
1.35 + typedef AlterationObserverRegistry<_Item> Registry;
1.36 +
1.37 + private:
1.38 /// The iterator to iterate on the keys.
1.39 - typedef typename MapRegistry::KeyIt KeyIt;
1.40 + typedef _ItemIt KeyIt;
1.41 +
1.42 + typedef _IdMap IdMap;
1.43 +
1.44 + typedef _Value Value;
1.45
1.46 /// The MapBase of the Map which imlements the core regisitry function.
1.47 - typedef typename MapRegistry::MapBase MapBase;
1.48 + typedef typename Registry::ObserverBase Parent;
1.49
1.50
1.51 public:
1.52 @@ -77,52 +86,47 @@
1.53 typedef const Value* ConstPointerType;
1.54
1.55
1.56 + private:
1.57 typedef std::allocator<Value> Allocator;
1.58
1.59 -
1.60 +
1.61 + public:
1.62 +
1.63 /** Graph and Registry initialized map constructor.
1.64 */
1.65 - ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
1.66 + ArrayMap(const Graph& _g, Registry& _r) : graph(&_g) {
1.67 + attach(_r);
1.68 allocate_memory();
1.69 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.70 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.71 + for (KeyIt it(*graph); it != INVALID; ++it) {
1.72 + int id = IdMap(*graph)[it];
1.73 allocator.construct(&(values[id]), Value());
1.74 }
1.75 }
1.76
1.77 - /** Constructor to use default value to initialize the map.
1.78 - */
1.79 - ArrayMap(const Graph& g, MapRegistry& r, const Value& v)
1.80 - : MapBase(g, r) {
1.81 + /// Constructor to use default value to initialize the map.
1.82 +
1.83 + /// It constrates a map and initialize all of the the map.
1.84 +
1.85 + ArrayMap(const Graph& _g, Registry& _r, const Value& _v) : graph(&_g) {
1.86 + attach(_r);
1.87 allocate_memory();
1.88 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.89 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.90 - allocator.construct(&(values[id]), v);
1.91 + for (KeyIt it(*graph); it != INVALID; ++it) {
1.92 + int id = IdMap(*graph)[it];
1.93 + allocator.construct(&(values[id]), _v);
1.94 }
1.95 }
1.96
1.97 /** Constructor to copy a map of the same map type.
1.98 */
1.99 - ArrayMap(const ArrayMap& copy) : MapBase(copy) {
1.100 + ArrayMap(const ArrayMap& copy) {
1.101 + if (copy.attached()) {
1.102 + attach(*copy.getRegistry());
1.103 + }
1.104 capacity = copy.capacity;
1.105 if (capacity == 0) return;
1.106 values = allocator.allocate(capacity);
1.107 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.108 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.109 - allocator.construct(&(values[id]), copy.values[id]);
1.110 - }
1.111 - }
1.112 -
1.113 - /** Constructor to copy a map of an other map type.
1.114 - */
1.115 - template <typename TT>
1.116 - ArrayMap(const ArrayMap<MapRegistry, TT>& copy)
1.117 - : MapBase(copy) {
1.118 - capacity = copy.capacity;
1.119 - if (capacity == 0) return;
1.120 - values = allocator.allocate(capacity);
1.121 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.122 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.123 + for (KeyIt it(*graph); it != INVALID; ++it) {
1.124 + int id = IdMap(*graph)[it];
1.125 allocator.construct(&(values[id]), copy.values[id]);
1.126 }
1.127 }
1.128 @@ -132,58 +136,33 @@
1.129 ArrayMap& operator=(const ArrayMap& copy) {
1.130 if (© == this) return *this;
1.131
1.132 - if (MapBase::getGraph() != copy.getGraph()) {
1.133 - if (capacity != 0) {
1.134 - MapBase::destroy();
1.135 - allocator.deallocate(values, capacity);
1.136 + if (graph != copy.graph) {
1.137 + if (attached()) {
1.138 + clear();
1.139 + detach();
1.140 }
1.141 -
1.142 - MapBase::operator=(copy);
1.143 + if (copy.attached()) {
1.144 + attach(*copy.getRegistry());
1.145 + }
1.146 capacity = copy.capacity;
1.147 if (capacity == 0) return *this;
1.148 values = allocator.allocate(capacity);
1.149 }
1.150
1.151 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.152 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.153 + for (KeyIt it(*graph); it != INVALID; ++it) {
1.154 + int id = IdMap(*graph)[it];
1.155 allocator.construct(&(values[id]), copy.values[id]);
1.156 }
1.157
1.158 return *this;
1.159 }
1.160
1.161 - /** Assign operator to copy a map of an other map type.
1.162 - */
1.163 - template <typename TT>
1.164 - ArrayMap& operator=(const ArrayMap<MapRegistry, TT>& copy) {
1.165 -
1.166 - if (MapBase::getGraph() != copy.getGraph()) {
1.167 - if (capacity != 0) {
1.168 - MapBase::destroy();
1.169 - allocator.deallocate(values, capacity);
1.170 - }
1.171 -
1.172 - MapBase::operator=(copy);
1.173 -
1.174 - capacity = copy.capacity;
1.175 - if (capacity == 0) return *this;
1.176 - values = allocator.allocate(capacity);
1.177 - }
1.178 -
1.179 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.180 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.181 - allocator.construct(&(values[id]), copy.values[id]);
1.182 - }
1.183 -
1.184 - return *this;
1.185 - }
1.186 -
1.187 /** The destructor of the map.
1.188 */
1.189 - virtual ~ArrayMap() {
1.190 - if (capacity != 0) {
1.191 - MapBase::destroy();
1.192 - allocator.deallocate(values, capacity);
1.193 + virtual ~ArrayMap() {
1.194 + if (attached()) {
1.195 + clear();
1.196 + detach();
1.197 }
1.198 }
1.199
1.200 @@ -193,7 +172,7 @@
1.201 * actual keys of the graph.
1.202 */
1.203 ReferenceType operator[](const KeyType& key) {
1.204 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.205 + int id = IdMap(*graph)[key];
1.206 return values[id];
1.207 }
1.208
1.209 @@ -202,7 +181,7 @@
1.210 * actual keys of the graph.
1.211 */
1.212 ConstReferenceType operator[](const KeyType& key) const {
1.213 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.214 + int id = IdMap(*graph)[key];
1.215 return values[id];
1.216 }
1.217
1.218 @@ -210,22 +189,21 @@
1.219 * This is a compatibility feature with the not dereferable maps.
1.220 */
1.221 void set(const KeyType& key, const ValueType& val) {
1.222 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.223 - values[id] = val;
1.224 + (*this)[key] = val;
1.225 }
1.226
1.227 /** Add a new key to the map. It called by the map registry.
1.228 */
1.229 void add(const KeyType& key) {
1.230 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.231 + int id = IdMap(*graph)[key];
1.232 if (id >= capacity) {
1.233 int new_capacity = (capacity == 0 ? 1 : capacity);
1.234 while (new_capacity <= id) {
1.235 new_capacity <<= 1;
1.236 }
1.237 - Value* new_values = allocator.allocate(new_capacity);;
1.238 - for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
1.239 - int jd = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
1.240 + Value* new_values = allocator.allocate(new_capacity);
1.241 + for (KeyIt it(*graph); it != INVALID; ++it) {
1.242 + int jd = IdMap(*graph)[it];
1.243 if (id != jd) {
1.244 allocator.construct(&(new_values[jd]), values[jd]);
1.245 allocator.destroy(&(values[jd]));
1.246 @@ -241,77 +219,86 @@
1.247 /** Erase a key from the map. It called by the map registry.
1.248 */
1.249 void erase(const KeyType& key) {
1.250 - int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
1.251 + int id = IdMap(*graph)[key];
1.252 allocator.destroy(&(values[id]));
1.253 }
1.254
1.255 - /** Clear the data structure.
1.256 - */
1.257 + void build() {
1.258 + allocate_memory();
1.259 + for (KeyIt it(*graph); it != INVALID; ++it) {
1.260 + int id = IdMap(*graph)[it];
1.261 + allocator.construct(&(values[id]), Value());
1.262 + }
1.263 + }
1.264 +
1.265 void clear() {
1.266 if (capacity != 0) {
1.267 - MapBase::destroy();
1.268 + for (KeyIt it(*graph); it != INVALID; ++it) {
1.269 + int id = IdMap(*graph)[it];
1.270 + allocator.destroy(&(values[id]));
1.271 + }
1.272 allocator.deallocate(values, capacity);
1.273 capacity = 0;
1.274 }
1.275 }
1.276
1.277 - /// The stl compatible pair iterator of the map.
1.278 - typedef MapIterator<ArrayMap> Iterator;
1.279 - /// The stl compatible const pair iterator of the map.
1.280 - typedef MapConstIterator<ArrayMap> ConstIterator;
1.281 +// /// The stl compatible pair iterator of the map.
1.282 +// typedef MapIterator<ArrayMap> Iterator;
1.283 +// /// The stl compatible const pair iterator of the map.
1.284 +// typedef MapConstIterator<ArrayMap> ConstIterator;
1.285
1.286 - /** Returns the begin iterator of the map.
1.287 - */
1.288 - Iterator begin() {
1.289 - return Iterator(*this, KeyIt(*MapBase::getGraph()));
1.290 - }
1.291 +// /** Returns the begin iterator of the map.
1.292 +// */
1.293 +// Iterator begin() {
1.294 +// return Iterator(*this, KeyIt(*MapBase::getGraph()));
1.295 +// }
1.296
1.297 - /** Returns the end iterator of the map.
1.298 - */
1.299 - Iterator end() {
1.300 - return Iterator(*this, INVALID);
1.301 - }
1.302 +// /** Returns the end iterator of the map.
1.303 +// */
1.304 +// Iterator end() {
1.305 +// return Iterator(*this, INVALID);
1.306 +// }
1.307
1.308 - /** Returns the begin ConstIterator of the map.
1.309 - */
1.310 - ConstIterator begin() const {
1.311 - return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
1.312 - }
1.313 +// /** Returns the begin ConstIterator of the map.
1.314 +// */
1.315 +// ConstIterator begin() const {
1.316 +// return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
1.317 +// }
1.318
1.319 - /** Returns the end const_iterator of the map.
1.320 - */
1.321 - ConstIterator end() const {
1.322 - return ConstIterator(*this, INVALID);
1.323 - }
1.324 +// /** Returns the end const_iterator of the map.
1.325 +// */
1.326 +// ConstIterator end() const {
1.327 +// return ConstIterator(*this, INVALID);
1.328 +// }
1.329
1.330 - /// The KeySet of the Map.
1.331 - typedef MapConstKeySet<ArrayMap> ConstKeySet;
1.332 +// /// The KeySet of the Map.
1.333 +// typedef MapConstKeySet<ArrayMap> ConstKeySet;
1.334
1.335 - /// KeySet getter function.
1.336 - ConstKeySet keySet() const {
1.337 - return ConstKeySet(*this);
1.338 - }
1.339 +// /// KeySet getter function.
1.340 +// ConstKeySet keySet() const {
1.341 +// return ConstKeySet(*this);
1.342 +// }
1.343
1.344 - /// The ConstValueSet of the Map.
1.345 - typedef MapConstValueSet<ArrayMap> ConstValueSet;
1.346 +// /// The ConstValueSet of the Map.
1.347 +// typedef MapConstValueSet<ArrayMap> ConstValueSet;
1.348
1.349 - /// ConstValueSet getter function.
1.350 - ConstValueSet valueSet() const {
1.351 - return ConstValueSet(*this);
1.352 - }
1.353 +// /// ConstValueSet getter function.
1.354 +// ConstValueSet valueSet() const {
1.355 +// return ConstValueSet(*this);
1.356 +// }
1.357
1.358 - /// The ValueSet of the Map.
1.359 - typedef MapValueSet<ArrayMap> ValueSet;
1.360 +// /// The ValueSet of the Map.
1.361 +// typedef MapValueSet<ArrayMap> ValueSet;
1.362
1.363 - /// ValueSet getter function.
1.364 - ValueSet valueSet() {
1.365 - return ValueSet(*this);
1.366 - }
1.367 +// /// ValueSet getter function.
1.368 +// ValueSet valueSet() {
1.369 +// return ValueSet(*this);
1.370 +// }
1.371
1.372 private:
1.373
1.374 void allocate_memory() {
1.375 - int max_id = KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph());
1.376 + int max_id = IdMap(*graph).maxId();
1.377 if (max_id == -1) {
1.378 capacity = 0;
1.379 values = 0;
1.380 @@ -324,24 +311,88 @@
1.381 values = allocator.allocate(capacity);
1.382 }
1.383
1.384 + const Graph* graph;
1.385 int capacity;
1.386 Value* values;
1.387 Allocator allocator;
1.388
1.389 public:
1.390 - // STL compatibility typedefs.
1.391 - typedef Iterator iterator;
1.392 - typedef ConstIterator const_iterator;
1.393 - typedef typename Iterator::PairValueType value_type;
1.394 - typedef typename Iterator::KeyType key_type;
1.395 - typedef typename Iterator::ValueType data_type;
1.396 - typedef typename Iterator::PairReferenceType reference;
1.397 - typedef typename Iterator::PairPointerType pointer;
1.398 - typedef typename ConstIterator::PairReferenceType const_reference;
1.399 - typedef typename ConstIterator::PairPointerType const_pointer;
1.400 - typedef int difference_type;
1.401 +// // STL compatibility typedefs.
1.402 +// typedef Iterator iterator;
1.403 +// typedef ConstIterator const_iterator;
1.404 +// typedef typename Iterator::PairValueType value_type;
1.405 +// typedef typename Iterator::KeyType key_type;
1.406 +// typedef typename Iterator::ValueType data_type;
1.407 +// typedef typename Iterator::PairReferenceType reference;
1.408 +// typedef typename Iterator::PairPointerType pointer;
1.409 +// typedef typename ConstIterator::PairReferenceType const_reference;
1.410 +// typedef typename ConstIterator::PairPointerType const_pointer;
1.411 +// typedef int difference_type;
1.412 };
1.413
1.414 + template <typename _Base>
1.415 + class ArrayMappableGraphExtender : public _Base {
1.416 + public:
1.417 +
1.418 + typedef ArrayMappableGraphExtender<_Base> Graph;
1.419 + typedef _Base Parent;
1.420 +
1.421 + typedef typename Parent::Node Node;
1.422 + typedef typename Parent::NodeIt NodeIt;
1.423 + typedef typename Parent::NodeIdMap NodeIdMap;
1.424 + typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
1.425 +
1.426 + typedef typename Parent::Edge Edge;
1.427 + typedef typename Parent::EdgeIt EdgeIt;
1.428 + typedef typename Parent::EdgeIdMap EdgeIdMap;
1.429 + typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
1.430 +
1.431 +
1.432 +
1.433 + template <typename _Value>
1.434 + class NodeMap : public ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> {
1.435 + public:
1.436 + typedef ArrayMappableGraphExtender<_Base> Graph;
1.437 +
1.438 + typedef typename Graph::Node Node;
1.439 + typedef typename Graph::NodeIt NodeIt;
1.440 + typedef typename Graph::NodeIdMap NodeIdMap;
1.441 +
1.442 + typedef ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;
1.443 +
1.444 + typedef typename Parent::Graph Graph;
1.445 + typedef typename Parent::Value Value;
1.446 +
1.447 + NodeMap(const Graph& g)
1.448 + : Parent(g, g.getNodeObserverRegistry()) {}
1.449 + NodeMap(const Graph& g, const Value& v)
1.450 + : Parent(g, g.getNodeObserverRegistry(), v) {}
1.451 +
1.452 + };
1.453 +
1.454 + template <typename _Value>
1.455 + class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> {
1.456 + public:
1.457 + typedef ArrayMappableGraphExtender<_Base> Graph;
1.458 +
1.459 + typedef typename Graph::Edge Edge;
1.460 + typedef typename Graph::EdgeIt EdgeIt;
1.461 + typedef typename Graph::EdgeIdMap EdgeIdMap;
1.462 +
1.463 + typedef ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;
1.464 +
1.465 + typedef typename Parent::Graph Graph;
1.466 + typedef typename Parent::Value Value;
1.467 +
1.468 + EdgeMap(const Graph& g)
1.469 + : Parent(g, g.getEdgeObserverRegistry()) {}
1.470 + EdgeMap(const Graph& g, const Value& v)
1.471 + : Parent(g, g.getEdgeObserverRegistry(), v) {}
1.472 +
1.473 + };
1.474 +
1.475 + };
1.476 +
1.477 /// @}
1.478
1.479 }