source: trunk/yat/utility/iterator_traits.h

Last change on this file was 3550, checked in by Peter, 5 years ago

Update copyright years. Happy New Year

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