LEMON/LEMON-official Changeset - r161:2c999941b871

Repositories » LEMON » LEMON-official

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

Changeset - r161:2c999941b871

« 159:c7d30f
« 160:b1bd0c

162:33247f »

r161:2c999941b871

Mon, 26 May 2008 14:50:47

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 2 0

merge default

0 files changed with 74 insertions and 18 deletions:

lemon/maps.h

test/maps_test.cc

↑ Collapse diff ↑

lemon/maps.h

Show inline comments

@@ -1653,100 +1653,134 @@
 		    typedef typename Parent::Value Value;
 		    /// Constructor
 		    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// \e
 		    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
 		  };
 		  /// Returns an \ref LessMap class
 		  /// This function just returns an \ref LessMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are maps with keys and values of
 		  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]<m2[x]</tt>.
 		  ///
 		  /// \relates LessMap
 		  template<typename M1, typename M2>
 		  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
 		    return LessMap<M1, M2>(m1,m2);
+		  }
 		  namespace _maps_bits {
 		    template <typename Value>
 		    struct Identity {
 		      typedef Value argument_type;
 		      typedef Value result_type;
 		      Value operator()(const Value& val) const {
 			return val;
+		      }
 		    };
 		    template <typename _Iterator, typename Enable = void>
 		    struct IteratorTraits {
 		      typedef typename std::iterator_traits<_Iterator>::value_type Value;
 		    };
 		    template <typename _Iterator>
 		    struct IteratorTraits<_Iterator,
 		      typename exists<typename _Iterator::container_type>::type>
+		    {
 		      typedef typename _Iterator::container_type::value_type Value;
 		    };
+		  }
 		  /// \brief Writable bool map for logging each \c true assigned element
 		  ///
-		  /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
+		  /// A \ref concepts::WriteMap "writable" bool map for logging
 		  /// each \c true assigned element, i.e it copies subsequently each
 		  /// keys set to \c true to the given iterator.
 		  /// The most important usage of it is storing certain nodes or arcs
 		  /// that were marked \c true by an algorithm.
 		  ///
 		  /// \tparam It the type of the Iterator.
 		  /// \tparam Ke the type of the map's Key. The default value should
-		  /// work in most cases.
+		  /// There are several algorithms that provide solutions through bool
 		  /// maps and most of them assign \c true at most once for each key.
 		  /// In these cases it is a natural request to store each \c true
 		  /// assigned elements (in order of the assignment), which can be
 		  /// easily done with StoreBoolMap.
 		  ///
 		  /// The simplest way of using this map is through the storeBoolMap()
 		  /// function.
 		  ///
 		  /// \tparam It The type of the iterator.
 		  /// \tparam Ke The key type of the map. The default value set
 		  /// according to the iterator type should work in most cases.
 		  ///
 		  /// \note The container of the iterator must contain enough space
 		  /// for the elements. (Or it should be an inserter iterator).
 		  ///
