# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1223465157 -3600
# Node ID fafece4177955d66895244c73b4cdac3c69803fe
# Parent  bfed14fbfdc5949178624835907e8b9005b957b3
Remove InverseMap and DescriptorMap

diff -r bfed14fbfdc5 -r fafece417795 lemon/maps.h
--- a/lemon/maps.h	Wed Oct 08 10:33:42 2008 +0100
+++ b/lemon/maps.h	Wed Oct 08 12:25:57 2008 +0100
@@ -1847,411 +1847,6 @@
 
   };
 
-
-  /// \brief General invertable graph-map type.
-
-  /// This type provides simple invertable graph-maps.
-  /// The InvertableMap wraps an arbitrary ReadWriteMap
-  /// and if a key is set to a new value then store it
-  /// in the inverse map.
-  ///
-  /// The values of the map can be accessed
-  /// with stl compatible forward iterator.
-  ///
-  /// \tparam _Graph The graph type.
-  /// \tparam _Item The item type of the graph.
-  /// \tparam _Value The value type of the map.
-  ///
-  /// \see IterableValueMap
-  template <typename _Graph, typename _Item, typename _Value>
-  class InvertableMap
-    : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
-  private:
-
-    typedef typename ItemSetTraits<_Graph, _Item>::
-    template Map<_Value>::Type Map;
-    typedef _Graph Graph;
-
-    typedef std::map<_Value, _Item> Container;
-    Container _inv_map;
-
-  public:
-
-    /// The key type of InvertableMap (Node, Arc, Edge).
-    typedef typename Map::Key Key;
-    /// The value type of the InvertableMap.
-    typedef typename Map::Value Value;
-
-
-
-    /// \brief Constructor.
-    ///
-    /// Construct a new InvertableMap for the graph.
-    ///
-    explicit InvertableMap(const Graph& graph) : Map(graph) {}
-
-    /// \brief Forward iterator for values.
-    ///
-    /// This iterator is an stl compatible forward
-    /// iterator on the values of the map. The values can
-    /// be accessed in the [beginValue, endValue) range.
-    ///
-    class ValueIterator
-      : public std::iterator<std::forward_iterator_tag, Value> {
-      friend class InvertableMap;
-    private:
-      ValueIterator(typename Container::const_iterator _it)
-        : it(_it) {}
-    public:
-
-      ValueIterator() {}
-
-      ValueIterator& operator++() { ++it; return *this; }
-      ValueIterator operator++(int) {
-        ValueIterator tmp(*this);
-        operator++();
-        return tmp;
-      }
-
-      const Value& operator*() const { return it->first; }
-      const Value* operator->() const { return &(it->first); }
-
-      bool operator==(ValueIterator jt) const { return it == jt.it; }
-      bool operator!=(ValueIterator jt) const { return it != jt.it; }
-
-    private:
-      typename Container::const_iterator it;
-    };
-
-    /// \brief Returns an iterator to the first value.
-    ///
-    /// Returns an stl compatible iterator to the
-    /// first value of the map. The values of the
-    /// map can be accessed in the [beginValue, endValue)
-    /// range.
-    ValueIterator beginValue() const {
-      return ValueIterator(_inv_map.begin());
-    }
-
-    /// \brief Returns an iterator after the last value.
-    ///
-    /// Returns an stl compatible iterator after the
-    /// last value of the map. The values of the
-    /// map can be accessed in the [beginValue, endValue)
-    /// range.
-    ValueIterator endValue() const {
-      return ValueIterator(_inv_map.end());
-    }
-
-    /// \brief The setter function of the map.
-    ///
-    /// Sets the mapped value.
-    void set(const Key& key, const Value& val) {
-      Value oldval = Map::operator[](key);
-      typename Container::iterator it = _inv_map.find(oldval);
-      if (it != _inv_map.end() && it->second == key) {
-        _inv_map.erase(it);
-      }
-      _inv_map.insert(make_pair(val, key));
-      Map::set(key, val);
-    }
-
-    /// \brief The getter function of the map.
-    ///
-    /// It gives back the value associated with the key.
-    typename MapTraits<Map>::ConstReturnValue
-    operator[](const Key& key) const {
-      return Map::operator[](key);
-    }
-
-    /// \brief Gives back the item by its value.
-    ///
-    /// Gives back the item by its value.
-    Key operator()(const Value& key) const {
-      typename Container::const_iterator it = _inv_map.find(key);
-      return it != _inv_map.end() ? it->second : INVALID;
-    }
-
-  protected:
-
-    /// \brief Erase the key from the map.
-    ///
-    /// Erase the key to the map. It is called by the
-    /// \c AlterationNotifier.
-    virtual void erase(const Key& key) {
-      Value val = Map::operator[](key);
-      typename Container::iterator it = _inv_map.find(val);
-      if (it != _inv_map.end() && it->second == key) {
-        _inv_map.erase(it);
-      }
-      Map::erase(key);
-    }
-
-    /// \brief Erase more keys from the map.
-    ///
-    /// Erase more keys from the map. It is called by the
-    /// \c AlterationNotifier.
-    virtual void erase(const std::vector<Key>& keys) {
-      for (int i = 0; i < int(keys.size()); ++i) {
-        Value val = Map::operator[](keys[i]);
-        typename Container::iterator it = _inv_map.find(val);
-        if (it != _inv_map.end() && it->second == keys[i]) {
-          _inv_map.erase(it);
-        }
-      }
-      Map::erase(keys);
-    }
-
-    /// \brief Clear the keys from the map and inverse map.
-    ///
-    /// Clear the keys from the map and inverse map. It is called by the
-    /// \c AlterationNotifier.
-    virtual void clear() {
-      _inv_map.clear();
-      Map::clear();
-    }
-
-  public:
-
-    /// \brief The inverse map type.
-    ///
-    /// The inverse of this map. The subscript operator of the map
-    /// gives back always the item what was last assigned to the value.
-    class InverseMap {
-    public:
-      /// \brief Constructor of the InverseMap.
-      ///
-      /// Constructor of the InverseMap.
-      explicit InverseMap(const InvertableMap& inverted)
-        : _inverted(inverted) {}
-
-      /// The value type of the InverseMap.
-      typedef typename InvertableMap::Key Value;
-      /// The key type of the InverseMap.
-      typedef typename InvertableMap::Value Key;
-
-      /// \brief Subscript operator.
-      ///
-      /// Subscript operator. It gives back always the item
-      /// what was last assigned to the value.
-      Value operator[](const Key& key) const {
-        return _inverted(key);
-      }
-
-    private:
-      const InvertableMap& _inverted;
-    };
-
-    /// \brief It gives back the just readable inverse map.
-    ///
-    /// It gives back the just readable inverse map.
-    InverseMap inverse() const {
-      return InverseMap(*this);
-    }
-
-
-
-  };
-
-  /// \brief Provides a mutable, continuous and unique descriptor for each
-  /// item in the graph.
-  ///
-  /// The DescriptorMap class provides a unique and continuous (but mutable)
-  /// descriptor (id) for each item of the same type (e.g. node) in the
-  /// graph. This id is <ul><li>\b unique: different items (nodes) get
-  /// different ids <li>\b continuous: the range of the ids is the set of
-  /// integers between 0 and \c n-1, where \c n is the number of the items of
-  /// this type (e.g. nodes) (so the id of a node can change if you delete an
-  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
-  /// with its member class \c InverseMap, or with the \c operator() member.
-  ///
-  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
-  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
-  /// Edge.
-  template <typename _Graph, typename _Item>
-  class DescriptorMap
-    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
-
-    typedef _Item Item;
-    typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
-
-  public:
-    /// The graph class of DescriptorMap.
-    typedef _Graph Graph;
-
-    /// The key type of DescriptorMap (Node, Arc, Edge).
-    typedef typename Map::Key Key;
-    /// The value type of DescriptorMap.
-    typedef typename Map::Value Value;
-
-    /// \brief Constructor.
-    ///
-    /// Constructor for descriptor map.
-    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
-      Item it;
-      const typename Map::Notifier* nf = Map::notifier();
-      for (nf->first(it); it != INVALID; nf->next(it)) {
-        Map::set(it, _inv_map.size());
-        _inv_map.push_back(it);
-      }
-    }
-
-  protected:
-
-    /// \brief Add a new key to the map.
-    ///
-    /// Add a new key to the map. It is called by the
-    /// \c AlterationNotifier.
-    virtual void add(const Item& item) {
-      Map::add(item);
-      Map::set(item, _inv_map.size());
-      _inv_map.push_back(item);
-    }
-
-    /// \brief Add more new keys to the map.
-    ///
-    /// Add more new keys to the map. It is called by the
-    /// \c AlterationNotifier.
-    virtual void add(const std::vector<Item>& items) {
-      Map::add(items);
-      for (int i = 0; i < int(items.size()); ++i) {
-        Map::set(items[i], _inv_map.size());
-        _inv_map.push_back(items[i]);
-      }
-    }
-
-    /// \brief Erase the key from the map.
-    ///
-    /// Erase the key from the map. It is called by the
-    /// \c AlterationNotifier.
-    virtual void erase(const Item& item) {
-      Map::set(_inv_map.back(), Map::operator[](item));
-      _inv_map[Map::operator[](item)] = _inv_map.back();
-      _inv_map.pop_back();
-      Map::erase(item);
-    }
-
-    /// \brief Erase more keys from the map.
-    ///
-    /// Erase more keys from the map. It is called by the
-    /// \c AlterationNotifier.
-    virtual void erase(const std::vector<Item>& items) {
-      for (int i = 0; i < int(items.size()); ++i) {
-        Map::set(_inv_map.back(), Map::operator[](items[i]));
-        _inv_map[Map::operator[](items[i])] = _inv_map.back();
-        _inv_map.pop_back();
-      }
-      Map::erase(items);
-    }
-
-    /// \brief Build the unique map.
-    ///
-    /// Build the unique map. It is called by the
-    /// \c AlterationNotifier.
-    virtual void build() {
-      Map::build();
-      Item it;
-      const typename Map::Notifier* nf = Map::notifier();
-      for (nf->first(it); it != INVALID; nf->next(it)) {
-        Map::set(it, _inv_map.size());
-        _inv_map.push_back(it);
-      }
-    }
-
-    /// \brief Clear the keys from the map.
-    ///
-    /// Clear the keys from the map. It is called by the
-    /// \c AlterationNotifier.
-    virtual void clear() {
-      _inv_map.clear();
-      Map::clear();
-    }
-
-  public:
-
-    /// \brief Returns the maximal value plus one.
-    ///
-    /// Returns the maximal value plus one in the map.
-    unsigned int size() const {
-      return _inv_map.size();
-    }
-
-    /// \brief Swaps the position of the two items in the map.
-    ///
-    /// Swaps the position of the two items in the map.
-    void swap(const Item& p, const Item& q) {
-      int pi = Map::operator[](p);
-      int qi = Map::operator[](q);
-      Map::set(p, qi);
-      _inv_map[qi] = p;
-      Map::set(q, pi);
-      _inv_map[pi] = q;
-    }
-
-    /// \brief Gives back the \e descriptor of the item.
-    ///
-    /// Gives back the mutable and unique \e descriptor of the map.
-    int operator[](const Item& item) const {
-      return Map::operator[](item);
-    }
-
-    /// \brief Gives back the item by its descriptor.
-    ///
-    /// Gives back th item by its descriptor.
-    Item operator()(int id) const {
-      return _inv_map[id];
-    }
-
-  private:
-
-    typedef std::vector<Item> Container;
-    Container _inv_map;
-
-  public:
-    /// \brief The inverse map type of DescriptorMap.
-    ///
-    /// The inverse map type of DescriptorMap.
-    class InverseMap {
-    public:
-      /// \brief Constructor of the InverseMap.
-      ///
-      /// Constructor of the InverseMap.
-      explicit InverseMap(const DescriptorMap& inverted)
-        : _inverted(inverted) {}
-
-
-      /// The value type of the InverseMap.
-      typedef typename DescriptorMap::Key Value;
-      /// The key type of the InverseMap.
-      typedef typename DescriptorMap::Value Key;
-
-      /// \brief Subscript operator.
-      ///
-      /// Subscript operator. It gives back the item
-      /// that the descriptor belongs to currently.
-      Value operator[](const Key& key) const {
-        return _inverted(key);
-      }
-
-      /// \brief Size of the map.
-      ///
-      /// Returns the size of the map.
-      unsigned int size() const {
-        return _inverted.size();
-      }
-
-    private:
-      const DescriptorMap& _inverted;
-    };
-
-    /// \brief Gives back the inverse of the map.
-    ///
-    /// Gives back the inverse of the map.
-    const InverseMap inverse() const {
-      return InverseMap(*this);
-    }
-  };
-
   /// \brief Returns the source of the given arc.
   ///
   /// The SourceMap gives back the source Node of the given arc.
