source: trunk/yat/utility/stl_utility.h @ 2731

#ifndef _theplu_yat_utility_stl_utility_
#define _theplu_yat_utility_stl_utility_

// $Id: stl_utility.h 2731 2012-04-30 05:58:27Z peter $

/*
  Copyright (C) 2004 Jari Häkkinen
  Copyright (C) 2005 Jari Häkkinen, Peter Johansson, Markus Ringnér
  Copyright (C) 2006 Jari Häkkinen
  Copyright (C) 2007, 2008 Jari Häkkinen, Peter Johansson
  Copyright (C) 2009, 2010, 2011, 2012 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/>.
*/

///
/// \file stl_utility.h
///
/// There are a number of useful functionality missing in the Standard
/// Template Library, STL. This file is an effort to provide
/// extensions to STL functionality.
///

#include "concept_check.h"
#include "DataWeight.h"
#include "Exception.h"

#include <boost/concept_check.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/mpl/if.hpp>
#include <boost/type_traits/add_const.hpp>
#include <boost/type_traits/is_const.hpp>
#include <boost/type_traits/remove_reference.hpp>

#include <algorithm>
#include <cmath>
#include <exception>
#include <functional>
#include <iterator>
#include <map>
#include <ostream>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

// We are intruding standard namespace, which might cause
// conflicts. Let the user turn off these declarations by defining
// YAT_STD_DISABE
#ifndef YAT_STD_DISABLE
namespace std {

  ///
  /// Print out a pair
  ///
  // This is in namespace std because we have not figured out how to have
  // pair and its operator<< in different namespaces
  template <class T1, class T2>
  std::ostream& operator<<(std::ostream& out, const std::pair<T1,T2>& p)
  { out << p.first << "\t" << p.second; return out; }

}
#endif

namespace theplu {
namespace yat {
namespace utility {

  /**
     Functor class taking absolute value
  */
  template<typename T>
  struct abs : std::unary_function<T, T>
  {
    /**
       \return absolute value
     */
    inline T operator()(T x) const
    { return std::abs(x); }
  };


  /**
     \brief Adaptor between pointer and pointee interface

     Functor takes a pointer and returns a reference to the instance
     pointer is pointing to. Return type is decided by <a
     href=http://www.sgi.com/tech/stl/iterator_traits.html>
     std::iterator_traits<Pointer>::reference </a>. Pointer must have
     an \c operator*, i.e., \c Pointer can be a traditional pointer or
     an \input_iterator.

     The class is designed to be used with boost::transform_iterator

     \code
     std::vector<MyClass*> vec;
     ...
     Dereferencer<MyClass*> dereferencer;
     std::set<MyClass> s;
     s.insert(boost::make_transform_iterator(vec.begin(), dereferencer),
              boost::make_transform_iterator(vec.end(), dereferencer))
     \endcode

     where elements in vec<MyClass*> are copied in to set<MyClass>.

     \since New in yat 0.7
   */
  template<typename Pointer>
  struct Dereferencer :
    public std::unary_function<Pointer,
                               typename std::iterator_traits<Pointer>::reference>
  {
    /**
       \brief constructor
     */
    Dereferencer(void)
    { BOOST_CONCEPT_ASSERT((TrivialIterator<Pointer>)); }

    /**
       \return * \a ti
     */
    typename std::iterator_traits<Pointer>::reference
    operator()(Pointer ti) const { return *ti; }
  };


