Chris@16: 
Chris@16: #ifndef BOOST_MPL_LOWER_BOUND_HPP_INCLUDED
Chris@16: #define BOOST_MPL_LOWER_BOUND_HPP_INCLUDED
Chris@16: 
Chris@16: // Copyright Aleksey Gurtovoy 2001-2004
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. 
Chris@16: // (See accompanying file LICENSE_1_0.txt or copy at 
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // See http://www.boost.org/libs/mpl for documentation.
Chris@16: 
Chris@101: // $Id$
Chris@101: // $Date$
Chris@101: // $Revision$
Chris@16: 
Chris@16: #include <boost/mpl/less.hpp>
Chris@16: #include <boost/mpl/lambda.hpp>
Chris@16: #include <boost/mpl/aux_/na_spec.hpp>
Chris@16: #include <boost/mpl/aux_/config/workaround.hpp>
Chris@16: 
Chris@16: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x610))
Chris@16: #   define BOOST_MPL_CFG_STRIPPED_DOWN_LOWER_BOUND_IMPL
Chris@16: #endif
Chris@16: 
Chris@16: #if !defined(BOOST_MPL_CFG_STRIPPED_DOWN_LOWER_BOUND_IMPL)
Chris@16: #   include <boost/mpl/minus.hpp>
Chris@16: #   include <boost/mpl/divides.hpp>
Chris@16: #   include <boost/mpl/size.hpp>
Chris@16: #   include <boost/mpl/advance.hpp>
Chris@16: #   include <boost/mpl/begin_end.hpp>
Chris@16: #   include <boost/mpl/long.hpp>
Chris@16: #   include <boost/mpl/eval_if.hpp>
Chris@16: #   include <boost/mpl/prior.hpp>
Chris@16: #   include <boost/mpl/deref.hpp>
Chris@16: #   include <boost/mpl/apply.hpp>
Chris@16: #   include <boost/mpl/aux_/value_wknd.hpp>
Chris@16: #else
Chris@16: #   include <boost/mpl/not.hpp>
Chris@16: #   include <boost/mpl/find.hpp>
Chris@16: #   include <boost/mpl/bind.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: 
Chris@16: namespace boost { namespace mpl {
Chris@16: 
Chris@16: #if defined(BOOST_MPL_CFG_STRIPPED_DOWN_LOWER_BOUND_IMPL)
Chris@16: 
Chris@16: // agurt 23/oct/02: has a wrong complexity etc., but at least it works
Chris@16: // feel free to contribute a better implementation!
Chris@16: template<
Chris@16:       typename BOOST_MPL_AUX_NA_PARAM(Sequence)
Chris@16:     , typename BOOST_MPL_AUX_NA_PARAM(T)
Chris@16:     , typename Predicate = less<>
Chris@16:     , typename pred_ = typename lambda<Predicate>::type
Chris@16:     >
Chris@16: struct lower_bound
Chris@16:     : find_if< Sequence, bind1< not_<>, bind2<pred_,_,T> > >
Chris@16: {
Chris@16: };
Chris@16: 
Chris@16: #else
Chris@16: 
Chris@16: namespace aux {
Chris@16: 
Chris@16: template<
Chris@16:       typename Distance
Chris@16:     , typename Predicate
Chris@16:     , typename T
Chris@16:     , typename DeferredIterator
Chris@16:     >
Chris@16: struct lower_bound_step_impl;
Chris@16: 
Chris@16: template< 
Chris@16:       typename Distance
Chris@16:     , typename Predicate
Chris@16:     , typename T
Chris@16:     , typename DeferredIterator
Chris@16:     >
Chris@16: struct lower_bound_step
Chris@16: {
Chris@16:     typedef typename eval_if<
Chris@16:           Distance
Chris@16:         , lower_bound_step_impl<Distance,Predicate,T,DeferredIterator>
Chris@16:         , DeferredIterator
Chris@16:         >::type type;
Chris@16: };
Chris@16:     
Chris@16: template<
Chris@16:       typename Distance
Chris@16:     , typename Predicate
Chris@16:     , typename T
Chris@16:     , typename DeferredIterator
Chris@16:     >
Chris@16: struct lower_bound_step_impl
Chris@16: {
Chris@16:     typedef typename divides< Distance, long_<2> >::type offset_;
Chris@16:     typedef typename DeferredIterator::type iter_;
Chris@16:     typedef typename advance< iter_,offset_ >::type middle_;
Chris@16:     typedef typename apply2<
Chris@16:               Predicate
Chris@16:             , typename deref<middle_>::type
Chris@16:             , T
Chris@16:             >::type cond_;
Chris@16: 
Chris@16:     typedef typename prior< minus< Distance, offset_> >::type step_;
Chris@16:     typedef lower_bound_step< offset_,Predicate,T,DeferredIterator > step_forward_;
Chris@16:     typedef lower_bound_step< step_,Predicate,T,next<middle_> > step_backward_;
Chris@16:     typedef typename eval_if<
Chris@16:           cond_
Chris@16:         , step_backward_
Chris@16:         , step_forward_
Chris@16:         >::type type;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: } // namespace aux
Chris@16: 
Chris@16: template<
Chris@16:       typename BOOST_MPL_AUX_NA_PARAM(Sequence)
Chris@16:     , typename BOOST_MPL_AUX_NA_PARAM(T)
Chris@16:     , typename Predicate = less<>
Chris@16:     >
Chris@16: struct lower_bound
Chris@16: {
Chris@16:  private:
Chris@16:     typedef typename lambda<Predicate>::type pred_;
Chris@16:     typedef typename size<Sequence>::type size_;
Chris@16: 
Chris@16:  public:
Chris@16:     typedef typename aux::lower_bound_step<
Chris@16:         size_,pred_,T,begin<Sequence>
Chris@16:         >::type type;
Chris@16: };
Chris@16: 
Chris@16: #endif // BOOST_MPL_CFG_STRIPPED_DOWN_LOWER_BOUND_IMPL
Chris@16: 
Chris@16: BOOST_MPL_AUX_NA_SPEC(2, lower_bound)
Chris@16: 
Chris@16: }}
Chris@16: 
Chris@16: #endif // BOOST_MPL_LOWER_BOUND_HPP_INCLUDED