COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1267:a93f94dbe3d3 in lemon-0.x


Ignore:
Timestamp:
03/26/05 00:31:57 (19 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1694
Message:

First version of iterable maps.

Location:
src
Files:
1 added
7 edited

Legend:

Unmodified
Added
Removed

  • src/lemon/array_map.h

    r1164 r1267  
    1919
    2020#include <memory>
     21#include <lemon/map_iterator.h>
    2122
    2223///\ingroup graphmaps
    … …  
    3637   *  the container functionality.
    3738   *
    38    *  The template parameter is the MapRegistry that the maps
     39   *  The template parameter is the AlterationNotifier that the maps
    3940   *  will belong to and the Value.
    4041   */
    … …  
    4243  template <typename _Graph,
    4344            typename _Item,
    44             typename _ItemIt,
    4545            typename _Value>
    4646  class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
    4747
     48    typedef _Item Item;
    4849  public:
    4950               
    … …  
    5556    typedef AlterationNotifier<_Item> Registry;
    5657
    57   private:
    58     /// The iterator to iterate on the keys.
    59     typedef _ItemIt KeyIt;
    60 
    6158    /// The MapBase of the Map which imlements the core regisitry function.
    6259    typedef typename Registry::ObserverBase Parent;
    6360               
    64    
    65   public:
    66 
    6761    /// The value type of the map.
    6862    typedef _Value Value;
    69     /// The reference type of the map;
    70     typedef Value& Reference;
    71     /// The pointer type of the map;
    72     typedef Value* Pointer;
    73 
    74     /// The const value type of the map.
    75     typedef const Value ConstValue;
    76     /// The const reference type of the map;
    77     typedef const Value& ConstReference;
    78     /// The pointer type of the map;
    79     typedef const Value* ConstPointer;
    8063
    8164
    … …  
    8972     */
    9073    ArrayMap(const Graph& _g) : graph(&_g) {
     74      Item it;
     75      attach(_g.getNotifier(Item()));
     76      allocate_memory();
     77      for (graph->first(it); it != INVALID; graph->next(it)) {
     78        int id = graph->id(it);;
     79        allocator.construct(&(values[id]), Value());
     80      }                                                         
     81    }
     82
     83    /// Constructor to use default value to initialize the map.
     84
     85    /// It constrates a map and initialize all of the the map.
     86
     87    ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
     88      Item it;
    9189      attach(_g.getNotifier(_Item()));
    9290      allocate_memory();
    93       for (KeyIt it(*graph); it != INVALID; ++it) {
    94         int id = graph->id(it);;
    95         allocator.construct(&(values[id]), Value());
    96       }                                                         
    97     }
    98 
    99     /// Constructor to use default value to initialize the map.
    100 
    101     /// It constrates a map and initialize all of the the map.
    102 
    103     ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
    104       attach(_g.getNotifier(_Item()));
    105       allocate_memory();
    106       for (KeyIt it(*graph); it != INVALID; ++it) {
     91      for (graph->first(it); it != INVALID; graph->next(it)) {
    10792        int id = graph->id(it);;
    10893        allocator.construct(&(values[id]), _v);
    … …  
    119104      if (capacity == 0) return;
    120105      values = allocator.allocate(capacity);
    121       for (KeyIt it(*graph); it != INVALID; ++it) {
     106      Item it;
     107      for (graph->first(it); it != INVALID; graph->next(it)) {
    122108        int id = graph->id(it);;
    123109        allocator.construct(&(values[id]), copy.values[id]);
    … …  
    147133      }
    148134
    149       for (KeyIt it(*graph); it != INVALID; ++it) {
     135      Item it;
     136      for (graph->first(it); it != INVALID; graph->next(it)) {
    150137        int id = graph->id(it);;
    151138        allocator.construct(&(values[id]), copy.values[id]);
    … …  
    169156     * actual keys of the graph.
    170157     */
    171     Reference operator[](const Key& key) {
     158    Value& operator[](const Key& key) {
    172159      int id = graph->id(key);
    173160      return values[id];
    … …  
    178165     * actual keys of the graph.
    179166     */
    180     ConstReference operator[](const Key& key) const {
     167    const Value& operator[](const Key& key) const {
    181168      int id = graph->id(key);
    182169      return values[id];
    … …  
    200187        }
    201188        Value* new_values = allocator.allocate(new_capacity);
    202         for (KeyIt it(*graph); it != INVALID; ++it) {
     189        Item it;
     190        for (graph->first(it); it != INVALID; graph->next(it)) {
    203191          int jd = graph->id(it);;
    204192          if (id != jd) {
    … …  
    223211    void build() {
    224212      allocate_memory();
    225       for (KeyIt it(*graph); it != INVALID; ++it) {
     213      Item it;
     214      for (graph->first(it); it != INVALID; graph->next(it)) {
    226215        int id = graph->id(it);;
    227216        allocator.construct(&(values[id]), Value());
    … …  
    231220    void clear() {     
    232221      if (capacity != 0) {
    233         for (KeyIt it(*graph); it != INVALID; ++it) {
     222        Item it;
     223        for (graph->first(it); it != INVALID; graph->next(it)) {
    234224          int id = graph->id(it);;
    235225          allocator.destroy(&(values[id]));
    … …  
    314304    Allocator allocator;
    315305
    316   public:
    317 //     // STL  compatibility typedefs.
    318 //     typedef Iterator iterator;
    319 //     typedef ConstIterator const_iterator;
    320 //     typedef typename Iterator::PairValue value_type;
    321 //     typedef typename Iterator::Key key_type;
    322 //     typedef typename Iterator::Value data_type;
    323 //     typedef typename Iterator::PairReference reference;
    324 //     typedef typename Iterator::PairPointer pointer;
    325 //     typedef typename ConstIterator::PairReference const_reference;
    326 //     typedef typename ConstIterator::PairPointer const_pointer;
    327 //     typedef int difference_type;             
    328306  };           
    329307
    … …  
    346324
    347325    template <typename _Value>
    348     class NodeMap : public ArrayMap<Graph, Node, NodeIt, _Value> {
     326    class NodeMap
     327      : public IterableMapExtender<ArrayMap<Graph, Node, _Value> > {
    349328    public:
    350329      typedef ArrayMappableGraphExtender<_Base> Graph;
    … …  
    353332      typedef typename Graph::NodeIt NodeIt;
    354333
    355       typedef ArrayMap<Graph, Node, NodeIt, _Value> Parent;
     334      typedef IterableMapExtender<ArrayMap<Graph, Node, _Value> > Parent;
    356335
    357336      //typedef typename Parent::Graph Graph;
    … …  
    366345
    367346    template <typename _Value>
    368     class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, _Value> {
     347    class EdgeMap
     348      : public IterableMapExtender<ArrayMap<Graph, Edge, _Value> > {
    369349    public:
    370350      typedef ArrayMappableGraphExtender<_Base> Graph;
    … …  
    373353      typedef typename Graph::EdgeIt EdgeIt;
    374354
    375       typedef ArrayMap<Graph, Edge, EdgeIt, _Value> Parent;
     355      typedef IterableMapExtender<ArrayMap<Graph, Edge, _Value> > Parent;
    376356
    377357      //typedef typename Parent::Graph Graph;

  • src/lemon/default_map.h

    r1164 r1267  
    4343
    4444
    45   template <typename _Graph, typename _Item, typename _ItemIt, typename _Value>
     45  template <typename _Graph, typename _Item, typename _Value>
    4646  struct DefaultMapSelector {
    47     typedef ArrayMap<_Graph, _Item, _ItemIt, _Value> Map;
     47    typedef ArrayMap<_Graph, _Item, _Value> Map;
    4848  };
    4949
    5050  // bool
    51   template <typename _Graph, typename _Item, typename _ItemIt>
    52   struct DefaultMapSelector<_Graph, _Item, _ItemIt, bool> {
     51  template <typename _Graph, typename _Item>
     52  struct DefaultMapSelector<_Graph, _Item, bool> {
    5353    typedef VectorMap<_Graph, _Item, bool> Map;
    5454  };
    5555
    5656  // char
    57   template <typename _Graph, typename _Item, typename _ItemIt>
    58   struct DefaultMapSelector<_Graph, _Item, _ItemIt, char> {
     57  template <typename _Graph, typename _Item>
     58  struct DefaultMapSelector<_Graph, _Item, char> {
    5959    typedef VectorMap<_Graph, _Item, char> Map;
    6060  };
    6161
    62   template <typename _Graph, typename _Item, typename _ItemIt>
    63   struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed char> {
     62  template <typename _Graph, typename _Item>
     63  struct DefaultMapSelector<_Graph, _Item, signed char> {
    6464    typedef VectorMap<_Graph, _Item, signed char> Map;
    6565  };
    6666
    67   template <typename _Graph, typename _Item, typename _ItemIt>
    68   struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned char> {
     67  template <typename _Graph, typename _Item>
     68  struct DefaultMapSelector<_Graph, _Item, unsigned char> {
    6969    typedef VectorMap<_Graph, _Item, unsigned char> Map;
    7070  };
    … …  
    7272
    7373  // int
    74   template <typename _Graph, typename _Item, typename _ItemIt>
    75   struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed int> {
     74  template <typename _Graph, typename _Item>
     75  struct DefaultMapSelector<_Graph, _Item, signed int> {
    7676    typedef VectorMap<_Graph, _Item, signed int> Map;
    7777  };
    7878
    79   template <typename _Graph, typename _Item, typename _ItemIt>
    80   struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned int> {
     79  template <typename _Graph, typename _Item>
     80  struct DefaultMapSelector<_Graph, _Item, unsigned int> {
    8181    typedef VectorMap<_Graph, _Item, unsigned int> Map;
    8282  };
    … …  
    8484
    8585  // short
    86   template <typename _Graph, typename _Item, typename _ItemIt>
    87   struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed short> {
     86  template <typename _Graph, typename _Item>
     87  struct DefaultMapSelector<_Graph, _Item, signed short> {
    8888    typedef VectorMap<_Graph, _Item, signed short> Map;
    8989  };
    9090
    91   template <typename _Graph, typename _Item, typename _ItemIt>
    92   struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned short> {
     91  template <typename _Graph, typename _Item>
     92  struct DefaultMapSelector<_Graph, _Item, unsigned short> {
    9393    typedef VectorMap<_Graph, _Item, unsigned short> Map;
    9494  };
    … …  
    9696
    9797  // long
    98   template <typename _Graph, typename _Item, typename _ItemIt>
    99   struct DefaultMapSelector<_Graph, _Item, _ItemIt, signed long> {
     98  template <typename _Graph, typename _Item>
     99  struct DefaultMapSelector<_Graph, _Item, signed long> {
    100100    typedef VectorMap<_Graph, _Item, signed long> Map;
    101101  };
    102102
    103   template <typename _Graph, typename _Item, typename _ItemIt>
    104   struct DefaultMapSelector<_Graph, _Item, _ItemIt, unsigned long> {
     103  template <typename _Graph, typename _Item>
     104  struct DefaultMapSelector<_Graph, _Item, unsigned long> {
    105105    typedef VectorMap<_Graph, _Item, unsigned long> Map;
    106106  };
    … …  
    110110
    111111  // float
    112   template <typename _Graph, typename _Item, typename _ItemIt>
    113   struct DefaultMapSelector<_Graph, _Item, _ItemIt, float> {
     112  template <typename _Graph, typename _Item>
     113  struct DefaultMapSelector<_Graph, _Item, float> {
    114114    typedef VectorMap<_Graph, _Item, float> Map;
    115115  };
    … …  
    117117
    118118  // double
    119   template <typename _Graph, typename _Item, typename _ItemIt>
    120   struct DefaultMapSelector<_Graph, _Item, _ItemIt, double> {
     119  template <typename _Graph, typename _Item>
     120  struct DefaultMapSelector<_Graph, _Item, double> {
    121121    typedef VectorMap<_Graph, _Item,  double> Map;
    122122  };
    … …  
    124124
    125125  // long double
    126   template <typename _Graph, typename _Item, typename _ItemIt>
    127   struct DefaultMapSelector<_Graph, _Item, _ItemIt, long double> {
     126  template <typename _Graph, typename _Item>
     127  struct DefaultMapSelector<_Graph, _Item, long double> {
    128128    typedef VectorMap<_Graph, _Item, long double> Map;
    129129  };
    … …  
    131131
    132132  // pointer
    133   template <typename _Graph, typename _Item, typename _ItemIt, typename _Ptr>
    134   struct DefaultMapSelector<_Graph, _Item, _ItemIt, _Ptr*> {
     133  template <typename _Graph, typename _Item, typename _Ptr>
     134  struct DefaultMapSelector<_Graph, _Item, _Ptr*> {
    135135    typedef VectorMap<_Graph, _Item, _Ptr*> Map;
    136136  };
    … …  
    138138
    139139
    140   template <typename _Graph,
    141             typename _Item,
    142             typename _ItemIt,
    143             typename _Value>
    144   class DefaultMap : public DefaultMapSelector<_Graph, _Item, _ItemIt, _Value>::Map {
     140  template <
     141    typename _Graph,
     142    typename _Item,
     143    typename _Value>
     144  class DefaultMap
     145    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
    145146  public:
    146     typedef typename DefaultMapSelector<_Graph, _Item, _ItemIt, _Value>::Map Parent;
    147     typedef DefaultMap<_Graph, _Item, _ItemIt, _Value> Map;
     147    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
     148    typedef DefaultMap<_Graph, _Item, _Value> Map;
    148149   
    149150    typedef typename Parent::Graph Graph;
    … …  
    171172   
    172173    template <typename _Value>
    173     class NodeMap : public DefaultMap<Graph, Node, NodeIt, _Value> {
     174    class NodeMap
     175      : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
    174176    public:
    175177      typedef DefaultMappableGraphExtender Graph;
    176       typedef DefaultMap<Graph, Node, NodeIt, _Value> Parent;
     178      typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    177179
    178180      NodeMap(const Graph& _g)
    … …  
    183185
    184186    template <typename _Value>
    185     class EdgeMap : public DefaultMap<Graph, Edge, EdgeIt, _Value> {
     187    class EdgeMap
     188      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
    186189    public:
    187190      typedef DefaultMappableGraphExtender Graph;
    188       typedef DefaultMap<Graph, Edge, EdgeIt, _Value> Parent;
     191      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    189192
    190193      EdgeMap(const Graph& _g)
    … …  
    205208
    206209    typedef typename Parent::UndirEdge UndirEdge;
    207     typedef typename Parent::UndirEdgeIt UndirEdgeIt;
    208210
    209211    template <typename _Value>
    210     class UndirEdgeMap :
    211       public DefaultMap<Graph, UndirEdge, UndirEdgeIt, _Value> {
     212    class UndirEdgeMap
     213      : public IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> > {
    212214    public:
    213215      typedef MappableUndirGraphExtender Graph;
    214       typedef DefaultMap<Graph, UndirEdge, UndirEdgeIt, _Value> Parent;
     216      typedef IterableMapExtender<
     217        DefaultMap<Graph, UndirEdge, _Value> > Parent;
    215218
    216219      UndirEdgeMap(const Graph& _g)

  • src/lemon/graph_utils.h

    r1192 r1267  
    2222#include <lemon/invalid.h>
    2323#include <lemon/utility.h>
    24 #include <lemon/map_utils.h>
    2524
    2625///\ingroup gutils
    … …  
    3534namespace lemon {
    3635
    37 /// \addtogroup gutils
    38 /// @{
     36  /// \addtogroup gutils
     37  /// @{
    3938
    4039  /// \brief Function to count the items in the graph.
    … …  
    161160  template <typename Graph>
    162161  typename Graph::Edge findEdge(const Graph &g,
    163                 typename Graph::Node u, typename Graph::Node v,
    164                 typename Graph::Edge prev = INVALID)
     162                                typename Graph::Node u, typename Graph::Node v,
     163                                typename Graph::Edge prev = INVALID)
    165164  {
    166165    typename Graph::OutEdgeIt e(g,prev);
    … …  
    226225  }
    227226 
    228    template <
     227  template <
    229228    typename _DestinationGraph,
    230229    typename _SourceGraph,
    … …  
    232231    =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
    233232    typename _EdgeBijection
    234     =typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
    235    >
    236    class GraphCopy {
    237    public:
    238 
    239      typedef _DestinationGraph DestinationGraph;
    240      typedef _SourceGraph SourceGraph;
    241 
    242      typedef _NodeBijection NodeBijection;
    243      typedef _EdgeBijection EdgeBijection;
    244 
    245    protected:         
    246 
    247      NodeBijection node_bijection;
    248      EdgeBijection edge_bijection;     
    249 
    250    public:
     233    = typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
     234  >
     235  class GraphCopy {
     236  public:
     237   
     238    typedef _DestinationGraph DestinationGraph;
     239    typedef _SourceGraph SourceGraph;
     240
     241    typedef _NodeBijection NodeBijection;
     242    typedef _EdgeBijection EdgeBijection;
     243   
     244  protected:         
     245   
     246    NodeBijection node_bijection;
     247    EdgeBijection edge_bijection;     
     248
     249  public:
    251250     
    252      GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
    253        copyGraph(_d, _s, node_bijection, edge_bijection);
    254      }
    255 
    256      const NodeBijection& getNodeBijection() const {
    257        return node_bijection;
    258      }
    259 
    260      const EdgeBijection& getEdgeBijection() const {
    261        return edge_bijection;
    262      }
     251    GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
     252      copyGraph(_d, _s, node_bijection, edge_bijection);
     253    }
     254   
     255    const NodeBijection& getNodeBijection() const {
     256      return node_bijection;
     257    }
     258
     259    const EdgeBijection& getEdgeBijection() const {
     260      return edge_bijection;
     261    }
    263262     
    264    };
     263  };
     264
     265
     266  template <typename _Graph, typename _Item>
     267  class ItemSetTraits {
     268  };
    265269 
    266270  template <typename _Graph>
    267   class GraphNodeSet {
     271  class ItemSetTraits<_Graph, typename _Graph::Node> {
    268272  public:
    269273   
    … …  
    284288    };
    285289
    286     typedef IdMap<Graph, Item> IdMap;
    287    
    288   private:
    289     Graph* graph;
    290290  };
    291291
    292292  template <typename _Graph>
    293   class GraphEdgeSet {
     293  class ItemSetTraits<_Graph, typename _Graph::Edge> {
    294294  public:
    295295   
    … …  
    310310    };
    311311
    312     typedef IdMap<Graph, Item> IdMap;
    313    
    314   private:
    315     Graph* graph;
    316   };
    317 
     312  };
     313
     314  template <typename _Graph>
     315  class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
     316  public:
     317   
     318    typedef _Graph Graph;
     319
     320    typedef typename Graph::UndirEdge Item;
     321    typedef typename Graph::UndirEdgeIt ItemIt;
     322
     323    template <typename _Value>
     324    class Map : public Graph::template UndirEdgeMap<_Value> {
     325    public:
     326      typedef typename Graph::template UndirEdgeMap<_Value> Parent;
     327      typedef typename Parent::Value Value;
     328
     329      Map(const Graph& _graph) : Parent(_graph) {}
     330      Map(const Graph& _graph, const Value& _value)
     331        : Parent(_graph, _value) {}
     332    };
     333
     334  };
    318335
    319336  /// @}

  • src/lemon/map_iterator.h

    r1164 r1267  
    2121
    2222#include <lemon/extended_pair.h>
     23#include <lemon/map_utils.h>
    2324
    2425///\ingroup graphmaps
    … …  
    3637   */
    3738
    38   template <typename Map>
     39  template <
     40    typename _Graph,
     41    typename _Item>
    3942  class MapIteratorBase {
    4043
    41   public:
     44  protected:
    4245
    4346    /// The key type of the iterator.
    44     typedef typename Map::Key Key;
    45     /// The iterator to iterate on the keys.
    46     typedef typename Map::KeyIt KeyIt;
    47 
    48     /// The value type of the iterator.
    49     typedef typename Map::Value Value;
    50     /// The reference type of the iterator.
    51     typedef typename Map::Reference Reference;
    52     /// The pointer type of the iterator.
    53     typedef typename Map::Pointer Pointer;
    54 
    55     /// The const value type of the iterator.
    56     typedef typename Map::ConstValue ConstValue;
    57     /// The const reference type of the iterator.
    58     typedef typename Map::ConstReference ConstReference;
    59     /// The pointer type of the iterator.
    60     typedef typename Map::ConstPointer ConstPointer;
    61 
    62   protected:
    63 
    64     KeyIt it;
     47    typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
     48
     49    ItemIt it;
    6550
    6651    /// Default constructor.
    6752    MapIteratorBase() {}
    6853
    69     /// KeyIt initialized MapIteratorBase constructor.
    70     MapIteratorBase(const KeyIt pit) : it(pit) {}
     54    /// ItemIt initialized MapIteratorBase constructor.
     55    MapIteratorBase(const ItemIt _it) : it(_it) {}
    7156
    7257  public:
    … …  
    7863
    7964    /// The equality operator of the map.
    80     bool operator==(const MapIteratorBase& pit) const {
    81       return pit.it == it;
     65    bool operator==(const MapIteratorBase& _it) const {
     66      return _it.it == it;
    8267    }
    8368       
    8469    /// The not-equality operator of the map.
    85     bool operator!=(const MapIteratorBase& pit) const {
    86       return !(*this == pit);
    87     }
    88   };
    89 
    90   template <typename Map> class MapConstIterator;
     70    bool operator!=(const MapIteratorBase& _it) const {
     71      return !(*this == _it);
     72    }
     73  };
     74
     75
     76  template <
     77    typename _Graph,
     78    typename _Item,
     79    typename _Map>
     80  class MapConstIterator;
    9181
    9282  /** Compatible iterator with the stl maps' iterators.
    9383   * It iterates on pairs of a key and a value.
    9484   */
    95   template <typename Map> 
    96   class MapIterator : public MapIteratorBase<Map> {
    97 
    98     friend class MapConstIterator<Map>;
     85  template <
     86    typename _Graph,
     87    typename _Item,
     88    typename _Map>
     89  class MapIterator : public MapIteratorBase<_Graph, _Item> {
     90
     91    friend class MapConstIterator<_Graph, _Item, _Map>;
    9992
    10093
    … …  
    10295
    10396    /// The iterator base class.
    104     typedef MapIteratorBase<Map> Base;
    105 
    106     /// The key type of the iterator.
    107     typedef typename Map::Key Key;
    108     /// The iterator to iterate on the keys.
    109     typedef typename Map::KeyIt KeyIt;
     97    typedef MapIteratorBase<_Graph, _Item> Parent;
     98
     99    typedef _Item Item;
     100    typedef _Map Map;
     101    typedef _Graph Graph;
     102
     103  protected:
     104
     105    typedef typename Parent::ItemIt ItemIt;
     106
     107    typedef typename ReferenceMapTraits<_Map>::Value MapValue;
     108    typedef typename ReferenceMapTraits<_Map>::Reference MapReference;
     109   
     110  public:
    110111
    111112    /// The value type of the iterator.
    112     typedef typename Map::Value Value;
    113     /// The reference type of the iterator.
    114     typedef typename Map::Reference Reference;
    115     /// The pointer type of the iterator.
    116     typedef typename Map::Pointer Pointer;
    117 
    118     /// The const value type of the iterator.
    119     typedef typename Map::ConstValue ConstValue;
    120     /// The const reference type of the iterator.
    121     typedef typename Map::ConstReference ConstReference;
    122     /// The pointer type of the iterator.
    123     typedef typename Map::ConstPointer ConstPointer;
    124    
    125   public:
    126 
    127     /// The value type of the iterator.
    128     typedef extended_pair<Key, const Key&,
    129       Value, const Value&> PairValue;
     113    typedef extended_pair<Item, const Item&,
     114      MapValue, const MapValue&> Value;
    130115
    131116    /// The reference type of the iterator.
    132     typedef extended_pair<const Key&, const Key&,
    133       Reference, Reference> PairReference;
     117    typedef extended_pair<const Item&, const Item&,
     118      MapReference, MapReference> Reference;
    134119
    135120    /// Default constructor.
    … …  
    138123    /// Constructor to initalize the iterators returned
    139124    /// by the begin() and end().
    140     MapIterator(Map& pmap, const KeyIt& pit) : Base(pit), map(&pmap) {}
     125    MapIterator(Map& _map, const ItemIt& _it)
     126      : Parent(_it), map(&_map) {}
    141127
    142128    /// Dereference operator for the iterator.
    143     PairReference operator*() {
    144       return PairReference(Base::it, (*map)[Base::it]);
     129    Reference operator*() {
     130      return Reference(Parent::it, (*map)[Parent::it]);
    145131    }
    146132
    147133    /// The pointer type of the iterator.
    148     class PairPointer {
     134    class Pointer {
    149135      friend class MapIterator;
    150     private:
    151       PairReference data;
    152       PairPointer(const Key& key, Reference val)
    153         : data(key, val) {}
     136    protected:
     137      Reference data;
     138      Pointer(const Item& item, MapReference val)
     139        : data(item, val) {}
    154140    public:
    155       PairReference* operator->() {return &data;}
     141      Reference* operator->() {return &data;}
    156142    };
    157143
    158144    /// Arrow operator for the iterator.
    159     PairPointer operator->() {
    160       return PairPointer(Base::it, ((*map)[Base::it]));
     145    Pointer operator->() {
     146      return Pointer(Parent::it, (*map)[Parent::it]);
    161147    }
    162148       
    163149    /// The pre increment operator of the iterator.
    164150    MapIterator& operator++() {
    165       Base::increment();
     151      Parent::increment();
    166152      return *this;
    167153    }
    … …  
    170156    MapIterator operator++(int) {
    171157      MapIterator tmp(*this);
    172       Base::increment();
     158      Parent::increment();
    173159      return tmp;
    174160    }
    175161
    176   private:
     162  protected:
     163
    177164    Map* map;
    178165
    … …  
    181168    typedef std::forward_iterator_tag iterator_category;
    182169    typedef int difference_type;
    183     typedef PairValue value_type;
    184     typedef PairReference reference;
    185     typedef PairPointer pointer;
     170    typedef Value value_type;
     171    typedef Reference reference;
     172    typedef Pointer pointer;
    186173  };
    187174
    … …  
    189176   *  It iterates on pairs of a key and a value.
    190177   */
    191   template <typename Map>
    192   class MapConstIterator : public MapIteratorBase<Map> {
    193    
     178  template <
     179    typename _Graph,
     180    typename _Item,
     181    typename _Map>
     182  class MapConstIterator : public MapIteratorBase<_Graph, _Item> {
     183
    194184  public:
    195185
    196186    /// The iterator base class.
    197     typedef MapIteratorBase<Map> Base;
    198 
    199     /// The key type of the iterator.
    200     typedef typename Map::Key Key;
    201     /// The iterator to iterate on the keys.
    202     typedef typename Map::KeyIt KeyIt;
     187    typedef MapIteratorBase<_Graph, _Item> Parent;
     188
     189    typedef _Graph Graph;
     190    typedef _Item Item;
     191    typedef _Map Map;
     192
     193  protected:
     194
     195    typedef typename Parent::ItemIt ItemIt;
     196
     197    typedef typename ReferenceMapTraits<_Map>::Value MapValue;
     198    typedef typename ReferenceMapTraits<_Map>::ConstReference
     199    MapReference;
     200   
     201  public:
    203202
    204203    /// The value type of the iterator.
    205     typedef typename Map::Value Value;
    206     /// The reference type of the iterator.
    207     typedef typename Map::Reference Reference;
    208     /// The pointer type of the iterator.
    209     typedef typename Map::Pointer Pointer;
    210 
    211     /// The const value type of the iterator.
    212     typedef typename Map::ConstValue ConstValue;
    213     /// The const reference type of the iterator.
    214     typedef typename Map::ConstReference ConstReference;
    215     /// The pointer type of the iterator.
    216     typedef typename Map::ConstPointer ConstPointer;
    217 
    218   public:   
     204    typedef extended_pair<Item, const Item&,
     205      MapValue, const MapValue&> Value;
     206
     207    /// The reference type of the iterator.
     208    typedef extended_pair<const Item&, const Item&,
     209      MapReference, MapReference> Reference;
    219210
    220211    /// Default constructor.
    221212    MapConstIterator() {}
    222213
    223     /// Constructor to initalize the the iterators returned
    224     ///  by the begin() and end().
    225     MapConstIterator(const Map& pmap, const KeyIt& pit)
    226       : Base(pit), map(&pmap) {}
    227 
    228     /// Constructor to create const iterator from a non const.
    229     MapConstIterator(const MapIterator<Map>& pit) {
    230       Base::it = pit.Base::it;
    231       map = pit.map;
    232     }
    233 
    234     /// The value type of the iterator.
    235     typedef extended_pair<Key, const Key&,
    236       Value, const Value&> PairValue;
    237 
    238     /// The reference type of map.
    239     typedef extended_pair<const Key&, const Key&,
    240       ConstReference, ConstReference> PairReference;
     214    /// Constructor to initalize the iterators returned
     215    /// by the begin() and end().
     216    MapConstIterator(const Map& _map, const ItemIt& _it)
     217      : Parent(_it), map(&_map) {}
    241218
    242219    /// Dereference operator for the iterator.
    243     PairReference operator*() {
    244       return PairReference(Base::it, (*map)[Base::it]);
     220    Reference operator*() {
     221      return Reference(Parent::it, (*map)[Parent::it]);
    245222    }
    246223
    247224    /// The pointer type of the iterator.
    248     class PairPointer {
     225    class Pointer {
    249226      friend class MapConstIterator;
    250     private:
    251       PairReference data;
    252       PairPointer(const Key& key, ConstReference val)
    253         : data(key, val) {}
     227    protected:
     228      Reference data;
     229      Pointer(const Item& item, MapReference val)
     230        : data(item, val) {}
    254231    public:
    255       PairReference* operator->() {return &data;}
     232      Reference* operator->() {return &data;}
    256233    };
    257234
    258235    /// Arrow operator for the iterator.
    259     PairPointer operator->() {
    260       return PairPointer(Base::it, (*map)[Base::it]);
    261     }
    262 
     236    Pointer operator->() {
     237      return Pointer(Parent::it, ((*map)[Parent::it]));
     238    }
     239       
    263240    /// The pre increment operator of the iterator.
    264241    MapConstIterator& operator++() {
    265       Base::increment();
     242      Parent::increment();
    266243      return *this;
    267244    }
    … …  
    270247    MapConstIterator operator++(int) {
    271248      MapConstIterator tmp(*this);
    272       Base::increment();
     249      Parent::increment();
    273250      return tmp;
    274251    }
    275252
    276   private:
     253  protected:
    277254    const Map* map;
    278255
    279256  public:
    280257    // STL  compatibility typedefs.
    281     typedef std::input_iterator_tag iterator_category;
    282     typedef int difference_type;
    283     typedef PairValue value_type;
    284     typedef PairReference reference;
    285     typedef PairPointer pointer;
    286   };
    287 
    288   /** The class makes the KeyIt to an stl compatible iterator
     258    typedef std::forward_iterator_tag iterator_category;
     259    typedef int difference_type;
     260    typedef Value value_type;
     261    typedef Reference reference;
     262    typedef Pointer pointer;
     263  };
     264 
     265  /** The class makes the ItemIt to an stl compatible iterator
    289266   *  with dereferencing operator.
    290267   */
    291   template <typename Map>
    292   class MapKeyIterator : public MapIteratorBase<Map> {
     268  template <
     269    typename _Graph,
     270    typename _Item>
     271  class MapConstKeyIterator : public MapIteratorBase<_Graph, _Item> {
    293272
    294273  public:
    295274
    296275    /// The iterator base class.
    297     typedef MapIteratorBase<Map> Base;
     276    typedef MapIteratorBase<_Graph, _Item> Parent;
    298277 
    299     /// The key type of the iterator.
    300     typedef typename Map::Key Key;
     278    typedef _Graph Graph;
     279    typedef _Item Item;
     280
     281  protected:
    301282    /// The iterator to iterate on the keys.
    302     typedef typename Map::KeyIt KeyIt;
    303 
    304   public:
     283    typedef typename Parent::ItemIt ItemIt;
     284
     285  public:
     286
     287    typedef Item Value;
     288    typedef const Item& Reference;
     289    typedef const Item* Pointer;
    305290
    306291    /// Default constructor.
    307     MapKeyIterator() {}
    308 
    309     /// KeyIt initialized iterator.
    310     MapKeyIterator(const KeyIt& pit) : Base(pit) {}
     292    MapConstKeyIterator() {}
     293
     294    /// ItemIt initialized iterator.
     295    MapConstKeyIterator(const ItemIt& pit) : Parent(pit) {}
    311296
    312297    /// The pre increment operator of the iterator.
    313     MapKeyIterator& operator++() {
    314       Base::increment();
     298    MapConstKeyIterator& operator++() {
     299      Parent::increment();
    315300      return *this;
    316301    }
    317302
    318303    /// The post increment operator of the iterator.
    319     MapKeyIterator operator++(int) {
    320       MapKeyIterator tmp(*this);
    321       Base::increment();
     304    MapConstKeyIterator operator++(int) {
     305      MapConstKeyIterator tmp(*this);
     306      Parent::increment();
    322307      return tmp;
    323308    }
    324309
    325310    /// The dereferencing operator of the iterator.
    326     Key operator*() const {
    327       return static_cast<Key>(Base::it);
     311    Item operator*() const {
     312      return static_cast<Item>(Parent::it);
    328313    }
    329314
    … …  
    332317    typedef std::input_iterator_tag iterator_category;
    333318    typedef int difference_type;
    334     typedef Key value_type;
    335     typedef const Key& reference;
    336     typedef const Key* pointer;
    337   };
    338 
    339   template <typename Map> class MapConstValueIterator;
     319    typedef Value value_type;
     320    typedef Reference reference;
     321    typedef Pointer pointer;
     322  };
     323
     324  template <
     325    typename _Graph,
     326    typename _Item,
     327    typename _Map>
     328  class MapConstValueIterator;
    340329
    341330  /** MapValueIterator creates an stl compatible iterator
    342331   *  for the values.
    343332   */
    344   template <typename Map>
    345   class MapValueIterator : public MapIteratorBase<Map> {
    346 
    347     friend class MapConstValueIterator<Map>;
     333  template <
     334    typename _Graph,
     335    typename _Item,
     336    typename _Map>
     337  class MapValueIterator : public MapIteratorBase<_Graph, _Item> {
     338
     339    friend class MapConstValueIterator<_Graph, _Item, _Map>;
    348340
    349341  public:
    350342
    351343    /// The iterator base class.
    352     typedef MapIteratorBase<Map> Base;
    353 
    354     /// The key type of the iterator.
    355     typedef typename Map::Key Key;
     344    typedef MapIteratorBase<_Graph, _Item> Parent;
     345
     346    typedef _Graph Graph;
     347    typedef _Item Item;
     348    typedef _Map Map;
     349
     350  protected:
     351
    356352    /// The iterator to iterate on the keys.
    357     typedef typename Map::KeyIt KeyIt;
    358 
     353    typedef typename Parent::ItemIt ItemIt;
    359354
    360355    /// The value type of the iterator.
    361     typedef typename Map::Value Value;
     356    typedef typename ReferenceMapTraits<Map>::Value MapValue;
    362357    /// The reference type of the iterator.
    363     typedef typename Map::Reference Reference;
     358    typedef typename ReferenceMapTraits<Map>::Reference MapReference;
    364359    /// The pointer type of the iterator.
    365     typedef typename Map::Pointer Pointer;
    366 
    367     /// The const value type of the iterator.
    368     typedef typename Map::ConstValue ConstValue;
    369     /// The const reference type of the iterator.
    370     typedef typename Map::ConstReference ConstReference;
    371     /// The pointer type of the iterator.
    372     typedef typename Map::ConstPointer ConstPointer;
    373 
    374   private:
    375 
    376     Map* map;
    377 
    378   public:
     360    typedef typename ReferenceMapTraits<Map>::Pointer MapPointer;
     361
     362  public:
     363
     364    typedef MapValue Value;
     365    typedef MapReference Reference;
     366    typedef MapPointer Pointer;
    379367
    380368    /// Default constructor.
    381369    MapValueIterator() {}
    382370
    383     /// Map and KeyIt initialized iterator.
    384     MapValueIterator(Map& pmap, const KeyIt& pit)
    385       : Base(pit), map(&pmap) {}
     371    /// Map and ItemIt initialized iterator.
     372    MapValueIterator(Map& _map, const ItemIt& _it)
     373      : Parent(_it), map(&_map) {}
    386374   
    387375
    388376    /// The pre increment operator of the iterator.
    389377    MapValueIterator& operator++() {
    390       Base::increment();
     378      Parent::increment();
    391379      return *this;
    392380    }
    … …  
    395383    MapValueIterator operator++(int) {
    396384      MapValueIterator tmp(*this);
    397       Base::increment();
     385      Parent::increment();
    398386      return tmp;
    399387    }
    … …  
    401389    /// The dereferencing operator of the iterator.
    402390    Reference operator*() const {
    403       return (*map)[Base::it];
     391      return (*map)[Parent::it];
    404392    }
    405393
    … …  
    409397    }
    410398
     399  protected:
     400
     401    Map* map;
     402
    411403  public:
    412404    // STL  compatibility typedefs.
    … …  
    419411
    420412  /** MapValueIterator creates an stl compatible iterator
    421    *  for the const values.
     413   *  for the values.
    422414   */
    423 
    424   template <typename Map>
    425   class MapConstValueIterator : public MapIteratorBase<Map> {
     415  template <
     416    typename _Graph,
     417    typename _Item,
     418    typename _Map>
     419  class MapConstValueIterator : public MapIteratorBase<_Graph, _Item> {
    426420
    427421  public:
    428422
    429423    /// The iterator base class.
    430     typedef MapIteratorBase<Map> Base;
    431 
    432     /// The key type of the iterator.
    433     typedef typename Map::Key Key;
     424    typedef MapIteratorBase<_Graph, _Item> Parent;
     425
     426    typedef _Graph Graph;
     427    typedef _Item Item;
     428    typedef _Map Map;
     429
     430  protected:
     431
    434432    /// The iterator to iterate on the keys.
    435     typedef typename Map::KeyIt KeyIt;
     433    typedef typename Parent::ItemIt ItemIt;
    436434
    437435    /// The value type of the iterator.
    438     typedef typename Map::Value Value;
     436    typedef typename ReferenceMapTraits<Map>::Value MapValue;
    439437    /// The reference type of the iterator.
    440     typedef typename Map::Reference Reference;
     438    typedef typename ReferenceMapTraits<Map>::ConstReference MapReference;
    441439    /// The pointer type of the iterator.
    442     typedef typename Map::Pointer Pointer;
    443 
    444     /// The const value type of the iterator.
    445     typedef typename Map::ConstValue ConstValue;
    446     /// The const reference type of the iterator.
    447     typedef typename Map::ConstReference ConstReference;
    448     /// The pointer type of the iterator.
    449     typedef typename Map::ConstPointer ConstPointer;
    450 
    451   private:
    452 
    453     const Map* map;
    454 
    455   public:
     440    typedef typename ReferenceMapTraits<Map>::ConstPointer MapPointer;
     441
     442  public:
     443
     444    typedef MapValue Value;
     445    typedef MapReference Reference;
     446    typedef MapPointer Pointer;
    456447
    457448    /// Default constructor.
    458449    MapConstValueIterator() {}
    459450
    460     /// Constructor to create const iterator from a non const.
    461     MapConstValueIterator(const MapValueIterator<Map>& pit) {
    462       Base::it = pit.Base::it;
    463       map = pit.map;
    464     }
    465 
    466     /// Map and KeyIt initialized iterator.
    467     MapConstValueIterator(const Map& pmap, const KeyIt& pit)
    468       : Base(pit), map(&pmap) {}
     451    /// Map and ItemIt initialized iterator.
     452    MapConstValueIterator(const Map& _map, const ItemIt& _it)
     453      : Parent(_it), map(&_map) {}
     454   
    469455
    470456    /// The pre increment operator of the iterator.
    471457    MapConstValueIterator& operator++() {
    472       Base::increment();
     458      Parent::increment();
    473459      return *this;
    474460    }
    … …  
    477463    MapConstValueIterator operator++(int) {
    478464      MapConstValueIterator tmp(*this);
    479       Base::increment();
     465      Parent::increment();
    480466      return tmp;
    481467    }
    482468
    483469    /// The dereferencing operator of the iterator.
    484     ConstReference operator*() const {
    485       return (*map)[Base::it];
     470    Reference operator*() const {
     471      return (*map)[Parent::it];
    486472    }
    487473
    488474    /// The arrow operator of the iterator.
    489     ConstPointer operator->() const {
     475    Pointer operator->() const {
    490476      return &(operator*());
    491477    }
    492478
    493   public:
    494     // STL  compatibility typedefs.
    495     typedef std::input_iterator_tag iterator_category;
    496     typedef int difference_type;
    497     typedef Value value_type;
    498     typedef ConstReference reference;
    499     typedef ConstPointer pointer;
     479  protected:
     480
     481    const Map* map;
     482
     483  public:
     484    // STL  compatibility typedefs.
     485    typedef std::forward_iterator_tag iterator_category;
     486    typedef int difference_type;
     487    typedef Value value_type;
     488    typedef Reference reference;
     489    typedef Pointer pointer;
    500490  };
    501491
    … …  
    504494   *  which contains all the keys of the map.
    505495   */
    506   template <typename Map>
     496  template <typename _Graph, typename _Item>
    507497  class MapConstKeySet {
    508498
    509     const Map* map;
    510 
    511   public:
    512 
     499  public:
     500
     501    typedef _Graph Graph;
    513502    /// The key type of the iterator.
    514     typedef typename Map::Key Key;
     503    typedef _Item Item;
    515504    /// The iterator to iterate on the keys.
    516     typedef typename Map::KeyIt KeyIt;
    517 
    518 
    519     /// The value type of the iterator.
    520     typedef typename Map::Value Value;
     505
     506  protected:
     507
     508    typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
     509
     510  public:
     511
     512    /// The map initialized const key set.
     513    MapConstKeySet(const Graph& _graph) : graph(&_graph) {}
     514
     515    /// The const iterator of the set.
     516    typedef MapConstKeyIterator<_Graph, _Item> ConstIterator;
     517
     518    typedef typename ConstIterator::Value Value;
    521519    /// The reference type of the iterator.
    522     typedef typename Map::Reference Reference;
     520    typedef typename ConstIterator::Reference ConstReference;
    523521    /// The pointer type of the iterator.
    524     typedef typename Map::Pointer Pointer;
    525 
    526     /// The const value type of the iterator.
    527     typedef typename Map::ConstValue ConstValue;
    528     /// The const reference type of the iterator.
    529     typedef typename Map::ConstReference ConstReference;
    530     /// The pointer type of the iterator.
    531     typedef typename Map::ConstPointer ConstPointer;
    532 
    533     /// The map initialized const key set.
    534     MapConstKeySet(const Map& pmap) : map(&pmap) {}
    535 
    536     /// The const iterator of the set.
    537     typedef MapKeyIterator<Map> ConstIterator;
     522    typedef typename ConstIterator::Pointer ConstPointer;
    538523
    539524    /// It gives back the const iterator pointed to the first element.
    540525    ConstIterator begin() const {
    541       return ConstIterator(KeyIt(*map->getGraph()));
     526      return ConstIterator(ItemIt(*graph));
    542527    }
    543528           
    544529    /// It gives back the const iterator pointed to the first ivalid element.
    545530    ConstIterator end() const {
    546       return ConstIterator(KeyIt(INVALID));
    547     }
     531      return ConstIterator(ItemIt(INVALID));
     532    }
     533
     534  protected:
     535
     536    const Graph* graph;
    548537 
    549538  public:
    … …  
    560549   *  The values cannot be modified.
    561550   */
    562   template <typename Map>
     551  template <typename _Graph, typename _Item, typename _Map>
    563552  class MapConstValueSet {
    564553
    565     const Map* map;
    566 
    567   public:
    568 
    569     /// The key type of the iterator.
    570     typedef typename Map::Key Key;
     554  public:
     555   
     556    typedef _Graph Graph;
     557    typedef _Item Item;
     558    typedef _Map Map;
     559
     560  protected:
     561
    571562    /// The iterator to iterate on the keys.
    572     typedef typename Map::KeyIt KeyIt;
    573 
    574 
    575     /// The value type of the iterator.
    576     typedef typename Map::Value Value;
    577     /// The reference type of the iterator.
    578     typedef typename Map::Reference Reference;
    579     /// The pointer type of the iterator.
    580     typedef typename Map::Pointer Pointer;
    581 
    582     /// The const value type of the iterator.
    583     typedef typename Map::ConstValue ConstValue;
    584     /// The const reference type of the iterator.
    585     typedef typename Map::ConstReference ConstReference;
    586     /// The pointer type of the iterator.
    587     typedef typename Map::ConstPointer ConstPointer;
     563    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
     564
     565  public:
    588566
    589567    /// The map initialized const value set.
    590     MapConstValueSet(const Map& pmap) : map(&pmap) {}
     568    MapConstValueSet(const Graph& _graph, const Map& _map)
     569      : graph(&_graph), map(&_map) {}
    591570
    592571    /// The const iterator of the set.
    593     typedef MapConstValueIterator<Map> ConstIterator;
     572    typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
     573
     574    typedef typename ConstIterator::Value Value;
     575    typedef typename ConstIterator::Reference ConstReference;
     576    typedef typename ConstIterator::Pointer ConstPointer;
    594577
    595578    /// It gives back the const iterator pointed to the first element.
    596579    ConstIterator begin() const {
    597       return ConstIterator(*map, KeyIt(*map->getGraph()));
     580      return ConstIterator(*map, ItemIt(*graph));
    598581    }
    599582
    600583    /// It gives back the const iterator pointed to the first invalid element.
    601584    ConstIterator end() const {
    602       return ConstIterator(*map, KeyIt(INVALID));
    603     }
     585      return ConstIterator(*map, ItemIt(INVALID));
     586    }
     587
     588  protected:
     589   
     590    const Map* map;
     591    const Graph * graph;
    604592
    605593  public:
    … …  
    617605   *  The values can be modified.
    618606   */
    619   template <typename Map>
     607  template <typename _Graph, typename _Item, typename _Map>
    620608  class MapValueSet {
    621609
    622     Map* map;
    623 
    624   public:
    625 
    626     /// The key type of the iterator.
    627     typedef typename Map::Key Key;
     610  public:
     611   
     612    typedef _Graph Graph;
     613    typedef _Item Item;
     614    typedef _Map Map;
     615
     616  protected:
     617
    628618    /// The iterator to iterate on the keys.
    629     typedef typename Map::KeyIt KeyIt;
    630 
    631 
    632     /// The value type of the iterator.
    633     typedef typename Map::Value Value;
    634     /// The reference type of the iterator.
    635     typedef typename Map::Reference Reference;
    636     /// The pointer type of the iterator.
    637     typedef typename Map::Pointer Pointer;
    638 
    639     /// The const value type of the iterator.
    640     typedef typename Map::ConstValue ConstValue;
    641     /// The const reference type of the iterator.
    642     typedef typename Map::ConstReference ConstReference;
    643     /// The pointer type of the iterator.
    644     typedef typename Map::ConstPointer ConstPointer;
    645 
    646     /// The map initialized value set.
    647     MapValueSet(Map& pmap) : map(&pmap) {}
     619    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
     620
     621  public:
     622
     623    /// The map initialized const value set.
     624    MapValueSet(const Graph& _graph, Map& _map)
     625      : graph(&_graph), map(&_map) {}
    648626
    649627    /// The const iterator of the set.
    650     typedef MapConstValueIterator<Map> ConstIterator;
     628    typedef MapValueIterator<_Graph, _Item, _Map> Iterator;
     629    /// The const iterator of the set.
     630    typedef MapConstValueIterator<_Graph, _Item, _Map> ConstIterator;
     631
     632    typedef typename ConstIterator::Value Value;
     633    typedef typename Iterator::Reference Reference;
     634    typedef typename Iterator::Pointer Pointer;
     635    typedef typename ConstIterator::Reference ConstReference;
     636    typedef typename ConstIterator::Pointer ConstPointer;
    651637
    652638    /// It gives back the const iterator pointed to the first element.
    653639    ConstIterator begin() const {
    654       return ConstIterator(*map, KeyIt(*map->getGraph()));
     640      return ConstIterator(*map, ItemIt(*graph));
    655641    }
    656642
    657643    /// It gives back the const iterator pointed to the first invalid element.
    658644    ConstIterator end() const {
    659       return ConstIterator(*map, KeyIt(INVALID));
    660     }
    661 
    662     /// The iterator of the set.
    663     typedef MapValueIterator<Map> Iterator;
     645      return ConstIterator(*map, ItemIt(INVALID));
     646    }
    664647
    665648    /// It gives back the iterator pointed to the first element.
    666649    Iterator begin() {
    667       return Iterator(*map, KeyIt(*map->getGraph()));
     650      return Iterator(*map, ItemIt(*graph));
    668651    }
    669652
    670653    /// It gives back the iterator pointed to the first invalid element.
    671654    Iterator end() {
    672       return Iterator(*map, KeyIt(INVALID));
    673     }
    674            
     655      return Iterator(*map, ItemIt(INVALID));
     656    }
     657
     658  protected:
     659   
     660    Map* map;
     661    const Graph * graph;
     662
    675663  public:
    676664    // STL  compatibility typedefs.
    … …  
    686674  };
    687675
     676  /** This class makes from a map an iteratable set
     677   *  which contains all the values of the map.
     678   *  The values can be modified.
     679   */
     680  template <
     681    typename _Graph,
     682    typename _Item,
     683    typename _Map
     684    >
     685  class MapSet {
     686  public:   
     687
     688    typedef _Graph Graph;
     689    typedef _Item Item;
     690    typedef _Map Map;
     691
     692  protected:
     693
     694    typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
     695
     696  public:
     697
     698    /// The map initialized value set.
     699    MapSet(const Graph& _graph, Map& _map) : graph(&_graph), map(&_map) {}
     700
     701    /// The const iterator of the set.
     702    typedef MapIterator<_Graph, _Item, _Map> Iterator;
     703    typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
     704
     705    typedef typename ConstIterator::Value Value;
     706    typedef typename Iterator::Reference Reference;
     707    typedef typename Iterator::Pointer Pointer;
     708    typedef typename ConstIterator::Reference ConstReference;
     709    typedef typename ConstIterator::Pointer ConstPointer;
     710
     711
     712    /// It gives back the const iterator pointed to the first element.
     713    ConstIterator begin() const {
     714      return ConstIterator(*map, ItemIt(*graph));
     715    }
     716
     717    /// It gives back the const iterator pointed to the first invalid element.
     718    ConstIterator end() const {
     719      return ConstIterator(*map, ItemIt(INVALID));
     720    }
     721
     722    /// The iterator of the set.
     723
     724    /// It gives back the iterator pointed to the first element.
     725    Iterator begin() {
     726      return Iterator(*map, ItemIt(*graph));
     727    }
     728
     729    /// It gives back the iterator pointed to the first invalid element.
     730    Iterator end() {
     731      return Iterator(*map, ItemIt(INVALID));
     732    }
     733
     734  protected:
     735   
     736    const Graph* graph;
     737    Map* map;
     738           
     739  public:
     740    // STL  compatibility typedefs.
     741    typedef Value value_type;
     742    typedef Iterator iterator;
     743    typedef ConstIterator const_iterator;
     744    typedef Reference reference;
     745    typedef ConstReference const_reference;
     746    typedef Pointer pointer;
     747    typedef ConstPointer const_pointer;
     748    typedef int difference_type;
     749
     750  };
     751
     752  template <
     753    typename _Graph,
     754    typename _Item,
     755    typename _Map
     756    >
     757  class ConstMapSet {
     758   
     759    typedef _Graph Graph;
     760    typedef _Map Map;
     761
     762    const Graph* graph;
     763    const Map* map;
     764
     765  public:
     766
     767    typedef typename ItemSetTraits<_Graph, _Item>::ItemIt ItemIt;
     768
     769
     770    /// The map initialized value set.
     771    ConstMapSet(const Graph& _graph, const Map& _map)
     772      : graph(&_graph), map(&_map) {}
     773
     774    /// The const iterator of the set.
     775    typedef MapConstIterator<_Graph, _Item, _Map> ConstIterator;
     776
     777    typedef typename ConstIterator::Value Value;
     778    typedef typename ConstIterator::Reference ConstReference;
     779    typedef typename ConstIterator::Pointer ConstPointer;
     780
     781
     782    /// It gives back the const iterator pointed to the first element.
     783    ConstIterator begin() const {
     784      return ConstIterator(*map, ItemIt(*graph));
     785    }
     786
     787    /// It gives back the const iterator pointed to the first invalid element.
     788    ConstIterator end() const {
     789      return ConstIterator(*map, ItemIt(INVALID));
     790    }
     791           
     792  public:
     793    // STL  compatibility typedefs.
     794    typedef Value value_type;
     795    typedef ConstIterator const_iterator;
     796    typedef ConstReference const_reference;
     797    typedef ConstPointer const_pointer;
     798    typedef int difference_type;
     799
     800  };
     801
     802  template <typename _Map>
     803  class IterableMapExtender : public _Map {
     804  public:
     805
     806    typedef _Map Parent;
     807    typedef Parent Map;
     808    typedef typename Map::Graph Graph;
     809    typedef typename Map::Key Item;
     810    typedef typename Map::Value Value;
     811
     812    typedef MapSet<Graph, Item, Map> MapSet;
     813
     814    IterableMapExtender() : Parent() {}
     815
     816    IterableMapExtender(const Graph& graph) : Parent(graph) {}
     817
     818    IterableMapExtender(const Graph& graph, const Value& value)
     819      : Parent(graph, value) {}
     820
     821    MapSet mapSet() {
     822      return MapSet(*Parent::getGraph(), *this);
     823    }
     824
     825    typedef ConstMapSet<Graph, Item, Map> ConstMapSet;
     826
     827    ConstMapSet mapSet() const {
     828      return ConstMapSet(*Parent::getGraph(), *this);
     829    }
     830
     831    typedef MapConstKeySet<Graph, Item> ConstKeySet;
     832 
     833    ConstKeySet keySet() const {
     834      return ConstKeySet(*Parent::getGraph());
     835    }
     836
     837    typedef MapValueSet<Graph, Item, Map> ValueSet;
     838 
     839    ValueSet valueSet() {
     840      return ValueSet(*Parent::getGraph(), *this);
     841    }
     842
     843    typedef MapConstValueSet<Graph, Item, Map> ConstValueSet;
     844 
     845    ConstValueSet valueSet() const {
     846      return ConstValueSet(*Parent::getGraph(), *this);
     847    }
     848
     849  };
     850
    688851  /// @}
    689852

  • src/lemon/map_utils.h

    r1239 r1267  
    2626#include <vector>
    2727
     28#include <lemon/graph_utils.h>
     29
    2830namespace lemon {
    2931
    3032  /// \addtogroup mutils
    3133  /// @{
     34
     35
     36  template <typename Map, typename Enable = void>
     37  struct ReferenceMapTraits {
     38    typedef typename Map::Value Value;
     39    typedef typename Map::Value& Reference;
     40    typedef const typename Map::Value& ConstReference;
     41    typedef typename Map::Value* Pointer;
     42    typedef const typename Map::Value* ConstPointer;
     43  };
     44
     45  template <typename Map>
     46  struct ReferenceMapTraits<
     47    Map,
     48    typename enable_if<typename Map::FullTypeTag, void>::type
     49  > {
     50    typedef typename Map::Value Value;
     51    typedef typename Map::Reference Reference;
     52    typedef typename Map::ConstReference ConstReference;
     53    typedef typename Map::Pointer Pointer;
     54    typedef typename Map::ConstPointer ConstPointer;
     55  };
    3256
    3357  /// \brief General inversable map type.
    … …  
    4064  /// \param _Map The map to extend with inversable functionality.
    4165  template <
    42     typename _Graph,
    43     typename _Map
     66    typename _Graph,
     67    typename _Item,
     68    typename _Value,
     69    typename _Map
     70    = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>
    4471  >
    4572  class InversableMap : protected _Map {
    4673
    4774  public:
     75 
     76    typedef _Map Map;
    4877    typedef _Graph Graph;
    49 
    50     typedef _Map Map;
    51     /// The key type of InversableMap (Node, Edge, UndirEdge).
     78   /// The key type of InversableMap (Node, Edge, UndirEdge).
    5279    typedef typename _Map::Key Key;
    5380    /// The value type of the InversableMap.
    5481    typedef typename _Map::Value Value;
     82
    5583    typedef std::map<Value, Key> InverseMap;
    5684   
    … …  
    6593    /// \brief The setter function of the map.
    6694    ///
    67     /// It sets the map and the inverse map to given key-value pair.
     95
    6896    void set(const Key& key, const Value& val) {
    6997      Value oldval = Map::operator[](key);
    … …  
    141169    typename _Graph,   
    142170    typename _Item,
    143     typename _Map
     171    typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int>
    144172  >
    145173  class DescriptorMap : protected _Map {
    … …  
    238266    typedef int Value;
    239267    typedef _Item Item;
     268    typedef _Item Key;
    240269
    241270    /// \brief The class represents the inverse of the map.

  • src/lemon/vector_map.h

    r1164 r1267  
    2121#include <algorithm>
    2222
     23#include <lemon/utility.h>
     24#include <lemon/map_iterator.h>
    2325#include <lemon/alteration_notifier.h>
    2426
    … …  
    4547       
    4648
    47   template <typename _Graph,
    48             typename _Item,
    49             typename _Value>
     49  template <
     50    typename _Graph,
     51    typename _Item,   
     52    typename _Value
     53    >
    5054  class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
    5155  public:
    … …  
    8387    /// The pointer type of the map;
    8488    typedef typename Container::const_pointer ConstPointer;
     89
     90    typedef True FullTypeTag;
    8591
    8692    /// Constructor to attach the new map into the registry.
    … …  
    206212      container.clear();
    207213    }
    208 
     214   
    209215  private:
    210216               
    … …  
    233239
    234240   
    235 
    236241    template <typename _Value>
    237     class NodeMap : public VectorMap<Graph, Node, _Value> {
     242    class NodeMap :
     243      public IterableMapExtender<VectorMap<Graph, Node, _Value> > {
    238244    public:
    239245      typedef VectorMappableGraphExtender<_Base> Graph;
    … …  
    241247      typedef typename Graph::Node Node;
    242248
    243       typedef VectorMap<Graph, Node, _Value> Parent;
     249      typedef IterableMapExtender<VectorMap<Graph, Node, _Value> > Parent;
    244250
    245251      //typedef typename Parent::Graph Graph;
    … …  
    254260
    255261    template <typename _Value>
    256     class EdgeMap : public VectorMap<Graph, Edge, _Value> {
     262    class EdgeMap
     263      : public IterableMapExtender<VectorMap<Graph, Edge, _Value> > {
    257264    public:
    258265      typedef VectorMappableGraphExtender<_Base> Graph;
    … …  
    260267      typedef typename Graph::Edge Edge;
    261268
    262       typedef VectorMap<Graph, Edge, _Value> Parent;
     269      typedef IterableMapExtender<VectorMap<Graph, Edge, _Value> > Parent;
    263270
    264271      //typedef typename Parent::Graph Graph;

  • src/work/deba/test.cpp

    r1210 r1267  
    55#include <lemon/utility.h>
    66
    7 using namespace std;
     7using namespace lemon;
    88/*
    99struct _EmptyList {
    … …  
    5858public:
    5959  typedef int X;
     60  typedef True XD;
    6061};
    6162
    … …  
    6364};
    6465
    65 template <typename A>
    66 class TRUE {
     66
     67template <typename _A, bool _B = false>
     68class B {
     69public:
     70  static const bool state = false;
     71};
     72
     73template <typename _A>
     74class B<_A, typename enable_if<typename _A::XD, void>::type> {
    6775public:
    6876  static const bool state = true;
    6977};
    7078
    71 template <typename _A>
    72 class B {
    73 public:
    74   typedef enable_if<A::X, int> state;
    75 };
    76 
    77 template <typename _A>
    78 class B<_A, void> {
    79 public:
    80   static const bool state = true;
    81 };
    8279
    8380int main() {
    84   printf("%s\n", B<A>::state(), true ? "true" : "false");
    85   printf("%s\n", B<C>::state(), true ? "true" : "false");
     81  printf("%s\n", B<A>::state ? "true" : "false");
     82  printf("%s\n", B<C>::state ? "true" : "false");
    8683  return 0;
    8784}
Note: See TracChangeset for help on using the changeset viewer.