00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_STATIC_MAP_H
00020 #define LEMON_STATIC_MAP_H
00021
00022 #include <algorithm>
00023 #include <iostream>
00024
00025 #include <lemon/utility.h>
00026 #include <lemon/bits/map_extender.h>
00027 #include <lemon/bits/alteration_notifier.h>
00028 #include <lemon/error.h>
00029 #include <lemon/concept_check.h>
00030 #include <lemon/concept/maps.h>
00031
00036
00037 namespace lemon {
00038
00053
00054
00055 template <typename _Graph, typename _Item, typename _Value>
00056 class StaticMap : public AlterationNotifier<_Item>::ObserverBase {
00057 public:
00058
00060 class UnsinportedOperation : public lemon::LogicError {
00061 public:
00062 virtual const char* exceptionName() const {
00063 return "lemon::StaticMap::UnsinportedOperation";
00064 }
00065 };
00066
00067 private:
00068
00069 typedef std::vector<_Value> Container;
00070
00071 public:
00072
00074 typedef _Graph Graph;
00076 typedef True ReferenceMapTag;
00077
00079 typedef _Item Key;
00081 typedef _Value Value;
00083 typedef typename Container::const_reference ConstReference;
00085 typedef typename Container::reference Reference;
00086
00087 typedef const Value ConstValue;
00088 typedef Value* Pointer;
00089 typedef const Value* ConstPointer;
00090
00091 typedef AlterationNotifier<_Item> Registry;
00092
00094 typedef StaticMap Map;
00096 typedef typename Registry::ObserverBase Parent;
00097
00102 StaticMap(const Graph& _g) : graph(&_g) {
00103 attach(_g.getNotifier(_Item()));
00104 build();
00105 }
00106
00111 StaticMap(const Graph& _g, const Value& _v) : graph(&_g) {
00112 attach(_g.getNotifier(_Item()));
00113 unsigned size = graph->maxId(_Item()) + 1;
00114 container.reserve(size);
00115 container.resize(size, _v);
00116 }
00117
00121 StaticMap(const StaticMap& _copy) : Parent(), graph(_copy.getGraph()) {
00122 if (_copy.attached()) {
00123 attach(*_copy.getRegistry());
00124 container = _copy.container;
00125 }
00126 }
00127
00131 virtual ~StaticMap() {
00132 clear();
00133 if (attached()) {
00134 detach();
00135 }
00136 }
00137
00138
00139 private:
00140
00141 StaticMap& operator=(const StaticMap&);
00142
00143 protected:
00144
00145 using Parent::attach;
00146 using Parent::detach;
00147 using Parent::attached;
00148
00149 const Graph* getGraph() const {
00150 return graph;
00151 }
00152
00153 public:
00154
00159
00160 Reference operator[](const Key& key) {
00161 return container[graph->id(key)];
00162 }
00163
00168
00169 ConstReference operator[](const Key& key) const {
00170 return container[graph->id(key)];
00171 }
00172
00173
00178 void set(const Key& key, const Value& value) {
00179 (*this)[key] = value;
00180 }
00181
00182 protected:
00183
00188
00189 void add(const Key&) {
00190 throw UnsinportedOperation();
00191 }
00192
00197 void erase(const Key&) {
00198 throw UnsinportedOperation();
00199 }
00200
00202
00205
00206 void build() {
00207 int size = graph->maxId(_Item()) + 1;
00208 container.reserve(size);
00209 container.resize(size);
00210 }
00211
00213
00216 void clear() {
00217 container.clear();
00218 }
00219
00220 private:
00221
00222 Container container;
00223 const Graph *graph;
00224
00225 };
00226
00228 template <typename _Base>
00229 class StaticMappableGraphExtender : public _Base {
00230 public:
00231
00232 typedef StaticMappableGraphExtender<_Base> Graph;
00233 typedef _Base Parent;
00234
00235 typedef typename Parent::Node Node;
00236 typedef typename Parent::NodeIt NodeIt;
00237
00238 typedef typename Parent::Edge Edge;
00239 typedef typename Parent::EdgeIt EdgeIt;
00240
00241
00242 template <typename _Value>
00243 class NodeMap
00244 : public IterableMapExtender<StaticMap<Graph, Node, _Value> > {
00245 public:
00246 typedef StaticMappableGraphExtender Graph;
00247 typedef IterableMapExtender<StaticMap<Graph, Node, _Value> > Parent;
00248
00249 NodeMap(const Graph& _g)
00250 : Parent(_g) {}
00251 NodeMap(const Graph& _g, const _Value& _v)
00252 : Parent(_g, _v) {}
00253
00254 NodeMap& operator=(const NodeMap& cmap) {
00255 return operator=<NodeMap>(cmap);
00256 }
00257
00258
00265 template <typename CMap>
00266 NodeMap& operator=(const CMap& cmap) {
00267 checkConcept<concept::ReadMap<Node, _Value>, CMap>();
00268 const typename Parent::Graph* graph = Parent::getGraph();
00269 Node it;
00270 for (graph->first(it); it != INVALID; graph->next(it)) {
00271 Parent::set(it, cmap[it]);
00272 }
00273 return *this;
00274 }
00275
00276 };
00277
00278 template <typename _Value>
00279 class EdgeMap
00280 : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
00281 public:
00282 typedef StaticMappableGraphExtender Graph;
00283 typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
00284
00285 EdgeMap(const Graph& _g)
00286 : Parent(_g) {}
00287 EdgeMap(const Graph& _g, const _Value& _v)
00288 : Parent(_g, _v) {}
00289
00290 EdgeMap& operator=(const EdgeMap& cmap) {
00291 return operator=<EdgeMap>(cmap);
00292 }
00293
00294 template <typename CMap>
00295 EdgeMap& operator=(const CMap& cmap) {
00296 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
00297 const typename Parent::Graph* graph = Parent::getGraph();
00298 Edge it;
00299 for (graph->first(it); it != INVALID; graph->next(it)) {
00300 Parent::set(it, cmap[it]);
00301 }
00302 return *this;
00303 }
00304 };
00305
00306 };
00307
00309 template <typename _Base>
00310 class StaticMappableUGraphExtender :
00311 public StaticMappableGraphExtender<_Base> {
00312 public:
00313
00314 typedef StaticMappableUGraphExtender Graph;
00315 typedef StaticMappableGraphExtender<_Base> Parent;
00316
00317 typedef typename Parent::UEdge UEdge;
00318
00319 template <typename _Value>
00320 class UEdgeMap
00321 : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {
00322 public:
00323 typedef StaticMappableUGraphExtender Graph;
00324 typedef IterableMapExtender<
00325 StaticMap<Graph, UEdge, _Value> > Parent;
00326
00327 UEdgeMap(const Graph& _g)
00328 : Parent(_g) {}
00329 UEdgeMap(const Graph& _g, const _Value& _v)
00330 : Parent(_g, _v) {}
00331
00332 UEdgeMap& operator=(const UEdgeMap& cmap) {
00333 return operator=<UEdgeMap>(cmap);
00334 }
00335
00336 template <typename CMap>
00337 UEdgeMap& operator=(const CMap& cmap) {
00338 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
00339 const typename Parent::Graph* graph = Parent::getGraph();
00340 UEdge it;
00341 for (graph->first(it); it != INVALID; graph->next(it)) {
00342 Parent::set(it, cmap[it]);
00343 }
00344 return *this;
00345 }
00346 };
00347
00348 };
00349
00350 template <typename _Base>
00351 class StaticMappableBpUGraphExtender : public _Base {
00352 public:
00353
00354 typedef _Base Parent;
00355 typedef StaticMappableBpUGraphExtender Graph;
00356
00357 typedef typename Parent::Node Node;
00358 typedef typename Parent::ANode ANode;
00359 typedef typename Parent::BNode BNode;
00360 typedef typename Parent::Edge Edge;
00361 typedef typename Parent::UEdge UEdge;
00362
00363 template <typename _Value>
00364 class ANodeMap
00365 : public IterableMapExtender<StaticMap<Graph, ANode, _Value> > {
00366 public:
00367 typedef StaticMappableBpUGraphExtender Graph;
00368 typedef IterableMapExtender<StaticMap<Graph, ANode, _Value> >
00369 Parent;
00370
00371 ANodeMap(const Graph& _g)
00372 : Parent(_g) {}
00373 ANodeMap(const Graph& _g, const _Value& _v)
00374 : Parent(_g, _v) {}
00375
00376 ANodeMap& operator=(const ANodeMap& cmap) {
00377 return operator=<ANodeMap>(cmap);
00378 }
00379
00380
00387 template <typename CMap>
00388 ANodeMap& operator=(const CMap& cmap) {
00389 checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
00390 const typename Parent::Graph* graph = Parent::getGraph();
00391 ANode it;
00392 for (graph->first(it); it != INVALID; graph->next(it)) {
00393 Parent::set(it, cmap[it]);
00394 }
00395 return *this;
00396 }
00397
00398 };
00399
00400 template <typename _Value>
00401 class BNodeMap
00402 : public IterableMapExtender<StaticMap<Graph, BNode, _Value> > {
00403 public:
00404 typedef StaticMappableBpUGraphExtender Graph;
00405 typedef IterableMapExtender<StaticMap<Graph, BNode, _Value> >
00406 Parent;
00407
00408 BNodeMap(const Graph& _g)
00409 : Parent(_g) {}
00410 BNodeMap(const Graph& _g, const _Value& _v)
00411 : Parent(_g, _v) {}
00412
00413 BNodeMap& operator=(const BNodeMap& cmap) {
00414 return operator=<BNodeMap>(cmap);
00415 }
00416
00417
00424 template <typename CMap>
00425 BNodeMap& operator=(const CMap& cmap) {
00426 checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
00427 const typename Parent::Graph* graph = Parent::getGraph();
00428 BNode it;
00429 for (graph->first(it); it != INVALID; graph->next(it)) {
00430 Parent::set(it, cmap[it]);
00431 }
00432 return *this;
00433 }
00434
00435 };
00436
00437 protected:
00438
00439 template <typename _Value>
00440 class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
00441 public:
00442 typedef StaticMappableBpUGraphExtender Graph;
00443
00444 typedef Node Key;
00445 typedef _Value Value;
00446
00448 typedef typename BNodeMap<_Value>::Reference Reference;
00450 typedef typename BNodeMap<_Value>::Pointer Pointer;
00451
00453 typedef const Value ConstValue;
00455 typedef typename BNodeMap<_Value>::ConstReference ConstReference;
00457 typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
00458
00459 typedef True ReferenceMapTag;
00460
00461 NodeMapBase(const Graph& _g)
00462 : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
00463 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
00464 }
00465 NodeMapBase(const Graph& _g, const _Value& _v)
00466 : graph(&_g), bNodeMap(_g, _v),
00467 aNodeMap(_g, _v) {
00468 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
00469 }
00470
00471 virtual ~NodeMapBase() {
00472 if (Parent::NodeNotifier::ObserverBase::attached()) {
00473 Parent::NodeNotifier::ObserverBase::detach();
00474 }
00475 }
00476
00477 ConstReference operator[](const Key& node) const {
00478 if (Parent::aNode(node)) {
00479 return aNodeMap[node];
00480 } else {
00481 return bNodeMap[node];
00482 }
00483 }
00484
00485 Reference operator[](const Key& node) {
00486 if (Parent::aNode(node)) {
00487 return aNodeMap[node];
00488 } else {
00489 return bNodeMap[node];
00490 }
00491 }
00492
00493 void set(const Key& node, const Value& value) {
00494 if (Parent::aNode(node)) {
00495 aNodeMap.set(node, value);
00496 } else {
00497 bNodeMap.set(node, value);
00498 }
00499 }
00500
00501 protected:
00502
00503 virtual void add(const Node&) {}
00504 virtual void erase(const Node&) {}
00505 virtual void clear() {}
00506 virtual void build() {}
00507
00508 const Graph* getGraph() const { return graph; }
00509
00510 private:
00511 const Graph* graph;
00512 BNodeMap<_Value> bNodeMap;
00513 ANodeMap<_Value> aNodeMap;
00514 };
00515
00516 public:
00517
00518 template <typename _Value>
00519 class NodeMap
00520 : public IterableMapExtender<NodeMapBase<_Value> > {
00521 public:
00522 typedef StaticMappableBpUGraphExtender Graph;
00523 typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
00524
00525 NodeMap(const Graph& _g)
00526 : Parent(_g) {}
00527 NodeMap(const Graph& _g, const _Value& _v)
00528 : Parent(_g, _v) {}
00529
00530 NodeMap& operator=(const NodeMap& cmap) {
00531 return operator=<NodeMap>(cmap);
00532 }
00533
00534
00541 template <typename CMap>
00542 NodeMap& operator=(const CMap& cmap) {
00543 checkConcept<concept::ReadMap<Node, _Value>, CMap>();
00544 const typename Parent::Graph* graph = Parent::getGraph();
00545 Node it;
00546 for (graph->first(it); it != INVALID; graph->next(it)) {
00547 Parent::set(it, cmap[it]);
00548 }
00549 return *this;
00550 }
00551
00552 };
00553
00554
00555
00556 template <typename _Value>
00557 class EdgeMap
00558 : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
00559 public:
00560 typedef StaticMappableBpUGraphExtender Graph;
00561 typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
00562
00563 EdgeMap(const Graph& _g)
00564 : Parent(_g) {}
00565 EdgeMap(const Graph& _g, const _Value& _v)
00566 : Parent(_g, _v) {}
00567
00568 EdgeMap& operator=(const EdgeMap& cmap) {
00569 return operator=<EdgeMap>(cmap);
00570 }
00571
00572 template <typename CMap>
00573 EdgeMap& operator=(const CMap& cmap) {
00574 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
00575 const typename Parent::Graph* graph = Parent::getGraph();
00576 Edge it;
00577 for (graph->first(it); it != INVALID; graph->next(it)) {
00578 Parent::set(it, cmap[it]);
00579 }
00580 return *this;
00581 }
00582 };
00583
00584 template <typename _Value>
00585 class UEdgeMap
00586 : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {
00587 public:
00588 typedef StaticMappableBpUGraphExtender Graph;
00589 typedef IterableMapExtender<StaticMap<Graph, UEdge, _Value> >
00590 Parent;
00591
00592 UEdgeMap(const Graph& _g)
00593 : Parent(_g) {}
00594 UEdgeMap(const Graph& _g, const _Value& _v)
00595 : Parent(_g, _v) {}
00596
00597 UEdgeMap& operator=(const UEdgeMap& cmap) {
00598 return operator=<UEdgeMap>(cmap);
00599 }
00600
00601 template <typename CMap>
00602 UEdgeMap& operator=(const CMap& cmap) {
00603 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
00604 const typename Parent::Graph* graph = Parent::getGraph();
00605 UEdge it;
00606 for (graph->first(it); it != INVALID; graph->next(it)) {
00607 Parent::set(it, cmap[it]);
00608 }
00609 return *this;
00610 }
00611 };
00612
00613 };
00614
00615 }
00616
00617 #endif