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

#ifndef _theplu_yat_utility_stl_utility_
#define _theplu_yat_utility_stl_utility_ 

// $Id: stl_utility.h 2239 2010-04-10 23:05:12Z 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 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 "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 <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); }
  };


  /**
     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 adaptable binary functor
     G must be an adaptable unary functor
     H must be an adaptable unary functor
   */
  template<class F, class G, class H>
  class compose_f_gx_hy : 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) {}

    /**
       \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.

     \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);
  }  

  /**
     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); }
  };

  /**
     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());
  }


  /**
     Adaptor class that can be used to compare pointers, T*, when you
     want to compare them with respect to the objects they point to.

     Example:
     \code
     std::vector<MyClass*> vec(18);
     ...
     PtrCompare<MyClass, std::greater<MyClass> > ptr_compare;
     std::sort(vec.begin(), vec.end(), ptr_compare);
     \endcode

     The class Compare must be a <a
     href="http://www.sgi.com/tech/stl/BinaryFunction.html">binary
     functor</a> that takes two \c const \c T& and returns \c bool.

     \since New in yat 0.7
   */
  template<typename T, class Compare = std::less<T> >
  class PtrCompare : std::binary_function<T const* const, T const* const, bool>
  {
  public:
    /**
       \brief Constructor.

       Creates an instance of Compare using its default constructor.
     */
    PtrCompare(void)
    {
      BOOST_CONCEPT_ASSERT((boost::BinaryFunction<Compare, bool, const T&, 
                            const T&>));
    }

    /**
       \brief Constructor.

       Creates a copy of \a c that will be used later.
     */
    PtrCompare(Compare c)
      : compare_(c) 
    {
      BOOST_CONCEPT_ASSERT((boost::BinaryFunction<Compare, bool, const T&, 
                            const T&>));
    }

    /**
       \return true iff Compare(* \a lhs, * \a rhs ) is true.
     */
    bool operator()(T const* const lhs, T const* const rhs) const
    { 
      return compare_(*lhs, *rhs); 
    }
  private:
    Compare compare_;

    // using compiler generated copy
    // PtrCompare(const PtrCompare&)
    // PtrCompare& operator=(const PtrCompare&)
  };

  ///
  /// @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 << "yat: 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