ceph/src/boost/libs/mpl/include/boost/mpl/lower_bound.hpp

   1
   2 #ifndef BOOST_MPL_LOWER_BOUND_HPP_INCLUDED
   3 #define BOOST_MPL_LOWER_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$
  14 // $Date$
  15 // $Revision$
  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_LOWER_BOUND_IMPL
  24 #endif
  25
  26 #if !defined(BOOST_MPL_CFG_STRIPPED_DOWN_LOWER_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/not.hpp>
  40 #   include <boost/mpl/find.hpp>
  41 #   include <boost/mpl/bind.hpp>
  42 #endif
  43
  44 #include <boost/config.hpp>
  45
  46 namespace boost { namespace mpl {
  47
  48 #if defined(BOOST_MPL_CFG_STRIPPED_DOWN_LOWER_BOUND_IMPL)
  49
  50 // agurt 23/oct/02: has a wrong complexity etc., but at least it works
  51 // feel free to contribute a better implementation!
  52 template<
  53       typename BOOST_MPL_AUX_NA_PARAM(Sequence)
  54     , typename BOOST_MPL_AUX_NA_PARAM(T)
  55     , typename Predicate = less<>
  56     , typename pred_ = typename lambda<Predicate>::type
  57     >
  58 struct lower_bound
  59     : find_if< Sequence, bind1< not_<>, bind2<pred_,_,T> > >
  60 {
  61 };
  62
  63 #else
  64
  65 namespace aux {
  66
  67 template<
  68       typename Distance
  69     , typename Predicate
  70     , typename T
  71     , typename DeferredIterator
  72     >
  73 struct lower_bound_step_impl;
  74
  75 template<
  76       typename Distance
  77     , typename Predicate
  78     , typename T
  79     , typename DeferredIterator
  80     >
  81 struct lower_bound_step
  82 {
  83     typedef typename eval_if<
  84           Distance
  85         , lower_bound_step_impl<Distance,Predicate,T,DeferredIterator>
  86         , DeferredIterator
  87         >::type type;
  88 };
  89
  90 template<
  91       typename Distance
  92     , typename Predicate
  93     , typename T
  94     , typename DeferredIterator
  95     >
  96 struct lower_bound_step_impl
  97 {
  98     typedef typename divides< Distance, long_<2> >::type offset_;
  99     typedef typename DeferredIterator::type iter_;
 100     typedef typename advance< iter_,offset_ >::type middle_;
 101     typedef typename apply2<
 102               Predicate
 103             , typename deref<middle_>::type
 104             , T
 105             >::type cond_;
 106
 107     typedef typename prior< minus< Distance, offset_> >::type step_;
 108     typedef lower_bound_step< offset_,Predicate,T,DeferredIterator > step_forward_;
 109     typedef lower_bound_step< step_,Predicate,T,next<middle_> > step_backward_;
 110     typedef typename eval_if<
 111           cond_
 112         , step_backward_
 113         , step_forward_
 114         >::type type;
 115 };
 116
 117
 118 } // namespace aux
 119
 120 template<
 121       typename BOOST_MPL_AUX_NA_PARAM(Sequence)
 122     , typename BOOST_MPL_AUX_NA_PARAM(T)
 123     , typename Predicate = less<>
 124     >
 125 struct lower_bound
 126 {
 127  private:
 128     typedef typename lambda<Predicate>::type pred_;
 129     typedef typename size<Sequence>::type size_;
 130
 131  public:
 132     typedef typename aux::lower_bound_step<
 133         size_,pred_,T,begin<Sequence>
 134         >::type type;
 135 };
 136
 137 #endif // BOOST_MPL_CFG_STRIPPED_DOWN_LOWER_BOUND_IMPL
 138
 139 BOOST_MPL_AUX_NA_SPEC(2, lower_bound)
 140
 141 }}
 142
 143 #endif // BOOST_MPL_LOWER_BOUND_HPP_INCLUDED