Statistics
| Revision:

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 2486 sjacqu01
//  (C) Copyright Herve Bronnimann 2004.
2 2486 sjacqu01
//
3 2486 sjacqu01
// Distributed under the Boost Software License, Version 1.0. (See accompanying
4 2486 sjacqu01
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5 2486 sjacqu01
6 2486 sjacqu01
/*
7 2486 sjacqu01
 Revision history:
8 2486 sjacqu01
   1 July 2004
9 2486 sjacqu01
      Split the code into two headers to lessen dependence on
10 2486 sjacqu01
      Boost.tuple. (Herve)
11 2486 sjacqu01
   26 June 2004
12 2486 sjacqu01
      Added the code for the boost minmax library. (Herve)
13 2486 sjacqu01
*/
14 2486 sjacqu01
15 2486 sjacqu01
#ifndef BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
16 2486 sjacqu01
#define BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
17 2486 sjacqu01
18 2486 sjacqu01
/* PROPOSED STANDARD EXTENSIONS:
19 2486 sjacqu01
 *
20 2486 sjacqu01
 * minmax_element(first, last)
21 2486 sjacqu01
 * Effect: std::make_pair( std::min_element(first, last),
22 2486 sjacqu01
 *                         std::max_element(first, last) );
23 2486 sjacqu01
 *
24 2486 sjacqu01
 * minmax_element(first, last, comp)
25 2486 sjacqu01
 * Effect: std::make_pair( std::min_element(first, last, comp),
26 2486 sjacqu01
 *                         std::max_element(first, last, comp) );
27 2486 sjacqu01
 */
28 2486 sjacqu01
29 2486 sjacqu01
#include <utility> // for std::pair and std::make_pair
30 2486 sjacqu01
31 2486 sjacqu01
namespace boost {
32 2486 sjacqu01
33 2486 sjacqu01
  namespace detail {  // for obtaining a uniform version of minmax_element
34 2486 sjacqu01
    // that compiles with VC++ 6.0 -- avoid the iterator_traits by
35 2486 sjacqu01
    // having comparison object over iterator, not over dereferenced value
36 2486 sjacqu01
37 2486 sjacqu01
    template <typename Iterator>
38 2486 sjacqu01
    struct less_over_iter {
39 2486 sjacqu01
      bool operator()(Iterator const& it1,
40 2486 sjacqu01
                      Iterator const& it2) const { return *it1 < *it2; }
41 2486 sjacqu01
    };
42 2486 sjacqu01
43 2486 sjacqu01
    template <typename Iterator, class BinaryPredicate>
44 2486 sjacqu01
    struct binary_pred_over_iter {
45 2486 sjacqu01
      explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {}
46 2486 sjacqu01
      bool operator()(Iterator const& it1,
47 2486 sjacqu01
                      Iterator const& it2) const { return m_p(*it1, *it2); }
48 2486 sjacqu01
    private:
49 2486 sjacqu01
      BinaryPredicate m_p;
50 2486 sjacqu01
    };
51 2486 sjacqu01
52 2486 sjacqu01
    // common base for the two minmax_element overloads
53 2486 sjacqu01
54 2486 sjacqu01
    template <typename ForwardIter, class Compare >
55 2486 sjacqu01
    std::pair<ForwardIter,ForwardIter>
56 2486 sjacqu01
    basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp)
57 2486 sjacqu01
    {
58 2486 sjacqu01
      if (first == last)
59 2486 sjacqu01
        return std::make_pair(last,last);
60 2486 sjacqu01
61 2486 sjacqu01
      ForwardIter min_result = first;
62 2486 sjacqu01
      ForwardIter max_result = first;
63 2486 sjacqu01
64 2486 sjacqu01
      // if only one element
65 2486 sjacqu01
      ForwardIter second = first; ++second;
66 2486 sjacqu01
      if (second == last)
67 2486 sjacqu01
        return std::make_pair(min_result, max_result);
68 2486 sjacqu01
69 2486 sjacqu01
      // treat first pair separately (only one comparison for first two elements)
70 2486 sjacqu01
      ForwardIter potential_min_result = last;
71 2486 sjacqu01
      if (comp(first, second))
72 2486 sjacqu01
        max_result = second;
73 2486 sjacqu01
      else {
74 2486 sjacqu01
        min_result = second;
75 2486 sjacqu01
        potential_min_result = first;
76 2486 sjacqu01
      }
77 2486 sjacqu01
78 2486 sjacqu01
      // then each element by pairs, with at most 3 comparisons per pair
79 2486 sjacqu01
      first = ++second; if (first != last) ++second;
80 2486 sjacqu01
      while (second != last) {
81 2486 sjacqu01
        if (comp(first, second)) {
82 2486 sjacqu01
          if (comp(first, min_result)) {
83 2486 sjacqu01
            min_result = first;
84 2486 sjacqu01
            potential_min_result = last;
85 2486 sjacqu01
          }
86 2486 sjacqu01
          if (comp(max_result, second))
87 2486 sjacqu01
            max_result = second;
88 2486 sjacqu01
        } else {
89 2486 sjacqu01
          if (comp(second, min_result)) {
90 2486 sjacqu01
            min_result = second;
91 2486 sjacqu01
            potential_min_result = first;
92 2486 sjacqu01
          }
93 2486 sjacqu01
          if (comp(max_result, first))
94 2486 sjacqu01
            max_result = first;
95 2486 sjacqu01
        }
96 2486 sjacqu01
        first = ++second;
97 2486 sjacqu01
        if (first != last) ++second;
98 2486 sjacqu01
      }
99 2486 sjacqu01
100 2486 sjacqu01
      // if odd number of elements, treat last element
101 2486 sjacqu01
      if (first != last) { // odd number of elements
102 2486 sjacqu01
        if (comp(first, min_result)) {
103 2486 sjacqu01
          min_result = first;
104 2486 sjacqu01
          potential_min_result = last;
105 2486 sjacqu01
          }
106 2486 sjacqu01
        else if (comp(max_result, first))
107 2486 sjacqu01
          max_result = first;
108 2486 sjacqu01
      }
109 2486 sjacqu01
110 2486 sjacqu01
      // resolve min_result being incorrect with one extra comparison
111 2486 sjacqu01
      // (in which case potential_min_result is necessarily the correct result)
112 2486 sjacqu01
      if (potential_min_result != last
113 2486 sjacqu01
        && !comp(min_result, potential_min_result))
114 2486 sjacqu01
        min_result = potential_min_result;
115 2486 sjacqu01
116 2486 sjacqu01
      return std::make_pair(min_result,max_result);
117 2486 sjacqu01
    }
118 2486 sjacqu01
119 2486 sjacqu01
  } // namespace detail
