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