VOP_FSYNC.9: Missing comma
[dragonfly.git] / contrib / gcc-4.7 / libstdc++-v3 / include / bits / stl_algo.h
1 // Algorithm implementation -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
4 // 2010, 2011
5 // Free Software Foundation, Inc.
6 //
7 // This file is part of the GNU ISO C++ Library.  This library is free
8 // software; you can redistribute it and/or modify it under the
9 // terms of the GNU General Public License as published by the
10 // Free Software Foundation; either version 3, or (at your option)
11 // any later version.
12
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 // GNU General Public License for more details.
17
18 // Under Section 7 of GPL version 3, you are granted additional
19 // permissions described in the GCC Runtime Library Exception, version
20 // 3.1, as published by the Free Software Foundation.
21
22 // You should have received a copy of the GNU General Public License and
23 // a copy of the GCC Runtime Library Exception along with this program;
24 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
25 // <http://www.gnu.org/licenses/>.
26
27 /*
28  *
29  * Copyright (c) 1994
30  * Hewlett-Packard Company
31  *
32  * Permission to use, copy, modify, distribute and sell this software
33  * and its documentation for any purpose is hereby granted without fee,
34  * provided that the above copyright notice appear in all copies and
35  * that both that copyright notice and this permission notice appear
36  * in supporting documentation.  Hewlett-Packard Company makes no
37  * representations about the suitability of this software for any
38  * purpose.  It is provided "as is" without express or implied warranty.
39  *
40  *
41  * Copyright (c) 1996
42  * Silicon Graphics Computer Systems, Inc.
43  *
44  * Permission to use, copy, modify, distribute and sell this software
45  * and its documentation for any purpose is hereby granted without fee,
46  * provided that the above copyright notice appear in all copies and
47  * that both that copyright notice and this permission notice appear
48  * in supporting documentation.  Silicon Graphics makes no
49  * representations about the suitability of this software for any
50  * purpose.  It is provided "as is" without express or implied warranty.
51  */
52
53 /** @file bits/stl_algo.h
54  *  This is an internal header file, included by other library headers.
55  *  Do not attempt to use it directly. @headername{algorithm}
56  */
57
58 #ifndef _STL_ALGO_H
59 #define _STL_ALGO_H 1
60
61 #include <cstdlib>             // for rand
62 #include <bits/algorithmfwd.h>
63 #include <bits/stl_heap.h>
64 #include <bits/stl_tempbuf.h>  // for _Temporary_buffer
65
66 #ifdef __GXX_EXPERIMENTAL_CXX0X__
67 #include <random>     // for std::uniform_int_distribution
68 #include <functional> // for std::bind
69 #endif
70
71 // See concept_check.h for the __glibcxx_*_requires macros.
72
73 namespace std _GLIBCXX_VISIBILITY(default)
74 {
75 _GLIBCXX_BEGIN_NAMESPACE_VERSION
76
77   /// Swaps the median value of *__a, *__b and *__c to *__a
78   template<typename _Iterator>
79     void
80     __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c)
81     {
82       // concept requirements
83       __glibcxx_function_requires(_LessThanComparableConcept<
84             typename iterator_traits<_Iterator>::value_type>)
85
86       if (*__a < *__b)
87         {
88           if (*__b < *__c)
89             std::iter_swap(__a, __b);
90           else if (*__a < *__c)
91             std::iter_swap(__a, __c);
92         }
93       else if (*__a < *__c)
94         return;
95       else if (*__b < *__c)
96         std::iter_swap(__a, __c);
97       else
98         std::iter_swap(__a, __b);
99     }
100
101   /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
102   template<typename _Iterator, typename _Compare>
103     void
104     __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c,
105                         _Compare __comp)
106     {
107       // concept requirements
108       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
109             typename iterator_traits<_Iterator>::value_type,
110             typename iterator_traits<_Iterator>::value_type>)
111
112       if (__comp(*__a, *__b))
113         {
114           if (__comp(*__b, *__c))
115             std::iter_swap(__a, __b);
116           else if (__comp(*__a, *__c))
117             std::iter_swap(__a, __c);
118         }
119       else if (__comp(*__a, *__c))
120         return;
121       else if (__comp(*__b, *__c))
122         std::iter_swap(__a, __c);
123       else
124         std::iter_swap(__a, __b);
125     }
126
127   // for_each
128
129   /// This is an overload used by find() for the Input Iterator case.
130   template<typename _InputIterator, typename _Tp>
131     inline _InputIterator
132     __find(_InputIterator __first, _InputIterator __last,
133            const _Tp& __val, input_iterator_tag)
134     {
135       while (__first != __last && !(*__first == __val))
136         ++__first;
137       return __first;
138     }
139
140   /// This is an overload used by find_if() for the Input Iterator case.
141   template<typename _InputIterator, typename _Predicate>
142     inline _InputIterator
143     __find_if(_InputIterator __first, _InputIterator __last,
144               _Predicate __pred, input_iterator_tag)
145     {
146       while (__first != __last && !bool(__pred(*__first)))
147         ++__first;
148       return __first;
149     }
150
151   /// This is an overload used by find() for the RAI case.
152   template<typename _RandomAccessIterator, typename _Tp>
153     _RandomAccessIterator
154     __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
155            const _Tp& __val, random_access_iterator_tag)
156     {
157       typename iterator_traits<_RandomAccessIterator>::difference_type
158         __trip_count = (__last - __first) >> 2;
159
160       for (; __trip_count > 0; --__trip_count)
161         {
162           if (*__first == __val)
163             return __first;
164           ++__first;
165
166           if (*__first == __val)
167             return __first;
168           ++__first;
169
170           if (*__first == __val)
171             return __first;
172           ++__first;
173
174           if (*__first == __val)
175             return __first;
176           ++__first;
177         }
178
179       switch (__last - __first)
180         {
181         case 3:
182           if (*__first == __val)
183             return __first;
184           ++__first;
185         case 2:
186           if (*__first == __val)
187             return __first;
188           ++__first;
189         case 1:
190           if (*__first == __val)
191             return __first;
192           ++__first;
193         case 0:
194         default:
195           return __last;
196         }
197     }
198
199   /// This is an overload used by find_if() for the RAI case.
200   template<typename _RandomAccessIterator, typename _Predicate>
201     _RandomAccessIterator
202     __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
203               _Predicate __pred, random_access_iterator_tag)
204     {
205       typename iterator_traits<_RandomAccessIterator>::difference_type
206         __trip_count = (__last - __first) >> 2;
207
208       for (; __trip_count > 0; --__trip_count)
209         {
210           if (__pred(*__first))
211             return __first;
212           ++__first;
213
214           if (__pred(*__first))
215             return __first;
216           ++__first;
217
218           if (__pred(*__first))
219             return __first;
220           ++__first;
221
222           if (__pred(*__first))
223             return __first;
224           ++__first;
225         }
226
227       switch (__last - __first)
228         {
229         case 3:
230           if (__pred(*__first))
231             return __first;
232           ++__first;
233         case 2:
234           if (__pred(*__first))
235             return __first;
236           ++__first;
237         case 1:
238           if (__pred(*__first))
239             return __first;
240           ++__first;
241         case 0:
242         default:
243           return __last;
244         }
245     }
246
247   /// This is an overload used by find_if_not() for the Input Iterator case.
248   template<typename _InputIterator, typename _Predicate>
249     inline _InputIterator
250     __find_if_not(_InputIterator __first, _InputIterator __last,
251                   _Predicate __pred, input_iterator_tag)
252     {
253       while (__first != __last && bool(__pred(*__first)))
254         ++__first;
255       return __first;
256     }
257
258   /// This is an overload used by find_if_not() for the RAI case.
259   template<typename _RandomAccessIterator, typename _Predicate>
260     _RandomAccessIterator
261     __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
262                   _Predicate __pred, random_access_iterator_tag)
263     {
264       typename iterator_traits<_RandomAccessIterator>::difference_type
265         __trip_count = (__last - __first) >> 2;
266
267       for (; __trip_count > 0; --__trip_count)
268         {
269           if (!bool(__pred(*__first)))
270             return __first;
271           ++__first;
272
273           if (!bool(__pred(*__first)))
274             return __first;
275           ++__first;
276
277           if (!bool(__pred(*__first)))
278             return __first;
279           ++__first;
280
281           if (!bool(__pred(*__first)))
282             return __first;
283           ++__first;
284         }
285
286       switch (__last - __first)
287         {
288         case 3:
289           if (!bool(__pred(*__first)))
290             return __first;
291           ++__first;
292         case 2:
293           if (!bool(__pred(*__first)))
294             return __first;
295           ++__first;
296         case 1:
297           if (!bool(__pred(*__first)))
298             return __first;
299           ++__first;
300         case 0:
301         default:
302           return __last;
303         }
304     }
305
306   /// Provided for stable_partition to use.
307   template<typename _InputIterator, typename _Predicate>
308     inline _InputIterator
309     __find_if_not(_InputIterator __first, _InputIterator __last,
310                   _Predicate __pred)
311     {
312       return std::__find_if_not(__first, __last, __pred,
313                                 std::__iterator_category(__first));
314     }
315
316   /// Like find_if_not(), but uses and updates a count of the
317   /// remaining range length instead of comparing against an end
318   /// iterator.
319   template<typename _InputIterator, typename _Predicate, typename _Distance>
320     _InputIterator
321     __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
322     {
323       for (; __len; --__len, ++__first)
324         if (!bool(__pred(*__first)))
325           break;
326       return __first;
327     }
328
329   // set_difference
330   // set_intersection
331   // set_symmetric_difference
332   // set_union
333   // for_each
334   // find
335   // find_if
336   // find_first_of
337   // adjacent_find
338   // count
339   // count_if
340   // search
341
342   /**
343    *  This is an uglified
344    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
345    *  overloaded for forward iterators.
346   */
347   template<typename _ForwardIterator, typename _Integer, typename _Tp>
348     _ForwardIterator
349     __search_n(_ForwardIterator __first, _ForwardIterator __last,
350                _Integer __count, const _Tp& __val,
351                std::forward_iterator_tag)
352     {
353       __first = _GLIBCXX_STD_A::find(__first, __last, __val);
354       while (__first != __last)
355         {
356           typename iterator_traits<_ForwardIterator>::difference_type
357             __n = __count;
358           _ForwardIterator __i = __first;
359           ++__i;
360           while (__i != __last && __n != 1 && *__i == __val)
361             {
362               ++__i;
363               --__n;
364             }
365           if (__n == 1)
366             return __first;
367           if (__i == __last)
368             return __last;
369           __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
370         }
371       return __last;
372     }
373
374   /**
375    *  This is an uglified
376    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
377    *  overloaded for random access iterators.
378   */
379   template<typename _RandomAccessIter, typename _Integer, typename _Tp>
380     _RandomAccessIter
381     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
382                _Integer __count, const _Tp& __val, 
383                std::random_access_iterator_tag)
384     {
385       
386       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
387         _DistanceType;
388
389       _DistanceType __tailSize = __last - __first;
390       const _DistanceType __pattSize = __count;
391
392       if (__tailSize < __pattSize)
393         return __last;
394
395       const _DistanceType __skipOffset = __pattSize - 1;
396       _RandomAccessIter __lookAhead = __first + __skipOffset;
397       __tailSize -= __pattSize;
398
399       while (1) // the main loop...
400         {
401           // __lookAhead here is always pointing to the last element of next 
402           // possible match.
403           while (!(*__lookAhead == __val)) // the skip loop...
404             {
405               if (__tailSize < __pattSize)
406                 return __last;  // Failure
407               __lookAhead += __pattSize;
408               __tailSize -= __pattSize;
409             }
410           _DistanceType __remainder = __skipOffset;
411           for (_RandomAccessIter __backTrack = __lookAhead - 1; 
412                *__backTrack == __val; --__backTrack)
413             {
414               if (--__remainder == 0)
415                 return (__lookAhead - __skipOffset); // Success
416             }
417           if (__remainder > __tailSize)
418             return __last; // Failure
419           __lookAhead += __remainder;
420           __tailSize -= __remainder;
421         }
422     }
423
424   // search_n
425
426   /**
427    *  This is an uglified
428    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
429    *           _BinaryPredicate)
430    *  overloaded for forward iterators.
431   */
432   template<typename _ForwardIterator, typename _Integer, typename _Tp,
433            typename _BinaryPredicate>
434     _ForwardIterator
435     __search_n(_ForwardIterator __first, _ForwardIterator __last,
436                _Integer __count, const _Tp& __val,
437                _BinaryPredicate __binary_pred, std::forward_iterator_tag)
438     {
439       while (__first != __last && !bool(__binary_pred(*__first, __val)))
440         ++__first;
441
442       while (__first != __last)
443         {
444           typename iterator_traits<_ForwardIterator>::difference_type
445             __n = __count;
446           _ForwardIterator __i = __first;
447           ++__i;
448           while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
449             {
450               ++__i;
451               --__n;
452             }
453           if (__n == 1)
454             return __first;
455           if (__i == __last)
456             return __last;
457           __first = ++__i;
458           while (__first != __last
459                  && !bool(__binary_pred(*__first, __val)))
460             ++__first;
461         }
462       return __last;
463     }
464
465   /**
466    *  This is an uglified
467    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
468    *           _BinaryPredicate)
469    *  overloaded for random access iterators.
470   */
471   template<typename _RandomAccessIter, typename _Integer, typename _Tp,
472            typename _BinaryPredicate>
473     _RandomAccessIter
474     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
475                _Integer __count, const _Tp& __val,
476                _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
477     {
478       
479       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
480         _DistanceType;
481
482       _DistanceType __tailSize = __last - __first;
483       const _DistanceType __pattSize = __count;
484
485       if (__tailSize < __pattSize)
486         return __last;
487
488       const _DistanceType __skipOffset = __pattSize - 1;
489       _RandomAccessIter __lookAhead = __first + __skipOffset;
490       __tailSize -= __pattSize;
491
492       while (1) // the main loop...
493         {
494           // __lookAhead here is always pointing to the last element of next 
495           // possible match.
496           while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop...
497             {
498               if (__tailSize < __pattSize)
499                 return __last;  // Failure
500               __lookAhead += __pattSize;
501               __tailSize -= __pattSize;
502             }
503           _DistanceType __remainder = __skipOffset;
504           for (_RandomAccessIter __backTrack = __lookAhead - 1; 
505                __binary_pred(*__backTrack, __val); --__backTrack)
506             {
507               if (--__remainder == 0)
508                 return (__lookAhead - __skipOffset); // Success
509             }
510           if (__remainder > __tailSize)
511             return __last; // Failure
512           __lookAhead += __remainder;
513           __tailSize -= __remainder;
514         }
515     }
516
517   // find_end for forward iterators.
518   template<typename _ForwardIterator1, typename _ForwardIterator2>
519     _ForwardIterator1
520     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
521                _ForwardIterator2 __first2, _ForwardIterator2 __last2,
522                forward_iterator_tag, forward_iterator_tag)
523     {
524       if (__first2 == __last2)
525         return __last1;
526       else
527         {
528           _ForwardIterator1 __result = __last1;
529           while (1)
530             {
531               _ForwardIterator1 __new_result
532                 = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
533               if (__new_result == __last1)
534                 return __result;
535               else
536                 {
537                   __result = __new_result;
538                   __first1 = __new_result;
539                   ++__first1;
540                 }
541             }
542         }
543     }
544
545   template<typename _ForwardIterator1, typename _ForwardIterator2,
546            typename _BinaryPredicate>
547     _ForwardIterator1
548     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
549                _ForwardIterator2 __first2, _ForwardIterator2 __last2,
550                forward_iterator_tag, forward_iterator_tag,
551                _BinaryPredicate __comp)
552     {
553       if (__first2 == __last2)
554         return __last1;
555       else
556         {
557           _ForwardIterator1 __result = __last1;
558           while (1)
559             {
560               _ForwardIterator1 __new_result
561                 = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
562                                          __last2, __comp);
563               if (__new_result == __last1)
564                 return __result;
565               else
566                 {
567                   __result = __new_result;
568                   __first1 = __new_result;
569                   ++__first1;
570                 }
571             }
572         }
573     }
574
575   // find_end for bidirectional iterators (much faster).
576   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
577     _BidirectionalIterator1
578     __find_end(_BidirectionalIterator1 __first1,
579                _BidirectionalIterator1 __last1,
580                _BidirectionalIterator2 __first2,
581                _BidirectionalIterator2 __last2,
582                bidirectional_iterator_tag, bidirectional_iterator_tag)
583     {
584       // concept requirements
585       __glibcxx_function_requires(_BidirectionalIteratorConcept<
586                                   _BidirectionalIterator1>)
587       __glibcxx_function_requires(_BidirectionalIteratorConcept<
588                                   _BidirectionalIterator2>)
589
590       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
591       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
592
593       _RevIterator1 __rlast1(__first1);
594       _RevIterator2 __rlast2(__first2);
595       _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
596                                                        __rlast1,
597                                                        _RevIterator2(__last2),
598                                                        __rlast2);
599
600       if (__rresult == __rlast1)
601         return __last1;
602       else
603         {
604           _BidirectionalIterator1 __result = __rresult.base();
605           std::advance(__result, -std::distance(__first2, __last2));
606           return __result;
607         }
608     }
609
610   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
611            typename _BinaryPredicate>
612     _BidirectionalIterator1
613     __find_end(_BidirectionalIterator1 __first1,
614                _BidirectionalIterator1 __last1,
615                _BidirectionalIterator2 __first2,
616                _BidirectionalIterator2 __last2,
617                bidirectional_iterator_tag, bidirectional_iterator_tag,
618                _BinaryPredicate __comp)
619     {
620       // concept requirements
621       __glibcxx_function_requires(_BidirectionalIteratorConcept<
622                                   _BidirectionalIterator1>)
623       __glibcxx_function_requires(_BidirectionalIteratorConcept<
624                                   _BidirectionalIterator2>)
625
626       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
627       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
628
629       _RevIterator1 __rlast1(__first1);
630       _RevIterator2 __rlast2(__first2);
631       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
632                                             _RevIterator2(__last2), __rlast2,
633                                             __comp);
634
635       if (__rresult == __rlast1)
636         return __last1;
637       else
638         {
639           _BidirectionalIterator1 __result = __rresult.base();
640           std::advance(__result, -std::distance(__first2, __last2));
641           return __result;
642         }
643     }
644
645   /**
646    *  @brief  Find last matching subsequence in a sequence.
647    *  @ingroup non_mutating_algorithms
648    *  @param  __first1  Start of range to search.
649    *  @param  __last1   End of range to search.
650    *  @param  __first2  Start of sequence to match.
651    *  @param  __last2   End of sequence to match.
652    *  @return   The last iterator @c i in the range
653    *  @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
654    *  @p *(__first2+N) for each @c N in the range @p
655    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
656    *
657    *  Searches the range @p [__first1,__last1) for a sub-sequence that
658    *  compares equal value-by-value with the sequence given by @p
659    *  [__first2,__last2) and returns an iterator to the __first
660    *  element of the sub-sequence, or @p __last1 if the sub-sequence
661    *  is not found.  The sub-sequence will be the last such
662    *  subsequence contained in [__first,__last1).
663    *
664    *  Because the sub-sequence must lie completely within the range @p
665    *  [__first1,__last1) it must start at a position less than @p
666    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
667    *  length of the sub-sequence.  This means that the returned
668    *  iterator @c i will be in the range @p
669    *  [__first1,__last1-(__last2-__first2))
670   */
671   template<typename _ForwardIterator1, typename _ForwardIterator2>
672     inline _ForwardIterator1
673     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
674              _ForwardIterator2 __first2, _ForwardIterator2 __last2)
675     {
676       // concept requirements
677       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
678       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
679       __glibcxx_function_requires(_EqualOpConcept<
680             typename iterator_traits<_ForwardIterator1>::value_type,
681             typename iterator_traits<_ForwardIterator2>::value_type>)
682       __glibcxx_requires_valid_range(__first1, __last1);
683       __glibcxx_requires_valid_range(__first2, __last2);
684
685       return std::__find_end(__first1, __last1, __first2, __last2,
686                              std::__iterator_category(__first1),
687                              std::__iterator_category(__first2));
688     }
689
690   /**
691    *  @brief  Find last matching subsequence in a sequence using a predicate.
692    *  @ingroup non_mutating_algorithms
693    *  @param  __first1  Start of range to search.
694    *  @param  __last1   End of range to search.
695    *  @param  __first2  Start of sequence to match.
696    *  @param  __last2   End of sequence to match.
697    *  @param  __comp    The predicate to use.
698    *  @return The last iterator @c i in the range @p
699    *  [__first1,__last1-(__last2-__first2)) such that @c
700    *  predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
701    *  range @p [0,__last2-__first2), or @p __last1 if no such iterator
702    *  exists.
703    *
704    *  Searches the range @p [__first1,__last1) for a sub-sequence that
705    *  compares equal value-by-value with the sequence given by @p
706    *  [__first2,__last2) using comp as a predicate and returns an
707    *  iterator to the first element of the sub-sequence, or @p __last1
708    *  if the sub-sequence is not found.  The sub-sequence will be the
709    *  last such subsequence contained in [__first,__last1).
710    *
711    *  Because the sub-sequence must lie completely within the range @p
712    *  [__first1,__last1) it must start at a position less than @p
713    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
714    *  length of the sub-sequence.  This means that the returned
715    *  iterator @c i will be in the range @p
716    *  [__first1,__last1-(__last2-__first2))
717   */
718   template<typename _ForwardIterator1, typename _ForwardIterator2,
719            typename _BinaryPredicate>
720     inline _ForwardIterator1
721     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
722              _ForwardIterator2 __first2, _ForwardIterator2 __last2,
723              _BinaryPredicate __comp)
724     {
725       // concept requirements
726       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
727       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
728       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
729             typename iterator_traits<_ForwardIterator1>::value_type,
730             typename iterator_traits<_ForwardIterator2>::value_type>)
731       __glibcxx_requires_valid_range(__first1, __last1);
732       __glibcxx_requires_valid_range(__first2, __last2);
733
734       return std::__find_end(__first1, __last1, __first2, __last2,
735                              std::__iterator_category(__first1),
736                              std::__iterator_category(__first2),
737                              __comp);
738     }
739
740 #ifdef __GXX_EXPERIMENTAL_CXX0X__
741   /**
742    *  @brief  Checks that a predicate is true for all the elements
743    *          of a sequence.
744    *  @ingroup non_mutating_algorithms
745    *  @param  __first   An input iterator.
746    *  @param  __last    An input iterator.
747    *  @param  __pred    A predicate.
748    *  @return  True if the check is true, false otherwise.
749    *
750    *  Returns true if @p __pred is true for each element in the range
751    *  @p [__first,__last), and false otherwise.
752   */
753   template<typename _InputIterator, typename _Predicate>
754     inline bool
755     all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
756     { return __last == std::find_if_not(__first, __last, __pred); }
757
758   /**
759    *  @brief  Checks that a predicate is false for all the elements
760    *          of a sequence.
761    *  @ingroup non_mutating_algorithms
762    *  @param  __first   An input iterator.
763    *  @param  __last    An input iterator.
764    *  @param  __pred    A predicate.
765    *  @return  True if the check is true, false otherwise.
766    *
767    *  Returns true if @p __pred is false for each element in the range
768    *  @p [__first,__last), and false otherwise.
769   */
770   template<typename _InputIterator, typename _Predicate>
771     inline bool
772     none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
773     { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
774
775   /**
776    *  @brief  Checks that a predicate is false for at least an element
777    *          of a sequence.
778    *  @ingroup non_mutating_algorithms
779    *  @param  __first   An input iterator.
780    *  @param  __last    An input iterator.
781    *  @param  __pred    A predicate.
782    *  @return  True if the check is true, false otherwise.
783    *
784    *  Returns true if an element exists in the range @p
785    *  [__first,__last) such that @p __pred is true, and false
786    *  otherwise.
787   */
788   template<typename _InputIterator, typename _Predicate>
789     inline bool
790     any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
791     { return !std::none_of(__first, __last, __pred); }
792
793   /**
794    *  @brief  Find the first element in a sequence for which a
795    *          predicate is false.
796    *  @ingroup non_mutating_algorithms
797    *  @param  __first  An input iterator.
798    *  @param  __last   An input iterator.
799    *  @param  __pred   A predicate.
800    *  @return   The first iterator @c i in the range @p [__first,__last)
801    *  such that @p __pred(*i) is false, or @p __last if no such iterator exists.
802   */
803   template<typename _InputIterator, typename _Predicate>
804     inline _InputIterator
805     find_if_not(_InputIterator __first, _InputIterator __last,
806                 _Predicate __pred)
807     {
808       // concept requirements
809       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
810       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
811               typename iterator_traits<_InputIterator>::value_type>)
812       __glibcxx_requires_valid_range(__first, __last);
813       return std::__find_if_not(__first, __last, __pred);
814     }
815
816   /**
817    *  @brief  Checks whether the sequence is partitioned.
818    *  @ingroup mutating_algorithms
819    *  @param  __first  An input iterator.
820    *  @param  __last   An input iterator.
821    *  @param  __pred   A predicate.
822    *  @return  True if the range @p [__first,__last) is partioned by @p __pred,
823    *  i.e. if all elements that satisfy @p __pred appear before those that
824    *  do not.
825   */
826   template<typename _InputIterator, typename _Predicate>
827     inline bool
828     is_partitioned(_InputIterator __first, _InputIterator __last,
829                    _Predicate __pred)
830     {
831       __first = std::find_if_not(__first, __last, __pred);
832       return std::none_of(__first, __last, __pred);
833     }
834
835   /**
836    *  @brief  Find the partition point of a partitioned range.
837    *  @ingroup mutating_algorithms
838    *  @param  __first   An iterator.
839    *  @param  __last    Another iterator.
840    *  @param  __pred    A predicate.
841    *  @return  An iterator @p mid such that @p all_of(__first, mid, __pred)
842    *           and @p none_of(mid, __last, __pred) are both true.
843   */
844   template<typename _ForwardIterator, typename _Predicate>
845     _ForwardIterator
846     partition_point(_ForwardIterator __first, _ForwardIterator __last,
847                     _Predicate __pred)
848     {
849       // concept requirements
850       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
851       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
852               typename iterator_traits<_ForwardIterator>::value_type>)
853
854       // A specific debug-mode test will be necessary...
855       __glibcxx_requires_valid_range(__first, __last);
856
857       typedef typename iterator_traits<_ForwardIterator>::difference_type
858         _DistanceType;
859
860       _DistanceType __len = std::distance(__first, __last);
861       _DistanceType __half;
862       _ForwardIterator __middle;
863
864       while (__len > 0)
865         {
866           __half = __len >> 1;
867           __middle = __first;
868           std::advance(__middle, __half);
869           if (__pred(*__middle))
870             {
871               __first = __middle;
872               ++__first;
873               __len = __len - __half - 1;
874             }
875           else
876             __len = __half;
877         }
878       return __first;
879     }
880 #endif
881
882
883   /**
884    *  @brief Copy a sequence, removing elements of a given value.
885    *  @ingroup mutating_algorithms
886    *  @param  __first   An input iterator.
887    *  @param  __last    An input iterator.
888    *  @param  __result  An output iterator.
889    *  @param  __value   The value to be removed.
890    *  @return   An iterator designating the end of the resulting sequence.
891    *
892    *  Copies each element in the range @p [__first,__last) not equal
893    *  to @p __value to the range beginning at @p __result.
894    *  remove_copy() is stable, so the relative order of elements that
895    *  are copied is unchanged.
896   */
897   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
898     _OutputIterator
899     remove_copy(_InputIterator __first, _InputIterator __last,
900                 _OutputIterator __result, const _Tp& __value)
901     {
902       // concept requirements
903       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
904       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
905             typename iterator_traits<_InputIterator>::value_type>)
906       __glibcxx_function_requires(_EqualOpConcept<
907             typename iterator_traits<_InputIterator>::value_type, _Tp>)
908       __glibcxx_requires_valid_range(__first, __last);
909
910       for (; __first != __last; ++__first)
911         if (!(*__first == __value))
912           {
913             *__result = *__first;
914             ++__result;
915           }
916       return __result;
917     }
918
919   /**
920    *  @brief Copy a sequence, removing elements for which a predicate is true.
921    *  @ingroup mutating_algorithms
922    *  @param  __first   An input iterator.
923    *  @param  __last    An input iterator.
924    *  @param  __result  An output iterator.
925    *  @param  __pred    A predicate.
926    *  @return   An iterator designating the end of the resulting sequence.
927    *
928    *  Copies each element in the range @p [__first,__last) for which
929    *  @p __pred returns false to the range beginning at @p __result.
930    *
931    *  remove_copy_if() is stable, so the relative order of elements that are
932    *  copied is unchanged.
933   */
934   template<typename _InputIterator, typename _OutputIterator,
935            typename _Predicate>
936     _OutputIterator
937     remove_copy_if(_InputIterator __first, _InputIterator __last,
938                    _OutputIterator __result, _Predicate __pred)
939     {
940       // concept requirements
941       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
942       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
943             typename iterator_traits<_InputIterator>::value_type>)
944       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
945             typename iterator_traits<_InputIterator>::value_type>)
946       __glibcxx_requires_valid_range(__first, __last);
947
948       for (; __first != __last; ++__first)
949         if (!bool(__pred(*__first)))
950           {
951             *__result = *__first;
952             ++__result;
953           }
954       return __result;
955     }
956
957 #ifdef __GXX_EXPERIMENTAL_CXX0X__
958   /**
959    *  @brief Copy the elements of a sequence for which a predicate is true.
960    *  @ingroup mutating_algorithms
961    *  @param  __first   An input iterator.
962    *  @param  __last    An input iterator.
963    *  @param  __result  An output iterator.
964    *  @param  __pred    A predicate.
965    *  @return   An iterator designating the end of the resulting sequence.
966    *
967    *  Copies each element in the range @p [__first,__last) for which
968    *  @p __pred returns true to the range beginning at @p __result.
969    *
970    *  copy_if() is stable, so the relative order of elements that are
971    *  copied is unchanged.
972   */
973   template<typename _InputIterator, typename _OutputIterator,
974            typename _Predicate>
975     _OutputIterator
976     copy_if(_InputIterator __first, _InputIterator __last,
977             _OutputIterator __result, _Predicate __pred)
978     {
979       // concept requirements
980       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
981       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
982             typename iterator_traits<_InputIterator>::value_type>)
983       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
984             typename iterator_traits<_InputIterator>::value_type>)
985       __glibcxx_requires_valid_range(__first, __last);
986
987       for (; __first != __last; ++__first)
988         if (__pred(*__first))
989           {
990             *__result = *__first;
991             ++__result;
992           }
993       return __result;
994     }
995
996
997   template<typename _InputIterator, typename _Size, typename _OutputIterator>
998     _OutputIterator
999     __copy_n(_InputIterator __first, _Size __n,
1000              _OutputIterator __result, input_iterator_tag)
1001     {
1002       if (__n > 0)
1003         {
1004           while (true)
1005             {
1006               *__result = *__first;
1007               ++__result;
1008               if (--__n > 0)
1009                 ++__first;
1010               else
1011                 break;
1012             }
1013         }
1014       return __result;
1015     }
1016
1017   template<typename _RandomAccessIterator, typename _Size,
1018            typename _OutputIterator>
1019     inline _OutputIterator
1020     __copy_n(_RandomAccessIterator __first, _Size __n,
1021              _OutputIterator __result, random_access_iterator_tag)
1022     { return std::copy(__first, __first + __n, __result); }
1023
1024   /**
1025    *  @brief Copies the range [first,first+n) into [result,result+n).
1026    *  @ingroup mutating_algorithms
1027    *  @param  __first  An input iterator.
1028    *  @param  __n      The number of elements to copy.
1029    *  @param  __result An output iterator.
1030    *  @return  result+n.
1031    *
1032    *  This inline function will boil down to a call to @c memmove whenever
1033    *  possible.  Failing that, if random access iterators are passed, then the
1034    *  loop count will be known (and therefore a candidate for compiler
1035    *  optimizations such as unrolling).
1036   */
1037   template<typename _InputIterator, typename _Size, typename _OutputIterator>
1038     inline _OutputIterator
1039     copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1040     {
1041       // concept requirements
1042       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1043       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1044             typename iterator_traits<_InputIterator>::value_type>)
1045
1046       return std::__copy_n(__first, __n, __result,
1047                            std::__iterator_category(__first));
1048     }
1049
1050   /**
1051    *  @brief Copy the elements of a sequence to separate output sequences
1052    *         depending on the truth value of a predicate.
1053    *  @ingroup mutating_algorithms
1054    *  @param  __first   An input iterator.
1055    *  @param  __last    An input iterator.
1056    *  @param  __out_true   An output iterator.
1057    *  @param  __out_false  An output iterator.
1058    *  @param  __pred    A predicate.
1059    *  @return   A pair designating the ends of the resulting sequences.
1060    *
1061    *  Copies each element in the range @p [__first,__last) for which
1062    *  @p __pred returns true to the range beginning at @p out_true
1063    *  and each element for which @p __pred returns false to @p __out_false.
1064   */
1065   template<typename _InputIterator, typename _OutputIterator1,
1066            typename _OutputIterator2, typename _Predicate>
1067     pair<_OutputIterator1, _OutputIterator2>
1068     partition_copy(_InputIterator __first, _InputIterator __last,
1069                    _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1070                    _Predicate __pred)
1071     {
1072       // concept requirements
1073       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1074       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1075             typename iterator_traits<_InputIterator>::value_type>)
1076       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1077             typename iterator_traits<_InputIterator>::value_type>)
1078       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1079             typename iterator_traits<_InputIterator>::value_type>)
1080       __glibcxx_requires_valid_range(__first, __last);
1081       
1082       for (; __first != __last; ++__first)
1083         if (__pred(*__first))
1084           {
1085             *__out_true = *__first;
1086             ++__out_true;
1087           }
1088         else
1089           {
1090             *__out_false = *__first;
1091             ++__out_false;
1092           }
1093
1094       return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
1095     }
1096 #endif
1097
1098   /**
1099    *  @brief Remove elements from a sequence.
1100    *  @ingroup mutating_algorithms
1101    *  @param  __first  An input iterator.
1102    *  @param  __last   An input iterator.
1103    *  @param  __value  The value to be removed.
1104    *  @return   An iterator designating the end of the resulting sequence.
1105    *
1106    *  All elements equal to @p __value are removed from the range
1107    *  @p [__first,__last).
1108    *
1109    *  remove() is stable, so the relative order of elements that are
1110    *  not removed is unchanged.
1111    *
1112    *  Elements between the end of the resulting sequence and @p __last
1113    *  are still present, but their value is unspecified.
1114   */
1115   template<typename _ForwardIterator, typename _Tp>
1116     _ForwardIterator
1117     remove(_ForwardIterator __first, _ForwardIterator __last,
1118            const _Tp& __value)
1119     {
1120       // concept requirements
1121       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1122                                   _ForwardIterator>)
1123       __glibcxx_function_requires(_EqualOpConcept<
1124             typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1125       __glibcxx_requires_valid_range(__first, __last);
1126
1127       __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1128       if(__first == __last)
1129         return __first;
1130       _ForwardIterator __result = __first;
1131       ++__first;
1132       for(; __first != __last; ++__first)
1133         if(!(*__first == __value))
1134           {
1135             *__result = _GLIBCXX_MOVE(*__first);
1136             ++__result;
1137           }
1138       return __result;
1139     }
1140
1141   /**
1142    *  @brief Remove elements from a sequence using a predicate.
1143    *  @ingroup mutating_algorithms
1144    *  @param  __first  A forward iterator.
1145    *  @param  __last   A forward iterator.
1146    *  @param  __pred   A predicate.
1147    *  @return   An iterator designating the end of the resulting sequence.
1148    *
1149    *  All elements for which @p __pred returns true are removed from the range
1150    *  @p [__first,__last).
1151    *
1152    *  remove_if() is stable, so the relative order of elements that are
1153    *  not removed is unchanged.
1154    *
1155    *  Elements between the end of the resulting sequence and @p __last
1156    *  are still present, but their value is unspecified.
1157   */
1158   template<typename _ForwardIterator, typename _Predicate>
1159     _ForwardIterator
1160     remove_if(_ForwardIterator __first, _ForwardIterator __last,
1161               _Predicate __pred)
1162     {
1163       // concept requirements
1164       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1165                                   _ForwardIterator>)
1166       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1167             typename iterator_traits<_ForwardIterator>::value_type>)
1168       __glibcxx_requires_valid_range(__first, __last);
1169
1170       __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1171       if(__first == __last)
1172         return __first;
1173       _ForwardIterator __result = __first;
1174       ++__first;
1175       for(; __first != __last; ++__first)
1176         if(!bool(__pred(*__first)))
1177           {
1178             *__result = _GLIBCXX_MOVE(*__first);
1179             ++__result;
1180           }
1181       return __result;
1182     }
1183
1184   /**
1185    *  @brief Remove consecutive duplicate values from a sequence.
1186    *  @ingroup mutating_algorithms
1187    *  @param  __first  A forward iterator.
1188    *  @param  __last   A forward iterator.
1189    *  @return  An iterator designating the end of the resulting sequence.
1190    *
1191    *  Removes all but the first element from each group of consecutive
1192    *  values that compare equal.
1193    *  unique() is stable, so the relative order of elements that are
1194    *  not removed is unchanged.
1195    *  Elements between the end of the resulting sequence and @p __last
1196    *  are still present, but their value is unspecified.
1197   */
1198   template<typename _ForwardIterator>
1199     _ForwardIterator
1200     unique(_ForwardIterator __first, _ForwardIterator __last)
1201     {
1202       // concept requirements
1203       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1204                                   _ForwardIterator>)
1205       __glibcxx_function_requires(_EqualityComparableConcept<
1206                      typename iterator_traits<_ForwardIterator>::value_type>)
1207       __glibcxx_requires_valid_range(__first, __last);
1208
1209       // Skip the beginning, if already unique.
1210       __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1211       if (__first == __last)
1212         return __last;
1213
1214       // Do the real copy work.
1215       _ForwardIterator __dest = __first;
1216       ++__first;
1217       while (++__first != __last)
1218         if (!(*__dest == *__first))
1219           *++__dest = _GLIBCXX_MOVE(*__first);
1220       return ++__dest;
1221     }
1222
1223   /**
1224    *  @brief Remove consecutive values from a sequence using a predicate.
1225    *  @ingroup mutating_algorithms
1226    *  @param  __first        A forward iterator.
1227    *  @param  __last         A forward iterator.
1228    *  @param  __binary_pred  A binary predicate.
1229    *  @return  An iterator designating the end of the resulting sequence.
1230    *
1231    *  Removes all but the first element from each group of consecutive
1232    *  values for which @p __binary_pred returns true.
1233    *  unique() is stable, so the relative order of elements that are
1234    *  not removed is unchanged.
1235    *  Elements between the end of the resulting sequence and @p __last
1236    *  are still present, but their value is unspecified.
1237   */
1238   template<typename _ForwardIterator, typename _BinaryPredicate>
1239     _ForwardIterator
1240     unique(_ForwardIterator __first, _ForwardIterator __last,
1241            _BinaryPredicate __binary_pred)
1242     {
1243       // concept requirements
1244       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1245                                   _ForwardIterator>)
1246       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1247                 typename iterator_traits<_ForwardIterator>::value_type,
1248                 typename iterator_traits<_ForwardIterator>::value_type>)
1249       __glibcxx_requires_valid_range(__first, __last);
1250
1251       // Skip the beginning, if already unique.
1252       __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1253       if (__first == __last)
1254         return __last;
1255
1256       // Do the real copy work.
1257       _ForwardIterator __dest = __first;
1258       ++__first;
1259       while (++__first != __last)
1260         if (!bool(__binary_pred(*__dest, *__first)))
1261           *++__dest = _GLIBCXX_MOVE(*__first);
1262       return ++__dest;
1263     }
1264
1265   /**
1266    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
1267    *                                  _OutputIterator)
1268    *  overloaded for forward iterators and output iterator as result.
1269   */
1270   template<typename _ForwardIterator, typename _OutputIterator>
1271     _OutputIterator
1272     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1273                   _OutputIterator __result,
1274                   forward_iterator_tag, output_iterator_tag)
1275     {
1276       // concept requirements -- taken care of in dispatching function
1277       _ForwardIterator __next = __first;
1278       *__result = *__first;
1279       while (++__next != __last)
1280         if (!(*__first == *__next))
1281           {
1282             __first = __next;
1283             *++__result = *__first;
1284           }
1285       return ++__result;
1286     }
1287
1288   /**
1289    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
1290    *                                  _OutputIterator)
1291    *  overloaded for input iterators and output iterator as result.
1292   */
1293   template<typename _InputIterator, typename _OutputIterator>
1294     _OutputIterator
1295     __unique_copy(_InputIterator __first, _InputIterator __last,
1296                   _OutputIterator __result,
1297                   input_iterator_tag, output_iterator_tag)
1298     {
1299       // concept requirements -- taken care of in dispatching function
1300       typename iterator_traits<_InputIterator>::value_type __value = *__first;
1301       *__result = __value;
1302       while (++__first != __last)
1303         if (!(__value == *__first))
1304           {
1305             __value = *__first;
1306             *++__result = __value;
1307           }
1308       return ++__result;
1309     }
1310
1311   /**
1312    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
1313    *                                  _OutputIterator)
1314    *  overloaded for input iterators and forward iterator as result.
1315   */
1316   template<typename _InputIterator, typename _ForwardIterator>
1317     _ForwardIterator
1318     __unique_copy(_InputIterator __first, _InputIterator __last,
1319                   _ForwardIterator __result,
1320                   input_iterator_tag, forward_iterator_tag)
1321     {
1322       // concept requirements -- taken care of in dispatching function
1323       *__result = *__first;
1324       while (++__first != __last)
1325         if (!(*__result == *__first))
1326           *++__result = *__first;
1327       return ++__result;
1328     }
1329
1330   /**
1331    *  This is an uglified
1332    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1333    *              _BinaryPredicate)
1334    *  overloaded for forward iterators and output iterator as result.
1335   */
1336   template<typename _ForwardIterator, typename _OutputIterator,
1337            typename _BinaryPredicate>
1338     _OutputIterator
1339     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1340                   _OutputIterator __result, _BinaryPredicate __binary_pred,
1341                   forward_iterator_tag, output_iterator_tag)
1342     {
1343       // concept requirements -- iterators already checked
1344       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1345           typename iterator_traits<_ForwardIterator>::value_type,
1346           typename iterator_traits<_ForwardIterator>::value_type>)
1347
1348       _ForwardIterator __next = __first;
1349       *__result = *__first;
1350       while (++__next != __last)
1351         if (!bool(__binary_pred(*__first, *__next)))
1352           {
1353             __first = __next;
1354             *++__result = *__first;
1355           }
1356       return ++__result;
1357     }
1358
1359   /**
1360    *  This is an uglified
1361    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1362    *              _BinaryPredicate)
1363    *  overloaded for input iterators and output iterator as result.
1364   */
1365   template<typename _InputIterator, typename _OutputIterator,
1366            typename _BinaryPredicate>
1367     _OutputIterator
1368     __unique_copy(_InputIterator __first, _InputIterator __last,
1369                   _OutputIterator __result, _BinaryPredicate __binary_pred,
1370                   input_iterator_tag, output_iterator_tag)
1371     {
1372       // concept requirements -- iterators already checked
1373       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1374           typename iterator_traits<_InputIterator>::value_type,
1375           typename iterator_traits<_InputIterator>::value_type>)
1376
1377       typename iterator_traits<_InputIterator>::value_type __value = *__first;
1378       *__result = __value;
1379       while (++__first != __last)
1380         if (!bool(__binary_pred(__value, *__first)))
1381           {
1382             __value = *__first;
1383             *++__result = __value;
1384           }
1385       return ++__result;
1386     }
1387
1388   /**
1389    *  This is an uglified
1390    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1391    *              _BinaryPredicate)
1392    *  overloaded for input iterators and forward iterator as result.
1393   */
1394   template<typename _InputIterator, typename _ForwardIterator,
1395            typename _BinaryPredicate>
1396     _ForwardIterator
1397     __unique_copy(_InputIterator __first, _InputIterator __last,
1398                   _ForwardIterator __result, _BinaryPredicate __binary_pred,
1399                   input_iterator_tag, forward_iterator_tag)
1400     {
1401       // concept requirements -- iterators already checked
1402       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1403           typename iterator_traits<_ForwardIterator>::value_type,
1404           typename iterator_traits<_InputIterator>::value_type>)
1405
1406       *__result = *__first;
1407       while (++__first != __last)
1408         if (!bool(__binary_pred(*__result, *__first)))
1409           *++__result = *__first;
1410       return ++__result;
1411     }
1412
1413   /**
1414    *  This is an uglified reverse(_BidirectionalIterator,
1415    *                              _BidirectionalIterator)
1416    *  overloaded for bidirectional iterators.
1417   */
1418   template<typename _BidirectionalIterator>
1419     void
1420     __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1421               bidirectional_iterator_tag)
1422     {
1423       while (true)
1424         if (__first == __last || __first == --__last)
1425           return;
1426         else
1427           {
1428             std::iter_swap(__first, __last);
1429             ++__first;
1430           }
1431     }
1432
1433   /**
1434    *  This is an uglified reverse(_BidirectionalIterator,
1435    *                              _BidirectionalIterator)
1436    *  overloaded for random access iterators.
1437   */
1438   template<typename _RandomAccessIterator>
1439     void
1440     __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1441               random_access_iterator_tag)
1442     {
1443       if (__first == __last)
1444         return;
1445       --__last;
1446       while (__first < __last)
1447         {
1448           std::iter_swap(__first, __last);
1449           ++__first;
1450           --__last;
1451         }
1452     }
1453
1454   /**
1455    *  @brief Reverse a sequence.
1456    *  @ingroup mutating_algorithms
1457    *  @param  __first  A bidirectional iterator.
1458    *  @param  __last   A bidirectional iterator.
1459    *  @return   reverse() returns no value.
1460    *
1461    *  Reverses the order of the elements in the range @p [__first,__last),
1462    *  so that the first element becomes the last etc.
1463    *  For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1464    *  swaps @p *(__first+i) and @p *(__last-(i+1))
1465   */
1466   template<typename _BidirectionalIterator>
1467     inline void
1468     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1469     {
1470       // concept requirements
1471       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1472                                   _BidirectionalIterator>)
1473       __glibcxx_requires_valid_range(__first, __last);
1474       std::__reverse(__first, __last, std::__iterator_category(__first));
1475     }
1476
1477   /**
1478    *  @brief Copy a sequence, reversing its elements.
1479    *  @ingroup mutating_algorithms
1480    *  @param  __first   A bidirectional iterator.
1481    *  @param  __last    A bidirectional iterator.
1482    *  @param  __result  An output iterator.
1483    *  @return  An iterator designating the end of the resulting sequence.
1484    *
1485    *  Copies the elements in the range @p [__first,__last) to the
1486    *  range @p [__result,__result+(__last-__first)) such that the
1487    *  order of the elements is reversed.  For every @c i such that @p
1488    *  0<=i<=(__last-__first), @p reverse_copy() performs the
1489    *  assignment @p *(__result+(__last-__first)-i) = *(__first+i).
1490    *  The ranges @p [__first,__last) and @p
1491    *  [__result,__result+(__last-__first)) must not overlap.
1492   */
1493   template<typename _BidirectionalIterator, typename _OutputIterator>
1494     _OutputIterator
1495     reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1496                  _OutputIterator __result)
1497     {
1498       // concept requirements
1499       __glibcxx_function_requires(_BidirectionalIteratorConcept<
1500                                   _BidirectionalIterator>)
1501       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1502                 typename iterator_traits<_BidirectionalIterator>::value_type>)
1503       __glibcxx_requires_valid_range(__first, __last);
1504
1505       while (__first != __last)
1506         {
1507           --__last;
1508           *__result = *__last;
1509           ++__result;
1510         }
1511       return __result;
1512     }
1513
1514   /**
1515    *  This is a helper function for the rotate algorithm specialized on RAIs.
1516    *  It returns the greatest common divisor of two integer values.
1517   */
1518   template<typename _EuclideanRingElement>
1519     _EuclideanRingElement
1520     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1521     {
1522       while (__n != 0)
1523         {
1524           _EuclideanRingElement __t = __m % __n;
1525           __m = __n;
1526           __n = __t;
1527         }
1528       return __m;
1529     }
1530
1531   /// This is a helper function for the rotate algorithm.
1532   template<typename _ForwardIterator>
1533     void
1534     __rotate(_ForwardIterator __first,
1535              _ForwardIterator __middle,
1536              _ForwardIterator __last,
1537              forward_iterator_tag)
1538     {
1539       if (__first == __middle || __last  == __middle)
1540         return;
1541
1542       _ForwardIterator __first2 = __middle;
1543       do
1544         {
1545           std::iter_swap(__first, __first2);
1546           ++__first;
1547           ++__first2;
1548           if (__first == __middle)
1549             __middle = __first2;
1550         }
1551       while (__first2 != __last);
1552
1553       __first2 = __middle;
1554
1555       while (__first2 != __last)
1556         {
1557           std::iter_swap(__first, __first2);
1558           ++__first;
1559           ++__first2;
1560           if (__first == __middle)
1561             __middle = __first2;
1562           else if (__first2 == __last)
1563             __first2 = __middle;
1564         }
1565     }
1566
1567    /// This is a helper function for the rotate algorithm.
1568   template<typename _BidirectionalIterator>
1569     void
1570     __rotate(_BidirectionalIterator __first,
1571              _BidirectionalIterator __middle,
1572              _BidirectionalIterator __last,
1573               bidirectional_iterator_tag)
1574     {
1575       // concept requirements
1576       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1577                                   _BidirectionalIterator>)
1578
1579       if (__first == __middle || __last  == __middle)
1580         return;
1581
1582       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1583       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1584
1585       while (__first != __middle && __middle != __last)
1586         {
1587           std::iter_swap(__first, --__last);
1588           ++__first;
1589         }
1590
1591       if (__first == __middle)
1592         std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1593       else
1594         std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1595     }
1596
1597   /// This is a helper function for the rotate algorithm.
1598   template<typename _RandomAccessIterator>
1599     void
1600     __rotate(_RandomAccessIterator __first,
1601              _RandomAccessIterator __middle,
1602              _RandomAccessIterator __last,
1603              random_access_iterator_tag)
1604     {
1605       // concept requirements
1606       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1607                                   _RandomAccessIterator>)
1608
1609       if (__first == __middle || __last  == __middle)
1610         return;
1611
1612       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1613         _Distance;
1614       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1615         _ValueType;
1616
1617       _Distance __n = __last   - __first;
1618       _Distance __k = __middle - __first;
1619
1620       if (__k == __n - __k)
1621         {
1622           std::swap_ranges(__first, __middle, __middle);
1623           return;
1624         }
1625
1626       _RandomAccessIterator __p = __first;
1627
1628       for (;;)
1629         {
1630           if (__k < __n - __k)
1631             {
1632               if (__is_pod(_ValueType) && __k == 1)
1633                 {
1634                   _ValueType __t = _GLIBCXX_MOVE(*__p);
1635                   _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1636                   *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1637                   return;
1638                 }
1639               _RandomAccessIterator __q = __p + __k;
1640               for (_Distance __i = 0; __i < __n - __k; ++ __i)
1641                 {
1642                   std::iter_swap(__p, __q);
1643                   ++__p;
1644                   ++__q;
1645                 }
1646               __n %= __k;
1647               if (__n == 0)
1648                 return;
1649               std::swap(__n, __k);
1650               __k = __n - __k;
1651             }
1652           else
1653             {
1654               __k = __n - __k;
1655               if (__is_pod(_ValueType) && __k == 1)
1656                 {
1657                   _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1658                   _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1659                   *__p = _GLIBCXX_MOVE(__t);
1660                   return;
1661                 }
1662               _RandomAccessIterator __q = __p + __n;
1663               __p = __q - __k;
1664               for (_Distance __i = 0; __i < __n - __k; ++ __i)
1665                 {
1666                   --__p;
1667                   --__q;
1668                   std::iter_swap(__p, __q);
1669                 }
1670               __n %= __k;
1671               if (__n == 0)
1672                 return;
1673               std::swap(__n, __k);
1674             }
1675         }
1676     }
1677
1678   /**
1679    *  @brief Rotate the elements of a sequence.
1680    *  @ingroup mutating_algorithms
1681    *  @param  __first   A forward iterator.
1682    *  @param  __middle  A forward iterator.
1683    *  @param  __last    A forward iterator.
1684    *  @return  Nothing.
1685    *
1686    *  Rotates the elements of the range @p [__first,__last) by 
1687    *  @p (__middle - __first) positions so that the element at @p __middle
1688    *  is moved to @p __first, the element at @p __middle+1 is moved to
1689    *  @p __first+1 and so on for each element in the range
1690    *  @p [__first,__last).
1691    *
1692    *  This effectively swaps the ranges @p [__first,__middle) and
1693    *  @p [__middle,__last).
1694    *
1695    *  Performs
1696    *   @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1697    *  for each @p n in the range @p [0,__last-__first).
1698   */
1699   template<typename _ForwardIterator>
1700     inline void
1701     rotate(_ForwardIterator __first, _ForwardIterator __middle,
1702            _ForwardIterator __last)
1703     {
1704       // concept requirements
1705       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1706                                   _ForwardIterator>)
1707       __glibcxx_requires_valid_range(__first, __middle);
1708       __glibcxx_requires_valid_range(__middle, __last);
1709
1710       typedef typename iterator_traits<_ForwardIterator>::iterator_category
1711         _IterType;
1712       std::__rotate(__first, __middle, __last, _IterType());
1713     }
1714
1715   /**
1716    *  @brief Copy a sequence, rotating its elements.
1717    *  @ingroup mutating_algorithms
1718    *  @param  __first   A forward iterator.
1719    *  @param  __middle  A forward iterator.
1720    *  @param  __last    A forward iterator.
1721    *  @param  __result  An output iterator.
1722    *  @return   An iterator designating the end of the resulting sequence.
1723    *
1724    *  Copies the elements of the range @p [__first,__last) to the
1725    *  range beginning at @result, rotating the copied elements by 
1726    *  @p (__middle-__first) positions so that the element at @p __middle
1727    *  is moved to @p __result, the element at @p __middle+1 is moved
1728    *  to @p __result+1 and so on for each element in the range @p
1729    *  [__first,__last).
1730    *
1731    *  Performs 
1732    *  @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1733    *  for each @p n in the range @p [0,__last-__first).
1734   */
1735   template<typename _ForwardIterator, typename _OutputIterator>
1736     _OutputIterator
1737     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1738                 _ForwardIterator __last, _OutputIterator __result)
1739     {
1740       // concept requirements
1741       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1742       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1743                 typename iterator_traits<_ForwardIterator>::value_type>)
1744       __glibcxx_requires_valid_range(__first, __middle);
1745       __glibcxx_requires_valid_range(__middle, __last);
1746
1747       return std::copy(__first, __middle,
1748                        std::copy(__middle, __last, __result));
1749     }
1750
1751   /// This is a helper function...
1752   template<typename _ForwardIterator, typename _Predicate>
1753     _ForwardIterator
1754     __partition(_ForwardIterator __first, _ForwardIterator __last,
1755                 _Predicate __pred, forward_iterator_tag)
1756     {
1757       if (__first == __last)
1758         return __first;
1759
1760       while (__pred(*__first))
1761         if (++__first == __last)
1762           return __first;
1763
1764       _ForwardIterator __next = __first;
1765
1766       while (++__next != __last)
1767         if (__pred(*__next))
1768           {
1769             std::iter_swap(__first, __next);
1770             ++__first;
1771           }
1772
1773       return __first;
1774     }
1775
1776   /// This is a helper function...
1777   template<typename _BidirectionalIterator, typename _Predicate>
1778     _BidirectionalIterator
1779     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1780                 _Predicate __pred, bidirectional_iterator_tag)
1781     {
1782       while (true)
1783         {
1784           while (true)
1785             if (__first == __last)
1786               return __first;
1787             else if (__pred(*__first))
1788               ++__first;
1789             else
1790               break;
1791           --__last;
1792           while (true)
1793             if (__first == __last)
1794               return __first;
1795             else if (!bool(__pred(*__last)))
1796               --__last;
1797             else
1798               break;
1799           std::iter_swap(__first, __last);
1800           ++__first;
1801         }
1802     }
1803
1804   // partition
1805
1806   /// This is a helper function...
1807   /// Requires __len != 0 and !__pred(*__first),
1808   /// same as __stable_partition_adaptive.
1809   template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1810     _ForwardIterator
1811     __inplace_stable_partition(_ForwardIterator __first,
1812                                _Predicate __pred, _Distance __len)
1813     {
1814       if (__len == 1)
1815         return __first;
1816       _ForwardIterator __middle = __first;
1817       std::advance(__middle, __len / 2);
1818       _ForwardIterator __left_split =
1819         std::__inplace_stable_partition(__first, __pred, __len / 2);
1820       // Advance past true-predicate values to satisfy this
1821       // function's preconditions.
1822       _Distance __right_len = __len - __len / 2;
1823       _ForwardIterator __right_split =
1824         std::__find_if_not_n(__middle, __right_len, __pred);
1825       if (__right_len)
1826         __right_split = std::__inplace_stable_partition(__middle,
1827                                                         __pred,
1828                                                         __right_len);
1829       std::rotate(__left_split, __middle, __right_split);
1830       std::advance(__left_split, std::distance(__middle, __right_split));
1831       return __left_split;
1832     }
1833
1834   /// This is a helper function...
1835   /// Requires __first != __last and !__pred(*__first)
1836   /// and __len == distance(__first, __last).
1837   ///
1838   /// !__pred(*__first) allows us to guarantee that we don't
1839   /// move-assign an element onto itself.
1840   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1841            typename _Distance>
1842     _ForwardIterator
1843     __stable_partition_adaptive(_ForwardIterator __first,
1844                                 _ForwardIterator __last,
1845                                 _Predicate __pred, _Distance __len,
1846                                 _Pointer __buffer,
1847                                 _Distance __buffer_size)
1848     {
1849       if (__len <= __buffer_size)
1850         {
1851           _ForwardIterator __result1 = __first;
1852           _Pointer __result2 = __buffer;
1853           // The precondition guarantees that !__pred(*__first), so
1854           // move that element to the buffer before starting the loop.
1855           // This ensures that we only call __pred once per element.
1856           *__result2 = _GLIBCXX_MOVE(*__first);
1857           ++__result2;
1858           ++__first;
1859           for (; __first != __last; ++__first)
1860             if (__pred(*__first))
1861               {
1862                 *__result1 = _GLIBCXX_MOVE(*__first);
1863                 ++__result1;
1864               }
1865             else
1866               {
1867                 *__result2 = _GLIBCXX_MOVE(*__first);
1868                 ++__result2;
1869               }
1870           _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1871           return __result1;
1872         }
1873       else
1874         {
1875           _ForwardIterator __middle = __first;
1876           std::advance(__middle, __len / 2);
1877           _ForwardIterator __left_split =
1878             std::__stable_partition_adaptive(__first, __middle, __pred,
1879                                              __len / 2, __buffer,
1880                                              __buffer_size);
1881           // Advance past true-predicate values to satisfy this
1882           // function's preconditions.
1883           _Distance __right_len = __len - __len / 2;
1884           _ForwardIterator __right_split =
1885             std::__find_if_not_n(__middle, __right_len, __pred);
1886           if (__right_len)
1887             __right_split =
1888               std::__stable_partition_adaptive(__right_split, __last, __pred,
1889                                                __right_len,
1890                                                __buffer, __buffer_size);
1891           std::rotate(__left_split, __middle, __right_split);
1892           std::advance(__left_split, std::distance(__middle, __right_split));
1893           return __left_split;
1894         }
1895     }
1896
1897   /**
1898    *  @brief Move elements for which a predicate is true to the beginning
1899    *         of a sequence, preserving relative ordering.
1900    *  @ingroup mutating_algorithms
1901    *  @param  __first   A forward iterator.
1902    *  @param  __last    A forward iterator.
1903    *  @param  __pred    A predicate functor.
1904    *  @return  An iterator @p middle such that @p __pred(i) is true for each
1905    *  iterator @p i in the range @p [first,middle) and false for each @p i
1906    *  in the range @p [middle,last).
1907    *
1908    *  Performs the same function as @p partition() with the additional
1909    *  guarantee that the relative ordering of elements in each group is
1910    *  preserved, so any two elements @p x and @p y in the range
1911    *  @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1912    *  relative ordering after calling @p stable_partition().
1913   */
1914   template<typename _ForwardIterator, typename _Predicate>
1915     _ForwardIterator
1916     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1917                      _Predicate __pred)
1918     {
1919       // concept requirements
1920       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1921                                   _ForwardIterator>)
1922       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1923             typename iterator_traits<_ForwardIterator>::value_type>)
1924       __glibcxx_requires_valid_range(__first, __last);
1925
1926       __first = std::__find_if_not(__first, __last, __pred);
1927
1928       if (__first == __last)
1929         return __first;
1930       else
1931         {
1932           typedef typename iterator_traits<_ForwardIterator>::value_type
1933             _ValueType;
1934           typedef typename iterator_traits<_ForwardIterator>::difference_type
1935             _DistanceType;
1936
1937           _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1938                                                                 __last);
1939         if (__buf.size() > 0)
1940           return
1941             std::__stable_partition_adaptive(__first, __last, __pred,
1942                                           _DistanceType(__buf.requested_size()),
1943                                           __buf.begin(),
1944                                           _DistanceType(__buf.size()));
1945         else
1946           return
1947             std::__inplace_stable_partition(__first, __pred,
1948                                          _DistanceType(__buf.requested_size()));
1949         }
1950     }
1951
1952   /// This is a helper function for the sort routines.
1953   template<typename _RandomAccessIterator>
1954     void
1955     __heap_select(_RandomAccessIterator __first,
1956                   _RandomAccessIterator __middle,
1957                   _RandomAccessIterator __last)
1958     {
1959       std::make_heap(__first, __middle);
1960       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1961         if (*__i < *__first)
1962           std::__pop_heap(__first, __middle, __i);
1963     }
1964
1965   /// This is a helper function for the sort routines.
1966   template<typename _RandomAccessIterator, typename _Compare>
1967     void
1968     __heap_select(_RandomAccessIterator __first,
1969                   _RandomAccessIterator __middle,
1970                   _RandomAccessIterator __last, _Compare __comp)
1971     {
1972       std::make_heap(__first, __middle, __comp);
1973       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1974         if (__comp(*__i, *__first))
1975           std::__pop_heap(__first, __middle, __i, __comp);
1976     }
1977
1978   // partial_sort
1979
1980   /**
1981    *  @brief Copy the smallest elements of a sequence.
1982    *  @ingroup sorting_algorithms
1983    *  @param  __first   An iterator.
1984    *  @param  __last    Another iterator.
1985    *  @param  __result_first   A random-access iterator.
1986    *  @param  __result_last    Another random-access iterator.
1987    *  @return   An iterator indicating the end of the resulting sequence.
1988    *
1989    *  Copies and sorts the smallest N values from the range @p [__first,__last)
1990    *  to the range beginning at @p __result_first, where the number of
1991    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
1992    *  @p (__result_last-__result_first).
1993    *  After the sort if @e i and @e j are iterators in the range
1994    *  @p [__result_first,__result_first+N) such that i precedes j then
1995    *  *j<*i is false.
1996    *  The value returned is @p __result_first+N.
1997   */
1998   template<typename _InputIterator, typename _RandomAccessIterator>
1999     _RandomAccessIterator
2000     partial_sort_copy(_InputIterator __first, _InputIterator __last,
2001                       _RandomAccessIterator __result_first,
2002                       _RandomAccessIterator __result_last)
2003     {
2004       typedef typename iterator_traits<_InputIterator>::value_type
2005         _InputValueType;
2006       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2007         _OutputValueType;
2008       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2009         _DistanceType;
2010
2011       // concept requirements
2012       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2013       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2014                                   _OutputValueType>)
2015       __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
2016                                                      _OutputValueType>)
2017       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
2018       __glibcxx_requires_valid_range(__first, __last);
2019       __glibcxx_requires_valid_range(__result_first, __result_last);
2020
2021       if (__result_first == __result_last)
2022         return __result_last;
2023       _RandomAccessIterator __result_real_last = __result_first;
2024       while(__first != __last && __result_real_last != __result_last)
2025         {
2026           *__result_real_last = *__first;
2027           ++__result_real_last;
2028           ++__first;
2029         }
2030       std::make_heap(__result_first, __result_real_last);
2031       while (__first != __last)
2032         {
2033           if (*__first < *__result_first)
2034             std::__adjust_heap(__result_first, _DistanceType(0),
2035                                _DistanceType(__result_real_last
2036                                              - __result_first),
2037                                _InputValueType(*__first));
2038           ++__first;
2039         }
2040       std::sort_heap(__result_first, __result_real_last);
2041       return __result_real_last;
2042     }
2043
2044   /**
2045    *  @brief Copy the smallest elements of a sequence using a predicate for
2046    *         comparison.
2047    *  @ingroup sorting_algorithms
2048    *  @param  __first   An input iterator.
2049    *  @param  __last    Another input iterator.
2050    *  @param  __result_first   A random-access iterator.
2051    *  @param  __result_last    Another random-access iterator.
2052    *  @param  __comp    A comparison functor.
2053    *  @return   An iterator indicating the end of the resulting sequence.
2054    *
2055    *  Copies and sorts the smallest N values from the range @p [__first,__last)
2056    *  to the range beginning at @p result_first, where the number of
2057    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
2058    *  @p (__result_last-__result_first).
2059    *  After the sort if @e i and @e j are iterators in the range
2060    *  @p [__result_first,__result_first+N) such that i precedes j then
2061    *  @p __comp(*j,*i) is false.
2062    *  The value returned is @p __result_first+N.
2063   */
2064   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2065     _RandomAccessIterator
2066     partial_sort_copy(_InputIterator __first, _InputIterator __last,
2067                       _RandomAccessIterator __result_first,
2068                       _RandomAccessIterator __result_last,
2069                       _Compare __comp)
2070     {
2071       typedef typename iterator_traits<_InputIterator>::value_type
2072         _InputValueType;
2073       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2074         _OutputValueType;
2075       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2076         _DistanceType;
2077
2078       // concept requirements
2079       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2080       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2081                                   _RandomAccessIterator>)
2082       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2083                                   _OutputValueType>)
2084       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2085                                   _InputValueType, _OutputValueType>)
2086       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2087                                   _OutputValueType, _OutputValueType>)
2088       __glibcxx_requires_valid_range(__first, __last);
2089       __glibcxx_requires_valid_range(__result_first, __result_last);
2090
2091       if (__result_first == __result_last)
2092         return __result_last;
2093       _RandomAccessIterator __result_real_last = __result_first;
2094       while(__first != __last && __result_real_last != __result_last)
2095         {
2096           *__result_real_last = *__first;
2097           ++__result_real_last;
2098           ++__first;
2099         }
2100       std::make_heap(__result_first, __result_real_last, __comp);
2101       while (__first != __last)
2102         {
2103           if (__comp(*__first, *__result_first))
2104             std::__adjust_heap(__result_first, _DistanceType(0),
2105                                _DistanceType(__result_real_last
2106                                              - __result_first),
2107                                _InputValueType(*__first),
2108                                __comp);
2109           ++__first;
2110         }
2111       std::sort_heap(__result_first, __result_real_last, __comp);
2112       return __result_real_last;
2113     }
2114
2115   /// This is a helper function for the sort routine.
2116   template<typename _RandomAccessIterator>
2117     void
2118     __unguarded_linear_insert(_RandomAccessIterator __last)
2119     {
2120       typename iterator_traits<_RandomAccessIterator>::value_type
2121         __val = _GLIBCXX_MOVE(*__last);
2122       _RandomAccessIterator __next = __last;
2123       --__next;
2124       while (__val < *__next)
2125         {
2126           *__last = _GLIBCXX_MOVE(*__next);
2127           __last = __next;
2128           --__next;
2129         }
2130       *__last = _GLIBCXX_MOVE(__val);
2131     }
2132
2133   /// This is a helper function for the sort routine.
2134   template<typename _RandomAccessIterator, typename _Compare>
2135     void
2136     __unguarded_linear_insert(_RandomAccessIterator __last,
2137                               _Compare __comp)
2138     {
2139       typename iterator_traits<_RandomAccessIterator>::value_type
2140         __val = _GLIBCXX_MOVE(*__last);
2141       _RandomAccessIterator __next = __last;
2142       --__next;
2143       while (__comp(__val, *__next))
2144         {
2145           *__last = _GLIBCXX_MOVE(*__next);
2146           __last = __next;
2147           --__next;
2148         }
2149       *__last = _GLIBCXX_MOVE(__val);
2150     }
2151
2152   /// This is a helper function for the sort routine.
2153   template<typename _RandomAccessIterator>
2154     void
2155     __insertion_sort(_RandomAccessIterator __first,
2156                      _RandomAccessIterator __last)
2157     {
2158       if (__first == __last)
2159         return;
2160
2161       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2162         {
2163           if (*__i < *__first)
2164             {
2165               typename iterator_traits<_RandomAccessIterator>::value_type
2166                 __val = _GLIBCXX_MOVE(*__i);
2167               _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2168               *__first = _GLIBCXX_MOVE(__val);
2169             }
2170           else
2171             std::__unguarded_linear_insert(__i);
2172         }
2173     }
2174
2175   /// This is a helper function for the sort routine.
2176   template<typename _RandomAccessIterator, typename _Compare>
2177     void
2178     __insertion_sort(_RandomAccessIterator __first,
2179                      _RandomAccessIterator __last, _Compare __comp)
2180     {
2181       if (__first == __last) return;
2182
2183       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2184         {
2185           if (__comp(*__i, *__first))
2186             {
2187               typename iterator_traits<_RandomAccessIterator>::value_type
2188                 __val = _GLIBCXX_MOVE(*__i);
2189               _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2190               *__first = _GLIBCXX_MOVE(__val);
2191             }
2192           else
2193             std::__unguarded_linear_insert(__i, __comp);
2194         }
2195     }
2196
2197   /// This is a helper function for the sort routine.
2198   template<typename _RandomAccessIterator>
2199     inline void
2200     __unguarded_insertion_sort(_RandomAccessIterator __first,
2201                                _RandomAccessIterator __last)
2202     {
2203       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2204         _ValueType;
2205
2206       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2207         std::__unguarded_linear_insert(__i);
2208     }
2209
2210   /// This is a helper function for the sort routine.
2211   template<typename _RandomAccessIterator, typename _Compare>
2212     inline void
2213     __unguarded_insertion_sort(_RandomAccessIterator __first,
2214                                _RandomAccessIterator __last, _Compare __comp)
2215     {
2216       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2217         _ValueType;
2218
2219       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2220         std::__unguarded_linear_insert(__i, __comp);
2221     }
2222
2223   /**
2224    *  @doctodo
2225    *  This controls some aspect of the sort routines.
2226   */
2227   enum { _S_threshold = 16 };
2228
2229   /// This is a helper function for the sort routine.
2230   template<typename _RandomAccessIterator>
2231     void
2232     __final_insertion_sort(_RandomAccessIterator __first,
2233                            _RandomAccessIterator __last)
2234     {
2235       if (__last - __first > int(_S_threshold))
2236         {
2237           std::__insertion_sort(__first, __first + int(_S_threshold));
2238           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2239         }
2240       else
2241         std::__insertion_sort(__first, __last);
2242     }
2243
2244   /// This is a helper function for the sort routine.
2245   template<typename _RandomAccessIterator, typename _Compare>
2246     void
2247     __final_insertion_sort(_RandomAccessIterator __first,
2248                            _RandomAccessIterator __last, _Compare __comp)
2249     {
2250       if (__last - __first > int(_S_threshold))
2251         {
2252           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2253           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2254                                           __comp);
2255         }
2256       else
2257         std::__insertion_sort(__first, __last, __comp);
2258     }
2259
2260   /// This is a helper function...
2261   template<typename _RandomAccessIterator, typename _Tp>
2262     _RandomAccessIterator
2263     __unguarded_partition(_RandomAccessIterator __first,
2264                           _RandomAccessIterator __last, const _Tp& __pivot)
2265     {
2266       while (true)
2267         {
2268           while (*__first < __pivot)
2269             ++__first;
2270           --__last;
2271           while (__pivot < *__last)
2272             --__last;
2273           if (!(__first < __last))
2274             return __first;
2275           std::iter_swap(__first, __last);
2276           ++__first;
2277         }
2278     }
2279
2280   /// This is a helper function...
2281   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2282     _RandomAccessIterator
2283     __unguarded_partition(_RandomAccessIterator __first,
2284                           _RandomAccessIterator __last,
2285                           const _Tp& __pivot, _Compare __comp)
2286     {
2287       while (true)
2288         {
2289           while (__comp(*__first, __pivot))
2290             ++__first;
2291           --__last;
2292           while (__comp(__pivot, *__last))
2293             --__last;
2294           if (!(__first < __last))
2295             return __first;
2296           std::iter_swap(__first, __last);
2297           ++__first;
2298         }
2299     }
2300
2301   /// This is a helper function...
2302   template<typename _RandomAccessIterator>
2303     inline _RandomAccessIterator
2304     __unguarded_partition_pivot(_RandomAccessIterator __first,
2305                                 _RandomAccessIterator __last)
2306     {
2307       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2308       std::__move_median_first(__first, __mid, (__last - 1));
2309       return std::__unguarded_partition(__first + 1, __last, *__first);
2310     }
2311
2312
2313   /// This is a helper function...
2314   template<typename _RandomAccessIterator, typename _Compare>
2315     inline _RandomAccessIterator
2316     __unguarded_partition_pivot(_RandomAccessIterator __first,
2317                                 _RandomAccessIterator __last, _Compare __comp)
2318     {
2319       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2320       std::__move_median_first(__first, __mid, (__last - 1), __comp);
2321       return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2322     }
2323
2324   /// This is a helper function for the sort routine.
2325   template<typename _RandomAccessIterator, typename _Size>
2326     void
2327     __introsort_loop(_RandomAccessIterator __first,
2328                      _RandomAccessIterator __last,
2329                      _Size __depth_limit)
2330     {
2331       while (__last - __first > int(_S_threshold))
2332         {
2333           if (__depth_limit == 0)
2334             {
2335               _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2336               return;
2337             }
2338           --__depth_limit;
2339           _RandomAccessIterator __cut =
2340             std::__unguarded_partition_pivot(__first, __last);
2341           std::__introsort_loop(__cut, __last, __depth_limit);
2342           __last = __cut;
2343         }
2344     }
2345
2346   /// This is a helper function for the sort routine.
2347   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2348     void
2349     __introsort_loop(_RandomAccessIterator __first,
2350                      _RandomAccessIterator __last,
2351                      _Size __depth_limit, _Compare __comp)
2352     {
2353       while (__last - __first > int(_S_threshold))
2354         {
2355           if (__depth_limit == 0)
2356             {
2357               _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2358               return;
2359             }
2360           --__depth_limit;
2361           _RandomAccessIterator __cut =
2362             std::__unguarded_partition_pivot(__first, __last, __comp);
2363           std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2364           __last = __cut;
2365         }
2366     }
2367
2368   // sort
2369
2370   template<typename _RandomAccessIterator, typename _Size>
2371     void
2372     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2373                   _RandomAccessIterator __last, _Size __depth_limit)
2374     {
2375       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2376         _ValueType;
2377
2378       while (__last - __first > 3)
2379         {
2380           if (__depth_limit == 0)
2381             {
2382               std::__heap_select(__first, __nth + 1, __last);
2383
2384               // Place the nth largest element in its final position.
2385               std::iter_swap(__first, __nth);
2386               return;
2387             }
2388           --__depth_limit;
2389           _RandomAccessIterator __cut =
2390             std::__unguarded_partition_pivot(__first, __last);
2391           if (__cut <= __nth)
2392             __first = __cut;
2393           else
2394             __last = __cut;
2395         }
2396       std::__insertion_sort(__first, __last);
2397     }
2398
2399   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2400     void
2401     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2402                   _RandomAccessIterator __last, _Size __depth_limit,
2403                   _Compare __comp)
2404     {
2405       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2406         _ValueType;
2407
2408       while (__last - __first > 3)
2409         {
2410           if (__depth_limit == 0)
2411             {
2412               std::__heap_select(__first, __nth + 1, __last, __comp);
2413               // Place the nth largest element in its final position.
2414               std::iter_swap(__first, __nth);
2415               return;
2416             }
2417           --__depth_limit;
2418           _RandomAccessIterator __cut =
2419             std::__unguarded_partition_pivot(__first, __last, __comp);
2420           if (__cut <= __nth)
2421             __first = __cut;
2422           else
2423             __last = __cut;
2424         }
2425       std::__insertion_sort(__first, __last, __comp);
2426     }
2427
2428   // nth_element
2429
2430   // lower_bound moved to stl_algobase.h
2431
2432   /**
2433    *  @brief Finds the first position in which @p __val could be inserted
2434    *         without changing the ordering.
2435    *  @ingroup binary_search_algorithms
2436    *  @param  __first   An iterator.
2437    *  @param  __last    Another iterator.
2438    *  @param  __val     The search term.
2439    *  @param  __comp    A functor to use for comparisons.
2440    *  @return An iterator pointing to the first element <em>not less
2441    *           than</em> @p __val, or end() if every element is less
2442    *           than @p __val.
2443    *  @ingroup binary_search_algorithms
2444    *
2445    *  The comparison function should have the same effects on ordering as
2446    *  the function used for the initial sort.
2447   */
2448   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2449     _ForwardIterator
2450     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2451                 const _Tp& __val, _Compare __comp)
2452     {
2453       typedef typename iterator_traits<_ForwardIterator>::value_type
2454         _ValueType;
2455       typedef typename iterator_traits<_ForwardIterator>::difference_type
2456         _DistanceType;
2457
2458       // concept requirements
2459       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2460       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2461                                   _ValueType, _Tp>)
2462       __glibcxx_requires_partitioned_lower_pred(__first, __last,
2463                                                 __val, __comp);
2464
2465       _DistanceType __len = std::distance(__first, __last);
2466
2467       while (__len > 0)
2468         {
2469           _DistanceType __half = __len >> 1;
2470           _ForwardIterator __middle = __first;
2471           std::advance(__middle, __half);
2472           if (__comp(*__middle, __val))
2473             {
2474               __first = __middle;
2475               ++__first;
2476               __len = __len - __half - 1;
2477             }
2478           else
2479             __len = __half;
2480         }
2481       return __first;
2482     }
2483
2484   /**
2485    *  @brief Finds the last position in which @p __val could be inserted
2486    *         without changing the ordering.
2487    *  @ingroup binary_search_algorithms
2488    *  @param  __first   An iterator.
2489    *  @param  __last    Another iterator.
2490    *  @param  __val     The search term.
2491    *  @return  An iterator pointing to the first element greater than @p __val,
2492    *           or end() if no elements are greater than @p __val.
2493    *  @ingroup binary_search_algorithms
2494   */
2495   template<typename _ForwardIterator, typename _Tp>
2496     _ForwardIterator
2497     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2498                 const _Tp& __val)
2499     {
2500       typedef typename iterator_traits<_ForwardIterator>::value_type
2501         _ValueType;
2502       typedef typename iterator_traits<_ForwardIterator>::difference_type
2503         _DistanceType;
2504
2505       // concept requirements
2506       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2507       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2508       __glibcxx_requires_partitioned_upper(__first, __last, __val);
2509
2510       _DistanceType __len = std::distance(__first, __last);
2511
2512       while (__len > 0)
2513         {
2514           _DistanceType __half = __len >> 1;
2515           _ForwardIterator __middle = __first;
2516           std::advance(__middle, __half);
2517           if (__val < *__middle)
2518             __len = __half;
2519           else
2520             {
2521               __first = __middle;
2522               ++__first;
2523               __len = __len - __half - 1;
2524             }
2525         }
2526       return __first;
2527     }
2528
2529   /**
2530    *  @brief Finds the last position in which @p __val could be inserted
2531    *         without changing the ordering.
2532    *  @ingroup binary_search_algorithms
2533    *  @param  __first   An iterator.
2534    *  @param  __last    Another iterator.
2535    *  @param  __val     The search term.
2536    *  @param  __comp    A functor to use for comparisons.
2537    *  @return  An iterator pointing to the first element greater than @p __val,
2538    *           or end() if no elements are greater than @p __val.
2539    *  @ingroup binary_search_algorithms
2540    *
2541    *  The comparison function should have the same effects on ordering as
2542    *  the function used for the initial sort.
2543   */
2544   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2545     _ForwardIterator
2546     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2547                 const _Tp& __val, _Compare __comp)
2548     {
2549       typedef typename iterator_traits<_ForwardIterator>::value_type
2550         _ValueType;
2551       typedef typename iterator_traits<_ForwardIterator>::difference_type
2552         _DistanceType;
2553
2554       // concept requirements
2555       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2556       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2557                                   _Tp, _ValueType>)
2558       __glibcxx_requires_partitioned_upper_pred(__first, __last,
2559                                                 __val, __comp);
2560
2561       _DistanceType __len = std::distance(__first, __last);
2562
2563       while (__len > 0)
2564         {