  /**
     See The C++ Standard Library - A Tutorial and Reference by
     Nicolai M. Josuttis

     If f is a binary functor, both g and h are unary functors, and
     return type of g (and h) is convertible to F's argument type,
     then compose_f_gx_hy can be used to create a functor equivalent
     to \f$ f(g(x), h(y)) \f$

     - F must be an <a
     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
     AdaptableBinaryFunction</a>
     - G must be an <a
     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
     AdaptableUnaryFunction</a>
     - H must be an <a
     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
     AdaptableUnaryFunction</a>
     - \c G::result_type is convertible to \c F::first_argument_type
     - \c H::result_type is convertible to \c F::second_argument_type

     \see compose_f_gxy and compose_f_gx
   */
  template<class F, class G, class H>
  class compose_f_gx_hy :
    public std::binary_function<typename G::argument_type,
                                typename H::argument_type,
                                typename F::result_type>
  {
  public:
    /**
       \brief Constructor
     */
    compose_f_gx_hy(F f, G g, H h)
      : f_(f), g_(g), h_(h)
    {
      BOOST_CONCEPT_ASSERT((boost::Convertible<typename G::result_type
                            , typename F::first_argument_type>));
      BOOST_CONCEPT_ASSERT((boost::Convertible<typename H::result_type
                            , typename F::second_argument_type>));

    }

    /**
       \brief Does the work
     */
    typename F::result_type
    operator()(typename G::argument_type x,
               typename H::argument_type y) const
    {
      return f_(g_(x), h_(y));
    }

  private:
    F f_;
    G g_;
    H h_;
  };

  /**
     Convenient function to create a compose_f_gx_hy.

     \relates compose_f_gx_hy

     \see std::make_pair
  */
  template<class F, class G, class H>
  compose_f_gx_hy<F, G, H> make_compose_f_gx_hy(F f, G g, H h)
  {
    return compose_f_gx_hy<F,G,H>(f,g,h);
  }


  /**
     See The C++ Standard Library - A Tutorial and Reference by
     Nicolai M. Josuttis

     If f is a unary functor, g is a binary functor, and return type
     of g is convertible to F's argument type, then
     compose_f_gxy can be used to create a functor equivalent to
     \f$ f(g(x,y)) \f$

     - F must be an <a
     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
     AdaptableUnaryFunction</a>
     - G must be an <a
     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
     AdaptableBinaryFunction</a>
     - \c G::result_type is convertible to \c F::argument_type

     \see compose_f_gx_hy and compose_f_gx

     \since New in yat 0.7
   */
  template<class F, class G>
  class compose_f_gxy :
    public std::binary_function<typename G::first_argument_type,
                                typename G::second_argument_type,
                                typename F::result_type>
  {
  public:
    /**
       \brief Constructor
     */
    compose_f_gxy(F f, G g)
      : f_(f), g_(g)
    {
      BOOST_CONCEPT_ASSERT((boost::Convertible<typename G::result_type
                            , typename F::argument_type>));
    }

    /**
       \brief Does the work
     */
    typename F::result_type
    operator()(typename G::first_argument_type x,
               typename G::second_argument_type y) const
    {
      return f_(g_(x,y));
    }

  private:
    F f_;
    G g_;
  };

  /**
     Convenient function to create a compose_f_gxy.

     \relates compose_f_gxy

     \see std::make_pair

     \since New in yat 0.7
  */
  template<class F, class G>
  compose_f_gxy<F, G> make_compose_f_gxy(F f, G g)
  {
    return compose_f_gxy<F,G>(f,g);
  }


  /**
     See The C++ Standard Library - A Tutorial and Reference by
     Nicolai M. Josuttis

     If f is a unary functor, g is a unary functor, and return type of
     g is convertible to F's argument type, then compose_f_gx can be
     used to create a functor equivalent to \f$ f(g(x)) \f$

     - F must be an <a
     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
     AdaptableBinaryFunction</a>
     - G must be an <a
     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
     AdaptableUnaryFunction</a>
     - \c G::result_type is convertible to \c F::argument_type

     \see compose_f_gx_hy and compose_f_gxy

     \since New in yat 0.7
   */
  template<class F, class G>
  class compose_f_gx : public std::unary_function<typename G::argument_type,
                                                  typename F::result_type>
  {
  public:
    /**
       \brief Constructor
     */
    compose_f_gx(F f, G g)
      : f_(f), g_(g)
    {
      BOOST_CONCEPT_ASSERT((boost::Convertible<typename G::result_type
                            , typename F::argument_type>));
    }

    /**
       \brief Does the work
     */
    typename F::result_type
    operator()(typename G::argument_type x) const
    {
      return f_(g_(x));
    }

  private:
    F f_;
    G g_;
  };

