default_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_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   // bool
00040   template <typename _Graph, typename _Item>
00041   struct DefaultMapSelector<_Graph, _Item, bool> {
00042     typedef VectorMap<_Graph, _Item, bool> Map;
00043   };
00044 
00045   // char
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   // int
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   // short
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   // long
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   // \todo handling long long type
00098 
00099 
00100   // float
00101   template <typename _Graph, typename _Item>
00102   struct DefaultMapSelector<_Graph, _Item, float> {
00103     typedef VectorMap<_Graph, _Item, float> Map;
00104   };
00105 
00106 
00107   // double
00108   template <typename _Graph, typename _Item>
00109   struct DefaultMapSelector<_Graph, _Item, double> {
00110     typedef VectorMap<_Graph, _Item,  double> Map;
00111   };
00112 
00113 
00114   // long double
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   // pointer
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

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