Mercuriallemon-1.3 / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/maps_test.cc
changeset 841 aa8c9008b3de
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 }
lemon-1.3