lemon/bits/vector_map.h
author deba
Fri, 04 Nov 2005 19:19:52 +0000
changeset 1778 4ba7965386fb
parent 1719 674182524bd9
child 1810 474d093466a5
permissions -rw-r--r--
Some just writeable bool maps.
     1 /* -*- C++ -*-
     2  * lemon/vector_map.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_VECTOR_MAP_H
    18 #define LEMON_VECTOR_MAP_H
    19 
    20 #include <vector>
    21 #include <algorithm>
    22 
    23 #include <lemon/utility.h>
    24 #include <lemon/bits/map_iterator.h>
    25 #include <lemon/bits/alteration_notifier.h>
    26 #include <lemon/concept_check.h>
    27 #include <lemon/concept/maps.h>
    28 
    29 /// \ingroup graphmapfactory
    30 ///
    31 ///\file
    32 ///\brief Vector based graph maps.
    33 
    34 namespace lemon {
    35 
    36   /// \ingroup graphmapfactory
    37   ///
    38   /// \brief Graph map based on the std::vector storage.
    39   ///
    40   /// The VectorMap template class is graph map structure what
    41   /// automatically updates the map when a key is added to or erased from
    42   /// the map. This map factory uses the allocators to implement 
    43   /// the container functionality. This map factory
    44   /// uses the std::vector to implement the container function.
    45   ///
    46   /// \param Registry The AlterationNotifier that will notify this map.
    47   /// \param Item The item type of the graph items.
    48   /// \param Value The value type of the map.
    49   /// 
    50   /// \author Balazs Dezso
    51   	
    52   template <
    53     typename _Graph, 
    54     typename _Item,    
    55     typename _Value
    56     >
    57   class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
    58   private:
    59 		
    60     /// The container type of the map.
    61     typedef std::vector<_Value> Container;	
    62 
    63   public:
    64 
    65     /// The graph type of the map. 
    66     typedef _Graph Graph;
    67     /// The reference map tag.
    68     typedef True ReferenceMapTag;
    69 
    70     /// The key type of the map.
    71     typedef _Item Key;
    72     /// The value type of the map.
    73     typedef _Value Value;
    74 
    75     typedef AlterationNotifier<_Item> Registry;
    76 
    77     /// The map type.
    78     typedef VectorMap Map;
    79     /// The base class of the map.
    80     typedef typename Registry::ObserverBase Parent;
    81 
    82     /// The reference type of the map;
    83     typedef typename Container::reference Reference;
    84     /// The pointer type of the map;
    85     typedef typename Container::pointer Pointer;
    86 
    87     /// The const value type of the map.
    88     typedef const Value ConstValue;
    89     /// The const reference type of the map;
    90     typedef typename Container::const_reference ConstReference;
    91     /// The pointer type of the map;
    92     typedef typename Container::const_pointer ConstPointer;
    93 
    94 
    95     /// \brief Constructor to attach the new map into the registry.
    96     ///
    97     /// It constructs a map and attachs it into the registry.
    98     /// It adds all the items of the graph to the map.
    99     VectorMap(const Graph& _g) : graph(&_g) {
   100       attach(_g.getNotifier(_Item()));
   101       build();
   102     }
   103 
   104     /// \brief Constructor uses given value to initialize the map. 
   105     ///
   106     /// It constructs a map uses a given value to initialize the map. 
   107     /// It adds all the items of the graph to the map.
   108     VectorMap(const Graph& _g, const Value& _v) : graph(&_g) { 
   109       attach(_g.getNotifier(_Item()));
   110       container.resize(graph->maxId(_Item()) + 1, _v);
   111     }
   112 
   113     /// \brief Copy constructor
   114     ///
   115     /// Copy constructor.
   116     VectorMap(const VectorMap& _copy) 
   117       : Parent(), graph(_copy.getGraph()) {
   118       if (_copy.attached()) {
   119 	attach(*_copy.getRegistry());
   120 	container = _copy.container;
   121       }
   122     }
   123 
   124     /// \brief Destrcutor
   125     ///
   126     /// Destructor.
   127     virtual ~VectorMap() {
   128       if (attached()) {
   129 	detach();
   130       }
   131     }
   132 
   133 
   134   private:
   135 
   136     VectorMap& operator=(const VectorMap&);
   137 
   138   protected:
   139 
   140     using Parent::attach;
   141     using Parent::detach;
   142     using Parent::attached;
   143 
   144     const Graph* getGraph() const {
   145       return graph;
   146     }
   147 
   148   public:
   149 
   150     /// \brief The subcript operator.
   151     ///
   152     /// The subscript operator. The map can be subscripted by the
   153     /// actual items of the graph.      
   154     Reference operator[](const Key& key) {
   155       return container[graph->id(key)];
   156     } 
   157 		
   158     /// \brief The const subcript operator.
   159     ///
   160     /// The const subscript operator. The map can be subscripted by the
   161     /// actual items of the graph. 
   162     ConstReference operator[](const Key& key) const {
   163       return container[graph->id(key)];
   164     }
   165 
   166 
   167     /// \brief The setter function of the map.
   168     ///
   169     /// It the same as operator[](key) = value expression.
   170     void set(const Key& key, const Value& value) {
   171       (*this)[key] = value;
   172     }
   173 
   174   protected:
   175 
   176     /// \brief Adds a new key to the map.
   177     ///		
   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     virtual void add(const Key& key) {
   181       int id = graph->id(key);
   182       if (id >= (int)container.size()) {
   183 	container.resize(id + 1);
   184       }
   185     }
   186 
   187     /// \brief Erase a key from the map.
   188     ///
   189     /// Erase a key from the map. It called by the observer registry
   190     /// and it overrides the erase() member function of the observer base.     
   191     virtual void erase(const Key&) {}
   192 
   193     /// \brief Buildes the map.
   194     ///	
   195     /// It buildes the map. It called by the observer registry
   196     /// and it overrides the build() member function of the observer base.
   197     virtual void build() { 
   198       container.resize(graph->maxId(_Item()) + 1);
   199     }
   200 
   201     /// \brief Clear the map.
   202     ///
   203     /// It erase all items from the map. It called by the observer registry
   204     /// and it overrides the clear() member function of the observer base.     
   205     virtual void clear() { 
   206       container.clear();
   207     }
   208     
   209   private:
   210 		
   211     Container container;
   212     const Graph *graph;
   213 
   214   };
   215 
   216 }
   217 
   218 #endif