source: trunk/yat/utility/iterator_traits.h @ 2472

Last change on this file since 2472 was 2472, checked in by Peter, 10 years ago

fixed some docs errors

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 10.8 KB
Line 
1#ifndef _theplu_yat_utility_iterator_traits_
2#define _theplu_yat_utility_iterator_traits_
3
4// $Id: iterator_traits.h 2472 2011-04-12 20:58:28Z peter $
5
6/*
7  Copyright (C) 2007 Jari Häkkinen, Peter Johansson
8  Copyright (C) 2008 Jari Häkkinen, Peter Johansson, Markus Ringnér
9  Copyright (C) 2010, 2011 Peter Johansson
10
11  This file is part of the yat library, http://dev.thep.lu.se/yat
12
13  The yat library is free software; you can redistribute it and/or
14  modify it under the terms of the GNU General Public License as
15  published by the Free Software Foundation; either version 3 of the
16  License, or (at your option) any later version.
17
18  The yat library is distributed in the hope that it will be useful,
19  but WITHOUT ANY WARRANTY; without even the implied warranty of
20  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21  General Public License for more details.
22
23  You should have received a copy of the GNU General Public License
24  along with yat. If not, see <http://www.gnu.org/licenses/>.
25*/
26
27#include "DataWeight.h"
28
29#include <boost/mpl/logical.hpp>
30#include <boost/type_traits/is_const.hpp>
31#include <boost/type_traits/is_convertible.hpp>
32#include <boost/type_traits/is_same.hpp>
33#include <boost/type_traits/remove_reference.hpp>
34#include <boost/utility/enable_if.hpp>
35
36#include <iterator>
37
38namespace theplu {
39namespace yat {
40namespace utility {
41
42  /**
43    Struct to be used to make compile-time decision that Iterator is
44    unweighted, which is the default.
45   */ 
46  struct unweighted_iterator_tag {};
47   
48  /**
49    Struct to be used to make compile-time decision that Iterator is
50    weighted. Some algorithms come also in a weighted version and
51    this tag could be used to decide on using them (rather than
52    the corresponding unweighted algorithm).
53   */ 
54  struct weighted_iterator_tag {};
55
56
57namespace detail {
58  /**
59     \internal
60
61     used in weighted_iterator_traits
62  */
63  template <typename T, typename Enable = void>
64  struct weighted_iterator_traits_detail {
65    /**
66       default is a iterator unweighted
67    */
68    typedef unweighted_iterator_tag type;
69  }; 
70
71  /**
72      \internal
73
74      specialization for iterators with value type convertible to DataWeight
75  */
76  template <typename T>
77  struct weighted_iterator_traits_detail<T, typename boost::enable_if<typename boost::is_convertible<T, DataWeight> >::type > {
78    /**
79       Iterators with value type convertible to DataWeight is weighted
80     */
81    typedef weighted_iterator_tag type;
82  }; 
83
84} // namespace detail
85
86
87  /**
88      Metafunction to decide whether an Iterator is weighted or
89      non-weighted. This (default) implementation returns
90      unweighted_iterator_tag, unless value_type of Iterator is
91      convertible to DataWeight in which case weighted_iterator_tag is
92      returned.
93  */
94  template <class Iterator>
95  struct weighted_iterator_traits
96  {
97  private:
98    typedef typename std::iterator_traits<Iterator>::value_type value;
99  public:
100    /**
101       \return weighted_iterator_tag if Iterator::value_type is
102       convertible to DataWeight
103     */
104    typedef typename detail::weighted_iterator_traits_detail<value>::type type;
105  };
106
107
108namespace detail {
109  /**
110     \internal
111
112    Metafunction that works on a pair weighted-unweighted types and
113    return weighted_type. The metafunction is specialized for
114    unweighted unweighted in which case unweighted is returned.
115   */
116  template <class T1, class T2>
117  struct unweighted_type_and {
118    /**
119       default return weighted_iterator_tag
120     */
121    typedef weighted_iterator_tag type;
122  };
123
124  /**
125     \internal
126
127    Specialization that sets type to be unweighted when both arguments
128    are unweighted
129   */
130  template <>
131  struct unweighted_type_and<unweighted_iterator_tag, unweighted_iterator_tag> {
132    /**
133       return unweighted_iterator_tag
134     */
135    typedef unweighted_iterator_tag type;
136  };
137} // namespace detail
138
139  /**
140    struct used to determine if a pair of iterators should be treated
141    as weighted. If both iterators are unweighted, type is set to
142    unweighted else weighted.
143  */
144  template <class T1, class T2>
145  struct weighted_if_any2 {
146  private:
147    typedef typename weighted_iterator_traits<T1>::type w_type1;
148    typedef typename weighted_iterator_traits<T2>::type w_type2;
149  public:
150    /// return unweighted if both are unweighted
151    typedef typename detail::unweighted_type_and<w_type1, w_type2>::type type;
152  };
153
154  /**
155    Same as weighted_iterator_traits2 but for 3 arguments.
156   */
157  template <class T1, class T2, class T3>
158  struct weighted_if_any3 {
159  private:
160    typedef typename weighted_if_any2<T1, T2>::type tmp;
161    typedef typename weighted_iterator_traits<T3>::type w_type3;
162  public:
163    /// return unweighted if all are unweighted
164    typedef typename detail::unweighted_type_and<tmp, w_type3>::type type;
165  };
166
167  namespace detail {
168    /**
169        \internal
170
171        check (at compile time) that iterator is unweighted.
172    */
173    inline void 
174    check_iterator_is_unweighted(utility::unweighted_iterator_tag x){} 
175  } // namespace detail
176
177  /**
178     \brief check (at compile time) that iterator is unweighted.
179
180     This function only compiles if iterator \a iter is unweighted.
181   */
182  template <class Iter>
183  void check_iterator_is_unweighted(Iter iter) 
184  { detail::check_iterator_is_unweighted(typename 
185                                 weighted_iterator_traits<Iter>::type());
186  }
187
188
189namespace detail {
190
191  /**
192     \internal
193
194     The following block of code is used to detect if weighted
195     iterators have functions 'double& data(void)' or if they only
196     have the const version.
197     
198     The technique used is taken from http://www.martinecker.com/wiki/
199   */
200  typedef char yes;
201  /**
202     \internal
203
204     This type (no) and type yes have different sizes and are used to
205     differentiate between the two cases.
206   */
207  typedef char (&no)[2];
208  /**
209     \internal
210
211     Overloaded function with template below. If there exists a
212     function that returns double& that will used and otherwise
213     overloaded template below will be used. This implementation and
214     template return different types to differentiate the two cases.
215   */
216  yes has_mutable(double&);
217  /**
218     \internal
219
220     Function used in iter_has_mutable_data and
221     iter_has_mutable_weight. The default case is used if function
222     called (e.g. data() does not return double&.
223   */
224  template<typename T>
225  no has_mutable(const T&);
226
227  /**
228     \internal
229
230     Struct to check if iterator has mutable data. *Iter must have a
231     function data(). If that function returns double& value is
232     true.
233   */
234  template <class Iter>
235  struct iter_has_mutable_data
236  {
237    /// instance of Iter
238    static Iter iter;
239    /// true if *iter has a function data() that returns double&
240    static const bool value = 
241      sizeof(has_mutable((*iter).data())) == sizeof(yes);
242  };
243
244
245  /**
246     \internal
247
248     Struct to check if iterator has mutable data. *Iter must have a
249     function data(). If that function returns double& value is
250     true.
251   */
252  template <class Iter>
253  struct iter_has_mutable_weight
254  {
255    /// instance of Iter
256    static Iter iter;
257    /// true if *iter has a function weight() that returns double&
258    static const bool value = 
259      sizeof(has_mutable((*iter).weight())) == sizeof(yes);
260  };
261
262
263  /**
264     \internal
265
266     Convenience meta-function. The struct is-a boost::true_type if
267     Iter is a weighted iterator
268
269     The purpose of the struct is to be used in boost::mpl, for
270     example, in boost::mpl::and_.
271
272     \see weighted_iterator_traits
273   */
274  template<typename Iter>
275  struct is_weighted 
276    : public boost::is_same<weighted_iterator_tag
277                            , typename weighted_iterator_traits<Iter>::type> 
278  {};
279
280  /**
281     \internal
282
283     same is_weighted but negated
284   */
285  template<typename Iter>
286  struct is_unweighted 
287    : public boost::is_same<unweighted_iterator_tag
288                            , typename weighted_iterator_traits<Iter>::type> 
289  {};
290
291
292  /**
293     \internal
294
295     Default implementation of iterator_traits_detail. Is supposed to
296     be used for unweighted iterators. Weighted iterators use
297     specialization below.
298   */
299  template <typename Iter, typename Enable = void>
300  struct iterator_traits_detail {
301    /**
302       for unweighted data_reference is reference
303    */
304    typedef typename std::iterator_traits<Iter>::reference data_reference;
305
306    /**
307       for unweighted weight_reference is a double
308    */
309    typedef const double weight_reference;
310
311    /**
312       \return * \a iter
313    */
314    data_reference data(Iter iter) const { return *iter; }
315
316    /**
317       \return 1.0
318    */
319    weight_reference weight(Iter iter) const { return 1.0; }
320  };
321
322  /**
323     \internal
324     Metafunction that returns double& if true and const double otherwise
325   */
326  template<bool>
327  struct mutable_reference {
328    /// return const double if bool is false
329    typedef const double type;
330  };
331
332  /**
333     \internal
334     Specialization that returns double& in true case
335  */
336  template<>
337  struct mutable_reference<true> {
338    /// return double& if bool is false
339    typedef double& type;
340  };
341
342
343  /**
344     \internal
345
346     Specialization for weighted iterators
347   */
348  // we need remove_reference because is_const seems to not work on const&
349  template <typename Iter>
350  struct iterator_traits_detail<Iter, 
351                         typename boost::enable_if<is_weighted<Iter> >::type >
352  {
353    /**
354       data_reference is double& for mutable iterators and const
355       double otherwise
356    */
357    typedef 
358    typename mutable_reference<iter_has_mutable_data<Iter>::value>::type
359    data_reference;
360
361    /**
362       weight_reference is double& for mutable iterators and const
363       double otherwise
364    */
365    typedef 
366    typename mutable_reference<iter_has_mutable_weight<Iter>::value>::type
367    weight_reference;
368
369    /**
370       return data of \a iter
371    */
372    data_reference data(Iter iter) const { return (*iter).data(); }
373
374    /**
375       return weight of \a iter
376    */
377    weight_reference weight(Iter iter) const { return (*iter).weight(); }
378  };
379
380} // namespace detail
381
382  /**
383     The purpose of this class is to allow polymorphism between
384     weighted and unweighted iterators. It allows to access data and
385     weight for both weighted and unweighted iterators.
386
387     For weighted iterators this class requires that *Iter has
388     functions data(void) and weight(void).
389   */ 
390  template <typename Iter>
391  struct iterator_traits {
392  private:
393    typedef detail::iterator_traits_detail<Iter> traits;
394  public:
395    /**
396       For unweighted iterator, data_reference is the same as
397       std::iterator_traits<Iter>::reference, i.e., the data if the
398       iterator is the same as *Iter.
399
400       For weighted iterators, data_reference is double& if *Iter has
401       a function double& data(void). Otherwise data_reference is
402       const double.
403     */
404    typedef typename traits::data_reference data_reference;
405
406    /**
407       For unweighted iterator, weight_reference is const double since
408       the weight is always implicitly 1.0 and not mutable.
409
410       For weighted iterators, weight_reference is double& if *Iter has
411       a function double& weight(void). Otherwise weight_reference is
412       const double.
413     */
414    typedef typename traits::weight_reference weight_reference;
415
416    /**
417       \return data of iterator \a iter
418    */
419    data_reference data(Iter iter) const 
420    { return traits().data(iter); }
421
422    /**
423       \return weight of iterator \a iter
424     */
425    weight_reference weight(Iter iter) const 
426    { return traits().weight(iter); }
427
428  };
429
430}}} // of namespace utility, yat, and theplu
431
432#endif
Note: See TracBrowser for help on using the repository browser.