LEMON/LEMON-official Changeset - r836:8ddb7deabab9

Repositories » LEMON » LEMON-official

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

Changeset - r836:8ddb7deabab9

« 831:1a7fe3

838:4e3484 »

r836:8ddb7deabab9

Fri, 13 Nov 2009 12:47:13

[Not Reviewed]

0 comments (0 inline)

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

Map utility functions (#320)

0 2 0

default

2 files changed with 493 insertions and 11 deletions:

lemon/maps.h

287

test/maps_test.cc

206

↑ Collapse diff ↑

lemon/maps.h

Show inline comments

@@ -3671,100 +3671,387 @@
 		    /// Gives back the out-degree of a Node.
 		    int operator[](const Key& key) const {
 		      return _deg[key];
+		    }
 		  protected:
 		    typedef typename Digraph::Arc Arc;
 		    virtual void add(const Arc& arc) {
 		      ++_deg[_digraph.source(arc)];
+		    }
 		    virtual void add(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        ++_deg[_digraph.source(arcs[i])];
+		      }
+		    }
 		    virtual void erase(const Arc& arc) {
 		      --_deg[_digraph.source(arc)];
+		    }
 		    virtual void erase(const std::vector<Arc>& arcs) {
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        --_deg[_digraph.source(arcs[i])];
+		      }
+		    }
 		    virtual void build() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = countOutArcs(_digraph, it);
+		      }
+		    }
 		    virtual void clear() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = 0;
