root / tmp / org.txm.statsengine.r.core.win32 / res / win32 / library / BH / include / boost / algorithm / minmax_element.hpp @ 2486
History  View  Annotate  Download (17 kB)
1 
// (C) Copyright Herve Bronnimann 2004.


2 
//

3 
// Distributed under the Boost Software License, Version 1.0. (See accompanying

4 
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

5  
6 
/*

7 
Revision history:

8 
1 July 2004

9 
Split the code into two headers to lessen dependence on

10 
Boost.tuple. (Herve)

11 
26 June 2004

12 
Added the code for the boost minmax library. (Herve)

13 
*/

14  
15 
#ifndef BOOST_ALGORITHM_MINMAX_ELEMENT_HPP

16 
#define BOOST_ALGORITHM_MINMAX_ELEMENT_HPP

17  
18 
/* PROPOSED STANDARD EXTENSIONS:

19 
*

20 
* minmax_element(first, last)

21 
* Effect: std::make_pair( std::min_element(first, last),

22 
* std::max_element(first, last) );

23 
*

24 
* minmax_element(first, last, comp)

25 
* Effect: std::make_pair( std::min_element(first, last, comp),

26 
* std::max_element(first, last, comp) );

27 
*/

28  
29 
#include <utility> // for std::pair and std::make_pair 
30  
31 
namespace boost {

32  
33 
namespace detail { // for obtaining a uniform version of minmax_element 
34 
// that compiles with VC++ 6.0  avoid the iterator_traits by

35 
// having comparison object over iterator, not over dereferenced value

36  
37 
template <typename Iterator> 
38 
struct less_over_iter {

39 
bool operator()(Iterator const& it1, 
40 
Iterator const& it2) const { return *it1 < *it2; } 
41 
}; 
42  
43 
template <typename Iterator, class BinaryPredicate> 
44 
struct binary_pred_over_iter {

45 
explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {} 
46 
bool operator()(Iterator const& it1, 
47 
Iterator const& it2) const { return m_p(*it1, *it2); } 
48 
private:

49 
BinaryPredicate m_p; 
50 
}; 
51  
52 
// common base for the two minmax_element overloads

53  
54 
template <typename ForwardIter, class Compare > 
55 
std::pair<ForwardIter,ForwardIter> 
56 
basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp) 
57 
{ 
58 
if (first == last)

59 
return std::make_pair(last,last);

60  
61 
ForwardIter min_result = first; 
62 
ForwardIter max_result = first; 
63  
64 
// if only one element

65 
ForwardIter second = first; ++second; 
66 
if (second == last)

67 
return std::make_pair(min_result, max_result);

68  
69 
// treat first pair separately (only one comparison for first two elements)

70 
ForwardIter potential_min_result = last; 
71 
if (comp(first, second))

72 
max_result = second; 
73 
else {

74 
min_result = second; 
75 
potential_min_result = first; 
76 
} 
77  
78 
// then each element by pairs, with at most 3 comparisons per pair

79 
first = ++second; if (first != last) ++second;

80 
while (second != last) {

81 
if (comp(first, second)) {

82 
if (comp(first, min_result)) {

83 
min_result = first; 
84 
potential_min_result = last; 
85 
} 
86 
if (comp(max_result, second))

87 
max_result = second; 
88 
} else {

89 
if (comp(second, min_result)) {

90 
min_result = second; 
91 
potential_min_result = first; 
92 
} 
93 
if (comp(max_result, first))

94 
max_result = first; 
95 
} 
96 
first = ++second; 
97 
if (first != last) ++second;

98 
} 
99  
100 
// if odd number of elements, treat last element

101 
if (first != last) { // odd number of elements 
102 
if (comp(first, min_result)) {

103 
min_result = first; 
104 
potential_min_result = last; 
105 
} 
106 
else if (comp(max_result, first)) 
107 
max_result = first; 
108 
} 
109  
110 
// resolve min_result being incorrect with one extra comparison

111 
// (in which case potential_min_result is necessarily the correct result)

112 
if (potential_min_result != last

113 
&& !comp(min_result, potential_min_result)) 
114 
min_result = potential_min_result; 
115  
116 
return std::make_pair(min_result,max_result);

117 
} 
118  
119 
} // namespace detail

