COIN-OR::LEMON - Graph Library

Changeset 946:c94ef40a22ce in lemon-0.x for src/lemon/vector_map.h


Ignore:
Timestamp:
10/28/04 00:38:50 (16 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322
Message:

The graph_factory branch (@ 1321) has been merged to trunk.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/vector_map.h

    r937 r946  
    1919
    2020#include <vector>
    21 
    22 #include <lemon/map_iterator.h>
    23 #include <lemon/map_bits.h>
     21#include <algorithm>
     22
     23#include <lemon/alteration_observer_registry.h>
    2424
    2525///\ingroup graphmaps
     
    3232  /// @{
    3333 
    34   /** The VectorMap template class is graph map structure what
    35    *  automatically updates the map when a key is added to or erased from
    36    *  the map. This map factory uses the allocators to implement
    37    *  the container functionality. This map factory
    38    *  uses the std::vector to implement the container function.
    39    *
    40    *  \param MapRegistry The MapRegistry that the maps will belong to.
    41    *  \param Value The value type of the map.
    42    *
    43    *  \author Balazs Dezso
    44    */
    45        
    46   template <typename MapRegistry, typename Value>
    47   class VectorMap : public MapRegistry::MapBase {
    48     template <typename MR, typename T> friend class VectorMap;
     34  /// The VectorMap template class is graph map structure what
     35  /// automatically updates the map when a key is added to or erased from
     36  /// the map. This map factory uses the allocators to implement
     37  /// the container functionality. This map factory
     38  /// uses the std::vector to implement the container function.
     39  ///
     40  /// \param Registry The AlterationObserverRegistry that will notify this map.
     41  /// \param IdMap The IdMap type of the graph items.
     42  /// \param Value The value type of the map.
     43  ///
     44  /// \author Balazs Dezso
     45       
     46
     47  template <typename _Graph,
     48            typename _Item,
     49            typename _IdMap,
     50            typename _Value>
     51  class VectorMap : public AlterationObserverRegistry<_Item>::ObserverBase {
    4952  public:
    5053               
    51     /// The graph type of the maps.
    52     typedef typename MapRegistry::Graph Graph;
    53     /// The key type of the maps.
    54     typedef typename MapRegistry::KeyType KeyType;
    55     /// The iterator to iterate on the keys.
    56     typedef typename MapRegistry::KeyIt KeyIt;
     54    /// The graph type of the map.
     55    typedef _Graph Graph;
     56    /// The key type of the map.
     57    typedef _Item KeyType;
     58    /// The id map type of the map.
     59    typedef _IdMap IdMap;
     60    /// The registry type of the map.
     61    typedef AlterationObserverRegistry<_Item> Registry;
     62    /// The value type of the map.
     63    typedef _Value Value;
    5764
    5865    /// The map type.
    5966    typedef VectorMap Map;
    60     /// The MapBase of the Map which implements the core regisitry function.
    61     typedef typename MapRegistry::MapBase MapBase;
     67    /// The base class of the map.
     68    typedef typename Registry::ObserverBase Parent;
    6269
    6370  private:
     
    6774
    6875  public:
    69 
    7076
    7177    /// The value type of the map.
     
    8389    typedef typename Container::const_pointer ConstPointerType;
    8490
    85     /// Constructor to attach the new map into a registry.
    86 
    87     /** Constructor to attach the new map into a registry.
    88      *  It adds all the nodes or edges of the graph to the map.
     91    /// Constructor to attach the new map into the registry.
     92
     93    /// It construates a map and attachs it into the registry.
     94    /// It adds all the items of the graph to the map.
     95     
     96    VectorMap(const Graph& _g, Registry& _r) : graph(&_g) {
     97      attach(_r);
     98      build();
     99    }
     100
     101    /// Constructor uses given value to initialize the map.
     102
     103    /// It construates a map uses a given value to initialize the map.
     104    /// It adds all the items of the graph to the map.
     105     
     106    VectorMap(const Graph& g, Registry& r, const Value& v) : graph(&g) {
     107      attach(r);
     108      container.resize(IdMap(*graph).maxId() + 1, v);
     109    }
     110
     111    VectorMap(const VectorMap& copy) : graph(copy.getGraph()) {
     112      if (copy.attached()) {
     113        attach(*copy.getRegistry());
     114        container = copy.container;
     115      }
     116    }
     117
     118
     119    /** Assign operator to copy a map of the same map type.
    89120     */
    90     VectorMap(const Graph& g, MapRegistry& r)
    91       : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
    92 
    93     /// Constructor uses given value to initialize the map.
    94 
    95     /** Constructor uses given value to initialize the map.
    96      *  It adds all the nodes or edges of the graph to the map.
    97      */
    98     VectorMap(const Graph& g, MapRegistry& r, const Value& v)
    99       : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {}
    100 
    101     /// Assign operator to copy a map of an other map type.
    102 
    103     /** Assign operator to copy a map of an other map type.
    104      *  This map's value type must be assignable by the other
    105      *  map type's value type.
    106      */
    107     template <typename TT>
    108     VectorMap(const VectorMap<MapRegistry, TT>& c)
    109       : MapBase(c), container(c.container.size()) {
    110       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    111         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
    112         container[id] = c.container[id];
    113       }
    114     }
    115 
    116     /// Assign operator to copy a map of an other map type.
    117 
    118     /** Assign operator to copy a map of an other map type.
    119      *  This map's value type must be assignable by the other
    120      *  map type's value type.
    121      */
    122     template <typename TT>
    123     VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) {
    124       if (MapBase::getGraph() != c.getGraph()) {
    125         MapBase::operator=(c);
    126         container.resize(c.container.size());
    127       }
    128       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    129         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
    130         container[id] = c.container[id];
    131       }
     121    VectorMap& operator=(const VectorMap& copy) {
     122      if (&copy == this) return *this;
     123     
     124      if (graph != copy.graph) {
     125        if (attached()) {
     126          detach();
     127        }
     128        if (copy.attached()) {
     129          attach(*copy.getRegistry());
     130        }
     131      }
     132      container = copy.container;
     133
    132134      return *this;
    133135    }
    134136
     137
     138    virtual ~VectorMap() {
     139      if (attached()) {
     140        detach();
     141      }
     142    }
     143
     144    const Graph* getGraph() const {
     145      return graph;
     146    }
     147
    135148    /// The subcript operator.
    136149
    137     /**
    138      * The subscript operator. The map can be subscripted by the
    139      * actual keys of the graph.
    140      */
     150    /// The subscript operator. The map can be subscripted by the
     151    /// actual items of the graph.
     152     
    141153    ReferenceType operator[](const KeyType& key) {
    142       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
    143       return container[id];
     154      return container[IdMap(*graph)[key]];
    144155    }
    145156               
    146157    /// The const subcript operator.
    147158
    148     /**
    149      * The const subscript operator. The map can be subscripted by the
    150      * actual keys of the graph.
    151      */
     159    /// The const subscript operator. The map can be subscripted by the
     160    /// actual items of the graph.
     161     
    152162    ConstReferenceType operator[](const KeyType& key) const {
    153       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
    154       return container[id];
    155     }
    156 
    157     ///Setter function of the map.
    158 
    159     /** Setter function of the map. Equivalent with map[key] = val.
    160      *  This is a compatibility feature with the not dereferable maps.
    161      */
    162     void set(const KeyType& key, const ValueType& val) {
    163       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
    164       container[id] = val;
    165     }
     163      return container[IdMap(*graph)[key]];
     164    }
     165
     166
     167    /// The setter function of the map.
     168
     169    /// It the same as operator[](key) = value expression.
     170    ///
     171     
     172    void set(const KeyType& key, const ValueType& value) {
     173      (*this)[key] = value;
     174    }
     175
    166176    /// Adds a new key to the map.
    167177               
    168     /** Adds a new key to the map. It called by the map registry
    169      *  and it overrides the \ref MapRegistry::MapBase MapBase's
    170      *  add() member function.
    171      */
     178    /// It adds a new key to the map. It called by the observer registry
     179    /// and it overrides the add() member function of the observer base.
     180     
    172181    void add(const KeyType& key) {
    173       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
     182      int id = IdMap(*graph)[key];
    174183      if (id >= (int)container.size()) {
    175184        container.resize(id + 1);
     
    179188    /// Erases a key from the map.
    180189               
    181     /** Erase a key from the map. It called by the map registry
    182      *  and it overrides the \ref MapRegistry::MapBase MapBase's
    183      *  erase() member function.
    184      */
     190    /// Erase a key from the map. It called by the observer registry
     191    /// and it overrides the erase() member function of the observer base.     
    185192    void erase(const KeyType& key) {}
    186193
    187     /// Makes empty the map.
    188 
    189     /** Makes empty the map. It called by the map registry
    190      *  and it overrides the \ref MapRegistry::MapBase MapBase's
    191      *  clear() member function.
    192      */
    193 
     194    /// Buildes the map.
     195               
     196    /// It buildes the map. It called by the observer registry
     197    /// and it overrides the build() member function of the observer base.
     198
     199    void build() {
     200      container.resize(IdMap(*graph).maxId() + 1);
     201    }
     202
     203    /// Clear the map.
     204
     205    /// It erase all items from the map. It called by the observer registry
     206    /// and it overrides the clear() member function of the observer base.     
    194207    void clear() {
    195208      container.clear();
    196209    }
    197210
    198     /// The stl compatible pair iterator of the map.
    199     typedef MapIterator<VectorMap> Iterator;
    200     /// The stl compatible const pair iterator of the map.
    201     typedef MapConstIterator<VectorMap> ConstIterator;
    202 
    203     /** Returns the begin iterator of the map.
    204      */
    205     Iterator begin() {
    206       return Iterator(*this, KeyIt(*MapBase::getGraph()));
    207     }
    208 
    209     /** Returns the end iterator of the map.
    210      */
    211     Iterator end() {
    212       return Iterator(*this, INVALID);
    213     }
    214 
    215     /** Returns the begin ConstIterator of the map.
    216      */
    217     ConstIterator begin() const {
    218       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
    219     }
    220 
    221     /** Returns the end const_iterator of the map.
    222      */
    223     ConstIterator end() const {
    224       return ConstIterator(*this, INVALID);
    225     }
    226 
    227     /// The KeySet of the Map.
    228     typedef MapConstKeySet<VectorMap> ConstKeySet;
    229 
    230     /// KeySet getter function.
    231     ConstKeySet keySet() const {
    232       return ConstKeySet(*this);
    233     }
    234 
    235     /// The ConstValueSet of the Map.
    236     typedef MapConstValueSet<VectorMap> ConstValueSet;
    237 
    238     /// ConstValueSet getter function.
    239     ConstValueSet valueSet() const {
    240       return ConstValueSet(*this);
    241     }
    242 
    243     /// The ValueSet of the Map.
    244     typedef MapValueSet<VectorMap> ValueSet;
    245 
    246     /// ValueSet getter function.
    247     ValueSet valueSet() {
    248       return ValueSet(*this);
    249     }
    250 
    251 
    252211  private:
    253212               
    254213    Container container;
    255 
     214    const Graph *graph;
     215
     216  };
     217
     218
     219  template <typename _Base>
     220  class VectorMappableGraphExtender : public _Base {
    256221  public:
    257     // STL  compatibility typedefs.
    258     typedef Iterator iterator;
    259     typedef ConstIterator const_iterator;
    260     typedef typename Iterator::PairValueType value_type;
    261     typedef typename Iterator::KeyType key_type;
    262     typedef typename Iterator::ValueType data_type;
    263     typedef typename Iterator::PairReferenceType reference;
    264     typedef typename Iterator::PairPointerType pointer;
    265     typedef typename ConstIterator::PairReferenceType const_reference;
    266     typedef typename ConstIterator::PairPointerType const_pointer;
    267     typedef int difference_type;               
     222
     223    typedef VectorMappableGraphExtender<_Base> Graph;
     224    typedef _Base Parent;
     225
     226    typedef typename Parent::Node Node;
     227    typedef typename Parent::NodeIt NodeIt;
     228    typedef typename Parent::NodeIdMap NodeIdMap;
     229    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
     230
     231    typedef typename Parent::Edge Edge;
     232    typedef typename Parent::EdgeIt EdgeIt;
     233    typedef typename Parent::EdgeIdMap EdgeIdMap;
     234    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
     235
     236   
     237
     238    template <typename _Value>
     239    class NodeMap : public VectorMap<Graph, Node, NodeIdMap, _Value> {
     240    public:
     241      typedef VectorMappableGraphExtender<_Base> Graph;
     242
     243      typedef typename Graph::Node Node;
     244      typedef typename Graph::NodeIdMap NodeIdMap;
     245
     246      typedef VectorMap<Graph, Node, NodeIdMap, _Value> Parent;
     247
     248      typedef typename Parent::Graph Graph;
     249      typedef typename Parent::Value Value;
     250
     251      NodeMap(const Graph& g)
     252        : Parent(g, g.getNodeObserverRegistry()) {}
     253      NodeMap(const Graph& g, const Value& v)
     254        : Parent(g, g.getNodeObserverRegistry(), v) {}
     255
     256    };
     257
     258    template <typename _Value>
     259    class EdgeMap : public VectorMap<Graph, Edge, EdgeIdMap, _Value> {
     260    public:
     261      typedef VectorMappableGraphExtender<_Base> Graph;
     262
     263      typedef typename Graph::Edge Edge;
     264      typedef typename Graph::EdgeIdMap EdgeIdMap;
     265
     266      typedef VectorMap<Graph, Edge, EdgeIdMap, _Value> Parent;
     267
     268      typedef typename Parent::Graph Graph;
     269      typedef typename Parent::Value Value;
     270
     271      EdgeMap(const Graph& g)
     272        : Parent(g, g.getEdgeObserverRegistry()) {}
     273      EdgeMap(const Graph& g, const Value& v)
     274        : Parent(g, g.getEdgeObserverRegistry(), v) {}
     275
     276    };
     277   
    268278  };
    269279 
Note: See TracChangeset for help on using the changeset viewer.