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
//  (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