120 2486 sjacqu01
121 2486 sjacqu01
  template <typename ForwardIter>
122 2486 sjacqu01
  std::pair<ForwardIter,ForwardIter>
123 2486 sjacqu01
  minmax_element(ForwardIter first, ForwardIter last)
124 2486 sjacqu01
  {
125 2486 sjacqu01
    return detail::basic_minmax_element(first, last,
126 2486 sjacqu01
             detail::less_over_iter<ForwardIter>() );
127 2486 sjacqu01
  }
128 2486 sjacqu01
129 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
130 2486 sjacqu01
  std::pair<ForwardIter,ForwardIter>
131 2486 sjacqu01
  minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
132 2486 sjacqu01
  {
133 2486 sjacqu01
    return detail::basic_minmax_element(first, last,
134 2486 sjacqu01
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
135 2486 sjacqu01
  }
136 2486 sjacqu01
137 2486 sjacqu01
}
138 2486 sjacqu01
139 2486 sjacqu01
/* PROPOSED BOOST EXTENSIONS
140 2486 sjacqu01
 * In the description below, [rfirst,rlast) denotes the reversed range
141 2486 sjacqu01
 * of [first,last). Even though the iterator type of first and last may
142 2486 sjacqu01
 * be only a Forward Iterator, it is possible to explain the semantics
143 2486 sjacqu01
 * by assuming that it is a Bidirectional Iterator. In the sequel,
144 2486 sjacqu01
 * reverse(ForwardIterator&) returns the reverse_iterator adaptor.
145 2486 sjacqu01
 * This is not how the functions would be implemented!
146 2486 sjacqu01
 *
147 2486 sjacqu01
 * first_min_element(first, last)
148 2486 sjacqu01
 * Effect: std::min_element(first, last);
149 2486 sjacqu01
 *
150 2486 sjacqu01
 * first_min_element(first, last, comp)
151 2486 sjacqu01
 * Effect: std::min_element(first, last, comp);
152 2486 sjacqu01
 *
153 2486 sjacqu01
 * last_min_element(first, last)
154 2486 sjacqu01
 * Effect: reverse( std::min_element(reverse(last), reverse(first)) );
155 2486 sjacqu01
 *
156 2486 sjacqu01
 * last_min_element(first, last, comp)
157 2486 sjacqu01
 * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) );
158 2486 sjacqu01
 *
159 2486 sjacqu01
 * first_max_element(first, last)
160 2486 sjacqu01
 * Effect: std::max_element(first, last);
161 2486 sjacqu01
 *
162 2486 sjacqu01
 * first_max_element(first, last, comp)
163 2486 sjacqu01
 * Effect: max_element(first, last);
164 2486 sjacqu01
 *
165 2486 sjacqu01
 * last_max_element(first, last)
166 2486 sjacqu01
 * Effect: reverse( std::max_element(reverse(last), reverse(first)) );
167 2486 sjacqu01
 *
168 2486 sjacqu01
 * last_max_element(first, last, comp)
169 2486 sjacqu01
 * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) );
170 2486 sjacqu01
 *
171 2486 sjacqu01
 * first_min_first_max_element(first, last)
172 2486 sjacqu01
 * Effect: std::make_pair( first_min_element(first, last),
173 2486 sjacqu01
 *                         first_max_element(first, last) );
174 2486 sjacqu01
 *
175 2486 sjacqu01
 * first_min_first_max_element(first, last, comp)
176 2486 sjacqu01
 * Effect: std::make_pair( first_min_element(first, last, comp),
177 2486 sjacqu01
 *                         first_max_element(first, last, comp) );
178 2486 sjacqu01
 *
179 2486 sjacqu01
 * first_min_last_max_element(first, last)
180 2486 sjacqu01
 * Effect: std::make_pair( first_min_element(first, last),
181 2486 sjacqu01
 *                         last_max_element(first, last) );
182 2486 sjacqu01
 *
183 2486 sjacqu01
 * first_min_last_max_element(first, last, comp)
184 2486 sjacqu01
 * Effect: std::make_pair( first_min_element(first, last, comp),
185 2486 sjacqu01
 *                         last_max_element(first, last, comp) );
186 2486 sjacqu01
 *
187 2486 sjacqu01
 * last_min_first_max_element(first, last)
188 2486 sjacqu01
 * Effect: std::make_pair( last_min_element(first, last),
189 2486 sjacqu01
 *                         first_max_element(first, last) );
190 2486 sjacqu01
 *
191 2486 sjacqu01
 * last_min_first_max_element(first, last, comp)
192 2486 sjacqu01
 * Effect: std::make_pair( last_min_element(first, last, comp),
193 2486 sjacqu01
 *                         first_max_element(first, last, comp) );
194 2486 sjacqu01
 *
195 2486 sjacqu01
 * last_min_last_max_element(first, last)
196 2486 sjacqu01
 * Effect: std::make_pair( last_min_element(first, last),
197 2486 sjacqu01
 *                         last_max_element(first, last) );
198 2486 sjacqu01
 *
199 2486 sjacqu01
 * last_min_last_max_element(first, last, comp)
200 2486 sjacqu01
 * Effect: std::make_pair( last_min_element(first, last, comp),
201 2486 sjacqu01
 *                         last_max_element(first, last, comp) );
202 2486 sjacqu01
 */
