1.1 --- a/lemon/graph_utils.h Mon Jan 30 09:37:41 2006 +0000
1.2 +++ b/lemon/graph_utils.h Tue Jan 31 19:33:48 2006 +0000
1.3 @@ -886,9 +886,15 @@
1.4 /// The InvertableMap wraps an arbitrary ReadWriteMap
1.5 /// and if a key is set to a new value then store it
1.6 /// in the inverse map.
1.7 + ///
1.8 + /// The values of the map can be accessed
1.9 + /// with stl compatible forward iterator.
1.10 + ///
1.11 /// \param _Graph The graph type.
1.12 /// \param _Item The item type of the graph.
1.13 /// \param _Value The value type of the map.
1.14 + ///
1.15 + /// \see IterableValueMap
1.16 #ifndef DOXYGEN
1.17 /// \param _Map A ReadWriteMap mapping from the item type to integer.
1.18 template <
1.19 @@ -899,22 +905,83 @@
1.20 template <typename _Graph, typename _Item, typename _Value>
1.21 #endif
1.22 class InvertableMap : protected _Map {
1.23 -
1.24 public:
1.25 -
1.26 - typedef _Map Map;
1.27 - typedef _Graph Graph;
1.28
1.29 /// The key type of InvertableMap (Node, Edge, UEdge).
1.30 typedef typename _Map::Key Key;
1.31 /// The value type of the InvertableMap.
1.32 typedef typename _Map::Value Value;
1.33
1.34 + private:
1.35 +
1.36 + typedef _Map Map;
1.37 + typedef _Graph Graph;
1.38 +
1.39 + typedef std::map<Value, Key> Container;
1.40 + Container invMap;
1.41 +
1.42 + public:
1.43 +
1.44 +
1.45 +
1.46 /// \brief Constructor.
1.47 ///
1.48 /// Construct a new InvertableMap for the graph.
1.49 ///
1.50 InvertableMap(const Graph& graph) : Map(graph) {}
1.51 +
1.52 + /// \brief Forward iterator for values.
1.53 + ///
1.54 + /// This iterator is an stl compatible forward
1.55 + /// iterator on the values of the map. The values can
1.56 + /// be accessed in the [beginValue, endValue) range.
1.57 + ///
1.58 + class ValueIterator
1.59 + : public std::iterator<std::forward_iterator_tag, Value> {
1.60 + friend class InvertableMap;
1.61 + private:
1.62 + ValueIterator(typename Container::const_iterator _it)
1.63 + : it(_it) {}
1.64 + public:
1.65 +
1.66 + ValueIterator() {}
1.67 +
1.68 + ValueIterator& operator++() { ++it; return *this; }
1.69 + ValueIterator operator++(int) {
1.70 + ValueIterator tmp(*this);
1.71 + operator++();
1.72 + return tmp;
1.73 + }
1.74 +
1.75 + const Value& operator*() const { return it->first; }
1.76 + const Value* operator->() const { return &(it->first); }
1.77 +
1.78 + bool operator==(ValueIterator jt) const { return it == jt.it; }
1.79 + bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.80 +
1.81 + private:
1.82 + typename Container::const_iterator it;
1.83 + };
1.84 +
1.85 + /// \brief Returns an iterator to the first value.
1.86 + ///
1.87 + /// Returns an stl compatible iterator to the
1.88 + /// first value of the map. The values of the
1.89 + /// map can be accessed in the [beginValue, endValue)
1.90 + /// range.
1.91 + ValueIterator beginValue() const {
1.92 + return ValueIterator(invMap.begin());
1.93 + }
1.94 +
1.95 + /// \brief Returns an iterator after the last value.
1.96 + ///
1.97 + /// Returns an stl compatible iterator after the
1.98 + /// last value of the map. The values of the
1.99 + /// map can be accessed in the [beginValue, endValue)
1.100 + /// range.
1.101 + ValueIterator endValue() const {
1.102 + return ValueIterator(invMap.end());
1.103 + }
1.104
1.105 /// \brief The setter function of the map.
1.106 ///
1.107 @@ -932,7 +999,8 @@
1.108 /// \brief The getter function of the map.
1.109 ///
1.110 /// It gives back the value associated with the key.
1.111 - Value operator[](const Key& key) const {
1.112 + typename MapTraits<Map>::ConstReturnValue
1.113 + operator[](const Key& key) const {
1.114 return Map::operator[](key);
1.115 }
1.116
1.117 @@ -975,11 +1043,6 @@
1.118 Map::clear();
1.119 }
1.120
1.121 - private:
1.122 -
1.123 - typedef std::map<Value, Key> Container;
1.124 - Container invMap;
1.125 -
1.126 public:
1.127
1.128 /// \brief The inverse map type.
1.129 @@ -1140,6 +1203,13 @@
1.130
1.131 public:
1.132
1.133 + /// \brief Returns the maximal value plus one.
1.134 + ///
1.135 + /// Returns the maximal value plus one in the map.
1.136 + unsigned int size() const {
1.137 + return invMap.size();
1.138 + }
1.139 +
1.140 /// \brief Swaps the position of the two items in the map.
1.141 ///
1.142 /// Swaps the position of the two items in the map.
1.143 @@ -1193,7 +1263,7 @@
1.144 /// \brief Size of the map.
1.145 ///
1.146 /// Returns the size of the map.
1.147 - int size() const {
1.148 + unsigned int size() const {
1.149 return inverted.invMap.size();
1.150 }
1.151
1.152 @@ -1447,6 +1517,7 @@
1.153 Parent::add(key);
1.154 Parent::set(key, 0);
1.155 }
1.156 +
1.157 virtual void add(const std::vector<Key>& keys) {
1.158 Parent::add(keys);
1.159 for (int i = 0; i < (int)keys.size(); ++i) {
1.160 @@ -1487,10 +1558,22 @@
1.161 ++deg[graph.target(edge)];
1.162 }
1.163
1.164 + virtual void add(const std::vector<Edge>& edges) {
1.165 + for (int i = 0; i < (int)edges.size(); ++i) {
1.166 + ++deg[graph.target(edges[i])];
1.167 + }
1.168 + }
1.169 +
1.170 virtual void erase(const Edge& edge) {
1.171 --deg[graph.target(edge)];
1.172 }
1.173
1.174 + virtual void erase(const std::vector<Edge>& edges) {
1.175 + for (int i = 0; i < (int)edges.size(); ++i) {
1.176 + --deg[graph.target(edges[i])];
1.177 + }
1.178 + }
1.179 +
1.180 virtual void build() {
1.181 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.182 deg[it] = countInEdges(graph, it);
1.183 @@ -1591,10 +1674,22 @@
1.184 ++deg[graph.source(edge)];
1.185 }
1.186
1.187 + virtual void add(const std::vector<Edge>& edges) {
1.188 + for (int i = 0; i < (int)edges.size(); ++i) {
1.189 + ++deg[graph.source(edges[i])];
1.190 + }
1.191 + }
1.192 +
1.193 virtual void erase(const Edge& edge) {
1.194 --deg[graph.source(edge)];
1.195 }
1.196
1.197 + virtual void erase(const std::vector<Edge>& edges) {
1.198 + for (int i = 0; i < (int)edges.size(); ++i) {
1.199 + --deg[graph.source(edges[i])];
1.200 + }
1.201 + }
1.202 +
1.203 virtual void build() {
1.204 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.205 deg[it] = countOutEdges(graph, it);