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