lemon-0.x: comparison src/lemon/graph

equal deleted inserted replaced

-:41a924a30722
+:8477bfeb497c
 #include <iterator>
 #include <map>
 #include <lemon/invalid.h>
 #include <lemon/utility.h>
+#include <lemon/maps.h>
 ///\ingroup gutils
 ///\file
 ///\brief Graph utilities.
 ///
 /// @}
 /// \addtogroup graph_maps
 /// @{
-/// Provides an immutable and unique id for each item in the graph.
-/// The IdMap class provides an unique and immutable mapping for each item
-/// in the graph.
-///
-template <typename _Graph, typename _Item>
-class IdMap {
-public:
-typedef _Graph Graph;
-typedef int Value;
-typedef _Item Item;
-typedef _Item Key;
-/// \brief The class represents the inverse of the map.
-///
-/// The class represents the inverse of the map.
-/// \see inverse()
-class InverseMap {
-public:
-/// \brief Constructor.
-///
-/// Constructor for creating an id-to-item map.
-InverseMap(const Graph& _graph) : graph(&_graph) {}
-/// \brief Gives back the given item from its id.
-///
-/// Gives back the given item from its id.
-///
-Item operator[](int id) const { return graph->fromId(id, Item());}
-private:
-const Graph* graph;
-};
-/// \brief Constructor.
-///
-/// Constructor for creating id map.
-IdMap(const Graph& _graph) : graph(&_graph) {}
-/// \brief Gives back the \e id of the item.
-///
-/// Gives back the immutable and unique \e id of the map.
-int operator[](const Item& item) const { return graph->id(item);}
-/// \brief Gives back the inverse of the map.
-///
-/// Gives back the inverse of the map.
-InverseMap inverse() const { return InverseMap(*graph);}
-private:
-const Graph* graph;
-};
 template <typename Map, typename Enable = void>
 struct ReferenceMapTraits {
 typedef typename Map::Value Value;
 typedef typename Map::Value& Reference;
 typedef const typename Map::Value& ConstReference;
 typedef typename Map::ConstReference ConstReference;
 typedef typename Map::Pointer Pointer;
 typedef typename Map::ConstPointer ConstPointer;
 };
+/// Provides an immutable and unique id for each item in the graph.
+/// The IdMap class provides an unique and immutable mapping for each item
+/// in the graph.
+///
+template <typename _Graph, typename _Item>
+class IdMap {
+public:
+typedef _Graph Graph;
+typedef int Value;
+typedef _Item Item;
+typedef _Item Key;
+/// \brief Constructor.
+///
+/// Constructor for creating id map.
+IdMap(const Graph& _graph) : graph(&_graph) {}
+/// \brief Gives back the \e id of the item.
+///
+/// Gives back the immutable and unique \e id of the map.
+int operator[](const Item& item) const { return graph->id(item);}
+private:
+const Graph* graph;
+public:
+/// \brief The class represents the inverse of the map.
+///
+/// The class represents the inverse of the map.
+/// \see inverse()
+class InverseMap {
+public:
+/// \brief Constructor.
+///
+/// Constructor for creating an id-to-item map.
+InverseMap(const Graph& _graph) : graph(&_graph) {}
+/// \brief Constructor.
+///
+/// Constructor for creating an id-to-item map.
+InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
+/// \brief Gives back the given item from its id.
+///
+/// Gives back the given item from its id.
+///
+Item operator[](int id) const { return graph->fromId(id, Item());}
+private:
+const Graph* graph;
+};
+/// \brief Gives back the inverse of the map.
+///
+/// Gives back the inverse of the map.
+InverseMap inverse() const { return InverseMap(*graph);}
+};
 /// \brief General inversable graph-map type.
 /// This type provides simple inversable map functions.
 /// The InversableMap wraps an arbitrary ReadWriteMap
 /// and if a key is setted to a new value then store it
 template <
 typename _Graph,
 typename _Item,
 typename _Value,
 typename _Map
-= typename ItemSetTraits<_Graph, _Item>::template Map<_Value>
+= typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent
 >
