boost/move/algo/detail/search.hpp
//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2022-2022.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/move for documentation.
//
//////////////////////////////////////////////////////////////////////////////
#ifndef BOOST_MOVE_DETAIL_SEARCH_HPP
#define BOOST_MOVE_DETAIL_SEARCH_HPP
#include <boost/move/detail/iterator_traits.hpp>
#if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wsign-conversion"
#endif
namespace boost {
namespace movelib {
template <class RandIt, class T, class Compare>
RandIt lower_bound
(RandIt first, const RandIt last, const T& key, Compare comp)
{
typedef typename iter_size<RandIt>::type size_type;
size_type len = size_type(last - first);
RandIt middle;
while (len) {
size_type step = size_type(len >> 1);
middle = first;
middle += step;
if (comp(*middle, key)) {
first = ++middle;
len = size_type(len - (step + 1));
}
else{
len = step;
}
}
return first;
}
template <class RandIt, class T, class Compare>
RandIt upper_bound
(RandIt first, const RandIt last, const T& key, Compare comp)
{
typedef typename iter_size<RandIt>::type size_type;
size_type len = size_type(last - first);
RandIt middle;
while (len) {
size_type step = size_type(len >> 1);
middle = first;
middle += step;
if (!comp(key, *middle)) {
first = ++middle;
len = size_type(len - (step + 1));
}
else{
len = step;
}
}
return first;
}
} //namespace movelib {
} //namespace boost {
#if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
#pragma GCC diagnostic pop
#endif
#endif //#define BOOST_MOVE_DETAIL_SEARCH_HPP