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