+		      }
+		    }
 		  private:
 		    const Digraph& _digraph;
 		    AutoNodeMap _deg;
 		  };
 		  /// \brief Potential difference map
 		  ///
 		  /// PotentialDifferenceMap returns the difference between the potentials of
 		  /// the source and target nodes of each arc in a digraph, i.e. it returns
 		  /// \code
 		  ///   potential[gr.target(arc)] - potential[gr.source(arc)].
 		  /// \endcode
 		  /// \tparam GR The digraph type.
 		  /// \tparam POT A node map storing the potentials.
 		  template <typename GR, typename POT>
 		  class PotentialDifferenceMap {
 		  public:
 		    /// Key type
 		    typedef typename GR::Arc Key;
 		    /// Value type
 		    typedef typename POT::Value Value;
 		    /// \brief Constructor
 		    ///
 		    /// Contructor of the map.
 		    explicit PotentialDifferenceMap(const GR& gr,
 		                                    const POT& potential)
 		      : _digraph(gr), _potential(potential) {}
 		    /// \brief Returns the potential difference for the given arc.
 		    ///
 		    /// Returns the potential difference for the given arc, i.e.
 		    /// \code
 		    ///   potential[gr.target(arc)] - potential[gr.source(arc)].
 		    /// \endcode
 		    Value operator[](const Key& arc) const {
 		      return _potential[_digraph.target(arc)] -
 		        _potential[_digraph.source(arc)];
+		    }
 		  private:
 		    const GR& _digraph;
 		    const POT& _potential;
 		  };
 		  /// \brief Returns a PotentialDifferenceMap.
 		  ///
 		  /// This function just returns a PotentialDifferenceMap.
 		  /// \relates PotentialDifferenceMap
 		  template <typename GR, typename POT>
 		  PotentialDifferenceMap<GR, POT>
 		  potentialDifferenceMap(const GR& gr, const POT& potential) {
 		    return PotentialDifferenceMap<GR, POT>(gr, potential);
+		  }
 		  /// \brief Copy the values of a graph map to another map.
 		  ///
 		  /// This function copies the values of a graph map to another graph map.
 		  /// \c To::Key must be equal or convertible to \c From::Key and
 		  /// \c From::Value must be equal or convertible to \c To::Value.
 		  ///
 		  /// For example, an edge map of \c int value type can be copied to
 		  /// an arc map of \c double value type in an undirected graph, but
 		  /// an arc map cannot be copied to an edge map.
 		  /// Note that even a \ref ConstMap can be copied to a standard graph map,
 		  /// but \ref mapFill() can also be used for this purpose.
 		  ///
 		  /// \param gr The graph for which the maps are defined.
 		  /// \param from The map from which the values have to be copied.
 		  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		  /// \param to The map to which the values have to be copied.
 		  /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		  template <typename GR, typename From, typename To>
 		  void mapCopy(const GR& gr, const From& from, To& to) {
 		    typedef typename To::Key Item;
 		    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
 		    for (ItemIt it(gr); it != INVALID; ++it) {
 		      to.set(it, from[it]);
+		    }
+		  }
 		  /// \brief Compare two graph maps.
 		  ///
 		  /// This function compares the values of two graph maps. It returns
 		  /// \c true if the maps assign the same value for all items in the graph.
 		  /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
 		  /// and their \c Value types must be comparable using \c %operator==().
 		  ///
 		  /// \param gr The graph for which the maps are defined.
 		  /// \param map1 The first map.
 		  /// \param map2 The second map.
 		  template <typename GR, typename Map1, typename Map2>
 		  bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {
 		    typedef typename Map2::Key Item;
 		    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
 		    for (ItemIt it(gr); it != INVALID; ++it) {
 		      if (!(map1[it] == map2[it])) return false;
+		    }
 		    return true;
+		  }
 		  /// \brief Return an item having minimum value of a graph map.
 		  ///
 		  /// This function returns an item (\c Node, \c Arc or \c Edge) having
 		  /// minimum value of the given graph map.
 		  /// If the item set is empty, it returns \c INVALID.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  template <typename GR, typename Map>
 		  typename Map::Key mapMin(const GR& gr, const Map& map) {
 		    return mapMin(gr, map, std::less<typename Map::Value>());
+		  }
 		  /// \brief Return an item having minimum value of a graph map.
 		  ///
 		  /// This function returns an item (\c Node, \c Arc or \c Edge) having
 		  /// minimum value of the given graph map.
 		  /// If the item set is empty, it returns \c INVALID.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  /// \param comp Comparison function object.
 		  template <typename GR, typename Map, typename Comp>
 		  typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) {
 		    typedef typename Map::Key Item;
 		    typedef typename Map::Value Value;
 		    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
 		    ItemIt min_item(gr);
 		    if (min_item == INVALID) return INVALID;
 		    Value min = map[min_item];
 		    for (ItemIt it(gr); it != INVALID; ++it) {
 		      if (comp(map[it], min)) {
 		        min = map[it];
 		        min_item = it;
+		      }
+		    }
 		    return min_item;
+		  }
 		  /// \brief Return an item having maximum value of a graph map.
 		  ///
 		  /// This function returns an item (\c Node, \c Arc or \c Edge) having
 		  /// maximum value of the given graph map.
 		  /// If the item set is empty, it returns \c INVALID.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  template <typename GR, typename Map>
 		  typename Map::Key mapMax(const GR& gr, const Map& map) {
 		    return mapMax(gr, map, std::less<typename Map::Value>());
+		  }
 		  /// \brief Return an item having maximum value of a graph map.
 		  ///
 		  /// This function returns an item (\c Node, \c Arc or \c Edge) having
 		  /// maximum value of the given graph map.
 		  /// If the item set is empty, it returns \c INVALID.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  /// \param comp Comparison function object.
 		  template <typename GR, typename Map, typename Comp>
 		  typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) {
 		    typedef typename Map::Key Item;
 		    typedef typename Map::Value Value;
 		    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
 		    ItemIt max_item(gr);
 		    if (max_item == INVALID) return INVALID;
 		    Value max = map[max_item];
 		    for (ItemIt it(gr); it != INVALID; ++it) {
 		      if (comp(max, map[it])) {
 		        max = map[it];
 		        max_item = it;
+		      }
+		    }
 		    return max_item;
+		  }
 		  /// \brief Return the minimum value of a graph map.
 		  ///
 		  /// This function returns the minimum value of the given graph map.
 		  /// The corresponding item set of the graph must not be empty.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  template <typename GR, typename Map>
 		  typename Map::Value mapMinValue(const GR& gr, const Map& map) {
 		    return map[mapMin(gr, map, std::less<typename Map::Value>())];
+		  }
 		  /// \brief Return the minimum value of a graph map.
 		  ///
 		  /// This function returns the minimum value of the given graph map.
 		  /// The corresponding item set of the graph must not be empty.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  /// \param comp Comparison function object.
 		  template <typename GR, typename Map, typename Comp>
 		  typename Map::Value
 		  mapMinValue(const GR& gr, const Map& map, const Comp& comp) {
 		    return map[mapMin(gr, map, comp)];
+		  }
 		  /// \brief Return the maximum value of a graph map.
 		  ///
 		  /// This function returns the maximum value of the given graph map.
 		  /// The corresponding item set of the graph must not be empty.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  template <typename GR, typename Map>
 		  typename Map::Value mapMaxValue(const GR& gr, const Map& map) {
 		    return map[mapMax(gr, map, std::less<typename Map::Value>())];
+		  }
 		  /// \brief Return the maximum value of a graph map.
 		  ///
 		  /// This function returns the maximum value of the given graph map.
 		  /// The corresponding item set of the graph must not be empty.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  /// \param comp Comparison function object.
 		  template <typename GR, typename Map, typename Comp>
 		  typename Map::Value
 		  mapMaxValue(const GR& gr, const Map& map, const Comp& comp) {
 		    return map[mapMax(gr, map, comp)];
+		  }
 		  /// \brief Return an item having a specified value in a graph map.
 		  ///
 		  /// This function returns an item (\c Node, \c Arc or \c Edge) having
 		  /// the specified assigned value in the given graph map.
 		  /// If no such item exists, it returns \c INVALID.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  /// \param val The value that have to be found.
 		  template <typename GR, typename Map>
 		  typename Map::Key
 		  mapFind(const GR& gr, const Map& map, const typename Map::Value& val) {
 		    typedef typename Map::Key Item;
 		    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
 		    for (ItemIt it(gr); it != INVALID; ++it) {
 		      if (map[it] == val) return it;
+		    }
 		    return INVALID;
+		  }
 		  /// \brief Return an item having value for which a certain predicate is
 		  /// true in a graph map.
 		  ///
 		  /// This function returns an item (\c Node, \c Arc or \c Edge) having
 		  /// such assigned value for which the specified predicate is true
 		  /// in the given graph map.
 		  /// If no such item exists, it returns \c INVALID.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  /// \param pred The predicate function object.
 		  template <typename GR, typename Map, typename Pred>
 		  typename Map::Key
 		  mapFindIf(const GR& gr, const Map& map, const Pred& pred) {
 		    typedef typename Map::Key Item;
 		    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
 		    for (ItemIt it(gr); it != INVALID; ++it) {
 		      if (pred(map[it])) return it;
+		    }
 		    return INVALID;
+		  }
 		  /// \brief Return the number of items having a specified value in a
 		  /// graph map.
 		  ///
 		  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
 		  /// having the specified assigned value in the given graph map.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  /// \param val The value that have to be counted.
 		  template <typename GR, typename Map>
 		  int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) {
 		    typedef typename Map::Key Item;
 		    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
 		    int cnt = 0;
 		    for (ItemIt it(gr); it != INVALID; ++it) {
 		      if (map[it] == val) ++cnt;
+		    }
 		    return cnt;
+		  }
 		  /// \brief Return the number of items having values for which a certain
 		  /// predicate is true in a graph map.
 		  ///
 		  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
 		  /// having such assigned values for which the specified predicate is true
 		  /// in the given graph map.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map.
 		  /// \param pred The predicate function object.
 		  template <typename GR, typename Map, typename Pred>
 		  int mapCountIf(const GR& gr, const Map& map, const Pred& pred) {
 		    typedef typename Map::Key Item;
 		    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
 		    int cnt = 0;
 		    for (ItemIt it(gr); it != INVALID; ++it) {
 		      if (pred(map[it])) ++cnt;
+		    }
 		    return cnt;
+		  }
 		  /// \brief Fill a graph map with a certain value.
 		  ///
 		  /// This function sets the specified value for all items (\c Node,
 		  /// \c Arc or \c Edge) in the given graph map.
 		  ///
 		  /// \param gr The graph for which the map is defined.
 		  /// \param map The graph map. It must conform to the
 		  /// \ref concepts::WriteMap "WriteMap" concept.
 		  /// \param val The value.
 		  template <typename GR, typename Map>
 		  void mapFill(const GR& gr, Map& map, const typename Map::Value& val) {
 		    typedef typename Map::Key Item;
 		    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
 		    for (ItemIt it(gr); it != INVALID; ++it) {
 		      map.set(it, val);
+		    }
+		  }
 		  /// @}
