RhodeCode

  /// \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);

    }

  }

#include <algorithm>

  int _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; }

template <typename T>

class Sum {

  T& _sum;

public:

  Sum(T& sum) : _sum(sum) {}

  void operator()(const T& t) { _sum += t; }

};

    check(mapCompare(gr,

          sourceMap(orienter(gr, constMap<Edge, bool>(true))),

          targetMap(orienter(gr, constMap<Edge, bool>(false)))),

          "Wrong SourceMap or TargetMap");

  // 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()");

  }