diff --git a/lemon/maps.h b/lemon/maps.h
--- a/lemon/maps.h
+++ b/lemon/maps.h
@@ -56,7 +56,7 @@
/// its type definitions, or if you have to provide a writable map,
/// but data written to it is not required (i.e. it will be sent to
/// /dev/null).
- /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+ /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
///
/// \sa ConstMap
template
@@ -89,7 +89,7 @@
/// value to each key.
///
/// In other aspects it is equivalent to \c NullMap.
- /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
+ /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
/// concept, but it absorbs the data written to it.
///
/// The simplest way of using this map is through the constMap()
@@ -158,7 +158,7 @@
/// value to each key.
///
/// In other aspects it is equivalent to \c NullMap.
- /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
+ /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
/// concept, but it absorbs the data written to it.
///
/// The simplest way of using this map is through the constMap()
@@ -232,7 +232,7 @@
/// values to integer keys from the range [0..size-1].
/// It can be used with some data structures, for example
/// \c UnionFind, \c BinHeap, when the used items are small
- /// integers. This map conforms the \ref concepts::ReferenceMap
+ /// integers. This map conforms to the \ref concepts::ReferenceMap
/// "ReferenceMap" concept.
///
/// The simplest way of using this map is through the rangeMap()
@@ -340,7 +340,7 @@
/// that you can specify a default value for the keys that are not
/// stored actually. This value can be different from the default
/// contructed value (i.e. \c %Value()).
- /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
+ /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
/// concept.
///
/// This map is useful if a default value should be assigned to most of
@@ -706,7 +706,7 @@
/// "readable map" to another type using the default conversion.
/// The \c Key type of it is inherited from \c M and the \c Value
/// type is \c V.
- /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
+ /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
///
/// The simplest way of using this map is through the convertMap()
/// function.
@@ -1789,11 +1789,11 @@
/// order of Dfs algorithm, as the following examples show.
/// \code
/// std::vector v;
- /// dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
+ /// dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
/// \endcode
/// \code
/// std::vector v(countNodes(g));
- /// dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
+ /// dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
/// \endcode
///
/// \note The container of the iterator must contain enough space
@@ -1825,7 +1825,7 @@
/// Using this map you get access (i.e. can read) the inner id values of
/// the items stored in the graph, which is returned by the \c id()
/// function of the graph. This map can be inverted with its member
- /// class \c InverseMap or with the \c operator() member.
+ /// class \c InverseMap or with the \c operator()() member.
///
/// \tparam GR The graph type.
/// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
@@ -1865,9 +1865,11 @@
public:
- /// \brief This class represents the inverse of its owner (IdMap).
+ /// \brief The inverse map type of IdMap.
///
- /// This class represents the inverse of its owner (IdMap).
+ /// The inverse map type of IdMap. The subscript operator gives back
+ /// an item by its id.
+ /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
/// \see inverse()
class InverseMap {
public:
@@ -1882,9 +1884,9 @@
/// Constructor for creating an id-to-item map.
explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
- /// \brief Gives back the given item from its id.
+ /// \brief Gives back an item by its id.
///
- /// Gives back the given item from its id.
+ /// Gives back an item by its id.
Item operator[](int id) const { return _graph->fromId(id, Item());}
private:
@@ -1897,14 +1899,31 @@
InverseMap inverse() const { return InverseMap(*_graph);}
};
+ /// \brief Returns an \c IdMap class.
+ ///
+ /// This function just returns an \c IdMap class.
+ /// \relates IdMap
+ template
+ inline IdMap idMap(const GR& graph) {
+ return IdMap(graph);
+ }
/// \brief General cross reference graph map type.
/// This class provides simple invertable graph maps.
/// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
/// and if a key is set to a new value, then stores it in the inverse map.
- /// The values of the map can be accessed
- /// with stl compatible forward iterator.
+ /// The graph items can be accessed by their values either using
+ /// \c InverseMap or \c operator()(), and the values of the map can be
+ /// accessed with an STL compatible forward iterator (\c ValueIt).
+ ///
+ /// This map is intended to be used when all associated values are
+ /// different (the map is actually invertable) or there are only a few
+ /// items with the same value.
+ /// Otherwise consider to use \c IterableValueMap, which is more
+ /// suitable and more efficient for such cases. It provides iterators
+ /// to traverse the items with the same associated value, however
+ /// it does not have \c InverseMap.
///
/// This type is not reference map, so it cannot be modified with
/// the subscript operator.
@@ -1945,56 +1964,66 @@
/// \brief Forward iterator for values.
///
- /// This iterator is an stl compatible forward
+ /// This iterator is an STL compatible forward
/// iterator on the values of the map. The values can
/// be accessed in the [beginValue, endValue) range.
/// They are considered with multiplicity, so each value is
/// traversed for each item it is assigned to.
- class ValueIterator
+ class ValueIt
: public std::iterator {
friend class CrossRefMap;
private:
- ValueIterator(typename Container::const_iterator _it)
+ ValueIt(typename Container::const_iterator _it)
: it(_it) {}
public:
- ValueIterator() {}
-
- ValueIterator& operator++() { ++it; return *this; }
- ValueIterator operator++(int) {
- ValueIterator tmp(*this);
+ /// Constructor
+ ValueIt() {}
+
+ /// \e
+ ValueIt& operator++() { ++it; return *this; }
+ /// \e
+ ValueIt operator++(int) {
+ ValueIt tmp(*this);
operator++();
return tmp;
}
+ /// \e
const Value& operator*() const { return it->first; }
+ /// \e
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; }
+ /// \e
+ bool operator==(ValueIt jt) const { return it == jt.it; }
+ /// \e
+ bool operator!=(ValueIt jt) const { return it != jt.it; }
private:
typename Container::const_iterator it;
};
+
+ /// Alias for \c ValueIt
+ typedef ValueIt ValueIterator;
/// \brief Returns an iterator to the first value.
///
- /// Returns an stl compatible iterator to the
+ /// 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());
+ ValueIt beginValue() const {
+ return ValueIt(_inv_map.begin());
}
/// \brief Returns an iterator after the last value.
///
- /// Returns an stl compatible iterator after the
+ /// 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());
+ ValueIt endValue() const {
+ return ValueIt(_inv_map.end());
}
/// \brief Sets the value associated with the given key.
@@ -2032,6 +2061,14 @@
typename Container::const_iterator it = _inv_map.find(val);
return it != _inv_map.end() ? it->second : INVALID;
}
+
+ /// \brief Returns the number of items with the given value.
+ ///
+ /// This function returns the number of items with the given value
+ /// associated with it.
+ int count(const Value &val) const {
+ return _inv_map.count(val);
+ }
protected:
@@ -2082,10 +2119,12 @@
public:
- /// \brief The inverse map type.
+ /// \brief The inverse map type of CrossRefMap.
///
- /// The inverse of this map. The subscript operator of the map
- /// gives back the item that was last assigned to the value.
+ /// The inverse map type of CrossRefMap. The subscript operator gives
+ /// back an item by its value.
+ /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
+ /// \see inverse()
class InverseMap {
public:
/// \brief Constructor
@@ -2112,20 +2151,20 @@
const CrossRefMap& _inverted;
};
- /// \brief It gives back the read-only inverse map.
+ /// \brief Gives back the inverse of the map.
///
- /// It gives back the read-only inverse map.
+ /// Gives back the inverse of the CrossRefMap.
InverseMap inverse() const {
return InverseMap(*this);
}
};
- /// \brief Provides continuous and unique ID for the
+ /// \brief Provides continuous and unique id for the
/// items of a graph.
///
/// RangeIdMap provides a unique and continuous
- /// ID for each item of a given type (\c Node, \c Arc or
+ /// id for each item of a given type (\c Node, \c Arc or
/// \c Edge) in a graph. This id is
/// - \b unique: different items get different ids,
/// - \b continuous: the range of the ids is the set of integers
@@ -2136,7 +2175,7 @@
/// Thus this id is not (necessarily) the same as what can get using
/// the \c id() function of the graph or \ref IdMap.
/// This map can be inverted with its member class \c InverseMap,
- /// or with the \c operator() member.
+ /// or with the \c operator()() member.
///
/// \tparam GR The graph type.
/// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
@@ -2264,16 +2303,16 @@
_inv_map[pi] = q;
}
- /// \brief Gives back the \e RangeId of the item
+ /// \brief Gives back the \e range \e id of the item
///
- /// Gives back the \e RangeId of the item.
+ /// Gives back the \e range \e id of the item.
int operator[](const Item& item) const {
return Map::operator[](item);
}
- /// \brief Gives back the item belonging to a \e RangeId
+ /// \brief Gives back the item belonging to a \e range \e id
///
- /// Gives back the item belonging to a \e RangeId.
+ /// Gives back the item belonging to the given \e range \e id.
Item operator()(int id) const {
return _inv_map[id];
}
@@ -2287,7 +2326,9 @@
/// \brief The inverse map type of RangeIdMap.
///
- /// The inverse map type of RangeIdMap.
+ /// The inverse map type of RangeIdMap. The subscript operator gives
+ /// back an item by its \e range \e id.
+ /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
class InverseMap {
public:
/// \brief Constructor
@@ -2305,7 +2346,7 @@
/// \brief Subscript operator.
///
/// Subscript operator. It gives back the item
- /// that the descriptor currently belongs to.
+ /// that the given \e range \e id currently belongs to.
Value operator[](const Key& key) const {
return _inverted(key);
}
@@ -2323,18 +2364,27 @@
/// \brief Gives back the inverse of the map.
///
- /// Gives back the inverse of the map.
+ /// Gives back the inverse of the RangeIdMap.
const InverseMap inverse() const {
return InverseMap(*this);
}
};
+ /// \brief Returns a \c RangeIdMap class.
+ ///
+ /// This function just returns an \c RangeIdMap class.
+ /// \relates RangeIdMap
+ template
+ inline RangeIdMap rangeIdMap(const GR& graph) {
+ return RangeIdMap(graph);
+ }
+
/// \brief Dynamic iterable \c bool map.
///
/// This class provides a special graph map type which can store a
/// \c bool value for graph items (\c Node, \c Arc or \c Edge).
/// For both \c true and \c false values it is possible to iterate on
- /// the keys.
+ /// the keys mapped to the value.
///
/// This type is a reference map, so it can be modified with the
/// subscript operator.
@@ -2703,6 +2753,11 @@
/// For each non-negative value it is possible to iterate on the keys
/// mapped to the value.
///
+ /// This map is intended to be used with small integer values, for which
+ /// it is efficient, and supports iteration only for non-negative values.
+ /// If you need large values and/or iteration for negative integers,
+ /// consider to use \ref IterableValueMap instead.
+ ///
/// This type is a reference map, so it can be modified with the
/// subscript operator.
///
@@ -2984,15 +3039,17 @@
/// \brief Dynamic iterable map for comparable values.
///
- /// This class provides a special graph map type which can store an
+ /// This class provides a special graph map type which can store a
/// comparable value for graph items (\c Node, \c Arc or \c Edge).
/// For each value it is possible to iterate on the keys mapped to
- /// the value.
+ /// the value (\c ItemIt), and the values of the map can be accessed
+ /// with an STL compatible forward iterator (\c ValueIt).
+ /// The map stores a linked list for each value, which contains
+ /// the items mapped to the value, and the used values are stored
+ /// in balanced binary tree (\c std::map).
///
- /// The map stores for each value a linked list with
- /// the items which mapped to the value, and the values are stored
- /// in balanced binary tree. The values of the map can be accessed
- /// with stl compatible forward iterator.
+ /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
+ /// specialized for \c bool and \c int values, respectively.
///
/// This type is not reference map, so it cannot be modified with
/// the subscript operator.
@@ -3071,31 +3128,38 @@
/// \brief Forward iterator for values.
///
- /// This iterator is an stl compatible forward
+ /// 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
+ class ValueIt
: public std::iterator {
friend class IterableValueMap;
private:
- ValueIterator(typename std::map::const_iterator _it)
+ ValueIt(typename std::map::const_iterator _it)
: it(_it) {}
public:
- ValueIterator() {}
-
- ValueIterator& operator++() { ++it; return *this; }
- ValueIterator operator++(int) {
- ValueIterator tmp(*this);
+ /// Constructor
+ ValueIt() {}
+
+ /// \e
+ ValueIt& operator++() { ++it; return *this; }
+ /// \e
+ ValueIt operator++(int) {
+ ValueIt tmp(*this);
operator++();
return tmp;
}
+ /// \e
const Value& operator*() const { return it->first; }
+ /// \e
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; }
+ /// \e
+ bool operator==(ValueIt jt) const { return it == jt.it; }
+ /// \e
+ bool operator!=(ValueIt jt) const { return it != jt.it; }
private:
typename std::map::const_iterator it;
@@ -3103,22 +3167,22 @@
/// \brief Returns an iterator to the first value.
///
- /// Returns an stl compatible iterator to the
+ /// 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(_first.begin());
+ ValueIt beginValue() const {
+ return ValueIt(_first.begin());
}
/// \brief Returns an iterator after the last value.
///
- /// Returns an stl compatible iterator after the
+ /// 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(_first.end());
+ ValueIt endValue() const {
+ return ValueIt(_first.end());
}
/// \brief Set operation of the map.
@@ -3236,9 +3300,9 @@
class SourceMap {
public:
- ///\e
+ /// The key type (the \c Arc type of the digraph).
typedef typename GR::Arc Key;
- ///\e
+ /// The value type (the \c Node type of the digraph).
typedef typename GR::Node Value;
/// \brief Constructor
@@ -3277,9 +3341,9 @@
class TargetMap {
public:
- ///\e
+ /// The key type (the \c Arc type of the digraph).
typedef typename GR::Arc Key;
- ///\e
+ /// The value type (the \c Node type of the digraph).
typedef typename GR::Node Value;
/// \brief Constructor
@@ -3319,8 +3383,10 @@
class ForwardMap {
public:
+ /// The key type (the \c Edge type of the digraph).
+ typedef typename GR::Edge Key;
+ /// The value type (the \c Arc type of the digraph).
typedef typename GR::Arc Value;
- typedef typename GR::Edge Key;
/// \brief Constructor
///
@@ -3359,8 +3425,10 @@
class BackwardMap {
public:
+ /// The key type (the \c Edge type of the digraph).
+ typedef typename GR::Edge Key;
+ /// The value type (the \c Arc type of the digraph).
typedef typename GR::Arc Value;
- typedef typename GR::Edge Key;
/// \brief Constructor
///