LEMON/LEMON-official Changeset - r741:71939d63ae77

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r741:71939d63ae77

« 740:7bda78

768:99124e »
742:8dae88 »

r741:71939d63ae77

Tue, 21 Jul 2009 22:43:31

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Improvements for iterable maps (#73)

0 2 0

default

2 files changed with 133 insertions and 123 deletions:

lemon/maps.h

126

117

test/maps_test.cc

↑ Collapse diff ↑

lemon/maps.h

Show inline comments

@@ -24,5 +24,5 @@
 		#include <vector>
 		#include <map>
 		#include <lemon/core.h>
 		#include <lemon/smart_graph.h>
@@ -32,4 +32,2 @@
 		#include <map>
 		namespace lemon {
@@ -1908,3 +1906,2 @@
 		  /// in the inverse map.
 		  ///
 		  /// The values of the map can be accessed
@@ -1912,2 +1909,5 @@
 		  ///
 		  /// This type is not reference map, so it cannot be modified with
 		  /// the subscription operator.
 		  ///
 		  /// \tparam GR The graph type.
@@ -2314,14 +2314,21 @@
 		  /// \brief Dynamic iterable bool map.
+		  /// \brief Dynamic iterable \c bool map.
 		  ///
 		  /// This class provides a special graph map type which can store for
 		  /// each graph item(node, arc, edge, etc.) a bool value. For both
 		  /// the true and the false values it is possible to iterate on the
 		  /// keys.
 		  /// 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.
 		  ///
 		  /// \param GR The graph type.
 		  /// \param ITEM One of the graph's item types, the key of the map.
-		  template <typename GR, typename ITEM>
+		  /// This type is a reference map, so it can be modified with the
 		  /// subscription operator.
 		  ///
 		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
 		  /// \c GR::Edge).
 		  ///
 		  /// \see IterableIntMap, IterableValueMap
 		  /// \see CrossRefMap
 		  template <typename GR, typename K>
 		  class IterableBoolMap
-		    : protected ItemSetTraits<GR, ITEM>::template Map<int>::Type {
+		    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
 		  private:
@@ -2329,6 +2336,6 @@
 		    typedef typename ItemSetTraits<Graph, ITEM>::ItemIt KeyIt;
 		    typedef typename ItemSetTraits<GR, ITEM>::template Map<int>::Type Parent;
 		    std::vector<ITEM> _array;
 		    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
 		    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
 		    std::vector<K> _array;
 		    int _sep;
@@ -2337,3 +2344,3 @@
-		    /// Indicates that the map if reference map.
+		    /// Indicates that the map is reference map.
 		    typedef True ReferenceMapTag;
@@ -2341,3 +2348,3 @@
 		    /// The key type
-		    typedef ITEM Key;
+		    typedef K Key;
 		    /// The value type
@@ -2355,6 +2362,6 @@
-		    /// \brief Refernce to the value of the map.
+		    /// \brief Reference to the value of the map.
 		    ///
 		    /// This class is similar to the bool type. It can be converted to
 		    /// bool and it provides the same operators.
 		    /// This class is similar to the \c bool type. It can be converted to
 		    /// \c bool and it provides the same operators.
 		    class Reference {
@@ -2456,5 +2463,5 @@
 		    /// \brief Returns the number of the keys mapped to true.
+		    /// \brief Returns the number of the keys mapped to \c true.
 		    ///
 		    /// Returns the number of the keys mapped to true.
+		    /// Returns the number of the keys mapped to \c true.
 		    int trueNum() const {
@@ -2463,5 +2470,5 @@
 		    /// \brief Returns the number of the keys mapped to false.
+		    /// \brief Returns the number of the keys mapped to \c false.
 		    ///
 		    /// Returns the number of the keys mapped to false.
+		    /// Returns the number of the keys mapped to \c false.
 		    int falseNum() const {
@@ -2470,8 +2477,8 @@
 		    /// \brief Iterator for the keys mapped to true.
+		    /// \brief Iterator for the keys mapped to \c true.
 		    ///
 		    /// Iterator for the keys mapped to true. It works
 		    /// like a graph item iterator in the map, it can be converted
 		    /// Iterator for the keys mapped to \c true. It works
 		    /// like a graph item iterator, it can be converted to
 		    /// the key type of the map, incremented with \c ++ operator, and
-		    /// if the iterator leave the last valid key it will be equal to
+		    /// if the iterator leaves the last valid key, it will be equal to
 		    /// \c INVALID.
@@ -2484,4 +2491,4 @@
 		      /// Creates an iterator. It iterates on the
 		      /// keys which mapped to true.
 		      /// \param map The IterableIntMap
 		      /// keys mapped to \c true.
 		      /// \param map The IterableBoolMap.
 		      explicit TrueIt(const IterableBoolMap& map)
@@ -2492,3 +2499,3 @@
 		      ///
-		      /// This constructor initializes the key to be invalid.
+		      /// This constructor initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
@@ -2498,3 +2505,3 @@
 		      ///
-		      /// Increment Operator.
+		      /// Increment operator.
 		      TrueIt& operator++() {
@@ -2505,3 +2512,2 @@
 		    private:
@@ -2510,8 +2516,8 @@
 		    /// \brief Iterator for the keys mapped to false.
+		    /// \brief Iterator for the keys mapped to \c false.
 		    ///
 		    /// Iterator for the keys mapped to false. It works
 		    /// like a graph item iterator in the map, it can be converted
 		    /// Iterator for the keys mapped to \c false. It works
 		    /// like a graph item iterator, it can be converted to
 		    /// the key type of the map, incremented with \c ++ operator, and
-		    /// if the iterator leave the last valid key it will be equal to
+		    /// if the iterator leaves the last valid key, it will be equal to
 		    /// \c INVALID.
@@ -2524,4 +2530,4 @@
 		      /// Creates an iterator. It iterates on the
 		      /// keys which mapped to false.
 		      /// \param map The IterableIntMap
 		      /// keys mapped to \c false.
 		      /// \param map The IterableBoolMap.
 		      explicit FalseIt(const IterableBoolMap& map)
@@ -2532,3 +2538,3 @@
 		      ///
-		      /// This constructor initializes the key to be invalid.
+		      /// This constructor initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
@@ -2538,3 +2544,3 @@
 		      ///
-		      /// Increment Operator.
+		      /// Increment operator.
 		      FalseIt& operator++() {
@@ -2552,5 +2558,5 @@
 		    /// Iterator for the keys mapped to a given value. It works
-		    /// like a graph item iterator in the map, it can be converted
+		    /// like a graph item iterator, it can be converted to
 		    /// the key type of the map, incremented with \c ++ operator, and
-		    /// if the iterator leave the last valid key it will be equal to
+		    /// if the iterator leaves the last valid key, it will be equal to
 		    /// \c INVALID.
@@ -2560,8 +2566,8 @@
 		      /// \brief Creates an iterator.
+		      /// \brief Creates an iterator with a value.
 		      ///
 		      /// Creates an iterator. It iterates on the
 		      /// keys which mapped to false.
 		      /// \param map The IterableIntMap
 		      /// \param value Which elements should be iterated.
 		      /// Creates an iterator with a value. It iterates on the
 		      /// keys mapped to the given value.
 		      /// \param map The IterableBoolMap.
 		      /// \param value The value.
 		      ItemIt(const IterableBoolMap& map, bool value)
@@ -2575,3 +2581,3 @@
 		      ///
-		      /// This constructor initializes the key to be invalid.
+		      /// This constructor initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
@@ -2581,3 +2587,3 @@
 		      ///
-		      /// Increment Operator.
+		      /// Increment operator.
 		      ItemIt& operator++() {
@@ -2675,26 +2681,31 @@
 		  ///\ingroup graph_maps
 		  ///
 		  /// \brief Dynamic iterable integer map.
 		  ///
 		  /// This class provides a special graph map type which can store
 		  /// for each graph item(node, edge, etc.) an integer value. For each
 		  /// non negative value it is possible to iterate on the keys which
 		  /// mapped to the given value.
 		  /// This class provides a special graph map type which can store an
 		  /// integer value for graph items (\c Node, \c Arc or \c Edge).
 		  /// For each non-negative value it is possible to iterate on the keys
 		  /// mapped to the value.
 		  ///
-		  /// \note The size of the data structure depends on the highest
+		  /// This type is a reference map, so it can be modified with the
 		  /// subscription operator.
 		  ///
 		  /// \note The size of the data structure depends on the largest
 		  /// value in the map.
 		  ///
 		  /// \param GR The graph type.
 		  /// \param ITEM One of the graph's item type, the key of the map.
-		  template <typename GR, typename ITEM>
+		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
 		  /// \c GR::Edge).
 		  ///
 		  /// \see IterableBoolMap, IterableValueMap
 		  /// \see CrossRefMap
 		  template <typename GR, typename K>
 		  class IterableIntMap
 		    : protected ItemSetTraits<GR, ITEM>::
 		        template Map<_maps_bits::IterableIntMapNode<ITEM> >::Type {
 		    : protected ItemSetTraits<GR, K>::
 		        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
 		  public:
 		    typedef typename ItemSetTraits<GR, ITEM>::
 		      template Map<_maps_bits::IterableIntMapNode<ITEM> >::Type Parent;
 		    typedef typename ItemSetTraits<GR, K>::
 		      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
 		    /// The key type
-		    typedef ITEM Key;
+		    typedef K Key;
 		    /// The value type
@@ -2706,3 +2717,3 @@
 		    ///
-		    /// Constructor of the map. It set all values to -1.
+		    /// Constructor of the map. It sets all values to -1.
 		    explicit IterableIntMap(const Graph& graph)
@@ -2714,3 +2725,3 @@
 		    explicit IterableIntMap(const Graph& graph, int value)
-		      : Parent(graph, _maps_bits::IterableIntMapNode<ITEM>(value)) {
+		      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
 		      if (value >= 0) {
@@ -2756,9 +2767,9 @@
-		    /// Indicates that the map if reference map.
+		    /// Indicates that the map is reference map.
 		    typedef True ReferenceMapTag;
-		    /// \brief Refernce to the value of the map.
+		    /// \brief Reference to the value of the map.
 		    ///
 		    /// This class is similar to the int type. It can
 		    /// be converted to int and it has the same operators.
 		    /// This class is similar to the \c int type. It can
 		    /// be converted to \c int and it has the same operators.
 		    class Reference {
@@ -2883,9 +2894,9 @@
 		    /// Iterator for the keys with the same value. It works
-		    /// like a graph item iterator in the map, it can be converted
+		    /// like a graph item iterator, it can be converted to
 		    /// the item type of the map, incremented with \c ++ operator, and
-		    /// if the iterator leave the last valid item it will be equal to
+		    /// if the iterator leaves the last valid item, it will be equal to
 		    /// \c INVALID.
-		    class ItemIt : public ITEM {
+		    class ItemIt : public Key {
 		    public:
-		      typedef ITEM Parent;
+		      typedef Key Parent;
@@ -2893,3 +2904,3 @@
 		      ///
-		      /// This constructor initializes the item to be invalid.
+		      /// This constructor initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
@@ -2900,5 +2911,5 @@
 		      /// Creates an iterator with a value. It iterates on the
 		      /// keys which have the given value.
 		      /// \param map The IterableIntMap
-		      /// \param value The value
+		      /// keys mapped to the given value.
 		      /// \param map The IterableIntMap.
 		      /// \param value The value.
 		      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
@@ -2913,3 +2924,3 @@
 		      ///
-		      /// Increment Operator.
+		      /// Increment operator.
 		      ItemIt& operator++() {
@@ -2920,3 +2931,2 @@
 		    private:
@@ -2945,3 +2955,3 @@
 		  private:
-		    std::vector<ITEM> _first;
+		    std::vector<Key> _first;
 		  };
@@ -2957,10 +2967,10 @@
 		  ///\ingroup graph_maps
 		  ///
 		  /// \brief Dynamic iterable map for comparable values.
 		  ///
 		  /// This class provides a special graph map type which can store
 		  /// for each graph item(node, edge, etc.) a value. For each
 		  /// value it is possible to iterate on the keys which mapped to the
 		  /// given value. The type stores for each value a linked list with
 		  /// This class provides a special graph map type which can store an
 		  /// 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 map stores for each value a linked list with
 		  /// the items which mapped to the value, and the values are stored
@@ -2969,22 +2979,25 @@
 		  ///
 		  /// This type is not reference map so it cannot be modified with
+		  /// This type is not reference map, so it cannot be modified with
 		  /// the subscription operator.
 		  ///
-		  /// \see InvertableMap
+		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
 		  /// \c GR::Edge).
 		  /// \tparam V The value type of the map. It can be any comparable
 		  /// value type.
 		  ///
 		  /// \param GR The graph type.
 		  /// \param ITEM One of the graph's item type, the key of the map.
 		  /// \param VAL Any comparable value type.
 		  template <typename GR, typename ITEM, typename VAL>
 		  /// \see IterableBoolMap, IterableIntMap
 		  /// \see CrossRefMap
 		  template <typename GR, typename K, typename V>
 		  class IterableValueMap
 		    : protected ItemSetTraits<GR, ITEM>::
 		        template Map<_maps_bits::IterableValueMapNode<ITEM, VAL> >::Type {
 		    : protected ItemSetTraits<GR, K>::
 		        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
 		  public:
 		    typedef typename ItemSetTraits<GR, ITEM>::
 		      template Map<_maps_bits::IterableValueMapNode<ITEM, VAL> >::Type Parent;
 		    typedef typename ItemSetTraits<GR, K>::
 		      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
 		    /// The key type
-		    typedef ITEM Key;
+		    typedef K Key;
 		    /// The value type
-		    typedef VAL Value;
+		    typedef V Value;
 		    /// The graph type
@@ -2994,8 +3007,8 @@
-		    /// \brief Constructor of the Map with a given value.
+		    /// \brief Constructor of the map with a given value.
 		    ///
-		    /// Constructor of the Map with a given value.
+		    /// Constructor of the map with a given value.
 		    explicit IterableValueMap(const Graph& graph,
 		                              const Value& value = Value())
-		      : Parent(graph, _maps_bits::IterableValueMapNode<ITEM, VAL>(value)) {
+		      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
 		      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
@@ -3028,5 +3041,2 @@
 		        node.prev = node.next = INVALID;
 		        if (node.next != INVALID) {
 		          Parent::operator[](node.next).prev = key;
+		        }
 		        _first.insert(std::make_pair(node.value, key));
@@ -3048,4 +3058,3 @@
 		    /// iterator on the values of the map. The values can
 		    /// be accessed in the [beginValue, endValue) range.
 		    ///
 		    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
 		    class ValueIterator
@@ -3081,3 +3090,3 @@
 		    /// first value of the map. The values of the
 		    /// map can be accessed in the [beginValue, endValue)
+		    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 		    /// range.
@@ -3091,3 +3100,3 @@
 		    /// last value of the map. The values of the
 		    /// map can be accessed in the [beginValue, endValue)
+		    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 		    /// range.
@@ -3116,9 +3125,9 @@
 		    /// Iterator for the keys with the same value. It works
-		    /// like a graph item iterator in the map, it can be converted
+		    /// like a graph item iterator, it can be converted to
 		    /// the item type of the map, incremented with \c ++ operator, and
-		    /// if the iterator leave the last valid item it will be equal to
+		    /// if the iterator leaves the last valid item, it will be equal to
 		    /// \c INVALID.
-		    class ItemIt : public ITEM {
+		    class ItemIt : public Key {
 		    public:
-		      typedef ITEM Parent;
+		      typedef Key Parent;
@@ -3126,3 +3135,3 @@
 		      ///
-		      /// This constructor initializes the item to be invalid.
+		      /// This constructor initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.

test/maps_test.cc

Show inline comments

@@ -24,2 +24,3 @@
 		#include <lemon/maps.h>
 		#include <lemon/smart_graph.h>
@@ -357,3 +358,3 @@
 		    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
-		    checkConcept<ReadWriteMap<Item, int>, Ibm>();
+		    checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
@@ -438,3 +439,3 @@
-		    checkConcept<ReadWriteMap<Item, int>, Iim>();
+		    checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
@@ -469,3 +470,3 @@
 		    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
-		      check(map1[static_cast<Item>(it)] == 0, "Wrong Value");
+		      check(map1[static_cast<Item>(it)] == 0, "Wrong value");
 		      ++n;
@@ -475,3 +476,3 @@
 		    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
-		      check(map1[static_cast<Item>(it)] == 1, "Wrong Value");
+		      check(map1[static_cast<Item>(it)] == 1, "Wrong value");
 		      ++n;
@@ -526,3 +527,3 @@
 		    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
-		      check(map1[static_cast<Item>(it)] == 0.0, "Wrong Value");
+		      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
 		      ++n;
@@ -532,3 +533,3 @@
 		    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
-		      check(map1[static_cast<Item>(it)] == 1.0, "Wrong Value");
+		      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
 		      ++n;

0 comments (0 inline)

RhodeCode

Login to your account