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_ 217
