00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_DEFAULT_MAP_H
00020 #define LEMON_DEFAULT_MAP_H
00021
00022
00023 #include <lemon/bits/array_map.h>
00024 #include <lemon/bits/vector_map.h>
00025
00030
00031 namespace lemon {
00032
00033
00034 template <typename _Graph, typename _Item, typename _Value>
00035 struct DefaultMapSelector {
00036 typedef ArrayMap<_Graph, _Item, _Value> Map;
00037 };
00038
00039
00040 template <typename _Graph, typename _Item>
00041 struct DefaultMapSelector<_Graph, _Item, bool> {
00042 typedef VectorMap<_Graph, _Item, bool> Map;
00043 };
00044
00045
00046 template <typename _Graph, typename _Item>
00047 struct DefaultMapSelector<_Graph, _Item, char> {
00048 typedef VectorMap<_Graph, _Item, char> Map;
00049 };
00050
00051 template <typename _Graph, typename _Item>
00052 struct DefaultMapSelector<_Graph, _Item, signed char> {
00053 typedef VectorMap<_Graph, _Item, signed char> Map;
00054 };
00055
00056 template <typename _Graph, typename _Item>
00057 struct DefaultMapSelector<_Graph, _Item, unsigned char> {
00058 typedef VectorMap<_Graph, _Item, unsigned char> Map;
00059 };
00060
00061
00062
00063 template <typename _Graph, typename _Item>
00064 struct DefaultMapSelector<_Graph, _Item, signed int> {
00065 typedef VectorMap<_Graph, _Item, signed int> Map;
00066 };
00067
00068 template <typename _Graph, typename _Item>
00069 struct DefaultMapSelector<_Graph, _Item, unsigned int> {
00070 typedef VectorMap<_Graph, _Item, unsigned int> Map;
00071 };
00072
00073
00074
00075 template <typename _Graph, typename _Item>
00076 struct DefaultMapSelector<_Graph, _Item, signed short> {
00077 typedef VectorMap<_Graph, _Item, signed short> Map;
00078 };
00079
00080 template <typename _Graph, typename _Item>
00081 struct DefaultMapSelector<_Graph, _Item, unsigned short> {
00082 typedef VectorMap<_Graph, _Item, unsigned short> Map;
00083 };
00084
00085
00086
00087 template <typename _Graph, typename _Item>
00088 struct DefaultMapSelector<_Graph, _Item, signed long> {
00089 typedef VectorMap<_Graph, _Item, signed long> Map;
00090 };
00091
00092 template <typename _Graph, typename _Item>
00093 struct DefaultMapSelector<_Graph, _Item, unsigned long> {
00094 typedef VectorMap<_Graph, _Item, unsigned long> Map;
00095 };
00096
00097
00098
00099
00100
00101 template <typename _Graph, typename _Item>
00102 struct DefaultMapSelector<_Graph, _Item, float> {
00103 typedef VectorMap<_Graph, _Item, float> Map;
00104 };
00105
00106
00107
00108 template <typename _Graph, typename _Item>
00109 struct DefaultMapSelector<_Graph, _Item, double> {
00110 typedef VectorMap<_Graph, _Item, double> Map;
00111 };
00112
00113
00114
00115 template <typename _Graph, typename _Item>
00116 struct DefaultMapSelector<_Graph, _Item, long double> {
00117 typedef VectorMap<_Graph, _Item, long double> Map;
00118 };
00119
00120
00121
00122 template <typename _Graph, typename _Item, typename _Ptr>
00123 struct DefaultMapSelector<_Graph, _Item, _Ptr*> {
00124 typedef VectorMap<_Graph, _Item, _Ptr*> Map;
00125 };
00126
00128 template <
00129 typename _Graph,
00130 typename _Item,
00131 typename _Value>
00132 class DefaultMap
00133 : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
00134 public:
00135 typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
00136 typedef DefaultMap<_Graph, _Item, _Value> Map;
00137
00138 typedef typename Parent::Graph Graph;
00139 typedef typename Parent::Value Value;
00140
00141 DefaultMap(const Graph& _g) : Parent(_g) {}
00142 DefaultMap(const Graph& _g, const Value& _v) : Parent(_g, _v) {}
00143
00144 };
00145
00146
00148 template <typename _Base>
00149 class MappableGraphExtender : public _Base {
00150 public:
00151
00152 typedef MappableGraphExtender<_Base> Graph;
00153 typedef _Base Parent;
00154
00155 typedef typename Parent::Node Node;
00156 typedef typename Parent::NodeIt NodeIt;
00157
00158 typedef typename Parent::Edge Edge;
00159 typedef typename Parent::EdgeIt EdgeIt;
00160
00161
00162 template <typename _Value>
00163 class NodeMap
00164 : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
00165 public:
00166 typedef MappableGraphExtender Graph;
00167 typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
00168
00169 NodeMap(const Graph& _g)
00170 : Parent(_g) {}
00171 NodeMap(const Graph& _g, const _Value& _v)
00172 : Parent(_g, _v) {}
00173
00174 NodeMap& operator=(const NodeMap& cmap) {
00175 return operator=<NodeMap>(cmap);
00176 }
00177
00178
00185 template <typename CMap>
00186 NodeMap& operator=(const CMap& cmap) {
00187 checkConcept<concept::ReadMap<Node, _Value>, CMap>();
00188 const typename Parent::Graph* graph = Parent::getGraph();
00189 Node it;
00190 for (graph->first(it); it != INVALID; graph->next(it)) {
00191 Parent::set(it, cmap[it]);
00192 }
00193 return *this;
00194 }
00195
00196 };
00197
00198 template <typename _Value>
00199 class EdgeMap
00200 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
00201 public:
00202 typedef MappableGraphExtender Graph;
00203 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
00204
00205 EdgeMap(const Graph& _g)
00206 : Parent(_g) {}
00207 EdgeMap(const Graph& _g, const _Value& _v)
00208 : Parent(_g, _v) {}
00209
00210 EdgeMap& operator=(const EdgeMap& cmap) {
00211 return operator=<EdgeMap>(cmap);
00212 }
00213
00214 template <typename CMap>
00215 EdgeMap& operator=(const CMap& cmap) {
00216 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
00217 const typename Parent::Graph* graph = Parent::getGraph();
00218 Edge it;
00219 for (graph->first(it); it != INVALID; graph->next(it)) {
00220 Parent::set(it, cmap[it]);
00221 }
00222 return *this;
00223 }
00224 };
00225
00226 };
00227
00229 template <typename _Base>
00230 class MappableEdgeSetExtender : public _Base {
00231 public:
00232
00233 typedef MappableEdgeSetExtender<_Base> Graph;
00234 typedef _Base Parent;
00235
00236 typedef typename Parent::Edge Edge;
00237 typedef typename Parent::EdgeIt EdgeIt;
00238
00239 template <typename _Value>
00240 class EdgeMap
00241 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
00242 public:
00243 typedef MappableEdgeSetExtender Graph;
00244 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
00245
00246 EdgeMap(const Graph& _g)
00247 : Parent(_g) {}
00248 EdgeMap(const Graph& _g, const _Value& _v)
00249 : Parent(_g, _v) {}
00250
00251 EdgeMap& operator=(const EdgeMap& cmap) {
00252 return operator=<EdgeMap>(cmap);
00253 }
00254
00255 template <typename CMap>
00256 EdgeMap& operator=(const CMap& cmap) {
00257 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
00258 const typename Parent::Graph* graph = Parent::getGraph();
00259 Edge it;
00260 for (graph->first(it); it != INVALID; graph->next(it)) {
00261 Parent::set(it, cmap[it]);
00262 }
00263 return *this;
00264 }
00265 };
00266
00267 };
00268
00270 template <typename _Base>
00271 class MappableUGraphExtender :
00272 public MappableGraphExtender<_Base> {
00273 public:
00274
00275 typedef MappableUGraphExtender Graph;
00276 typedef MappableGraphExtender<_Base> Parent;
00277
00278 typedef typename Parent::UEdge UEdge;
00279
00280 template <typename _Value>
00281 class UEdgeMap
00282 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
00283 public:
00284 typedef MappableUGraphExtender Graph;
00285 typedef IterableMapExtender<
00286 DefaultMap<Graph, UEdge, _Value> > Parent;
00287
00288 UEdgeMap(const Graph& _g)
00289 : Parent(_g) {}
00290 UEdgeMap(const Graph& _g, const _Value& _v)
00291 : Parent(_g, _v) {}
00292
00293 UEdgeMap& operator=(const UEdgeMap& cmap) {
00294 return operator=<UEdgeMap>(cmap);
00295 }
00296
00297 template <typename CMap>
00298 UEdgeMap& operator=(const CMap& cmap) {
00299 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
00300 const typename Parent::Graph* graph = Parent::getGraph();
00301 UEdge it;
00302 for (graph->first(it); it != INVALID; graph->next(it)) {
00303 Parent::set(it, cmap[it]);
00304 }
00305 return *this;
00306 }
00307 };
00308
00309
00310 };
00311
00313 template <typename _Base>
00314 class MappableUEdgeSetExtender :
00315 public MappableEdgeSetExtender<_Base> {
00316 public:
00317
00318 typedef MappableUEdgeSetExtender Graph;
00319 typedef MappableEdgeSetExtender<_Base> Parent;
00320
00321 typedef typename Parent::UEdge UEdge;
00322
00323 template <typename _Value>
00324 class UEdgeMap
00325 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
00326 public:
00327 typedef MappableUEdgeSetExtender Graph;
00328 typedef IterableMapExtender<
00329 DefaultMap<Graph, UEdge, _Value> > Parent;
00330
00331 UEdgeMap(const Graph& _g)
00332 : Parent(_g) {}
00333 UEdgeMap(const Graph& _g, const _Value& _v)
00334 : Parent(_g, _v) {}
00335
00336 UEdgeMap& operator=(const UEdgeMap& cmap) {
00337 return operator=<UEdgeMap>(cmap);
00338 }
00339
00340 template <typename CMap>
00341 UEdgeMap& operator=(const CMap& cmap) {
00342 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
00343 const typename Parent::Graph* graph = Parent::getGraph();
00344 UEdge it;
00345 for (graph->first(it); it != INVALID; graph->next(it)) {
00346 Parent::set(it, cmap[it]);
00347 }
00348 return *this;
00349 }
00350 };
00351
00352
00353 };
00354
00355
00356 template <typename _Base>
00357 class MappableBpUGraphExtender : public _Base {
00358 public:
00359
00360 typedef _Base Parent;
00361 typedef MappableBpUGraphExtender Graph;
00362
00363 typedef typename Parent::Node Node;
00364 typedef typename Parent::ANode ANode;
00365 typedef typename Parent::BNode BNode;
00366 typedef typename Parent::Edge Edge;
00367 typedef typename Parent::UEdge UEdge;
00368
00369 template <typename _Value>
00370 class ANodeMap
00371 : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
00372 public:
00373 typedef MappableBpUGraphExtender Graph;
00374 typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >
00375 Parent;
00376
00377 ANodeMap(const Graph& _g)
00378 : Parent(_g) {}
00379 ANodeMap(const Graph& _g, const _Value& _v)
00380 : Parent(_g, _v) {}
00381
00382 ANodeMap& operator=(const ANodeMap& cmap) {
00383 return operator=<ANodeMap>(cmap);
00384 }
00385
00386
00393 template <typename CMap>
00394 ANodeMap& operator=(const CMap& cmap) {
00395 checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
00396 const typename Parent::Graph* graph = Parent::getGraph();
00397 ANode it;
00398 for (graph->first(it); it != INVALID; graph->next(it)) {
00399 Parent::set(it, cmap[it]);
00400 }
00401 return *this;
00402 }
00403
00404 };
00405
00406 template <typename _Value>
00407 class BNodeMap
00408 : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {
00409 public:
00410 typedef MappableBpUGraphExtender Graph;
00411 typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >
00412 Parent;
00413
00414 BNodeMap(const Graph& _g)
00415 : Parent(_g) {}
00416 BNodeMap(const Graph& _g, const _Value& _v)
00417 : Parent(_g, _v) {}
00418
00419 BNodeMap& operator=(const BNodeMap& cmap) {
00420 return operator=<BNodeMap>(cmap);
00421 }
00422
00423
00430 template <typename CMap>
00431 BNodeMap& operator=(const CMap& cmap) {
00432 checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
00433 const typename Parent::Graph* graph = Parent::getGraph();
00434 BNode it;
00435 for (graph->first(it); it != INVALID; graph->next(it)) {
00436 Parent::set(it, cmap[it]);
00437 }
00438 return *this;
00439 }
00440
00441 };
00442
00443 protected:
00444
00445 template <typename _Value>
00446 class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
00447 public:
00448 typedef MappableBpUGraphExtender Graph;
00449
00450 typedef Node Key;
00451 typedef _Value Value;
00452
00454 typedef typename BNodeMap<_Value>::Reference Reference;
00456 typedef typename BNodeMap<_Value>::Pointer Pointer;
00457
00459 typedef const Value ConstValue;
00461 typedef typename BNodeMap<_Value>::ConstReference ConstReference;
00463 typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
00464
00465 typedef True ReferenceMapTag;
00466
00467 NodeMapBase(const Graph& _g)
00468 : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
00469 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
00470 }
00471 NodeMapBase(const Graph& _g, const _Value& _v)
00472 : graph(&_g), bNodeMap(_g, _v),
00473 aNodeMap(_g, _v) {
00474 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
00475 }
00476
00477 virtual ~NodeMapBase() {
00478 if (Parent::NodeNotifier::ObserverBase::attached()) {
00479 Parent::NodeNotifier::ObserverBase::detach();
00480 }
00481 }
00482
00483 ConstReference operator[](const Key& node) const {
00484 if (Parent::aNode(node)) {
00485 return aNodeMap[node];
00486 } else {
00487 return bNodeMap[node];
00488 }
00489 }
00490
00491 Reference operator[](const Key& node) {
00492 if (Parent::aNode(node)) {
00493 return aNodeMap[node];
00494 } else {
00495 return bNodeMap[node];
00496 }
00497 }
00498
00499 void set(const Key& node, const Value& value) {
00500 if (Parent::aNode(node)) {
00501 aNodeMap.set(node, value);
00502 } else {
00503 bNodeMap.set(node, value);
00504 }
00505 }
00506
00507 protected:
00508
00509 virtual void add(const Node&) {}
00510 virtual void erase(const Node&) {}
00511 virtual void clear() {}
00512 virtual void build() {}
00513
00514 const Graph* getGraph() const { return graph; }
00515
00516 private:
00517 const Graph* graph;
00518 BNodeMap<_Value> bNodeMap;
00519 ANodeMap<_Value> aNodeMap;
00520 };
00521
00522 public:
00523
00524 template <typename _Value>
00525 class NodeMap
00526 : public IterableMapExtender<NodeMapBase<_Value> > {
00527 public:
00528 typedef MappableBpUGraphExtender Graph;
00529 typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
00530
00531 NodeMap(const Graph& _g)
00532 : Parent(_g) {}
00533 NodeMap(const Graph& _g, const _Value& _v)
00534 : Parent(_g, _v) {}
00535
00536 NodeMap& operator=(const NodeMap& cmap) {
00537 return operator=<NodeMap>(cmap);
00538 }
00539
00540
00547 template <typename CMap>
00548 NodeMap& operator=(const CMap& cmap) {
00549 checkConcept<concept::ReadMap<Node, _Value>, CMap>();
00550 const typename Parent::Graph* graph = Parent::getGraph();
00551 Node it;
00552 for (graph->first(it); it != INVALID; graph->next(it)) {
00553 Parent::set(it, cmap[it]);
00554 }
00555 return *this;
00556 }
00557
00558 };
00559
00560
00561
00562 template <typename _Value>
00563 class EdgeMap
00564 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
00565 public:
00566 typedef MappableBpUGraphExtender Graph;
00567 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
00568
00569 EdgeMap(const Graph& _g)
00570 : Parent(_g) {}
00571 EdgeMap(const Graph& _g, const _Value& _v)
00572 : Parent(_g, _v) {}
00573
00574 EdgeMap& operator=(const EdgeMap& cmap) {
00575 return operator=<EdgeMap>(cmap);
00576 }
00577
00578 template <typename CMap>
00579 EdgeMap& operator=(const CMap& cmap) {
00580 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
00581 const typename Parent::Graph* graph = Parent::getGraph();
00582 Edge it;
00583 for (graph->first(it); it != INVALID; graph->next(it)) {
00584 Parent::set(it, cmap[it]);
00585 }
00586 return *this;
00587 }
00588 };
00589
00590 template <typename _Value>
00591 class UEdgeMap
00592 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
00593 public:
00594 typedef MappableBpUGraphExtender Graph;
00595 typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >
00596 Parent;
00597
00598 UEdgeMap(const Graph& _g)
00599 : Parent(_g) {}
00600 UEdgeMap(const Graph& _g, const _Value& _v)
00601 : Parent(_g, _v) {}
00602
00603 UEdgeMap& operator=(const UEdgeMap& cmap) {
00604 return operator=<UEdgeMap>(cmap);
00605 }
00606
00607 template <typename CMap>
00608 UEdgeMap& operator=(const CMap& cmap) {
00609 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
00610 const typename Parent::Graph* graph = Parent::getGraph();
00611 UEdge it;
00612 for (graph->first(it); it != INVALID; graph->next(it)) {
00613 Parent::set(it, cmap[it]);
00614 }
00615 return *this;
00616 }
00617 };
00618
00619 };
00620
00621 }
00622
00623 #endif