test/maps_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 13 Mar 2010 22:01:38 +0100
changeset 864 d3ea191c3412
parent 726 3fc2a801c39e
child 877 141f9c0db4a3
permissions -rw-r--r--
Rename min mean cycle classes and their members (#179)
with respect to the possible introduction of min ratio
cycle algorithms in the future.

The renamed classes:
- Karp --> KarpMmc
- HartmannOrlin --> HartmannOrlinMmc
- Howard --> HowardMmc

The renamed members:
- cycleLength() --> cycleCost()
- cycleArcNum() --> cycleSize()
- findMinMean() --> findCycleMean()
- Value --> Cost
- LargeValue --> LargeCost
- SetLargeValue --> SetLargeCost
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@25
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@25
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@25
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@25
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@25
     8
 *
alpar@25
     9
 * Permission to use, modify and distribute this software is granted
alpar@25
    10
 * provided that this copyright notice appears in all copies. For
alpar@25
    11
 * precise terms see the accompanying LICENSE file.
alpar@25
    12
 *
alpar@25
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@25
    14
 * express or implied, and with no claim as to its suitability for any
alpar@25
    15
 * purpose.
alpar@25
    16
 *
alpar@25
    17
 */
alpar@25
    18
alpar@25
    19
#include <deque>
alpar@25
    20
#include <set>
alpar@25
    21
alpar@25
    22
#include <lemon/concept_check.h>
alpar@25
    23
#include <lemon/concepts/maps.h>
alpar@25
    24
#include <lemon/maps.h>
kpeter@684
    25
#include <lemon/list_graph.h>
kpeter@694
    26
#include <lemon/smart_graph.h>
kpeter@723
    27
#include <lemon/adaptors.h>
kpeter@723
    28
#include <lemon/dfs.h>
kpeter@789
    29
#include <algorithm>
alpar@25
    30
alpar@25
    31
#include "test_tools.h"
alpar@25
    32
alpar@25
    33
using namespace lemon;
alpar@25
    34
using namespace lemon::concepts;
alpar@25
    35
alpar@25
    36
struct A {};
alpar@25
    37
inline bool operator<(A, A) { return true; }
alpar@25
    38
struct B {};
alpar@25
    39
kpeter@94
    40
class C {
kpeter@789
    41
  int _x;
kpeter@94
    42
public:
kpeter@789
    43
  C(int x) : _x(x) {}
kpeter@789
    44
  int get() const { return _x; }
kpeter@789
    45
};
kpeter@789
    46
inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); }
kpeter@789
    47
inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); }
kpeter@789
    48
kpeter@789
    49
C createC(int x) { return C(x); }
kpeter@789
    50
kpeter@789
    51
template <typename T>
kpeter@789
    52
class Less {
kpeter@789
    53
  T _t;
kpeter@789
    54
public:
kpeter@789
    55
  Less(T t): _t(t) {}
kpeter@789
    56
  bool operator()(const T& t) const { return t < _t; }
kpeter@94
    57
};
kpeter@94
    58
alpar@25
    59
class F {
alpar@25
    60
public:
alpar@25
    61
  typedef A argument_type;
alpar@25
    62
  typedef B result_type;
alpar@25
    63
kpeter@80
    64
  B operator()(const A&) const { return B(); }
kpeter@80
    65
private:
kpeter@80
    66
  F& operator=(const F&);
alpar@25
    67
};
alpar@25
    68
kpeter@80
    69
int func(A) { return 3; }
alpar@25
    70
kpeter@80
    71
int binc(int a, B) { return a+1; }
alpar@25
    72
kpeter@789
    73
template <typename T>
kpeter@789
    74
class Sum {
kpeter@789
    75
  T& _sum;
kpeter@789
    76
public:
kpeter@789
    77
  Sum(T& sum) : _sum(sum) {}
kpeter@789
    78
  void operator()(const T& t) { _sum += t; }
kpeter@789
    79
};
kpeter@789
    80
kpeter@80
    81
typedef ReadMap<A, double> DoubleMap;
kpeter@80
    82
typedef ReadWriteMap<A, double> DoubleWriteMap;
kpeter@80
    83
typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
alpar@25
    84
kpeter@80
    85
typedef ReadMap<A, bool> BoolMap;
alpar@25
    86
typedef ReadWriteMap<A, bool> BoolWriteMap;
kpeter@80
    87
typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
alpar@25
    88
alpar@25
    89
int main()
kpeter@80
    90
{
kpeter@80
    91
  // Map concepts
alpar@25
    92
  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
kpeter@94
    93
  checkConcept<ReadMap<A,C>, ReadMap<A,C> >();
alpar@25
    94
  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
kpeter@94
    95
  checkConcept<WriteMap<A,C>, WriteMap<A,C> >();
alpar@25
    96
  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
kpeter@94
    97
  checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();
alpar@25
    98
  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
kpeter@94
    99
  checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >();
alpar@25
   100
kpeter@80
   101
  // NullMap
kpeter@80
   102
  {
kpeter@80
   103
    checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >();
kpeter@80
   104
    NullMap<A,B> map1;
kpeter@80
   105
    NullMap<A,B> map2 = map1;
kpeter@80
   106
    map1 = nullMap<A,B>();
kpeter@80
   107
  }
kpeter@80
   108
kpeter@80
   109
  // ConstMap
kpeter@80
   110
  {
kpeter@80
   111
    checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >();
kpeter@123
   112
    checkConcept<ReadWriteMap<A,C>, ConstMap<A,C> >();
kpeter@80
   113
    ConstMap<A,B> map1;
deba@136
   114
    ConstMap<A,B> map2 = B();
kpeter@80
   115
    ConstMap<A,B> map3 = map1;
kpeter@80
   116
    map1 = constMap<A>(B());
kpeter@123
   117
    map1 = constMap<A,B>();
kpeter@80
   118
    map1.setAll(B());
kpeter@123
   119
    ConstMap<A,C> map4(C(1));
kpeter@123
   120
    ConstMap<A,C> map5 = map4;
kpeter@123
   121
    map4 = constMap<A>(C(2));
kpeter@123
   122
    map4.setAll(C(3));
kpeter@82
   123
kpeter@80
   124
    checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >();
kpeter@80
   125
    check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap");
kpeter@80
   126
kpeter@80
   127
    checkConcept<ReadWriteMap<A,int>, ConstMap<A,Const<int,10> > >();
kpeter@123
   128
    ConstMap<A,Const<int,10> > map6;
kpeter@123
   129
    ConstMap<A,Const<int,10> > map7 = map6;
kpeter@123
   130
    map6 = constMap<A,int,10>();
kpeter@123
   131
    map7 = constMap<A,Const<int,10> >();
alpar@210
   132
    check(map6[A()] == 10 && map7[A()] == 10,
alpar@210
   133
          "Something is wrong with ConstMap");
kpeter@80
   134
  }
kpeter@80
   135
kpeter@80
   136
  // IdentityMap
kpeter@80
   137
  {
kpeter@80
   138
    checkConcept<ReadMap<A,A>, IdentityMap<A> >();
kpeter@80
   139
    IdentityMap<A> map1;
kpeter@80
   140
    IdentityMap<A> map2 = map1;
kpeter@80
   141
    map1 = identityMap<A>();
kpeter@82
   142
kpeter@80
   143
    checkConcept<ReadMap<double,double>, IdentityMap<double> >();
alpar@210
   144
    check(identityMap<double>()[1.0] == 1.0 &&
alpar@210
   145
          identityMap<double>()[3.14] == 3.14,
kpeter@80
   146
          "Something is wrong with IdentityMap");
kpeter@80
   147
  }
kpeter@80
   148
kpeter@80
   149
  // RangeMap
kpeter@80
   150
  {
kpeter@80
   151
    checkConcept<ReferenceMap<int,B,B&,const B&>, RangeMap<B> >();
kpeter@80
   152
    RangeMap<B> map1;
kpeter@80
   153
    RangeMap<B> map2(10);
kpeter@80
   154
    RangeMap<B> map3(10,B());
kpeter@80
   155
    RangeMap<B> map4 = map1;
kpeter@80
   156
    RangeMap<B> map5 = rangeMap<B>();
kpeter@80
   157
    RangeMap<B> map6 = rangeMap<B>(10);
kpeter@80
   158
    RangeMap<B> map7 = rangeMap(10,B());
kpeter@80
   159
kpeter@80
   160
    checkConcept< ReferenceMap<int, double, double&, const double&>,
kpeter@80
   161
                  RangeMap<double> >();
kpeter@80
   162
    std::vector<double> v(10, 0);
kpeter@80
   163
    v[5] = 100;
kpeter@80
   164
    RangeMap<double> map8(v);
kpeter@80
   165
    RangeMap<double> map9 = rangeMap(v);
kpeter@80
   166
    check(map9.size() == 10 && map9[2] == 0 && map9[5] == 100,
kpeter@80
   167
          "Something is wrong with RangeMap");
kpeter@80
   168
  }
kpeter@80
   169
kpeter@80
   170
  // SparseMap
kpeter@80
   171
  {
kpeter@80
   172
    checkConcept<ReferenceMap<A,B,B&,const B&>, SparseMap<A,B> >();
kpeter@80
   173
    SparseMap<A,B> map1;
deba@136
   174
    SparseMap<A,B> map2 = B();
kpeter@80
   175
    SparseMap<A,B> map3 = sparseMap<A,B>();
kpeter@80
   176
    SparseMap<A,B> map4 = sparseMap<A>(B());
kpeter@80
   177
kpeter@80
   178
    checkConcept< ReferenceMap<double, int, int&, const int&>,
kpeter@80
   179
                  SparseMap<double, int> >();
kpeter@80
   180
    std::map<double, int> m;
kpeter@80
   181
    SparseMap<double, int> map5(m);
kpeter@80
   182
    SparseMap<double, int> map6(m,10);
kpeter@80
   183
    SparseMap<double, int> map7 = sparseMap(m);
kpeter@80
   184
    SparseMap<double, int> map8 = sparseMap(m,10);
kpeter@80
   185
alpar@210
   186
    check(map5[1.0] == 0 && map5[3.14] == 0 &&
alpar@210
   187
          map6[1.0] == 10 && map6[3.14] == 10,
kpeter@80
   188
          "Something is wrong with SparseMap");
kpeter@80
   189
    map5[1.0] = map6[3.14] = 100;
alpar@210
   190
    check(map5[1.0] == 100 && map5[3.14] == 0 &&
alpar@210
   191
          map6[1.0] == 10 && map6[3.14] == 100,
kpeter@80
   192
          "Something is wrong with SparseMap");
kpeter@80
   193
  }
kpeter@80
   194
kpeter@80
   195
  // ComposeMap
kpeter@80
   196
  {
kpeter@80
   197
    typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;
kpeter@80
   198
    checkConcept<ReadMap<B,double>, CompMap>();
alpar@507
   199
    CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());
kpeter@80
   200
    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
kpeter@82
   201
kpeter@80
   202
    SparseMap<double, bool> m1(false); m1[3.14] = true;
kpeter@80
   203
    RangeMap<double> m2(2); m2[0] = 3.0; m2[1] = 3.14;
alpar@210
   204
    check(!composeMap(m1,m2)[0] && composeMap(m1,m2)[1],
alpar@210
   205
          "Something is wrong with ComposeMap")
kpeter@80
   206
  }
kpeter@80
   207
kpeter@80
   208
  // CombineMap
kpeter@80
   209
  {
kpeter@80
   210
    typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap;
kpeter@80
   211
    checkConcept<ReadMap<A,double>, CombMap>();
alpar@507
   212
    CombMap map1 = CombMap(DoubleMap(), DoubleMap());
kpeter@80
   213
    CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());
kpeter@80
   214
kpeter@80
   215
    check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3,
kpeter@80
   216
          "Something is wrong with CombineMap");
kpeter@80
   217
  }
kpeter@80
   218
kpeter@80
   219
  // FunctorToMap, MapToFunctor
kpeter@80
   220
  {
kpeter@80
   221
    checkConcept<ReadMap<A,B>, FunctorToMap<F,A,B> >();
kpeter@80
   222
    checkConcept<ReadMap<A,B>, FunctorToMap<F> >();
kpeter@80
   223
    FunctorToMap<F> map1;
alpar@507
   224
    FunctorToMap<F> map2 = FunctorToMap<F>(F());
kpeter@80
   225
    B b = functorToMap(F())[A()];
kpeter@80
   226
kpeter@80
   227
    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
alpar@507
   228
    MapToFunctor<ReadMap<A,B> > map = MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
kpeter@80
   229
alpar@210
   230
    check(functorToMap(&func)[A()] == 3,
alpar@210
   231
          "Something is wrong with FunctorToMap");
alpar@210
   232
    check(mapToFunctor(constMap<A,int>(2))(A()) == 2,
alpar@210
   233
          "Something is wrong with MapToFunctor");
alpar@210
   234
    check(mapToFunctor(functorToMap(&func))(A()) == 3 &&
alpar@210
   235
          mapToFunctor(functorToMap(&func))[A()] == 3,
kpeter@80
   236
          "Something is wrong with FunctorToMap or MapToFunctor");
kpeter@80
   237
    check(functorToMap(mapToFunctor(constMap<A,int>(2)))[A()] == 2,
kpeter@80
   238
          "Something is wrong with FunctorToMap or MapToFunctor");
kpeter@80
   239
  }
kpeter@80
   240
kpeter@80
   241
  // ConvertMap
kpeter@80
   242
  {
alpar@210
   243
    checkConcept<ReadMap<double,double>,
alpar@210
   244
      ConvertMap<ReadMap<double, int>, double> >();
kpeter@80
   245
    ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true));
kpeter@80
   246
    ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false));
kpeter@80
   247
  }
kpeter@80
   248
kpeter@80
   249
  // ForkMap
kpeter@80
   250
  {
kpeter@80
   251
    checkConcept<DoubleWriteMap, ForkMap<DoubleWriteMap, DoubleWriteMap> >();
kpeter@82
   252
kpeter@80
   253
    typedef RangeMap<double> RM;
kpeter@80
   254
    typedef SparseMap<int, double> SM;
kpeter@80
   255
    RM m1(10, -1);
kpeter@80
   256
    SM m2(-1);
kpeter@80
   257
    checkConcept<ReadWriteMap<int, double>, ForkMap<RM, SM> >();
kpeter@80
   258
    checkConcept<ReadWriteMap<int, double>, ForkMap<SM, RM> >();
kpeter@80
   259
    ForkMap<RM, SM> map1(m1,m2);
kpeter@80
   260
    ForkMap<SM, RM> map2 = forkMap(m2,m1);
kpeter@80
   261
    map2.set(5, 10);
alpar@210
   262
    check(m1[1] == -1 && m1[5] == 10 && m2[1] == -1 &&
alpar@210
   263
          m2[5] == 10 && map2[1] == -1 && map2[5] == 10,
kpeter@80
   264
          "Something is wrong with ForkMap");
kpeter@80
   265
  }
kpeter@82
   266
kpeter@80
   267
  // Arithmetic maps:
kpeter@80
   268
  // - AddMap, SubMap, MulMap, DivMap
kpeter@80
   269
  // - ShiftMap, ShiftWriteMap, ScaleMap, ScaleWriteMap
kpeter@80
   270
  // - NegMap, NegWriteMap, AbsMap
kpeter@80
   271
  {
kpeter@80
   272
    checkConcept<DoubleMap, AddMap<DoubleMap,DoubleMap> >();
kpeter@80
   273
    checkConcept<DoubleMap, SubMap<DoubleMap,DoubleMap> >();
kpeter@80
   274
    checkConcept<DoubleMap, MulMap<DoubleMap,DoubleMap> >();
kpeter@80
   275
    checkConcept<DoubleMap, DivMap<DoubleMap,DoubleMap> >();
kpeter@82
   276
kpeter@80
   277
    ConstMap<int, double> c1(1.0), c2(3.14);
kpeter@80
   278
    IdentityMap<int> im;
kpeter@80
   279
    ConvertMap<IdentityMap<int>, double> id(im);
alpar@210
   280
    check(addMap(c1,id)[0] == 1.0  && addMap(c1,id)[10] == 11.0,
alpar@210
   281
          "Something is wrong with AddMap");
alpar@210
   282
    check(subMap(id,c1)[0] == -1.0 && subMap(id,c1)[10] == 9.0,
alpar@210
   283
          "Something is wrong with SubMap");
alpar@210
   284
    check(mulMap(id,c2)[0] == 0    && mulMap(id,c2)[2]  == 6.28,
alpar@210
   285
          "Something is wrong with MulMap");
alpar@210
   286
    check(divMap(c2,id)[1] == 3.14 && divMap(c2,id)[2]  == 1.57,
alpar@210
   287
          "Something is wrong with DivMap");
kpeter@82
   288
kpeter@80
   289
    checkConcept<DoubleMap, ShiftMap<DoubleMap> >();
kpeter@80
   290
    checkConcept<DoubleWriteMap, ShiftWriteMap<DoubleWriteMap> >();
kpeter@80
   291
    checkConcept<DoubleMap, ScaleMap<DoubleMap> >();
kpeter@80
   292
    checkConcept<DoubleWriteMap, ScaleWriteMap<DoubleWriteMap> >();
kpeter@80
   293
    checkConcept<DoubleMap, NegMap<DoubleMap> >();
kpeter@80
   294
    checkConcept<DoubleWriteMap, NegWriteMap<DoubleWriteMap> >();
kpeter@80
   295
    checkConcept<DoubleMap, AbsMap<DoubleMap> >();
alpar@25
   296
kpeter@80
   297
    check(shiftMap(id, 2.0)[1] == 3.0 && shiftMap(id, 2.0)[10] == 12.0,
kpeter@80
   298
          "Something is wrong with ShiftMap");
alpar@210
   299
    check(shiftWriteMap(id, 2.0)[1] == 3.0 &&
alpar@210
   300
          shiftWriteMap(id, 2.0)[10] == 12.0,
kpeter@80
   301
          "Something is wrong with ShiftWriteMap");
kpeter@80
   302
    check(scaleMap(id, 2.0)[1] == 2.0 && scaleMap(id, 2.0)[10] == 20.0,
kpeter@80
   303
          "Something is wrong with ScaleMap");
alpar@210
   304
    check(scaleWriteMap(id, 2.0)[1] == 2.0 &&
alpar@210
   305
          scaleWriteMap(id, 2.0)[10] == 20.0,
kpeter@80
   306
          "Something is wrong with ScaleWriteMap");
kpeter@80
   307
    check(negMap(id)[1] == -1.0 && negMap(id)[-10] == 10.0,
kpeter@80
   308
          "Something is wrong with NegMap");
kpeter@80
   309
    check(negWriteMap(id)[1] == -1.0 && negWriteMap(id)[-10] == 10.0,
kpeter@80
   310
          "Something is wrong with NegWriteMap");
kpeter@80
   311
    check(absMap(id)[1] == 1.0 && absMap(id)[-10] == 10.0,
kpeter@80
   312
          "Something is wrong with AbsMap");
kpeter@80
   313
  }
kpeter@82
   314
kpeter@82
   315
  // Logical maps:
kpeter@82
   316
  // - TrueMap, FalseMap
kpeter@82
   317
  // - AndMap, OrMap
kpeter@82
   318
  // - NotMap, NotWriteMap
kpeter@82
   319
  // - EqualMap, LessMap
kpeter@80
   320
  {
kpeter@82
   321
    checkConcept<BoolMap, TrueMap<A> >();
kpeter@82
   322
    checkConcept<BoolMap, FalseMap<A> >();
kpeter@82
   323
    checkConcept<BoolMap, AndMap<BoolMap,BoolMap> >();
kpeter@82
   324
    checkConcept<BoolMap, OrMap<BoolMap,BoolMap> >();
kpeter@80
   325
    checkConcept<BoolMap, NotMap<BoolMap> >();
kpeter@80
   326
    checkConcept<BoolWriteMap, NotWriteMap<BoolWriteMap> >();
kpeter@82
   327
    checkConcept<BoolMap, EqualMap<DoubleMap,DoubleMap> >();
kpeter@82
   328
    checkConcept<BoolMap, LessMap<DoubleMap,DoubleMap> >();
kpeter@82
   329
kpeter@82
   330
    TrueMap<int> tm;
kpeter@82
   331
    FalseMap<int> fm;
kpeter@80
   332
    RangeMap<bool> rm(2);
kpeter@80
   333
    rm[0] = true; rm[1] = false;
alpar@210
   334
    check(andMap(tm,rm)[0] && !andMap(tm,rm)[1] &&
alpar@210
   335
          !andMap(fm,rm)[0] && !andMap(fm,rm)[1],
kpeter@82
   336
          "Something is wrong with AndMap");
alpar@210
   337
    check(orMap(tm,rm)[0] && orMap(tm,rm)[1] &&
alpar@210
   338
          orMap(fm,rm)[0] && !orMap(fm,rm)[1],
kpeter@82
   339
          "Something is wrong with OrMap");
alpar@210
   340
    check(!notMap(rm)[0] && notMap(rm)[1],
alpar@210
   341
          "Something is wrong with NotMap");
alpar@210
   342
    check(!notWriteMap(rm)[0] && notWriteMap(rm)[1],
alpar@210
   343
          "Something is wrong with NotWriteMap");
kpeter@82
   344
kpeter@82
   345
    ConstMap<int, double> cm(2.0);
kpeter@82
   346
    IdentityMap<int> im;
kpeter@82
   347
    ConvertMap<IdentityMap<int>, double> id(im);
kpeter@82
   348
    check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3],
kpeter@82
   349
          "Something is wrong with LessMap");
kpeter@82
   350
    check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3],
kpeter@82
   351
          "Something is wrong with EqualMap");
kpeter@80
   352
  }
alpar@209
   353
kpeter@167
   354
  // LoggerBoolMap
kpeter@159
   355
  {
kpeter@159
   356
    typedef std::vector<int> vec;
kpeter@720
   357
    checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >();
kpeter@720
   358
    checkConcept<WriteMap<int, bool>,
kpeter@720
   359
                 LoggerBoolMap<std::back_insert_iterator<vec> > >();
kpeter@720
   360
kpeter@159
   361
    vec v1;
kpeter@159
   362
    vec v2(10);
alpar@210
   363
    LoggerBoolMap<std::back_insert_iterator<vec> >
alpar@210
   364
      map1(std::back_inserter(v1));
kpeter@167
   365
    LoggerBoolMap<vec::iterator> map2(v2.begin());
kpeter@159
   366
    map1.set(10, false);
kpeter@159
   367
    map1.set(20, true);   map2.set(20, true);
kpeter@159
   368
    map1.set(30, false);  map2.set(40, false);
kpeter@159
   369
    map1.set(50, true);   map2.set(50, true);
kpeter@159
   370
    map1.set(60, true);   map2.set(60, true);
kpeter@159
   371
    check(v1.size() == 3 && v2.size() == 10 &&
alpar@210
   372
          v1[0]==20 && v1[1]==50 && v1[2]==60 &&
alpar@210
   373
          v2[0]==20 && v2[1]==50 && v2[2]==60,
kpeter@167
   374
          "Something is wrong with LoggerBoolMap");
alpar@209
   375
kpeter@159
   376
    int i = 0;
kpeter@167
   377
    for ( LoggerBoolMap<vec::iterator>::Iterator it = map2.begin();
kpeter@159
   378
          it != map2.end(); ++it )
kpeter@167
   379
      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
kpeter@723
   380
    
kpeter@723
   381
    typedef ListDigraph Graph;
kpeter@723
   382
    DIGRAPH_TYPEDEFS(Graph);
kpeter@723
   383
    Graph gr;
kpeter@723
   384
kpeter@723
   385
    Node n0 = gr.addNode();
kpeter@723
   386
    Node n1 = gr.addNode();
kpeter@723
   387
    Node n2 = gr.addNode();
kpeter@723
   388
    Node n3 = gr.addNode();
kpeter@723
   389
    
kpeter@723
   390
    gr.addArc(n3, n0);
kpeter@723
   391
    gr.addArc(n3, n2);
kpeter@723
   392
    gr.addArc(n0, n2);
kpeter@723
   393
    gr.addArc(n2, n1);
kpeter@723
   394
    gr.addArc(n0, n1);
kpeter@723
   395
    
kpeter@723
   396
    {
kpeter@723
   397
      std::vector<Node> v;
kpeter@723
   398
      dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run();
kpeter@723
   399
kpeter@723
   400
      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
kpeter@723
   401
            "Something is wrong with LoggerBoolMap");
kpeter@723
   402
    }
kpeter@723
   403
    {
kpeter@723
   404
      std::vector<Node> v(countNodes(gr));
kpeter@723
   405
      dfs(gr).processedMap(loggerBoolMap(v.begin())).run();
kpeter@723
   406
      
kpeter@723
   407
      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
kpeter@723
   408
            "Something is wrong with LoggerBoolMap");
kpeter@723
   409
    }
kpeter@694
   410
  }
kpeter@684
   411
  
kpeter@720
   412
  // IdMap, RangeIdMap
kpeter@720
   413
  {
kpeter@720
   414
    typedef ListDigraph Graph;
kpeter@720
   415
    DIGRAPH_TYPEDEFS(Graph);
kpeter@720
   416
kpeter@720
   417
    checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >();
kpeter@720
   418
    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();
kpeter@720
   419
    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();
kpeter@720
   420
    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();
kpeter@720
   421
    
kpeter@720
   422
    Graph gr;
kpeter@720
   423
    IdMap<Graph, Node> nmap(gr);
kpeter@720
   424
    IdMap<Graph, Arc> amap(gr);
kpeter@720
   425
    RangeIdMap<Graph, Node> nrmap(gr);
kpeter@720
   426
    RangeIdMap<Graph, Arc> armap(gr);
kpeter@720
   427
    
kpeter@720
   428
    Node n0 = gr.addNode();
kpeter@720
   429
    Node n1 = gr.addNode();
kpeter@720
   430
    Node n2 = gr.addNode();
kpeter@720
   431
    
kpeter@720
   432
    Arc a0 = gr.addArc(n0, n1);
kpeter@720
   433
    Arc a1 = gr.addArc(n0, n2);
kpeter@720
   434
    Arc a2 = gr.addArc(n2, n1);
kpeter@720
   435
    Arc a3 = gr.addArc(n2, n0);
kpeter@720
   436
    
kpeter@720
   437
    check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap");
kpeter@720
   438
    check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap");
kpeter@720
   439
    check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap");
kpeter@720
   440
kpeter@720
   441
    check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap");
kpeter@720
   442
    check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap");
kpeter@720
   443
    check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap");
kpeter@720
   444
    check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap");
kpeter@720
   445
kpeter@720
   446
    check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap");
kpeter@720
   447
    check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap");
kpeter@720
   448
    
kpeter@720
   449
    check(nrmap.size() == 3 && armap.size() == 4,
kpeter@720
   450
          "Wrong RangeIdMap::size()");
kpeter@720
   451
kpeter@720
   452
    check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap");
kpeter@720
   453
    check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap");
kpeter@720
   454
    check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap");
kpeter@720
   455
    
kpeter@720
   456
    check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap");
kpeter@720
   457
    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
kpeter@720
   458
    check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap");
kpeter@720
   459
    check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap");
kpeter@720
   460
kpeter@720
   461
    check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap");
kpeter@720
   462
    check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap");
kpeter@720
   463
    
kpeter@720
   464
    gr.erase(n1);
kpeter@720
   465
    
kpeter@720
   466
    if (nrmap[n0] == 1) nrmap.swap(n0, n2);
kpeter@720
   467
    nrmap.swap(n2, n0);
kpeter@720
   468
    if (armap[a1] == 1) armap.swap(a1, a3);
kpeter@720
   469
    armap.swap(a3, a1);
kpeter@720
   470
    
kpeter@720
   471
    check(nrmap.size() == 2 && armap.size() == 2,
kpeter@720
   472
          "Wrong RangeIdMap::size()");
kpeter@720
   473
kpeter@720
   474
    check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap");
kpeter@720
   475
    check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap");
kpeter@720
   476
    
kpeter@720
   477
    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
kpeter@720
   478
    check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap");
kpeter@720
   479
kpeter@720
   480
    check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap");
kpeter@720
   481
    check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap");
kpeter@720
   482
  }
kpeter@720
   483
  
kpeter@723
   484
  // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap
kpeter@723
   485
  {
kpeter@723
   486
    typedef ListGraph Graph;
kpeter@723
   487
    GRAPH_TYPEDEFS(Graph);
kpeter@723
   488
    
kpeter@723
   489
    checkConcept<ReadMap<Arc, Node>, SourceMap<Graph> >();
kpeter@723
   490
    checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >();
kpeter@723
   491
    checkConcept<ReadMap<Edge, Arc>, ForwardMap<Graph> >();
kpeter@723
   492
    checkConcept<ReadMap<Edge, Arc>, BackwardMap<Graph> >();
kpeter@723
   493
    checkConcept<ReadMap<Node, int>, InDegMap<Graph> >();
kpeter@723
   494
    checkConcept<ReadMap<Node, int>, OutDegMap<Graph> >();
kpeter@723
   495
kpeter@723
   496
    Graph gr;
kpeter@723
   497
    Node n0 = gr.addNode();
kpeter@723
   498
    Node n1 = gr.addNode();
kpeter@723
   499
    Node n2 = gr.addNode();
kpeter@723
   500
    
kpeter@723
   501
    gr.addEdge(n0,n1);
kpeter@723
   502
    gr.addEdge(n1,n2);
kpeter@723
   503
    gr.addEdge(n0,n2);
kpeter@723
   504
    gr.addEdge(n2,n1);
kpeter@723
   505
    gr.addEdge(n1,n2);
kpeter@723
   506
    gr.addEdge(n0,n1);
kpeter@723
   507
    
kpeter@723
   508
    for (EdgeIt e(gr); e != INVALID; ++e) {
kpeter@723
   509
      check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");
kpeter@723
   510
      check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");
kpeter@723
   511
    }
kpeter@723
   512
    
kpeter@789
   513
    check(mapCompare(gr,
kpeter@789
   514
          sourceMap(orienter(gr, constMap<Edge, bool>(true))),
kpeter@789
   515
          targetMap(orienter(gr, constMap<Edge, bool>(false)))),
kpeter@789
   516
          "Wrong SourceMap or TargetMap");
kpeter@723
   517
kpeter@723
   518
    typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
kpeter@723
   519
    Digraph dgr(gr, constMap<Edge, bool>(true));
kpeter@723
   520
    OutDegMap<Digraph> odm(dgr);
kpeter@723
   521
    InDegMap<Digraph> idm(dgr);
kpeter@723
   522
    
kpeter@723
   523
    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap");
kpeter@723
   524
    check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
kpeter@723
   525
   
kpeter@723
   526
    gr.addEdge(n2, n0);
kpeter@723
   527
kpeter@723
   528
    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap");
kpeter@723
   529
    check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
kpeter@723
   530
  }
kpeter@723
   531
  
kpeter@684
   532
  // CrossRefMap
kpeter@684
   533
  {
kpeter@684
   534
    typedef ListDigraph Graph;
kpeter@684
   535
    DIGRAPH_TYPEDEFS(Graph);
kpeter@684
   536
kpeter@684
   537
    checkConcept<ReadWriteMap<Node, int>,
kpeter@684
   538
                 CrossRefMap<Graph, Node, int> >();
kpeter@720
   539
    checkConcept<ReadWriteMap<Node, bool>,
kpeter@720
   540
                 CrossRefMap<Graph, Node, bool> >();
kpeter@720
   541
    checkConcept<ReadWriteMap<Node, double>,
kpeter@720
   542
                 CrossRefMap<Graph, Node, double> >();
kpeter@684
   543
    
kpeter@684
   544
    Graph gr;
kpeter@684
   545
    typedef CrossRefMap<Graph, Node, char> CRMap;
kpeter@684
   546
    CRMap map(gr);
kpeter@684
   547
    
kpeter@684
   548
    Node n0 = gr.addNode();
kpeter@684
   549
    Node n1 = gr.addNode();
kpeter@684
   550
    Node n2 = gr.addNode();
kpeter@684
   551
    
kpeter@684
   552
    map.set(n0, 'A');
kpeter@684
   553
    map.set(n1, 'B');
kpeter@684
   554
    map.set(n2, 'C');
kpeter@720
   555
    
kpeter@720
   556
    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,
kpeter@720
   557
          "Wrong CrossRefMap");
kpeter@720
   558
    check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1,
kpeter@720
   559
          "Wrong CrossRefMap");
kpeter@720
   560
    check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2,
kpeter@720
   561
          "Wrong CrossRefMap");
kpeter@720
   562
    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
kpeter@720
   563
          "Wrong CrossRefMap::count()");
kpeter@720
   564
    
kpeter@724
   565
    CRMap::ValueIt it = map.beginValue();
kpeter@720
   566
    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
kpeter@720
   567
          it == map.endValue(), "Wrong value iterator");
kpeter@720
   568
    
kpeter@684
   569
    map.set(n2, 'A');
kpeter@720
   570
kpeter@720
   571
    check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A',
kpeter@720
   572
          "Wrong CrossRefMap");
kpeter@720
   573
    check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap");
kpeter@720
   574
    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
kpeter@720
   575
    check(map('C') == INVALID && map.inverse()['C'] == INVALID,
kpeter@720
   576
          "Wrong CrossRefMap");
kpeter@720
   577
    check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0,
kpeter@720
   578
          "Wrong CrossRefMap::count()");
kpeter@720
   579
kpeter@720
   580
    it = map.beginValue();
kpeter@720
   581
    check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' &&
kpeter@720
   582
          it == map.endValue(), "Wrong value iterator");
kpeter@720
   583
kpeter@684
   584
    map.set(n0, 'C');
kpeter@684
   585
kpeter@684
   586
    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
kpeter@684
   587
          "Wrong CrossRefMap");
kpeter@684
   588
    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
kpeter@684
   589
    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
kpeter@684
   590
    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
kpeter@720
   591
    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
kpeter@720
   592
          "Wrong CrossRefMap::count()");
kpeter@684
   593
kpeter@720
   594
    it = map.beginValue();
kpeter@684
   595
    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
kpeter@684
   596
          it == map.endValue(), "Wrong value iterator");
kpeter@159
   597
  }
alpar@25
   598
kpeter@684
   599
  // CrossRefMap
kpeter@684
   600
  {
alpar@695
   601
    typedef SmartDigraph Graph;
kpeter@684
   602
    DIGRAPH_TYPEDEFS(Graph);
kpeter@684
   603
kpeter@684
   604
    checkConcept<ReadWriteMap<Node, int>,
kpeter@684
   605
                 CrossRefMap<Graph, Node, int> >();
kpeter@684
   606
    
kpeter@684
   607
    Graph gr;
kpeter@684
   608
    typedef CrossRefMap<Graph, Node, char> CRMap;
kpeter@684
   609
    typedef CRMap::ValueIterator ValueIt;
kpeter@684
   610
    CRMap map(gr);
kpeter@684
   611
    
kpeter@684
   612
    Node n0 = gr.addNode();
kpeter@684
   613
    Node n1 = gr.addNode();
kpeter@684
   614
    Node n2 = gr.addNode();
kpeter@684
   615
    
kpeter@684
   616
    map.set(n0, 'A');
kpeter@684
   617
    map.set(n1, 'B');
kpeter@684
   618
    map.set(n2, 'C');
kpeter@684
   619
    map.set(n2, 'A');
kpeter@684
   620
    map.set(n0, 'C');
kpeter@684
   621
kpeter@684
   622
    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
kpeter@684
   623
          "Wrong CrossRefMap");
kpeter@684
   624
    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
kpeter@684
   625
    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
kpeter@684
   626
    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
kpeter@684
   627
kpeter@684
   628
    ValueIt it = map.beginValue();
kpeter@684
   629
    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
kpeter@684
   630
          it == map.endValue(), "Wrong value iterator");
kpeter@684
   631
  }
alpar@695
   632
  
deba@693
   633
  // Iterable bool map
deba@693
   634
  {
deba@693
   635
    typedef SmartGraph Graph;
deba@693
   636
    typedef SmartGraph::Node Item;
deba@693
   637
deba@693
   638
    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
kpeter@694
   639
    checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
deba@693
   640
deba@693
   641
    const int num = 10;
deba@693
   642
    Graph g;
deba@693
   643
    std::vector<Item> items;
deba@693
   644
    for (int i = 0; i < num; ++i) {
deba@693
   645
      items.push_back(g.addNode());
deba@693
   646
    }
deba@693
   647
deba@693
   648
    Ibm map1(g, true);
deba@693
   649
    int n = 0;
deba@693
   650
    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
deba@693
   651
      check(map1[static_cast<Item>(it)], "Wrong TrueIt");
deba@693
   652
      ++n;
deba@693
   653
    }
deba@693
   654
    check(n == num, "Wrong number");
deba@693
   655
deba@693
   656
    n = 0;
deba@693
   657
    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
deba@693
   658
        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
deba@693
   659
        ++n;
deba@693
   660
    }
deba@693
   661
    check(n == num, "Wrong number");
deba@693
   662
    check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
deba@693
   663
    check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
deba@693
   664
deba@693
   665
    map1[items[5]] = true;
deba@693
   666
deba@693
   667
    n = 0;
deba@693
   668
    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
deba@693
   669
        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
deba@693
   670
        ++n;
deba@693
   671
    }
deba@693
   672
    check(n == num, "Wrong number");
deba@693
   673
deba@693
   674
    map1[items[num / 2]] = false;
deba@693
   675
    check(map1[items[num / 2]] == false, "Wrong map value");
deba@693
   676
deba@693
   677
    n = 0;
deba@693
   678
    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
deba@693
   679
        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
deba@693
   680
        ++n;
deba@693
   681
    }
deba@693
   682
    check(n == num - 1, "Wrong number");
deba@693
   683
deba@693
   684
    n = 0;
deba@693
   685
    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
deba@693
   686
        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
deba@693
   687
        ++n;
deba@693
   688
    }
deba@693
   689
    check(n == 1, "Wrong number");
deba@693
   690
deba@693
   691
    map1[items[0]] = false;
deba@693
   692
    check(map1[items[0]] == false, "Wrong map value");
deba@693
   693
deba@693
   694
    map1[items[num - 1]] = false;
deba@693
   695
    check(map1[items[num - 1]] == false, "Wrong map value");
deba@693
   696
deba@693
   697
    n = 0;
deba@693
   698
    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
deba@693
   699
        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
deba@693
   700
        ++n;
deba@693
   701
    }
deba@693
   702
    check(n == num - 3, "Wrong number");
deba@693
   703
    check(map1.trueNum() == num - 3, "Wrong number");
deba@693
   704
deba@693
   705
    n = 0;
deba@693
   706
    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
deba@693
   707
        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
deba@693
   708
        ++n;
deba@693
   709
    }
deba@693
   710
    check(n == 3, "Wrong number");
deba@693
   711
    check(map1.falseNum() == 3, "Wrong number");
deba@693
   712
  }
deba@693
   713
deba@693
   714
  // Iterable int map
deba@693
   715
  {
deba@693
   716
    typedef SmartGraph Graph;
deba@693
   717
    typedef SmartGraph::Node Item;
deba@693
   718
    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
deba@693
   719
kpeter@694
   720
    checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
deba@693
   721
deba@693
   722
    const int num = 10;
deba@693
   723
    Graph g;
deba@693
   724
    std::vector<Item> items;
deba@693
   725
    for (int i = 0; i < num; ++i) {
deba@693
   726
      items.push_back(g.addNode());
deba@693
   727
    }
deba@693
   728
deba@693
   729
    Iim map1(g);
deba@693
   730
    check(map1.size() == 0, "Wrong size");
deba@693
   731
deba@693
   732
    for (int i = 0; i < num; ++i) {
deba@693
   733
      map1[items[i]] = i;
deba@693
   734
    }
deba@693
   735
    check(map1.size() == num, "Wrong size");
deba@693
   736
deba@693
   737
    for (int i = 0; i < num; ++i) {
deba@693
   738
      Iim::ItemIt it(map1, i);
deba@693
   739
      check(static_cast<Item>(it) == items[i], "Wrong value");
deba@693
   740
      ++it;
deba@693
   741
      check(static_cast<Item>(it) == INVALID, "Wrong value");
deba@693
   742
    }
deba@693
   743
deba@693
   744
    for (int i = 0; i < num; ++i) {
deba@693
   745
      map1[items[i]] = i % 2;
deba@693
   746
    }
deba@693
   747
    check(map1.size() == 2, "Wrong size");
deba@693
   748
deba@693
   749
    int n = 0;
deba@693
   750
    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
kpeter@694
   751
      check(map1[static_cast<Item>(it)] == 0, "Wrong value");
deba@693
   752
      ++n;
deba@693
   753
    }
deba@693
   754
    check(n == (num + 1) / 2, "Wrong number");
deba@693
   755
deba@693
   756
    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
kpeter@694
   757
      check(map1[static_cast<Item>(it)] == 1, "Wrong value");
deba@693
   758
      ++n;
deba@693
   759
    }
deba@693
   760
    check(n == num, "Wrong number");
deba@693
   761
deba@693
   762
  }
deba@693
   763
deba@693
   764
  // Iterable value map
deba@693
   765
  {
deba@693
   766
    typedef SmartGraph Graph;
deba@693
   767
    typedef SmartGraph::Node Item;
deba@693
   768
    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
deba@693
   769
deba@693
   770
    checkConcept<ReadWriteMap<Item, double>, Ivm>();
deba@693
   771
deba@693
   772
    const int num = 10;
deba@693
   773
    Graph g;
deba@693
   774
    std::vector<Item> items;
deba@693
   775
    for (int i = 0; i < num; ++i) {
deba@693
   776
      items.push_back(g.addNode());
deba@693
   777
    }
deba@693
   778
deba@693
   779
    Ivm map1(g, 0.0);
deba@693
   780
    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
deba@693
   781
    check(*map1.beginValue() == 0.0, "Wrong value");
deba@693
   782
deba@693
   783
    for (int i = 0; i < num; ++i) {
deba@693
   784
      map1.set(items[i], static_cast<double>(i));
deba@693
   785
    }
deba@693
   786
    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
deba@693
   787
deba@693
   788
    for (int i = 0; i < num; ++i) {
deba@693
   789
      Ivm::ItemIt it(map1, static_cast<double>(i));
deba@693
   790
      check(static_cast<Item>(it) == items[i], "Wrong value");
deba@693
   791
      ++it;
deba@693
   792
      check(static_cast<Item>(it) == INVALID, "Wrong value");
deba@693
   793
    }
deba@693
   794
kpeter@724
   795
    for (Ivm::ValueIt vit = map1.beginValue();
deba@693
   796
         vit != map1.endValue(); ++vit) {
deba@693
   797
      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
kpeter@724
   798
            "Wrong ValueIt");
deba@693
   799
    }
deba@693
   800
deba@693
   801
    for (int i = 0; i < num; ++i) {
deba@693
   802
      map1.set(items[i], static_cast<double>(i % 2));
deba@693
   803
    }
deba@693
   804
    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
deba@693
   805
deba@693
   806
    int n = 0;
deba@693
   807
    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
kpeter@694
   808
      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
deba@693
   809
      ++n;
deba@693
   810
    }
deba@693
   811
    check(n == (num + 1) / 2, "Wrong number");
deba@693
   812
deba@693
   813
    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
kpeter@694
   814
      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
deba@693
   815
      ++n;
deba@693
   816
    }
deba@693
   817
    check(n == num, "Wrong number");
deba@693
   818
deba@693
   819
  }
kpeter@789
   820
  
kpeter@789
   821
  // Graph map utilities:
kpeter@789
   822
  // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
kpeter@789
   823
  // mapFind(), mapFindIf(), mapCount(), mapCountIf()
kpeter@789
   824
  // mapCopy(), mapCompare(), mapFill()
kpeter@789
   825
  {
kpeter@789
   826
    DIGRAPH_TYPEDEFS(SmartDigraph);
kpeter@789
   827
kpeter@789
   828
    SmartDigraph g;
kpeter@789
   829
    Node n1 = g.addNode();
kpeter@789
   830
    Node n2 = g.addNode();
kpeter@789
   831
    Node n3 = g.addNode();
kpeter@789
   832
    
kpeter@789
   833
    SmartDigraph::NodeMap<int> map1(g);
kpeter@789
   834
    SmartDigraph::ArcMap<char> map2(g);
kpeter@789
   835
    ConstMap<Node, A> cmap1 = A();
kpeter@789
   836
    ConstMap<Arc, C> cmap2 = C(0);
kpeter@789
   837
    
kpeter@789
   838
    map1[n1] = 10;
kpeter@789
   839
    map1[n2] = 5;
kpeter@789
   840
    map1[n3] = 12;
kpeter@789
   841
    
kpeter@789
   842
    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
kpeter@789
   843
    check(mapMin(g, map1) == n2, "Wrong mapMin()");
kpeter@789
   844
    check(mapMax(g, map1) == n3, "Wrong mapMax()");
kpeter@789
   845
    check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()");
kpeter@789
   846
    check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()");
kpeter@789
   847
    check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()");
kpeter@789
   848
    check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()");
kpeter@789
   849
kpeter@789
   850
    check(mapMin(g, map2) == INVALID, "Wrong mapMin()");
kpeter@789
   851
    check(mapMax(g, map2) == INVALID, "Wrong mapMax()");
kpeter@789
   852
kpeter@789
   853
    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
kpeter@789
   854
    check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()");
kpeter@789
   855
kpeter@789
   856
    Arc a1 = g.addArc(n1, n2);
kpeter@789
   857
    Arc a2 = g.addArc(n1, n3);
kpeter@789
   858
    Arc a3 = g.addArc(n2, n3);
kpeter@789
   859
    Arc a4 = g.addArc(n3, n1);
kpeter@789
   860
    
kpeter@789
   861
    map2[a1] = 'b';
kpeter@789
   862
    map2[a2] = 'a';
kpeter@789
   863
    map2[a3] = 'b';
kpeter@789
   864
    map2[a4] = 'c';
kpeter@789
   865
kpeter@789
   866
    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
kpeter@789
   867
    check(mapMin(g, map2) == a2, "Wrong mapMin()");
kpeter@789
   868
    check(mapMax(g, map2) == a4, "Wrong mapMax()");
kpeter@789
   869
    check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()");
kpeter@789
   870
    check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()");
kpeter@789
   871
    check(mapMinValue(g, map2, std::greater<int>()) == 'c',
kpeter@789
   872
          "Wrong mapMinValue()");
kpeter@789
   873
    check(mapMaxValue(g, map2, std::greater<int>()) == 'a',
kpeter@789
   874
          "Wrong mapMaxValue()");
kpeter@789
   875
kpeter@789
   876
    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
kpeter@789
   877
    check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()");
kpeter@789
   878
    check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()");
kpeter@789
   879
kpeter@789
   880
    check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2,
kpeter@789
   881
          "Wrong mapMin()");