diff -r bfed14fbfdc5 -r fafece417795 test/graph_utils_test.cc
--- a/test/graph_utils_test.cc	Wed Oct 08 10:33:42 2008 +0100
+++ b/test/graph_utils_test.cc	Wed Oct 08 12:25:57 2008 +0100
@@ -35,18 +35,18 @@
 
   {
     Digraph digraph;
+    typename Digraph::template NodeMap<int> nodes(digraph);
+    std::vector<Node> invNodes;
     for (int i = 0; i < 10; ++i) {
-      digraph.addNode();
+      invNodes.push_back(digraph.addNode());
+      nodes[invNodes.back()]=invNodes.size()-1;
     }
-    DescriptorMap<Digraph, Node> nodes(digraph);
-    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
     for (int i = 0; i < 100; ++i) {
       int src = rnd[invNodes.size()];
       int trg = rnd[invNodes.size()];
       digraph.addArc(invNodes[src], invNodes[trg]);
     }
     typename Digraph::template ArcMap<bool> found(digraph, false);
-    DescriptorMap<Digraph, Arc> arcs(digraph);
     for (NodeIt src(digraph); src != INVALID; ++src) {
       for (NodeIt trg(digraph); trg != INVALID; ++trg) {
         for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
@@ -110,18 +110,18 @@
 void checkFindEdges() {
   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   Graph graph;
+  typename Graph::template NodeMap<int> nodes(graph);
+  std::vector<Node> invNodes;
   for (int i = 0; i < 10; ++i) {
-    graph.addNode();
+    invNodes.push_back(graph.addNode());
+    nodes[invNodes.back()]=invNodes.size()-1;
   }
-  DescriptorMap<Graph, Node> nodes(graph);
-  typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
   for (int i = 0; i < 100; ++i) {
     int src = rnd[invNodes.size()];
     int trg = rnd[invNodes.size()];
     graph.addEdge(invNodes[src], invNodes[trg]);
   }
   typename Graph::template EdgeMap<int> found(graph, 0);
-  DescriptorMap<Graph, Edge> edges(graph);
   for (NodeIt src(graph); src != INVALID; ++src) {
     for (NodeIt trg(graph); trg != INVALID; ++trg) {
       for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {