COIN-OR::LEMON - Graph Library

Changeset 1979:c2992fd74dad in lemon-0.x for lemon/bits/default_map.h


Ignore:
Timestamp:
02/22/06 19:26:56 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2569
Message:

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/default_map.h

    r1966 r1979  
    2323#include <lemon/bits/array_map.h>
    2424#include <lemon/bits/vector_map.h>
     25#include <lemon/bits/static_map.h>
    2526
    2627///\ingroup graphmapfactory
     
    3132namespace lemon {
    3233 
    33 #ifndef GLIBCXX_DEBUG
     34 
     35#ifndef _GLIBCXX_DEBUG
    3436
    3537  template <typename _Graph, typename _Item, typename _Value>
     
    168170  };
    169171
    170 
    171   /// \e
    172   template <typename _Base>
    173   class MappableGraphExtender : public _Base {
    174   public:
    175 
    176     typedef MappableGraphExtender<_Base> Graph;
    177     typedef _Base Parent;
    178 
    179     typedef typename Parent::Node Node;
    180     typedef typename Parent::NodeIt NodeIt;
    181 
    182     typedef typename Parent::Edge Edge;
    183     typedef typename Parent::EdgeIt EdgeIt;
    184 
    185    
    186     template <typename _Value>
    187     class NodeMap
    188       : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
    189     public:
    190       typedef MappableGraphExtender Graph;
    191       typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    192 
    193       NodeMap(const Graph& _g)
    194         : Parent(_g) {}
    195       NodeMap(const Graph& _g, const _Value& _v)
    196         : Parent(_g, _v) {}
    197 
    198       NodeMap& operator=(const NodeMap& cmap) {
    199         return operator=<NodeMap>(cmap);
    200       }
    201 
    202 
    203       /// \brief Template assign operator.
    204       ///
    205       /// The given parameter should be conform to the ReadMap
    206       /// concecpt and could be indiced by the current item set of
    207       /// the NodeMap. In this case the value for each item
    208       /// is assigned by the value of the given ReadMap.
    209       template <typename CMap>
    210       NodeMap& operator=(const CMap& cmap) {
    211         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    212         const typename Parent::Graph* graph = Parent::getGraph();
    213         Node it;
    214         for (graph->first(it); it != INVALID; graph->next(it)) {
    215           Parent::set(it, cmap[it]);
    216         }
    217         return *this;
    218       }
    219 
    220     };
    221 
    222     template <typename _Value>
    223     class EdgeMap
    224       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
    225     public:
    226       typedef MappableGraphExtender Graph;
    227       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    228 
    229       EdgeMap(const Graph& _g)
    230         : Parent(_g) {}
    231       EdgeMap(const Graph& _g, const _Value& _v)
    232         : Parent(_g, _v) {}
    233 
    234       EdgeMap& operator=(const EdgeMap& cmap) {
    235         return operator=<EdgeMap>(cmap);
    236       }
    237 
    238       template <typename CMap>
    239       EdgeMap& operator=(const CMap& cmap) {
    240         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    241         const typename Parent::Graph* graph = Parent::getGraph();
    242         Edge it;
    243         for (graph->first(it); it != INVALID; graph->next(it)) {
    244           Parent::set(it, cmap[it]);
    245         }
    246         return *this;
    247       }
    248     };
    249    
    250   };
    251 
    252   /// \e
    253   template <typename _Base>
    254   class MappableEdgeSetExtender : public _Base {
    255   public:
    256 
    257     typedef MappableEdgeSetExtender<_Base> Graph;
    258     typedef _Base Parent;
    259 
    260     typedef typename Parent::Edge Edge;
    261     typedef typename Parent::EdgeIt EdgeIt;
    262 
    263     template <typename _Value>
    264     class EdgeMap
    265       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
    266     public:
    267       typedef MappableEdgeSetExtender Graph;
    268       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    269 
    270       EdgeMap(const Graph& _g)
    271         : Parent(_g) {}
    272       EdgeMap(const Graph& _g, const _Value& _v)
    273         : Parent(_g, _v) {}
    274 
    275       EdgeMap& operator=(const EdgeMap& cmap) {
    276         return operator=<EdgeMap>(cmap);
    277       }
    278 
    279       template <typename CMap>
    280       EdgeMap& operator=(const CMap& cmap) {
    281         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    282         const typename Parent::Graph* graph = Parent::getGraph();
    283         Edge it;
    284         for (graph->first(it); it != INVALID; graph->next(it)) {
    285           Parent::set(it, cmap[it]);
    286         }
    287         return *this;
    288       }
    289     };
    290    
    291   };
    292 
    293   /// \e
    294   template <typename _Base>
    295   class MappableUGraphExtender :
    296     public MappableGraphExtender<_Base> {
    297   public:
    298 
    299     typedef MappableUGraphExtender Graph;
    300     typedef MappableGraphExtender<_Base> Parent;
    301 
    302     typedef typename Parent::UEdge UEdge;
    303 
    304     template <typename _Value>
    305     class UEdgeMap
    306       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
    307     public:
    308       typedef MappableUGraphExtender Graph;
    309       typedef IterableMapExtender<
    310         DefaultMap<Graph, UEdge, _Value> > Parent;
    311 
    312       UEdgeMap(const Graph& _g)
    313         : Parent(_g) {}
    314       UEdgeMap(const Graph& _g, const _Value& _v)
    315         : Parent(_g, _v) {}
    316 
    317       UEdgeMap& operator=(const UEdgeMap& cmap) {
    318         return operator=<UEdgeMap>(cmap);
    319       }
    320 
    321       template <typename CMap>
    322       UEdgeMap& operator=(const CMap& cmap) {
    323         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    324         const typename Parent::Graph* graph = Parent::getGraph();
    325         UEdge it;
    326         for (graph->first(it); it != INVALID; graph->next(it)) {
    327           Parent::set(it, cmap[it]);
    328         }
    329         return *this;
    330       }
    331     };
    332 
    333 
    334   };
    335 
    336   /// \e
    337   template <typename _Base>
    338   class MappableUEdgeSetExtender :
    339     public MappableEdgeSetExtender<_Base> {
    340   public:
    341 
    342     typedef MappableUEdgeSetExtender Graph;
    343     typedef MappableEdgeSetExtender<_Base> Parent;
    344 
    345     typedef typename Parent::UEdge UEdge;
    346 
    347     template <typename _Value>
    348     class UEdgeMap
    349       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
    350     public:
    351       typedef MappableUEdgeSetExtender Graph;
    352       typedef IterableMapExtender<
    353         DefaultMap<Graph, UEdge, _Value> > Parent;
    354 
    355       UEdgeMap(const Graph& _g)
    356         : Parent(_g) {}
    357       UEdgeMap(const Graph& _g, const _Value& _v)
    358         : Parent(_g, _v) {}
    359 
    360       UEdgeMap& operator=(const UEdgeMap& cmap) {
    361         return operator=<UEdgeMap>(cmap);
    362       }
    363 
    364       template <typename CMap>
    365       UEdgeMap& operator=(const CMap& cmap) {
    366         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    367         const typename Parent::Graph* graph = Parent::getGraph();
    368         UEdge it;
    369         for (graph->first(it); it != INVALID; graph->next(it)) {
    370           Parent::set(it, cmap[it]);
    371         }
    372         return *this;
    373       }
    374     };
    375 
    376 
    377   };
    378 
    379 
    380   template <typename _Base>
    381   class MappableBpUGraphExtender : public _Base {
    382   public:
    383 
    384     typedef _Base Parent;
    385     typedef MappableBpUGraphExtender Graph;
    386 
    387     typedef typename Parent::Node Node;
    388     typedef typename Parent::ANode ANode;
    389     typedef typename Parent::BNode BNode;
    390     typedef typename Parent::Edge Edge;
    391     typedef typename Parent::UEdge UEdge;
    392    
    393     template <typename _Value>
    394     class ANodeMap
    395       : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
    396     public:
    397       typedef MappableBpUGraphExtender Graph;
    398       typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >
    399       Parent;
    400    
    401       ANodeMap(const Graph& _g)
    402         : Parent(_g) {}
    403       ANodeMap(const Graph& _g, const _Value& _v)
    404         : Parent(_g, _v) {}
    405    
    406       ANodeMap& operator=(const ANodeMap& cmap) {
    407         return operator=<ANodeMap>(cmap);
    408       }
    409    
    410 
    411       /// \brief Template assign operator.
    412       ///
    413       /// The given parameter should be conform to the ReadMap
    414       /// concept and could be indiced by the current item set of
    415       /// the ANodeMap. In this case the value for each item
    416       /// is assigned by the value of the given ReadMap.
    417       template <typename CMap>
    418       ANodeMap& operator=(const CMap& cmap) {
    419         checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
    420         const typename Parent::Graph* graph = Parent::getGraph();
    421         ANode it;
    422         for (graph->first(it); it != INVALID; graph->next(it)) {
    423           Parent::set(it, cmap[it]);
    424         }
    425         return *this;
    426       }
    427    
    428     };
    429 
    430     template <typename _Value>
    431     class BNodeMap
    432       : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {
    433     public:
    434       typedef MappableBpUGraphExtender Graph;
    435       typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >
    436       Parent;
    437    
    438       BNodeMap(const Graph& _g)
    439         : Parent(_g) {}
    440       BNodeMap(const Graph& _g, const _Value& _v)
    441         : Parent(_g, _v) {}
    442    
    443       BNodeMap& operator=(const BNodeMap& cmap) {
    444         return operator=<BNodeMap>(cmap);
    445       }
    446    
    447 
    448       /// \brief Template assign operator.
    449       ///
    450       /// The given parameter should be conform to the ReadMap
    451       /// concept and could be indiced by the current item set of
    452       /// the BNodeMap. In this case the value for each item
    453       /// is assigned by the value of the given ReadMap.
    454       template <typename CMap>
    455       BNodeMap& operator=(const CMap& cmap) {
    456         checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
    457         const typename Parent::Graph* graph = Parent::getGraph();
    458         BNode it;
    459         for (graph->first(it); it != INVALID; graph->next(it)) {
    460           Parent::set(it, cmap[it]);
    461         }
    462         return *this;
    463       }
    464    
    465     };
    466 
    467   protected:
    468 
    469     template <typename _Value>
    470     class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
    471     public:
    472       typedef MappableBpUGraphExtender Graph;
    473 
    474       typedef Node Key;
    475       typedef _Value Value;
    476 
    477       /// The reference type of the map;
    478       typedef typename BNodeMap<_Value>::Reference Reference;
    479       /// The pointer type of the map;
    480       typedef typename BNodeMap<_Value>::Pointer Pointer;
    481      
    482       /// The const value type of the map.
    483       typedef const Value ConstValue;
    484       /// The const reference type of the map;
    485       typedef typename BNodeMap<_Value>::ConstReference ConstReference;
    486       /// The pointer type of the map;
    487       typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
    488 
    489       typedef True ReferenceMapTag;
    490 
    491       NodeMapBase(const Graph& _g)
    492         : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
    493         Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    494       }
    495       NodeMapBase(const Graph& _g, const _Value& _v)
    496         : graph(&_g), bNodeMap(_g, _v),
    497           aNodeMap(_g, _v) {
    498         Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    499       }
    500 
    501       virtual ~NodeMapBase() {     
    502         if (Parent::NodeNotifier::ObserverBase::attached()) {
    503           Parent::NodeNotifier::ObserverBase::detach();
    504         }
    505       }
    506    
    507       ConstReference operator[](const Key& node) const {
    508         if (Parent::aNode(node)) {
    509           return aNodeMap[node];
    510         } else {
    511           return bNodeMap[node];
    512         }
    513       }
    514 
    515       Reference operator[](const Key& node) {
    516         if (Parent::aNode(node)) {
    517           return aNodeMap[node];
    518         } else {
    519           return bNodeMap[node];
    520         }
    521       }
    522 
    523       void set(const Key& node, const Value& value) {
    524         if (Parent::aNode(node)) {
    525           aNodeMap.set(node, value);
    526         } else {
    527           bNodeMap.set(node, value);
    528         }
    529       }
    530 
    531     protected:
    532      
    533       virtual void add(const Node&) {}
    534       virtual void add(const std::vector<Node>&) {}
    535       virtual void erase(const Node&) {}
    536       virtual void erase(const std::vector<Node>&) {}
    537       virtual void clear() {}
    538       virtual void build() {}
    539 
    540       const Graph* getGraph() const { return graph; }
    541      
    542     private:
    543       const Graph* graph;
    544       BNodeMap<_Value> bNodeMap;
    545       ANodeMap<_Value> aNodeMap;
    546     };
    547    
    548   public:
    549 
    550     template <typename _Value>
    551     class NodeMap
    552       : public IterableMapExtender<NodeMapBase<_Value> > {
    553     public:
    554       typedef MappableBpUGraphExtender Graph;
    555       typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
    556    
    557       NodeMap(const Graph& _g)
    558         : Parent(_g) {}
    559       NodeMap(const Graph& _g, const _Value& _v)
    560         : Parent(_g, _v) {}
    561    
    562       NodeMap& operator=(const NodeMap& cmap) {
    563         return operator=<NodeMap>(cmap);
    564       }
    565    
    566 
    567       /// \brief Template assign operator.
    568       ///
    569       /// The given parameter should be conform to the ReadMap
    570       /// concept and could be indiced by the current item set of
    571       /// the NodeMap. In this case the value for each item
    572       /// is assigned by the value of the given ReadMap.
    573       template <typename CMap>
    574       NodeMap& operator=(const CMap& cmap) {
    575         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    576         const typename Parent::Graph* graph = Parent::getGraph();
    577         Node it;
    578         for (graph->first(it); it != INVALID; graph->next(it)) {
    579           Parent::set(it, cmap[it]);
    580         }
    581         return *this;
    582       }
    583    
    584     };
    585 
    586 
    587 
    588     template <typename _Value>
    589     class EdgeMap
    590       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
    591     public:
    592       typedef MappableBpUGraphExtender Graph;
    593       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    594    
    595       EdgeMap(const Graph& _g)
    596         : Parent(_g) {}
    597       EdgeMap(const Graph& _g, const _Value& _v)
    598         : Parent(_g, _v) {}
    599    
    600       EdgeMap& operator=(const EdgeMap& cmap) {
    601         return operator=<EdgeMap>(cmap);
    602       }
    603    
    604       template <typename CMap>
    605       EdgeMap& operator=(const CMap& cmap) {
    606         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    607         const typename Parent::Graph* graph = Parent::getGraph();
    608         Edge it;
    609         for (graph->first(it); it != INVALID; graph->next(it)) {
    610           Parent::set(it, cmap[it]);
    611         }
    612         return *this;
    613       }
    614     };
    615 
    616     template <typename _Value>
    617     class UEdgeMap
    618       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
    619     public:
    620       typedef MappableBpUGraphExtender Graph;
    621       typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >
    622       Parent;
    623    
    624       UEdgeMap(const Graph& _g)
    625         : Parent(_g) {}
    626       UEdgeMap(const Graph& _g, const _Value& _v)
    627         : Parent(_g, _v) {}
    628    
    629       UEdgeMap& operator=(const UEdgeMap& cmap) {
    630         return operator=<UEdgeMap>(cmap);
    631       }
    632    
    633       template <typename CMap>
    634       UEdgeMap& operator=(const CMap& cmap) {
    635         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    636         const typename Parent::Graph* graph = Parent::getGraph();
    637         UEdge it;
    638         for (graph->first(it); it != INVALID; graph->next(it)) {
    639           Parent::set(it, cmap[it]);
    640         }
    641         return *this;
    642       }
    643     };
    644  
    645   };
    646 
    647172}
    648173
Note: See TracChangeset for help on using the changeset viewer.