Remove InverseMap and DescriptorMap 1.0
authorAlpar Juttner <alpar@cs.elte.hu>
Wed, 08 Oct 2008 12:25:57 +0100
branch1.0
changeset 324fafece417795
parent 323 bfed14fbfdc5
child 326 de38fca76780
Remove InverseMap and DescriptorMap
lemon/maps.h
test/graph_utils_test.cc
     1.1 --- a/lemon/maps.h	Wed Oct 08 10:33:42 2008 +0100
     1.2 +++ b/lemon/maps.h	Wed Oct 08 12:25:57 2008 +0100
     1.3 @@ -1847,411 +1847,6 @@
     1.4  
     1.5    };
     1.6  
     1.7 -
     1.8 -  /// \brief General invertable graph-map type.
     1.9 -
    1.10 -  /// This type provides simple invertable graph-maps.
    1.11 -  /// The InvertableMap wraps an arbitrary ReadWriteMap
    1.12 -  /// and if a key is set to a new value then store it
    1.13 -  /// in the inverse map.
    1.14 -  ///
    1.15 -  /// The values of the map can be accessed
    1.16 -  /// with stl compatible forward iterator.
    1.17 -  ///
    1.18 -  /// \tparam _Graph The graph type.
    1.19 -  /// \tparam _Item The item type of the graph.
    1.20 -  /// \tparam _Value The value type of the map.
    1.21 -  ///
    1.22 -  /// \see IterableValueMap
    1.23 -  template <typename _Graph, typename _Item, typename _Value>
    1.24 -  class InvertableMap
    1.25 -    : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
    1.26 -  private:
    1.27 -
    1.28 -    typedef typename ItemSetTraits<_Graph, _Item>::
    1.29 -    template Map<_Value>::Type Map;
    1.30 -    typedef _Graph Graph;
    1.31 -
    1.32 -    typedef std::map<_Value, _Item> Container;
    1.33 -    Container _inv_map;
    1.34 -
    1.35 -  public:
    1.36 -
    1.37 -    /// The key type of InvertableMap (Node, Arc, Edge).
    1.38 -    typedef typename Map::Key Key;
    1.39 -    /// The value type of the InvertableMap.
    1.40 -    typedef typename Map::Value Value;
    1.41 -
    1.42 -
    1.43 -
    1.44 -    /// \brief Constructor.
    1.45 -    ///
    1.46 -    /// Construct a new InvertableMap for the graph.
    1.47 -    ///
    1.48 -    explicit InvertableMap(const Graph& graph) : Map(graph) {}
    1.49 -
    1.50 -    /// \brief Forward iterator for values.
    1.51 -    ///
    1.52 -    /// This iterator is an stl compatible forward
    1.53 -    /// iterator on the values of the map. The values can
    1.54 -    /// be accessed in the [beginValue, endValue) range.
    1.55 -    ///
    1.56 -    class ValueIterator
    1.57 -      : public std::iterator<std::forward_iterator_tag, Value> {
    1.58 -      friend class InvertableMap;
    1.59 -    private:
    1.60 -      ValueIterator(typename Container::const_iterator _it)
    1.61 -        : it(_it) {}
    1.62 -    public:
    1.63 -
    1.64 -      ValueIterator() {}
    1.65 -
    1.66 -      ValueIterator& operator++() { ++it; return *this; }
    1.67 -      ValueIterator operator++(int) {
    1.68 -        ValueIterator tmp(*this);
    1.69 -        operator++();
    1.70 -        return tmp;
    1.71 -      }
    1.72 -
    1.73 -      const Value& operator*() const { return it->first; }
    1.74 -      const Value* operator->() const { return &(it->first); }
    1.75 -
    1.76 -      bool operator==(ValueIterator jt) const { return it == jt.it; }
    1.77 -      bool operator!=(ValueIterator jt) const { return it != jt.it; }
    1.78 -
    1.79 -    private:
    1.80 -      typename Container::const_iterator it;
    1.81 -    };
    1.82 -
    1.83 -    /// \brief Returns an iterator to the first value.
    1.84 -    ///
    1.85 -    /// Returns an stl compatible iterator to the
    1.86 -    /// first value of the map. The values of the
    1.87 -    /// map can be accessed in the [beginValue, endValue)
    1.88 -    /// range.
    1.89 -    ValueIterator beginValue() const {
    1.90 -      return ValueIterator(_inv_map.begin());
    1.91 -    }
    1.92 -
    1.93 -    /// \brief Returns an iterator after the last value.
    1.94 -    ///
    1.95 -    /// Returns an stl compatible iterator after the
    1.96 -    /// last value of the map. The values of the
    1.97 -    /// map can be accessed in the [beginValue, endValue)
    1.98 -    /// range.
    1.99 -    ValueIterator endValue() const {
   1.100 -      return ValueIterator(_inv_map.end());
   1.101 -    }
   1.102 -
   1.103 -    /// \brief The setter function of the map.
   1.104 -    ///
   1.105 -    /// Sets the mapped value.
   1.106 -    void set(const Key& key, const Value& val) {
   1.107 -      Value oldval = Map::operator[](key);
   1.108 -      typename Container::iterator it = _inv_map.find(oldval);
   1.109 -      if (it != _inv_map.end() && it->second == key) {
   1.110 -        _inv_map.erase(it);
   1.111 -      }
   1.112 -      _inv_map.insert(make_pair(val, key));
   1.113 -      Map::set(key, val);
   1.114 -    }
   1.115 -
   1.116 -    /// \brief The getter function of the map.
   1.117 -    ///
   1.118 -    /// It gives back the value associated with the key.
   1.119 -    typename MapTraits<Map>::ConstReturnValue
   1.120 -    operator[](const Key& key) const {
   1.121 -      return Map::operator[](key);
   1.122 -    }
   1.123 -
   1.124 -    /// \brief Gives back the item by its value.
   1.125 -    ///
   1.126 -    /// Gives back the item by its value.
   1.127 -    Key operator()(const Value& key) const {
   1.128 -      typename Container::const_iterator it = _inv_map.find(key);
   1.129 -      return it != _inv_map.end() ? it->second : INVALID;
   1.130 -    }
   1.131 -
   1.132 -  protected:
   1.133 -
   1.134 -    /// \brief Erase the key from the map.
   1.135 -    ///
   1.136 -    /// Erase the key to the map. It is called by the
   1.137 -    /// \c AlterationNotifier.
   1.138 -    virtual void erase(const Key& key) {
   1.139 -      Value val = Map::operator[](key);
   1.140 -      typename Container::iterator it = _inv_map.find(val);
   1.141 -      if (it != _inv_map.end() && it->second == key) {
   1.142 -        _inv_map.erase(it);
   1.143 -      }
   1.144 -      Map::erase(key);
   1.145 -    }
   1.146 -
   1.147 -    /// \brief Erase more keys from the map.
   1.148 -    ///
   1.149 -    /// Erase more keys from the map. It is called by the
   1.150 -    /// \c AlterationNotifier.
   1.151 -    virtual void erase(const std::vector<Key>& keys) {
   1.152 -      for (int i = 0; i < int(keys.size()); ++i) {
   1.153 -        Value val = Map::operator[](keys[i]);
   1.154 -        typename Container::iterator it = _inv_map.find(val);
   1.155 -        if (it != _inv_map.end() && it->second == keys[i]) {
   1.156 -          _inv_map.erase(it);
   1.157 -        }
   1.158 -      }
   1.159 -      Map::erase(keys);
   1.160 -    }
   1.161 -
   1.162 -    /// \brief Clear the keys from the map and inverse map.
   1.163 -    ///
   1.164 -    /// Clear the keys from the map and inverse map. It is called by the
   1.165 -    /// \c AlterationNotifier.
   1.166 -    virtual void clear() {
   1.167 -      _inv_map.clear();
   1.168 -      Map::clear();
   1.169 -    }
   1.170 -
   1.171 -  public:
   1.172 -
   1.173 -    /// \brief The inverse map type.
   1.174 -    ///
   1.175 -    /// The inverse of this map. The subscript operator of the map
   1.176 -    /// gives back always the item what was last assigned to the value.
   1.177 -    class InverseMap {
   1.178 -    public:
   1.179 -      /// \brief Constructor of the InverseMap.
   1.180 -      ///
   1.181 -      /// Constructor of the InverseMap.
   1.182 -      explicit InverseMap(const InvertableMap& inverted)
   1.183 -        : _inverted(inverted) {}
   1.184 -
   1.185 -      /// The value type of the InverseMap.
   1.186 -      typedef typename InvertableMap::Key Value;
   1.187 -      /// The key type of the InverseMap.
   1.188 -      typedef typename InvertableMap::Value Key;
   1.189 -
   1.190 -      /// \brief Subscript operator.
   1.191 -      ///
   1.192 -      /// Subscript operator. It gives back always the item
   1.193 -      /// what was last assigned to the value.
   1.194 -      Value operator[](const Key& key) const {
   1.195 -        return _inverted(key);
   1.196 -      }
   1.197 -
   1.198 -    private:
   1.199 -      const InvertableMap& _inverted;
   1.200 -    };
   1.201 -
   1.202 -    /// \brief It gives back the just readable inverse map.
   1.203 -    ///
   1.204 -    /// It gives back the just readable inverse map.
   1.205 -    InverseMap inverse() const {
   1.206 -      return InverseMap(*this);
   1.207 -    }
   1.208 -
   1.209 -
   1.210 -
   1.211 -  };
   1.212 -
   1.213 -  /// \brief Provides a mutable, continuous and unique descriptor for each
   1.214 -  /// item in the graph.
   1.215 -  ///
   1.216 -  /// The DescriptorMap class provides a unique and continuous (but mutable)
   1.217 -  /// descriptor (id) for each item of the same type (e.g. node) in the
   1.218 -  /// graph. This id is <ul><li>\b unique: different items (nodes) get
   1.219 -  /// different ids <li>\b continuous: the range of the ids is the set of
   1.220 -  /// integers between 0 and \c n-1, where \c n is the number of the items of
   1.221 -  /// this type (e.g. nodes) (so the id of a node can change if you delete an
   1.222 -  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
   1.223 -  /// with its member class \c InverseMap, or with the \c operator() member.
   1.224 -  ///
   1.225 -  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
   1.226 -  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
   1.227 -  /// Edge.
   1.228 -  template <typename _Graph, typename _Item>
   1.229 -  class DescriptorMap
   1.230 -    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
   1.231 -
   1.232 -    typedef _Item Item;
   1.233 -    typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
   1.234 -
   1.235 -  public:
   1.236 -    /// The graph class of DescriptorMap.
   1.237 -    typedef _Graph Graph;
   1.238 -
   1.239 -    /// The key type of DescriptorMap (Node, Arc, Edge).
   1.240 -    typedef typename Map::Key Key;
   1.241 -    /// The value type of DescriptorMap.
   1.242 -    typedef typename Map::Value Value;
   1.243 -
   1.244 -    /// \brief Constructor.
   1.245 -    ///
   1.246 -    /// Constructor for descriptor map.
   1.247 -    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
   1.248 -      Item it;
   1.249 -      const typename Map::Notifier* nf = Map::notifier();
   1.250 -      for (nf->first(it); it != INVALID; nf->next(it)) {
   1.251 -        Map::set(it, _inv_map.size());
   1.252 -        _inv_map.push_back(it);
   1.253 -      }
   1.254 -    }
   1.255 -
   1.256 -  protected:
   1.257 -
   1.258 -    /// \brief Add a new key to the map.
   1.259 -    ///
   1.260 -    /// Add a new key to the map. It is called by the
   1.261 -    /// \c AlterationNotifier.
   1.262 -    virtual void add(const Item& item) {
   1.263 -      Map::add(item);
   1.264 -      Map::set(item, _inv_map.size());
   1.265 -      _inv_map.push_back(item);
   1.266 -    }
   1.267 -
   1.268 -    /// \brief Add more new keys to the map.
   1.269 -    ///
   1.270 -    /// Add more new keys to the map. It is called by the
   1.271 -    /// \c AlterationNotifier.
   1.272 -    virtual void add(const std::vector<Item>& items) {
   1.273 -      Map::add(items);
   1.274 -      for (int i = 0; i < int(items.size()); ++i) {
   1.275 -        Map::set(items[i], _inv_map.size());
   1.276 -        _inv_map.push_back(items[i]);
   1.277 -      }
   1.278 -    }
   1.279 -
   1.280 -    /// \brief Erase the key from the map.
   1.281 -    ///
   1.282 -    /// Erase the key from the map. It is called by the
   1.283 -    /// \c AlterationNotifier.
   1.284 -    virtual void erase(const Item& item) {
   1.285 -      Map::set(_inv_map.back(), Map::operator[](item));
   1.286 -      _inv_map[Map::operator[](item)] = _inv_map.back();
   1.287 -      _inv_map.pop_back();
   1.288 -      Map::erase(item);
   1.289 -    }
   1.290 -
   1.291 -    /// \brief Erase more keys from the map.
   1.292 -    ///
   1.293 -    /// Erase more keys from the map. It is called by the
   1.294 -    /// \c AlterationNotifier.
   1.295 -    virtual void erase(const std::vector<Item>& items) {
   1.296 -      for (int i = 0; i < int(items.size()); ++i) {
   1.297 -        Map::set(_inv_map.back(), Map::operator[](items[i]));
   1.298 -        _inv_map[Map::operator[](items[i])] = _inv_map.back();
   1.299 -        _inv_map.pop_back();
   1.300 -      }
   1.301 -      Map::erase(items);
   1.302 -    }
   1.303 -
   1.304 -    /// \brief Build the unique map.
   1.305 -    ///
   1.306 -    /// Build the unique map. It is called by the
   1.307 -    /// \c AlterationNotifier.
   1.308 -    virtual void build() {
   1.309 -      Map::build();
   1.310 -      Item it;
   1.311 -      const typename Map::Notifier* nf = Map::notifier();
   1.312 -      for (nf->first(it); it != INVALID; nf->next(it)) {
   1.313 -        Map::set(it, _inv_map.size());
   1.314 -        _inv_map.push_back(it);
   1.315 -      }
   1.316 -    }
   1.317 -
   1.318 -    /// \brief Clear the keys from the map.
   1.319 -    ///
   1.320 -    /// Clear the keys from the map. It is called by the
   1.321 -    /// \c AlterationNotifier.
   1.322 -    virtual void clear() {
   1.323 -      _inv_map.clear();
   1.324 -      Map::clear();
   1.325 -    }
   1.326 -
   1.327 -  public:
   1.328 -
   1.329 -    /// \brief Returns the maximal value plus one.
   1.330 -    ///
   1.331 -    /// Returns the maximal value plus one in the map.
   1.332 -    unsigned int size() const {
   1.333 -      return _inv_map.size();
   1.334 -    }
   1.335 -
   1.336 -    /// \brief Swaps the position of the two items in the map.
   1.337 -    ///
   1.338 -    /// Swaps the position of the two items in the map.
   1.339 -    void swap(const Item& p, const Item& q) {
   1.340 -      int pi = Map::operator[](p);
   1.341 -      int qi = Map::operator[](q);
   1.342 -      Map::set(p, qi);
   1.343 -      _inv_map[qi] = p;
   1.344 -      Map::set(q, pi);
   1.345 -      _inv_map[pi] = q;
   1.346 -    }
   1.347 -
   1.348 -    /// \brief Gives back the \e descriptor of the item.
   1.349 -    ///
   1.350 -    /// Gives back the mutable and unique \e descriptor of the map.
   1.351 -    int operator[](const Item& item) const {
   1.352 -      return Map::operator[](item);
   1.353 -    }
   1.354 -
   1.355 -    /// \brief Gives back the item by its descriptor.
   1.356 -    ///
   1.357 -    /// Gives back th item by its descriptor.
   1.358 -    Item operator()(int id) const {
   1.359 -      return _inv_map[id];
   1.360 -    }
   1.361 -
   1.362 -  private:
   1.363 -
   1.364 -    typedef std::vector<Item> Container;
   1.365 -    Container _inv_map;
   1.366 -
   1.367 -  public:
   1.368 -    /// \brief The inverse map type of DescriptorMap.
   1.369 -    ///
   1.370 -    /// The inverse map type of DescriptorMap.
   1.371 -    class InverseMap {
   1.372 -    public:
   1.373 -      /// \brief Constructor of the InverseMap.
   1.374 -      ///
   1.375 -      /// Constructor of the InverseMap.
   1.376 -      explicit InverseMap(const DescriptorMap& inverted)
   1.377 -        : _inverted(inverted) {}
   1.378 -
   1.379 -
   1.380 -      /// The value type of the InverseMap.
   1.381 -      typedef typename DescriptorMap::Key Value;
   1.382 -      /// The key type of the InverseMap.
   1.383 -      typedef typename DescriptorMap::Value Key;
   1.384 -
   1.385 -      /// \brief Subscript operator.
   1.386 -      ///
   1.387 -      /// Subscript operator. It gives back the item
   1.388 -      /// that the descriptor belongs to currently.
   1.389 -      Value operator[](const Key& key) const {
   1.390 -        return _inverted(key);
   1.391 -      }
   1.392 -
   1.393 -      /// \brief Size of the map.
   1.394 -      ///
   1.395 -      /// Returns the size of the map.
   1.396 -      unsigned int size() const {
   1.397 -        return _inverted.size();
   1.398 -      }
   1.399 -
   1.400 -    private:
   1.401 -      const DescriptorMap& _inverted;
   1.402 -    };
   1.403 -
   1.404 -    /// \brief Gives back the inverse of the map.
   1.405 -    ///
   1.406 -    /// Gives back the inverse of the map.
   1.407 -    const InverseMap inverse() const {
   1.408 -      return InverseMap(*this);
   1.409 -    }
   1.410 -  };
   1.411 -
   1.412    /// \brief Returns the source of the given arc.
   1.413    ///
   1.414    /// The SourceMap gives back the source Node of the given arc.
     2.1 --- a/test/graph_utils_test.cc	Wed Oct 08 10:33:42 2008 +0100
     2.2 +++ b/test/graph_utils_test.cc	Wed Oct 08 12:25:57 2008 +0100
     2.3 @@ -35,18 +35,18 @@
     2.4  
     2.5    {
     2.6      Digraph digraph;
     2.7 +    typename Digraph::template NodeMap<int> nodes(digraph);
     2.8 +    std::vector<Node> invNodes;
     2.9      for (int i = 0; i < 10; ++i) {
    2.10 -      digraph.addNode();
    2.11 +      invNodes.push_back(digraph.addNode());
    2.12 +      nodes[invNodes.back()]=invNodes.size()-1;
    2.13      }
    2.14 -    DescriptorMap<Digraph, Node> nodes(digraph);
    2.15 -    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
    2.16      for (int i = 0; i < 100; ++i) {
    2.17        int src = rnd[invNodes.size()];
    2.18        int trg = rnd[invNodes.size()];
    2.19        digraph.addArc(invNodes[src], invNodes[trg]);
    2.20      }
    2.21      typename Digraph::template ArcMap<bool> found(digraph, false);
    2.22 -    DescriptorMap<Digraph, Arc> arcs(digraph);
    2.23      for (NodeIt src(digraph); src != INVALID; ++src) {
    2.24        for (NodeIt trg(digraph); trg != INVALID; ++trg) {
    2.25          for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
    2.26 @@ -110,18 +110,18 @@
    2.27  void checkFindEdges() {
    2.28    TEMPLATE_GRAPH_TYPEDEFS(Graph);
    2.29    Graph graph;
    2.30 +  typename Graph::template NodeMap<int> nodes(graph);
    2.31 +  std::vector<Node> invNodes;
    2.32    for (int i = 0; i < 10; ++i) {
    2.33 -    graph.addNode();
    2.34 +    invNodes.push_back(graph.addNode());
    2.35 +    nodes[invNodes.back()]=invNodes.size()-1;
    2.36    }
    2.37 -  DescriptorMap<Graph, Node> nodes(graph);
    2.38 -  typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
    2.39    for (int i = 0; i < 100; ++i) {
    2.40      int src = rnd[invNodes.size()];
    2.41      int trg = rnd[invNodes.size()];
    2.42      graph.addEdge(invNodes[src], invNodes[trg]);
    2.43    }
    2.44    typename Graph::template EdgeMap<int> found(graph, 0);
    2.45 -  DescriptorMap<Graph, Edge> edges(graph);
    2.46    for (NodeIt src(graph); src != INVALID; ++src) {
    2.47      for (NodeIt trg(graph); trg != INVALID; ++trg) {
    2.48        for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {