doc/adaptor_references.dox
author deba
Mon, 03 Oct 2005 10:17:53 +0000
changeset 1697 4c593a4096da
parent 1590 ba2cb5006358
permissions -rw-r--r--
Preliminary SplitGraphAdaptor
And some other improvments
deba@1418
     1
namespace lemon {
deba@1418
     2
/*!
deba@1418
     3
deba@1418
     4
\page adaptor-references Smart Reference Handling
deba@1418
     5
deba@1418
     6
The adaptor classes are very useful tools in the lemon library. It makes
deba@1418
     7
possible to create various data view of the current data structures without
deba@1418
     8
of the copy of them. This makes the lemon programming efficient and 
deba@1418
     9
consederably fast.
deba@1418
    10
deba@1418
    11
\section problem The problem
deba@1418
    12
deba@1418
    13
The adaptors usually use references or pointers to reference to an 
alpar@1591
    14
existing data structure. We may use an algorithm in the following way:
deba@1418
    15
\code
deba@1418
    16
function_algorithm(adaptor(structure));
deba@1418
    17
\endcode 
deba@1418
    18
deba@1418
    19
But what about the class algorithms:
deba@1418
    20
\code
deba@1418
    21
class_algorithm alg;
deba@1418
    22
alg.add(adaptor(structure));
deba@1418
    23
alg.run();
deba@1418
    24
\endcode
deba@1418
    25
The algorithm store a reference to the given structure. It is a created
deba@1418
    26
as temporarly and when the expression of the \c add() function is evaluated it
deba@1418
    27
will be destructed. It is very dangerous handling of the adaptors.
deba@1418
    28
deba@1418
    29
\section solution The solution
deba@1418
    30
deba@1418
    31
We made reference to a temporarly constructed adaptor but we should make
deba@1418
    32
a copy of the adaptor when it is given as parameter to a class.
deba@1418
    33
It is not impossible with a little tranformation of the code.
deba@1418
    34
deba@1418
    35
Let's first create some helper class:
deba@1418
    36
\code
deba@1418
    37
template <typename _Type, typename Enable = void>
deba@1418
    38
struct SmartConstReference {
deba@1418
    39
  typedef const _Type& Type;
deba@1418
    40
};
deba@1418
    41
  
deba@1418
    42
template <typename _Type>
deba@1418
    43
struct SmartConstReference<
deba@1418
    44
  _Type, 
deba@1418
    45
  typename enable_if<typename _Type::NeedCopy, void>::type
deba@1418
    46
> {
deba@1418
    47
  typedef const _Type Type;
deba@1418
    48
};
deba@1418
    49
\endcode
deba@1418
    50
Then we can place NeedCopy tags in the adaptor classes:
deba@1418
    51
\code
deba@1418
    52
template<class M1,class M2> 
deba@1418
    53
class AddMap {
deba@1418
    54
  typename SmartConstReference<M1>::Type m1;
deba@1418
    55
  typename SmartConstReference<M2>::Type m2;
deba@1418
    56
deba@1418
    57
public:
deba@1418
    58
deba@1418
    59
  typedef True NeedCopy;
deba@1418
    60
deba@1418
    61
  typedef typename M1::Key Key;
deba@1418
    62
  typedef typename M1::Value Value;
deba@1418
    63
deba@1418
    64
  AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
deba@1418
    65
  Value operator[](Key k) const {return m1[k]+m2[k];}
deba@1418
    66
};
deba@1418
    67
\endcode
deba@1418
    68
Then we can transform all of the template map and graph references to
deba@1418
    69
\c SmartConstReference<Map>::Type or \c SmartConstReference<Graph>::Type.
deba@1418
    70
This way we copy all of maps and graphs what we should copy but the
deba@1418
    71
greater data structures are not copied.
deba@1418
    72
deba@1418
    73
\section not-const If the adaptor is not const
deba@1418
    74
The solution is very similar but it gives an additional problem.
deba@1418
    75
We make the same \c SmartReferences:
deba@1418
    76
\code
deba@1418
    77
template <typename _Type, typename Enable = void>
deba@1418
    78
struct SmartReference {
deba@1418
    79
  typedef _Type& Type;
deba@1418
    80
};
deba@1418
    81
deba@1418
    82
template <typename _Type>
deba@1418
    83
struct SmartReference<
deba@1418
    84
  _Type, 
deba@1418
    85
  typename enable_if<typename _Type::NeedCopy, void>::type
deba@1418
    86
> {
deba@1418
    87
  typedef _Type Type;
deba@1418
    88
};
deba@1418
    89
\endcode
deba@1418
    90
Let's create a class that use it:
deba@1418
    91
\code
deba@1418
    92
template <typename Map>
deba@1418
    93
class Algorithm {
deba@1418
    94
public:
deba@1418
    95
  SmartReference<Map>::Type map;
deba@1418
    96
  Algorithm(Map& _map) : map(_map) {}
deba@1418
    97
  ...
deba@1418
    98
};
deba@1418
    99
\endcode
deba@1418
   100
But if we want to give an adaptor function as parameter
deba@1418
   101
it will be a compile error. The adaptor will be created as temporarly
deba@1418
   102
so it cannot give as reference just as const reference.
deba@1418
   103
deba@1418
   104
Make more helper class:
deba@1418
   105
\code
deba@1418
   106
template <typename _Type, typename Enable = void>
deba@1418
   107
struct SmartParameter {
deba@1418
   108
  typedef _Type& Type;
deba@1418
   109
};
deba@1418
   110
deba@1418
   111
template <typename _Type>
deba@1418
   112
struct SmartParameter<
deba@1418
   113
  _Type, 
deba@1418
   114
  typename enable_if<typename _Type::NeedCopy, void>::type
deba@1418
   115
> {
deba@1418
   116
  typedef const _Type& Type;
deba@1418
   117
};
deba@1418
   118
\endcode
deba@1418
   119
And the repaired code:
deba@1418
   120
\code
deba@1418
   121
template <typename Map>
deba@1418
   122
class Algorithm {
deba@1418
   123
public:
deba@1418
   124
  SmartReference<Map>::Type map;
deba@1418
   125
  Algorithm(SmartParameter<Map>::Type _map) : map(_map) {}
deba@1418
   126
  ...
deba@1418
   127
};
deba@1418
   128
\endcode
deba@1418
   129
But some times it does not help:
deba@1418
   130
\code
deba@1418
   131
class Algorithm {
deba@1418
   132
public:
deba@1418
   133
  ...
deba@1418
   134
deba@1418
   135
  template <typename Map>
deba@1418
   136
  void addMap(SmartParameter<Map>::Type _map) {
deba@1418
   137
    ...
deba@1418
   138
  }
deba@1418
   139
  ...
deba@1418
   140
};
deba@1418
   141
\endcode
deba@1418
   142
Actually, it is a good code but the template parameter should
deba@1418
   143
be written because it cannot be found out from the parameter type.
deba@1418
   144
This can be solved with a bigger transformation:
deba@1418
   145
\code
deba@1418
   146
class Algorithm {
deba@1418
   147
public:
deba@1418
   148
  ...
deba@1418
   149
deba@1418
   150
  template <typename Map>
deba@1418
   151
  void addMap(const Map& _map) {
deba@1418
   152
    _addMap<SmartParameter<Map>::Type, Map>(_map);
deba@1418
   153
  }
deba@1418
   154
  template <typename Map>
deba@1418
   155
  void addMap(const Map& _map) {
deba@1418
   156
    _addMap<SmartParameter<Map>::Type, Map>(_map);
deba@1418
   157
  }
deba@1418
   158
deba@1418
   159
private:
deba@1418
   160
  template <typename MapParameter, typename Map>
deba@1418
   161
  void _addMap(MapParameter _map) {
deba@1418
   162
    ...
deba@1418
   163
  }
deba@1418
   164
  ...
deba@1418
   165
};
deba@1418
   166
\endcode
deba@1418
   167
This way we solved the smart referencing problem.
deba@1418
   168
\author Balazs Dezso
deba@1418
   169
*/
deba@1418
   170
}