kpeter@789
   882
    check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4,
kpeter@789
   883
          "Wrong mapMax()");
kpeter@789
   884
    check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'),
kpeter@789
   885
          "Wrong mapMinValue()");
kpeter@789
   886
    check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'),
kpeter@789
   887
          "Wrong mapMaxValue()");
kpeter@789
   888
kpeter@789
   889
    // mapFind(), mapFindIf()
kpeter@789
   890
    check(mapFind(g, map1, 5) == n2, "Wrong mapFind()");
kpeter@789
   891
    check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()");
kpeter@789
   892
    check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()");
kpeter@789
   893
    check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()");
kpeter@789
   894
    check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()");
kpeter@789
   895
    check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()");
kpeter@789
   896
kpeter@789
   897
    check(mapFindIf(g, map1, Less<int>(7)) == n2,
kpeter@789
   898
          "Wrong mapFindIf()");
kpeter@789
   899
    check(mapFindIf(g, map1, Less<int>(5)) == INVALID,
kpeter@789
   900
          "Wrong mapFindIf()");
kpeter@789
   901
    check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g),
kpeter@789
   902
          "Wrong mapFindIf()");
kpeter@789
   903
    check(mapFindIf(g, map2, Less<char>('a')) == INVALID,
kpeter@789
   904
          "Wrong mapFindIf()");
kpeter@789
   905
kpeter@789
   906
    // mapCount(), mapCountIf()
kpeter@789
   907
    check(mapCount(g, map1, 5) == 1, "Wrong mapCount()");
kpeter@789
   908
    check(mapCount(g, map1, 6) == 0, "Wrong mapCount()");
kpeter@789
   909
    check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()");
kpeter@789
   910
    check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()");
kpeter@789
   911
    check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()");
kpeter@789
   912
    check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()");
kpeter@789
   913
    check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()");
kpeter@789
   914
kpeter@789
   915
    check(mapCountIf(g, map1, Less<int>(11)) == 2,
kpeter@789
   916
          "Wrong mapCountIf()");
kpeter@789
   917
    check(mapCountIf(g, map1, Less<int>(13)) == 3,
kpeter@789
   918
          "Wrong mapCountIf()");
kpeter@789
   919
    check(mapCountIf(g, map1, Less<int>(5)) == 0,
kpeter@789
   920
          "Wrong mapCountIf()");
kpeter@789
   921
    check(mapCountIf(g, map2, Less<char>('d')) == 4,
kpeter@789
   922
          "Wrong mapCountIf()");
kpeter@789
   923
    check(mapCountIf(g, map2, Less<char>('c')) == 3,
kpeter@789
   924
          "Wrong mapCountIf()");
kpeter@789
   925
    check(mapCountIf(g, map2, Less<char>('a')) == 0,
kpeter@789
   926
          "Wrong mapCountIf()");
kpeter@789
   927
     
kpeter@789
   928
    // MapIt, ConstMapIt
kpeter@789
   929
/*
kpeter@789
   930
These tests can be used after applying bugfix #330
kpeter@789
   931
    typedef SmartDigraph::NodeMap<int>::MapIt MapIt;
kpeter@789
   932
    typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt;
kpeter@789
   933
    check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5,
kpeter@789
   934
          "Wrong NodeMap<>::MapIt");
kpeter@789
   935
    check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12,
kpeter@789
   936
          "Wrong NodeMap<>::MapIt");
kpeter@789
   937
    
kpeter@789
   938
    int sum = 0;
kpeter@789
   939
    std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum));
kpeter@789
   940
    check(sum == 27, "Wrong NodeMap<>::MapIt");
kpeter@789
   941
    std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum));
kpeter@789
   942
    check(sum == 54, "Wrong NodeMap<>::ConstMapIt");
kpeter@789
   943
*/
kpeter@789
   944
kpeter@789
   945
    // mapCopy(), mapCompare(), mapFill()
kpeter@789
   946
    check(mapCompare(g, map1, map1), "Wrong mapCompare()");
kpeter@789
   947
    check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()");
kpeter@789
   948
    check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()");
kpeter@789
   949
    check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()");
kpeter@789
   950
    check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()");
kpeter@789
   951
kpeter@789
   952
    SmartDigraph::NodeMap<int> map3(g, 0);
kpeter@789
   953
    SmartDigraph::ArcMap<char> map4(g, 'a');
kpeter@789
   954
    
kpeter@789
   955
    check(!mapCompare(g, map1, map3), "Wrong mapCompare()");
kpeter@789
   956
    check(!mapCompare(g, map2, map4), "Wrong mapCompare()");    
kpeter@789
   957
    
kpeter@789
   958
    mapCopy(g, map1, map3);
kpeter@789
   959
    mapCopy(g, map2, map4);
kpeter@789
   960
kpeter@789
   961
    check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()");
kpeter@789
   962
    check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");    
kpeter@789
   963
    
kpeter@789
   964
    Undirector<SmartDigraph> ug(g);
kpeter@789
   965
    Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x');
kpeter@789
   966
    Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14);
kpeter@789
   967
    
kpeter@789
   968
    check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
kpeter@789
   969
    check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
kpeter@789
   970
    check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
kpeter@789
   971
    check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
kpeter@789
   972
    
kpeter@789
   973
    mapCopy(g, map2, umap1);
kpeter@789
   974
kpeter@789
   975
    check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
kpeter@789
   976
    check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
kpeter@789
   977
    check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
kpeter@789
   978
    check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
kpeter@789
   979
    
kpeter@789
   980
    mapCopy(g, map2, umap1);
kpeter@789
   981
    mapCopy(g, umap1, map2);
kpeter@789
   982
    mapCopy(ug, map2, umap1);
kpeter@789
   983
    mapCopy(ug, umap1, map2);
kpeter@789
   984
    
kpeter@789
   985
    check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
kpeter@789
   986
    mapCopy(ug, umap1, umap2);
kpeter@789
   987
    check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
kpeter@789
   988
    
kpeter@789
   989
    check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()");
kpeter@789
   990
    mapFill(g, map1, 2);
kpeter@789
   991
    check(mapCompare(g, constMap<Node>(2), map1), "Wrong mapFill()");
kpeter@789
   992
kpeter@789
   993
    check(!mapCompare(g, map2, constMap<Arc>('z')), "Wrong mapCompare()");
kpeter@789
   994
    mapCopy(g, constMap<Arc>('z'), map2);
kpeter@789
   995
    check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()");
kpeter@789
   996
  }
kpeter@789
   997
  
alpar@25
   998
  return 0;
alpar@25
   999
}