120  
121 
template <typename ForwardIter> 
122 
std::pair<ForwardIter,ForwardIter> 
123 
minmax_element(ForwardIter first, ForwardIter last) 
124 
{ 
125 
return detail::basic_minmax_element(first, last,

126 
detail::less_over_iter<ForwardIter>() ); 
127 
} 
128  
129 
template <typename ForwardIter, class BinaryPredicate> 
130 
std::pair<ForwardIter,ForwardIter> 
131 
minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 
132 
{ 
133 
return detail::basic_minmax_element(first, last,

134 
detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 
135 
} 
136  
137 
} 
138  
139 
/* PROPOSED BOOST EXTENSIONS

140 
* In the description below, [rfirst,rlast) denotes the reversed range

141 
* of [first,last). Even though the iterator type of first and last may

142 
* be only a Forward Iterator, it is possible to explain the semantics

143 
* by assuming that it is a Bidirectional Iterator. In the sequel,

144 
* reverse(ForwardIterator&) returns the reverse_iterator adaptor.

145 
* This is not how the functions would be implemented!

146 
*

147 
* first_min_element(first, last)

148 
* Effect: std::min_element(first, last);

149 
*

150 
* first_min_element(first, last, comp)

151 
* Effect: std::min_element(first, last, comp);

152 
*

153 
* last_min_element(first, last)

154 
* Effect: reverse( std::min_element(reverse(last), reverse(first)) );

155 
*

156 
* last_min_element(first, last, comp)

157 
* Effect: reverse( std::min_element(reverse(last), reverse(first), comp) );

158 
*

159 
* first_max_element(first, last)

160 
* Effect: std::max_element(first, last);

161 
*

162 
* first_max_element(first, last, comp)

163 
* Effect: max_element(first, last);

164 
*

165 
* last_max_element(first, last)

166 
* Effect: reverse( std::max_element(reverse(last), reverse(first)) );

167 
*

168 
* last_max_element(first, last, comp)

169 
* Effect: reverse( std::max_element(reverse(last), reverse(first), comp) );

170 
*

171 
* first_min_first_max_element(first, last)

172 
* Effect: std::make_pair( first_min_element(first, last),

173 
* first_max_element(first, last) );

174 
*

175 
* first_min_first_max_element(first, last, comp)

176 
* Effect: std::make_pair( first_min_element(first, last, comp),

177 
* first_max_element(first, last, comp) );

178 
*

179 
* first_min_last_max_element(first, last)

180 
* Effect: std::make_pair( first_min_element(first, last),

181 
* last_max_element(first, last) );

182 
*

183 
* first_min_last_max_element(first, last, comp)

184 
* Effect: std::make_pair( first_min_element(first, last, comp),

185 
* last_max_element(first, last, comp) );

186 
*

187 
* last_min_first_max_element(first, last)

188 
* Effect: std::make_pair( last_min_element(first, last),

189 
* first_max_element(first, last) );

190 
*

191 
* last_min_first_max_element(first, last, comp)

192 
* Effect: std::make_pair( last_min_element(first, last, comp),

193 
* first_max_element(first, last, comp) );

194 
*

195 
* last_min_last_max_element(first, last)

196 
* Effect: std::make_pair( last_min_element(first, last),

197 
* last_max_element(first, last) );

198 
*

199 
* last_min_last_max_element(first, last, comp)

200 
* Effect: std::make_pair( last_min_element(first, last, comp),

201 
* last_max_element(first, last, comp) );

202 
*/

