COIN-OR::LEMON - Graph Library

Changeset 1979:c2992fd74dad in lemon-0.x for lemon/bits/static_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/static_map.h

    r1961 r1979  
    5757  public:
    5858
    59     /// \brief Exception class for unsinported exceptions.
    60     class UnsinportedOperation : public lemon::LogicError {
     59    /// \brief Exception class for unsupported exceptions.
     60    class UnsupportedOperation : public lemon::LogicError {
    6161    public:
    6262      virtual const char* exceptionName() const {
    63         return "lemon::StaticMap::UnsinportedOperation";
     63        return "lemon::StaticMap::UnsupportedOperation";
    6464      }
    6565    };
     
    188188     
    189189    void add(const Key&) {
    190       throw UnsinportedOperation();
     190      throw UnsupportedOperation();
    191191    }
    192192
     
    196196    /// and it overrides the erase() member function of the observer base.     
    197197    void erase(const Key&) {
    198       throw UnsinportedOperation();
     198      throw UnsupportedOperation();
    199199    }
    200200
     
    225225  };
    226226
    227   /// \e
    228   template <typename _Base>
    229   class StaticMappableGraphExtender : public _Base {
    230   public:
    231 
    232     typedef StaticMappableGraphExtender<_Base> Graph;
    233     typedef _Base Parent;
    234 
    235     typedef typename Parent::Node Node;
    236     typedef typename Parent::NodeIt NodeIt;
    237 
    238     typedef typename Parent::Edge Edge;
    239     typedef typename Parent::EdgeIt EdgeIt;
    240 
    241    
    242     template <typename _Value>
    243     class NodeMap
    244       : public IterableMapExtender<StaticMap<Graph, Node, _Value> > {
    245     public:
    246       typedef StaticMappableGraphExtender Graph;
    247       typedef IterableMapExtender<StaticMap<Graph, Node, _Value> > Parent;
    248 
    249       NodeMap(const Graph& _g)
    250         : Parent(_g) {}
    251       NodeMap(const Graph& _g, const _Value& _v)
    252         : Parent(_g, _v) {}
    253 
    254       NodeMap& operator=(const NodeMap& cmap) {
    255         return operator=<NodeMap>(cmap);
    256       }
    257 
    258 
    259       /// \brief Template assign operator.
    260       ///
    261       /// The given parameter should be conform to the ReadMap
    262       /// concecpt and could be indiced by the current item set of
    263       /// the NodeMap. In this case the value for each item
    264       /// is assigned by the value of the given ReadMap.
    265       template <typename CMap>
    266       NodeMap& operator=(const CMap& cmap) {
    267         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    268         const typename Parent::Graph* graph = Parent::getGraph();
    269         Node it;
    270         for (graph->first(it); it != INVALID; graph->next(it)) {
    271           Parent::set(it, cmap[it]);
    272         }
    273         return *this;
    274       }
    275 
    276     };
    277 
    278     template <typename _Value>
    279     class EdgeMap
    280       : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
    281     public:
    282       typedef StaticMappableGraphExtender Graph;
    283       typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
    284 
    285       EdgeMap(const Graph& _g)
    286         : Parent(_g) {}
    287       EdgeMap(const Graph& _g, const _Value& _v)
    288         : Parent(_g, _v) {}
    289 
    290       EdgeMap& operator=(const EdgeMap& cmap) {
    291         return operator=<EdgeMap>(cmap);
    292       }
    293 
    294       template <typename CMap>
    295       EdgeMap& operator=(const CMap& cmap) {
    296         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    297         const typename Parent::Graph* graph = Parent::getGraph();
    298         Edge it;
    299         for (graph->first(it); it != INVALID; graph->next(it)) {
    300           Parent::set(it, cmap[it]);
    301         }
    302         return *this;
    303       }
    304     };
    305    
    306   };
    307 
    308   /// \e
    309   template <typename _Base>
    310   class StaticMappableUGraphExtender :
    311     public StaticMappableGraphExtender<_Base> {
    312   public:
    313 
    314     typedef StaticMappableUGraphExtender Graph;
    315     typedef StaticMappableGraphExtender<_Base> Parent;
    316 
    317     typedef typename Parent::UEdge UEdge;
    318 
    319     template <typename _Value>
    320     class UEdgeMap
    321       : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {
    322     public:
    323       typedef StaticMappableUGraphExtender Graph;
    324       typedef IterableMapExtender<
    325         StaticMap<Graph, UEdge, _Value> > Parent;
    326 
    327       UEdgeMap(const Graph& _g)
    328         : Parent(_g) {}
    329       UEdgeMap(const Graph& _g, const _Value& _v)
    330         : Parent(_g, _v) {}
    331 
    332       UEdgeMap& operator=(const UEdgeMap& cmap) {
    333         return operator=<UEdgeMap>(cmap);
    334       }
    335 
    336       template <typename CMap>
    337       UEdgeMap& operator=(const CMap& cmap) {
    338         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    339         const typename Parent::Graph* graph = Parent::getGraph();
    340         UEdge it;
    341         for (graph->first(it); it != INVALID; graph->next(it)) {
    342           Parent::set(it, cmap[it]);
    343         }
    344         return *this;
    345       }
    346     };
    347 
    348   };
    349 
    350   template <typename _Base>
    351   class StaticMappableBpUGraphExtender : public _Base {
    352   public:
    353 
    354     typedef _Base Parent;
    355     typedef StaticMappableBpUGraphExtender Graph;
    356 
    357     typedef typename Parent::Node Node;
    358     typedef typename Parent::ANode ANode;
    359     typedef typename Parent::BNode BNode;
    360     typedef typename Parent::Edge Edge;
    361     typedef typename Parent::UEdge UEdge;
    362    
    363     template <typename _Value>
    364     class ANodeMap
    365       : public IterableMapExtender<StaticMap<Graph, ANode, _Value> > {
    366     public:
    367       typedef StaticMappableBpUGraphExtender Graph;
    368       typedef IterableMapExtender<StaticMap<Graph, ANode, _Value> >
    369       Parent;
    370    
    371       ANodeMap(const Graph& _g)
    372         : Parent(_g) {}
    373       ANodeMap(const Graph& _g, const _Value& _v)
    374         : Parent(_g, _v) {}
    375    
    376       ANodeMap& operator=(const ANodeMap& cmap) {
    377         return operator=<ANodeMap>(cmap);
    378       }
    379    
    380 
    381       /// \brief Template assign operator.
    382       ///
    383       /// The given parameter should be conform to the ReadMap
    384       /// concept and could be indiced by the current item set of
    385       /// the ANodeMap. In this case the value for each item
    386       /// is assigned by the value of the given ReadMap.
    387       template <typename CMap>
    388       ANodeMap& operator=(const CMap& cmap) {
    389         checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
    390         const typename Parent::Graph* graph = Parent::getGraph();
    391         ANode it;
    392         for (graph->first(it); it != INVALID; graph->next(it)) {
    393           Parent::set(it, cmap[it]);
    394         }
    395         return *this;
    396       }
    397    
    398     };
    399 
    400     template <typename _Value>
    401     class BNodeMap
    402       : public IterableMapExtender<StaticMap<Graph, BNode, _Value> > {
    403     public:
    404       typedef StaticMappableBpUGraphExtender Graph;
    405       typedef IterableMapExtender<StaticMap<Graph, BNode, _Value> >
    406       Parent;
    407    
    408       BNodeMap(const Graph& _g)
    409         : Parent(_g) {}
    410       BNodeMap(const Graph& _g, const _Value& _v)
    411         : Parent(_g, _v) {}
    412    
    413       BNodeMap& operator=(const BNodeMap& cmap) {
    414         return operator=<BNodeMap>(cmap);
    415       }
    416    
    417 
    418       /// \brief Template assign operator.
    419       ///
    420       /// The given parameter should be conform to the ReadMap
    421       /// concept and could be indiced by the current item set of
    422       /// the BNodeMap. In this case the value for each item
    423       /// is assigned by the value of the given ReadMap.
    424       template <typename CMap>
    425       BNodeMap& operator=(const CMap& cmap) {
    426         checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
    427         const typename Parent::Graph* graph = Parent::getGraph();
    428         BNode it;
    429         for (graph->first(it); it != INVALID; graph->next(it)) {
    430           Parent::set(it, cmap[it]);
    431         }
    432         return *this;
    433       }
    434    
    435     };
    436 
    437   protected:
    438 
    439     template <typename _Value>
    440     class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
    441     public:
    442       typedef StaticMappableBpUGraphExtender Graph;
    443 
    444       typedef Node Key;
    445       typedef _Value Value;
    446 
    447       /// The reference type of the map;
    448       typedef typename BNodeMap<_Value>::Reference Reference;
    449       /// The pointer type of the map;
    450       typedef typename BNodeMap<_Value>::Pointer Pointer;
    451      
    452       /// The const value type of the map.
    453       typedef const Value ConstValue;
    454       /// The const reference type of the map;
    455       typedef typename BNodeMap<_Value>::ConstReference ConstReference;
    456       /// The pointer type of the map;
    457       typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
    458 
    459       typedef True ReferenceMapTag;
    460 
    461       NodeMapBase(const Graph& _g)
    462         : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
    463         Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    464       }
    465       NodeMapBase(const Graph& _g, const _Value& _v)
    466         : graph(&_g), bNodeMap(_g, _v),
    467           aNodeMap(_g, _v) {
    468         Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    469       }
    470 
    471       virtual ~NodeMapBase() {     
    472         if (Parent::NodeNotifier::ObserverBase::attached()) {
    473           Parent::NodeNotifier::ObserverBase::detach();
    474         }
    475       }
    476    
    477       ConstReference operator[](const Key& node) const {
    478         if (Parent::aNode(node)) {
    479           return aNodeMap[node];
    480         } else {
    481           return bNodeMap[node];
    482         }
    483       }
    484 
    485       Reference operator[](const Key& node) {
    486         if (Parent::aNode(node)) {
    487           return aNodeMap[node];
    488         } else {
    489           return bNodeMap[node];
    490         }
    491       }
    492 
    493       void set(const Key& node, const Value& value) {
    494         if (Parent::aNode(node)) {
    495           aNodeMap.set(node, value);
    496         } else {
    497           bNodeMap.set(node, value);
    498         }
    499       }
    500 
    501     protected:
    502      
    503       virtual void add(const Node&) {}
    504       virtual void add(const std::vector<Node>&) {}
    505       virtual void erase(const Node&) {}
    506       virtual void erase(const std::vector<Node>&) {}
    507       virtual void clear() {}
    508       virtual void build() {}
    509 
    510       const Graph* getGraph() const { return graph; }
    511      
    512     private:
    513       const Graph* graph;
    514       BNodeMap<_Value> bNodeMap;
    515       ANodeMap<_Value> aNodeMap;
    516     };
    517    
    518   public:
    519 
    520     template <typename _Value>
    521     class NodeMap
    522       : public IterableMapExtender<NodeMapBase<_Value> > {
    523     public:
    524       typedef StaticMappableBpUGraphExtender Graph;
    525       typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
    526    
    527       NodeMap(const Graph& _g)
    528         : Parent(_g) {}
    529       NodeMap(const Graph& _g, const _Value& _v)
    530         : Parent(_g, _v) {}
    531    
    532       NodeMap& operator=(const NodeMap& cmap) {
    533         return operator=<NodeMap>(cmap);
    534       }
    535    
    536 
    537       /// \brief Template assign operator.
    538       ///
    539       /// The given parameter should be conform to the ReadMap
    540       /// concept and could be indiced by the current item set of
    541       /// the NodeMap. In this case the value for each item
    542       /// is assigned by the value of the given ReadMap.
    543       template <typename CMap>
    544       NodeMap& operator=(const CMap& cmap) {
    545         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    546         const typename Parent::Graph* graph = Parent::getGraph();
    547         Node it;
    548         for (graph->first(it); it != INVALID; graph->next(it)) {
    549           Parent::set(it, cmap[it]);
    550         }
    551         return *this;
    552       }
    553    
    554     };
    555 
    556 
    557 
    558     template <typename _Value>
    559     class EdgeMap
    560       : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
    561     public:
    562       typedef StaticMappableBpUGraphExtender Graph;
    563       typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
    564    
    565       EdgeMap(const Graph& _g)
    566         : Parent(_g) {}
    567       EdgeMap(const Graph& _g, const _Value& _v)
    568         : Parent(_g, _v) {}
    569    
    570       EdgeMap& operator=(const EdgeMap& cmap) {
    571         return operator=<EdgeMap>(cmap);
    572       }
    573    
    574       template <typename CMap>
    575       EdgeMap& operator=(const CMap& cmap) {
    576         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    577         const typename Parent::Graph* graph = Parent::getGraph();
    578         Edge it;
    579         for (graph->first(it); it != INVALID; graph->next(it)) {
    580           Parent::set(it, cmap[it]);
    581         }
    582         return *this;
    583       }
    584     };
    585 
    586     template <typename _Value>
    587     class UEdgeMap
    588       : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {
    589     public:
    590       typedef StaticMappableBpUGraphExtender Graph;
    591       typedef IterableMapExtender<StaticMap<Graph, UEdge, _Value> >
    592       Parent;
    593    
    594       UEdgeMap(const Graph& _g)
    595         : Parent(_g) {}
    596       UEdgeMap(const Graph& _g, const _Value& _v)
    597         : Parent(_g, _v) {}
    598    
    599       UEdgeMap& operator=(const UEdgeMap& cmap) {
    600         return operator=<UEdgeMap>(cmap);
    601       }
    602    
    603       template <typename CMap>
    604       UEdgeMap& operator=(const CMap& cmap) {
    605         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    606         const typename Parent::Graph* graph = Parent::getGraph();
    607         UEdge it;
    608         for (graph->first(it); it != INVALID; graph->next(it)) {
    609           Parent::set(it, cmap[it]);
    610         }
    611         return *this;
    612       }
    613     };
    614  
    615   };
    616 
    617227}
    618228
Note: See TracChangeset for help on using the changeset viewer.