boost/mpl/upper_bound.hpp

0001
0002 #ifndef BOOST_MPL_UPPER_BOUND_HPP_INCLUDED
0003 #define BOOST_MPL_UPPER_BOUND_HPP_INCLUDED
0004
0005 // Copyright Aleksey Gurtovoy 2001-2004
0006 //
0007 // Distributed under the Boost Software License, Version 1.0.
0008 // (See accompanying file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // See http://www.boost.org/libs/mpl for documentation.
0012
0013 // $Id$
0014 // $Date$
0015 // $Revision$
0016
0017 #include <boost/mpl/less.hpp>
0018 #include <boost/mpl/lambda.hpp>
0019 #include <boost/mpl/aux_/na_spec.hpp>
0020 #include <boost/mpl/aux_/config/workaround.hpp>
0021
0022 #if BOOST_WORKAROUND(BOOST_BORLANDC, BOOST_TESTED_AT(0x610))
0023 #   define BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL
0024 #endif
0025
0026 #if !defined(BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL)
0027 #   include <boost/mpl/minus.hpp>
0028 #   include <boost/mpl/divides.hpp>
0029 #   include <boost/mpl/size.hpp>
0030 #   include <boost/mpl/advance.hpp>
0031 #   include <boost/mpl/begin_end.hpp>
0032 #   include <boost/mpl/long.hpp>
0033 #   include <boost/mpl/eval_if.hpp>
0034 #   include <boost/mpl/prior.hpp>
0035 #   include <boost/mpl/deref.hpp>
0036 #   include <boost/mpl/apply.hpp>
0037 #   include <boost/mpl/aux_/value_wknd.hpp>
0038 #else
0039 #   include <boost/mpl/find.hpp>
0040 #   include <boost/mpl/bind.hpp>
0041 #endif
0042
0043 #include <boost/config.hpp>
0044
0045 namespace boost { namespace mpl {
0046
0047 #if defined(BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL)
0048
0049 // agurt 23/oct/02: has a wrong complexity etc., but at least it works;
0050 // feel free to contribute a better implementation!
0051 template<
0052       typename BOOST_MPL_AUX_NA_PARAM(Sequence)
0053     , typename BOOST_MPL_AUX_NA_PARAM(T)
0054     , typename Predicate = less<>
0055     , typename pred_ = typename lambda<Predicate>::type
0056     >
0057 struct upper_bound
0058     : find_if< Sequence, bind2<pred_,T,_> >
0059 {
0060 };
0061
0062 #else
0063
0064 namespace aux {
0065
0066 template<
0067       typename Distance
0068     , typename Predicate
0069     , typename T
0070     , typename DeferredIterator
0071     >
0072 struct upper_bound_step_impl;
0073
0074 template<
0075       typename Distance
0076     , typename Predicate
0077     , typename T
0078     , typename DeferredIterator
0079     >
0080 struct upper_bound_step
0081 {
0082     typedef typename eval_if<
0083           Distance
0084         , upper_bound_step_impl<Distance,Predicate,T,DeferredIterator>
0085         , DeferredIterator
0086         >::type type;
0087 };
0088
0089 template<
0090       typename Distance
0091     , typename Predicate
0092     , typename T
0093     , typename DeferredIterator
0094     >
0095 struct upper_bound_step_impl
0096 {
0097     typedef typename divides< Distance, long_<2> >::type offset_;
0098     typedef typename DeferredIterator::type iter_;
0099     typedef typename advance< iter_,offset_ >::type middle_;
0100     typedef typename apply2<
0101               Predicate
0102             , T
0103             , typename deref<middle_>::type
0104             >::type cond_;
0105
0106     typedef typename prior< minus< Distance, offset_ > >::type step_;
0107     typedef upper_bound_step< offset_,Predicate,T,DeferredIterator > step_forward_;
0108     typedef upper_bound_step< step_,Predicate,T,next<middle_> > step_backward_;
0109     typedef typename eval_if<
0110           cond_
0111         , step_forward_
0112         , step_backward_
0113         >::type type;
0114 };
0115
0116 } // namespace aux
0117
0118 template<
0119       typename BOOST_MPL_AUX_NA_PARAM(Sequence)
0120     , typename BOOST_MPL_AUX_NA_PARAM(T)
0121     , typename Predicate = less<>
0122     >
0123 struct upper_bound
0124 {
0125  private:
0126     typedef typename lambda<Predicate>::type pred_;
0127     typedef typename size<Sequence>::type size_;
0128
0129  public:
0130     typedef typename aux::upper_bound_step<
0131         size_,pred_,T,begin<Sequence>
0132         >::type type;
0133 };
0134
0135 #endif // BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL
0136
0137 BOOST_MPL_AUX_NA_SPEC(2, upper_bound)
0138
0139 }}
0140
0141 #endif // BOOST_MPL_UPPER_BOUND_HPP_INCLUDED