-		  /// \todo Revise the name of this class and give an example code.
+		  /// for the elements or the iterator should be an inserter iterator.
 		#ifdef DOXYGEN
 		  template <typename It, typename Ke>
 		#else
 		  template <typename It,
 			    typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
 		#endif
 		  class StoreBoolMap {
 		  public:
 		    typedef It Iterator;
 		    typedef Ke Key;
 		    typedef bool Value;
 		    /// Constructor
 		    StoreBoolMap(Iterator it)
 		      : _begin(it), _end(it) {}
 		    /// Gives back the given iterator set for the first key
 		    Iterator begin() const {
 		      return _begin;
+		    }
 		    /// Gives back the the 'after the last' iterator
 		    Iterator end() const {
 		      return _end;
+		    }
 		    /// The set function of the map
-		    void set(const Key& key, Value value) const {
 		    void set(const Key& key, Value value) {
 		      if (value) {
 			*_end++ = key;
+		      }
+		    }
 		  private:
 		    Iterator _begin;
-		    mutable Iterator _end;
 		    Iterator _end;
 		  };
 		  /// Returns a \ref StoreBoolMap class
 		  /// This function just returns a \ref StoreBoolMap class.
 		  ///
 		  /// The most important usage of it is storing certain nodes or arcs
 		  /// that were marked \c true by an algorithm.
 		  /// For example it makes easier to store the nodes in the processing
 		  /// order of Dfs algorithm, as the following examples show.
 		  /// \code
 		  ///   std::vector<Node> v;
 		  ///   dfs(g,s).processedMap(storeBoolMap(std::back_inserter(v))).run();
 		  /// \endcode
 		  /// \code
 		  ///   std::vector<Node> v(countNodes(g));
 		  ///   dfs(g,s).processedMap(storeBoolMap(v.begin())).run();
 		  /// \endcode
 		  ///
 		  /// \note The container of the iterator must contain enough space
 		  /// for the elements or the iterator should be an inserter iterator.
 		  ///
 		  /// \note StoreBoolMap is just \ref concepts::WriteMap "writable", so
 		  /// it cannot be used when a readable map is needed, for example as
 		  /// \c ReachedMap for Bfs, Dfs and Dijkstra algorithms.
 		  ///
 		  /// \relates StoreBoolMap
 		  template<typename Iterator>
 		  inline StoreBoolMap<Iterator> storeBoolMap(Iterator it) {
 		    return StoreBoolMap<Iterator>(it);
+		  }
 		  /// @}
+		}
 		#endif // LEMON_MAPS_H

test/maps_test.cc

Show inline comments

@@ -283,27 +283,49 @@
 		    checkConcept<BoolMap, NotMap<BoolMap> >();
 		    checkConcept<BoolWriteMap, NotWriteMap<BoolWriteMap> >();
 		    checkConcept<BoolMap, EqualMap<DoubleMap,DoubleMap> >();
 		    checkConcept<BoolMap, LessMap<DoubleMap,DoubleMap> >();
 		    TrueMap<int> tm;
 		    FalseMap<int> fm;
 		    RangeMap<bool> rm(2);
 		    rm[0] = true; rm[1] = false;
 		    check(andMap(tm,rm)[0] && !andMap(tm,rm)[1] && !andMap(fm,rm)[0] && !andMap(fm,rm)[1],
 		          "Something is wrong with AndMap");
 		    check(orMap(tm,rm)[0] && orMap(tm,rm)[1] && orMap(fm,rm)[0] && !orMap(fm,rm)[1],
 		          "Something is wrong with OrMap");
 		    check(!notMap(rm)[0] && notMap(rm)[1], "Something is wrong with NotMap");
 		    check(!notWriteMap(rm)[0] && notWriteMap(rm)[1], "Something is wrong with NotWriteMap");
 		    ConstMap<int, double> cm(2.0);
 		    IdentityMap<int> im;
 		    ConvertMap<IdentityMap<int>, double> id(im);
 		    check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3],
 		          "Something is wrong with LessMap");
 		    check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3],
 		          "Something is wrong with EqualMap");
+		  }
 		  // StoreBoolMap
+		  {
 		    typedef std::vector<int> vec;
 		    vec v1;
 		    vec v2(10);
 		    StoreBoolMap<std::back_insert_iterator<vec> > map1(std::back_inserter(v1));
 		    StoreBoolMap<vec::iterator> map2(v2.begin());
 		    map1.set(10, false);
 		    map1.set(20, true);   map2.set(20, true);
 		    map1.set(30, false);  map2.set(40, false);
 		    map1.set(50, true);   map2.set(50, true);
 		    map1.set(60, true);   map2.set(60, true);
 		    check(v1.size() == 3 && v2.size() == 10 &&
 		          v1[0]==20 && v1[1]==50 && v1[2]==60 && v2[0]==20 && v2[1]==50 && v2[2]==60,
 		          "Something is wrong with StoreBoolMap");
 		    int i = 0;
 		    for ( StoreBoolMap<vec::iterator>::Iterator it = map2.begin();
 		          it != map2.end(); ++it )
 		      check(v1[i++] == *it, "Something is wrong with StoreBoolMap");
+		  }
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account