Subject: [Boost-commit] svn:boost r50480 - in sandbox/partition_point: boost boost/iterator boost/multi_index boost/partition_point boost/partition_point/detail libs libs/partition_point
From: aschoedl_at_[hidden]
Date: 2009-01-05 05:40:00
Author: schoedl
Date: 2009-01-05 05:39:59 EST (Mon, 05 Jan 2009)
New Revision: 50480
URL: http://svn.boost.org/trac/boost/changeset/50480
Log:
new library partition_point (2)
Added:
sandbox/partition_point/boost/
sandbox/partition_point/boost/iterator/
sandbox/partition_point/boost/iterator/filter_partition_point.hpp (contents, props changed)
sandbox/partition_point/boost/iterator/indirect_partition_point.hpp (contents, props changed)
sandbox/partition_point/boost/iterator/shared_container_partition_point.hpp (contents, props changed)
sandbox/partition_point/boost/iterator/transform_partition_point.hpp (contents, props changed)
sandbox/partition_point/boost/multi_index/
sandbox/partition_point/boost/multi_index/ordered_index_partition_point.hpp (contents, props changed)
sandbox/partition_point/boost/partition_point/
sandbox/partition_point/boost/partition_point/detail/
sandbox/partition_point/boost/partition_point/detail/lazy_typedef.hpp (contents, props changed)
sandbox/partition_point/boost/partition_point/partition_algorithms.hpp (contents, props changed)
sandbox/partition_point/boost/partition_point/partition_point.hpp (contents, props changed)
sandbox/partition_point/boost/partition_point/partition_range_algorithms.hpp (contents, props changed)
sandbox/partition_point/libs/
sandbox/partition_point/libs/partition_point/
Added: sandbox/partition_point/boost/iterator/filter_partition_point.hpp
==============================================================================
--- (empty file)
+++ sandbox/partition_point/boost/iterator/filter_partition_point.hpp 2009-01-05 05:39:59 EST (Mon, 05 Jan 2009)
@@ -0,0 +1,32 @@
+#ifndef BOOST_FILTER_PARTITION_POINT_HPP
+#define BOOST_FILTER_PARTITION_POINT_HPP
+
+#if defined(_MSC_VER)&&(_MSC_VER>=1200)
+#pragma once
+#endif
+
+#include <boost/partition_point/partition_point.hpp>
+#include <boost/iterator/filter_iterator.hpp>
+
+namespace boost {
+
+/* Template functions lower_bound, upper_bound, equal_range and binary_search
+expressed in terms of partition_point, special version for filter_iterator */
+template< class FilterPred, class Iterator, class UnaryPred >
+filter_iterator<FilterPred, Iterator> partition_point( filter_iterator<FilterPred, Iterator> itBegin, filter_iterator<FilterPred, Iterator> itEnd, UnaryPred pred ) {
+ _ASSERT(itBegin.end()==itEnd.end());
+ using boost::partition_point;
+ return boost::make_filter_iterator(
+ itBegin.predicate(),
+ partition_point(
+ itBegin.base(),
+ itEnd.base(),
+ pred
+ ),
+ itBegin.end()
+ );
+}
+
+}; /* namespace */
+
+#endif // BOOST_FILTER_PARTITION_POINT_HPP
Added: sandbox/partition_point/boost/iterator/indirect_partition_point.hpp
==============================================================================
--- (empty file)
+++ sandbox/partition_point/boost/iterator/indirect_partition_point.hpp 2009-01-05 05:39:59 EST (Mon, 05 Jan 2009)
@@ -0,0 +1,52 @@
+#ifndef BOOST_INDIRECT_PARTITION_POINT_HPP
+#define BOOST_INDIRECT_PARTITION_POINT_HPP
+
+#if defined(_MSC_VER)&&(_MSC_VER>=1200)
+#pragma once
+#endif
+
+#include <boost/partition_point/partition_point.hpp>
+#include <boost/iterator/indirect_iterator.hpp>
+#include <boost/iterator/iterator_traits.hpp>
+#include <boost/bind.hpp> // for bind
+
+namespace boost {
+
+// As a functor for dereferencing, operator* is not defined for pointers,
+// so a pointer-to-member cannot be used. There is also no functor defined
+// in std for the dereference operator, so we define our own.
+// It takes the functor by value just like boost::bind.
+namespace detail {
+ template< class UnaryPred >
+ struct chain_dereference {
+ private:
+ UnaryPred m_pred;
+
+ public:
+ chain_dereference( UnaryPred pred )
+ : m_pred( pred ) {};
+
+ template< class T >
+ bool operator()( T const& t ) const {
+ return m_pred( *t );
+ }
+ };
+}
+
+/* Template functions lower_bound, upper_bound, equal_range and binary_search
+expressed in terms of partition_point, special version for indirect_iterator */
+template< class Iterator, class UnaryPred >
+indirect_iterator<Iterator> partition_point( indirect_iterator<Iterator> itBegin, indirect_iterator<Iterator> itEnd, UnaryPred pred ) {
+ using boost::partition_point;
+ return boost::make_indirect_iterator(
+ partition_point(
+ itBegin.base(),
+ itEnd.base(),
+ detail::chain_dereference<UnaryPred>( pred )
+ )
+ );
+}
+
+}; /* namespace */
+
+#endif // BOOST_INDIRECT_PARTITION_POINT_HPP
\ No newline at end of file
Added: sandbox/partition_point/boost/iterator/shared_container_partition_point.hpp
==============================================================================
--- (empty file)
+++ sandbox/partition_point/boost/iterator/shared_container_partition_point.hpp 2009-01-05 05:39:59 EST (Mon, 05 Jan 2009)
@@ -0,0 +1,30 @@
+#ifndef BOOST_SHARED_CONTAINER_PARTITION_POINT_HPP
+#define BOOST_SHARED_CONTAINER_PARTITION_POINT_HPP
+
+#if defined(_MSC_VER)&&(_MSC_VER>=1200)
+#pragma once
+#endif
+
+#include <boost/partition_point/partition_point.hpp>
+#include <boost/iterator/shared_container_iterator.hpp>
+
+namespace boost {
+
+/* Template functions lower_bound, upper_bound, equal_range and binary_search
+expressed in terms of partition_point, special version for shared_container_iterator */
+template< class UnaryFunc, class Iterator, class UnaryPred >
+shared_container_iterator<UnaryFunc, Iterator> partition_point( shared_container_iterator<UnaryFunc, Iterator> itBegin, shared_container_iterator<UnaryFunc, Iterator> itEnd, UnaryPred pred ) {
+ using boost::partition_point;
+ return boost::make_shared_container_iterator(
+ partition_point(
+ itBegin.base(),
+ itEnd.base(),
+ pred
+ ),
+ itBegin.container_ref
+ );
+}
+
+}; /* namespace */
+
+#endif // BOOST_SHARED_CONTAINER_PARTITION_POINT_HPP
\ No newline at end of file
Added: sandbox/partition_point/boost/iterator/transform_partition_point.hpp
==============================================================================
--- (empty file)
+++ sandbox/partition_point/boost/iterator/transform_partition_point.hpp 2009-01-05 05:39:59 EST (Mon, 05 Jan 2009)
@@ -0,0 +1,31 @@
+#ifndef BOOST_TRANSFORM_PARTITION_POINT_HPP
+#define BOOST_TRANSFORM_PARTITION_POINT_HPP
+
+#if defined(_MSC_VER)&&(_MSC_VER>=1200)
+#pragma once
+#endif
+
+#include <boost/partition_point/partition_point.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/bind.hpp> // for bind
+
+namespace boost {
+
+/* Template functions lower_bound, upper_bound, equal_range and binary_search
+expressed in terms of partition_point, special version for transform_iterator */
+template< class UnaryFunc, class Iterator, class UnaryPred >
+transform_iterator<UnaryFunc, Iterator> partition_point( transform_iterator<UnaryFunc, Iterator> itBegin, transform_iterator<UnaryFunc, Iterator> itEnd, UnaryPred pred ) {
+ using boost::partition_point;
+ return boost::make_transform_iterator(
+ partition_point(
+ itBegin.base(),
+ itEnd.base(),
+ boost::bind( pred, boost::bind( itBegin.functor(), _1 ) )
+ ),
+ itBegin.functor()
+ );
+}
+
+}; /* namespace */
+
+#endif // BOOST_TRANSFORM_PARTITION_POINT_HPP
\ No newline at end of file
Added: sandbox/partition_point/boost/multi_index/ordered_index_partition_point.hpp
==============================================================================
--- (empty file)
+++ sandbox/partition_point/boost/multi_index/ordered_index_partition_point.hpp 2009-01-05 05:39:59 EST (Mon, 05 Jan 2009)
@@ -0,0 +1,92 @@
+#ifndef BOOST_MULTI_INDEX_ORDERED_INDEX_PARTITION_POINT_HPP
+#define BOOST_MULTI_INDEX_ORDERED_INDEX_PARTITION_POINT_HPP
+
+#if defined(_MSC_VER)&&(_MSC_VER>=1200)
+#pragma once
+#endif
+
+#include <boost/multi_index/ordered_index.hpp>
+
+namespace boost {
+
+/* Template functions lower_bound, upper_bound, equal_range and binary_search
+expressed in terms of partition_point, special version for iterators ranging in
+multi_index_container's index
+
+NodeBase is a base type of the multi_index_container's node (internal data
+structure used to store elements). */
+
+#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
+template< typename NodeBase, typename OrderedIndex, typename UnaryPred >
+boost::multi_index::safe_mode::safe_iterator<
+ boost::multi_index::detail::bidir_node_iterator<boost::multi_index::detail::ordered_index_node<NodeBase> >,
+ OrderedIndex
+>
+partition_point(
+ boost::multi_index::safe_mode::safe_iterator<
+ boost::multi_index::detail::bidir_node_iterator<boost::multi_index::detail::ordered_index_node<NodeBase> >,
+ OrderedIndex
+ > first,
+ boost::multi_index::safe_mode::safe_iterator<
+ boost::multi_index::detail::bidir_node_iterator<boost::multi_index::detail::ordered_index_node<NodeBase> >,
+ OrderedIndex
+ > last,
+ UnaryPred pred
+)
+#else
+template< typename NodeBase, typename UnaryPred >
+boost::multi_index::detail::bidir_node_iterator<boost::multi_index::detail::ordered_index_node<NodeBase> >
+partition_point(
+ boost::multi_index::detail::bidir_node_iterator<boost::multi_index::detail::ordered_index_node<NodeBase> > first,
+ boost::multi_index::detail::bidir_node_iterator<boost::multi_index::detail::ordered_index_node<NodeBase> > last,
+ UnaryPred pred
+)
+#endif
+{
+ typedef boost::multi_index::detail::ordered_index_node<NodeBase> node_type;
+
+ if(first==last) return last;
+
+ /* find special nodes of the underlying internal tree: root and header;
+ header points to the end of the index and is used here instead of end() */
+ node_type* root=first.get_node();
+ node_type* header=
+ node_type::from_impl(root->parent());
+ node_type* next=
+ node_type::from_impl(header->parent());
+ while(root!=next) {
+ root=header;
+ header=next;
+ next=node_type::from_impl(next->parent());
+ }
+
+ /* find the node of the partition point, using binary search */
+ node_type *top = root;
+ node_type *i = header;
+ while(top) {
+ if(pred(top->value())){
+ top=node_type::from_impl(top->right());
+ } else {
+ i=top;
+ top=node_type::from_impl(top->left());
+ }
+ }
+
+ /* find its projection on the interval */
+ if(i==header)
+ return last;
+ if((last.get_node()!=header) && (pred(*last) && !pred(i->value())))
+ return last;
+ if(!pred(*first) || pred(i->value()))
+ return first;
+#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
+ return boost::multi_index::safe_mode::safe_iterator<boost::multi_index::detail::bidir_node_iterator<boost::multi_index::detail::ordered_index_node<NodeBase> >, OrderedIndex>(i, const_cast<OrderedIndex*>(first.owner()));
+#else
+ return boost::multi_index::detail::bidir_node_iterator<boost::multi_index::detail::ordered_index_node<NodeBase> >(i);
+#endif
+}
+
+}; /* namespace */
+
+
+#endif // BOOST_MULTI_INDEX_ORDERED_INDEX_PARTITION_POINT_HPP
Added: sandbox/partition_point/boost/partition_point/detail/lazy_typedef.hpp
==============================================================================
--- (empty file)
+++ sandbox/partition_point/boost/partition_point/detail/lazy_typedef.hpp 2009-01-05 05:39:59 EST (Mon, 05 Jan 2009)
@@ -0,0 +1,33 @@
+#ifndef BOOST_PARTITION_POINT_LAZY_TYPEDEF_HPP
+#define BOOST_PARTITION_POINT_LAZY_TYPEDEF_HPP
+
+#if defined(_MSC_VER) && (_MSC_VER >= 1200)
+# pragma once
+#endif
+
+#include <boost/config.hpp>
+
+#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#error lazy_typedef.hpp requires partial template specialization!
+#endif
+
+namespace boost {
+ namespace detail {
+ template< typename T > struct exists { typedef void type; };
+ }
+}
+
+// Defines extract_some_typedef<T> which exposes T::some_typedef as extract_some_typedef<T>::type
+// if T::some_typedef exists. Otherwise extract_some_typedef<T> is empty.
+#define BOOST_DECLARE_LAZY_TYPEDEF( some_typedef ) \
+ template< typename C, typename Enable=void > \
+ struct lazy_typedef_ ## some_typedef \
+ {}; \
+ template< typename C > \
+ struct lazy_typedef_ ## some_typedef< C \
+ , BOOST_DEDUCED_TYPENAME boost::detail::exists< BOOST_DEDUCED_TYPENAME C::some_typedef >::type \
+ > { \
+ typedef BOOST_DEDUCED_TYPENAME C::some_typedef type; \
+ };
+
+#endif // BOOST_PARTITION_POINT_LAZY_TYPEDEF_HPP
\ No newline at end of file
Added: sandbox/partition_point/boost/partition_point/partition_algorithms.hpp
==============================================================================
--- (empty file)
+++ sandbox/partition_point/boost/partition_point/partition_algorithms.hpp 2009-01-05 05:39:59 EST (Mon, 05 Jan 2009)
@@ -0,0 +1,100 @@
+// (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 BOOST_PARTITION_ALGORITHMS_HPP
+#define BOOST_PARTITION_ALGORITHMS_HPP
+
+#ifdef _MSC_VER
+#if(_MSC_VER>=1200)
+#pragma once
+#endif
+#pragma warning( push )
+#pragma warning( disable: 4244 )
+#endif
+
+#include "partition_point.hpp"
+#include <boost/ref.hpp> // for boost::cref
+#include <boost/bind.hpp> // for bind
+#include <functional> // for std::less
+#include <utility> // for std::pair
+
+namespace boost {
+
+ namespace detail {
+ struct generic_less {
+ template< class T1, class T2 >
+ bool operator()( T1 const& t1, T2 const& t2 ) const {
+ return t1 < t2;
+ }
+ };
+ }
+
+ namespace partition_algorithms_adl_barrier {
+
+ // std::bind1st/2nd require argument_type to be defined, at least in Dinkumware's implementation.
+ // The standard does not require this for the predicate passed to lower_bound et. al.
+ // We thus use boost::bind, which with explicit return type does not require any typedefs.
+
+ template< typename It, typename Val, typename BinPred >
+ It lower_bound(It itBegin,It itEnd,Val const& x,BinPred pred) {
+ using boost::partition_point;
+ return partition_point(itBegin,itEnd,boost::bind<bool>(pred,_1,boost::cref(x)));
+ }
+
+ template< typename It, typename Val, typename BinPred >
+ It upper_bound(It itBegin,It itEnd,Val const& x,BinPred pred) {
+ using boost::partition_point;
+ return partition_point(itBegin,itEnd,!boost::bind<bool>(pred,boost::cref(x),_1));
+ }
+
+ template< typename It, typename Val, typename BinPred >
+ bool binary_search(It itBegin,It itEnd,Val const& x,BinPred pred) {
+ It it = boost::lower_bound(itBegin,itEnd,x,pred);
+ return it!=itEnd && !pred(x,*it);
+ }
+
+ template< typename It, typename Val, typename BinPred >
+ std::pair<It,It> equal_range(It itBegin,It itEnd,Val const& x,BinPred pred) {
+ // Construct std::pair<It,It> initialized so that transform_iterator functor
+ // does not have to be default-constructible. This is non-standard conformant,
+ // but may be practical.
+ itBegin=boost::lower_bound(itBegin,itEnd,x,pred);
+ return std::pair<It,It>( itBegin, boost::upper_bound(itBegin,itEnd,x,pred) );
+ }
+
+ // According to http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270
+ // the less-than comparison may be carried out on unequal types. Thus
+ // we use our own implementation instead of std::less.
+
+ template< typename It, typename Val >
+ It lower_bound(It itBegin,It itEnd,Val const& x) {
+ return boost::lower_bound( itBegin, itEnd, x, ::boost::detail::generic_less() );
+ }
+
+ template< typename It, typename Val >
+ It upper_bound(It itBegin,It itEnd,Val const& x) {
+ return boost::upper_bound( itBegin, itEnd, x, ::boost::detail::generic_less() );
+ }
+
+ template< typename It, typename Val >
+ bool binary_search(It itBegin,It itEnd,Val const& x) {
+ return boost::binary_search( itBegin, itEnd, x, ::boost::detail::generic_less() );
+ }
+
+ template< typename It, typename Val >
+ std::pair<It,It> equal_range(It itBegin,It itEnd,Val const& x) {
+ return boost::equal_range( itBegin, itEnd, x, ::boost::detail::generic_less() );
+ }
+ }
+
+ using namespace partition_algorithms_adl_barrier;
+
+} // namespace boost
+
+#ifdef _MSC_VER
+#pragma warning( pop )
+#endif
+
+#endif // BOOST_PARTITION_ALGORITHMS_HPP
Added: sandbox/partition_point/boost/partition_point/partition_point.hpp
==============================================================================
--- (empty file)
+++ sandbox/partition_point/boost/partition_point/partition_point.hpp 2009-01-05 05:39:59 EST (Mon, 05 Jan 2009)
@@ -0,0 +1,38 @@
+#ifndef BOOST_PARTITION_POINT_HPP
+#define BOOST_PARTITION_POINT_HPP
+
+#if defined(_MSC_VER)&&(_MSC_VER>=1200)
+#pragma once
+#endif
+
+#include <boost/iterator/iterator_traits.hpp>
+
+namespace boost {
+
+template<class It, class UnaryPred>
+It partition_point( It itBegin, It itEnd, UnaryPred pred ) {
+#ifdef _DEBUG /* is pred a partitioning? True must not occur after false */
+ It itPartitionPoint = std::find_if(itBegin, itEnd, !boost::bind<bool>(pred, _1));
+ _ASSERT( std::find_if(itPartitionPoint, itEnd, pred) == itEnd );
+#endif
+ boost::iterator_difference<It>::type nCount = std::distance(itBegin, itEnd);
+ while( 0 < nCount ) {
+ boost::iterator_difference<It>::type nCount2 = nCount / 2;
+ It itMid = itBegin;
+ std::advance(itMid, nCount2);
+ if( pred(*itMid) ) {
+ itBegin = ++itMid;
+ nCount -= nCount2 + 1;
+ } else {
+ nCount = nCount2;
+ }
+ }
+#ifdef _DEBUG /* we have already found the partition point; compare result */
+ _ASSERT( itBegin == itPartitionPoint );
+#endif
+ return itBegin;
+}
+
+}; /* namespace boost */
+
+#endif /* BOOST_PARTITION_POINT_HPP */
Added: sandbox/partition_point/boost/partition_point/partition_range_algorithms.hpp
==============================================================================
--- (empty file)
+++ sandbox/partition_point/boost/partition_point/partition_range_algorithms.hpp 2009-01-05 05:39:59 EST (Mon, 05 Jan 2009)
@@ -0,0 +1,167 @@
+#ifndef BOOST_PARTITION_RANGE_ALGORITHMS_HPP
+#define BOOST_PARTITION_RANGE_ALGORITHMS_HPP
+
+#ifdef _MSC_VER
+#if(_MSC_VER>=1200)
+#pragma once
+#endif
+#endif
+
+#include <boost/partition_point/partition_algorithms.hpp>
+#include <boost/config.hpp>
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+#pragma warning( push )
+#pragma warning( disable: 4018 )
+#include <boost/range/sub_range.hpp>
+#pragma warning( pop )
+#include <boost/partition_point/detail/lazy_typedef.hpp>
+
+namespace boost {
+ namespace improved {
+ ///////////////////////////////////////////////////////////////////////////////////////////////////////////
+ // Versions of range_const/mutable_iterator<C> that if C::(const_)iterator is undefined,
+ // do not define range_const/mutable_iterator<C>::type, instead of defining it but
+ // failing to compile when type is actually accessed. This helps disambiguating overloads.
+
+ //////////////////////////////////////////////////////////////////////////
+ // default
+ //////////////////////////////////////////////////////////////////////////
+
+ namespace detail {
+ BOOST_DECLARE_LAZY_TYPEDEF( const_iterator )
+ }
+
+ template< typename C >
+ struct range_const_iterator: detail::lazy_typedef_const_iterator<C>
+ {};
+
+ //////////////////////////////////////////////////////////////////////////
+ // pair
+ //////////////////////////////////////////////////////////////////////////
+
+ template< typename Iterator >
+ struct range_const_iterator< std::pair<Iterator,Iterator> >
+ {
+ typedef Iterator type;
+ };
+
+ //////////////////////////////////////////////////////////////////////////
+ // array
+ //////////////////////////////////////////////////////////////////////////
+
+ template< typename T, std::size_t sz >
+ struct range_const_iterator< T[sz] >
+ {
+ typedef const T* type;
+ };
+
+ //////////////////////////////////////////////////////////////////////////
+ // default
+ //////////////////////////////////////////////////////////////////////////
+
+ namespace detail {
+ BOOST_DECLARE_LAZY_TYPEDEF( iterator )
+ }
+
+ template< typename C >
+ struct range_mutable_iterator: detail::lazy_typedef_iterator<C>
+ {};
+
+ //////////////////////////////////////////////////////////////////////////
+ // pair
+ //////////////////////////////////////////////////////////////////////////
+
+ template< typename Iterator >
+ struct range_mutable_iterator< std::pair<Iterator,Iterator> >
+ {
+ typedef Iterator type;
+ };
+
+ //////////////////////////////////////////////////////////////////////////
+ // array
+ //////////////////////////////////////////////////////////////////////////
+
+ template< typename T, std::size_t sz >
+ struct range_mutable_iterator< T[sz] >
+ {
+ typedef T* type;
+ };
+ } // namespace improved
+
+ namespace partition_algorithms_adl_barrier {
+
+ template< typename Rng, typename Val >
+ BOOST_DEDUCED_TYPENAME boost::improved::range_const_iterator<Rng>::type lower_bound(Rng const& rng,Val const& x) {
+ return boost::lower_bound(boost::begin(rng),boost::end(rng),x);
+ }
+
+ template< typename Rng, typename Val >
+ BOOST_DEDUCED_TYPENAME boost::improved::range_mutable_iterator<Rng>::type lower_bound(Rng & rng,Val const& x) {
+ return boost::lower_bound(boost::begin(rng),boost::end(rng),x);
+ }
+
+ template< typename Rng, typename Val, typename BinPred>
+ BOOST_DEDUCED_TYPENAME boost::improved::range_const_iterator<Rng>::type lower_bound(Rng const& rng,Val const& x,BinPred pred) {
+ return boost::lower_bound(boost::begin(rng),boost::end(rng),x,pred);
+ }
+
+ template< typename Rng, typename Val, typename BinPred>
+ BOOST_DEDUCED_TYPENAME boost::improved::range_mutable_iterator<Rng>::type lower_bound(Rng & rng,Val const& x,BinPred pred) {
+ return boost::lower_bound(boost::begin(rng),boost::end(rng),x,pred);
+ }
+
+ template< typename Rng, typename Val >
+ BOOST_DEDUCED_TYPENAME boost::improved::range_const_iterator<Rng>::type upper_bound(Rng const& rng,Val const& x) {
+ return boost::upper_bound(boost::begin(rng),boost::end(rng),x);
+ }
+
+ template< typename Rng, typename Val >
+ BOOST_DEDUCED_TYPENAME boost::improved::range_mutable_iterator<Rng>::type upper_bound(Rng & rng,Val const& x) {
+ return boost::upper_bound(boost::begin(rng),boost::end(rng),x);
+ }
+
+ template< typename Rng, typename Val, typename BinPred>
+ BOOST_DEDUCED_TYPENAME boost::improved::range_const_iterator<Rng>::type upper_bound(Rng const& rng,Val const& x,BinPred pred) {
+ return boost::upper_bound(boost::begin(rng),boost::end(rng),x,pred);
+ }
+
+ template< typename Rng, typename Val, typename BinPred>
+ BOOST_DEDUCED_TYPENAME boost::improved::range_mutable_iterator<Rng>::type upper_bound(Rng & rng,Val const& x,BinPred pred) {
+ return boost::upper_bound(boost::begin(rng),boost::end(rng),x,pred);
+ }
+
+ template< typename Rng, typename Val >
+ bool binary_search(Rng const& rng,Val const& x) {
+ return boost::binary_search(boost::begin(rng),boost::end(rng),x);
+ }
+
+ template< typename Rng, typename Val, typename BinPred>
+ bool binary_search(Rng const& rng,Val const& x,BinPred pred) {
+ return boost::binary_search(boost::begin(rng),boost::end(rng),x,pred);
+ }
+
+ template< typename Rng, typename Val >
+ boost::sub_range<Rng const> equal_range(Rng const& rng,Val const& x) {
+ return boost::equal_range(boost::begin(rng),boost::end(rng),x);
+ }
+
+ template< typename Rng, typename Val >
+ boost::sub_range<Rng> equal_range(Rng & rng,Val const& x) {
+ return boost::equal_range(boost::begin(rng),boost::end(rng),x);
+ }
+
+ template< typename Rng, typename Val, typename BinPred>
+ boost::sub_range<Rng const> equal_range(Rng const& rng,Val const& x,BinPred pred) {
+ return boost::equal_range(boost::begin(rng),boost::end(rng),x,pred);
+ }
+
+ template< typename Rng, typename Val, typename BinPred>
+ boost::sub_range<Rng> equal_range(Rng & rng,Val const& x,BinPred pred) {
+ return boost::equal_range(boost::begin(rng),boost::end(rng),x,pred);
+ }
+ } // namespace partition_algorithms_adl_barrier
+
+} // namespace boost
+
+#endif // BOOST_PARTITION_RANGE_ALGORITHMS_HPP
\ No newline at end of file