stl_utility.h

Go to the documentation of this file.

#ifndef _theplu_yat_utility_stl_utility_
#define _theplu_yat_utility_stl_utility_

// $Id: stl_utility.h 2857 2012-09-27 23:17:17Z 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/>.
*/


#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 {

  // 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 {

  template<typename T>
  struct abs : std::unary_function<T, T>
  {
    inline T operator()(T x) const
    { return std::abs(x); }
  };


  template<typename Pointer>
  struct Dereferencer :
    public std::unary_function<Pointer,
                               typename std::iterator_traits<Pointer>::reference>
  {
    Dereferencer(void)
    { BOOST_CONCEPT_ASSERT((TrivialIterator<Pointer>)); }

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


  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:
    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>));

    }

    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_;
  };

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


  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:
    compose_f_gxy(F f, G g)
      : f_(f), g_(g)
    {
      BOOST_CONCEPT_ASSERT((boost::Convertible<typename G::result_type
                            , typename F::argument_type>));
    }

    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_;
  };

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


  template<class F, class G>
  class compose_f_gx : public std::unary_function<typename G::argument_type,
                                                  typename F::result_type>
  {
  public:
    compose_f_gx(F f, G g)
      : f_(f), g_(g)
    {
      BOOST_CONCEPT_ASSERT((boost::Convertible<typename G::result_type
                            , typename F::argument_type>));
    }

    typename F::result_type
    operator()(typename G::argument_type x) const
    {
      return f_(g_(x));
    }

  private:
    F f_;
    G g_;
  };

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


  template<typename T>
  struct Exp : std::unary_function<T, T>
  {
    inline T operator()(T x) const
    { return std::exp(x); }
  };

  template<typename T>
  struct Identity : public std::unary_function<T, T>
  {
    T operator()(T arg) const { return arg; }
  };


  template <typename Key, typename Tp, typename Compare, typename Alloc>
  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key& k);


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

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


  template<typename InputIterator, typename Key, typename Comp>
  void inverse(InputIterator first, InputIterator last,
               std::map<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[*first] = i;
  }

  template<typename T>
  struct less_nan : std::binary_function<T, T, bool>
  {
    inline bool operator()(T x, T y) const
    {
      if (std::isnan(x))
        return false;
      if (std::isnan(y))
        return true;
      return x<y;
    }
  };


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


  template<typename T>
  class Log : std::unary_function<T, T>
  {
  public:
    Log(void)
      : log_base_(1.0) {}

    explicit Log(double base) : log_base_(std::log(base)) {}

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

  private:
    double log_base_;
  };

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


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


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


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


  template <class T1,class T2>
  struct pair_value_compare
  {
    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)));
    }
  };

  template <class Pair>
  struct PairFirst
  {
    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;

    typedef Pair& argument_type;

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

  };


  template <class Pair>
  struct PairSecond
  {
    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;

    typedef Pair& argument_type;

    inline result_type operator()(argument_type p) const
    { return p.second; }

  };


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


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


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

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


  std::string& to_lower(std::string& s);

  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