80 lines
2.0 KiB
C++
80 lines
2.0 KiB
C++
//////////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// (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
|