boost/detail/binary_search.hpp

   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_