Handling smarter the references
authordeba
Sat, 14 May 2005 17:32:11 +0000
changeset 1418afaa773d0ad0
parent 1417 53c2a0ccc9a4
child 1419 c3244a26adb1
Handling smarter the references
It's used by the lemon IO and proposed by the adaptors.
doc/adaptor_references.dox
src/lemon/utility.h
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/doc/adaptor_references.dox	Sat May 14 17:32:11 2005 +0000
     1.3 @@ -0,0 +1,170 @@
     1.4 +namespace lemon {
     1.5 +/*!
     1.6 +
     1.7 +\page adaptor-references Smart Reference Handling
     1.8 +
     1.9 +The adaptor classes are very useful tools in the lemon library. It makes
    1.10 +possible to create various data view of the current data structures without
    1.11 +of the copy of them. This makes the lemon programming efficient and 
    1.12 +consederably fast.
    1.13 +
    1.14 +\section problem The problem
    1.15 +
    1.16 +The adaptors usually use references or pointers to reference to an 
    1.17 +existing data structure. We may use an algorithm in the next way:
    1.18 +\code
    1.19 +function_algorithm(adaptor(structure));
    1.20 +\endcode 
    1.21 +
    1.22 +But what about the class algorithms:
    1.23 +\code
    1.24 +class_algorithm alg;
    1.25 +alg.add(adaptor(structure));
    1.26 +alg.run();
    1.27 +\endcode
    1.28 +The algorithm store a reference to the given structure. It is a created
    1.29 +as temporarly and when the expression of the \c add() function is evaluated it
    1.30 +will be destructed. It is very dangerous handling of the adaptors.
    1.31 +
    1.32 +\section solution The solution
    1.33 +
    1.34 +We made reference to a temporarly constructed adaptor but we should make
    1.35 +a copy of the adaptor when it is given as parameter to a class.
    1.36 +It is not impossible with a little tranformation of the code.
    1.37 +
    1.38 +Let's first create some helper class:
    1.39 +\code
    1.40 +template <typename _Type, typename Enable = void>
    1.41 +struct SmartConstReference {
    1.42 +  typedef const _Type& Type;
    1.43 +};
    1.44 +  
    1.45 +template <typename _Type>
    1.46 +struct SmartConstReference<
    1.47 +  _Type, 
    1.48 +  typename enable_if<typename _Type::NeedCopy, void>::type
    1.49 +> {
    1.50 +  typedef const _Type Type;
    1.51 +};
    1.52 +\endcode
    1.53 +Then we can place NeedCopy tags in the adaptor classes:
    1.54 +\code
    1.55 +template<class M1,class M2> 
    1.56 +class AddMap {
    1.57 +  typename SmartConstReference<M1>::Type m1;
    1.58 +  typename SmartConstReference<M2>::Type m2;
    1.59 +
    1.60 +public:
    1.61 +
    1.62 +  typedef True NeedCopy;
    1.63 +
    1.64 +  typedef typename M1::Key Key;
    1.65 +  typedef typename M1::Value Value;
    1.66 +
    1.67 +  AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
    1.68 +  Value operator[](Key k) const {return m1[k]+m2[k];}
    1.69 +};
    1.70 +\endcode
    1.71 +Then we can transform all of the template map and graph references to
    1.72 +\c SmartConstReference<Map>::Type or \c SmartConstReference<Graph>::Type.
    1.73 +This way we copy all of maps and graphs what we should copy but the
    1.74 +greater data structures are not copied.
    1.75 +
    1.76 +\section not-const If the adaptor is not const
    1.77 +The solution is very similar but it gives an additional problem.
    1.78 +We make the same \c SmartReferences:
    1.79 +\code
    1.80 +template <typename _Type, typename Enable = void>
    1.81 +struct SmartReference {
    1.82 +  typedef _Type& Type;
    1.83 +};
    1.84 +
    1.85 +template <typename _Type>
    1.86 +struct SmartReference<
    1.87 +  _Type, 
    1.88 +  typename enable_if<typename _Type::NeedCopy, void>::type
    1.89 +> {
    1.90 +  typedef _Type Type;
    1.91 +};
    1.92 +\endcode
    1.93 +Let's create a class that use it:
    1.94 +\code
    1.95 +template <typename Map>
    1.96 +class Algorithm {
    1.97 +public:
    1.98 +  SmartReference<Map>::Type map;
    1.99 +  Algorithm(Map& _map) : map(_map) {}
   1.100 +  ...
   1.101 +};
   1.102 +\endcode
   1.103 +But if we want to give an adaptor function as parameter
   1.104 +it will be a compile error. The adaptor will be created as temporarly
   1.105 +so it cannot give as reference just as const reference.
   1.106 +
   1.107 +Make more helper class:
   1.108 +\code
   1.109 +template <typename _Type, typename Enable = void>
   1.110 +struct SmartParameter {
   1.111 +  typedef _Type& Type;
   1.112 +};
   1.113 +
   1.114 +template <typename _Type>
   1.115 +struct SmartParameter<
   1.116 +  _Type, 
   1.117 +  typename enable_if<typename _Type::NeedCopy, void>::type
   1.118 +> {
   1.119 +  typedef const _Type& Type;
   1.120 +};
   1.121 +\endcode
   1.122 +And the repaired code:
   1.123 +\code
   1.124 +template <typename Map>
   1.125 +class Algorithm {
   1.126 +public:
   1.127 +  SmartReference<Map>::Type map;
   1.128 +  Algorithm(SmartParameter<Map>::Type _map) : map(_map) {}
   1.129 +  ...
   1.130 +};
   1.131 +\endcode
   1.132 +But some times it does not help:
   1.133 +\code
   1.134 +class Algorithm {
   1.135 +public:
   1.136 +  ...
   1.137 +
   1.138 +  template <typename Map>
   1.139 +  void addMap(SmartParameter<Map>::Type _map) {
   1.140 +    ...
   1.141 +  }
   1.142 +  ...
   1.143 +};
   1.144 +\endcode
   1.145 +Actually, it is a good code but the template parameter should
   1.146 +be written because it cannot be found out from the parameter type.
   1.147 +This can be solved with a bigger transformation:
   1.148 +\code
   1.149 +class Algorithm {
   1.150 +public:
   1.151 +  ...
   1.152 +
   1.153 +  template <typename Map>
   1.154 +  void addMap(const Map& _map) {
   1.155 +    _addMap<SmartParameter<Map>::Type, Map>(_map);
   1.156 +  }
   1.157 +  template <typename Map>
   1.158 +  void addMap(const Map& _map) {
   1.159 +    _addMap<SmartParameter<Map>::Type, Map>(_map);
   1.160 +  }
   1.161 +
   1.162 +private:
   1.163 +  template <typename MapParameter, typename Map>
   1.164 +  void _addMap(MapParameter _map) {
   1.165 +    ...
   1.166 +  }
   1.167 +  ...
   1.168 +};
   1.169 +\endcode
   1.170 +This way we solved the smart referencing problem.
   1.171 +\author Balazs Dezso
   1.172 +*/
   1.173 +}
     2.1 --- a/src/lemon/utility.h	Sat May 14 17:29:28 2005 +0000
     2.2 +++ b/src/lemon/utility.h	Sat May 14 17:32:11 2005 +0000
     2.3 @@ -107,6 +107,47 @@
     2.4    template <class Cond, class T> 
     2.5    struct lazy_disable_if : public lazy_disable_if_c<Cond::value, T> {};
     2.6  
     2.7 +  // smart referencing
     2.8 +
     2.9 +  template <typename _Type, typename Enable = void>
    2.10 +  struct SmartReference {
    2.11 +    typedef _Type& Type;
    2.12 +  };
    2.13 +  
    2.14 +  template <typename _Type>
    2.15 +  struct SmartReference<
    2.16 +    _Type, 
    2.17 +    typename enable_if<typename _Type::NeedCopy, void>::type
    2.18 +  > {
    2.19 +    typedef _Type Type;
    2.20 +  };
    2.21 +
    2.22 +  template <typename _Type, typename Enable = void>
    2.23 +  struct SmartConstReference {
    2.24 +    typedef const _Type& Type;
    2.25 +  };
    2.26 +  
    2.27 +  template <typename _Type>
    2.28 +  struct SmartConstReference<
    2.29 +    _Type, 
    2.30 +    typename enable_if<typename _Type::NeedCopy, void>::type
    2.31 +  > {
    2.32 +    typedef const _Type Type;
    2.33 +  };
    2.34 +
    2.35 +  template <typename _Type, typename Enable = void>
    2.36 +  struct SmartParameter {
    2.37 +    typedef _Type& Type;
    2.38 +  };
    2.39 +  
    2.40 +  template <typename _Type>
    2.41 +  struct SmartParameter<
    2.42 +    _Type, 
    2.43 +    typename enable_if<typename _Type::NeedCopy, void>::type
    2.44 +  > {
    2.45 +    typedef const _Type& Type;
    2.46 +  };
    2.47 +
    2.48  } // namespace lemon
    2.49  
    2.50  #endif