+		}
 		#endif // LEMON_MAPS_H

test/maps_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <deque>
 		#include <set>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/maps.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/adaptors.h>
 		#include <lemon/dfs.h>
 		#include <algorithm>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		struct A {};
 		inline bool operator<(A, A) { return true; }
 		struct B {};
 		class C {
-		  int x;
+		  int _x;
 		public:
-		  C(int _x) : x(_x) {}
+		  C(int x) : _x(x) {}
 		  int get() const { return _x; }
 		};
 		inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); }
 		inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); }
 		C createC(int x) { return C(x); }
 		template <typename T>
 		class Less {
 		  T _t;
 		public:
 		  Less(T t): _t(t) {}
 		  bool operator()(const T& t) const { return t < _t; }
 		};
 		class F {
 		public:
 		  typedef A argument_type;
 		  typedef B result_type;
 		  B operator()(const A&) const { return B(); }
 		private:
 		  F& operator=(const F&);
 		};
 		int func(A) { return 3; }
 		int binc(int a, B) { return a+1; }
 		template <typename T>
 		class Sum {
 		  T& _sum;
 		public:
 		  Sum(T& sum) : _sum(sum) {}
 		  void operator()(const T& t) { _sum += t; }
 		};
 		typedef ReadMap<A, double> DoubleMap;
 		typedef ReadWriteMap<A, double> DoubleWriteMap;
 		typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
 		typedef ReadMap<A, bool> BoolMap;
 		typedef ReadWriteMap<A, bool> BoolWriteMap;
 		typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
 		template<typename Map1, typename Map2, typename ItemIt>
 		void compareMap(const Map1& map1, const Map2& map2, ItemIt it) {
 		  for (; it != INVALID; ++it)
 		    check(map1[it] == map2[it], "The maps are not equal");
+		}
 		int main()
