src/boost/boost/mpl/upper_bound.hpp

   1
   2 #ifndef BOOST_MPL_UPPER_BOUND_HPP_INCLUDED
   3 #define BOOST_MPL_UPPER_BOUND_HPP_INCLUDED
   4
   5 // Copyright Aleksey Gurtovoy 2001-2004
   6 //
   7 // Distributed under the Boost Software License, Version 1.0.
   8 // (See accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10 //
  11 // See http://www.boost.org/libs/mpl for documentation.
  12
  13 // $Id: upper_bound.hpp 49267 2008-10-11 06:19:02Z agurtovoy $
  14 // $Date: 2008-10-11 02:19:02 -0400 (Sat, 11 Oct 2008) $
  15 // $Revision: 49267 $
  16
  17 #include <boost/mpl/less.hpp>
  18 #include <boost/mpl/lambda.hpp>
  19 #include <boost/mpl/aux_/na_spec.hpp>
  20 #include <boost/mpl/aux_/config/workaround.hpp>
  21
  22 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x610))
  23 #   define BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL
  24 #endif
  25
  26 #if !defined(BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL)
  27 #   include <boost/mpl/minus.hpp>
  28 #   include <boost/mpl/divides.hpp>
  29 #   include <boost/mpl/size.hpp>
  30 #   include <boost/mpl/advance.hpp>
  31 #   include <boost/mpl/begin_end.hpp>
  32 #   include <boost/mpl/long.hpp>
  33 #   include <boost/mpl/eval_if.hpp>
  34 #   include <boost/mpl/prior.hpp>
  35 #   include <boost/mpl/deref.hpp>
  36 #   include <boost/mpl/apply.hpp>
  37 #   include <boost/mpl/aux_/value_wknd.hpp>
  38 #else
  39 #   include <boost/mpl/find.hpp>
  40 #   include <boost/mpl/bind.hpp>
  41 #endif
  42
  43 #include <boost/config.hpp>
  44
  45 namespace boost { namespace mpl {
  46
  47 #if defined(BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL)
  48
  49 // agurt 23/oct/02: has a wrong complexity etc., but at least it works;
  50 // feel free to contribute a better implementation!
  51 template<
  52       typename BOOST_MPL_AUX_NA_PARAM(Sequence)
  53     , typename BOOST_MPL_AUX_NA_PARAM(T)
  54     , typename Predicate = less<>
  55     , typename pred_ = typename lambda<Predicate>::type
  56     >
  57 struct upper_bound
  58     : find_if< Sequence, bind2<pred_,T,_> >
  59 {
  60 };
  61
  62 #else
  63
  64 namespace aux {
  65
  66 template<
  67       typename Distance
  68     , typename Predicate
  69     , typename T
  70     , typename DeferredIterator
  71     >
  72 struct upper_bound_step_impl;
  73
  74 template<
  75       typename Distance
  76     , typename Predicate
  77     , typename T
  78     , typename DeferredIterator
  79     >
  80 struct upper_bound_step
  81 {
  82     typedef typename eval_if<
  83           Distance
  84         , upper_bound_step_impl<Distance,Predicate,T,DeferredIterator>
  85         , DeferredIterator
  86         >::type type;
  87 };
  88
  89 template<
  90       typename Distance
  91     , typename Predicate
  92     , typename T
  93     , typename DeferredIterator
  94     >
  95 struct upper_bound_step_impl
  96 {
  97     typedef typename divides< Distance, long_<2> >::type offset_;
  98     typedef typename DeferredIterator::type iter_;
  99     typedef typename advance< iter_,offset_ >::type middle_;
 100     typedef typename apply2<
 101               Predicate
 102             , T
 103             , typename deref<middle_>::type
 104             >::type cond_;
 105
 106     typedef typename prior< minus< Distance, offset_ > >::type step_;
 107     typedef upper_bound_step< offset_,Predicate,T,DeferredIterator > step_forward_;
 108     typedef upper_bound_step< step_,Predicate,T,next<middle_> > step_backward_;
 109     typedef typename eval_if<
 110           cond_
 111         , step_forward_
 112         , step_backward_
 113         >::type type;
 114 };
 115
 116 } // namespace aux
 117
 118 template<
 119       typename BOOST_MPL_AUX_NA_PARAM(Sequence)
 120     , typename BOOST_MPL_AUX_NA_PARAM(T)
 121     , typename Predicate = less<>
 122     >
 123 struct upper_bound
 124 {
 125  private:
 126     typedef typename lambda<Predicate>::type pred_;
 127     typedef typename size<Sequence>::type size_;
 128
 129  public:
 130     typedef typename aux::upper_bound_step<
 131         size_,pred_,T,begin<Sequence>
 132         >::type type;
 133 };
 134
 135 #endif // BOOST_MPL_CFG_STRIPPED_DOWN_UPPER_BOUND_IMPL
 136
 137 BOOST_MPL_AUX_NA_SPEC(2, upper_bound)
 138
 139 }}
 140
 141 #endif // BOOST_MPL_UPPER_BOUND_HPP_INCLUDED