lemon-0.x: comparison lemon/graph

equal deleted inserted replaced

-:5588a06c73c0
+:84b8b9401e50
 /// 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.
+///
 /// \param _Graph The graph type.
 /// \param _Item The item type of the graph.
 /// \param _Value The value type of the map.
+///
+/// \see IterableValueMap
 #ifndef DOXYGEN
 /// \param _Map A ReadWriteMap mapping from the item type to integer.
 template <
 typename _Graph, typename _Item, typename _Value, typename _Map
 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
 >
 #else
 template <typename _Graph, typename _Item, typename _Value>
 #endif
 class InvertableMap : protected _Map {
+public:
-public:
-typedef _Map Map;
-typedef _Graph Graph;
 /// The key type of InvertableMap (Node, Edge, UEdge).
 typedef typename _Map::Key Key;
 /// The value type of the InvertableMap.
 typedef typename _Map::Value Value;
+private:
+typedef _Map Map;
+typedef _Graph Graph;
+typedef std::map<Value, Key> Container;
+Container invMap;
+public:
 /// \brief Constructor.
 ///
 /// Construct a new InvertableMap for the graph.
 ///
 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(invMap.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(invMap.end());
+}
 /// \brief The setter function of the map.
 ///
 /// Sets the mapped value.
 void set(const Key& key, const Value& val) {
 }
 /// \brief The getter function of the map.
 ///
 /// It gives back the value associated with the key.
-Value operator[](const Key& key) const {
+typename MapTraits<Map>::ConstReturnValue
+operator[](const Key& key) const {
 return Map::operator[](key);
 }
 protected:
 /// \c AlterationNotifier.
 virtual void clear() {
 invMap.clear();
 Map::clear();
 }
-private:
-typedef std::map<Value, Key> Container;
-Container invMap;
 public:
 /// \brief The inverse map type.
 ///
 Map::clear();
 }
 public:
+/// \brief Returns the maximal value plus one.
+///
+/// Returns the maximal value plus one in the map.
+unsigned int size() const {
+return invMap.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);
 }
 /// \brief Size of the map.
 ///
 /// Returns the size of the map.
-int size() const {
+unsigned int size() const {
 	return inverted.invMap.size();
 }
 private:
 const DescriptorMap& inverted;
 virtual void add(const Key& key) {
 	Parent::add(key);
 	Parent::set(key, 0);
 }
 virtual void add(const std::vector<Key>& keys) {
 	Parent::add(keys);
 	for (int i = 0; i < (int)keys.size(); ++i) {
 	  Parent::set(keys[i], 0);
 	}
 virtual void add(const Edge& edge) {
 ++deg[graph.target(edge)];
 }
+virtual void add(const std::vector<Edge>& edges) {
+for (int i = 0; i < (int)edges.size(); ++i) {
+++deg[graph.target(edges[i])];
+}
+}
 virtual void erase(const Edge& edge) {
 --deg[graph.target(edge)];
+}
+virtual void erase(const std::vector<Edge>& edges) {
+for (int i = 0; i < (int)edges.size(); ++i) {
+--deg[graph.target(edges[i])];
+}
 }
 virtual void build() {
 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
 	deg[it] = countInEdges(graph, it);
 virtual void add(const Edge& edge) {
 ++deg[graph.source(edge)];
 }
+virtual void add(const std::vector<Edge>& edges) {
+for (int i = 0; i < (int)edges.size(); ++i) {
+++deg[graph.source(edges[i])];
+}
+}
 virtual void erase(const Edge& edge) {
 --deg[graph.source(edge)];
+}
+virtual void erase(const std::vector<Edge>& edges) {
+for (int i = 0; i < (int)edges.size(); ++i) {
+--deg[graph.source(edges[i])];
+}
 }
 virtual void build() {
 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
 	deg[it] = countOutEdges(graph, it);

changeset 1944	89d5cf6e6abb
parent 1909	2d806130e700
child 1946	17eb3eaad9f8