+		{
 		  // Map concepts
 		  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
 		  checkConcept<ReadMap<A,C>, ReadMap<A,C> >();
 		  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
 		  checkConcept<WriteMap<A,C>, WriteMap<A,C> >();
 		  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
 		  checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();
 		  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
 		  checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >();
 		  // NullMap
+		  {
 		    checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >();
 		    NullMap<A,B> map1;
 		    NullMap<A,B> map2 = map1;
 		    map1 = nullMap<A,B>();
+		  }
 		  // ConstMap
+		  {
 		    checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >();
 		    checkConcept<ReadWriteMap<A,C>, ConstMap<A,C> >();
 		    ConstMap<A,B> map1;
 		    ConstMap<A,B> map2 = B();
 		    ConstMap<A,B> map3 = map1;
 		    map1 = constMap<A>(B());
 		    map1 = constMap<A,B>();
 		    map1.setAll(B());
 		    ConstMap<A,C> map4(C(1));
 		    ConstMap<A,C> map5 = map4;
 		    map4 = constMap<A>(C(2));
 		    map4.setAll(C(3));
 		    checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >();
 		    check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap");
 		    checkConcept<ReadWriteMap<A,int>, ConstMap<A,Const<int,10> > >();
 		    ConstMap<A,Const<int,10> > map6;
 		    ConstMap<A,Const<int,10> > map7 = map6;
 		    map6 = constMap<A,int,10>();
 		    map7 = constMap<A,Const<int,10> >();
 		    check(map6[A()] == 10 && map7[A()] == 10,
 		          "Something is wrong with ConstMap");
+		  }
 		  // IdentityMap
+		  {
 		    checkConcept<ReadMap<A,A>, IdentityMap<A> >();
 		    IdentityMap<A> map1;
 		    IdentityMap<A> map2 = map1;
 		    map1 = identityMap<A>();
 		    checkConcept<ReadMap<double,double>, IdentityMap<double> >();
 		    check(identityMap<double>()[1.0] == 1.0 &&
 		          identityMap<double>()[3.14] == 3.14,
 		          "Something is wrong with IdentityMap");
+		  }
 		  // RangeMap
+		  {
 		    checkConcept<ReferenceMap<int,B,B&,const B&>, RangeMap<B> >();
 		    RangeMap<B> map1;
 		    RangeMap<B> map2(10);
 		    RangeMap<B> map3(10,B());
 		    RangeMap<B> map4 = map1;
 		    RangeMap<B> map5 = rangeMap<B>();
 		    RangeMap<B> map6 = rangeMap<B>(10);
 		    RangeMap<B> map7 = rangeMap(10,B());
 		    checkConcept< ReferenceMap<int, double, double&, const double&>,
 		                  RangeMap<double> >();
 		    std::vector<double> v(10, 0);
 		    v[5] = 100;
 		    RangeMap<double> map8(v);
 		    RangeMap<double> map9 = rangeMap(v);
 		    check(map9.size() == 10 && map9[2] == 0 && map9[5] == 100,
 		          "Something is wrong with RangeMap");
+		  }
 		  // SparseMap
+		  {
 		    checkConcept<ReferenceMap<A,B,B&,const B&>, SparseMap<A,B> >();
 		    SparseMap<A,B> map1;
 		    SparseMap<A,B> map2 = B();
 		    SparseMap<A,B> map3 = sparseMap<A,B>();
 		    SparseMap<A,B> map4 = sparseMap<A>(B());
 		    checkConcept< ReferenceMap<double, int, int&, const int&>,
 		                  SparseMap<double, int> >();
 		    std::map<double, int> m;
 		    SparseMap<double, int> map5(m);
 		    SparseMap<double, int> map6(m,10);
 		    SparseMap<double, int> map7 = sparseMap(m);
 		    SparseMap<double, int> map8 = sparseMap(m,10);
@@ -401,195 +417,196 @@
 		    checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >();
 		    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();
 		    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();
 		    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();
 		    Graph gr;
 		    IdMap<Graph, Node> nmap(gr);
 		    IdMap<Graph, Arc> amap(gr);
 		    RangeIdMap<Graph, Node> nrmap(gr);
 		    RangeIdMap<Graph, Arc> armap(gr);
 		    Node n0 = gr.addNode();
 		    Node n1 = gr.addNode();
 		    Node n2 = gr.addNode();
 		    Arc a0 = gr.addArc(n0, n1);
 		    Arc a1 = gr.addArc(n0, n2);
 		    Arc a2 = gr.addArc(n2, n1);
 		    Arc a3 = gr.addArc(n2, n0);
 		    check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap");
 		    check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap");
 		    check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap");
 		    check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap");
 		    check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap");
 		    check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap");
 		    check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap");
 		    check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap");
 		    check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap");
 		    check(nrmap.size() == 3 && armap.size() == 4,
 		          "Wrong RangeIdMap::size()");
 		    check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap");
 		    check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap");
 		    check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap");
 		    check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap");
 		    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
 		    check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap");
 		    check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap");
 		    check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap");
 		    check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap");
 		    gr.erase(n1);
 		    if (nrmap[n0] == 1) nrmap.swap(n0, n2);
 		    nrmap.swap(n2, n0);
 		    if (armap[a1] == 1) armap.swap(a1, a3);
 		    armap.swap(a3, a1);
 		    check(nrmap.size() == 2 && armap.size() == 2,
 		          "Wrong RangeIdMap::size()");
 		    check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap");
 		    check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap");
 		    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
 		    check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap");
 		    check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap");
 		    check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap");
+		  }
 		  // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap
+		  {
 		    typedef ListGraph Graph;
 		    GRAPH_TYPEDEFS(Graph);
 		    checkConcept<ReadMap<Arc, Node>, SourceMap<Graph> >();
 		    checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >();
 		    checkConcept<ReadMap<Edge, Arc>, ForwardMap<Graph> >();
 		    checkConcept<ReadMap<Edge, Arc>, BackwardMap<Graph> >();
 		    checkConcept<ReadMap<Node, int>, InDegMap<Graph> >();
 		    checkConcept<ReadMap<Node, int>, OutDegMap<Graph> >();
 		    Graph gr;
 		    Node n0 = gr.addNode();
 		    Node n1 = gr.addNode();
 		    Node n2 = gr.addNode();
 		    gr.addEdge(n0,n1);
 		    gr.addEdge(n1,n2);
 		    gr.addEdge(n0,n2);
 		    gr.addEdge(n2,n1);
 		    gr.addEdge(n1,n2);
 		    gr.addEdge(n0,n1);
 		    for (EdgeIt e(gr); e != INVALID; ++e) {
 		      check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");
 		      check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");
+		    }
 		    compareMap(sourceMap(orienter(gr, constMap<Edge, bool>(true))),
 		               targetMap(orienter(gr, constMap<Edge, bool>(false))),
-		               EdgeIt(gr));
+		    check(mapCompare(gr,
 		          sourceMap(orienter(gr, constMap<Edge, bool>(true))),
 		          targetMap(orienter(gr, constMap<Edge, bool>(false)))),
 		          "Wrong SourceMap or TargetMap");
 		    typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
 		    Digraph dgr(gr, constMap<Edge, bool>(true));
 		    OutDegMap<Digraph> odm(dgr);
 		    InDegMap<Digraph> idm(dgr);
 		    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap");
 		    check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
 		    gr.addEdge(n2, n0);
 		    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap");
 		    check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
+		  }
 		  // CrossRefMap
+		  {
 		    typedef ListDigraph Graph;
 		    DIGRAPH_TYPEDEFS(Graph);
 		    checkConcept<ReadWriteMap<Node, int>,
 		                 CrossRefMap<Graph, Node, int> >();
 		    checkConcept<ReadWriteMap<Node, bool>,
 		                 CrossRefMap<Graph, Node, bool> >();
 		    checkConcept<ReadWriteMap<Node, double>,
 		                 CrossRefMap<Graph, Node, double> >();
 		    Graph gr;
 		    typedef CrossRefMap<Graph, Node, char> CRMap;
 		    CRMap map(gr);
 		    Node n0 = gr.addNode();
 		    Node n1 = gr.addNode();
 		    Node n2 = gr.addNode();
 		    map.set(n0, 'A');
 		    map.set(n1, 'B');
 		    map.set(n2, 'C');
 		    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,
 		          "Wrong CrossRefMap");
 		    check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1,
 		          "Wrong CrossRefMap");
 		    check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2,
 		          "Wrong CrossRefMap");
 		    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
 		          "Wrong CrossRefMap::count()");
 		    CRMap::ValueIt it = map.beginValue();
 		    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
 		          it == map.endValue(), "Wrong value iterator");
 		    map.set(n2, 'A');
 		    check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A',
 		          "Wrong CrossRefMap");
 		    check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap");
 		    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
 		    check(map('C') == INVALID && map.inverse()['C'] == INVALID,
 		          "Wrong CrossRefMap");
 		    check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0,
 		          "Wrong CrossRefMap::count()");
 		    it = map.beginValue();
 		    check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' &&
 		          it == map.endValue(), "Wrong value iterator");
 		    map.set(n0, 'C');
 		    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
 		          "Wrong CrossRefMap");
 		    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
 		    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
 		    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
 		    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
 		          "Wrong CrossRefMap::count()");
 		    it = map.beginValue();
 		    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
 		          it == map.endValue(), "Wrong value iterator");