  /**
     Convenient function to create a compose_f_gx.

     \relates compose_f_gx

     \see std::make_pair

     \since New in yat 0.7
  */
  template<class F, class G>
  compose_f_gx<F, G> make_compose_f_gx(F f, G g)
  {
    return compose_f_gx<F,G>(f,g);
  }


  /**
     Functor class to exponentiate values using std::exp

     T should be either \c float, \c double, or \c long \c double

     \since New in yat 0.5
  */
  template<typename T>
  struct Exp : std::unary_function<T, T>
  {
    /**
       \return exponentiated value
     */
    inline T operator()(T x) const
    { return std::exp(x); }
  };

  /**
     \brief Identity functor that returns its argument

     \since New in yat 0.7
   */
  template<typename T>
  struct Identity : public std::unary_function<T, T>
  {
    /// \return \a arg
    T operator()(T arg) const { return arg; }
  };


  /**
     Same functionality as map::operator[] but the function does not
     modify the map and the function throws if key does not exist in
     the map.

     \return const reference to m[k]

     \since New in yat 0.7
   */
  template <typename Key, typename Tp, typename Compare, typename Alloc>
  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key& k);


  /**
     Creating a map from a range [first, last) such that m[key]
     returns a vector with indices of which element in [first, last)
     that is equal to \a key, or more technically: m[element].size()
     returns number of elements equal to \a element, and
     m[*element][i] = distance(first, element) for every \a element in
     [first, last) and \a i smaller than m[element].size().

     Requirement: InputIterator's value type is assignable to Key

     \since New in yat 0.5
   */
  template<typename InputIterator, typename Key, typename Comp>
  void inverse(InputIterator first, InputIterator last,
               std::map<Key, std::vector<size_t>, Comp >& m)
  {
    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
    m.clear();
    for (size_t i=0; first!=last; ++i, ++first)
      m[*first].push_back(i);
  }

  /**
     In the created multimap each element e will fulfill: \f$ *(first
     + e->second) == e->first \f$

     Requirement: InputIterator's value type is assignable to Key

     \since New in yat 0.5
   */
  template<typename Key, typename InputIterator, typename Comp>
  void inverse(InputIterator first, InputIterator last,
               std::multimap<Key, size_t, Comp>& m)
  {
    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
    m.clear();
    for (size_t i=0; first!=last; ++i, ++first)
      m.insert(std::make_pair(*first, i));
  }


  /**
     \brief Functor that behaves like std::less with the exception
     that it treates NaN as a number larger than infinity.

     This functor is useful when sorting ranges with NaNs. The problem
     with NaNs is that std::less always returns \c false when one of
     the arguments is NaN. That together with the fact that std::sort
     only guarantees that an element \c i is never less than previous
     element \c --i. Therefore {10, NaN, 2} is sorted according to
     this definition, but most often it is desired that the 2 is
     located before the 10 in the range. Using this functor, less_nan,
     this can easily be achieved as std::sort(first, last, less_nan)

     The default implementation uses std::isnan(T), which consequently
     must be supported.

     There is a specialization less_nan<DataWeight>

     \since New in yat 0.6
  */
  template<typename T>
  struct less_nan : std::binary_function<T, T, bool>
  {
    /**
       \return \c true if x is less than y. NaNs are treated as a number
       larger than infinity, which implies \c true is returned if y is
       NaN and x is not.
     */
    inline bool operator()(T x, T y) const
    {
      if (std::isnan(x))
        return false;
      if (std::isnan(y))
        return true;
      return x<y;
    }
  };


  /**
     \brief Specialization for DataWeight.
   */
  template<>
  struct less_nan<DataWeight>
    : std::binary_function<DataWeight, DataWeight, bool>
  {
    /**
       \return less_nan<double>(x.data(), y.data())
     */
    inline bool operator()(const DataWeight& x, const DataWeight& y) const
    {
      less_nan<double> compare;
      return compare(x.data(), y.data());
    }
  };