-class InversableMap : protected _Map {
+class InvertableMap : protected _Map {
 public:
 typedef _Map Map;
 typedef _Graph Graph;
-/// The key type of InversableMap (Node, Edge, UndirEdge).
+/// The key type of InvertableMap (Node, Edge, UndirEdge).
 typedef typename _Map::Key Key;
-/// The value type of the InversableMap.
+/// The value type of the InvertableMap.
 typedef typename _Map::Value Value;
-typedef std::map<Value, Key> InverseMap;
-typedef typename _Map::ConstReference ConstReference;
 /// \brief Constructor.
 ///
-/// Construct a new InversableMap for the graph.
+/// Construct a new InvertableMap for the graph.
 ///
-InversableMap(const Graph& graph) : Map(graph) {}
+InvertableMap(const Graph& graph) : Map(graph) {}
 /// \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 InverseMap::iterator it = invMap.find(oldval);
+typename Container::iterator it = invMap.find(oldval);
 if (it != invMap.end() && it->second == key) {
 	invMap.erase(it);
 }
 invMap.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.
-ConstReference operator[](const Key& key) const {
+const Value operator[](const Key& key) const {
 return Map::operator[](key);
 }
 /// \brief Add a new key to 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 InverseMap::iterator it = invMap.find(val);
+typename Container::iterator it = invMap.find(val);
 if (it != invMap.end() && it->second == key) {
 	invMap.erase(it);
 }
 Map::erase(key);
 }
 virtual void clear() {
 invMap.clear();
 Map::clear();
 }
+private:
+typedef std::map<Value, Key> Container;
+Container invMap;
+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.
+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 {
+	typename Container::const_iterator it = inverted.invMap.find(key);
+	return it->second;
+}
+private:
+const InvertableMap& inverted;
+};
 /// \brief It gives back the just readeable inverse map.
 ///
 /// It gives back the just readeable inverse map.
-const InverseMap& inverse() const {
+InverseMap inverse() const {
-return invMap;
+return InverseMap(*this);
 }
-private:
-InverseMap invMap;
 };
 /// \brief Provides a mutable, continuous and unique descriptor for each
 /// item in the graph.
 ///
 /// The DescriptorMap class provides a mutable, continuous and immutable
-/// mapping for each item in the graph.
+/// mapping for each item in the graph. The value for an item may mutated
+/// on each operation when the an item erased or added to graph.
 ///
 /// \param _Graph The graph class the \c DescriptorMap belongs to.
 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
 /// UndirEdge.
 /// \param _Map A ReadWriteMap mapping from the item type to integer.
 template <
 typename _Graph,
 typename _Item,
-typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int>
+typename _Map
+= typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent
 >
 class DescriptorMap : protected _Map {
 typedef _Item Item;
 typedef _Map Map;
 /// The key type of DescriptorMap (Node, Edge, UndirEdge).
 typedef typename _Map::Key Key;
 /// The value type of DescriptorMap.
 typedef typename _Map::Value Value;
-typedef std::vector<Item> InverseMap;
 /// \brief Constructor.
 ///
-/// Constructor for creating descriptor map.
+/// Constructor for descriptor map.
 DescriptorMap(const Graph& _graph) : Map(_graph) {
 build();
 }
 /// \brief Add a new key to the map.
 /// Erase the key to the map. It is called by the
 /// \c AlterationNotifier.
 virtual void erase(const Item& item) {
 Map::set(invMap.back(), Map::operator[](item));
 invMap[Map::operator[](item)] = invMap.back();
+invMap.pop_back();
 Map::erase(item);
 }
 /// \brief Build the unique map.
 ///
 /// Gives back the mutable and unique \e descriptor of the map.
 int operator[](const Item& item) const {
 return Map::operator[](item);
 }
+private:
+typedef std::vector<Item> Container;
+Container invMap;
+public:
+/// \brief The inverse map type.
+///
+/// The inverse map type.
+class InverseMap {
+public:
+/// \brief Constructor of the InverseMap.
+///
+/// Constructor of the InverseMap.
+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.invMap[key];
+}
+private:
+const DescriptorMap& inverted;
+};
 /// \brief Gives back the inverse of the map.
 ///
 /// Gives back the inverse of the map.
 const InverseMap inverse() const {
-return invMap;
+return InverseMap(*this);
 }
-private:
-std::vector<Item> invMap;
 };
 /// \brief Returns the source of the given edge.
 ///
 /// The SourceMap gives back the source Node of the given edge.

changeset 1414	01d9d6bc1284
parent 1402	655d8e78454d
child 1419	c3244a26adb1