+		  }
 		  // CrossRefMap
+		  {
 		    typedef SmartDigraph Graph;
 		    DIGRAPH_TYPEDEFS(Graph);
 		    checkConcept<ReadWriteMap<Node, int>,
 		                 CrossRefMap<Graph, Node, int> >();
 		    Graph gr;
 		    typedef CrossRefMap<Graph, Node, char> CRMap;
 		    typedef CRMap::ValueIterator ValueIt;
 		    CRMap map(gr);
 		    Node n0 = gr.addNode();
@@ -707,98 +724,276 @@
 		    std::vector<Item> items;
 		    for (int i = 0; i < num; ++i) {
 		      items.push_back(g.addNode());
+		    }
 		    Iim map1(g);
 		    check(map1.size() == 0, "Wrong size");
 		    for (int i = 0; i < num; ++i) {
 		      map1[items[i]] = i;
+		    }
 		    check(map1.size() == num, "Wrong size");
 		    for (int i = 0; i < num; ++i) {
 		      Iim::ItemIt it(map1, i);
 		      check(static_cast<Item>(it) == items[i], "Wrong value");
 		      ++it;
 		      check(static_cast<Item>(it) == INVALID, "Wrong value");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      map1[items[i]] = i % 2;
+		    }
 		    check(map1.size() == 2, "Wrong size");
 		    int n = 0;
 		    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 0, "Wrong value");
 		      ++n;
