// (C) Arno Schoedl 2008.
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)#ifndef PARTITION_ALGORITHMS_FACADE_HPP
#ifndef BOOST_PARTITION_ALGORITHMS_FACADE_HPP
#define BOOST_PARTITION_ALGORITHMS_FACADE_HPP

#if defined(_MSC_VER)&&(_MSC_VER>=1200)
#pragma once
#endif

#include <boost/ref.hpp> // for boost::cref
#include <boost/preprocessor/punctuation/comma.hpp> // for BOOST_PP_COMMA
#include <boost/bind.hpp> // for bind
#include <functional> // for std::less
#include <utility> // for std::pair

namespace boost {

// empty_base copied from boost/operators.hpp
namespace detail_partition_algorithms_facade {

template <typename T> class empty_base {
// Helmut Zeisel, empty base class optimization bug with GCC 3.0.0
#if defined(__GNUC__) && __GNUC__==3 && __GNUC_MINOR__==0 && __GNU_PATCHLEVEL__==0
	bool dummy; 
#endif
};

} // namespace detail_partition_algorithms_facade

template< class Derived, class Base = detail_partition_algorithms_facade::empty_base<T> >
class partition_point_facade : public Base {
protected:
	// Make custom implementations private and put 
	// friend class partition_point_facade_;
	// into Derived class to avoid polluting your public interface.
	// This is less code than an extra partition_point_access class.
	// If there are reasons to do it with an extra class, let me know
	// and I will change it.
	typedef partition_point_facade< Derived, Base > partition_point_facade_;

private:
	Derived const& derived() const {
		return static_cast<Derived const&>(*this);
	}

	// Here, functor can be passed by reference because this function
	// is only called from the friend ADL overloads below.
	template<class Derived, class UnaryPred>
	static Derived partition_point__(Derived const& itBegin,Derived const& itEnd,UnaryPred& pred) {
		return itBegin.partition_point_( itEnd, pred );
	}

	// Free friend functions have no direct friend access to Derived and 
	// thus must go through the partition_point__ forwarder defined above.

	// We forward non-BinPred function versions to other non-BinPred functions
	// instead of forwarding to their own BinPred version with BinPred bound to std::less
	// to avoid to incur the overhead of bind twice.
	template<class UnaryPred>
	friend Derived partition_point(Derived itBegin,Derived itEnd,UnaryPred pred) {
		return partition_point_facade_::partition_point__(itBegin,itEnd,pred);
	}
	template<class Val>
	friend Derived lower_bound(Derived itBegin,Derived itEnd,const Val &x) {
		return partition_point_facade_::partition_point__(itBegin,itEnd,!bind(std::less<Val>(),_1,boost::cref(x)));
	}
	template<class Val, class BinPred>
	friend Derived lower_bound(Derived itBegin,Derived itEnd,const Val &x,BinPred pred) {
		return partition_point_facade_::partition_point__(itBegin,itEnd,!bind(pred,_1,boost::cref(x)));
	}
	template<class Val>
	friend Derived upper_bound(Derived itBegin,Derived itEnd,const Val &x) {
		return partition_point_facade_::partition_point__(itBegin,itEnd,bind(std::less<Val>(),boost::cref(x),_1));
	}
	template<class Val, class BinPred>
	friend Derived upper_bound(Derived itBegin,Derived itEnd,const Val &x,BinPred pred) {
		return partition_point_facade_::partition_point__(itBegin,itEnd,bind(pred,boost::cref(x),_1));
	}
	template<class Val>
	friend bool binary_search(Derived itBegin,Derived itEnd,const Val &x) {
		Derived it = lower_bound(itBegin,itEnd,x);
		return it!=itEnd && !(x<*it);
	}
	template<class Val, class BinPred>
	friend bool binary_search(Derived itBegin,Derived itEnd,const Val &x,BinPred pred) {
		Derived it = lower_bound(itBegin,itEnd,x,pred);
		return it!=itEnd && !pred(x,*it);
	}
	template<class Val>
	friend std::pair<Derived,Derived> equal_range(Derived itBegin,Derived itEnd,const Val &x) {
		// Construct std::pair<Derived,Derived> initialized so that transform_iterator functor
		// does not have to be default-constructible. This is non-standard conformant,
		// but may be practical.
		itBegin=lower_bound(itBegin,itEnd,x);
		return std::pair<Derived,Derived>( itBegin, upper_bound(itBegin,itEnd,x) );
	}
	template<class Val, class BinPred>
	friend std::pair<Derived,Derived> equal_range(Derived itBegin,Derived itEnd,const Val &x,BinPred pred) {
		// Construct std::pair<Derived,Derived> initialized so that transform_iterator functor
		// does not have to be default-constructible. This is non-standard conformant,
		// but may be practical.
		itBegin=lower_bound(itBegin,itEnd,x,pred);
		return std::pair<Derived,Derived>( itBegin, upper_bound(itBegin,itEnd,x,pred) );
	}
};

} // namespace boost

#endif // BOOST_PARTITION_ALGORITHMS_FACADE_HPP