1 // Copyright (c)  2000 David Abrahams. 

     2 // Distributed under the Boost Software License, Version 1.0. 

     3 // (See accompanying file LICENSE_1_0.txt or copy at 

     4 // http://www.boost.org/LICENSE_1_0.txt)

     5 // 

     6 // Copyright (c) 1994

     7 // Hewlett-Packard Company

     8 // 

     9 // Permission to use, copy, modify, distribute and sell this software

    10 // and its documentation for any purpose is hereby granted without fee,

    11 // provided that the above copyright notice appear in all copies and

    12 // that both that copyright notice and this permission notice appear

    13 // in supporting documentation.  Hewlett-Packard Company makes no

    14 // representations about the suitability of this software for any

    15 // purpose.  It is provided "as is" without express or implied warranty.

    16 // 

    17 // Copyright (c) 1996

    18 // Silicon Graphics Computer Systems, Inc.

    19 // 

    20 // Permission to use, copy, modify, distribute and sell this software

    21 // and its documentation for any purpose is hereby granted without fee,

    22 // provided that the above copyright notice appear in all copies and

    23 // that both that copyright notice and this permission notice appear

    24 // in supporting documentation.  Silicon Graphics makes no

    25 // representations about the suitability of this software for any

    26 // purpose.  It is provided "as is" without express or implied warranty.

    27 // 

    28 #ifndef BINARY_SEARCH_DWA_122600_H_

    29 # define BINARY_SEARCH_DWA_122600_H_

    30 

    31 # include <boost/detail/iterator.hpp>

    32 # include <utility>

    33 

    34 namespace boost { namespace detail {

    35 

    36 template <class ForwardIter, class Tp>

    37 ForwardIter lower_bound(ForwardIter first, ForwardIter last,

    38                              const Tp& val) 

    39 {

    40     typedef detail::iterator_traits<ForwardIter> traits;

    41     

    42     typename traits::difference_type len = boost::detail::distance(first, last);

    43     typename traits::difference_type half;

    44     ForwardIter middle;

    45 

    46     while (len > 0) {

    47       half = len >> 1;

    48       middle = first;

    49       std::advance(middle, half);

    50       if (*middle < val) {

    51         first = middle;

    52         ++first;

    53         len = len - half - 1;

    54       }

    55       else

    56         len = half;

    57     }

    58     return first;

    59 }

    60 

    61 template <class ForwardIter, class Tp, class Compare>

    62 ForwardIter lower_bound(ForwardIter first, ForwardIter last,

    63                               const Tp& val, Compare comp)

    64 {

    65   typedef detail::iterator_traits<ForwardIter> traits;

    66 

    67   typename traits::difference_type len = boost::detail::distance(first, last);

    68   typename traits::difference_type half;

    69   ForwardIter middle;

    70 

    71   while (len > 0) {

    72     half = len >> 1;

    73     middle = first;

    74     std::advance(middle, half);

    75     if (comp(*middle, val)) {

    76       first = middle;

    77       ++first;

    78       len = len - half - 1;

    79     }

    80     else

    81       len = half;

    82   }

    83   return first;

    84 }

    85 

    86 template <class ForwardIter, class Tp>

    87 ForwardIter upper_bound(ForwardIter first, ForwardIter last,

    88                            const Tp& val)

    89 {

    90   typedef detail::iterator_traits<ForwardIter> traits;

    91 

    92   typename traits::difference_type len = boost::detail::distance(first, last);

    93   typename traits::difference_type half;

    94   ForwardIter middle;

    95 

    96   while (len > 0) {

    97     half = len >> 1;

    98     middle = first;

    99     std::advance(middle, half);

   100     if (val < *middle)

   101       len = half;

   102     else {

   103       first = middle;

   104       ++first;

   105       len = len - half - 1;

   106     }

   107   }

   108   return first;

   109 }

   110 

   111 template <class ForwardIter, class Tp, class Compare>

   112 ForwardIter upper_bound(ForwardIter first, ForwardIter last,

   113                            const Tp& val, Compare comp)

   114 {

   115   typedef detail::iterator_traits<ForwardIter> traits;

   116 

   117   typename traits::difference_type len = boost::detail::distance(first, last);

   118   typename traits::difference_type half;

   119   ForwardIter middle;

   120 

   121   while (len > 0) {

   122     half = len >> 1;

   123     middle = first;

   124     std::advance(middle, half);

   125     if (comp(val, *middle))

   126       len = half;

   127     else {

   128       first = middle;

   129       ++first;

   130       len = len - half - 1;

   131     }

   132   }

   133   return first;

   134 }

   135 

   136 template <class ForwardIter, class Tp>

   137 std::pair<ForwardIter, ForwardIter>

   138 equal_range(ForwardIter first, ForwardIter last, const Tp& val)

   139 {

   140   typedef detail::iterator_traits<ForwardIter> traits;

   141 

   142   typename traits::difference_type len = boost::detail::distance(first, last);

   143   typename traits::difference_type half;

   144   ForwardIter middle, left, right;

   145 

   146   while (len > 0) {

   147     half = len >> 1;

   148     middle = first;

   149     std::advance(middle, half);

   150     if (*middle < val) {

   151       first = middle;

   152       ++first;

   153       len = len - half - 1;

   154     }

   155     else if (val < *middle)

   156       len = half;

   157     else {

   158       left = boost::detail::lower_bound(first, middle, val);

   159       std::advance(first, len);

   160       right = boost::detail::upper_bound(++middle, first, val);

   161       return std::pair<ForwardIter, ForwardIter>(left, right);

   162     }

   163   }

   164   return std::pair<ForwardIter, ForwardIter>(first, first);

   165 }

   166 

   167 template <class ForwardIter, class Tp, class Compare>

   168 std::pair<ForwardIter, ForwardIter>

   169 equal_range(ForwardIter first, ForwardIter last, const Tp& val,

   170               Compare comp)

   171 {

   172   typedef detail::iterator_traits<ForwardIter> traits;

   173 

   174   typename traits::difference_type len = boost::detail::distance(first, last);

   175   typename traits::difference_type half;

   176   ForwardIter middle, left, right;

   177 

   178   while (len > 0) {

   179     half = len >> 1;

   180     middle = first;

   181     std::advance(middle, half);

   182     if (comp(*middle, val)) {

   183       first = middle;

   184       ++first;

   185       len = len - half - 1;

   186     }

   187     else if (comp(val, *middle))

   188       len = half;

   189     else {

   190       left = boost::detail::lower_bound(first, middle, val, comp);

   191       std::advance(first, len);

   192       right = boost::detail::upper_bound(++middle, first, val, comp);

   193       return std::pair<ForwardIter, ForwardIter>(left, right);

   194     }

   195   }

   196   return std::pair<ForwardIter, ForwardIter>(first, first);

   197 }           

   198 

   199 template <class ForwardIter, class Tp>

   200 bool binary_search(ForwardIter first, ForwardIter last,

   201                    const Tp& val) {

   202   ForwardIter i = boost::detail::lower_bound(first, last, val);

   203   return i != last && !(val < *i);

   204 }

   205 

   206 template <class ForwardIter, class Tp, class Compare>

   207 bool binary_search(ForwardIter first, ForwardIter last,

   208                    const Tp& val,

   209                    Compare comp) {

   210   ForwardIter i = boost::detail::lower_bound(first, last, val, comp);

   211   return i != last && !comp(val, *i);

   212 }

   213 

   214 }} // namespace boost::detail

   215 

   216 #endif // BINARY_SEARCH_DWA_122600_H_