algo/detail/search.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2022-2022.
0004 // Distributed under the Boost Software License, Version 1.0.
0005 // (See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 // See http://www.boost.org/libs/move for documentation.
0009 //
0010 //////////////////////////////////////////////////////////////////////////////
0011 #ifndef BOOST_MOVE_DETAIL_SEARCH_HPP
0012 #define BOOST_MOVE_DETAIL_SEARCH_HPP
0013
0014 #include <boost/move/detail/iterator_traits.hpp>
0015
0016 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0017 #pragma GCC diagnostic push
0018 #pragma GCC diagnostic ignored "-Wsign-conversion"
0019 #endif
0020
0021 namespace boost {
0022 namespace movelib {
0023
0024 template <class RandIt, class T, class Compare>
0025 RandIt lower_bound
0026    (RandIt first, const RandIt last, const T& key, Compare comp)
0027 {
0028    typedef typename iter_size<RandIt>::type size_type;
0029    size_type len = size_type(last - first);
0030    RandIt middle;
0031
0032    while (len) {
0033       size_type step = size_type(len >> 1);
0034       middle = first;
0035       middle += step;
0036
0037       if (comp(*middle, key)) {
0038          first = ++middle;
0039          len = size_type(len - (step + 1));
0040       }
0041       else{
0042          len = step;
0043       }
0044    }
0045    return first;
0046 }
0047
0048 template <class RandIt, class T, class Compare>
0049 RandIt upper_bound
0050    (RandIt first, const RandIt last, const T& key, Compare comp)
0051 {
0052    typedef typename iter_size<RandIt>::type size_type;
0053    size_type len = size_type(last - first);
0054    RandIt middle;
0055
0056    while (len) {
0057       size_type step = size_type(len >> 1);
0058       middle = first;
0059       middle += step;
0060
0061       if (!comp(key, *middle)) {
0062          first = ++middle;
0063          len = size_type(len - (step + 1));
0064       }
0065       else{
0066          len = step;
0067       }
0068    }
0069    return first;
0070 }
0071
0072 }  //namespace movelib {
0073 }  //namespace boost {
0074
0075 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0076 #pragma GCC diagnostic pop
0077 #endif
0078
0079 #endif   //#define BOOST_MOVE_DETAIL_SEARCH_HPP