test/maps_test.cc
changeset 789 8ddb7deabab9
parent 726 3fc2a801c39e
child 877 141f9c0db4a3
equal deleted inserted replaced
21:e544b7a1eb52 22:3eb5ca24e997
    24 #include <lemon/maps.h>
    24 #include <lemon/maps.h>
    25 #include <lemon/list_graph.h>
    25 #include <lemon/list_graph.h>
    26 #include <lemon/smart_graph.h>
    26 #include <lemon/smart_graph.h>
    27 #include <lemon/adaptors.h>
    27 #include <lemon/adaptors.h>
    28 #include <lemon/dfs.h>
    28 #include <lemon/dfs.h>
       
    29 #include <algorithm>
    29 
    30 
    30 #include "test_tools.h"
    31 #include "test_tools.h"
    31 
    32 
    32 using namespace lemon;
    33 using namespace lemon;
    33 using namespace lemon::concepts;
    34 using namespace lemon::concepts;
    35 struct A {};
    36 struct A {};
    36 inline bool operator<(A, A) { return true; }
    37 inline bool operator<(A, A) { return true; }
    37 struct B {};
    38 struct B {};
    38 
    39 
    39 class C {
    40 class C {
    40   int x;
    41   int _x;
    41 public:
    42 public:
    42   C(int _x) : x(_x) {}
    43   C(int x) : _x(x) {}
       
    44   int get() const { return _x; }
       
    45 };
       
    46 inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); }
       
    47 inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); }
       
    48 
       
    49 C createC(int x) { return C(x); }
       
    50 
       
    51 template <typename T>
       
    52 class Less {
       
    53   T _t;
       
    54 public:
       
    55   Less(T t): _t(t) {}
       
    56   bool operator()(const T& t) const { return t < _t; }
    43 };
    57 };
    44 
    58 
    45 class F {
    59 class F {
    46 public:
    60 public:
    47   typedef A argument_type;
    61   typedef A argument_type;
    54 
    68 
    55 int func(A) { return 3; }
    69 int func(A) { return 3; }
    56 
    70 
    57 int binc(int a, B) { return a+1; }
    71 int binc(int a, B) { return a+1; }
    58 
    72 
       
    73 template <typename T>
       
    74 class Sum {
       
    75   T& _sum;
       
    76 public:
       
    77   Sum(T& sum) : _sum(sum) {}
       
    78   void operator()(const T& t) { _sum += t; }
       
    79 };
       
    80 
    59 typedef ReadMap<A, double> DoubleMap;
    81 typedef ReadMap<A, double> DoubleMap;
    60 typedef ReadWriteMap<A, double> DoubleWriteMap;
    82 typedef ReadWriteMap<A, double> DoubleWriteMap;
    61 typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
    83 typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
    62 
    84 
    63 typedef ReadMap<A, bool> BoolMap;
    85 typedef ReadMap<A, bool> BoolMap;
    64 typedef ReadWriteMap<A, bool> BoolWriteMap;
    86 typedef ReadWriteMap<A, bool> BoolWriteMap;
    65 typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
    87 typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
    66 
       
    67 template<typename Map1, typename Map2, typename ItemIt>
       
    68 void compareMap(const Map1& map1, const Map2& map2, ItemIt it) {
       
    69   for (; it != INVALID; ++it)
       
    70     check(map1[it] == map2[it], "The maps are not equal");
       
    71 }
       
    72 
    88 
    73 int main()
    89 int main()
    74 {
    90 {
    75   // Map concepts
    91   // Map concepts
    76   checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
    92   checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
   492     for (EdgeIt e(gr); e != INVALID; ++e) {
   508     for (EdgeIt e(gr); e != INVALID; ++e) {
   493       check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");
   509       check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");
   494       check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");
   510       check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");
   495     }
   511     }
   496     
   512     
   497     compareMap(sourceMap(orienter(gr, constMap<Edge, bool>(true))),
   513     check(mapCompare(gr,
   498                targetMap(orienter(gr, constMap<Edge, bool>(false))),
   514           sourceMap(orienter(gr, constMap<Edge, bool>(true))),
   499                EdgeIt(gr));
   515           targetMap(orienter(gr, constMap<Edge, bool>(false)))),
       
   516           "Wrong SourceMap or TargetMap");
   500 
   517 
   501     typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
   518     typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
   502     Digraph dgr(gr, constMap<Edge, bool>(true));
   519     Digraph dgr(gr, constMap<Edge, bool>(true));
   503     OutDegMap<Digraph> odm(dgr);
   520     OutDegMap<Digraph> odm(dgr);
   504     InDegMap<Digraph> idm(dgr);
   521     InDegMap<Digraph> idm(dgr);
   798       ++n;
   815       ++n;
   799     }
   816     }
   800     check(n == num, "Wrong number");
   817     check(n == num, "Wrong number");
   801 
   818 
   802   }
   819   }
       
   820   
       
   821   // Graph map utilities:
       
   822   // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
       
   823   // mapFind(), mapFindIf(), mapCount(), mapCountIf()
       
   824   // mapCopy(), mapCompare(), mapFill()
       
   825   {
       
   826     DIGRAPH_TYPEDEFS(SmartDigraph);
       
   827 
       
   828     SmartDigraph g;
       
   829     Node n1 = g.addNode();
       
   830     Node n2 = g.addNode();
       
   831     Node n3 = g.addNode();
       
   832     
       
   833     SmartDigraph::NodeMap<int> map1(g);
       
   834     SmartDigraph::ArcMap<char> map2(g);
       
   835     ConstMap<Node, A> cmap1 = A();
       
   836     ConstMap<Arc, C> cmap2 = C(0);
       
   837     
       
   838     map1[n1] = 10;
       
   839     map1[n2] = 5;
       
   840     map1[n3] = 12;
       
   841     
       
   842     // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
       
   843     check(mapMin(g, map1) == n2, "Wrong mapMin()");
       
   844     check(mapMax(g, map1) == n3, "Wrong mapMax()");
       
   845     check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()");
       
   846     check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()");
       
   847     check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()");
       
   848     check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()");
       
   849 
       
   850     check(mapMin(g, map2) == INVALID, "Wrong mapMin()");
       
   851     check(mapMax(g, map2) == INVALID, "Wrong mapMax()");
       
   852 
       
   853     check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
       
   854     check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()");
       
   855 
       
   856     Arc a1 = g.addArc(n1, n2);
       
   857     Arc a2 = g.addArc(n1, n3);
       
   858     Arc a3 = g.addArc(n2, n3);
       
   859     Arc a4 = g.addArc(n3, n1);
       
   860     
       
   861     map2[a1] = 'b';
       
   862     map2[a2] = 'a';
       
   863     map2[a3] = 'b';
       
   864     map2[a4] = 'c';
       
   865 
       
   866     // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
       
   867     check(mapMin(g, map2) == a2, "Wrong mapMin()");
       
   868     check(mapMax(g, map2) == a4, "Wrong mapMax()");
       
   869     check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()");
       
   870     check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()");
       
   871     check(mapMinValue(g, map2, std::greater<int>()) == 'c',
       
   872           "Wrong mapMinValue()");
       
   873     check(mapMaxValue(g, map2, std::greater<int>()) == 'a',
       
   874           "Wrong mapMaxValue()");
       
   875 
       
   876     check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
       
   877     check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()");
       
   878     check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()");
       
   879 
       
   880     check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2,
       
   881           "Wrong mapMin()");
       
   882     check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4,
       
   883           "Wrong mapMax()");
       
   884     check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'),
       
   885           "Wrong mapMinValue()");
       
   886     check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'),
       
   887           "Wrong mapMaxValue()");
       
   888 
       
   889     // mapFind(), mapFindIf()
       
   890     check(mapFind(g, map1, 5) == n2, "Wrong mapFind()");
       
   891     check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()");
       
   892     check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()");
       
   893     check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()");
       
   894     check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()");
       
   895     check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()");
       
   896 
       
   897     check(mapFindIf(g, map1, Less<int>(7)) == n2,
       
   898           "Wrong mapFindIf()");
       
   899     check(mapFindIf(g, map1, Less<int>(5)) == INVALID,
       
   900           "Wrong mapFindIf()");
       
   901     check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g),
       
   902           "Wrong mapFindIf()");
       
   903     check(mapFindIf(g, map2, Less<char>('a')) == INVALID,
       
   904           "Wrong mapFindIf()");
       
   905 
       
   906     // mapCount(), mapCountIf()
       
   907     check(mapCount(g, map1, 5) == 1, "Wrong mapCount()");
       
   908     check(mapCount(g, map1, 6) == 0, "Wrong mapCount()");
       
   909     check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()");
       
   910     check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()");
       
   911     check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()");
       
   912     check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()");
       
   913     check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()");
       
   914 
       
   915     check(mapCountIf(g, map1, Less<int>(11)) == 2,
       
   916           "Wrong mapCountIf()");
       
   917     check(mapCountIf(g, map1, Less<int>(13)) == 3,
       
   918           "Wrong mapCountIf()");
       
   919     check(mapCountIf(g, map1, Less<int>(5)) == 0,
       
   920           "Wrong mapCountIf()");
       
   921     check(mapCountIf(g, map2, Less<char>('d')) == 4,
       
   922           "Wrong mapCountIf()");
       
   923     check(mapCountIf(g, map2, Less<char>('c')) == 3,
       
   924           "Wrong mapCountIf()");
       
   925     check(mapCountIf(g, map2, Less<char>('a')) == 0,
       
   926           "Wrong mapCountIf()");
       
   927      
       
   928     // MapIt, ConstMapIt
       
   929 /*
       
   930 These tests can be used after applying bugfix #330
       
   931     typedef SmartDigraph::NodeMap<int>::MapIt MapIt;
       
   932     typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt;
       
   933     check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5,
       
   934           "Wrong NodeMap<>::MapIt");
       
   935     check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12,
       
   936           "Wrong NodeMap<>::MapIt");
       
   937     
       
   938     int sum = 0;
       
   939     std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum));
       
   940     check(sum == 27, "Wrong NodeMap<>::MapIt");
       
   941     std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum));
       
   942     check(sum == 54, "Wrong NodeMap<>::ConstMapIt");
       
   943 */
       
   944 
       
   945     // mapCopy(), mapCompare(), mapFill()
       
   946     check(mapCompare(g, map1, map1), "Wrong mapCompare()");
       
   947     check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()");
       
   948     check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()");
       
   949     check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()");
       
   950     check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()");
       
   951 
       
   952     SmartDigraph::NodeMap<int> map3(g, 0);
       
   953     SmartDigraph::ArcMap<char> map4(g, 'a');
       
   954     
       
   955     check(!mapCompare(g, map1, map3), "Wrong mapCompare()");
       
   956     check(!mapCompare(g, map2, map4), "Wrong mapCompare()");    
       
   957     
       
   958     mapCopy(g, map1, map3);
       
   959     mapCopy(g, map2, map4);
       
   960 
       
   961     check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()");
       
   962     check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");    
       
   963     
       
   964     Undirector<SmartDigraph> ug(g);
       
   965     Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x');
       
   966     Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14);
       
   967     
       
   968     check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
       
   969     check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
       
   970     check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
       
   971     check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
       
   972     
       
   973     mapCopy(g, map2, umap1);
       
   974 
       
   975     check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
       
   976     check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
       
   977     check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
       
   978     check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
       
   979     
       
   980     mapCopy(g, map2, umap1);
       
   981     mapCopy(g, umap1, map2);
       
   982     mapCopy(ug, map2, umap1);
       
   983     mapCopy(ug, umap1, map2);
       
   984     
       
   985     check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
       
   986     mapCopy(ug, umap1, umap2);
       
   987     check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
       
   988     
       
   989     check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()");
       
   990     mapFill(g, map1, 2);
       
   991     check(mapCompare(g, constMap<Node>(2), map1), "Wrong mapFill()");
       
   992 
       
   993     check(!mapCompare(g, map2, constMap<Arc>('z')), "Wrong mapCompare()");
       
   994     mapCopy(g, constMap<Arc>('z'), map2);
       
   995     check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()");
       
   996   }
       
   997   
   803   return 0;
   998   return 0;
   804 }
   999 }