stc/exp/ml_stc_linux_make_v1.0/include/boost/detail/binary_search.hpp

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