src/lemon/map_utils.h
author athos
Wed, 23 Mar 2005 11:51:40 +0000
changeset 1247 60708e1475ae
parent 1237 2414b5ab7684
child 1267 a93f94dbe3d3
permissions -rw-r--r--
Completions.
     1 /* -*- C++ -*-
     2  * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Combinatorial Optimization Research Group, 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 
    18 ///\ingroup mutils
    19 ///\file
    20 ///\brief Map utilities.
    21 
    22 #ifndef LEMON_MAP_UTILS_H
    23 #define LEMON_MAP_UTILS_H
    24 
    25 #include <map>
    26 #include <vector>
    27 
    28 namespace lemon {
    29 
    30   /// \addtogroup mutils
    31   /// @{
    32 
    33   /// \brief General inversable map type.
    34 
    35   /// This type provides simple inversable map functions. 
    36   /// The InversableMap wraps an arbitrary ReadWriteMap 
    37   /// and if a key is setted to a new value then store it
    38   /// in the inverse map.
    39   /// \param _Graph The graph type.
    40   /// \param _Map The map to extend with inversable functionality. 
    41   template <
    42     typename _Graph, 
    43     typename _Map
    44   >
    45   class InversableMap : protected _Map {
    46 
    47   public:
    48     typedef _Graph Graph;
    49 
    50     typedef _Map Map;
    51     /// The key type of InversableMap (Node, Edge, UndirEdge).
    52     typedef typename _Map::Key Key;
    53     /// The value type of the InversableMap.
    54     typedef typename _Map::Value Value;
    55     typedef std::map<Value, Key> InverseMap;
    56     
    57     typedef typename _Map::ConstReference ConstReference;
    58 
    59     /// \brief Constructor.
    60     ///
    61     /// Construct a new InversableMap for the graph.
    62     ///
    63     InversableMap(const Graph& graph) : Map(graph) {} 
    64     
    65     /// \brief The setter function of the map.
    66     ///
    67     /// It sets the map and the inverse map to given key-value pair.
    68     void set(const Key& key, const Value& val) {
    69       Value oldval = Map::operator[](key);
    70       typename InverseMap::iterator it = invMap.find(oldval);
    71       if (it != invMap.end() && it->second == key) {
    72 	invMap.erase(it);
    73       }      
    74       invMap.insert(make_pair(val, key));
    75       Map::set(key, val);
    76     }
    77 
    78     /// \brief The getter function of the map.
    79     ///
    80     /// It gives back the value associated with the key.
    81     ConstReference operator[](const Key& key) const {
    82       return Map::operator[](key);
    83     }
    84 
    85     /// \brief Add a new key to the map.
    86     ///
    87     /// Add a new key to the map. It is called by the
    88     /// \c AlterationNotifier.
    89     virtual void add(const Key& key) {
    90       Map::add(key);
    91     }
    92 
    93     /// \brief Erase the key from the map.
    94     ///
    95     /// Erase the key to the map. It is called by the
    96     /// \c AlterationNotifier.
    97     virtual void erase(const Key& key) {
    98       Value val = Map::operator[](key);
    99       typename InverseMap::iterator it = invMap.find(val);
   100       if (it != invMap.end() && it->second == key) {
   101 	invMap.erase(it);
   102       }
   103       Map::erase(key);
   104     }
   105 
   106     /// \brief Clear the keys from the map and inverse map.
   107     ///
   108     /// Clear the keys from the map and inverse map. It is called by the
   109     /// \c AlterationNotifier.
   110     virtual void clear() {
   111       invMap.clear();
   112       Map::clear();
   113     }
   114 
   115     /// \brief It gives back the just readeable inverse map.
   116     ///
   117     /// It gives back the just readeable inverse map.
   118     const InverseMap& inverse() const {
   119       return invMap;
   120     } 
   121 
   122 
   123   private:
   124     InverseMap invMap;    
   125   };
   126 
   127 
   128   
   129   /// \brief Provides a mutable, continous and unique descriptor for each 
   130   /// item in the graph.
   131   ///
   132   /// The DescriptorMap class provides a mutable, continous and immutable
   133   /// mapping for each item in the graph.
   134   ///
   135   /// \param _Graph The graph class the \c DescriptorMap belongs to.
   136   /// \param _Item The Item is the Key of the Map. It may be Node, Edge or 
   137   /// UndirEdge.
   138   /// \param _Map A ReadWriteMap mapping from the item type to integer.
   139 
   140   template <
   141     typename _Graph,   
   142     typename _Item,
   143     typename _Map
   144   >
   145   class DescriptorMap : protected _Map {
   146 
   147     typedef _Item Item;
   148     typedef _Map Map;
   149 
   150   public:
   151     /// The graph class of DescriptorMap.
   152     typedef _Graph Graph;
   153 
   154     /// The key type of DescriptorMap (Node, Edge, UndirEdge).
   155     typedef typename _Map::Key Key;
   156     /// The value type of DescriptorMap.
   157     typedef typename _Map::Value Value;
   158 
   159     typedef std::vector<Item> InverseMap;
   160 
   161     /// \brief Constructor.
   162     ///
   163     /// Constructor for creating descriptor map.
   164     DescriptorMap(const Graph& _graph) : Map(_graph) {
   165       build();
   166     }
   167 
   168     /// \brief Add a new key to the map.
   169     ///
   170     /// Add a new key to the map. It is called by the
   171     /// \c AlterationNotifier.
   172     virtual void add(const Item& item) {
   173       Map::add(item);
   174       Map::set(item, invMap.size());
   175       invMap.push_back(item);
   176     }
   177 
   178     /// \brief Erase the key from the map.
   179     ///
   180     /// Erase the key to the map. It is called by the
   181     /// \c AlterationNotifier.
   182     virtual void erase(const Item& item) {
   183       Map::set(invMap.back(), Map::operator[](item));
   184       invMap[Map::operator[](item)] = invMap.back();
   185       Map::erase(item);
   186     }
   187 
   188     /// \brief Build the unique map.
   189     ///
   190     /// Build the unique map. It is called by the
   191     /// \c AlterationNotifier.
   192     virtual void build() {
   193       Map::build();
   194       Item it;
   195       const Graph* graph = Map::getGraph(); 
   196       for (graph->first(it); it != INVALID; graph->next(it)) {
   197 	Map::set(it, invMap.size());
   198 	invMap.push_back(it);	
   199       }      
   200     }
   201     
   202     /// \brief Clear the keys from the map.
   203     ///
   204     /// Clear the keys from the map. It is called by the
   205     /// \c AlterationNotifier.
   206     virtual void clear() {
   207       invMap.clear();
   208       Map::clear();
   209     }
   210 
   211     /// \brief Gives back the \e descriptor of the item.
   212     ///
   213     /// Gives back the mutable and unique \e descriptor of the map.
   214     int operator[](const Item& item) const {
   215       return Map::operator[](item);
   216     }
   217     
   218     /// \brief Gives back the inverse of the map.
   219     ///
   220     /// Gives back the inverse of the map.
   221     const InverseMap inverse() const {
   222       return invMap;
   223     }
   224 
   225   private:
   226     std::vector<Item> invMap;
   227   };
   228   
   229   /// Provides an immutable and unique id for each item in the graph.
   230 
   231   /// The IdMap class provides an unique and immutable mapping for each item
   232   /// in the graph.
   233   ///
   234   template <typename _Graph, typename _Item>
   235   class IdMap {
   236   public:
   237     typedef _Graph Graph;
   238     typedef int Value;
   239     typedef _Item Item;
   240 
   241     /// \brief The class represents the inverse of the map.
   242     ///
   243     /// The class represents the inverse of the map.
   244     /// \see inverse()
   245     class InverseMap {
   246     public:
   247       /// \brief Constructor.
   248       ///
   249       /// Constructor for creating an id-to-item map.
   250       InverseMap(const Graph& _graph) : graph(&_graph) {}
   251       /// \brief Gives back the given item from its id.
   252       ///
   253       /// Gives back the given item from its id.
   254       /// 
   255       Item operator[](int id) const { return graph->fromId(id, Item());}
   256     private:
   257       const Graph* graph;
   258     };
   259 
   260     /// \brief Constructor.
   261     ///
   262     /// Constructor for creating id map.
   263     IdMap(const Graph& _graph) : graph(&_graph) {}
   264 
   265     /// \brief Gives back the \e id of the item.
   266     ///
   267     /// Gives back the immutable and unique \e id of the map.
   268     int operator[](const Item& item) const { return graph->id(item);}
   269 
   270     /// \brief Gives back the inverse of the map.
   271     ///
   272     /// Gives back the inverse of the map.
   273     InverseMap inverse() const { return InverseMap(*graph);} 
   274 
   275   private:
   276     const Graph* graph;
   277 
   278   };
   279 
   280 }
   281 
   282 #endif