+		    }
 		    check(n == (num + 1) / 2, "Wrong number");
 		    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 1, "Wrong value");
 		      ++n;
+		    }
 		    check(n == num, "Wrong number");
+		  }
 		  // Iterable value map
+		  {
 		    typedef SmartGraph Graph;
 		    typedef SmartGraph::Node Item;
 		    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
 		    checkConcept<ReadWriteMap<Item, double>, Ivm>();
 		    const int num = 10;
 		    Graph g;
 		    std::vector<Item> items;
 		    for (int i = 0; i < num; ++i) {
 		      items.push_back(g.addNode());
+		    }
 		    Ivm map1(g, 0.0);
 		    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
 		    check(*map1.beginValue() == 0.0, "Wrong value");
 		    for (int i = 0; i < num; ++i) {
 		      map1.set(items[i], static_cast<double>(i));
+		    }
 		    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
 		    for (int i = 0; i < num; ++i) {
 		      Ivm::ItemIt it(map1, static_cast<double>(i));
 		      check(static_cast<Item>(it) == items[i], "Wrong value");
 		      ++it;
 		      check(static_cast<Item>(it) == INVALID, "Wrong value");
+		    }
 		    for (Ivm::ValueIt vit = map1.beginValue();
 		         vit != map1.endValue(); ++vit) {
 		      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
 		            "Wrong ValueIt");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      map1.set(items[i], static_cast<double>(i % 2));
+		    }
 		    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
 		    int n = 0;
 		    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
 		      ++n;
