]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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_ |