203 2486 sjacqu01
204 2486 sjacqu01
namespace boost {
205 2486 sjacqu01
206 2486 sjacqu01
  // Min_element and max_element variants
207 2486 sjacqu01
208 2486 sjacqu01
  namespace detail {  // common base for the overloads
209 2486 sjacqu01
210 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
211 2486 sjacqu01
  ForwardIter
212 2486 sjacqu01
  basic_first_min_element(ForwardIter first, ForwardIter last,
213 2486 sjacqu01
                          BinaryPredicate comp)
214 2486 sjacqu01
  {
215 2486 sjacqu01
    if (first == last) return last;
216 2486 sjacqu01
    ForwardIter min_result = first;
217 2486 sjacqu01
    while (++first != last)
218 2486 sjacqu01
      if (comp(first, min_result))
219 2486 sjacqu01
        min_result = first;
220 2486 sjacqu01
    return min_result;
221 2486 sjacqu01
  }
222 2486 sjacqu01
223 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
224 2486 sjacqu01
  ForwardIter
225 2486 sjacqu01
  basic_last_min_element(ForwardIter first, ForwardIter last,
226 2486 sjacqu01
                         BinaryPredicate comp)
227 2486 sjacqu01
  {
228 2486 sjacqu01
    if (first == last) return last;
229 2486 sjacqu01
    ForwardIter min_result = first;
230 2486 sjacqu01
    while (++first != last)
231 2486 sjacqu01
      if (!comp(min_result, first))
232 2486 sjacqu01
        min_result = first;
233 2486 sjacqu01
    return min_result;
234 2486 sjacqu01
  }
235 2486 sjacqu01
236 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
237 2486 sjacqu01
  ForwardIter
238 2486 sjacqu01
  basic_first_max_element(ForwardIter first, ForwardIter last,
239 2486 sjacqu01
                          BinaryPredicate comp)
240 2486 sjacqu01
  {
241 2486 sjacqu01
    if (first == last) return last;
242 2486 sjacqu01
    ForwardIter max_result = first;
243 2486 sjacqu01
    while (++first != last)
244 2486 sjacqu01
      if (comp(max_result, first))
245 2486 sjacqu01
        max_result = first;
246 2486 sjacqu01
    return max_result;
247 2486 sjacqu01
  }
248 2486 sjacqu01
249 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
250 2486 sjacqu01
  ForwardIter
251 2486 sjacqu01
  basic_last_max_element(ForwardIter first, ForwardIter last,
252 2486 sjacqu01
                         BinaryPredicate comp)
253 2486 sjacqu01
  {
254 2486 sjacqu01
    if (first == last) return last;
255 2486 sjacqu01
    ForwardIter max_result = first;
256 2486 sjacqu01
    while (++first != last)
257 2486 sjacqu01
      if (!comp(first, max_result))
258 2486 sjacqu01
        max_result = first;
259 2486 sjacqu01
    return max_result;
260 2486 sjacqu01
  }
261 2486 sjacqu01
262 2486 sjacqu01
  } // namespace detail
263 2486 sjacqu01
264 2486 sjacqu01
  template <typename ForwardIter>
265 2486 sjacqu01
  ForwardIter
266 2486 sjacqu01
  first_min_element(ForwardIter first, ForwardIter last)
267 2486 sjacqu01
  {
268 2486 sjacqu01
    return detail::basic_first_min_element(first, last,
269 2486 sjacqu01
             detail::less_over_iter<ForwardIter>() );
270 2486 sjacqu01
  }
271 2486 sjacqu01
272 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
273 2486 sjacqu01
  ForwardIter
274 2486 sjacqu01
  first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
275 2486 sjacqu01
  {
276 2486 sjacqu01
    return detail::basic_first_min_element(first, last,
277 2486 sjacqu01
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
278 2486 sjacqu01
  }
279 2486 sjacqu01
280 2486 sjacqu01
  template <typename ForwardIter>
281 2486 sjacqu01
  ForwardIter
282 2486 sjacqu01
  last_min_element(ForwardIter first, ForwardIter last)
283 2486 sjacqu01
  {
284 2486 sjacqu01
    return detail::basic_last_min_element(first, last,
285 2486 sjacqu01
             detail::less_over_iter<ForwardIter>() );
286 2486 sjacqu01
  }
287 2486 sjacqu01
288 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
289 2486 sjacqu01
  ForwardIter
290 2486 sjacqu01
  last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
291 2486 sjacqu01
  {
292 2486 sjacqu01
    return detail::basic_last_min_element(first, last,
293 2486 sjacqu01
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
294 2486 sjacqu01
  }
295 2486 sjacqu01
296 2486 sjacqu01
  template <typename ForwardIter>
297 2486 sjacqu01
  ForwardIter
298 2486 sjacqu01
  first_max_element(ForwardIter first, ForwardIter last)
299 2486 sjacqu01
  {
300 2486 sjacqu01
    return detail::basic_first_max_element(first, last,
301 2486 sjacqu01
             detail::less_over_iter<ForwardIter>() );
302 2486 sjacqu01
  }
303 2486 sjacqu01
304 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
305 2486 sjacqu01
  ForwardIter
306 2486 sjacqu01
  first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
307 2486 sjacqu01
  {
308 2486 sjacqu01
    return detail::basic_first_max_element(first, last,
309 2486 sjacqu01
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
310 2486 sjacqu01
  }
311 2486 sjacqu01
312 2486 sjacqu01
  template <typename ForwardIter>
313 2486 sjacqu01
  ForwardIter
314 2486 sjacqu01
  last_max_element(ForwardIter first, ForwardIter last)
315 2486 sjacqu01
  {
316 2486 sjacqu01
    return detail::basic_last_max_element(first, last,
317 2486 sjacqu01
             detail::less_over_iter<ForwardIter>() );
318 2486 sjacqu01
  }
319 2486 sjacqu01
320 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
321 2486 sjacqu01
  ForwardIter
322 2486 sjacqu01
  last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
323 2486 sjacqu01
  {
324 2486 sjacqu01
    return detail::basic_last_max_element(first, last,
325 2486 sjacqu01
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
326 2486 sjacqu01
  }
327 2486 sjacqu01
328 2486 sjacqu01
329 2486 sjacqu01
  // Minmax_element variants -- comments removed
330 2486 sjacqu01
331 2486 sjacqu01
  namespace detail {
332 2486 sjacqu01
333 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
334 2486 sjacqu01
  std::pair<ForwardIter,ForwardIter>
335 2486 sjacqu01
  basic_first_min_last_max_element(ForwardIter first, ForwardIter last,
336 2486 sjacqu01
                                   BinaryPredicate comp)
337 2486 sjacqu01
  {
338 2486 sjacqu01
    if (first == last)
339 2486 sjacqu01
      return std::make_pair(last,last);
340 2486 sjacqu01
341 2486 sjacqu01
    ForwardIter min_result = first;
342 2486 sjacqu01
    ForwardIter max_result = first;
343 2486 sjacqu01
344 2486 sjacqu01
    ForwardIter second = ++first;
345 2486 sjacqu01
    if (second == last)
346 2486 sjacqu01
      return std::make_pair(min_result, max_result);
347 2486 sjacqu01
348 2486 sjacqu01
    if (comp(second, min_result))
349 2486 sjacqu01
      min_result = second;
350 2486 sjacqu01
    else
351 2486 sjacqu01
      max_result = second;
352 2486 sjacqu01
353 2486 sjacqu01
    first = ++second; if (first != last) ++second;
354 2486 sjacqu01
    while (second != last) {
355 2486 sjacqu01
      if (!comp(second, first)) {
356 2486 sjacqu01
        if (comp(first, min_result))
357 2486 sjacqu01
                 min_result = first;
358 2486 sjacqu01
        if (!comp(second, max_result))
359 2486 sjacqu01
          max_result = second;
360 2486 sjacqu01
      } else {
361 2486 sjacqu01
        if (comp(second, min_result))
362 2486 sjacqu01
          min_result = second;
363 2486 sjacqu01
        if (!comp(first, max_result))
364 2486 sjacqu01
              max_result = first;
365 2486 sjacqu01
      }
366 2486 sjacqu01
      first = ++second; if (first != last) ++second;
367 2486 sjacqu01
    }
368 2486 sjacqu01
369 2486 sjacqu01
    if (first != last) {
370 2486 sjacqu01
      if (comp(first, min_result))
371 2486 sjacqu01
         min_result = first;
372 2486 sjacqu01
      else if (!comp(first, max_result))
373 2486 sjacqu01
               max_result = first;
374 2486 sjacqu01
    }
375 2486 sjacqu01
376 2486 sjacqu01
    return std::make_pair(min_result, max_result);
377 2486 sjacqu01
  }
378 2486 sjacqu01
379 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
380 2486 sjacqu01
  std::pair<ForwardIter,ForwardIter>
381 2486 sjacqu01
  basic_last_min_first_max_element(ForwardIter first, ForwardIter last,
382 2486 sjacqu01
                                   BinaryPredicate comp)
383 2486 sjacqu01
  {
384 2486 sjacqu01
    if (first == last) return std::make_pair(last,last);
385 2486 sjacqu01
386 2486 sjacqu01
    ForwardIter min_result = first;
387 2486 sjacqu01
    ForwardIter max_result = first;
388 2486 sjacqu01
389 2486 sjacqu01
    ForwardIter second = ++first;
390 2486 sjacqu01
    if (second == last)
391 2486 sjacqu01
      return std::make_pair(min_result, max_result);
392 2486 sjacqu01
393 2486 sjacqu01
    if (comp(max_result, second))
394 2486 sjacqu01
      max_result = second;
395 2486 sjacqu01
    else
396 2486 sjacqu01
      min_result = second;
397 2486 sjacqu01
398 2486 sjacqu01
    first = ++second; if (first != last) ++second;
399 2486 sjacqu01
    while (second != last)  {
400 2486 sjacqu01
      if (comp(first, second)) {
401 2486 sjacqu01
        if (!comp(min_result, first))
402 2486 sjacqu01
          min_result = first;
403 2486 sjacqu01
        if (comp(max_result, second))
404 2486 sjacqu01
          max_result = second;
405 2486 sjacqu01
      } else {
406 2486 sjacqu01
        if (!comp(min_result, second))
407 2486 sjacqu01
          min_result = second;
408 2486 sjacqu01
        if (comp(max_result, first))
409 2486 sjacqu01
          max_result = first;
410 2486 sjacqu01
      }
411 2486 sjacqu01
      first = ++second; if (first != last) ++second;
412 2486 sjacqu01
    }
413 2486 sjacqu01
414 2486 sjacqu01
    if (first != last) {
415 2486 sjacqu01
      if (!comp(min_result, first))
416 2486 sjacqu01
        min_result = first;
417 2486 sjacqu01
      else if (comp(max_result, first))
418 2486 sjacqu01
        max_result = first;
419 2486 sjacqu01
    }
420 2486 sjacqu01
421 2486 sjacqu01
    return std::make_pair(min_result, max_result);
422 2486 sjacqu01
  }
423 2486 sjacqu01
424 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
425 2486 sjacqu01
  std::pair<ForwardIter,ForwardIter>
426 2486 sjacqu01
  basic_last_min_last_max_element(ForwardIter first, ForwardIter last,
427 2486 sjacqu01
                                  BinaryPredicate comp)
428 2486 sjacqu01
  {
429 2486 sjacqu01
    if (first == last) return std::make_pair(last,last);
430 2486 sjacqu01
431 2486 sjacqu01
    ForwardIter min_result = first;
432 2486 sjacqu01
    ForwardIter max_result = first;
433 2486 sjacqu01
434 2486 sjacqu01
    ForwardIter second = first; ++second;
435 2486 sjacqu01
    if (second == last)
436 2486 sjacqu01
      return std::make_pair(min_result,max_result);
437 2486 sjacqu01
438 2486 sjacqu01
    ForwardIter potential_max_result = last;
439 2486 sjacqu01
    if (comp(first, second))
440 2486 sjacqu01
      max_result = second;
441 2486 sjacqu01
    else {
442 2486 sjacqu01
      min_result = second;
443 2486 sjacqu01
      potential_max_result = second;
444 2486 sjacqu01
    }
445 2486 sjacqu01
446 2486 sjacqu01
    first = ++second; if (first != last) ++second;
447 2486 sjacqu01
    while (second != last) {
448 2486 sjacqu01
      if (comp(first, second)) {
449 2486 sjacqu01
        if (!comp(min_result, first))
450 2486 sjacqu01
          min_result = first;
451 2486 sjacqu01
        if (!comp(second, max_result)) {
452 2486 sjacqu01
          max_result = second;
453 2486 sjacqu01
          potential_max_result = last;
454 2486 sjacqu01
        }
455 2486 sjacqu01
      } else {
456 2486 sjacqu01
        if (!comp(min_result, second))
457 2486 sjacqu01
          min_result = second;
458 2486 sjacqu01
        if (!comp(first, max_result)) {
459 2486 sjacqu01
          max_result = first;
460 2486 sjacqu01
          potential_max_result = second;
461 2486 sjacqu01
        }
462 2486 sjacqu01
      }
463 2486 sjacqu01
      first = ++second;
464 2486 sjacqu01
      if (first != last) ++second;
465 2486 sjacqu01
    }
466 2486 sjacqu01
467 2486 sjacqu01
    if (first != last) {
468 2486 sjacqu01
      if (!comp(min_result, first))
469 2486 sjacqu01
        min_result = first;
470 2486 sjacqu01
      if (!comp(first, max_result)) {
471 2486 sjacqu01
        max_result = first;
472 2486 sjacqu01
               potential_max_result = last;
473 2486 sjacqu01
      }
474 2486 sjacqu01
    }
475 2486 sjacqu01
476 2486 sjacqu01
    if (potential_max_result != last
477 2486 sjacqu01
        && !comp(potential_max_result, max_result))
478 2486 sjacqu01
      max_result = potential_max_result;
479 2486 sjacqu01
480 2486 sjacqu01
    return std::make_pair(min_result,max_result);
481 2486 sjacqu01
  }
482 2486 sjacqu01
483 2486 sjacqu01
  } // namespace detail
484 2486 sjacqu01
485 2486 sjacqu01
  template <typename ForwardIter>
486 2486 sjacqu01
  inline std::pair<ForwardIter,ForwardIter>
487 2486 sjacqu01
  first_min_first_max_element(ForwardIter first, ForwardIter last)
488 2486 sjacqu01
  {
489 2486 sjacqu01
    return minmax_element(first, last);
490 2486 sjacqu01
  }
491 2486 sjacqu01
492 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
493 2486 sjacqu01
  inline std::pair<ForwardIter,ForwardIter>
494 2486 sjacqu01
  first_min_first_max_element(ForwardIter first, ForwardIter last,
495 2486 sjacqu01
                              BinaryPredicate comp)
496 2486 sjacqu01
  {
497 2486 sjacqu01
    return minmax_element(first, last, comp);
498 2486 sjacqu01
  }
499 2486 sjacqu01
500 2486 sjacqu01
  template <typename ForwardIter>
501 2486 sjacqu01
  std::pair<ForwardIter,ForwardIter>
502 2486 sjacqu01
  first_min_last_max_element(ForwardIter first, ForwardIter last)
503 2486 sjacqu01
  {
504 2486 sjacqu01
    return detail::basic_first_min_last_max_element(first, last,
505 2486 sjacqu01
             detail::less_over_iter<ForwardIter>() );
506 2486 sjacqu01
  }
507 2486 sjacqu01
508 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
509 2486 sjacqu01
  inline std::pair<ForwardIter,ForwardIter>
510 2486 sjacqu01
  first_min_last_max_element(ForwardIter first, ForwardIter last,
511 2486 sjacqu01
                              BinaryPredicate comp)
512 2486 sjacqu01
  {
513 2486 sjacqu01
    return detail::basic_first_min_last_max_element(first, last,
514 2486 sjacqu01
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
515 2486 sjacqu01
  }
516 2486 sjacqu01
517 2486 sjacqu01
  template <typename ForwardIter>
518 2486 sjacqu01
  std::pair<ForwardIter,ForwardIter>
519 2486 sjacqu01
  last_min_first_max_element(ForwardIter first, ForwardIter last)
520 2486 sjacqu01
  {
521 2486 sjacqu01
    return detail::basic_last_min_first_max_element(first, last,
522 2486 sjacqu01
             detail::less_over_iter<ForwardIter>() );
523 2486 sjacqu01
  }
524 2486 sjacqu01
525 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
526 2486 sjacqu01
  inline std::pair<ForwardIter,ForwardIter>
527 2486 sjacqu01
  last_min_first_max_element(ForwardIter first, ForwardIter last,
528 2486 sjacqu01
                              BinaryPredicate comp)
529 2486 sjacqu01
  {
530 2486 sjacqu01
    return detail::basic_last_min_first_max_element(first, last,
531 2486 sjacqu01
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
532 2486 sjacqu01
  }
533 2486 sjacqu01
534 2486 sjacqu01
  template <typename ForwardIter>
535 2486 sjacqu01
  std::pair<ForwardIter,ForwardIter>
536 2486 sjacqu01
  last_min_last_max_element(ForwardIter first, ForwardIter last)
537 2486 sjacqu01
  {
538 2486 sjacqu01
    return detail::basic_last_min_last_max_element(first, last,
539 2486 sjacqu01
             detail::less_over_iter<ForwardIter>() );
540 2486 sjacqu01
  }
541 2486 sjacqu01
542 2486 sjacqu01
  template <typename ForwardIter, class BinaryPredicate>
543 2486 sjacqu01
  inline std::pair<ForwardIter,ForwardIter>
544 2486 sjacqu01
  last_min_last_max_element(ForwardIter first, ForwardIter last,
545 2486 sjacqu01
                              BinaryPredicate comp)
546 2486 sjacqu01
  {
547 2486 sjacqu01
    return detail::basic_last_min_last_max_element(first, last,
548 2486 sjacqu01
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
549 2486 sjacqu01
  }
550 2486 sjacqu01
551 2486 sjacqu01
} // namespace boost
552 2486 sjacqu01
553 2486 sjacqu01
#endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP