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(BOOST_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 144