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.
8 // Hewlett-Packard Company
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.
19 // Silicon Graphics Computer Systems, Inc.
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.
29 #ifndef BINARY_SEARCH_DWA_122600_H_
30 # define BINARY_SEARCH_DWA_122600_H_
32 # include <boost/detail/iterator.hpp>
35 namespace boost { namespace detail {
37 template <class ForwardIter, class Tp>
38 ForwardIter lower_bound(ForwardIter first, ForwardIter last,
41 typedef detail::iterator_traits<ForwardIter> traits;
43 typename traits::difference_type len = boost::detail::distance(first, last);
44 typename traits::difference_type half;
50 std::advance(middle, half);
62 template <class ForwardIter, class Tp, class Compare>
63 ForwardIter lower_bound(ForwardIter first, ForwardIter last,
64 const Tp& val, Compare comp)
66 typedef detail::iterator_traits<ForwardIter> traits;
68 typename traits::difference_type len = boost::detail::distance(first, last);
69 typename traits::difference_type half;
75 std::advance(middle, half);
76 if (comp(*middle, val)) {
87 template <class ForwardIter, class Tp>
88 ForwardIter upper_bound(ForwardIter first, ForwardIter last,
91 typedef detail::iterator_traits<ForwardIter> traits;
93 typename traits::difference_type len = boost::detail::distance(first, last);
94 typename traits::difference_type half;
100 std::advance(middle, half);
106 len = len - half - 1;
112 template <class ForwardIter, class Tp, class Compare>
113 ForwardIter upper_bound(ForwardIter first, ForwardIter last,
114 const Tp& val, Compare comp)
116 typedef detail::iterator_traits<ForwardIter> traits;
118 typename traits::difference_type len = boost::detail::distance(first, last);
119 typename traits::difference_type half;
125 std::advance(middle, half);
126 if (comp(val, *middle))
131 len = len - half - 1;
137 template <class ForwardIter, class Tp>
138 std::pair<ForwardIter, ForwardIter>
139 equal_range(ForwardIter first, ForwardIter last, const Tp& val)
141 typedef detail::iterator_traits<ForwardIter> traits;
143 typename traits::difference_type len = boost::detail::distance(first, last);
144 typename traits::difference_type half;
145 ForwardIter middle, left, right;
150 std::advance(middle, half);
154 len = len - half - 1;
156 else if (val < *middle)
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);
165 return std::pair<ForwardIter, ForwardIter>(first, first);
168 template <class ForwardIter, class Tp, class Compare>
169 std::pair<ForwardIter, ForwardIter>
170 equal_range(ForwardIter first, ForwardIter last, const Tp& val,
173 typedef detail::iterator_traits<ForwardIter> traits;
175 typename traits::difference_type len = boost::detail::distance(first, last);
176 typename traits::difference_type half;
177 ForwardIter middle, left, right;
182 std::advance(middle, half);
183 if (comp(*middle, val)) {
186 len = len - half - 1;
188 else if (comp(val, *middle))
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);
197 return std::pair<ForwardIter, ForwardIter>(first, first);
200 template <class ForwardIter, class Tp>
201 bool binary_search(ForwardIter first, ForwardIter last,
203 ForwardIter i = boost::detail::lower_bound(first, last, val);
204 return i != last && !(val < *i);
207 template <class ForwardIter, class Tp, class Compare>
208 bool binary_search(ForwardIter first, ForwardIter last,
211 ForwardIter i = boost::detail::lower_bound(first, last, val, comp);
212 return i != last && !comp(val, *i);
215 }} // namespace boost::detail
217 #endif // BINARY_SEARCH_DWA_122600_H_