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$ 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(BOOST_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 142