binary_search.hpp

Go to the documentation of this file.

/*
    Copyright 2005-2007 Adobe Systems Incorporated
    Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
    or a copy at http://stlab.adobe.com/licenses.html)
*/

/*************************************************************************************************/

#ifndef ADOBE_ALGORITHM_BINARY_SEARCH_HPP
#define ADOBE_ALGORITHM_BINARY_SEARCH_HPP

#include <adobe/config.hpp>

#include <boost/range/begin.hpp>
#include <boost/range/const_iterator.hpp>
#include <boost/range/end.hpp>
#include <boost/range/iterator.hpp>

#include <adobe/algorithm/lower_bound.hpp>
#include <adobe/functional/operator.hpp>

/*************************************************************************************************/

namespace adobe {

namespace implementation {

template <typename I, // I models ForwardIterator
          typename T, // T models Regular
          typename C, // C models StrictWeakOrdering
          typename P> // P models UnaryFunction(value_type(I)) -> T
inline I binary_search(I f, I l, const T& x, C c, P p)
{
    I result = adobe::lower_bound(f, l, x, c, p);
    if (result != l && p(*result) == x) return result;
    return l;
}

}

/*************************************************************************************************/
/*************************************************************************************************/

template <typename I, // I models ForwardIterator
          typename T, // T models Regular
          typename C, // C models StrictWeakOrdering
          typename P> // P models UnaryFunction(value_type(I)) -> T
inline I binary_search(I f, I l, const T& x, C c, P p)
{
    return implementation::binary_search(f, l, x, c, boost::bind(p, _1));
}


template <typename I, // I models ForwardIterator
          typename T, // T models Regular
          typename C> // C models StrictWeakOrdering
inline I binary_search(I f, I l, const T& x, C c)
{
    return adobe::binary_search(f, l, x, c, identity<T>());
}

template <typename I, // I models ForwardIterator
          typename T> // T models Regular
inline I binary_search(I f, I l, const T& x)
{ return binary_search(f, l, x, less()); }

template <typename I, typename T>
inline typename boost::range_iterator<I>::type binary_search(I& range, const T& x)
{
    return adobe::binary_search(boost::begin(range), boost::end(range), x);
}

template <typename I, typename T>
inline typename boost::range_const_iterator<I>::type binary_search(const I& range, const T& x)
{
    return adobe::binary_search(boost::begin(range), boost::end(range), x);
}

template <typename I, typename T, typename C>
inline typename boost::range_iterator<I>::type binary_search(I& range, const T& x, C c)
{
    return adobe::binary_search(boost::begin(range), boost::end(range), x, c);
}

template <typename I, typename T, typename C>
inline typename boost::range_const_iterator<I>::type binary_search(const I& range, const T& x, C c)
{
    return adobe::binary_search(boost::begin(range), boost::end(range), x, c);
}

/*************************************************************************************************/

template <  typename I, // I models ForwardRange
            typename T, // T == result_type(P)
            typename C, // C models StrictWeakOrdering(T, T)
            typename P> // P models UnaryFunction(value_type(I)) -> T
inline
    typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type
        binary_search(I& r, const T& x, C c, P p)
{ return adobe::binary_search(boost::begin(r), boost::end(r), x, c, p); }

/*************************************************************************************************/

template <  typename I, // I models ForwardRange
            typename T, // T == result_type(P)
            typename C, // C models StrictWeakOrdering(T, T)
            typename P> // P models UnaryFunction(value_type(I)) -> T
inline
    typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type
        binary_search(const I& r, const T& x, C c, P p)
{ return adobe::binary_search(boost::begin(r), boost::end(r), x, c, p); }

/*************************************************************************************************/

} // namespace adobe

/*************************************************************************************************/

#endif

/*************************************************************************************************/