  /**
     Functor class to take logarithm

     T should be either \c float, \c double, or \c long \c double

     \since New in yat 0.5
  */
  template<typename T>
  class Log : std::unary_function<T, T>
  {
  public:
    /**
       Default constructor using natural base \f$ e \f$
     */
    Log(void)
      : log_base_(1.0) {}

    /**
       \param base Taking logarithm in which base, e.g. 2 or 10.
    */
    explicit Log(double base) : log_base_(std::log(base)) {}

    /**
       \return logarithm
     */
    inline T operator()(T x) const
    { return std::log(x)/log_base_; }

  private:
    double log_base_;
  };

  /**
     \return max of values
   */
  template <typename T>
  T max(const T& a, const T& b, const T& c)
  {
    return std::max(std::max(a,b),c);
  }


  /**
     \return max of values
   */
  template <typename T>
  T max(const T& a, const T& b, const T& c, const T& d)
  {
    return std::max(std::max(a,b), std::max(c,d));
  }


  /**
     \return max of values
   */
  template <typename T>
  T max(const T& a, const T& b, const T& c, const T& d, const T& e)
  {
    return std::max(max(a,b,c,d), e);
  }


  /**
     \return max of values
   */
  template <typename T>
  T max(const T& a, const T& b, const T& c, const T& d, const T& e, const T& f)
  {
    return std::max(max(a,b,c,d), std::max(e,f));
  }


  ///
  /// @brief Functor comparing pairs using second.
  ///
  /// STL provides operator< for the pair.first element, but none for
  /// pair.second. This template provides this and can be used as the
  /// comparison object in generic functions such as the STL sort.
  ///
  template <class T1,class T2>
  struct pair_value_compare
  {
    ///
    /// @return true if x.second<y.second or (!(y.second<y.second) and
    /// x.first<y.first)
    ///
    inline bool operator()(const std::pair<T1,T2>& x,
                           const std::pair<T1,T2>& y) {
      return ((x.second<y.second) ||
              (!(y.second<x.second) && (x.first<y.first)));
    }
  };

  /**
     \brief Functor that return std::pair.first

     \see pair_first_iterator

     \since New in yat 0.5
   */
  template <class Pair>
  struct PairFirst
  {
    /**
       The type returned is Pair::first_type& with the exception when
       Pair is const and Pair::first_type is non-const, in which case
       const Pair::first_type& is return type.
     */
    typedef typename boost::mpl::if_<
                  typename boost::is_const<Pair>::type,
                  typename boost::add_const<typename Pair::first_type>::type&,
                  typename Pair::first_type&>::type result_type;

    /**
       The argument type is Pair&.
     */
    typedef Pair& argument_type;

    /**
       \return p.first
     */
    inline result_type operator()(argument_type p) const
    { return p.first; }

  };


  /**
     \brief Functor that return std::pair.second

     \see pair_second_iterator

     \since New in yat 0.5
   */
  template <class Pair>
  struct PairSecond
  {
    /**
       The type returned is Pair::second_type& with the exception when
       Pair is const and Pair::second_type is non-const, in which case
       const Pair::first_type& is return type.
     */
    typedef typename boost::mpl::if_<
                  typename boost::is_const<Pair>::type,
                  typename boost::add_const<typename Pair::second_type>::type&,
                  typename Pair::second_type&>::type result_type;

    /**
       The argument type is Pair&.
     */
    typedef Pair& argument_type;

    /**
       \return p.first
     */
    inline result_type operator()(argument_type p) const
    { return p.second; }

  };