203  
204 
namespace boost {

205  
206 
// Min_element and max_element variants

207  
208 
namespace detail { // common base for the overloads 
209  
210 
template <typename ForwardIter, class BinaryPredicate> 
211 
ForwardIter 
212 
basic_first_min_element(ForwardIter first, ForwardIter last, 
213 
BinaryPredicate comp) 
214 
{ 
215 
if (first == last) return last; 
216 
ForwardIter min_result = first; 
217 
while (++first != last)

218 
if (comp(first, min_result))

219 
min_result = first; 
220 
return min_result;

221 
} 
222  
223 
template <typename ForwardIter, class BinaryPredicate> 
224 
ForwardIter 
225 
basic_last_min_element(ForwardIter first, ForwardIter last, 
226 
BinaryPredicate comp) 
227 
{ 
228 
if (first == last) return last; 
229 
ForwardIter min_result = first; 
230 
while (++first != last)

231 
if (!comp(min_result, first))

232 
min_result = first; 
233 
return min_result;

234 
} 
235  
236 
template <typename ForwardIter, class BinaryPredicate> 
237 
ForwardIter 
238 
basic_first_max_element(ForwardIter first, ForwardIter last, 
239 
BinaryPredicate comp) 
240 
{ 
241 
if (first == last) return last; 
242 
ForwardIter max_result = first; 
243 
while (++first != last)

244 
if (comp(max_result, first))

245 
max_result = first; 
246 
return max_result;

247 
} 
248  
249 
template <typename ForwardIter, class BinaryPredicate> 
250 
ForwardIter 
251 
basic_last_max_element(ForwardIter first, ForwardIter last, 
252 
BinaryPredicate comp) 
253 
{ 
254 
if (first == last) return last; 
255 
ForwardIter max_result = first; 
256 
while (++first != last)

257 
if (!comp(first, max_result))

258 
max_result = first; 
259 
return max_result;

260 
} 
261  
262 
} // namespace detail

263  
264 
template <typename ForwardIter> 
265 
ForwardIter 
266 
first_min_element(ForwardIter first, ForwardIter last) 
267 
{ 
268 
return detail::basic_first_min_element(first, last,

269 
detail::less_over_iter<ForwardIter>() ); 
270 
} 
271  
272 
template <typename ForwardIter, class BinaryPredicate> 
273 
ForwardIter 
274 
first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 
275 
{ 
276 
return detail::basic_first_min_element(first, last,

277 
detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 
278 
} 
279  
280 
template <typename ForwardIter> 
281 
ForwardIter 
282 
last_min_element(ForwardIter first, ForwardIter last) 
283 
{ 
284 
return detail::basic_last_min_element(first, last,

285 
detail::less_over_iter<ForwardIter>() ); 
286 
} 
287  
288 
template <typename ForwardIter, class BinaryPredicate> 
289 
ForwardIter 
290 
last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 
291 
{ 
292 
return detail::basic_last_min_element(first, last,

293 
detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 
294 
} 
295  
296 
template <typename ForwardIter> 
297 
ForwardIter 
298 
first_max_element(ForwardIter first, ForwardIter last) 
299 
{ 
300 
return detail::basic_first_max_element(first, last,

301 
detail::less_over_iter<ForwardIter>() ); 
302 
} 
303  
304 
template <typename ForwardIter, class BinaryPredicate> 
305 
ForwardIter 
306 
first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 
307 
{ 
308 
return detail::basic_first_max_element(first, last,

309 
detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 
310 
} 
311  
312 
template <typename ForwardIter> 
313 
ForwardIter 
314 
last_max_element(ForwardIter first, ForwardIter last) 
315 
{ 
316 
return detail::basic_last_max_element(first, last,

317 
detail::less_over_iter<ForwardIter>() ); 
318 
} 
319  
320 
template <typename ForwardIter, class BinaryPredicate> 
321 
ForwardIter 
322 
last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 
323 
{ 
324 
return detail::basic_last_max_element(first, last,

325 
detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 
326 
} 
327  
328  
329 
// Minmax_element variants  comments removed

330  
331 
namespace detail {

332  
333 
template <typename ForwardIter, class BinaryPredicate> 
334 
std::pair<ForwardIter,ForwardIter> 
335 
basic_first_min_last_max_element(ForwardIter first, ForwardIter last, 
336 
BinaryPredicate comp) 
337 
{ 
338 
if (first == last)

339 
return std::make_pair(last,last);

340  
341 
ForwardIter min_result = first; 
342 
ForwardIter max_result = first; 
343  
344 
ForwardIter second = ++first; 
345 
if (second == last)

346 
return std::make_pair(min_result, max_result);

347  
348 
if (comp(second, min_result))

349 
min_result = second; 
350 
else

351 
max_result = second; 
352  
353 
first = ++second; if (first != last) ++second;

354 
while (second != last) {

355 
if (!comp(second, first)) {

356 
if (comp(first, min_result))

357 
min_result = first; 
358 
if (!comp(second, max_result))

359 
max_result = second; 
360 
} else {

361 
if (comp(second, min_result))

362 
min_result = second; 
363 
if (!comp(first, max_result))

364 
max_result = first; 
365 
} 
366 
first = ++second; if (first != last) ++second;

367 
} 
368  
369 
if (first != last) {

370 
if (comp(first, min_result))

371 
min_result = first; 
372 
else if (!comp(first, max_result)) 
373 
max_result = first; 
374 
} 
375  
376 
return std::make_pair(min_result, max_result);

377 
} 
378  
379 
template <typename ForwardIter, class BinaryPredicate> 
380 
std::pair<ForwardIter,ForwardIter> 
381 
basic_last_min_first_max_element(ForwardIter first, ForwardIter last, 
382 
BinaryPredicate comp) 
383 
{ 
384 
if (first == last) return std::make_pair(last,last); 
385  
386 
ForwardIter min_result = first; 
387 
ForwardIter max_result = first; 
388  
389 
ForwardIter second = ++first; 
390 
if (second == last)

391 
return std::make_pair(min_result, max_result);

392  
393 
if (comp(max_result, second))

394 
max_result = second; 
395 
else

396 
min_result = second; 
397  
398 
first = ++second; if (first != last) ++second;

399 
while (second != last) {

400 
if (comp(first, second)) {

401 
if (!comp(min_result, first))

402 
min_result = first; 
403 
if (comp(max_result, second))

404 
max_result = second; 
405 
} else {

406 
if (!comp(min_result, second))

407 
min_result = second; 
408 
if (comp(max_result, first))

409 
max_result = first; 
410 
} 
411 
first = ++second; if (first != last) ++second;

412 
} 
413  
414 
if (first != last) {

415 
if (!comp(min_result, first))

416 
min_result = first; 
417 
else if (comp(max_result, first)) 
418 
max_result = first; 
419 
} 
420  
421 
return std::make_pair(min_result, max_result);

422 
} 
423  
424 
template <typename ForwardIter, class BinaryPredicate> 
425 
std::pair<ForwardIter,ForwardIter> 
426 
basic_last_min_last_max_element(ForwardIter first, ForwardIter last, 
427 
BinaryPredicate comp) 
428 
{ 
429 
if (first == last) return std::make_pair(last,last); 
430  
431 
ForwardIter min_result = first; 
432 
ForwardIter max_result = first; 
433  
434 
ForwardIter second = first; ++second; 
435 
if (second == last)

436 
return std::make_pair(min_result,max_result);

437  
438 
ForwardIter potential_max_result = last; 
439 
if (comp(first, second))

440 
max_result = second; 
441 
else {

442 
min_result = second; 
443 
potential_max_result = second; 
444 
} 
445  
446 
first = ++second; if (first != last) ++second;

447 
while (second != last) {

448 
if (comp(first, second)) {

449 
if (!comp(min_result, first))

450 
min_result = first; 
451 
if (!comp(second, max_result)) {

452 
max_result = second; 
453 
potential_max_result = last; 
454 
} 
455 
} else {

456 
if (!comp(min_result, second))

457 
min_result = second; 
458 
if (!comp(first, max_result)) {

459 
max_result = first; 
460 
potential_max_result = second; 
461 
} 
462 
} 
463 
first = ++second; 
464 
if (first != last) ++second;

465 
} 
466  
467 
if (first != last) {

468 
if (!comp(min_result, first))

469 
min_result = first; 
470 
if (!comp(first, max_result)) {

471 
max_result = first; 
472 
potential_max_result = last; 
473 
} 
474 
} 
475  
476 
if (potential_max_result != last

477 
&& !comp(potential_max_result, max_result)) 
478 
max_result = potential_max_result; 
479  
480 
return std::make_pair(min_result,max_result);

481 
} 
482  
483 
} // namespace detail

484  
485 
template <typename ForwardIter> 
486 
inline std::pair<ForwardIter,ForwardIter>

487 
first_min_first_max_element(ForwardIter first, ForwardIter last) 
488 
{ 
489 
return minmax_element(first, last);

490 
} 
491  
492 
template <typename ForwardIter, class BinaryPredicate> 
493 
inline std::pair<ForwardIter,ForwardIter>

494 
first_min_first_max_element(ForwardIter first, ForwardIter last, 
495 
BinaryPredicate comp) 
496 
{ 
497 
return minmax_element(first, last, comp);

498 
} 
499  
500 
template <typename ForwardIter> 
501 
std::pair<ForwardIter,ForwardIter> 
502 
first_min_last_max_element(ForwardIter first, ForwardIter last) 
503 
{ 
504 
return detail::basic_first_min_last_max_element(first, last,

505 
detail::less_over_iter<ForwardIter>() ); 
506 
} 
507  
508 
template <typename ForwardIter, class BinaryPredicate> 
509 
inline std::pair<ForwardIter,ForwardIter>

510 
first_min_last_max_element(ForwardIter first, ForwardIter last, 
511 
BinaryPredicate comp) 
512 
{ 
513 
return detail::basic_first_min_last_max_element(first, last,

514 
detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 
515 
} 
516  
517 
template <typename ForwardIter> 
518 
std::pair<ForwardIter,ForwardIter> 
519 
last_min_first_max_element(ForwardIter first, ForwardIter last) 
520 
{ 
521 
return detail::basic_last_min_first_max_element(first, last,

522 
detail::less_over_iter<ForwardIter>() ); 
523 
} 
524  
525 
template <typename ForwardIter, class BinaryPredicate> 
526 
inline std::pair<ForwardIter,ForwardIter>

527 
last_min_first_max_element(ForwardIter first, ForwardIter last, 
528 
BinaryPredicate comp) 
529 
{ 
530 
return detail::basic_last_min_first_max_element(first, last,

531 
detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 
532 
} 
533  
534 
template <typename ForwardIter> 
535 
std::pair<ForwardIter,ForwardIter> 
536 
last_min_last_max_element(ForwardIter first, ForwardIter last) 
537 
{ 
538 
return detail::basic_last_min_last_max_element(first, last,

539 
detail::less_over_iter<ForwardIter>() ); 
540 
} 
541  
542 
template <typename ForwardIter, class BinaryPredicate> 
543 
inline std::pair<ForwardIter,ForwardIter>

544 
last_min_last_max_element(ForwardIter first, ForwardIter last, 
545 
BinaryPredicate comp) 
546 
{ 
547 
return detail::basic_last_min_last_max_element(first, last,

548 
detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 
549 
} 
550  
551 
} // namespace boost

552  
553 
#endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP 