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

#ifndef _theplu_yat_utility_iterator_traits_
#define _theplu_yat_utility_iterator_traits_

// $Id: iterator_traits.h 2472 2011-04-12 20:58:28Z peter $

/*
  Copyright (C) 2007 Jari Häkkinen, Peter Johansson
  Copyright (C) 2008 Jari Häkkinen, Peter Johansson, Markus Ringnér
  Copyright (C) 2010, 2011 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 3 of the
  License, or (at your option) any later version.

  The yat library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include "DataWeight.h"

#include <boost/mpl/logical.hpp>
#include <boost/type_traits/is_const.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/remove_reference.hpp>
#include <boost/utility/enable_if.hpp>

#include <iterator>

namespace theplu {
namespace yat {
namespace utility {

  /**
    Struct to be used to make compile-time decision that Iterator is
    unweighted, which is the default.
   */ 
  struct unweighted_iterator_tag {};
    
  /**
    Struct to be used to make compile-time decision that Iterator is
    weighted. Some algorithms come also in a weighted version and
    this tag could be used to decide on using them (rather than
    the corresponding unweighted algorithm).
   */ 
  struct weighted_iterator_tag {};


namespace detail {
  /**
     \internal

     used in weighted_iterator_traits
  */
  template <typename T, typename Enable = void>
  struct weighted_iterator_traits_detail {
    /**
       default is a iterator unweighted
    */
    typedef unweighted_iterator_tag type;
  };  

  /** 
      \internal

      specialization for iterators with value type convertible to DataWeight
  */
  template <typename T>
  struct weighted_iterator_traits_detail<T, typename boost::enable_if<typename boost::is_convertible<T, DataWeight> >::type > {
    /**
       Iterators with value type convertible to DataWeight is weighted
     */
    typedef weighted_iterator_tag type;
  };  

} // namespace detail


  /** 
      Metafunction to decide whether an Iterator is weighted or
      non-weighted. This (default) implementation returns
      unweighted_iterator_tag, unless value_type of Iterator is
      convertible to DataWeight in which case weighted_iterator_tag is
      returned.
  */
  template <class Iterator>
  struct weighted_iterator_traits 
  {
  private:
    typedef typename std::iterator_traits<Iterator>::value_type value;
  public:
    /**
       \return weighted_iterator_tag if Iterator::value_type is
       convertible to DataWeight
     */
    typedef typename detail::weighted_iterator_traits_detail<value>::type type;
  };


namespace detail {
  /**
     \internal

    Metafunction that works on a pair weighted-unweighted types and
    return weighted_type. The metafunction is specialized for
    unweighted unweighted in which case unweighted is returned.
   */
  template <class T1, class T2>
  struct unweighted_type_and {
    /**
       default return weighted_iterator_tag
     */
    typedef weighted_iterator_tag type;
  };

  /**
     \internal

    Specialization that sets type to be unweighted when both arguments
    are unweighted
   */
  template <>
  struct unweighted_type_and<unweighted_iterator_tag, unweighted_iterator_tag> {
    /**
       return unweighted_iterator_tag
     */
    typedef unweighted_iterator_tag type;
  };
} // namespace detail

  /**
    struct used to determine if a pair of iterators should be treated
    as weighted. If both iterators are unweighted, type is set to
    unweighted else weighted.
  */
  template <class T1, class T2>
  struct weighted_if_any2 {
  private:
    typedef typename weighted_iterator_traits<T1>::type w_type1;
    typedef typename weighted_iterator_traits<T2>::type w_type2;
  public:
    /// return unweighted if both are unweighted
    typedef typename detail::unweighted_type_and<w_type1, w_type2>::type type;
  };

  /**
    Same as weighted_iterator_traits2 but for 3 arguments.
   */
  template <class T1, class T2, class T3>
  struct weighted_if_any3 {
  private:
    typedef typename weighted_if_any2<T1, T2>::type tmp;
    typedef typename weighted_iterator_traits<T3>::type w_type3;
  public:
    /// return unweighted if all are unweighted
    typedef typename detail::unweighted_type_and<tmp, w_type3>::type type;
  };

  namespace detail {
    /** 
        \internal

        check (at compile time) that iterator is unweighted. 
    */
    inline void 
    check_iterator_is_unweighted(utility::unweighted_iterator_tag x){} 
  } // namespace detail

  /**
     \brief check (at compile time) that iterator is unweighted.

     This function only compiles if iterator \a iter is unweighted.
   */
  template <class Iter>
  void check_iterator_is_unweighted(Iter iter) 
  { detail::check_iterator_is_unweighted(typename 
                                 weighted_iterator_traits<Iter>::type());
  }


namespace detail {

  /**
     \internal

     The following block of code is used to detect if weighted
     iterators have functions 'double& data(void)' or if they only
     have the const version.
     
     The technique used is taken from http://www.martinecker.com/wiki/
   */
  typedef char yes;
  /**
     \internal

     This type (no) and type yes have different sizes and are used to
     differentiate between the two cases.
   */
  typedef char (&no)[2];
  /**
     \internal

     Overloaded function with template below. If there exists a
     function that returns double& that will used and otherwise
     overloaded template below will be used. This implementation and
     template return different types to differentiate the two cases.
   */
  yes has_mutable(double&);
  /**
     \internal

     Function used in iter_has_mutable_data and
     iter_has_mutable_weight. The default case is used if function
     called (e.g. data() does not return double&.
   */
  template<typename T>
  no has_mutable(const T&);

  /**
     \internal

     Struct to check if iterator has mutable data. *Iter must have a
     function data(). If that function returns double& value is
     true.
   */
  template <class Iter>
  struct iter_has_mutable_data
  {
    /// instance of Iter
    static Iter iter;
    /// true if *iter has a function data() that returns double&
    static const bool value = 
      sizeof(has_mutable((*iter).data())) == sizeof(yes);
  };


  /**
     \internal

     Struct to check if iterator has mutable data. *Iter must have a
     function data(). If that function returns double& value is
     true.
   */
  template <class Iter>
  struct iter_has_mutable_weight
  {
    /// instance of Iter
    static Iter iter;
    /// true if *iter has a function weight() that returns double&
    static const bool value = 
      sizeof(has_mutable((*iter).weight())) == sizeof(yes);
  };


  /**
     \internal

     Convenience meta-function. The struct is-a boost::true_type if
     Iter is a weighted iterator

     The purpose of the struct is to be used in boost::mpl, for
     example, in boost::mpl::and_.

     \see weighted_iterator_traits
   */
  template<typename Iter>
  struct is_weighted 
    : public boost::is_same<weighted_iterator_tag
                            , typename weighted_iterator_traits<Iter>::type> 
  {};

  /**
     \internal

     same is_weighted but negated
   */
  template<typename Iter>
  struct is_unweighted 
    : public boost::is_same<unweighted_iterator_tag
                            , typename weighted_iterator_traits<Iter>::type> 
  {};


  /**
     \internal

     Default implementation of iterator_traits_detail. Is supposed to
     be used for unweighted iterators. Weighted iterators use
     specialization below.
   */
  template <typename Iter, typename Enable = void>
  struct iterator_traits_detail {
    /**
       for unweighted data_reference is reference
    */
    typedef typename std::iterator_traits<Iter>::reference data_reference;

    /**
       for unweighted weight_reference is a double
    */
    typedef const double weight_reference;

    /**
       \return * \a iter 
    */
    data_reference data(Iter iter) const { return *iter; }

    /**
       \return 1.0
    */
    weight_reference weight(Iter iter) const { return 1.0; }
  };

  /**
     \internal
     Metafunction that returns double& if true and const double otherwise
   */
  template<bool>
  struct mutable_reference {
    /// return const double if bool is false
    typedef const double type;
  };

  /**
     \internal
     Specialization that returns double& in true case
  */
  template<>
  struct mutable_reference<true> {
    /// return double& if bool is false
    typedef double& type;
  };


  /**
     \internal

     Specialization for weighted iterators
   */
  // we need remove_reference because is_const seems to not work on const&
  template <typename Iter>
  struct iterator_traits_detail<Iter, 
                         typename boost::enable_if<is_weighted<Iter> >::type >
  {
    /**
       data_reference is double& for mutable iterators and const
       double otherwise
    */
    typedef 
    typename mutable_reference<iter_has_mutable_data<Iter>::value>::type 
    data_reference;

    /**
       weight_reference is double& for mutable iterators and const
       double otherwise
    */
    typedef 
    typename mutable_reference<iter_has_mutable_weight<Iter>::value>::type 
    weight_reference;

    /**
       return data of \a iter
    */
    data_reference data(Iter iter) const { return (*iter).data(); }

    /**
       return weight of \a iter
    */
    weight_reference weight(Iter iter) const { return (*iter).weight(); }
  };

} // namespace detail

  /**
     The purpose of this class is to allow polymorphism between
     weighted and unweighted iterators. It allows to access data and
     weight for both weighted and unweighted iterators.

     For weighted iterators this class requires that *Iter has
     functions data(void) and weight(void).
   */ 
  template <typename Iter>
  struct iterator_traits {
  private:
    typedef detail::iterator_traits_detail<Iter> traits;
  public:
    /**
       For unweighted iterator, data_reference is the same as
       std::iterator_traits<Iter>::reference, i.e., the data if the
       iterator is the same as *Iter.

       For weighted iterators, data_reference is double& if *Iter has
       a function double& data(void). Otherwise data_reference is
       const double.
     */
    typedef typename traits::data_reference data_reference;

    /**
       For unweighted iterator, weight_reference is const double since
       the weight is always implicitly 1.0 and not mutable.

       For weighted iterators, weight_reference is double& if *Iter has
       a function double& weight(void). Otherwise weight_reference is
       const double.
     */
    typedef typename traits::weight_reference weight_reference;

    /**
       \return data of iterator \a iter
    */
    data_reference data(Iter iter) const 
    { return traits().data(iter); }

    /**
       \return weight of iterator \a iter
     */
    weight_reference weight(Iter iter) const 
    { return traits().weight(iter); }

  };

}}} // of namespace utility, yat, and theplu

#endif