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