static_map.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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

Generated on Fri Feb 3 18:35:55 2006 for LEMON by  doxygen 1.4.6