+		    }
 		    check(n == (num + 1) / 2, "Wrong number");
 		    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
 		      ++n;
+		    }
 		    check(n == num, "Wrong number");
+		  }
 		  // Graph map utilities:
 		  // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
 		  // mapFind(), mapFindIf(), mapCount(), mapCountIf()
 		  // mapCopy(), mapCompare(), mapFill()
+		  {
 		    DIGRAPH_TYPEDEFS(SmartDigraph);
 		    SmartDigraph g;
 		    Node n1 = g.addNode();
 		    Node n2 = g.addNode();
 		    Node n3 = g.addNode();
 		    SmartDigraph::NodeMap<int> map1(g);
 		    SmartDigraph::ArcMap<char> map2(g);
 		    ConstMap<Node, A> cmap1 = A();
 		    ConstMap<Arc, C> cmap2 = C(0);
 		    map1[n1] = 10;
 		    map1[n2] = 5;
 		    map1[n3] = 12;
 		    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
 		    check(mapMin(g, map1) == n2, "Wrong mapMin()");
 		    check(mapMax(g, map1) == n3, "Wrong mapMax()");
 		    check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()");
 		    check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()");
 		    check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()");
 		    check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()");
 		    check(mapMin(g, map2) == INVALID, "Wrong mapMin()");
 		    check(mapMax(g, map2) == INVALID, "Wrong mapMax()");
 		    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
 		    check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()");
 		    Arc a1 = g.addArc(n1, n2);
 		    Arc a2 = g.addArc(n1, n3);
 		    Arc a3 = g.addArc(n2, n3);
 		    Arc a4 = g.addArc(n3, n1);
 		    map2[a1] = 'b';
 		    map2[a2] = 'a';
 		    map2[a3] = 'b';
 		    map2[a4] = 'c';
 		    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
 		    check(mapMin(g, map2) == a2, "Wrong mapMin()");
 		    check(mapMax(g, map2) == a4, "Wrong mapMax()");
 		    check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()");
 		    check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()");
 		    check(mapMinValue(g, map2, std::greater<int>()) == 'c',
 		          "Wrong mapMinValue()");
 		    check(mapMaxValue(g, map2, std::greater<int>()) == 'a',
 		          "Wrong mapMaxValue()");
 		    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
 		    check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()");
 		    check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()");
 		    check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2,
 		          "Wrong mapMin()");
 		    check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4,
 		          "Wrong mapMax()");
 		    check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'),
 		          "Wrong mapMinValue()");
 		    check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'),
 		          "Wrong mapMaxValue()");
 		    // mapFind(), mapFindIf()
 		    check(mapFind(g, map1, 5) == n2, "Wrong mapFind()");
 		    check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()");
 		    check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()");
 		    check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()");
 		    check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()");
 		    check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()");
 		    check(mapFindIf(g, map1, Less<int>(7)) == n2,
 		          "Wrong mapFindIf()");
 		    check(mapFindIf(g, map1, Less<int>(5)) == INVALID,
 		          "Wrong mapFindIf()");
 		    check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g),
 		          "Wrong mapFindIf()");
 		    check(mapFindIf(g, map2, Less<char>('a')) == INVALID,
 		          "Wrong mapFindIf()");
 		    // mapCount(), mapCountIf()
 		    check(mapCount(g, map1, 5) == 1, "Wrong mapCount()");
 		    check(mapCount(g, map1, 6) == 0, "Wrong mapCount()");
 		    check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()");
 		    check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()");
 		    check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()");
 		    check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()");
 		    check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()");
 		    check(mapCountIf(g, map1, Less<int>(11)) == 2,
 		          "Wrong mapCountIf()");
 		    check(mapCountIf(g, map1, Less<int>(13)) == 3,
 		          "Wrong mapCountIf()");
 		    check(mapCountIf(g, map1, Less<int>(5)) == 0,
 		          "Wrong mapCountIf()");
 		    check(mapCountIf(g, map2, Less<char>('d')) == 4,
 		          "Wrong mapCountIf()");
 		    check(mapCountIf(g, map2, Less<char>('c')) == 3,
 		          "Wrong mapCountIf()");
 		    check(mapCountIf(g, map2, Less<char>('a')) == 0,
 		          "Wrong mapCountIf()");
 		    // MapIt, ConstMapIt
 		/*
 		These tests can be used after applying bugfix #330
 		    typedef SmartDigraph::NodeMap<int>::MapIt MapIt;
 		    typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt;
 		    check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5,
 		          "Wrong NodeMap<>::MapIt");
 		    check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12,
 		          "Wrong NodeMap<>::MapIt");
 		    int sum = 0;
 		    std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum));
 		    check(sum == 27, "Wrong NodeMap<>::MapIt");
 		    std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum));
 		    check(sum == 54, "Wrong NodeMap<>::ConstMapIt");
 		*/
 		    // mapCopy(), mapCompare(), mapFill()
 		    check(mapCompare(g, map1, map1), "Wrong mapCompare()");
 		    check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()");
 		    check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()");
 		    check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()");
 		    check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()");
 		    SmartDigraph::NodeMap<int> map3(g, 0);
 		    SmartDigraph::ArcMap<char> map4(g, 'a');
 		    check(!mapCompare(g, map1, map3), "Wrong mapCompare()");
 		    check(!mapCompare(g, map2, map4), "Wrong mapCompare()");
 		    mapCopy(g, map1, map3);
 		    mapCopy(g, map2, map4);
 		    check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()");
 		    check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");
 		    Undirector<SmartDigraph> ug(g);
 		    Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x');
 		    Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14);
 		    check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
 		    check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
 		    check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
 		    check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
 		    mapCopy(g, map2, umap1);
 		    check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
 		    check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
 		    check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
 		    check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
 		    mapCopy(g, map2, umap1);
 		    mapCopy(g, umap1, map2);
 		    mapCopy(ug, map2, umap1);
 		    mapCopy(ug, umap1, map2);
 		    check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
 		    mapCopy(ug, umap1, umap2);
 		    check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
 		    check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()");
 		    mapFill(g, map1, 2);
 		    check(mapCompare(g, constMap<Node>(2), map1), "Wrong mapFill()");
 		    check(!mapCompare(g, map2, constMap<Arc>('z')), "Wrong mapCompare()");
 		    mapCopy(g, constMap<Arc>('z'), map2);
 		    check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()");
+		  }
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account