#ifndef _theplu_yat_utility_stl_utility_
#define _theplu_yat_utility_stl_utility_

// $Id$

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

#ifdef HAVE_BOOST
	/**
		 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); }
	};
#endif

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


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


	/**
		 Create a map mapping from values in range [first, last) to the
		 distance from first.

		 Post-condition: m[first[i]] == i (for all i that correspond to a
		 unique element). For non-unique element behaviour is undefined.

		 Requirement: InputIterator's value type is assignable to Key

		 \since New in yat 0.10
	 */
	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;
	}

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

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