EIC code displayed by LXR master/​include/​boost/​detail/​binary_search.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-18 09:30:41

 // Copyright (c)  2000 David Abrahams.
 // 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)
 //
 // Copyright (c) 1994
 // Hewlett-Packard Company
 //
 // Permission to use, copy, modify, distribute and sell this software
 // and its documentation for any purpose is hereby granted without fee,
 // provided that the above copyright notice appear in all copies and
 // that both that copyright notice and this permission notice appear
 // in supporting documentation.  Hewlett-Packard Company makes no
 // representations about the suitability of this software for any
 // purpose.  It is provided "as is" without express or implied warranty.
 //
 // Copyright (c) 1996
 // Silicon Graphics Computer Systems, Inc.
 //
 // Permission to use, copy, modify, distribute and sell this software
 // and its documentation for any purpose is hereby granted without fee,
 // provided that the above copyright notice appear in all copies and
 // that both that copyright notice and this permission notice appear
 // in supporting documentation.  Silicon Graphics makes no
 // representations about the suitability of this software for any
 // purpose.  It is provided "as is" without express or implied warranty.
 //
 #ifndef BINARY_SEARCH_DWA_122600_H_
 # define BINARY_SEARCH_DWA_122600_H_
 
 # include <utility>
 # include <iterator>
 
 namespace boost { namespace detail {
 
 template <class ForwardIter, class Tp>
 ForwardIter lower_bound(ForwardIter first, ForwardIter last,
                              const Tp& val)
 {
     typedef std::iterator_traits<ForwardIter> traits;
 
     typename traits::difference_type len = std::distance(first, last);
     typename traits::difference_type half;
     ForwardIter middle;
 
     while (len > 0) {
       half = len >> 1;
       middle = first;
       std::advance(middle, half);
       if (*middle < val) {
         first = middle;
         ++first;
         len = len - half - 1;
       }
       else
         len = half;
     }
     return first;
 }
 
 template <class ForwardIter, class Tp, class Compare>
 ForwardIter lower_bound(ForwardIter first, ForwardIter last,
                               const Tp& val, Compare comp)
 {
   typedef std::iterator_traits<ForwardIter> traits;
 
   typename traits::difference_type len = std::distance(first, last);
   typename traits::difference_type half;
   ForwardIter middle;
 
   while (len > 0) {
     half = len >> 1;
     middle = first;
     std::advance(middle, half);
     if (comp(*middle, val)) {
       first = middle;
       ++first;
       len = len - half - 1;
     }
     else
       len = half;
   }
   return first;
 }
 
 template <class ForwardIter, class Tp>
 ForwardIter upper_bound(ForwardIter first, ForwardIter last,
                            const Tp& val)
 {
   typedef std::iterator_traits<ForwardIter> traits;
 
   typename traits::difference_type len = std::distance(first, last);
   typename traits::difference_type half;
   ForwardIter middle;
 
   while (len > 0) {
     half = len >> 1;
     middle = first;
     std::advance(middle, half);
     if (val < *middle)
       len = half;
     else {
       first = middle;
       ++first;
       len = len - half - 1;
     }
   }
   return first;
 }
 
 template <class ForwardIter, class Tp, class Compare>
 ForwardIter upper_bound(ForwardIter first, ForwardIter last,
                            const Tp& val, Compare comp)
 {
   typedef std::iterator_traits<ForwardIter> traits;
 
   typename traits::difference_type len = std::distance(first, last);
   typename traits::difference_type half;
   ForwardIter middle;
 
   while (len > 0) {
     half = len >> 1;
     middle = first;
     std::advance(middle, half);
     if (comp(val, *middle))
       len = half;
     else {
       first = middle;
       ++first;
       len = len - half - 1;
     }
   }
   return first;
 }
 
 template <class ForwardIter, class Tp>
 std::pair<ForwardIter, ForwardIter>
 equal_range(ForwardIter first, ForwardIter last, const Tp& val)
 {
   typedef std::iterator_traits<ForwardIter> traits;
 
   typename traits::difference_type len = std::distance(first, last);
   typename traits::difference_type half;
   ForwardIter middle, left, right;
 
   while (len > 0) {
     half = len >> 1;
     middle = first;
     std::advance(middle, half);
     if (*middle < val) {
       first = middle;
       ++first;
       len = len - half - 1;
     }
     else if (val < *middle)
       len = half;
     else {
       left = boost::detail::lower_bound(first, middle, val);
       std::advance(first, len);
       right = boost::detail::upper_bound(++middle, first, val);
       return std::pair<ForwardIter, ForwardIter>(left, right);
     }
   }
   return std::pair<ForwardIter, ForwardIter>(first, first);
 }
 
 template <class ForwardIter, class Tp, class Compare>
 std::pair<ForwardIter, ForwardIter>
 equal_range(ForwardIter first, ForwardIter last, const Tp& val,
               Compare comp)
 {
   typedef std::iterator_traits<ForwardIter> traits;
 
   typename traits::difference_type len = std::distance(first, last);
   typename traits::difference_type half;
   ForwardIter middle, left, right;
 
   while (len > 0) {
     half = len >> 1;
     middle = first;
     std::advance(middle, half);
     if (comp(*middle, val)) {
       first = middle;
       ++first;
       len = len - half - 1;
     }
     else if (comp(val, *middle))
       len = half;
     else {
       left = boost::detail::lower_bound(first, middle, val, comp);
       std::advance(first, len);
       right = boost::detail::upper_bound(++middle, first, val, comp);
       return std::pair<ForwardIter, ForwardIter>(left, right);
     }
   }
   return std::pair<ForwardIter, ForwardIter>(first, first);
 }
 
 template <class ForwardIter, class Tp>
 bool binary_search(ForwardIter first, ForwardIter last,
                    const Tp& val) {
   ForwardIter i = boost::detail::lower_bound(first, last, val);
   return i != last && !(val < *i);
 }
 
 template <class ForwardIter, class Tp, class Compare>
 bool binary_search(ForwardIter first, ForwardIter last,
                    const Tp& val,
                    Compare comp) {
   ForwardIter i = boost::detail::lower_bound(first, last, val, comp);
   return i != last && !comp(val, *i);
 }
 
 }} // namespace boost::detail
 
 #endif // BINARY_SEARCH_DWA_122600_H_

This page was automatically generated by the 2.3.7 LXR engine. The LXR team