boost/boost/detail/binary_search.hpp

   1 // Copyright (c)  2000 David Abrahams. Permission to copy, use, modify,
   2 // sell and distribute this software is granted provided this
   3 // copyright notice appears in all copies. This software is provided
   4 // "as is" without express or implied warranty, and with no claim as
   5 // to its suitability for any purpose.
   6 //
   7 // Copyright (c) 1994
   8 // Hewlett-Packard Company
   9 //
  10 // Permission to use, copy, modify, distribute and sell this software
  11 // and its documentation for any purpose is hereby granted without fee,
  12 // provided that the above copyright notice appear in all copies and
  13 // that both that copyright notice and this permission notice appear
  14 // in supporting documentation.  Hewlett-Packard Company makes no
  15 // representations about the suitability of this software for any
  16 // purpose.  It is provided "as is" without express or implied warranty.
  17 //
  18 // Copyright (c) 1996
  19 // Silicon Graphics Computer Systems, Inc.
  20 //
  21 // Permission to use, copy, modify, distribute and sell this software
  22 // and its documentation for any purpose is hereby granted without fee,
  23 // provided that the above copyright notice appear in all copies and
  24 // that both that copyright notice and this permission notice appear
  25 // in supporting documentation.  Silicon Graphics makes no
  26 // representations about the suitability of this software for any
  27 // purpose.  It is provided "as is" without express or implied warranty.
  28 //
  29 #ifndef BINARY_SEARCH_DWA_122600_H_
  30 # define BINARY_SEARCH_DWA_122600_H_
  31
  32 # include <boost/detail/iterator.hpp>
  33 # include <utility>
  34
  35 namespace boost { namespace detail {
  36
  37 template <class ForwardIter, class Tp>
  38 ForwardIter lower_bound(ForwardIter first, ForwardIter last,
  39                              const Tp& val)
  40 {
  41     typedef detail::iterator_traits<ForwardIter> traits;
  42
  43     typename traits::difference_type len = boost::detail::distance(first, last);
  44     typename traits::difference_type half;
  45     ForwardIter middle;
  46
  47     while (len > 0) {
  48       half = len >> 1;
  49       middle = first;
  50       std::advance(middle, half);
  51       if (*middle < val) {
  52         first = middle;
  53         ++first;
  54         len = len - half - 1;
  55       }
  56       else
  57         len = half;
  58     }
  59     return first;
  60 }
  61
  62 template <class ForwardIter, class Tp, class Compare>
  63 ForwardIter lower_bound(ForwardIter first, ForwardIter last,
  64                               const Tp& val, Compare comp)
  65 {
  66   typedef detail::iterator_traits<ForwardIter> traits;
  67
  68   typename traits::difference_type len = boost::detail::distance(first, last);
  69   typename traits::difference_type half;
  70   ForwardIter middle;
  71
  72   while (len > 0) {
  73     half = len >> 1;
  74     middle = first;
  75     std::advance(middle, half);
  76     if (comp(*middle, val)) {
  77       first = middle;
  78       ++first;
  79       len = len - half - 1;
  80     }
  81     else
  82       len = half;
  83   }
  84   return first;
  85 }
  86
  87 template <class ForwardIter, class Tp>
  88 ForwardIter upper_bound(ForwardIter first, ForwardIter last,
  89                            const Tp& val)
  90 {
  91   typedef detail::iterator_traits<ForwardIter> traits;
  92
  93   typename traits::difference_type len = boost::detail::distance(first, last);
  94   typename traits::difference_type half;
  95   ForwardIter middle;
  96
  97   while (len > 0) {
  98     half = len >> 1;
  99     middle = first;
 100     std::advance(middle, half);
 101     if (val < *middle)
 102       len = half;
 103     else {
 104       first = middle;
 105       ++first;
 106       len = len - half - 1;
 107     }
 108   }
 109   return first;
 110 }
 111
 112 template <class ForwardIter, class Tp, class Compare>
 113 ForwardIter upper_bound(ForwardIter first, ForwardIter last,
 114                            const Tp& val, Compare comp)
 115 {
 116   typedef detail::iterator_traits<ForwardIter> traits;
 117
 118   typename traits::difference_type len = boost::detail::distance(first, last);
 119   typename traits::difference_type half;
 120   ForwardIter middle;
 121
 122   while (len > 0) {
 123     half = len >> 1;
 124     middle = first;
 125     std::advance(middle, half);
 126     if (comp(val, *middle))
 127       len = half;
 128     else {
 129       first = middle;
 130       ++first;
 131       len = len - half - 1;
 132     }
 133   }
 134   return first;
 135 }
 136
 137 template <class ForwardIter, class Tp>
 138 std::pair<ForwardIter, ForwardIter>
 139 equal_range(ForwardIter first, ForwardIter last, const Tp& val)
 140 {
 141   typedef detail::iterator_traits<ForwardIter> traits;
 142
 143   typename traits::difference_type len = boost::detail::distance(first, last);
 144   typename traits::difference_type half;
 145   ForwardIter middle, left, right;
 146
 147   while (len > 0) {
 148     half = len >> 1;
 149     middle = first;
 150     std::advance(middle, half);
 151     if (*middle < val) {
 152       first = middle;
 153       ++first;
 154       len = len - half - 1;
 155     }
 156     else if (val < *middle)
 157       len = half;
 158     else {
 159       left = boost::detail::lower_bound(first, middle, val);
 160       std::advance(first, len);
 161       right = boost::detail::upper_bound(++middle, first, val);
 162       return std::pair<ForwardIter, ForwardIter>(left, right);
 163     }
 164   }
 165   return std::pair<ForwardIter, ForwardIter>(first, first);
 166 }
 167
 168 template <class ForwardIter, class Tp, class Compare>
 169 std::pair<ForwardIter, ForwardIter>
 170 equal_range(ForwardIter first, ForwardIter last, const Tp& val,
 171               Compare comp)
 172 {
 173   typedef detail::iterator_traits<ForwardIter> traits;
 174
 175   typename traits::difference_type len = boost::detail::distance(first, last);
 176   typename traits::difference_type half;
 177   ForwardIter middle, left, right;
 178
 179   while (len > 0) {
 180     half = len >> 1;
 181     middle = first;
 182     std::advance(middle, half);
 183     if (comp(*middle, val)) {
 184       first = middle;
 185       ++first;
 186       len = len - half - 1;
 187     }
 188     else if (comp(val, *middle))
 189       len = half;
 190     else {
 191       left = boost::detail::lower_bound(first, middle, val, comp);
 192       std::advance(first, len);
 193       right = boost::detail::upper_bound(++middle, first, val, comp);
 194       return std::pair<ForwardIter, ForwardIter>(left, right);
 195     }
 196   }
 197   return std::pair<ForwardIter, ForwardIter>(first, first);
 198 }
 199
 200 template <class ForwardIter, class Tp>
 201 bool binary_search(ForwardIter first, ForwardIter last,
 202                    const Tp& val) {
 203   ForwardIter i = boost::detail::lower_bound(first, last, val);
 204   return i != last && !(val < *i);
 205 }
 206
 207 template <class ForwardIter, class Tp, class Compare>
 208 bool binary_search(ForwardIter first, ForwardIter last,
 209                    const Tp& val,
 210                    Compare comp) {
 211   ForwardIter i = boost::detail::lower_bound(first, last, val, comp);
 212   return i != last && !comp(val, *i);
 213 }
 214
 215 }} // namespace boost::detail
 216
 217 #endif // BINARY_SEARCH_DWA_122600_H_