Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/bits/vector_map.h
changeset 2023 f34f044a043c
parent 1996 5dc13b93f8b4
child 2031 080d51024ac5
equal deleted inserted replaced
13:3b8c4da1f1bd 14:e71478d66dc2 
    14  * express or implied, and with no claim as to its suitability for any
 
    14  * express or implied, and with no claim as to its suitability for any
 
    15  * purpose.
 
    15  * purpose.
 
    16  *
 
    16  *
 
    17  */
 
    17  */
 
    18 
    18 
    19 #ifndef LEMON_VECTOR_MAP_H
 
    19 #ifndef LEMON_BITS_VECTOR_MAP_H
 
    20 #define LEMON_VECTOR_MAP_H
 
    20 #define LEMON_BITS_VECTOR_MAP_H
 
    21 
    21 
    22 #include <vector>
 
    22 #include <vector>
 
    23 #include <algorithm>
 
    23 #include <algorithm>
 
    24 
    24 
       
    25 #include <lemon/bits/traits.h>
 
    25 #include <lemon/bits/utility.h>
 
    26 #include <lemon/bits/utility.h>
 
    26 #include <lemon/bits/map_extender.h>
 
    27 
    27 #include <lemon/bits/alteration_notifier.h>
 
    28 #include <lemon/bits/alteration_notifier.h>
 
    28 #include <lemon/concept_check.h>
 
    29 
    29 #include <lemon/concept/maps.h>
 
    30 ///\ingroup graphbits
 
    30 
       
    31 /// \ingroup graphbits
 
       
    32 ///
 
    31 ///
 
    33 ///\file
 
    32 ///\file
 
    34 ///\brief Vector based graph maps.
 
    33 ///\brief Vector based graph maps.
 
    35 
       
    36 namespace lemon {
 
    34 namespace lemon {
 
    37 
    35 
    38   /// \ingroup graphbits
 
    36   /// \ingroup graphbits
 
    39   ///
 
    37   ///
 
    40   /// \brief Graph map based on the std::vector storage.
 
    38   /// \brief Graph map based on the std::vector storage.
 
    41   ///
 
    39   ///
 
    42   /// The VectorMap template class is graph map structure what
 
    40   /// The VectorMap template class is graph map structure what
 
    43   /// automatically indates the map when a key is added to or erased from
 
    41   /// automatically updates the map when a key is added to or erased from
 
    44   /// the map. This map factory uses the allocators to implement 
    42   /// the map. This map factory uses the allocators to implement 
    45   /// the container functionality. This map factory
 
    43   /// the container functionality. This map factory
 
    46   /// uses the std::vector to implement the container function.
 
    44   /// uses the std::vector to implement the container function.
 
    47   ///
 
    45   ///
 
    48   /// \param Registry The AlterationNotifier that will notify this map.
 
    46   /// \param Notifier The AlterationNotifier that will notify this map.
 
    49   /// \param Item The item type of the graph items.
 
    47   /// \param Item The item type of the graph items.
 
    50   /// \param Value The value type of the map.
 
    48   /// \param Value The value type of the map.
 
    51   /// 
    49   /// 
    52   /// \author Balazs Dezso
 
    50   /// \author Balazs Dezso  	
    53   	
    51   template <typename _Graph, typename _Item, typename _Value>
 
    54   template <
 
    52   class VectorMap 
    55     typename _Graph, 
    53     : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
 
    56     typename _Item,    
       
    57     typename _Value
 
       
    58     >
 
       
    59   class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
 
       
    60   private:
 
    54   private:
 
    61 		
    55 		
    62     /// The container type of the map.
 
    56     /// The container type of the map.
 
    63     typedef std::vector<_Value> Container;	
    57     typedef std::vector<_Value> Container;	
    64 
    58 
    65   public:
 
    59   public:
 
    66 
    60 
    67     /// The graph type of the map. 
    61     /// The graph type of the map. 
    68     typedef _Graph Graph;
 
    62     typedef _Graph Graph;
 
       
    63     /// The item type of the map.
 
       
    64     typedef _Item Item;
 
    69     /// The reference map tag.
 
    65     /// The reference map tag.
 
    70     typedef True ReferenceMapTag;
 
    66     typedef True ReferenceMapTag;
 
    71 
    67 
    72     /// The key type of the map.
 
    68     /// The key type of the map.
 
    73     typedef _Item Key;
 
    69     typedef _Item Key;
 
    74     /// The value type of the map.
 
    70     /// The value type of the map.
 
    75     typedef _Value Value;
 
    71     typedef _Value Value;
 
    76 
    72 
    77     typedef AlterationNotifier<_Item> Registry;
 
    73     /// The notifier type.
 
       
    74     typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
 
    78 
    75 
    79     /// The map type.
 
    76     /// The map type.
 
    80     typedef VectorMap Map;
 
    77     typedef VectorMap Map;
 
    81     /// The base class of the map.
 
    78     /// The base class of the map.
 
    82     typedef typename Registry::ObserverBase Parent;
 
    79     typedef typename Notifier::ObserverBase Parent;
 
    83 
    80 
    84     /// The reference type of the map;
 
    81     /// The reference type of the map;
 
    85     typedef typename Container::reference Reference;
 
    82     typedef typename Container::reference Reference;
 
    86     /// The pointer type of the map;
 
       
    87     typedef typename Container::pointer Pointer;
 
       
    88 
       
    89     /// The const value type of the map.
 
       
    90     typedef const Value ConstValue;
 
       
    91     /// The const reference type of the map;
 
    83     /// The const reference type of the map;
 
    92     typedef typename Container::const_reference ConstReference;
 
    84     typedef typename Container::const_reference ConstReference;
 
    93     /// The pointer type of the map;
 
    85 
    94     typedef typename Container::const_pointer ConstPointer;
 
    86 
    95 
    87     /// \brief Constructor to attach the new map into the notifier.
 
    96 
    88     ///
 
    97     /// \brief Constructor to attach the new map into the registry.
 
    89     /// It constructs a map and attachs it into the notifier.
 
    98     ///
 
       
    99     /// It constructs a map and attachs it into the registry.
 
       
   100     /// It adds all the items of the graph to the map.
 
    90     /// It adds all the items of the graph to the map.
 
   101     VectorMap(const Graph& _g) : graph(&_g) {
 
    91     VectorMap(const Graph& graph) {
 
   102       attach(_g.getNotifier(_Item()));
 
    92       Parent::attach(graph.getNotifier(Item()));
 
   103       build();
 
    93       container.resize(Parent::getNotifier()->maxId() + 1);
 
   104     }
 
    94     }
 
   105 
    95 
   106     /// \brief Constructor uses given value to initialize the map. 
    96     /// \brief Constructor uses given value to initialize the map. 
   107     ///
 
    97     ///
 
   108     /// It constructs a map uses a given value to initialize the map. 
    98     /// It constructs a map uses a given value to initialize the map. 
   109     /// It adds all the items of the graph to the map.
 
    99     /// It adds all the items of the graph to the map.
 
   110     VectorMap(const Graph& _g, const Value& _v) : graph(&_g) { 
   100     VectorMap(const Graph& graph, const Value& value) {
 
   111       attach(_g.getNotifier(_Item()));
 
   101       Parent::attach(graph.getNotifier(Item()));
 
   112       container.resize(graph->maxId(_Item()) + 1, _v);
 
   102       container.resize(Parent::getNotifier()->maxId() + 1, value);
 
   113     }
 
   103     }
 
   114 
   104 
   115     /// \brief Copy constructor
 
   105     /// \brief Copy constructor
 
   116     ///
 
   106     ///
 
   117     /// Copy constructor.
 
   107     /// Copy constructor.
 
   118     VectorMap(const VectorMap& _copy) 
   108     VectorMap(const VectorMap& _copy) : Parent() {
 
   119       : Parent(), graph(_copy.getGraph()) {
 
       
   120       if (_copy.attached()) {
 
   109       if (_copy.attached()) {
 
   121 	attach(*_copy.getRegistry());
 
   110 	Parent::attach(*_copy.getNotifier());
 
   122 	container = _copy.container;
 
   111 	container = _copy.container;
 
   123       }
 
   112       }
 
   124     }
 
   113     }
 
   125 
   114 
   126     /// \brief Destrcutor
 
       
   127     ///
 
       
   128     /// Destructor.
 
       
   129     virtual ~VectorMap() {
 
       
   130       if (attached()) {
 
       
   131 	detach();
 
       
   132       }
 
       
   133     }
 
       
   134 
       
   135 
       
   136   private:
 
   115   private:
 
   137 
   116 
   138     VectorMap& operator=(const VectorMap&);
 
   117     VectorMap& operator=(const VectorMap&);
 
   139 
       
   140   protected:
 
       
   141 
       
   142     using Parent::attach;
 
       
   143     using Parent::detach;
 
       
   144     using Parent::attached;
 
       
   145 
       
   146     const Graph* getGraph() const {
 
       
   147       return graph;
 
       
   148     }
 
       
   149 
   118 
   150   public:
 
   119   public:
 
   151 
   120 
   152     /// \brief The subcript operator.
 
   121     /// \brief The subcript operator.
 
   153     ///
 
   122     ///
 
   154     /// The subscript operator. The map can be subscripted by the
 
   123     /// The subscript operator. The map can be subscripted by the
 
   155     /// actual items of the graph.      
   124     /// actual items of the graph.      
   156     Reference operator[](const Key& key) {
 
   125     Reference operator[](const Key& key) {
 
   157       return container[graph->id(key)];
 
   126       return container[Parent::getNotifier()->id(key)];
 
   158     } 
   127     } 
   159 		
   128 		
   160     /// \brief The const subcript operator.
 
   129     /// \brief The const subcript operator.
 
   161     ///
 
   130     ///
 
   162     /// The const subscript operator. The map can be subscripted by the
 
   131     /// The const subscript operator. The map can be subscripted by the
 
   163     /// actual items of the graph. 
   132     /// actual items of the graph. 
   164     ConstReference operator[](const Key& key) const {
 
   133     ConstReference operator[](const Key& key) const {
 
   165       return container[graph->id(key)];
 
   134       return container[Parent::getNotifier()->id(key)];
 
   166     }
 
   135     }
 
   167 
   136 
   168 
   137 
   169     /// \brief The setter function of the map.
 
   138     /// \brief The setter function of the map.
 
   170     ///
 
   139     ///
 
   175 
   144 
   176   protected:
 
   145   protected:
 
   177 
   146 
   178     /// \brief Adds a new key to the map.
 
   147     /// \brief Adds a new key to the map.
 
   179     ///		
   148     ///		
   180     /// It adds a new key to the map. It called by the observer registry
 
   149     /// It adds a new key to the map. It called by the observer notifier
 
   181     /// and it overrides the add() member function of the observer base.     
   150     /// and it overrides the add() member function of the observer base.     
   182     virtual void add(const Key& key) {
 
   151     virtual void add(const Key& key) {
 
   183       int id = graph->id(key);
 
   152       int id = Parent::getNotifier()->id(key);
 
   184       if (id >= (int)container.size()) {
 
   153       if (id >= (int)container.size()) {
 
   185 	container.resize(id + 1);
 
   154 	container.resize(id + 1);
 
   186       }
 
   155       }
 
   187     }
 
   156     }
 
   188 
   157 
   189     /// \brief Adds more new keys to the map.
 
   158     /// \brief Adds more new keys to the map.
 
   190     ///		
   159     ///		
   191     /// It adds more new keys to the map. It called by the observer registry
 
   160     /// It adds more new keys to the map. It called by the observer notifier
 
   192     /// and it overrides the add() member function of the observer base.     
   161     /// and it overrides the add() member function of the observer base.     
   193     virtual void add(const std::vector<Key>& keys) {
 
   162     virtual void add(const std::vector<Key>& keys) {
 
       
   163       int max = container.size() - 1;
 
   194       for (int i = 0; i < (int)keys.size(); ++i) {
 
   164       for (int i = 0; i < (int)keys.size(); ++i) {
 
   195 	add(keys[i]);
 
   165         int id = Parent::getNotifier()->id(keys[i]);
 
   196       }
 
   166         if (id >= max) {
 
       
   167           max = id;
 
       
   168         }
 
       
   169       }
 
       
   170       container.resize(max + 1);
 
   197     }
 
   171     }
 
   198 
   172 
   199     /// \brief Erase a key from the map.
 
   173     /// \brief Erase a key from the map.
 
   200     ///
 
   174     ///
 
   201     /// Erase a key from the map. It called by the observer registry
 
   175     /// Erase a key from the map. It called by the observer notifier
 
   202     /// and it overrides the erase() member function of the observer base.     
   176     /// and it overrides the erase() member function of the observer base.     
   203     virtual void erase(const Key&) {}
 
   177     virtual void erase(const Key& key) {
 
       
   178       container[Parent::getNotifier()->id(key)] = Value();
 
       
   179     }
 
   204 
   180 
   205     /// \brief Erase more keys from the map.
 
   181     /// \brief Erase more keys from the map.
 
   206     ///
 
   182     ///
 
   207     /// Erase more keys from the map. It called by the observer registry
 
   183     /// Erase more keys from the map. It called by the observer notifier
 
   208     /// and it overrides the erase() member function of the observer base.     
   184     /// and it overrides the erase() member function of the observer base.     
   209     virtual void erase(const std::vector<Key>&) {}
 
   185     virtual void erase(const std::vector<Key>& keys) {
 
       
   186       for (int i = 0; i < (int)keys.size(); ++i) {
 
       
   187 	container[Parent::getNotifier()->id(keys[i])] = Value();
 
       
   188       }
 
       
   189     }
 
   210     
   190     
   211     /// \brief Buildes the map.
 
   191     /// \brief Buildes the map.
 
   212     ///	
   192     ///	
   213     /// It buildes the map. It called by the observer registry
 
   193     /// It buildes the map. It called by the observer notifier
 
   214     /// and it overrides the build() member function of the observer base.
 
   194     /// and it overrides the build() member function of the observer base.
 
   215     virtual void build() { 
   195     virtual void build() { 
   216       container.resize(graph->maxId(_Item()) + 1);
 
   196       int size = Parent::getNotifier()->maxId() + 1;
 
       
   197       container.reserve(size);
 
       
   198       container.resize(size);
 
   217     }
 
   199     }
 
   218 
   200 
   219     /// \brief Clear the map.
 
   201     /// \brief Clear the map.
 
   220     ///
 
   202     ///
 
   221     /// It erase all items from the map. It called by the observer registry
 
   203     /// It erase all items from the map. It called by the observer notifier
 
   222     /// and it overrides the clear() member function of the observer base.     
   204     /// and it overrides the clear() member function of the observer base.     
   223     virtual void clear() { 
   205     virtual void clear() { 
   224       container.clear();
 
   206       container.clear();
 
   225     }
 
   207     }
 
   226     
   208     
   227   private:
 
   209   private:
 
   228 		
   210 		
   229     Container container;
 
   211     Container container;
 
   230     const Graph *graph;
 
       
   231 
   212 
   232   };
 
   213   };
 
   233 
   214 
   234 }
 
   215 }
 
   235 
   216
lemon-0.x