  /**
     Creates a transform_iterator that transforms an iterator with
     value type std::pair to an iterator with value type
     std::pair::first_type. This can be used, for example, to
     communicate between a std::map and std::vector

     \code
     std::map<std::string, int> map;
     ...
     std::vector<std::string> vec;
     vec.resize(map.size());
     std::copy(pair_first_iterator(map.begin()), pair_first_iterator(map.end()),
               vec.begin());
     \endcode

     \since New in yat 0.5
   */
  template<class Iter>
  boost::transform_iterator<
    PairFirst<typename boost::remove_reference<
                 typename std::iterator_traits<Iter>::reference
                 >::type>,
    Iter> pair_first_iterator(Iter i)
  {
    // We are going via ::reference in order to remain const info;
    // ::value_type does not contain const information.
    typedef typename std::iterator_traits<Iter>::reference ref_type;
    typedef typename boost::remove_reference<ref_type>::type val_type;
    typedef PairFirst<val_type> PF;
    return boost::transform_iterator<PF, Iter>(i, PF());
  }


  /**
     Creates a transform_iterator that transforms an iterator with
     value type std::pair to an iterator with value type
     std::pair::second_type. This can be used, for example, to
     communicate between a std::map and std::vector

     \code
     std::map<std::string, int> map;
     ...
     std::vector<int> vec(map.size(),0);
     std::copy(vec.begin(), vec.end(), pair_second_iterator(map.begin()));
     \endcode

     \since New in yat 0.5
   */
  template<class Iter>
  boost::transform_iterator<
    PairSecond<typename boost::remove_reference<
                 typename std::iterator_traits<Iter>::reference
                 >::type>,
    Iter> pair_second_iterator(Iter i)
  {
    // We are going via ::reference in order to remain const info;
    // ::value_type does not contain const information.
    typedef typename std::iterator_traits<Iter>::reference ref_type;
    typedef typename boost::remove_reference<ref_type>::type val_type;
    typedef PairSecond<val_type> PS;
    return boost::transform_iterator<PS, Iter>(i, PS());
  }


  /**
     Convenient function that creates a binary predicate that can be
     used to compare pointers when you want to compare them with
     respect to the objects they point to.

     Example:
     \code
     std::vector<MyClass*> vec(18);
     ...
     std::sort(vec.begin(), vec.end(),
               make_ptr_compare(vec[0], std::greater<MyClass>());
     \endcode


     Type Requirement:
     - \a compare must be a <a
     href="http://www.sgi.com/tech/stl/AdaptableBinaryPredicate.html">Adaptable
     Binary Predicate</a>.
     - value_type of Pointer must be convertible to argument_type of
       compare

     \return a compose_f_gx_hy in which \c F is defined by \a compare
     and both \c G and \c H are \c Dereferencer functors.

     \see compose_f_gx_hy

     \since New in yat 0.7
   */
  template<typename Pointer, class Compare>
  compose_f_gx_hy<Compare, Dereferencer<Pointer>, Dereferencer<Pointer> >
  make_ptr_compare(Pointer p, Compare compare)
  {
    return make_compose_f_gx_hy(compare, Dereferencer<Pointer>(),
                                Dereferencer<Pointer>());
  }

  /**
     Same as make_ptr_compare(2) except that std::less is used to
     compare pointers.

     \since New in yat 0.7
   */
  template<typename Pointer>
  compose_f_gx_hy<std::less<typename std::iterator_traits<Pointer>::value_type>,
                  Dereferencer<Pointer>, Dereferencer<Pointer> >
  make_ptr_compare(Pointer p)
  {
    typedef typename std::iterator_traits<Pointer>::value_type value_type;
    BOOST_CONCEPT_ASSERT((boost::LessThanComparable<value_type>));
    std::less<value_type> compare;
    return make_ptr_compare(p, compare);
  }


  ///
  /// @brief Function converting a string to lower case
  ///
  std::string& to_lower(std::string& s);

  ///
  /// @brief Function converting a string to upper case
  ///
  std::string& to_upper(std::string& s);


  // template implementations

  template <typename Key, typename Tp, typename Compare, typename Alloc>
  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key& key)
  {
    typename std::map<Key, Tp, Compare,Alloc>::const_iterator iter(m.find(key));
    if (iter==m.end()) {
      std::stringstream ss;
      ss << "utility::get(const Map&, const Key&): `"
         << key << "' not found in map\n";
      throw runtime_error(ss.str());
    }
    return iter->second;
  }

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