Changes in lemon/maps.h [327:12626fc94ccf:314:2cc60866a0c9] in lemon

File:

• lemon/maps.h (modified) (1 diff)

lemon/maps.h

@@ -1856 +1856 @@
     InverseMap inverse() const { return InverseMap(*_graph);}
 
+  };
+
+
+  /// \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);
+    }
   };