stl_algo.h revision 97403
197403Sobrien// Algorithm implementation -*- C++ -*- 297403Sobrien 397403Sobrien// Copyright (C) 2001, 2002 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the 797403Sobrien// terms of the GNU General Public License as published by the 897403Sobrien// Free Software Foundation; either version 2, or (at your option) 997403Sobrien// any later version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, 1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1497403Sobrien// GNU General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License along 1797403Sobrien// with this library; see the file COPYING. If not, write to the Free 1897403Sobrien// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 1997403Sobrien// USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free software 2297403Sobrien// library without restriction. Specifically, if other files instantiate 2397403Sobrien// templates or use macros or inline functions from this file, or you compile 2497403Sobrien// this file and link it with other files to produce an executable, this 2597403Sobrien// file does not by itself cause the resulting executable to be covered by 2697403Sobrien// the GNU General Public License. This exception does not however 2797403Sobrien// invalidate any other reasons why the executable file might be covered by 2897403Sobrien// the GNU General Public License. 2997403Sobrien 3097403Sobrien/* 3197403Sobrien * 3297403Sobrien * Copyright (c) 1994 3397403Sobrien * Hewlett-Packard Company 3497403Sobrien * 3597403Sobrien * Permission to use, copy, modify, distribute and sell this software 3697403Sobrien * and its documentation for any purpose is hereby granted without fee, 3797403Sobrien * provided that the above copyright notice appear in all copies and 3897403Sobrien * that both that copyright notice and this permission notice appear 3997403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4097403Sobrien * representations about the suitability of this software for any 4197403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4297403Sobrien * 4397403Sobrien * 4497403Sobrien * Copyright (c) 1996 4597403Sobrien * Silicon Graphics Computer Systems, Inc. 4697403Sobrien * 4797403Sobrien * Permission to use, copy, modify, distribute and sell this software 4897403Sobrien * and its documentation for any purpose is hereby granted without fee, 4997403Sobrien * provided that the above copyright notice appear in all copies and 5097403Sobrien * that both that copyright notice and this permission notice appear 5197403Sobrien * in supporting documentation. Silicon Graphics makes no 5297403Sobrien * representations about the suitability of this software for any 5397403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5497403Sobrien */ 5597403Sobrien 5697403Sobrien/** @file stl_algo.h 5797403Sobrien * This is an internal header file, included by other library headers. 5897403Sobrien * You should not attempt to use it directly. 5997403Sobrien */ 6097403Sobrien 6197403Sobrien#ifndef __GLIBCPP_INTERNAL_ALGO_H 6297403Sobrien#define __GLIBCPP_INTERNAL_ALGO_H 6397403Sobrien 6497403Sobrien#include <bits/stl_heap.h> 6597403Sobrien#include <bits/stl_tempbuf.h> // for _Temporary_buffer 6697403Sobrien 6797403Sobrien// See concept_check.h for the __glibcpp_*_requires macros. 6897403Sobrien 6997403Sobriennamespace std 7097403Sobrien{ 7197403Sobrien 7297403Sobrien /** 7397403Sobrien * @brief Find the median of three values. 7497403Sobrien * @param a A value. 7597403Sobrien * @param b A value. 7697403Sobrien * @param c A value. 7797403Sobrien * @return One of @p a, @p b or @p c. 7897403Sobrien * 7997403Sobrien * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n 8097403Sobrien * then the value returned will be @c m. 8197403Sobrien * This is an SGI extension. 8297403Sobrien * @ingroup SGIextensions 8397403Sobrien */ 8497403Sobrien template<typename _Tp> 8597403Sobrien inline const _Tp& 8697403Sobrien __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) 8797403Sobrien { 8897403Sobrien // concept requirements 8997403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 9097403Sobrien if (__a < __b) 9197403Sobrien if (__b < __c) 9297403Sobrien return __b; 9397403Sobrien else if (__a < __c) 9497403Sobrien return __c; 9597403Sobrien else 9697403Sobrien return __a; 9797403Sobrien else if (__a < __c) 9897403Sobrien return __a; 9997403Sobrien else if (__b < __c) 10097403Sobrien return __c; 10197403Sobrien else 10297403Sobrien return __b; 10397403Sobrien } 10497403Sobrien 10597403Sobrien /** 10697403Sobrien * @brief Find the median of three values using a predicate for comparison. 10797403Sobrien * @param a A value. 10897403Sobrien * @param b A value. 10997403Sobrien * @param c A value. 11097403Sobrien * @param comp A binary predicate. 11197403Sobrien * @return One of @p a, @p b or @p c. 11297403Sobrien * 11397403Sobrien * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) 11497403Sobrien * and @p comp(m,n) are both true then the value returned will be @c m. 11597403Sobrien * This is an SGI extension. 11697403Sobrien * @ingroup SGIextensions 11797403Sobrien */ 11897403Sobrien template<typename _Tp, typename _Compare> 11997403Sobrien inline const _Tp& 12097403Sobrien __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) 12197403Sobrien { 12297403Sobrien // concept requirements 12397403Sobrien __glibcpp_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>) 12497403Sobrien if (__comp(__a, __b)) 12597403Sobrien if (__comp(__b, __c)) 12697403Sobrien return __b; 12797403Sobrien else if (__comp(__a, __c)) 12897403Sobrien return __c; 12997403Sobrien else 13097403Sobrien return __a; 13197403Sobrien else if (__comp(__a, __c)) 13297403Sobrien return __a; 13397403Sobrien else if (__comp(__b, __c)) 13497403Sobrien return __c; 13597403Sobrien else 13697403Sobrien return __b; 13797403Sobrien } 13897403Sobrien 13997403Sobrien /** 14097403Sobrien * @brief Apply a function to every element of a sequence. 14197403Sobrien * @param first An input iterator. 14297403Sobrien * @param last An input iterator. 14397403Sobrien * @param f A unary function object. 14497403Sobrien * @return @p f. 14597403Sobrien * 14697403Sobrien * Applies the function object @p f to each element in the range 14797403Sobrien * @p [first,last). @p f must not modify the order of the sequence. 14897403Sobrien * If @p f has a return value it is ignored. 14997403Sobrien */ 15097403Sobrien template<typename _InputIter, typename _Function> 15197403Sobrien _Function 15297403Sobrien for_each(_InputIter __first, _InputIter __last, _Function __f) 15397403Sobrien { 15497403Sobrien // concept requirements 15597403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 15697403Sobrien for ( ; __first != __last; ++__first) 15797403Sobrien __f(*__first); 15897403Sobrien return __f; 15997403Sobrien } 16097403Sobrien 16197403Sobrien /** 16297403Sobrien * @if maint 16397403Sobrien * This is an overload used by find() for the Input Iterator case. 16497403Sobrien * @endif 16597403Sobrien */ 16697403Sobrien template<typename _InputIter, typename _Tp> 16797403Sobrien inline _InputIter 16897403Sobrien find(_InputIter __first, _InputIter __last, 16997403Sobrien const _Tp& __val, 17097403Sobrien input_iterator_tag) 17197403Sobrien { 17297403Sobrien while (__first != __last && !(*__first == __val)) 17397403Sobrien ++__first; 17497403Sobrien return __first; 17597403Sobrien } 17697403Sobrien 17797403Sobrien /** 17897403Sobrien * @if maint 17997403Sobrien * This is an overload used by find_if() for the Input Iterator case. 18097403Sobrien * @endif 18197403Sobrien */ 18297403Sobrien template<typename _InputIter, typename _Predicate> 18397403Sobrien inline _InputIter 18497403Sobrien find_if(_InputIter __first, _InputIter __last, 18597403Sobrien _Predicate __pred, 18697403Sobrien input_iterator_tag) 18797403Sobrien { 18897403Sobrien while (__first != __last && !__pred(*__first)) 18997403Sobrien ++__first; 19097403Sobrien return __first; 19197403Sobrien } 19297403Sobrien 19397403Sobrien /** 19497403Sobrien * @if maint 19597403Sobrien * This is an overload used by find() for the RAI case. 19697403Sobrien * @endif 19797403Sobrien */ 19897403Sobrien template<typename _RandomAccessIter, typename _Tp> 19997403Sobrien _RandomAccessIter 20097403Sobrien find(_RandomAccessIter __first, _RandomAccessIter __last, 20197403Sobrien const _Tp& __val, 20297403Sobrien random_access_iterator_tag) 20397403Sobrien { 20497403Sobrien typename iterator_traits<_RandomAccessIter>::difference_type __trip_count 20597403Sobrien = (__last - __first) >> 2; 20697403Sobrien 20797403Sobrien for ( ; __trip_count > 0 ; --__trip_count) { 20897403Sobrien if (*__first == __val) return __first; 20997403Sobrien ++__first; 21097403Sobrien 21197403Sobrien if (*__first == __val) return __first; 21297403Sobrien ++__first; 21397403Sobrien 21497403Sobrien if (*__first == __val) return __first; 21597403Sobrien ++__first; 21697403Sobrien 21797403Sobrien if (*__first == __val) return __first; 21897403Sobrien ++__first; 21997403Sobrien } 22097403Sobrien 22197403Sobrien switch(__last - __first) { 22297403Sobrien case 3: 22397403Sobrien if (*__first == __val) return __first; 22497403Sobrien ++__first; 22597403Sobrien case 2: 22697403Sobrien if (*__first == __val) return __first; 22797403Sobrien ++__first; 22897403Sobrien case 1: 22997403Sobrien if (*__first == __val) return __first; 23097403Sobrien ++__first; 23197403Sobrien case 0: 23297403Sobrien default: 23397403Sobrien return __last; 23497403Sobrien } 23597403Sobrien } 23697403Sobrien 23797403Sobrien /** 23897403Sobrien * @if maint 23997403Sobrien * This is an overload used by find_if() for the RAI case. 24097403Sobrien * @endif 24197403Sobrien */ 24297403Sobrien template<typename _RandomAccessIter, typename _Predicate> 24397403Sobrien _RandomAccessIter 24497403Sobrien find_if(_RandomAccessIter __first, _RandomAccessIter __last, 24597403Sobrien _Predicate __pred, 24697403Sobrien random_access_iterator_tag) 24797403Sobrien { 24897403Sobrien typename iterator_traits<_RandomAccessIter>::difference_type __trip_count 24997403Sobrien = (__last - __first) >> 2; 25097403Sobrien 25197403Sobrien for ( ; __trip_count > 0 ; --__trip_count) { 25297403Sobrien if (__pred(*__first)) return __first; 25397403Sobrien ++__first; 25497403Sobrien 25597403Sobrien if (__pred(*__first)) return __first; 25697403Sobrien ++__first; 25797403Sobrien 25897403Sobrien if (__pred(*__first)) return __first; 25997403Sobrien ++__first; 26097403Sobrien 26197403Sobrien if (__pred(*__first)) return __first; 26297403Sobrien ++__first; 26397403Sobrien } 26497403Sobrien 26597403Sobrien switch(__last - __first) { 26697403Sobrien case 3: 26797403Sobrien if (__pred(*__first)) return __first; 26897403Sobrien ++__first; 26997403Sobrien case 2: 27097403Sobrien if (__pred(*__first)) return __first; 27197403Sobrien ++__first; 27297403Sobrien case 1: 27397403Sobrien if (__pred(*__first)) return __first; 27497403Sobrien ++__first; 27597403Sobrien case 0: 27697403Sobrien default: 27797403Sobrien return __last; 27897403Sobrien } 27997403Sobrien } 28097403Sobrien 28197403Sobrien /** 28297403Sobrien * @brief Find the first occurrence of a value in a sequence. 28397403Sobrien * @param first An input iterator. 28497403Sobrien * @param last An input iterator. 28597403Sobrien * @param val The value to find. 28697403Sobrien * @return The first iterator @c i in the range @p [first,last) 28797403Sobrien * such that @c *i == @p val, or @p last if no such iterator exists. 28897403Sobrien */ 28997403Sobrien template<typename _InputIter, typename _Tp> 29097403Sobrien inline _InputIter 29197403Sobrien find(_InputIter __first, _InputIter __last, 29297403Sobrien const _Tp& __val) 29397403Sobrien { 29497403Sobrien // concept requirements 29597403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 29697403Sobrien __glibcpp_function_requires(_EqualOpConcept< 29797403Sobrien typename iterator_traits<_InputIter>::value_type, _Tp>) 29897403Sobrien return find(__first, __last, __val, __iterator_category(__first)); 29997403Sobrien } 30097403Sobrien 30197403Sobrien /** 30297403Sobrien * @brief Find the first element in a sequence for which a predicate is true. 30397403Sobrien * @param first An input iterator. 30497403Sobrien * @param last An input iterator. 30597403Sobrien * @param pred A predicate. 30697403Sobrien * @return The first iterator @c i in the range @p [first,last) 30797403Sobrien * such that @p pred(*i) is true, or @p last if no such iterator exists. 30897403Sobrien */ 30997403Sobrien template<typename _InputIter, typename _Predicate> 31097403Sobrien inline _InputIter 31197403Sobrien find_if(_InputIter __first, _InputIter __last, 31297403Sobrien _Predicate __pred) 31397403Sobrien { 31497403Sobrien // concept requirements 31597403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 31697403Sobrien __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 31797403Sobrien typename iterator_traits<_InputIter>::value_type>) 31897403Sobrien return find_if(__first, __last, __pred, __iterator_category(__first)); 31997403Sobrien } 32097403Sobrien 32197403Sobrien /** 32297403Sobrien * @brief Find two adjacent values in a sequence that are equal. 32397403Sobrien * @param first A forward iterator. 32497403Sobrien * @param last A forward iterator. 32597403Sobrien * @return The first iterator @c i such that @c i and @c i+1 are both 32697403Sobrien * valid iterators in @p [first,last) and such that @c *i == @c *(i+1), 32797403Sobrien * or @p last if no such iterator exists. 32897403Sobrien */ 32997403Sobrien template<typename _ForwardIter> 33097403Sobrien _ForwardIter 33197403Sobrien adjacent_find(_ForwardIter __first, _ForwardIter __last) 33297403Sobrien { 33397403Sobrien // concept requirements 33497403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 33597403Sobrien __glibcpp_function_requires(_EqualityComparableConcept< 33697403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 33797403Sobrien if (__first == __last) 33897403Sobrien return __last; 33997403Sobrien _ForwardIter __next = __first; 34097403Sobrien while(++__next != __last) { 34197403Sobrien if (*__first == *__next) 34297403Sobrien return __first; 34397403Sobrien __first = __next; 34497403Sobrien } 34597403Sobrien return __last; 34697403Sobrien } 34797403Sobrien 34897403Sobrien /** 34997403Sobrien * @brief Find two adjacent values in a sequence using a predicate. 35097403Sobrien * @param first A forward iterator. 35197403Sobrien * @param last A forward iterator. 35297403Sobrien * @param binary_pred A binary predicate. 35397403Sobrien * @return The first iterator @c i such that @c i and @c i+1 are both 35497403Sobrien * valid iterators in @p [first,last) and such that 35597403Sobrien * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator 35697403Sobrien * exists. 35797403Sobrien */ 35897403Sobrien template<typename _ForwardIter, typename _BinaryPredicate> 35997403Sobrien _ForwardIter 36097403Sobrien adjacent_find(_ForwardIter __first, _ForwardIter __last, 36197403Sobrien _BinaryPredicate __binary_pred) 36297403Sobrien { 36397403Sobrien // concept requirements 36497403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 36597403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 36697403Sobrien typename iterator_traits<_ForwardIter>::value_type, 36797403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 36897403Sobrien if (__first == __last) 36997403Sobrien return __last; 37097403Sobrien _ForwardIter __next = __first; 37197403Sobrien while(++__next != __last) { 37297403Sobrien if (__binary_pred(*__first, *__next)) 37397403Sobrien return __first; 37497403Sobrien __first = __next; 37597403Sobrien } 37697403Sobrien return __last; 37797403Sobrien } 37897403Sobrien 37997403Sobrien /** 38097403Sobrien * @brief Count the number of copies of a value in a sequence. 38197403Sobrien * @param first An input iterator. 38297403Sobrien * @param last An input iterator. 38397403Sobrien * @param value The value to be counted. 38497403Sobrien * @return The number of iterators @c i in the range @p [first,last) 38597403Sobrien * for which @c *i == @p value 38697403Sobrien */ 38797403Sobrien template<typename _InputIter, typename _Tp> 38897403Sobrien typename iterator_traits<_InputIter>::difference_type 38997403Sobrien count(_InputIter __first, _InputIter __last, const _Tp& __value) 39097403Sobrien { 39197403Sobrien // concept requirements 39297403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 39397403Sobrien __glibcpp_function_requires(_EqualityComparableConcept< 39497403Sobrien typename iterator_traits<_InputIter>::value_type >) 39597403Sobrien __glibcpp_function_requires(_EqualityComparableConcept<_Tp>) 39697403Sobrien typename iterator_traits<_InputIter>::difference_type __n = 0; 39797403Sobrien for ( ; __first != __last; ++__first) 39897403Sobrien if (*__first == __value) 39997403Sobrien ++__n; 40097403Sobrien return __n; 40197403Sobrien } 40297403Sobrien 40397403Sobrien /** 40497403Sobrien * @brief Count the elements of a sequence for which a predicate is true. 40597403Sobrien * @param first An input iterator. 40697403Sobrien * @param last An input iterator. 40797403Sobrien * @param pred A predicate. 40897403Sobrien * @return The number of iterators @c i in the range @p [first,last) 40997403Sobrien * for which @p pred(*i) is true. 41097403Sobrien */ 41197403Sobrien template<typename _InputIter, typename _Predicate> 41297403Sobrien typename iterator_traits<_InputIter>::difference_type 41397403Sobrien count_if(_InputIter __first, _InputIter __last, _Predicate __pred) 41497403Sobrien { 41597403Sobrien // concept requirements 41697403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 41797403Sobrien __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 41897403Sobrien typename iterator_traits<_InputIter>::value_type>) 41997403Sobrien typename iterator_traits<_InputIter>::difference_type __n = 0; 42097403Sobrien for ( ; __first != __last; ++__first) 42197403Sobrien if (__pred(*__first)) 42297403Sobrien ++__n; 42397403Sobrien return __n; 42497403Sobrien } 42597403Sobrien 42697403Sobrien 42797403Sobrien /** 42897403Sobrien * @brief Search a sequence for a matching sub-sequence. 42997403Sobrien * @param first1 A forward iterator. 43097403Sobrien * @param last1 A forward iterator. 43197403Sobrien * @param first2 A forward iterator. 43297403Sobrien * @param last2 A forward iterator. 43397403Sobrien * @return The first iterator @c i in the range 43497403Sobrien * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) 43597403Sobrien * for each @c N in the range @p [0,last2-first2), or @p last1 if no 43697403Sobrien * such iterator exists. 43797403Sobrien * 43897403Sobrien * Searches the range @p [first1,last1) for a sub-sequence that compares 43997403Sobrien * equal value-by-value with the sequence given by @p [first2,last2) and 44097403Sobrien * returns an iterator to the first element of the sub-sequence, or 44197403Sobrien * @p last1 if the sub-sequence is not found. 44297403Sobrien * 44397403Sobrien * Because the sub-sequence must lie completely within the range 44497403Sobrien * @p [first1,last1) it must start at a position less than 44597403Sobrien * @p last1-(last2-first2) where @p last2-first2 is the length of the 44697403Sobrien * sub-sequence. 44797403Sobrien * This means that the returned iterator @c i will be in the range 44897403Sobrien * @p [first1,last1-(last2-first2)) 44997403Sobrien */ 45097403Sobrien template<typename _ForwardIter1, typename _ForwardIter2> 45197403Sobrien _ForwardIter1 45297403Sobrien search(_ForwardIter1 __first1, _ForwardIter1 __last1, 45397403Sobrien _ForwardIter2 __first2, _ForwardIter2 __last2) 45497403Sobrien { 45597403Sobrien // concept requirements 45697403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 45797403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 45897403Sobrien __glibcpp_function_requires(_EqualOpConcept< 45997403Sobrien typename iterator_traits<_ForwardIter1>::value_type, 46097403Sobrien typename iterator_traits<_ForwardIter2>::value_type>) 46197403Sobrien 46297403Sobrien // Test for empty ranges 46397403Sobrien if (__first1 == __last1 || __first2 == __last2) 46497403Sobrien return __first1; 46597403Sobrien 46697403Sobrien // Test for a pattern of length 1. 46797403Sobrien _ForwardIter2 __tmp(__first2); 46897403Sobrien ++__tmp; 46997403Sobrien if (__tmp == __last2) 47097403Sobrien return find(__first1, __last1, *__first2); 47197403Sobrien 47297403Sobrien // General case. 47397403Sobrien 47497403Sobrien _ForwardIter2 __p1, __p; 47597403Sobrien 47697403Sobrien __p1 = __first2; ++__p1; 47797403Sobrien 47897403Sobrien _ForwardIter1 __current = __first1; 47997403Sobrien 48097403Sobrien while (__first1 != __last1) { 48197403Sobrien __first1 = find(__first1, __last1, *__first2); 48297403Sobrien if (__first1 == __last1) 48397403Sobrien return __last1; 48497403Sobrien 48597403Sobrien __p = __p1; 48697403Sobrien __current = __first1; 48797403Sobrien if (++__current == __last1) 48897403Sobrien return __last1; 48997403Sobrien 49097403Sobrien while (*__current == *__p) { 49197403Sobrien if (++__p == __last2) 49297403Sobrien return __first1; 49397403Sobrien if (++__current == __last1) 49497403Sobrien return __last1; 49597403Sobrien } 49697403Sobrien 49797403Sobrien ++__first1; 49897403Sobrien } 49997403Sobrien return __first1; 50097403Sobrien } 50197403Sobrien 50297403Sobrien /** 50397403Sobrien * @brief Search a sequence for a matching sub-sequence using a predicate. 50497403Sobrien * @param first1 A forward iterator. 50597403Sobrien * @param last1 A forward iterator. 50697403Sobrien * @param first2 A forward iterator. 50797403Sobrien * @param last2 A forward iterator. 50897403Sobrien * @param predicate A binary predicate. 50997403Sobrien * @return The first iterator @c i in the range 51097403Sobrien * @p [first1,last1-(last2-first2)) such that 51197403Sobrien * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range 51297403Sobrien * @p [0,last2-first2), or @p last1 if no such iterator exists. 51397403Sobrien * 51497403Sobrien * Searches the range @p [first1,last1) for a sub-sequence that compares 51597403Sobrien * equal value-by-value with the sequence given by @p [first2,last2), 51697403Sobrien * using @p predicate to determine equality, and returns an iterator 51797403Sobrien * to the first element of the sub-sequence, or @p last1 if no such 51897403Sobrien * iterator exists. 51997403Sobrien * 52097403Sobrien * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 52197403Sobrien */ 52297403Sobrien template<typename _ForwardIter1, typename _ForwardIter2, typename _BinaryPred> 52397403Sobrien _ForwardIter1 52497403Sobrien search(_ForwardIter1 __first1, _ForwardIter1 __last1, 52597403Sobrien _ForwardIter2 __first2, _ForwardIter2 __last2, 52697403Sobrien _BinaryPred __predicate) 52797403Sobrien { 52897403Sobrien // concept requirements 52997403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 53097403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 53197403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred, 53297403Sobrien typename iterator_traits<_ForwardIter1>::value_type, 53397403Sobrien typename iterator_traits<_ForwardIter2>::value_type>) 53497403Sobrien 53597403Sobrien // Test for empty ranges 53697403Sobrien if (__first1 == __last1 || __first2 == __last2) 53797403Sobrien return __first1; 53897403Sobrien 53997403Sobrien // Test for a pattern of length 1. 54097403Sobrien _ForwardIter2 __tmp(__first2); 54197403Sobrien ++__tmp; 54297403Sobrien if (__tmp == __last2) { 54397403Sobrien while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 54497403Sobrien ++__first1; 54597403Sobrien return __first1; 54697403Sobrien } 54797403Sobrien 54897403Sobrien // General case. 54997403Sobrien 55097403Sobrien _ForwardIter2 __p1, __p; 55197403Sobrien 55297403Sobrien __p1 = __first2; ++__p1; 55397403Sobrien 55497403Sobrien _ForwardIter1 __current = __first1; 55597403Sobrien 55697403Sobrien while (__first1 != __last1) { 55797403Sobrien while (__first1 != __last1) { 55897403Sobrien if (__predicate(*__first1, *__first2)) 55997403Sobrien break; 56097403Sobrien ++__first1; 56197403Sobrien } 56297403Sobrien while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 56397403Sobrien ++__first1; 56497403Sobrien if (__first1 == __last1) 56597403Sobrien return __last1; 56697403Sobrien 56797403Sobrien __p = __p1; 56897403Sobrien __current = __first1; 56997403Sobrien if (++__current == __last1) return __last1; 57097403Sobrien 57197403Sobrien while (__predicate(*__current, *__p)) { 57297403Sobrien if (++__p == __last2) 57397403Sobrien return __first1; 57497403Sobrien if (++__current == __last1) 57597403Sobrien return __last1; 57697403Sobrien } 57797403Sobrien 57897403Sobrien ++__first1; 57997403Sobrien } 58097403Sobrien return __first1; 58197403Sobrien } 58297403Sobrien 58397403Sobrien /** 58497403Sobrien * @brief Search a sequence for a number of consecutive values. 58597403Sobrien * @param first A forward iterator. 58697403Sobrien * @param last A forward iterator. 58797403Sobrien * @param count The number of consecutive values. 58897403Sobrien * @param val The value to find. 58997403Sobrien * @return The first iterator @c i in the range @p [first,last-count) 59097403Sobrien * such that @c *(i+N) == @p val for each @c N in the range @p [0,count), 59197403Sobrien * or @p last if no such iterator exists. 59297403Sobrien * 59397403Sobrien * Searches the range @p [first,last) for @p count consecutive elements 59497403Sobrien * equal to @p val. 59597403Sobrien */ 59697403Sobrien template<typename _ForwardIter, typename _Integer, typename _Tp> 59797403Sobrien _ForwardIter 59897403Sobrien search_n(_ForwardIter __first, _ForwardIter __last, 59997403Sobrien _Integer __count, const _Tp& __val) 60097403Sobrien { 60197403Sobrien // concept requirements 60297403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 60397403Sobrien __glibcpp_function_requires(_EqualityComparableConcept< 60497403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 60597403Sobrien __glibcpp_function_requires(_EqualityComparableConcept<_Tp>) 60697403Sobrien 60797403Sobrien if (__count <= 0) 60897403Sobrien return __first; 60997403Sobrien else { 61097403Sobrien __first = find(__first, __last, __val); 61197403Sobrien while (__first != __last) { 61297403Sobrien _Integer __n = __count - 1; 61397403Sobrien _ForwardIter __i = __first; 61497403Sobrien ++__i; 61597403Sobrien while (__i != __last && __n != 0 && *__i == __val) { 61697403Sobrien ++__i; 61797403Sobrien --__n; 61897403Sobrien } 61997403Sobrien if (__n == 0) 62097403Sobrien return __first; 62197403Sobrien else 62297403Sobrien __first = find(__i, __last, __val); 62397403Sobrien } 62497403Sobrien return __last; 62597403Sobrien } 62697403Sobrien } 62797403Sobrien 62897403Sobrien /** 62997403Sobrien * @brief Search a sequence for a number of consecutive values using a 63097403Sobrien * predicate. 63197403Sobrien * @param first A forward iterator. 63297403Sobrien * @param last A forward iterator. 63397403Sobrien * @param count The number of consecutive values. 63497403Sobrien * @param val The value to find. 63597403Sobrien * @param binary_pred A binary predicate. 63697403Sobrien * @return The first iterator @c i in the range @p [first,last-count) 63797403Sobrien * such that @p binary_pred(*(i+N),val) is true for each @c N in the 63897403Sobrien * range @p [0,count), or @p last if no such iterator exists. 63997403Sobrien * 64097403Sobrien * Searches the range @p [first,last) for @p count consecutive elements 64197403Sobrien * for which the predicate returns true. 64297403Sobrien */ 64397403Sobrien template<typename _ForwardIter, typename _Integer, typename _Tp, 64497403Sobrien typename _BinaryPred> 64597403Sobrien _ForwardIter 64697403Sobrien search_n(_ForwardIter __first, _ForwardIter __last, 64797403Sobrien _Integer __count, const _Tp& __val, 64897403Sobrien _BinaryPred __binary_pred) 64997403Sobrien { 65097403Sobrien // concept requirements 65197403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 65297403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred, 65397403Sobrien typename iterator_traits<_ForwardIter>::value_type, _Tp>) 65497403Sobrien 65597403Sobrien if (__count <= 0) 65697403Sobrien return __first; 65797403Sobrien else { 65897403Sobrien while (__first != __last) { 65997403Sobrien if (__binary_pred(*__first, __val)) 66097403Sobrien break; 66197403Sobrien ++__first; 66297403Sobrien } 66397403Sobrien while (__first != __last) { 66497403Sobrien _Integer __n = __count - 1; 66597403Sobrien _ForwardIter __i = __first; 66697403Sobrien ++__i; 66797403Sobrien while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) { 66897403Sobrien ++__i; 66997403Sobrien --__n; 67097403Sobrien } 67197403Sobrien if (__n == 0) 67297403Sobrien return __first; 67397403Sobrien else { 67497403Sobrien while (__i != __last) { 67597403Sobrien if (__binary_pred(*__i, __val)) 67697403Sobrien break; 67797403Sobrien ++__i; 67897403Sobrien } 67997403Sobrien __first = __i; 68097403Sobrien } 68197403Sobrien } 68297403Sobrien return __last; 68397403Sobrien } 68497403Sobrien } 68597403Sobrien 68697403Sobrien /** 68797403Sobrien * @brief Swap the elements of two sequences. 68897403Sobrien * @param first1 A forward iterator. 68997403Sobrien * @param last1 A forward iterator. 69097403Sobrien * @param first2 A forward iterator. 69197403Sobrien * @return An iterator equal to @p first2+(last1-first1). 69297403Sobrien * 69397403Sobrien * Swaps each element in the range @p [first1,last1) with the 69497403Sobrien * corresponding element in the range @p [first2,(last1-first1)). 69597403Sobrien * The ranges must not overlap. 69697403Sobrien */ 69797403Sobrien template<typename _ForwardIter1, typename _ForwardIter2> 69897403Sobrien _ForwardIter2 69997403Sobrien swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, 70097403Sobrien _ForwardIter2 __first2) 70197403Sobrien { 70297403Sobrien // concept requirements 70397403Sobrien __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>) 70497403Sobrien __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>) 70597403Sobrien __glibcpp_function_requires(_ConvertibleConcept< 70697403Sobrien typename iterator_traits<_ForwardIter1>::value_type, 70797403Sobrien typename iterator_traits<_ForwardIter2>::value_type>) 70897403Sobrien __glibcpp_function_requires(_ConvertibleConcept< 70997403Sobrien typename iterator_traits<_ForwardIter2>::value_type, 71097403Sobrien typename iterator_traits<_ForwardIter1>::value_type>) 71197403Sobrien 71297403Sobrien for ( ; __first1 != __last1; ++__first1, ++__first2) 71397403Sobrien iter_swap(__first1, __first2); 71497403Sobrien return __first2; 71597403Sobrien } 71697403Sobrien 71797403Sobrien /** 71897403Sobrien * @brief Perform an operation on a sequence. 71997403Sobrien * @param first An input iterator. 72097403Sobrien * @param last An input iterator. 72197403Sobrien * @param result An output iterator. 72297403Sobrien * @param unary_op A unary operator. 72397403Sobrien * @return An output iterator equal to @p result+(last-first). 72497403Sobrien * 72597403Sobrien * Applies the operator to each element in the input range and assigns 72697403Sobrien * the results to successive elements of the output sequence. 72797403Sobrien * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the 72897403Sobrien * range @p [0,last-first). 72997403Sobrien * 73097403Sobrien * @p unary_op must not alter its argument. 73197403Sobrien */ 73297403Sobrien template<typename _InputIter, typename _OutputIter, typename _UnaryOperation> 73397403Sobrien _OutputIter 73497403Sobrien transform(_InputIter __first, _InputIter __last, 73597403Sobrien _OutputIter __result, _UnaryOperation __unary_op) 73697403Sobrien { 73797403Sobrien // concept requirements 73897403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 73997403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 74097403Sobrien // "the type returned by a _UnaryOperation" 74197403Sobrien __typeof__(__unary_op(*__first))>) 74297403Sobrien 74397403Sobrien for ( ; __first != __last; ++__first, ++__result) 74497403Sobrien *__result = __unary_op(*__first); 74597403Sobrien return __result; 74697403Sobrien } 74797403Sobrien 74897403Sobrien /** 74997403Sobrien * @brief Perform an operation on corresponding elements of two sequences. 75097403Sobrien * @param first1 An input iterator. 75197403Sobrien * @param last1 An input iterator. 75297403Sobrien * @param first2 An input iterator. 75397403Sobrien * @param result An output iterator. 75497403Sobrien * @param binary_op A binary operator. 75597403Sobrien * @return An output iterator equal to @p result+(last-first). 75697403Sobrien * 75797403Sobrien * Applies the operator to the corresponding elements in the two 75897403Sobrien * input ranges and assigns the results to successive elements of the 75997403Sobrien * output sequence. 76097403Sobrien * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each 76197403Sobrien * @c N in the range @p [0,last1-first1). 76297403Sobrien * 76397403Sobrien * @p binary_op must not alter either of its arguments. 76497403Sobrien */ 76597403Sobrien template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 76697403Sobrien typename _BinaryOperation> 76797403Sobrien _OutputIter 76897403Sobrien transform(_InputIter1 __first1, _InputIter1 __last1, 76997403Sobrien _InputIter2 __first2, _OutputIter __result, 77097403Sobrien _BinaryOperation __binary_op) 77197403Sobrien { 77297403Sobrien // concept requirements 77397403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 77497403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 77597403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 77697403Sobrien // "the type returned by a _BinaryOperation" 77797403Sobrien __typeof__(__binary_op(*__first1,*__first2))>) 77897403Sobrien 77997403Sobrien for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) 78097403Sobrien *__result = __binary_op(*__first1, *__first2); 78197403Sobrien return __result; 78297403Sobrien } 78397403Sobrien 78497403Sobrien /** 78597403Sobrien * @brief Replace each occurrence of one value in a sequence with another 78697403Sobrien * value. 78797403Sobrien * @param first A forward iterator. 78897403Sobrien * @param last A forward iterator. 78997403Sobrien * @param old_value The value to be replaced. 79097403Sobrien * @param new_value The replacement value. 79197403Sobrien * @return replace() returns no value. 79297403Sobrien * 79397403Sobrien * For each iterator @c i in the range @p [first,last) if @c *i == 79497403Sobrien * @p old_value then the assignment @c *i = @p new_value is performed. 79597403Sobrien */ 79697403Sobrien template<typename _ForwardIter, typename _Tp> 79797403Sobrien void 79897403Sobrien replace(_ForwardIter __first, _ForwardIter __last, 79997403Sobrien const _Tp& __old_value, const _Tp& __new_value) 80097403Sobrien { 80197403Sobrien // concept requirements 80297403Sobrien __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 80397403Sobrien __glibcpp_function_requires(_EqualOpConcept< 80497403Sobrien typename iterator_traits<_ForwardIter>::value_type, _Tp>) 80597403Sobrien __glibcpp_function_requires(_ConvertibleConcept<_Tp, 80697403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 80797403Sobrien 80897403Sobrien for ( ; __first != __last; ++__first) 80997403Sobrien if (*__first == __old_value) 81097403Sobrien *__first = __new_value; 81197403Sobrien } 81297403Sobrien 81397403Sobrien /** 81497403Sobrien * @brief Replace each value in a sequence for which a predicate returns 81597403Sobrien * true with another value. 81697403Sobrien * @param first A forward iterator. 81797403Sobrien * @param last A forward iterator. 81897403Sobrien * @param pred A predicate. 81997403Sobrien * @param new_value The replacement value. 82097403Sobrien * @return replace_if() returns no value. 82197403Sobrien * 82297403Sobrien * For each iterator @c i in the range @p [first,last) if @p pred(*i) 82397403Sobrien * is true then the assignment @c *i = @p new_value is performed. 82497403Sobrien */ 82597403Sobrien template<typename _ForwardIter, typename _Predicate, typename _Tp> 82697403Sobrien void 82797403Sobrien replace_if(_ForwardIter __first, _ForwardIter __last, 82897403Sobrien _Predicate __pred, const _Tp& __new_value) 82997403Sobrien { 83097403Sobrien // concept requirements 83197403Sobrien __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 83297403Sobrien __glibcpp_function_requires(_ConvertibleConcept<_Tp, 83397403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 83497403Sobrien __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 83597403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 83697403Sobrien 83797403Sobrien for ( ; __first != __last; ++__first) 83897403Sobrien if (__pred(*__first)) 83997403Sobrien *__first = __new_value; 84097403Sobrien } 84197403Sobrien 84297403Sobrien /** 84397403Sobrien * @brief Copy a sequence, replacing each element of one value with another 84497403Sobrien * value. 84597403Sobrien * @param first An input iterator. 84697403Sobrien * @param last An input iterator. 84797403Sobrien * @param result An output iterator. 84897403Sobrien * @param old_value The value to be replaced. 84997403Sobrien * @param new_value The replacement value. 85097403Sobrien * @return The end of the output sequence, @p result+(last-first). 85197403Sobrien * 85297403Sobrien * Copies each element in the input range @p [first,last) to the 85397403Sobrien * output range @p [result,result+(last-first)) replacing elements 85497403Sobrien * equal to @p old_value with @p new_value. 85597403Sobrien */ 85697403Sobrien template<typename _InputIter, typename _OutputIter, typename _Tp> 85797403Sobrien _OutputIter 85897403Sobrien replace_copy(_InputIter __first, _InputIter __last, 85997403Sobrien _OutputIter __result, 86097403Sobrien const _Tp& __old_value, const _Tp& __new_value) 86197403Sobrien { 86297403Sobrien // concept requirements 86397403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 86497403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 86597403Sobrien typename iterator_traits<_InputIter>::value_type>) 86697403Sobrien __glibcpp_function_requires(_EqualOpConcept< 86797403Sobrien typename iterator_traits<_InputIter>::value_type, _Tp>) 86897403Sobrien 86997403Sobrien for ( ; __first != __last; ++__first, ++__result) 87097403Sobrien *__result = *__first == __old_value ? __new_value : *__first; 87197403Sobrien return __result; 87297403Sobrien } 87397403Sobrien 87497403Sobrien /** 87597403Sobrien * @brief Copy a sequence, replacing each value for which a predicate 87697403Sobrien * returns true with another value. 87797403Sobrien * @param first An input iterator. 87897403Sobrien * @param last An input iterator. 87997403Sobrien * @param result An output iterator. 88097403Sobrien * @param pred A predicate. 88197403Sobrien * @param new_value The replacement value. 88297403Sobrien * @return The end of the output sequence, @p result+(last-first). 88397403Sobrien * 88497403Sobrien * Copies each element in the range @p [first,last) to the range 88597403Sobrien * @p [result,result+(last-first)) replacing elements for which 88697403Sobrien * @p pred returns true with @p new_value. 88797403Sobrien */ 88897403Sobrien template<typename _InputIter, typename _OutputIter, typename _Predicate, 88997403Sobrien typename _Tp> 89097403Sobrien _OutputIter 89197403Sobrien replace_copy_if(_InputIter __first, _InputIter __last, 89297403Sobrien _OutputIter __result, 89397403Sobrien _Predicate __pred, const _Tp& __new_value) 89497403Sobrien { 89597403Sobrien // concept requirements 89697403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 89797403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 89897403Sobrien typename iterator_traits<_InputIter>::value_type>) 89997403Sobrien __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 90097403Sobrien typename iterator_traits<_InputIter>::value_type>) 90197403Sobrien 90297403Sobrien for ( ; __first != __last; ++__first, ++__result) 90397403Sobrien *__result = __pred(*__first) ? __new_value : *__first; 90497403Sobrien return __result; 90597403Sobrien } 90697403Sobrien 90797403Sobrien /** 90897403Sobrien * @brief Assign the result of a function object to each value in a 90997403Sobrien * sequence. 91097403Sobrien * @param first A forward iterator. 91197403Sobrien * @param last A forward iterator. 91297403Sobrien * @param gen A function object taking no arguments. 91397403Sobrien * @return generate() returns no value. 91497403Sobrien * 91597403Sobrien * Performs the assignment @c *i = @p gen() for each @c i in the range 91697403Sobrien * @p [first,last). 91797403Sobrien */ 91897403Sobrien template<typename _ForwardIter, typename _Generator> 91997403Sobrien void 92097403Sobrien generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) 92197403Sobrien { 92297403Sobrien // concept requirements 92397403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 92497403Sobrien __glibcpp_function_requires(_GeneratorConcept<_Generator, 92597403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 92697403Sobrien 92797403Sobrien for ( ; __first != __last; ++__first) 92897403Sobrien *__first = __gen(); 92997403Sobrien } 93097403Sobrien 93197403Sobrien /** 93297403Sobrien * @brief Assign the result of a function object to each value in a 93397403Sobrien * sequence. 93497403Sobrien * @param first A forward iterator. 93597403Sobrien * @param n The length of the sequence. 93697403Sobrien * @param gen A function object taking no arguments. 93797403Sobrien * @return The end of the sequence, @p first+n 93897403Sobrien * 93997403Sobrien * Performs the assignment @c *i = @p gen() for each @c i in the range 94097403Sobrien * @p [first,first+n). 94197403Sobrien */ 94297403Sobrien template<typename _OutputIter, typename _Size, typename _Generator> 94397403Sobrien _OutputIter 94497403Sobrien generate_n(_OutputIter __first, _Size __n, _Generator __gen) 94597403Sobrien { 94697403Sobrien // concept requirements 94797403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 94897403Sobrien // "the type returned by a _Generator" 94997403Sobrien __typeof__(gen())>) 95097403Sobrien 95197403Sobrien for ( ; __n > 0; --__n, ++__first) 95297403Sobrien *__first = __gen(); 95397403Sobrien return __first; 95497403Sobrien } 95597403Sobrien 95697403Sobrien /** 95797403Sobrien * @brief Copy a sequence, removing elements of a given value. 95897403Sobrien * @param first An input iterator. 95997403Sobrien * @param last An input iterator. 96097403Sobrien * @param result An output iterator. 96197403Sobrien * @param value The value to be removed. 96297403Sobrien * @return An iterator designating the end of the resulting sequence. 96397403Sobrien * 96497403Sobrien * Copies each element in the range @p [first,last) not equal to @p value 96597403Sobrien * to the range beginning at @p result. 96697403Sobrien * remove_copy() is stable, so the relative order of elements that are 96797403Sobrien * copied is unchanged. 96897403Sobrien */ 96997403Sobrien template<typename _InputIter, typename _OutputIter, typename _Tp> 97097403Sobrien _OutputIter 97197403Sobrien remove_copy(_InputIter __first, _InputIter __last, 97297403Sobrien _OutputIter __result, const _Tp& __value) 97397403Sobrien { 97497403Sobrien // concept requirements 97597403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 97697403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 97797403Sobrien typename iterator_traits<_InputIter>::value_type>) 97897403Sobrien __glibcpp_function_requires(_EqualOpConcept< 97997403Sobrien typename iterator_traits<_InputIter>::value_type, _Tp>) 98097403Sobrien 98197403Sobrien for ( ; __first != __last; ++__first) 98297403Sobrien if (!(*__first == __value)) { 98397403Sobrien *__result = *__first; 98497403Sobrien ++__result; 98597403Sobrien } 98697403Sobrien return __result; 98797403Sobrien } 98897403Sobrien 98997403Sobrien /** 99097403Sobrien * @brief Copy a sequence, removing elements for which a predicate is true. 99197403Sobrien * @param first An input iterator. 99297403Sobrien * @param last An input iterator. 99397403Sobrien * @param result An output iterator. 99497403Sobrien * @param pred A predicate. 99597403Sobrien * @return An iterator designating the end of the resulting sequence. 99697403Sobrien * 99797403Sobrien * Copies each element in the range @p [first,last) for which 99897403Sobrien * @p pred returns true to the range beginning at @p result. 99997403Sobrien * 100097403Sobrien * remove_copy_if() is stable, so the relative order of elements that are 100197403Sobrien * copied is unchanged. 100297403Sobrien */ 100397403Sobrien template<typename _InputIter, typename _OutputIter, typename _Predicate> 100497403Sobrien _OutputIter 100597403Sobrien remove_copy_if(_InputIter __first, _InputIter __last, 100697403Sobrien _OutputIter __result, _Predicate __pred) 100797403Sobrien { 100897403Sobrien // concept requirements 100997403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 101097403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 101197403Sobrien typename iterator_traits<_InputIter>::value_type>) 101297403Sobrien __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 101397403Sobrien typename iterator_traits<_InputIter>::value_type>) 101497403Sobrien 101597403Sobrien for ( ; __first != __last; ++__first) 101697403Sobrien if (!__pred(*__first)) { 101797403Sobrien *__result = *__first; 101897403Sobrien ++__result; 101997403Sobrien } 102097403Sobrien return __result; 102197403Sobrien } 102297403Sobrien 102397403Sobrien /** 102497403Sobrien * @brief Remove elements from a sequence. 102597403Sobrien * @param first An input iterator. 102697403Sobrien * @param last An input iterator. 102797403Sobrien * @param value The value to be removed. 102897403Sobrien * @return An iterator designating the end of the resulting sequence. 102997403Sobrien * 103097403Sobrien * All elements equal to @p value are removed from the range 103197403Sobrien * @p [first,last). 103297403Sobrien * 103397403Sobrien * remove() is stable, so the relative order of elements that are 103497403Sobrien * not removed is unchanged. 103597403Sobrien * 103697403Sobrien * Elements between the end of the resulting sequence and @p last 103797403Sobrien * are still present, but their value is unspecified. 103897403Sobrien */ 103997403Sobrien template<typename _ForwardIter, typename _Tp> 104097403Sobrien _ForwardIter 104197403Sobrien remove(_ForwardIter __first, _ForwardIter __last, 104297403Sobrien const _Tp& __value) 104397403Sobrien { 104497403Sobrien // concept requirements 104597403Sobrien __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 104697403Sobrien __glibcpp_function_requires(_ConvertibleConcept<_Tp, 104797403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 104897403Sobrien __glibcpp_function_requires(_EqualOpConcept< 104997403Sobrien typename iterator_traits<_ForwardIter>::value_type, _Tp>) 105097403Sobrien 105197403Sobrien __first = find(__first, __last, __value); 105297403Sobrien _ForwardIter __i = __first; 105397403Sobrien return __first == __last ? __first 105497403Sobrien : remove_copy(++__i, __last, __first, __value); 105597403Sobrien } 105697403Sobrien 105797403Sobrien /** 105897403Sobrien * @brief Remove elements from a sequence using a predicate. 105997403Sobrien * @param first A forward iterator. 106097403Sobrien * @param last A forward iterator. 106197403Sobrien * @param pred A predicate. 106297403Sobrien * @return An iterator designating the end of the resulting sequence. 106397403Sobrien * 106497403Sobrien * All elements for which @p pred returns true are removed from the range 106597403Sobrien * @p [first,last). 106697403Sobrien * 106797403Sobrien * remove_if() is stable, so the relative order of elements that are 106897403Sobrien * not removed is unchanged. 106997403Sobrien * 107097403Sobrien * Elements between the end of the resulting sequence and @p last 107197403Sobrien * are still present, but their value is unspecified. 107297403Sobrien */ 107397403Sobrien template<typename _ForwardIter, typename _Predicate> 107497403Sobrien _ForwardIter 107597403Sobrien remove_if(_ForwardIter __first, _ForwardIter __last, 107697403Sobrien _Predicate __pred) 107797403Sobrien { 107897403Sobrien // concept requirements 107997403Sobrien __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 108097403Sobrien __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 108197403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 108297403Sobrien 108397403Sobrien __first = find_if(__first, __last, __pred); 108497403Sobrien _ForwardIter __i = __first; 108597403Sobrien return __first == __last ? __first 108697403Sobrien : remove_copy_if(++__i, __last, __first, __pred); 108797403Sobrien } 108897403Sobrien 108997403Sobrien /** 109097403Sobrien * @if maint 109197403Sobrien * This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter) 109297403Sobrien * overloaded for output iterators. 109397403Sobrien * @endif 109497403Sobrien */ 109597403Sobrien template<typename _InputIter, typename _OutputIter> 109697403Sobrien _OutputIter 109797403Sobrien __unique_copy(_InputIter __first, _InputIter __last, 109897403Sobrien _OutputIter __result, 109997403Sobrien output_iterator_tag) 110097403Sobrien { 110197403Sobrien // concept requirements -- taken care of in dispatching function 110297403Sobrien typename iterator_traits<_InputIter>::value_type __value = *__first; 110397403Sobrien *__result = __value; 110497403Sobrien while (++__first != __last) 110597403Sobrien if (!(__value == *__first)) { 110697403Sobrien __value = *__first; 110797403Sobrien *++__result = __value; 110897403Sobrien } 110997403Sobrien return ++__result; 111097403Sobrien } 111197403Sobrien 111297403Sobrien /** 111397403Sobrien * @if maint 111497403Sobrien * This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter) 111597403Sobrien * overloaded for forward iterators. 111697403Sobrien * @endif 111797403Sobrien */ 111897403Sobrien template<typename _InputIter, typename _ForwardIter> 111997403Sobrien _ForwardIter 112097403Sobrien __unique_copy(_InputIter __first, _InputIter __last, 112197403Sobrien _ForwardIter __result, 112297403Sobrien forward_iterator_tag) 112397403Sobrien { 112497403Sobrien // concept requirements -- taken care of in dispatching function 112597403Sobrien *__result = *__first; 112697403Sobrien while (++__first != __last) 112797403Sobrien if (!(*__result == *__first)) 112897403Sobrien *++__result = *__first; 112997403Sobrien return ++__result; 113097403Sobrien } 113197403Sobrien 113297403Sobrien /** 113397403Sobrien * @brief Copy a sequence, removing consecutive duplicate values. 113497403Sobrien * @param first An input iterator. 113597403Sobrien * @param last An input iterator. 113697403Sobrien * @param result An output iterator. 113797403Sobrien * @return An iterator designating the end of the resulting sequence. 113897403Sobrien * 113997403Sobrien * Copies each element in the range @p [first,last) to the range 114097403Sobrien * beginning at @p result, except that only the first element is copied 114197403Sobrien * from groups of consecutive elements that compare equal. 114297403Sobrien * unique_copy() is stable, so the relative order of elements that are 114397403Sobrien * copied is unchanged. 114497403Sobrien */ 114597403Sobrien template<typename _InputIter, typename _OutputIter> 114697403Sobrien inline _OutputIter 114797403Sobrien unique_copy(_InputIter __first, _InputIter __last, 114897403Sobrien _OutputIter __result) 114997403Sobrien { 115097403Sobrien // concept requirements 115197403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 115297403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 115397403Sobrien typename iterator_traits<_InputIter>::value_type>) 115497403Sobrien __glibcpp_function_requires(_EqualityComparableConcept< 115597403Sobrien typename iterator_traits<_InputIter>::value_type>) 115697403Sobrien 115797403Sobrien typedef typename iterator_traits<_OutputIter>::iterator_category _IterType; 115897403Sobrien 115997403Sobrien if (__first == __last) return __result; 116097403Sobrien return __unique_copy(__first, __last, __result, _IterType()); 116197403Sobrien } 116297403Sobrien 116397403Sobrien /** 116497403Sobrien * @if maint 116597403Sobrien * This is an uglified 116697403Sobrien * unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate) 116797403Sobrien * overloaded for output iterators. 116897403Sobrien * @endif 116997403Sobrien */ 117097403Sobrien template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate> 117197403Sobrien _OutputIter 117297403Sobrien __unique_copy(_InputIter __first, _InputIter __last, 117397403Sobrien _OutputIter __result, 117497403Sobrien _BinaryPredicate __binary_pred, 117597403Sobrien output_iterator_tag) 117697403Sobrien { 117797403Sobrien // concept requirements -- iterators already checked 117897403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 117997403Sobrien typename iterator_traits<_InputIter>::value_type, 118097403Sobrien typename iterator_traits<_InputIter>::value_type>) 118197403Sobrien 118297403Sobrien typename iterator_traits<_InputIter>::value_type __value = *__first; 118397403Sobrien *__result = __value; 118497403Sobrien while (++__first != __last) 118597403Sobrien if (!__binary_pred(__value, *__first)) { 118697403Sobrien __value = *__first; 118797403Sobrien *++__result = __value; 118897403Sobrien } 118997403Sobrien return ++__result; 119097403Sobrien } 119197403Sobrien 119297403Sobrien /** 119397403Sobrien * @if maint 119497403Sobrien * This is an uglified 119597403Sobrien * unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate) 119697403Sobrien * overloaded for forward iterators. 119797403Sobrien * @endif 119897403Sobrien */ 119997403Sobrien template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate> 120097403Sobrien _ForwardIter 120197403Sobrien __unique_copy(_InputIter __first, _InputIter __last, 120297403Sobrien _ForwardIter __result, 120397403Sobrien _BinaryPredicate __binary_pred, 120497403Sobrien forward_iterator_tag) 120597403Sobrien { 120697403Sobrien // concept requirements -- iterators already checked 120797403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 120897403Sobrien typename iterator_traits<_ForwardIter>::value_type, 120997403Sobrien typename iterator_traits<_InputIter>::value_type>) 121097403Sobrien 121197403Sobrien *__result = *__first; 121297403Sobrien while (++__first != __last) 121397403Sobrien if (!__binary_pred(*__result, *__first)) *++__result = *__first; 121497403Sobrien return ++__result; 121597403Sobrien } 121697403Sobrien 121797403Sobrien /** 121897403Sobrien * @brief Copy a sequence, removing consecutive values using a predicate. 121997403Sobrien * @param first An input iterator. 122097403Sobrien * @param last An input iterator. 122197403Sobrien * @param result An output iterator. 122297403Sobrien * @param binary_pred A binary predicate. 122397403Sobrien * @return An iterator designating the end of the resulting sequence. 122497403Sobrien * 122597403Sobrien * Copies each element in the range @p [first,last) to the range 122697403Sobrien * beginning at @p result, except that only the first element is copied 122797403Sobrien * from groups of consecutive elements for which @p binary_pred returns 122897403Sobrien * true. 122997403Sobrien * unique_copy() is stable, so the relative order of elements that are 123097403Sobrien * copied is unchanged. 123197403Sobrien */ 123297403Sobrien template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate> 123397403Sobrien inline _OutputIter 123497403Sobrien unique_copy(_InputIter __first, _InputIter __last, 123597403Sobrien _OutputIter __result, 123697403Sobrien _BinaryPredicate __binary_pred) 123797403Sobrien { 123897403Sobrien // concept requirements -- predicates checked later 123997403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 124097403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 124197403Sobrien typename iterator_traits<_InputIter>::value_type>) 124297403Sobrien 124397403Sobrien typedef typename iterator_traits<_OutputIter>::iterator_category _IterType; 124497403Sobrien 124597403Sobrien if (__first == __last) return __result; 124697403Sobrien return __unique_copy(__first, __last, 124797403Sobrien__result, __binary_pred, _IterType()); 124897403Sobrien } 124997403Sobrien 125097403Sobrien /** 125197403Sobrien * @brief Remove consecutive duplicate values from a sequence. 125297403Sobrien * @param first A forward iterator. 125397403Sobrien * @param last A forward iterator. 125497403Sobrien * @return An iterator designating the end of the resulting sequence. 125597403Sobrien * 125697403Sobrien * Removes all but the first element from each group of consecutive 125797403Sobrien * values that compare equal. 125897403Sobrien * unique() is stable, so the relative order of elements that are 125997403Sobrien * not removed is unchanged. 126097403Sobrien * Elements between the end of the resulting sequence and @p last 126197403Sobrien * are still present, but their value is unspecified. 126297403Sobrien */ 126397403Sobrien template<typename _ForwardIter> 126497403Sobrien _ForwardIter 126597403Sobrien unique(_ForwardIter __first, _ForwardIter __last) 126697403Sobrien { 126797403Sobrien // concept requirements 126897403Sobrien __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 126997403Sobrien __glibcpp_function_requires(_EqualityComparableConcept< 127097403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 127197403Sobrien 127297403Sobrien __first = adjacent_find(__first, __last); 127397403Sobrien return unique_copy(__first, __last, __first); 127497403Sobrien } 127597403Sobrien 127697403Sobrien /** 127797403Sobrien * @brief Remove consecutive values from a sequence using a predicate. 127897403Sobrien * @param first A forward iterator. 127997403Sobrien * @param last A forward iterator. 128097403Sobrien * @param binary_pred A binary predicate. 128197403Sobrien * @return An iterator designating the end of the resulting sequence. 128297403Sobrien * 128397403Sobrien * Removes all but the first element from each group of consecutive 128497403Sobrien * values for which @p binary_pred returns true. 128597403Sobrien * unique() is stable, so the relative order of elements that are 128697403Sobrien * not removed is unchanged. 128797403Sobrien * Elements between the end of the resulting sequence and @p last 128897403Sobrien * are still present, but their value is unspecified. 128997403Sobrien */ 129097403Sobrien template<typename _ForwardIter, typename _BinaryPredicate> 129197403Sobrien _ForwardIter 129297403Sobrien unique(_ForwardIter __first, _ForwardIter __last, 129397403Sobrien _BinaryPredicate __binary_pred) 129497403Sobrien { 129597403Sobrien // concept requirements 129697403Sobrien __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 129797403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 129897403Sobrien typename iterator_traits<_ForwardIter>::value_type, 129997403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 130097403Sobrien 130197403Sobrien __first = adjacent_find(__first, __last, __binary_pred); 130297403Sobrien return unique_copy(__first, __last, __first, __binary_pred); 130397403Sobrien } 130497403Sobrien 130597403Sobrien /** 130697403Sobrien * @if maint 130797403Sobrien * This is an uglified reverse(_BidirectionalIter, _BidirectionalIter) 130897403Sobrien * overloaded for bidirectional iterators. 130997403Sobrien * @endif 131097403Sobrien */ 131197403Sobrien template<typename _BidirectionalIter> 131297403Sobrien void 131397403Sobrien __reverse(_BidirectionalIter __first, _BidirectionalIter __last, 131497403Sobrien bidirectional_iterator_tag) 131597403Sobrien { 131697403Sobrien while (true) 131797403Sobrien if (__first == __last || __first == --__last) 131897403Sobrien return; 131997403Sobrien else 132097403Sobrien iter_swap(__first++, __last); 132197403Sobrien } 132297403Sobrien 132397403Sobrien /** 132497403Sobrien * @if maint 132597403Sobrien * This is an uglified reverse(_BidirectionalIter, _BidirectionalIter) 132697403Sobrien * overloaded for bidirectional iterators. 132797403Sobrien * @endif 132897403Sobrien */ 132997403Sobrien template<typename _RandomAccessIter> 133097403Sobrien void 133197403Sobrien __reverse(_RandomAccessIter __first, _RandomAccessIter __last, 133297403Sobrien random_access_iterator_tag) 133397403Sobrien { 133497403Sobrien while (__first < __last) 133597403Sobrien iter_swap(__first++, --__last); 133697403Sobrien } 133797403Sobrien 133897403Sobrien /** 133997403Sobrien * @brief Reverse a sequence. 134097403Sobrien * @param first A bidirectional iterator. 134197403Sobrien * @param last A bidirectional iterator. 134297403Sobrien * @return reverse() returns no value. 134397403Sobrien * 134497403Sobrien * Reverses the order of the elements in the range @p [first,last), 134597403Sobrien * so that the first element becomes the last etc. 134697403Sobrien * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse() 134797403Sobrien * swaps @p *(first+i) and @p *(last-(i+1)) 134897403Sobrien */ 134997403Sobrien template<typename _BidirectionalIter> 135097403Sobrien inline void 135197403Sobrien reverse(_BidirectionalIter __first, _BidirectionalIter __last) 135297403Sobrien { 135397403Sobrien // concept requirements 135497403Sobrien __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 135597403Sobrien _BidirectionalIter>) 135697403Sobrien __reverse(__first, __last, __iterator_category(__first)); 135797403Sobrien } 135897403Sobrien 135997403Sobrien /** 136097403Sobrien * @brief Copy a sequence, reversing its elements. 136197403Sobrien * @param first A bidirectional iterator. 136297403Sobrien * @param last A bidirectional iterator. 136397403Sobrien * @param result An output iterator. 136497403Sobrien * @return An iterator designating the end of the resulting sequence. 136597403Sobrien * 136697403Sobrien * Copies the elements in the range @p [first,last) to the range 136797403Sobrien * @p [result,result+(last-first)) such that the order of the 136897403Sobrien * elements is reversed. 136997403Sobrien * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy() 137097403Sobrien * performs the assignment @p *(result+(last-first)-i) = *(first+i). 137197403Sobrien * The ranges @p [first,last) and @p [result,result+(last-first)) 137297403Sobrien * must not overlap. 137397403Sobrien */ 137497403Sobrien template<typename _BidirectionalIter, typename _OutputIter> 137597403Sobrien _OutputIter 137697403Sobrien reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last, 137797403Sobrien _OutputIter __result) 137897403Sobrien { 137997403Sobrien // concept requirements 138097403Sobrien __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 138197403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 138297403Sobrien typename iterator_traits<_BidirectionalIter>::value_type>) 138397403Sobrien 138497403Sobrien while (__first != __last) { 138597403Sobrien --__last; 138697403Sobrien *__result = *__last; 138797403Sobrien ++__result; 138897403Sobrien } 138997403Sobrien return __result; 139097403Sobrien } 139197403Sobrien 139297403Sobrien 139397403Sobrien /** 139497403Sobrien * @if maint 139597403Sobrien * This is a helper function for the rotate algorithm specialized on RAIs. 139697403Sobrien * It returns the greatest common divisor of two integer values. 139797403Sobrien * @endif 139897403Sobrien */ 139997403Sobrien template<typename _EuclideanRingElement> 140097403Sobrien _EuclideanRingElement 140197403Sobrien __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) 140297403Sobrien { 140397403Sobrien while (__n != 0) { 140497403Sobrien _EuclideanRingElement __t = __m % __n; 140597403Sobrien __m = __n; 140697403Sobrien __n = __t; 140797403Sobrien } 140897403Sobrien return __m; 140997403Sobrien } 141097403Sobrien 141197403Sobrien /** 141297403Sobrien * @if maint 141397403Sobrien * This is a helper function for the rotate algorithm. 141497403Sobrien * @endif 141597403Sobrien */ 141697403Sobrien template<typename _ForwardIter> 141797403Sobrien void 141897403Sobrien __rotate(_ForwardIter __first, 141997403Sobrien _ForwardIter __middle, 142097403Sobrien _ForwardIter __last, 142197403Sobrien forward_iterator_tag) 142297403Sobrien { 142397403Sobrien if ((__first == __middle) || (__last == __middle)) 142497403Sobrien return; 142597403Sobrien 142697403Sobrien _ForwardIter __first2 = __middle; 142797403Sobrien do { 142897403Sobrien swap(*__first++, *__first2++); 142997403Sobrien if (__first == __middle) 143097403Sobrien __middle = __first2; 143197403Sobrien } while (__first2 != __last); 143297403Sobrien 143397403Sobrien __first2 = __middle; 143497403Sobrien 143597403Sobrien while (__first2 != __last) { 143697403Sobrien swap(*__first++, *__first2++); 143797403Sobrien if (__first == __middle) 143897403Sobrien __middle = __first2; 143997403Sobrien else if (__first2 == __last) 144097403Sobrien __first2 = __middle; 144197403Sobrien } 144297403Sobrien } 144397403Sobrien 144497403Sobrien /** 144597403Sobrien * @if maint 144697403Sobrien * This is a helper function for the rotate algorithm. 144797403Sobrien * @endif 144897403Sobrien */ 144997403Sobrien template<typename _BidirectionalIter> 145097403Sobrien void 145197403Sobrien __rotate(_BidirectionalIter __first, 145297403Sobrien _BidirectionalIter __middle, 145397403Sobrien _BidirectionalIter __last, 145497403Sobrien bidirectional_iterator_tag) 145597403Sobrien { 145697403Sobrien // concept requirements 145797403Sobrien __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 145897403Sobrien _BidirectionalIter>) 145997403Sobrien 146097403Sobrien if ((__first == __middle) || (__last == __middle)) 146197403Sobrien return; 146297403Sobrien 146397403Sobrien __reverse(__first, __middle, bidirectional_iterator_tag()); 146497403Sobrien __reverse(__middle, __last, bidirectional_iterator_tag()); 146597403Sobrien 146697403Sobrien while (__first != __middle && __middle != __last) 146797403Sobrien swap (*__first++, *--__last); 146897403Sobrien 146997403Sobrien if (__first == __middle) { 147097403Sobrien __reverse(__middle, __last, bidirectional_iterator_tag()); 147197403Sobrien } 147297403Sobrien else { 147397403Sobrien __reverse(__first, __middle, bidirectional_iterator_tag()); 147497403Sobrien } 147597403Sobrien } 147697403Sobrien 147797403Sobrien /** 147897403Sobrien * @if maint 147997403Sobrien * This is a helper function for the rotate algorithm. 148097403Sobrien * @endif 148197403Sobrien */ 148297403Sobrien template<typename _RandomAccessIter> 148397403Sobrien void 148497403Sobrien __rotate(_RandomAccessIter __first, 148597403Sobrien _RandomAccessIter __middle, 148697403Sobrien _RandomAccessIter __last, 148797403Sobrien random_access_iterator_tag) 148897403Sobrien { 148997403Sobrien // concept requirements 149097403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 149197403Sobrien _RandomAccessIter>) 149297403Sobrien 149397403Sobrien if ((__first == __middle) || (__last == __middle)) 149497403Sobrien return; 149597403Sobrien 149697403Sobrien typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 149797403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 149897403Sobrien 149997403Sobrien _Distance __n = __last - __first; 150097403Sobrien _Distance __k = __middle - __first; 150197403Sobrien _Distance __l = __n - __k; 150297403Sobrien 150397403Sobrien if (__k == __l) { 150497403Sobrien swap_ranges(__first, __middle, __middle); 150597403Sobrien return; 150697403Sobrien } 150797403Sobrien 150897403Sobrien _Distance __d = __gcd(__n, __k); 150997403Sobrien 151097403Sobrien for (_Distance __i = 0; __i < __d; __i++) { 151197403Sobrien _ValueType __tmp = *__first; 151297403Sobrien _RandomAccessIter __p = __first; 151397403Sobrien 151497403Sobrien if (__k < __l) { 151597403Sobrien for (_Distance __j = 0; __j < __l/__d; __j++) { 151697403Sobrien if (__p > __first + __l) { 151797403Sobrien *__p = *(__p - __l); 151897403Sobrien __p -= __l; 151997403Sobrien } 152097403Sobrien 152197403Sobrien *__p = *(__p + __k); 152297403Sobrien __p += __k; 152397403Sobrien } 152497403Sobrien } 152597403Sobrien 152697403Sobrien else { 152797403Sobrien for (_Distance __j = 0; __j < __k/__d - 1; __j ++) { 152897403Sobrien if (__p < __last - __k) { 152997403Sobrien *__p = *(__p + __k); 153097403Sobrien __p += __k; 153197403Sobrien } 153297403Sobrien 153397403Sobrien *__p = * (__p - __l); 153497403Sobrien __p -= __l; 153597403Sobrien } 153697403Sobrien } 153797403Sobrien 153897403Sobrien *__p = __tmp; 153997403Sobrien ++__first; 154097403Sobrien } 154197403Sobrien } 154297403Sobrien 154397403Sobrien /** 154497403Sobrien * @brief Rotate the elements of a sequence. 154597403Sobrien * @param first A forward iterator. 154697403Sobrien * @param middle A forward iterator. 154797403Sobrien * @param last A forward iterator. 154897403Sobrien * @return Nothing. 154997403Sobrien * 155097403Sobrien * Rotates the elements of the range @p [first,last) by @p (middle-first) 155197403Sobrien * positions so that the element at @p middle is moved to @p first, the 155297403Sobrien * element at @p middle+1 is moved to @first+1 and so on for each element 155397403Sobrien * in the range @p [first,last). 155497403Sobrien * 155597403Sobrien * This effectively swaps the ranges @p [first,middle) and 155697403Sobrien * @p [middle,last). 155797403Sobrien * 155897403Sobrien * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for 155997403Sobrien * each @p n in the range @p [0,last-first). 156097403Sobrien */ 156197403Sobrien template<typename _ForwardIter> 156297403Sobrien inline void 156397403Sobrien rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) 156497403Sobrien { 156597403Sobrien // concept requirements 156697403Sobrien __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 156797403Sobrien 156897403Sobrien typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType; 156997403Sobrien __rotate(__first, __middle, __last, _IterType()); 157097403Sobrien } 157197403Sobrien 157297403Sobrien /** 157397403Sobrien * @brief Copy a sequence, rotating its elements. 157497403Sobrien * @param first A forward iterator. 157597403Sobrien * @param middle A forward iterator. 157697403Sobrien * @param last A forward iterator. 157797403Sobrien * @param result An output iterator. 157897403Sobrien * @return An iterator designating the end of the resulting sequence. 157997403Sobrien * 158097403Sobrien * Copies the elements of the range @p [first,last) to the range 158197403Sobrien * beginning at @result, rotating the copied elements by @p (middle-first) 158297403Sobrien * positions so that the element at @p middle is moved to @p result, the 158397403Sobrien * element at @p middle+1 is moved to @result+1 and so on for each element 158497403Sobrien * in the range @p [first,last). 158597403Sobrien * 158697403Sobrien * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for 158797403Sobrien * each @p n in the range @p [0,last-first). 158897403Sobrien */ 158997403Sobrien template<typename _ForwardIter, typename _OutputIter> 159097403Sobrien _OutputIter 159197403Sobrien rotate_copy(_ForwardIter __first, _ForwardIter __middle, 159297403Sobrien _ForwardIter __last, _OutputIter __result) 159397403Sobrien { 159497403Sobrien // concept requirements 159597403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 159697403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 159797403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 159897403Sobrien 159997403Sobrien return copy(__first, __middle, copy(__middle, __last, __result)); 160097403Sobrien } 160197403Sobrien 160297403Sobrien 160397403Sobrien /** 160497403Sobrien * @if maint 160597403Sobrien * Return a random number in the range [0, __n). This function encapsulates 160697403Sobrien * whether we're using rand (part of the standard C library) or lrand48 160797403Sobrien * (not standard, but a much better choice whenever it's available). 160897403Sobrien * 160997403Sobrien * XXX There is no corresponding encapsulation fn to seed the generator. 161097403Sobrien * @endif 161197403Sobrien */ 161297403Sobrien template<typename _Distance> 161397403Sobrien inline _Distance 161497403Sobrien __random_number(_Distance __n) 161597403Sobrien { 161697403Sobrien #ifdef _GLIBCPP_HAVE_DRAND48 161797403Sobrien return lrand48() % __n; 161897403Sobrien #else 161997403Sobrien return rand() % __n; 162097403Sobrien #endif 162197403Sobrien } 162297403Sobrien 162397403Sobrien 162497403Sobrien /** 162597403Sobrien * @brief Randomly shuffle the elements of a sequence. 162697403Sobrien * @param first A forward iterator. 162797403Sobrien * @param last A forward iterator. 162897403Sobrien * @return Nothing. 162997403Sobrien * 163097403Sobrien * Reorder the elements in the range @p [first,last) using a random 163197403Sobrien * distribution, so that every possible ordering of the sequence is 163297403Sobrien * equally likely. 163397403Sobrien */ 163497403Sobrien template<typename _RandomAccessIter> 163597403Sobrien inline void 163697403Sobrien random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last) 163797403Sobrien { 163897403Sobrien // concept requirements 163997403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 164097403Sobrien _RandomAccessIter>) 164197403Sobrien 164297403Sobrien if (__first == __last) return; 164397403Sobrien for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 164497403Sobrien iter_swap(__i, __first + __random_number((__i - __first) + 1)); 164597403Sobrien } 164697403Sobrien 164797403Sobrien /** 164897403Sobrien * @brief Shuffle the elements of a sequence using a random number 164997403Sobrien * generator. 165097403Sobrien * @param first A forward iterator. 165197403Sobrien * @param last A forward iterator. 165297403Sobrien * @param rand The RNG functor or function. 165397403Sobrien * @return Nothing. 165497403Sobrien * 165597403Sobrien * Reorders the elements in the range @p [first,last) using @p rand to 165697403Sobrien * provide a random distribution. Calling @p rand(N) for a positive 165797403Sobrien * integer @p N should return a randomly chosen integer from the 165897403Sobrien * range [0,N). 165997403Sobrien */ 166097403Sobrien template<typename _RandomAccessIter, typename _RandomNumberGenerator> 166197403Sobrien void 166297403Sobrien random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, 166397403Sobrien _RandomNumberGenerator& __rand) 166497403Sobrien { 166597403Sobrien // concept requirements 166697403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 166797403Sobrien _RandomAccessIter>) 166897403Sobrien 166997403Sobrien if (__first == __last) return; 167097403Sobrien for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 167197403Sobrien iter_swap(__i, __first + __rand((__i - __first) + 1)); 167297403Sobrien } 167397403Sobrien 167497403Sobrien 167597403Sobrien /** 167697403Sobrien * @if maint 167797403Sobrien * This is a helper function... 167897403Sobrien * @endif 167997403Sobrien */ 168097403Sobrien template<typename _ForwardIter, typename _Predicate> 168197403Sobrien _ForwardIter 168297403Sobrien __partition(_ForwardIter __first, _ForwardIter __last, 168397403Sobrien _Predicate __pred, 168497403Sobrien forward_iterator_tag) 168597403Sobrien { 168697403Sobrien if (__first == __last) return __first; 168797403Sobrien 168897403Sobrien while (__pred(*__first)) 168997403Sobrien if (++__first == __last) return __first; 169097403Sobrien 169197403Sobrien _ForwardIter __next = __first; 169297403Sobrien 169397403Sobrien while (++__next != __last) 169497403Sobrien if (__pred(*__next)) { 169597403Sobrien swap(*__first, *__next); 169697403Sobrien ++__first; 169797403Sobrien } 169897403Sobrien 169997403Sobrien return __first; 170097403Sobrien } 170197403Sobrien 170297403Sobrien /** 170397403Sobrien * @if maint 170497403Sobrien * This is a helper function... 170597403Sobrien * @endif 170697403Sobrien */ 170797403Sobrien template<typename _BidirectionalIter, typename _Predicate> 170897403Sobrien _BidirectionalIter 170997403Sobrien __partition(_BidirectionalIter __first, _BidirectionalIter __last, 171097403Sobrien _Predicate __pred, 171197403Sobrien bidirectional_iterator_tag) 171297403Sobrien { 171397403Sobrien while (true) { 171497403Sobrien while (true) 171597403Sobrien if (__first == __last) 171697403Sobrien return __first; 171797403Sobrien else if (__pred(*__first)) 171897403Sobrien ++__first; 171997403Sobrien else 172097403Sobrien break; 172197403Sobrien --__last; 172297403Sobrien while (true) 172397403Sobrien if (__first == __last) 172497403Sobrien return __first; 172597403Sobrien else if (!__pred(*__last)) 172697403Sobrien --__last; 172797403Sobrien else 172897403Sobrien break; 172997403Sobrien iter_swap(__first, __last); 173097403Sobrien ++__first; 173197403Sobrien } 173297403Sobrien } 173397403Sobrien 173497403Sobrien /** 173597403Sobrien * @brief Move elements for which a predicate is true to the beginning 173697403Sobrien * of a sequence. 173797403Sobrien * @param first A forward iterator. 173897403Sobrien * @param last A forward iterator. 173997403Sobrien * @param pred A predicate functor. 174097403Sobrien * @return An iterator @p middle such that @p pred(i) is true for each 174197403Sobrien * iterator @p i in the range @p [first,middle) and false for each @p i 174297403Sobrien * in the range @p [middle,last). 174397403Sobrien * 174497403Sobrien * @p pred must not modify its operand. @p partition() does not preserve 174597403Sobrien * the relative ordering of elements in each group, use 174697403Sobrien * @p stable_partition() if this is needed. 174797403Sobrien */ 174897403Sobrien template<typename _ForwardIter, typename _Predicate> 174997403Sobrien inline _ForwardIter 175097403Sobrien partition(_ForwardIter __first, _ForwardIter __last, 175197403Sobrien _Predicate __pred) 175297403Sobrien { 175397403Sobrien // concept requirements 175497403Sobrien __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 175597403Sobrien __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 175697403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 175797403Sobrien 175897403Sobrien return __partition(__first, __last, __pred, __iterator_category(__first)); 175997403Sobrien } 176097403Sobrien 176197403Sobrien 176297403Sobrien /** 176397403Sobrien * @if maint 176497403Sobrien * This is a helper function... 176597403Sobrien * @endif 176697403Sobrien */ 176797403Sobrien template<typename _ForwardIter, typename _Predicate, typename _Distance> 176897403Sobrien _ForwardIter 176997403Sobrien __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last, 177097403Sobrien _Predicate __pred, _Distance __len) 177197403Sobrien { 177297403Sobrien if (__len == 1) 177397403Sobrien return __pred(*__first) ? __last : __first; 177497403Sobrien _ForwardIter __middle = __first; 177597403Sobrien advance(__middle, __len / 2); 177697403Sobrien _ForwardIter __begin = __inplace_stable_partition(__first, __middle, 177797403Sobrien __pred, 177897403Sobrien __len / 2); 177997403Sobrien _ForwardIter __end = __inplace_stable_partition(__middle, __last, 178097403Sobrien __pred, 178197403Sobrien __len - __len / 2); 178297403Sobrien rotate(__begin, __middle, __end); 178397403Sobrien advance(__begin, distance(__middle, __end)); 178497403Sobrien return __begin; 178597403Sobrien } 178697403Sobrien 178797403Sobrien /** 178897403Sobrien * @if maint 178997403Sobrien * This is a helper function... 179097403Sobrien * @endif 179197403Sobrien */ 179297403Sobrien template<typename _ForwardIter, typename _Pointer, typename _Predicate, 179397403Sobrien typename _Distance> 179497403Sobrien _ForwardIter 179597403Sobrien __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last, 179697403Sobrien _Predicate __pred, _Distance __len, 179797403Sobrien _Pointer __buffer, 179897403Sobrien _Distance __buffer_size) 179997403Sobrien { 180097403Sobrien if (__len <= __buffer_size) { 180197403Sobrien _ForwardIter __result1 = __first; 180297403Sobrien _Pointer __result2 = __buffer; 180397403Sobrien for ( ; __first != __last ; ++__first) 180497403Sobrien if (__pred(*__first)) { 180597403Sobrien *__result1 = *__first; 180697403Sobrien ++__result1; 180797403Sobrien } 180897403Sobrien else { 180997403Sobrien *__result2 = *__first; 181097403Sobrien ++__result2; 181197403Sobrien } 181297403Sobrien copy(__buffer, __result2, __result1); 181397403Sobrien return __result1; 181497403Sobrien } 181597403Sobrien else { 181697403Sobrien _ForwardIter __middle = __first; 181797403Sobrien advance(__middle, __len / 2); 181897403Sobrien _ForwardIter __begin = __stable_partition_adaptive(__first, __middle, 181997403Sobrien __pred, 182097403Sobrien __len / 2, 182197403Sobrien __buffer, __buffer_size); 182297403Sobrien _ForwardIter __end = __stable_partition_adaptive( __middle, __last, 182397403Sobrien __pred, 182497403Sobrien __len - __len / 2, 182597403Sobrien __buffer, __buffer_size); 182697403Sobrien rotate(__begin, __middle, __end); 182797403Sobrien advance(__begin, distance(__middle, __end)); 182897403Sobrien return __begin; 182997403Sobrien } 183097403Sobrien } 183197403Sobrien 183297403Sobrien /** 183397403Sobrien * @brief Move elements for which a predicate is true to the beginning 183497403Sobrien * of a sequence, preserving relative ordering. 183597403Sobrien * @param first A forward iterator. 183697403Sobrien * @param last A forward iterator. 183797403Sobrien * @param pred A predicate functor. 183897403Sobrien * @return An iterator @p middle such that @p pred(i) is true for each 183997403Sobrien * iterator @p i in the range @p [first,middle) and false for each @p i 184097403Sobrien * in the range @p [middle,last). 184197403Sobrien * 184297403Sobrien * Performs the same function as @p partition() with the additional 184397403Sobrien * guarantee that the relative ordering of elements in each group is 184497403Sobrien * preserved, so any two elements @p x and @p y in the range 184597403Sobrien * @p [first,last) such that @p pred(x)==pred(y) will have the same 184697403Sobrien * relative ordering after calling @p stable_partition(). 184797403Sobrien */ 184897403Sobrien template<typename _ForwardIter, typename _Predicate> 184997403Sobrien _ForwardIter 185097403Sobrien stable_partition(_ForwardIter __first, _ForwardIter __last, 185197403Sobrien _Predicate __pred) 185297403Sobrien { 185397403Sobrien // concept requirements 185497403Sobrien __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 185597403Sobrien __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 185697403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 185797403Sobrien 185897403Sobrien if (__first == __last) 185997403Sobrien return __first; 186097403Sobrien else 186197403Sobrien { 186297403Sobrien typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 186397403Sobrien typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 186497403Sobrien 186597403Sobrien _Temporary_buffer<_ForwardIter, _ValueType> __buf(__first, __last); 186697403Sobrien if (__buf.size() > 0) 186797403Sobrien return __stable_partition_adaptive(__first, __last, __pred, 186897403Sobrien _DistanceType(__buf.requested_size()), 186997403Sobrien __buf.begin(), __buf.size()); 187097403Sobrien else 187197403Sobrien return __inplace_stable_partition(__first, __last, __pred, 187297403Sobrien _DistanceType(__buf.requested_size())); 187397403Sobrien } 187497403Sobrien } 187597403Sobrien 187697403Sobrien /** 187797403Sobrien * @if maint 187897403Sobrien * This is a helper function... 187997403Sobrien * @endif 188097403Sobrien */ 188197403Sobrien template<typename _RandomAccessIter, typename _Tp> 188297403Sobrien _RandomAccessIter 188397403Sobrien __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, 188497403Sobrien _Tp __pivot) 188597403Sobrien { 188697403Sobrien while (true) { 188797403Sobrien while (*__first < __pivot) 188897403Sobrien ++__first; 188997403Sobrien --__last; 189097403Sobrien while (__pivot < *__last) 189197403Sobrien --__last; 189297403Sobrien if (!(__first < __last)) 189397403Sobrien return __first; 189497403Sobrien iter_swap(__first, __last); 189597403Sobrien ++__first; 189697403Sobrien } 189797403Sobrien } 189897403Sobrien 189997403Sobrien /** 190097403Sobrien * @if maint 190197403Sobrien * This is a helper function... 190297403Sobrien * @endif 190397403Sobrien */ 190497403Sobrien template<typename _RandomAccessIter, typename _Tp, typename _Compare> 190597403Sobrien _RandomAccessIter 190697403Sobrien __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, 190797403Sobrien _Tp __pivot, _Compare __comp) 190897403Sobrien { 190997403Sobrien while (true) { 191097403Sobrien while (__comp(*__first, __pivot)) 191197403Sobrien ++__first; 191297403Sobrien --__last; 191397403Sobrien while (__comp(__pivot, *__last)) 191497403Sobrien --__last; 191597403Sobrien if (!(__first < __last)) 191697403Sobrien return __first; 191797403Sobrien iter_swap(__first, __last); 191897403Sobrien ++__first; 191997403Sobrien } 192097403Sobrien } 192197403Sobrien 192297403Sobrien 192397403Sobrien /** 192497403Sobrien * @if maint 192597403Sobrien * @doctodo 192697403Sobrien * This controls some aspect of the sort routines. 192797403Sobrien * @endif 192897403Sobrien */ 192997403Sobrien enum { _M_threshold = 16 }; 193097403Sobrien 193197403Sobrien /** 193297403Sobrien * @if maint 193397403Sobrien * This is a helper function for the sort routine. 193497403Sobrien * @endif 193597403Sobrien */ 193697403Sobrien template<typename _RandomAccessIter, typename _Tp> 193797403Sobrien void 193897403Sobrien __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) 193997403Sobrien { 194097403Sobrien _RandomAccessIter __next = __last; 194197403Sobrien --__next; 194297403Sobrien while (__val < *__next) { 194397403Sobrien *__last = *__next; 194497403Sobrien __last = __next; 194597403Sobrien --__next; 194697403Sobrien } 194797403Sobrien *__last = __val; 194897403Sobrien } 194997403Sobrien 195097403Sobrien /** 195197403Sobrien * @if maint 195297403Sobrien * This is a helper function for the sort routine. 195397403Sobrien * @endif 195497403Sobrien */ 195597403Sobrien template<typename _RandomAccessIter, typename _Tp, typename _Compare> 195697403Sobrien void 195797403Sobrien __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp) 195897403Sobrien { 195997403Sobrien _RandomAccessIter __next = __last; 196097403Sobrien --__next; 196197403Sobrien while (__comp(__val, *__next)) { 196297403Sobrien *__last = *__next; 196397403Sobrien __last = __next; 196497403Sobrien --__next; 196597403Sobrien } 196697403Sobrien *__last = __val; 196797403Sobrien } 196897403Sobrien 196997403Sobrien /** 197097403Sobrien * @if maint 197197403Sobrien * This is a helper function for the sort routine. 197297403Sobrien * @endif 197397403Sobrien */ 197497403Sobrien template<typename _RandomAccessIter> 197597403Sobrien void 197697403Sobrien __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 197797403Sobrien { 197897403Sobrien if (__first == __last) return; 197997403Sobrien 198097403Sobrien for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 198197403Sobrien { 198297403Sobrien typename iterator_traits<_RandomAccessIter>::value_type __val = *__i; 198397403Sobrien if (__val < *__first) { 198497403Sobrien copy_backward(__first, __i, __i + 1); 198597403Sobrien *__first = __val; 198697403Sobrien } 198797403Sobrien else 198897403Sobrien __unguarded_linear_insert(__i, __val); 198997403Sobrien } 199097403Sobrien } 199197403Sobrien 199297403Sobrien /** 199397403Sobrien * @if maint 199497403Sobrien * This is a helper function for the sort routine. 199597403Sobrien * @endif 199697403Sobrien */ 199797403Sobrien template<typename _RandomAccessIter, typename _Compare> 199897403Sobrien void 199997403Sobrien __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 200097403Sobrien _Compare __comp) 200197403Sobrien { 200297403Sobrien if (__first == __last) return; 200397403Sobrien 200497403Sobrien for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 200597403Sobrien { 200697403Sobrien typename iterator_traits<_RandomAccessIter>::value_type __val = *__i; 200797403Sobrien if (__comp(__val, *__first)) { 200897403Sobrien copy_backward(__first, __i, __i + 1); 200997403Sobrien *__first = __val; 201097403Sobrien } 201197403Sobrien else 201297403Sobrien __unguarded_linear_insert(__i, __val, __comp); 201397403Sobrien } 201497403Sobrien } 201597403Sobrien 201697403Sobrien /** 201797403Sobrien * @if maint 201897403Sobrien * This is a helper function for the sort routine. 201997403Sobrien * @endif 202097403Sobrien */ 202197403Sobrien template<typename _RandomAccessIter> 202297403Sobrien inline void 202397403Sobrien __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 202497403Sobrien { 202597403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 202697403Sobrien 202797403Sobrien for (_RandomAccessIter __i = __first; __i != __last; ++__i) 202897403Sobrien __unguarded_linear_insert(__i, _ValueType(*__i)); 202997403Sobrien } 203097403Sobrien 203197403Sobrien /** 203297403Sobrien * @if maint 203397403Sobrien * This is a helper function for the sort routine. 203497403Sobrien * @endif 203597403Sobrien */ 203697403Sobrien template<typename _RandomAccessIter, typename _Compare> 203797403Sobrien inline void 203897403Sobrien __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 203997403Sobrien _Compare __comp) 204097403Sobrien { 204197403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 204297403Sobrien 204397403Sobrien for (_RandomAccessIter __i = __first; __i != __last; ++__i) 204497403Sobrien __unguarded_linear_insert(__i, _ValueType(*__i), __comp); 204597403Sobrien } 204697403Sobrien 204797403Sobrien /** 204897403Sobrien * @if maint 204997403Sobrien * This is a helper function for the sort routine. 205097403Sobrien * @endif 205197403Sobrien */ 205297403Sobrien template<typename _RandomAccessIter> 205397403Sobrien void 205497403Sobrien __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 205597403Sobrien { 205697403Sobrien if (__last - __first > _M_threshold) { 205797403Sobrien __insertion_sort(__first, __first + _M_threshold); 205897403Sobrien __unguarded_insertion_sort(__first + _M_threshold, __last); 205997403Sobrien } 206097403Sobrien else 206197403Sobrien __insertion_sort(__first, __last); 206297403Sobrien } 206397403Sobrien 206497403Sobrien /** 206597403Sobrien * @if maint 206697403Sobrien * This is a helper function for the sort routine. 206797403Sobrien * @endif 206897403Sobrien */ 206997403Sobrien template<typename _RandomAccessIter, typename _Compare> 207097403Sobrien void 207197403Sobrien __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 207297403Sobrien _Compare __comp) 207397403Sobrien { 207497403Sobrien if (__last - __first > _M_threshold) { 207597403Sobrien __insertion_sort(__first, __first + _M_threshold, __comp); 207697403Sobrien __unguarded_insertion_sort(__first + _M_threshold, __last, __comp); 207797403Sobrien } 207897403Sobrien else 207997403Sobrien __insertion_sort(__first, __last, __comp); 208097403Sobrien } 208197403Sobrien 208297403Sobrien /** 208397403Sobrien * @if maint 208497403Sobrien * This is a helper function for the sort routine. 208597403Sobrien * @endif 208697403Sobrien */ 208797403Sobrien template<typename _Size> 208897403Sobrien inline _Size 208997403Sobrien __lg(_Size __n) 209097403Sobrien { 209197403Sobrien _Size __k; 209297403Sobrien for (__k = 0; __n != 1; __n >>= 1) ++__k; 209397403Sobrien return __k; 209497403Sobrien } 209597403Sobrien 209697403Sobrien /** 209797403Sobrien * @if maint 209897403Sobrien * This is a helper function for the sort routine. 209997403Sobrien * @endif 210097403Sobrien */ 210197403Sobrien template<typename _RandomAccessIter, typename _Size> 210297403Sobrien void 210397403Sobrien __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, 210497403Sobrien _Size __depth_limit) 210597403Sobrien { 210697403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 210797403Sobrien 210897403Sobrien while (__last - __first > _M_threshold) { 210997403Sobrien if (__depth_limit == 0) { 211097403Sobrien partial_sort(__first, __last, __last); 211197403Sobrien return; 211297403Sobrien } 211397403Sobrien --__depth_limit; 211497403Sobrien _RandomAccessIter __cut = 211597403Sobrien __unguarded_partition(__first, __last, 211697403Sobrien _ValueType(__median(*__first, 211797403Sobrien *(__first + (__last - __first)/2), 211897403Sobrien *(__last - 1)))); 211997403Sobrien __introsort_loop(__cut, __last, __depth_limit); 212097403Sobrien __last = __cut; 212197403Sobrien } 212297403Sobrien } 212397403Sobrien 212497403Sobrien /** 212597403Sobrien * @if maint 212697403Sobrien * This is a helper function for the sort routine. 212797403Sobrien * @endif 212897403Sobrien */ 212997403Sobrien template<typename _RandomAccessIter, typename _Size, typename _Compare> 213097403Sobrien void 213197403Sobrien __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, 213297403Sobrien _Size __depth_limit, _Compare __comp) 213397403Sobrien { 213497403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 213597403Sobrien 213697403Sobrien while (__last - __first > _M_threshold) { 213797403Sobrien if (__depth_limit == 0) { 213897403Sobrien partial_sort(__first, __last, __last, __comp); 213997403Sobrien return; 214097403Sobrien } 214197403Sobrien --__depth_limit; 214297403Sobrien _RandomAccessIter __cut = 214397403Sobrien __unguarded_partition(__first, __last, 214497403Sobrien _ValueType(__median(*__first, 214597403Sobrien *(__first + (__last - __first)/2), 214697403Sobrien *(__last - 1), __comp)), 214797403Sobrien __comp); 214897403Sobrien __introsort_loop(__cut, __last, __depth_limit, __comp); 214997403Sobrien __last = __cut; 215097403Sobrien } 215197403Sobrien } 215297403Sobrien 215397403Sobrien /** 215497403Sobrien * @brief Sort the elements of a sequence. 215597403Sobrien * @param first An iterator. 215697403Sobrien * @param last Another iterator. 215797403Sobrien * @return Nothing. 215897403Sobrien * 215997403Sobrien * Sorts the elements in the range @p [first,last) in ascending order, 216097403Sobrien * such that @p *(i+1)<*i is false for each iterator @p i in the range 216197403Sobrien * @p [first,last-1). 216297403Sobrien * 216397403Sobrien * The relative ordering of equivalent elements is not preserved, use 216497403Sobrien * @p stable_sort() if this is needed. 216597403Sobrien */ 216697403Sobrien template<typename _RandomAccessIter> 216797403Sobrien inline void 216897403Sobrien sort(_RandomAccessIter __first, _RandomAccessIter __last) 216997403Sobrien { 217097403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 217197403Sobrien 217297403Sobrien // concept requirements 217397403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 217497403Sobrien _RandomAccessIter>) 217597403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 217697403Sobrien 217797403Sobrien if (__first != __last) { 217897403Sobrien __introsort_loop(__first, __last, __lg(__last - __first) * 2); 217997403Sobrien __final_insertion_sort(__first, __last); 218097403Sobrien } 218197403Sobrien } 218297403Sobrien 218397403Sobrien /** 218497403Sobrien * @brief Sort the elements of a sequence using a predicate for comparison. 218597403Sobrien * @param first An iterator. 218697403Sobrien * @param last Another iterator. 218797403Sobrien * @param comp A comparison functor. 218897403Sobrien * @return Nothing. 218997403Sobrien * 219097403Sobrien * Sorts the elements in the range @p [first,last) in ascending order, 219197403Sobrien * such that @p comp(*(i+1),*i) is false for every iterator @p i in the 219297403Sobrien * range @p [first,last-1). 219397403Sobrien * 219497403Sobrien * The relative ordering of equivalent elements is not preserved, use 219597403Sobrien * @p stable_sort() if this is needed. 219697403Sobrien */ 219797403Sobrien template<typename _RandomAccessIter, typename _Compare> 219897403Sobrien inline void 219997403Sobrien sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) 220097403Sobrien { 220197403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 220297403Sobrien 220397403Sobrien // concept requirements 220497403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 220597403Sobrien _RandomAccessIter>) 220697403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>) 220797403Sobrien 220897403Sobrien if (__first != __last) { 220997403Sobrien __introsort_loop(__first, __last, __lg(__last - __first) * 2, __comp); 221097403Sobrien __final_insertion_sort(__first, __last, __comp); 221197403Sobrien } 221297403Sobrien } 221397403Sobrien 221497403Sobrien 221597403Sobrien /** 221697403Sobrien * @if maint 221797403Sobrien * This is a helper function for the stable sorting routines. 221897403Sobrien * @endif 221997403Sobrien */ 222097403Sobrien template<typename _RandomAccessIter> 222197403Sobrien void 222297403Sobrien __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) 222397403Sobrien { 222497403Sobrien if (__last - __first < 15) { 222597403Sobrien __insertion_sort(__first, __last); 222697403Sobrien return; 222797403Sobrien } 222897403Sobrien _RandomAccessIter __middle = __first + (__last - __first) / 2; 222997403Sobrien __inplace_stable_sort(__first, __middle); 223097403Sobrien __inplace_stable_sort(__middle, __last); 223197403Sobrien __merge_without_buffer(__first, __middle, __last, 223297403Sobrien __middle - __first, 223397403Sobrien __last - __middle); 223497403Sobrien } 223597403Sobrien 223697403Sobrien /** 223797403Sobrien * @if maint 223897403Sobrien * This is a helper function for the stable sorting routines. 223997403Sobrien * @endif 224097403Sobrien */ 224197403Sobrien template<typename _RandomAccessIter, typename _Compare> 224297403Sobrien void 224397403Sobrien __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, 224497403Sobrien _Compare __comp) 224597403Sobrien { 224697403Sobrien if (__last - __first < 15) { 224797403Sobrien __insertion_sort(__first, __last, __comp); 224897403Sobrien return; 224997403Sobrien } 225097403Sobrien _RandomAccessIter __middle = __first + (__last - __first) / 2; 225197403Sobrien __inplace_stable_sort(__first, __middle, __comp); 225297403Sobrien __inplace_stable_sort(__middle, __last, __comp); 225397403Sobrien __merge_without_buffer(__first, __middle, __last, 225497403Sobrien __middle - __first, 225597403Sobrien __last - __middle, 225697403Sobrien __comp); 225797403Sobrien } 225897403Sobrien 225997403Sobrien template<typename _RandomAccessIter1, typename _RandomAccessIter2, 226097403Sobrien typename _Distance> 226197403Sobrien void 226297403Sobrien __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, 226397403Sobrien _RandomAccessIter2 __result, _Distance __step_size) 226497403Sobrien { 226597403Sobrien _Distance __two_step = 2 * __step_size; 226697403Sobrien 226797403Sobrien while (__last - __first >= __two_step) { 226897403Sobrien __result = merge(__first, __first + __step_size, 226997403Sobrien __first + __step_size, __first + __two_step, 227097403Sobrien __result); 227197403Sobrien __first += __two_step; 227297403Sobrien } 227397403Sobrien 227497403Sobrien __step_size = min(_Distance(__last - __first), __step_size); 227597403Sobrien merge(__first, __first + __step_size, __first + __step_size, __last, 227697403Sobrien __result); 227797403Sobrien } 227897403Sobrien 227997403Sobrien template<typename _RandomAccessIter1, typename _RandomAccessIter2, 228097403Sobrien typename _Distance, typename _Compare> 228197403Sobrien void 228297403Sobrien __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, 228397403Sobrien _RandomAccessIter2 __result, _Distance __step_size, 228497403Sobrien _Compare __comp) 228597403Sobrien { 228697403Sobrien _Distance __two_step = 2 * __step_size; 228797403Sobrien 228897403Sobrien while (__last - __first >= __two_step) { 228997403Sobrien __result = merge(__first, __first + __step_size, 229097403Sobrien __first + __step_size, __first + __two_step, 229197403Sobrien __result, 229297403Sobrien __comp); 229397403Sobrien __first += __two_step; 229497403Sobrien } 229597403Sobrien __step_size = min(_Distance(__last - __first), __step_size); 229697403Sobrien 229797403Sobrien merge(__first, __first + __step_size, 229897403Sobrien __first + __step_size, __last, 229997403Sobrien __result, 230097403Sobrien __comp); 230197403Sobrien } 230297403Sobrien 230397403Sobrien enum { _M_chunk_size = 7 }; 230497403Sobrien 230597403Sobrien template<typename _RandomAccessIter, typename _Distance> 230697403Sobrien void 230797403Sobrien __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 230897403Sobrien _Distance __chunk_size) 230997403Sobrien { 231097403Sobrien while (__last - __first >= __chunk_size) { 231197403Sobrien __insertion_sort(__first, __first + __chunk_size); 231297403Sobrien __first += __chunk_size; 231397403Sobrien } 231497403Sobrien __insertion_sort(__first, __last); 231597403Sobrien } 231697403Sobrien 231797403Sobrien template<typename _RandomAccessIter, typename _Distance, typename _Compare> 231897403Sobrien void 231997403Sobrien __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 232097403Sobrien _Distance __chunk_size, _Compare __comp) 232197403Sobrien { 232297403Sobrien while (__last - __first >= __chunk_size) { 232397403Sobrien __insertion_sort(__first, __first + __chunk_size, __comp); 232497403Sobrien __first += __chunk_size; 232597403Sobrien } 232697403Sobrien __insertion_sort(__first, __last, __comp); 232797403Sobrien } 232897403Sobrien 232997403Sobrien template<typename _RandomAccessIter, typename _Pointer> 233097403Sobrien void 233197403Sobrien __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, 233297403Sobrien _Pointer __buffer) 233397403Sobrien { 233497403Sobrien typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 233597403Sobrien 233697403Sobrien _Distance __len = __last - __first; 233797403Sobrien _Pointer __buffer_last = __buffer + __len; 233897403Sobrien 233997403Sobrien _Distance __step_size = _M_chunk_size; 234097403Sobrien __chunk_insertion_sort(__first, __last, __step_size); 234197403Sobrien 234297403Sobrien while (__step_size < __len) { 234397403Sobrien __merge_sort_loop(__first, __last, __buffer, __step_size); 234497403Sobrien __step_size *= 2; 234597403Sobrien __merge_sort_loop(__buffer, __buffer_last, __first, __step_size); 234697403Sobrien __step_size *= 2; 234797403Sobrien } 234897403Sobrien } 234997403Sobrien 235097403Sobrien template<typename _RandomAccessIter, typename _Pointer, typename _Compare> 235197403Sobrien void 235297403Sobrien __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, 235397403Sobrien _Pointer __buffer, _Compare __comp) 235497403Sobrien { 235597403Sobrien typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 235697403Sobrien 235797403Sobrien _Distance __len = __last - __first; 235897403Sobrien _Pointer __buffer_last = __buffer + __len; 235997403Sobrien 236097403Sobrien _Distance __step_size = _M_chunk_size; 236197403Sobrien __chunk_insertion_sort(__first, __last, __step_size, __comp); 236297403Sobrien 236397403Sobrien while (__step_size < __len) { 236497403Sobrien __merge_sort_loop(__first, __last, __buffer, __step_size, __comp); 236597403Sobrien __step_size *= 2; 236697403Sobrien __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp); 236797403Sobrien __step_size *= 2; 236897403Sobrien } 236997403Sobrien } 237097403Sobrien 237197403Sobrien template<typename _RandomAccessIter, typename _Pointer, typename _Distance> 237297403Sobrien void 237397403Sobrien __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, 237497403Sobrien _Pointer __buffer, _Distance __buffer_size) 237597403Sobrien { 237697403Sobrien _Distance __len = (__last - __first + 1) / 2; 237797403Sobrien _RandomAccessIter __middle = __first + __len; 237897403Sobrien if (__len > __buffer_size) { 237997403Sobrien __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size); 238097403Sobrien __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size); 238197403Sobrien } 238297403Sobrien else { 238397403Sobrien __merge_sort_with_buffer(__first, __middle, __buffer); 238497403Sobrien __merge_sort_with_buffer(__middle, __last, __buffer); 238597403Sobrien } 238697403Sobrien __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 238797403Sobrien _Distance(__last - __middle), __buffer, __buffer_size); 238897403Sobrien } 238997403Sobrien 239097403Sobrien template<typename _RandomAccessIter, typename _Pointer, typename _Distance, 239197403Sobrien typename _Compare> 239297403Sobrien void 239397403Sobrien __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, 239497403Sobrien _Pointer __buffer, _Distance __buffer_size, 239597403Sobrien _Compare __comp) 239697403Sobrien { 239797403Sobrien _Distance __len = (__last - __first + 1) / 2; 239897403Sobrien _RandomAccessIter __middle = __first + __len; 239997403Sobrien if (__len > __buffer_size) { 240097403Sobrien __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, 240197403Sobrien __comp); 240297403Sobrien __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, 240397403Sobrien __comp); 240497403Sobrien } 240597403Sobrien else { 240697403Sobrien __merge_sort_with_buffer(__first, __middle, __buffer, __comp); 240797403Sobrien __merge_sort_with_buffer(__middle, __last, __buffer, __comp); 240897403Sobrien } 240997403Sobrien __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 241097403Sobrien _Distance(__last - __middle), __buffer, __buffer_size, 241197403Sobrien __comp); 241297403Sobrien } 241397403Sobrien 241497403Sobrien /** 241597403Sobrien * @brief Sort the elements of a sequence, preserving the relative order 241697403Sobrien * of equivalent elements. 241797403Sobrien * @param first An iterator. 241897403Sobrien * @param last Another iterator. 241997403Sobrien * @return Nothing. 242097403Sobrien * 242197403Sobrien * Sorts the elements in the range @p [first,last) in ascending order, 242297403Sobrien * such that @p *(i+1)<*i is false for each iterator @p i in the range 242397403Sobrien * @p [first,last-1). 242497403Sobrien * 242597403Sobrien * The relative ordering of equivalent elements is preserved, so any two 242697403Sobrien * elements @p x and @p y in the range @p [first,last) such that 242797403Sobrien * @p x<y is false and @p y<x is false will have the same relative 242897403Sobrien * ordering after calling @p stable_sort(). 242997403Sobrien */ 243097403Sobrien template<typename _RandomAccessIter> 243197403Sobrien inline void 243297403Sobrien stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) 243397403Sobrien { 243497403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 243597403Sobrien typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 243697403Sobrien 243797403Sobrien // concept requirements 243897403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 243997403Sobrien _RandomAccessIter>) 244097403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 244197403Sobrien 244297403Sobrien _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last); 244397403Sobrien if (buf.begin() == 0) 244497403Sobrien __inplace_stable_sort(__first, __last); 244597403Sobrien else 244697403Sobrien __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size())); 244797403Sobrien } 244897403Sobrien 244997403Sobrien /** 245097403Sobrien * @brief Sort the elements of a sequence using a predicate for comparison, 245197403Sobrien * preserving the relative order of equivalent elements. 245297403Sobrien * @param first An iterator. 245397403Sobrien * @param last Another iterator. 245497403Sobrien * @param comp A comparison functor. 245597403Sobrien * @return Nothing. 245697403Sobrien * 245797403Sobrien * Sorts the elements in the range @p [first,last) in ascending order, 245897403Sobrien * such that @p comp(*(i+1),*i) is false for each iterator @p i in the 245997403Sobrien * range @p [first,last-1). 246097403Sobrien * 246197403Sobrien * The relative ordering of equivalent elements is preserved, so any two 246297403Sobrien * elements @p x and @p y in the range @p [first,last) such that 246397403Sobrien * @p comp(x,y) is false and @p comp(y,x) is false will have the same 246497403Sobrien * relative ordering after calling @p stable_sort(). 246597403Sobrien */ 246697403Sobrien template<typename _RandomAccessIter, typename _Compare> 246797403Sobrien inline void 246897403Sobrien stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) 246997403Sobrien { 247097403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 247197403Sobrien typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 247297403Sobrien 247397403Sobrien // concept requirements 247497403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 247597403Sobrien _RandomAccessIter>) 247697403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 247797403Sobrien _ValueType, _ValueType>) 247897403Sobrien 247997403Sobrien _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last); 248097403Sobrien if (buf.begin() == 0) 248197403Sobrien __inplace_stable_sort(__first, __last, __comp); 248297403Sobrien else 248397403Sobrien __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()), 248497403Sobrien __comp); 248597403Sobrien } 248697403Sobrien 248797403Sobrien /** 248897403Sobrien * @brief Sort the smallest elements of a sequence. 248997403Sobrien * @param first An iterator. 249097403Sobrien * @param middle Another iterator. 249197403Sobrien * @param last Another iterator. 249297403Sobrien * @return Nothing. 249397403Sobrien * 249497403Sobrien * Sorts the smallest @p (middle-first) elements in the range 249597403Sobrien * @p [first,last) and moves them to the range @p [first,middle). The 249697403Sobrien * order of the remaining elements in the range @p [middle,last) is 249797403Sobrien * undefined. 249897403Sobrien * After the sort if @p i and @j are iterators in the range 249997403Sobrien * @p [first,middle) such that @i precedes @j and @k is an iterator in 250097403Sobrien * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false. 250197403Sobrien */ 250297403Sobrien template<typename _RandomAccessIter> 250397403Sobrien void 250497403Sobrien partial_sort(_RandomAccessIter __first, 250597403Sobrien _RandomAccessIter __middle, 250697403Sobrien _RandomAccessIter __last) 250797403Sobrien { 250897403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 250997403Sobrien 251097403Sobrien // concept requirements 251197403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 251297403Sobrien _RandomAccessIter>) 251397403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 251497403Sobrien 251597403Sobrien make_heap(__first, __middle); 251697403Sobrien for (_RandomAccessIter __i = __middle; __i < __last; ++__i) 251797403Sobrien if (*__i < *__first) 251897403Sobrien __pop_heap(__first, __middle, __i, _ValueType(*__i)); 251997403Sobrien sort_heap(__first, __middle); 252097403Sobrien } 252197403Sobrien 252297403Sobrien /** 252397403Sobrien * @brief Sort the smallest elements of a sequence using a predicate 252497403Sobrien * for comparison. 252597403Sobrien * @param first An iterator. 252697403Sobrien * @param middle Another iterator. 252797403Sobrien * @param last Another iterator. 252897403Sobrien * @param comp A comparison functor. 252997403Sobrien * @return Nothing. 253097403Sobrien * 253197403Sobrien * Sorts the smallest @p (middle-first) elements in the range 253297403Sobrien * @p [first,last) and moves them to the range @p [first,middle). The 253397403Sobrien * order of the remaining elements in the range @p [middle,last) is 253497403Sobrien * undefined. 253597403Sobrien * After the sort if @p i and @j are iterators in the range 253697403Sobrien * @p [first,middle) such that @i precedes @j and @k is an iterator in 253797403Sobrien * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i) 253897403Sobrien * are both false. 253997403Sobrien */ 254097403Sobrien template<typename _RandomAccessIter, typename _Compare> 254197403Sobrien void 254297403Sobrien partial_sort(_RandomAccessIter __first, 254397403Sobrien _RandomAccessIter __middle, 254497403Sobrien _RandomAccessIter __last, 254597403Sobrien _Compare __comp) 254697403Sobrien { 254797403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 254897403Sobrien 254997403Sobrien // concept requirements 255097403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 255197403Sobrien _RandomAccessIter>) 255297403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 255397403Sobrien _ValueType, _ValueType>) 255497403Sobrien 255597403Sobrien make_heap(__first, __middle, __comp); 255697403Sobrien for (_RandomAccessIter __i = __middle; __i < __last; ++__i) 255797403Sobrien if (__comp(*__i, *__first)) 255897403Sobrien __pop_heap(__first, __middle, __i, _ValueType(*__i), __comp); 255997403Sobrien sort_heap(__first, __middle, __comp); 256097403Sobrien } 256197403Sobrien 256297403Sobrien /** 256397403Sobrien * @brief Copy the smallest elements of a sequence. 256497403Sobrien * @param first An iterator. 256597403Sobrien * @param last Another iterator. 256697403Sobrien * @param result_first A random-access iterator. 256797403Sobrien * @param result_last Another random-access iterator. 256897403Sobrien * @return An iterator indicating the end of the resulting sequence. 256997403Sobrien * 257097403Sobrien * Copies and sorts the smallest N values from the range @p [first,last) 257197403Sobrien * to the range beginning at @p result_first, where the number of 257297403Sobrien * elements to be copied, @p N, is the smaller of @p (last-first) and 257397403Sobrien * @p (result_last-result_first). 257497403Sobrien * After the sort if @p i and @j are iterators in the range 257597403Sobrien * @p [result_first,result_first+N) such that @i precedes @j then 257697403Sobrien * @p *j<*i is false. 257797403Sobrien * The value returned is @p result_first+N. 257897403Sobrien */ 257997403Sobrien template<typename _InputIter, typename _RandomAccessIter> 258097403Sobrien _RandomAccessIter 258197403Sobrien partial_sort_copy(_InputIter __first, _InputIter __last, 258297403Sobrien _RandomAccessIter __result_first, 258397403Sobrien _RandomAccessIter __result_last) 258497403Sobrien { 258597403Sobrien typedef typename iterator_traits<_InputIter>::value_type _InputValueType; 258697403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType; 258797403Sobrien typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 258897403Sobrien 258997403Sobrien // concept requirements 259097403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 259197403Sobrien __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>) 259297403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_OutputValueType>) 259397403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_InputValueType>) 259497403Sobrien 259597403Sobrien if (__result_first == __result_last) return __result_last; 259697403Sobrien _RandomAccessIter __result_real_last = __result_first; 259797403Sobrien while(__first != __last && __result_real_last != __result_last) { 259897403Sobrien *__result_real_last = *__first; 259997403Sobrien ++__result_real_last; 260097403Sobrien ++__first; 260197403Sobrien } 260297403Sobrien make_heap(__result_first, __result_real_last); 260397403Sobrien while (__first != __last) { 260497403Sobrien if (*__first < *__result_first) 260597403Sobrien __adjust_heap(__result_first, _DistanceType(0), 260697403Sobrien _DistanceType(__result_real_last - __result_first), 260797403Sobrien _InputValueType(*__first)); 260897403Sobrien ++__first; 260997403Sobrien } 261097403Sobrien sort_heap(__result_first, __result_real_last); 261197403Sobrien return __result_real_last; 261297403Sobrien } 261397403Sobrien 261497403Sobrien /** 261597403Sobrien * @brief Copy the smallest elements of a sequence using a predicate for 261697403Sobrien * comparison. 261797403Sobrien * @param first An input iterator. 261897403Sobrien * @param last Another input iterator. 261997403Sobrien * @param result_first A random-access iterator. 262097403Sobrien * @param result_last Another random-access iterator. 262197403Sobrien * @param comp A comparison functor. 262297403Sobrien * @return An iterator indicating the end of the resulting sequence. 262397403Sobrien * 262497403Sobrien * Copies and sorts the smallest N values from the range @p [first,last) 262597403Sobrien * to the range beginning at @p result_first, where the number of 262697403Sobrien * elements to be copied, @p N, is the smaller of @p (last-first) and 262797403Sobrien * @p (result_last-result_first). 262897403Sobrien * After the sort if @p i and @j are iterators in the range 262997403Sobrien * @p [result_first,result_first+N) such that @i precedes @j then 263097403Sobrien * @p comp(*j,*i) is false. 263197403Sobrien * The value returned is @p result_first+N. 263297403Sobrien */ 263397403Sobrien template<typename _InputIter, typename _RandomAccessIter, typename _Compare> 263497403Sobrien _RandomAccessIter 263597403Sobrien partial_sort_copy(_InputIter __first, _InputIter __last, 263697403Sobrien _RandomAccessIter __result_first, 263797403Sobrien _RandomAccessIter __result_last, 263897403Sobrien _Compare __comp) 263997403Sobrien { 264097403Sobrien typedef typename iterator_traits<_InputIter>::value_type _InputValueType; 264197403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType; 264297403Sobrien typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 264397403Sobrien 264497403Sobrien // concept requirements 264597403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 264697403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 264797403Sobrien __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>) 264897403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 264997403Sobrien _OutputValueType, _OutputValueType>) 265097403Sobrien 265197403Sobrien if (__result_first == __result_last) return __result_last; 265297403Sobrien _RandomAccessIter __result_real_last = __result_first; 265397403Sobrien while(__first != __last && __result_real_last != __result_last) { 265497403Sobrien *__result_real_last = *__first; 265597403Sobrien ++__result_real_last; 265697403Sobrien ++__first; 265797403Sobrien } 265897403Sobrien make_heap(__result_first, __result_real_last, __comp); 265997403Sobrien while (__first != __last) { 266097403Sobrien if (__comp(*__first, *__result_first)) 266197403Sobrien __adjust_heap(__result_first, _DistanceType(0), 266297403Sobrien _DistanceType(__result_real_last - __result_first), 266397403Sobrien _InputValueType(*__first), 266497403Sobrien __comp); 266597403Sobrien ++__first; 266697403Sobrien } 266797403Sobrien sort_heap(__result_first, __result_real_last, __comp); 266897403Sobrien return __result_real_last; 266997403Sobrien } 267097403Sobrien 267197403Sobrien /** 267297403Sobrien * @brief Sort a sequence just enough to find a particular position. 267397403Sobrien * @param first An iterator. 267497403Sobrien * @param nth Another iterator. 267597403Sobrien * @param last Another iterator. 267697403Sobrien * @return Nothing. 267797403Sobrien * 267897403Sobrien * Rearranges the elements in the range @p [first,last) so that @p *nth 267997403Sobrien * is the same element that would have been in that position had the 268097403Sobrien * whole sequence been sorted. 268197403Sobrien * whole sequence been sorted. The elements either side of @p *nth are 268297403Sobrien * not completely sorted, but for any iterator @i in the range 268397403Sobrien * @p [first,nth) and any iterator @j in the range @p [nth,last) it 268497403Sobrien * holds that @p *j<*i is false. 268597403Sobrien */ 268697403Sobrien template<typename _RandomAccessIter> 268797403Sobrien void 268897403Sobrien nth_element(_RandomAccessIter __first, 268997403Sobrien _RandomAccessIter __nth, 269097403Sobrien _RandomAccessIter __last) 269197403Sobrien { 269297403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 269397403Sobrien 269497403Sobrien // concept requirements 269597403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 269697403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 269797403Sobrien 269897403Sobrien while (__last - __first > 3) { 269997403Sobrien _RandomAccessIter __cut = 270097403Sobrien __unguarded_partition(__first, __last, 270197403Sobrien _ValueType(__median(*__first, 270297403Sobrien *(__first + (__last - __first)/2), 270397403Sobrien *(__last - 1)))); 270497403Sobrien if (__cut <= __nth) 270597403Sobrien __first = __cut; 270697403Sobrien else 270797403Sobrien __last = __cut; 270897403Sobrien } 270997403Sobrien __insertion_sort(__first, __last); 271097403Sobrien } 271197403Sobrien 271297403Sobrien /** 271397403Sobrien * @brief Sort a sequence just enough to find a particular position 271497403Sobrien * using a predicate for comparison. 271597403Sobrien * @param first An iterator. 271697403Sobrien * @param nth Another iterator. 271797403Sobrien * @param last Another iterator. 271897403Sobrien * @param comp A comparison functor. 271997403Sobrien * @return Nothing. 272097403Sobrien * 272197403Sobrien * Rearranges the elements in the range @p [first,last) so that @p *nth 272297403Sobrien * is the same element that would have been in that position had the 272397403Sobrien * whole sequence been sorted. The elements either side of @p *nth are 272497403Sobrien * not completely sorted, but for any iterator @i in the range 272597403Sobrien * @p [first,nth) and any iterator @j in the range @p [nth,last) it 272697403Sobrien * holds that @p comp(*j,*i) is false. 272797403Sobrien */ 272897403Sobrien template<typename _RandomAccessIter, typename _Compare> 272997403Sobrien void 273097403Sobrien nth_element(_RandomAccessIter __first, 273197403Sobrien _RandomAccessIter __nth, 273297403Sobrien _RandomAccessIter __last, 273397403Sobrien _Compare __comp) 273497403Sobrien { 273597403Sobrien typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 273697403Sobrien 273797403Sobrien // concept requirements 273897403Sobrien __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 273997403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 274097403Sobrien _ValueType, _ValueType>) 274197403Sobrien 274297403Sobrien while (__last - __first > 3) { 274397403Sobrien _RandomAccessIter __cut = 274497403Sobrien __unguarded_partition(__first, __last, 274597403Sobrien _ValueType(__median(*__first, 274697403Sobrien *(__first + (__last - __first)/2), 274797403Sobrien *(__last - 1), 274897403Sobrien __comp)), 274997403Sobrien __comp); 275097403Sobrien if (__cut <= __nth) 275197403Sobrien __first = __cut; 275297403Sobrien else 275397403Sobrien __last = __cut; 275497403Sobrien } 275597403Sobrien __insertion_sort(__first, __last, __comp); 275697403Sobrien } 275797403Sobrien 275897403Sobrien 275997403Sobrien /** 276097403Sobrien * @brief Finds the first position in which @a val could be inserted 276197403Sobrien * without changing the ordering. 276297403Sobrien * @param first An iterator. 276397403Sobrien * @param last Another iterator. 276497403Sobrien * @param val The search term. 276597403Sobrien * @return An iterator pointing to the first element "not less than" @a val. 276697403Sobrien * @ingroup binarysearch 276797403Sobrien */ 276897403Sobrien template<typename _ForwardIter, typename _Tp> 276997403Sobrien _ForwardIter 277097403Sobrien lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 277197403Sobrien { 277297403Sobrien typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 277397403Sobrien typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 277497403Sobrien 277597403Sobrien // concept requirements 277697403Sobrien // Note that these are slightly stricter than those of the 4-argument 277797403Sobrien // version, defined next. The difference is in the strictness of the 277897403Sobrien // comparison operations... so for looser checking, define your own 277997403Sobrien // comparison function, as was intended. 278097403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 278197403Sobrien __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 278297403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 278397403Sobrien 278497403Sobrien _DistanceType __len = distance(__first, __last); 278597403Sobrien _DistanceType __half; 278697403Sobrien _ForwardIter __middle; 278797403Sobrien 278897403Sobrien while (__len > 0) { 278997403Sobrien __half = __len >> 1; 279097403Sobrien __middle = __first; 279197403Sobrien advance(__middle, __half); 279297403Sobrien if (*__middle < __val) { 279397403Sobrien __first = __middle; 279497403Sobrien ++__first; 279597403Sobrien __len = __len - __half - 1; 279697403Sobrien } 279797403Sobrien else 279897403Sobrien __len = __half; 279997403Sobrien } 280097403Sobrien return __first; 280197403Sobrien } 280297403Sobrien 280397403Sobrien /** 280497403Sobrien * @brief Finds the first position in which @a val could be inserted 280597403Sobrien * without changing the ordering. 280697403Sobrien * @param first An iterator. 280797403Sobrien * @param last Another iterator. 280897403Sobrien * @param val The search term. 280997403Sobrien * @param comp A functor to use for comparisons. 281097403Sobrien * @return An iterator pointing to the first element "not less than" @a val. 281197403Sobrien * @ingroup binarysearch 281297403Sobrien * 281397403Sobrien * The comparison function should have the same effects on ordering as 281497403Sobrien * the function used for the initial sort. 281597403Sobrien */ 281697403Sobrien template<typename _ForwardIter, typename _Tp, typename _Compare> 281797403Sobrien _ForwardIter 281897403Sobrien lower_bound(_ForwardIter __first, _ForwardIter __last, 281997403Sobrien const _Tp& __val, _Compare __comp) 282097403Sobrien { 282197403Sobrien typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 282297403Sobrien typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 282397403Sobrien 282497403Sobrien // concept requirements 282597403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 282697403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>) 282797403Sobrien 282897403Sobrien _DistanceType __len = distance(__first, __last); 282997403Sobrien _DistanceType __half; 283097403Sobrien _ForwardIter __middle; 283197403Sobrien 283297403Sobrien while (__len > 0) { 283397403Sobrien __half = __len >> 1; 283497403Sobrien __middle = __first; 283597403Sobrien advance(__middle, __half); 283697403Sobrien if (__comp(*__middle, __val)) { 283797403Sobrien __first = __middle; 283897403Sobrien ++__first; 283997403Sobrien __len = __len - __half - 1; 284097403Sobrien } 284197403Sobrien else 284297403Sobrien __len = __half; 284397403Sobrien } 284497403Sobrien return __first; 284597403Sobrien } 284697403Sobrien 284797403Sobrien /** 284897403Sobrien * @brief Finds the last position in which @a val could be inserted 284997403Sobrien * without changing the ordering. 285097403Sobrien * @param first An iterator. 285197403Sobrien * @param last Another iterator. 285297403Sobrien * @param val The search term. 285397403Sobrien * @return An iterator pointing to the first element greater than @a val. 285497403Sobrien * @ingroup binarysearch 285597403Sobrien */ 285697403Sobrien template<typename _ForwardIter, typename _Tp> 285797403Sobrien _ForwardIter 285897403Sobrien upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 285997403Sobrien { 286097403Sobrien typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 286197403Sobrien typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 286297403Sobrien 286397403Sobrien // concept requirements 286497403Sobrien // See comments on lower_bound. 286597403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 286697403Sobrien __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 286797403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 286897403Sobrien 286997403Sobrien _DistanceType __len = distance(__first, __last); 287097403Sobrien _DistanceType __half; 287197403Sobrien _ForwardIter __middle; 287297403Sobrien 287397403Sobrien while (__len > 0) { 287497403Sobrien __half = __len >> 1; 287597403Sobrien __middle = __first; 287697403Sobrien advance(__middle, __half); 287797403Sobrien if (__val < *__middle) 287897403Sobrien __len = __half; 287997403Sobrien else { 288097403Sobrien __first = __middle; 288197403Sobrien ++__first; 288297403Sobrien __len = __len - __half - 1; 288397403Sobrien } 288497403Sobrien } 288597403Sobrien return __first; 288697403Sobrien } 288797403Sobrien 288897403Sobrien /** 288997403Sobrien * @brief Finds the last position in which @a val could be inserted 289097403Sobrien * without changing the ordering. 289197403Sobrien * @param first An iterator. 289297403Sobrien * @param last Another iterator. 289397403Sobrien * @param val The search term. 289497403Sobrien * @param comp A functor to use for comparisons. 289597403Sobrien * @return An iterator pointing to the first element greater than @a val. 289697403Sobrien * @ingroup binarysearch 289797403Sobrien * 289897403Sobrien * The comparison function should have the same effects on ordering as 289997403Sobrien * the function used for the initial sort. 290097403Sobrien */ 290197403Sobrien template<typename _ForwardIter, typename _Tp, typename _Compare> 290297403Sobrien _ForwardIter 290397403Sobrien upper_bound(_ForwardIter __first, _ForwardIter __last, 290497403Sobrien const _Tp& __val, _Compare __comp) 290597403Sobrien { 290697403Sobrien typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 290797403Sobrien typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 290897403Sobrien 290997403Sobrien // concept requirements 291097403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 291197403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>) 291297403Sobrien 291397403Sobrien _DistanceType __len = distance(__first, __last); 291497403Sobrien _DistanceType __half; 291597403Sobrien _ForwardIter __middle; 291697403Sobrien 291797403Sobrien while (__len > 0) { 291897403Sobrien __half = __len >> 1; 291997403Sobrien __middle = __first; 292097403Sobrien advance(__middle, __half); 292197403Sobrien if (__comp(__val, *__middle)) 292297403Sobrien __len = __half; 292397403Sobrien else { 292497403Sobrien __first = __middle; 292597403Sobrien ++__first; 292697403Sobrien __len = __len - __half - 1; 292797403Sobrien } 292897403Sobrien } 292997403Sobrien return __first; 293097403Sobrien } 293197403Sobrien 293297403Sobrien /** 293397403Sobrien * @brief Finds the largest subrange in which @a val could be inserted 293497403Sobrien * at any place in it without changing the ordering. 293597403Sobrien * @param first An iterator. 293697403Sobrien * @param last Another iterator. 293797403Sobrien * @param val The search term. 293897403Sobrien * @return An pair of iterators defining the subrange. 293997403Sobrien * @ingroup binarysearch 294097403Sobrien * 294197403Sobrien * This is equivalent to 294297403Sobrien * @code 294397403Sobrien * std::make_pair(lower_bound(first, last, val), 294497403Sobrien * upper_bound(first, last, val)) 294597403Sobrien * @endcode 294697403Sobrien * but does not actually call those functions. 294797403Sobrien */ 294897403Sobrien template<typename _ForwardIter, typename _Tp> 294997403Sobrien pair<_ForwardIter, _ForwardIter> 295097403Sobrien equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 295197403Sobrien { 295297403Sobrien typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 295397403Sobrien typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 295497403Sobrien 295597403Sobrien // concept requirements 295697403Sobrien // See comments on lower_bound. 295797403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 295897403Sobrien __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 295997403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 296097403Sobrien 296197403Sobrien _DistanceType __len = distance(__first, __last); 296297403Sobrien _DistanceType __half; 296397403Sobrien _ForwardIter __middle, __left, __right; 296497403Sobrien 296597403Sobrien while (__len > 0) { 296697403Sobrien __half = __len >> 1; 296797403Sobrien __middle = __first; 296897403Sobrien advance(__middle, __half); 296997403Sobrien if (*__middle < __val) { 297097403Sobrien __first = __middle; 297197403Sobrien ++__first; 297297403Sobrien __len = __len - __half - 1; 297397403Sobrien } 297497403Sobrien else if (__val < *__middle) 297597403Sobrien __len = __half; 297697403Sobrien else { 297797403Sobrien __left = lower_bound(__first, __middle, __val); 297897403Sobrien advance(__first, __len); 297997403Sobrien __right = upper_bound(++__middle, __first, __val); 298097403Sobrien return pair<_ForwardIter, _ForwardIter>(__left, __right); 298197403Sobrien } 298297403Sobrien } 298397403Sobrien return pair<_ForwardIter, _ForwardIter>(__first, __first); 298497403Sobrien } 298597403Sobrien 298697403Sobrien /** 298797403Sobrien * @brief Finds the largest subrange in which @a val could be inserted 298897403Sobrien * at any place in it without changing the ordering. 298997403Sobrien * @param first An iterator. 299097403Sobrien * @param last Another iterator. 299197403Sobrien * @param val The search term. 299297403Sobrien * @param comp A functor to use for comparisons. 299397403Sobrien * @return An pair of iterators defining the subrange. 299497403Sobrien * @ingroup binarysearch 299597403Sobrien * 299697403Sobrien * This is equivalent to 299797403Sobrien * @code 299897403Sobrien * std::make_pair(lower_bound(first, last, val, comp), 299997403Sobrien * upper_bound(first, last, val, comp)) 300097403Sobrien * @endcode 300197403Sobrien * but does not actually call those functions. 300297403Sobrien */ 300397403Sobrien template<typename _ForwardIter, typename _Tp, typename _Compare> 300497403Sobrien pair<_ForwardIter, _ForwardIter> 300597403Sobrien equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 300697403Sobrien _Compare __comp) 300797403Sobrien { 300897403Sobrien typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 300997403Sobrien typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 301097403Sobrien 301197403Sobrien // concept requirements 301297403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 301397403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>) 301497403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>) 301597403Sobrien 301697403Sobrien _DistanceType __len = distance(__first, __last); 301797403Sobrien _DistanceType __half; 301897403Sobrien _ForwardIter __middle, __left, __right; 301997403Sobrien 302097403Sobrien while (__len > 0) { 302197403Sobrien __half = __len >> 1; 302297403Sobrien __middle = __first; 302397403Sobrien advance(__middle, __half); 302497403Sobrien if (__comp(*__middle, __val)) { 302597403Sobrien __first = __middle; 302697403Sobrien ++__first; 302797403Sobrien __len = __len - __half - 1; 302897403Sobrien } 302997403Sobrien else if (__comp(__val, *__middle)) 303097403Sobrien __len = __half; 303197403Sobrien else { 303297403Sobrien __left = lower_bound(__first, __middle, __val, __comp); 303397403Sobrien advance(__first, __len); 303497403Sobrien __right = upper_bound(++__middle, __first, __val, __comp); 303597403Sobrien return pair<_ForwardIter, _ForwardIter>(__left, __right); 303697403Sobrien } 303797403Sobrien } 303897403Sobrien return pair<_ForwardIter, _ForwardIter>(__first, __first); 303997403Sobrien } 304097403Sobrien 304197403Sobrien /** 304297403Sobrien * @brief Determines whether an element exists in a range. 304397403Sobrien * @param first An iterator. 304497403Sobrien * @param last Another iterator. 304597403Sobrien * @param val The search term. 304697403Sobrien * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 304797403Sobrien * @ingroup binarysearch 304897403Sobrien * 304997403Sobrien * Note that this does not actually return an iterator to @a val. For 305097403Sobrien * that, use std::find or a container's specialized find member functions. 305197403Sobrien */ 305297403Sobrien template<typename _ForwardIter, typename _Tp> 305397403Sobrien bool 305497403Sobrien binary_search(_ForwardIter __first, _ForwardIter __last, 305597403Sobrien const _Tp& __val) 305697403Sobrien { 305797403Sobrien // concept requirements 305897403Sobrien // See comments on lower_bound. 305997403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 306097403Sobrien __glibcpp_function_requires(_SameTypeConcept<_Tp, 306197403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 306297403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 306397403Sobrien 306497403Sobrien _ForwardIter __i = lower_bound(__first, __last, __val); 306597403Sobrien return __i != __last && !(__val < *__i); 306697403Sobrien } 306797403Sobrien 306897403Sobrien /** 306997403Sobrien * @brief Determines whether an element exists in a range. 307097403Sobrien * @param first An iterator. 307197403Sobrien * @param last Another iterator. 307297403Sobrien * @param val The search term. 307397403Sobrien * @param comp A functor to use for comparisons. 307497403Sobrien * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 307597403Sobrien * @ingroup binarysearch 307697403Sobrien * 307797403Sobrien * Note that this does not actually return an iterator to @a val. For 307897403Sobrien * that, use std::find or a container's specialized find member functions. 307997403Sobrien * 308097403Sobrien * The comparison function should have the same effects on ordering as 308197403Sobrien * the function used for the initial sort. 308297403Sobrien */ 308397403Sobrien template<typename _ForwardIter, typename _Tp, typename _Compare> 308497403Sobrien bool 308597403Sobrien binary_search(_ForwardIter __first, _ForwardIter __last, 308697403Sobrien const _Tp& __val, _Compare __comp) 308797403Sobrien { 308897403Sobrien // concept requirements 308997403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 309097403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 309197403Sobrien typename iterator_traits<_ForwardIter>::value_type, _Tp>) 309297403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, 309397403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 309497403Sobrien 309597403Sobrien _ForwardIter __i = lower_bound(__first, __last, __val, __comp); 309697403Sobrien return __i != __last && !__comp(__val, *__i); 309797403Sobrien } 309897403Sobrien 309997403Sobrien /** 310097403Sobrien * @brief Merges two sorted ranges. 310197403Sobrien * @param first1 An iterator. 310297403Sobrien * @param first2 Another iterator. 310397403Sobrien * @param last1 Another iterator. 310497403Sobrien * @param last2 Another iterator. 310597403Sobrien * @param result An iterator pointing to the end of the merged range. 310697403Sobrien * @return An iterator pointing to the first element "not less than" @a val. 310797403Sobrien * 310897403Sobrien * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 310997403Sobrien * [result, result + (last1-first1) + (last2-first2)). Both input ranges 311097403Sobrien * must be sorted, and the output range must not overlap with either of 311197403Sobrien * the input ranges. The sort is @e stable, that is, for equivalent 311297403Sobrien * elements in the two ranges, elements from the first range will always 311397403Sobrien * come before elements from the second. 311497403Sobrien */ 311597403Sobrien template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 311697403Sobrien _OutputIter 311797403Sobrien merge(_InputIter1 __first1, _InputIter1 __last1, 311897403Sobrien _InputIter2 __first2, _InputIter2 __last2, 311997403Sobrien _OutputIter __result) 312097403Sobrien { 312197403Sobrien // concept requirements 312297403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 312397403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 312497403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 312597403Sobrien typename iterator_traits<_InputIter1>::value_type>) 312697403Sobrien __glibcpp_function_requires(_SameTypeConcept< 312797403Sobrien typename iterator_traits<_InputIter1>::value_type, 312897403Sobrien typename iterator_traits<_InputIter2>::value_type>) 312997403Sobrien __glibcpp_function_requires(_LessThanComparableConcept< 313097403Sobrien typename iterator_traits<_InputIter1>::value_type>) 313197403Sobrien 313297403Sobrien while (__first1 != __last1 && __first2 != __last2) { 313397403Sobrien if (*__first2 < *__first1) { 313497403Sobrien *__result = *__first2; 313597403Sobrien ++__first2; 313697403Sobrien } 313797403Sobrien else { 313897403Sobrien *__result = *__first1; 313997403Sobrien ++__first1; 314097403Sobrien } 314197403Sobrien ++__result; 314297403Sobrien } 314397403Sobrien return copy(__first2, __last2, copy(__first1, __last1, __result)); 314497403Sobrien } 314597403Sobrien 314697403Sobrien /** 314797403Sobrien * @brief Merges two sorted ranges. 314897403Sobrien * @param first1 An iterator. 314997403Sobrien * @param first2 Another iterator. 315097403Sobrien * @param last1 Another iterator. 315197403Sobrien * @param last2 Another iterator. 315297403Sobrien * @param result An iterator pointing to the end of the merged range. 315397403Sobrien * @param comp A functor to use for comparisons. 315497403Sobrien * @return An iterator pointing to the first element "not less than" @a val. 315597403Sobrien * 315697403Sobrien * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 315797403Sobrien * [result, result + (last1-first1) + (last2-first2)). Both input ranges 315897403Sobrien * must be sorted, and the output range must not overlap with either of 315997403Sobrien * the input ranges. The sort is @e stable, that is, for equivalent 316097403Sobrien * elements in the two ranges, elements from the first range will always 316197403Sobrien * come before elements from the second. 316297403Sobrien * 316397403Sobrien * The comparison function should have the same effects on ordering as 316497403Sobrien * the function used for the initial sort. 316597403Sobrien */ 316697403Sobrien template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 316797403Sobrien typename _Compare> 316897403Sobrien _OutputIter 316997403Sobrien merge(_InputIter1 __first1, _InputIter1 __last1, 317097403Sobrien _InputIter2 __first2, _InputIter2 __last2, 317197403Sobrien _OutputIter __result, _Compare __comp) 317297403Sobrien { 317397403Sobrien // concept requirements 317497403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 317597403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 317697403Sobrien __glibcpp_function_requires(_SameTypeConcept< 317797403Sobrien typename iterator_traits<_InputIter1>::value_type, 317897403Sobrien typename iterator_traits<_InputIter2>::value_type>) 317997403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 318097403Sobrien typename iterator_traits<_InputIter1>::value_type>) 318197403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 318297403Sobrien typename iterator_traits<_InputIter1>::value_type, 318397403Sobrien typename iterator_traits<_InputIter2>::value_type>) 318497403Sobrien 318597403Sobrien while (__first1 != __last1 && __first2 != __last2) { 318697403Sobrien if (__comp(*__first2, *__first1)) { 318797403Sobrien *__result = *__first2; 318897403Sobrien ++__first2; 318997403Sobrien } 319097403Sobrien else { 319197403Sobrien *__result = *__first1; 319297403Sobrien ++__first1; 319397403Sobrien } 319497403Sobrien ++__result; 319597403Sobrien } 319697403Sobrien return copy(__first2, __last2, copy(__first1, __last1, __result)); 319797403Sobrien } 319897403Sobrien 319997403Sobrien /** 320097403Sobrien * @if maint 320197403Sobrien * This is a helper function for the merge routines. 320297403Sobrien * @endif 320397403Sobrien */ 320497403Sobrien template<typename _BidirectionalIter, typename _Distance> 320597403Sobrien void 320697403Sobrien __merge_without_buffer(_BidirectionalIter __first, 320797403Sobrien _BidirectionalIter __middle, 320897403Sobrien _BidirectionalIter __last, 320997403Sobrien _Distance __len1, _Distance __len2) 321097403Sobrien { 321197403Sobrien if (__len1 == 0 || __len2 == 0) 321297403Sobrien return; 321397403Sobrien if (__len1 + __len2 == 2) { 321497403Sobrien if (*__middle < *__first) 321597403Sobrien iter_swap(__first, __middle); 321697403Sobrien return; 321797403Sobrien } 321897403Sobrien _BidirectionalIter __first_cut = __first; 321997403Sobrien _BidirectionalIter __second_cut = __middle; 322097403Sobrien _Distance __len11 = 0; 322197403Sobrien _Distance __len22 = 0; 322297403Sobrien if (__len1 > __len2) { 322397403Sobrien __len11 = __len1 / 2; 322497403Sobrien advance(__first_cut, __len11); 322597403Sobrien __second_cut = lower_bound(__middle, __last, *__first_cut); 322697403Sobrien __len22 = distance(__middle, __second_cut); 322797403Sobrien } 322897403Sobrien else { 322997403Sobrien __len22 = __len2 / 2; 323097403Sobrien advance(__second_cut, __len22); 323197403Sobrien __first_cut = upper_bound(__first, __middle, *__second_cut); 323297403Sobrien __len11 = distance(__first, __first_cut); 323397403Sobrien } 323497403Sobrien rotate(__first_cut, __middle, __second_cut); 323597403Sobrien _BidirectionalIter __new_middle = __first_cut; 323697403Sobrien advance(__new_middle, distance(__middle, __second_cut)); 323797403Sobrien __merge_without_buffer(__first, __first_cut, __new_middle, 323897403Sobrien __len11, __len22); 323997403Sobrien __merge_without_buffer(__new_middle, __second_cut, __last, 324097403Sobrien __len1 - __len11, __len2 - __len22); 324197403Sobrien } 324297403Sobrien 324397403Sobrien /** 324497403Sobrien * @if maint 324597403Sobrien * This is a helper function for the merge routines. 324697403Sobrien * @endif 324797403Sobrien */ 324897403Sobrien template<typename _BidirectionalIter, typename _Distance, typename _Compare> 324997403Sobrien void 325097403Sobrien __merge_without_buffer(_BidirectionalIter __first, 325197403Sobrien _BidirectionalIter __middle, 325297403Sobrien _BidirectionalIter __last, 325397403Sobrien _Distance __len1, _Distance __len2, 325497403Sobrien _Compare __comp) 325597403Sobrien { 325697403Sobrien if (__len1 == 0 || __len2 == 0) 325797403Sobrien return; 325897403Sobrien if (__len1 + __len2 == 2) { 325997403Sobrien if (__comp(*__middle, *__first)) 326097403Sobrien iter_swap(__first, __middle); 326197403Sobrien return; 326297403Sobrien } 326397403Sobrien _BidirectionalIter __first_cut = __first; 326497403Sobrien _BidirectionalIter __second_cut = __middle; 326597403Sobrien _Distance __len11 = 0; 326697403Sobrien _Distance __len22 = 0; 326797403Sobrien if (__len1 > __len2) { 326897403Sobrien __len11 = __len1 / 2; 326997403Sobrien advance(__first_cut, __len11); 327097403Sobrien __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); 327197403Sobrien __len22 = distance(__middle, __second_cut); 327297403Sobrien } 327397403Sobrien else { 327497403Sobrien __len22 = __len2 / 2; 327597403Sobrien advance(__second_cut, __len22); 327697403Sobrien __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); 327797403Sobrien __len11 = distance(__first, __first_cut); 327897403Sobrien } 327997403Sobrien rotate(__first_cut, __middle, __second_cut); 328097403Sobrien _BidirectionalIter __new_middle = __first_cut; 328197403Sobrien advance(__new_middle, distance(__middle, __second_cut)); 328297403Sobrien __merge_without_buffer(__first, __first_cut, __new_middle, 328397403Sobrien __len11, __len22, __comp); 328497403Sobrien __merge_without_buffer(__new_middle, __second_cut, __last, 328597403Sobrien __len1 - __len11, __len2 - __len22, __comp); 328697403Sobrien } 328797403Sobrien 328897403Sobrien /** 328997403Sobrien * @if maint 329097403Sobrien * This is a helper function for the merge routines. 329197403Sobrien * @endif 329297403Sobrien */ 329397403Sobrien template<typename _BidirectionalIter1, typename _BidirectionalIter2, 329497403Sobrien typename _Distance> 329597403Sobrien _BidirectionalIter1 329697403Sobrien __rotate_adaptive(_BidirectionalIter1 __first, 329797403Sobrien _BidirectionalIter1 __middle, 329897403Sobrien _BidirectionalIter1 __last, 329997403Sobrien _Distance __len1, _Distance __len2, 330097403Sobrien _BidirectionalIter2 __buffer, 330197403Sobrien _Distance __buffer_size) 330297403Sobrien { 330397403Sobrien _BidirectionalIter2 __buffer_end; 330497403Sobrien if (__len1 > __len2 && __len2 <= __buffer_size) { 330597403Sobrien __buffer_end = copy(__middle, __last, __buffer); 330697403Sobrien copy_backward(__first, __middle, __last); 330797403Sobrien return copy(__buffer, __buffer_end, __first); 330897403Sobrien } 330997403Sobrien else if (__len1 <= __buffer_size) { 331097403Sobrien __buffer_end = copy(__first, __middle, __buffer); 331197403Sobrien copy(__middle, __last, __first); 331297403Sobrien return copy_backward(__buffer, __buffer_end, __last); 331397403Sobrien } 331497403Sobrien else { 331597403Sobrien rotate(__first, __middle, __last); 331697403Sobrien advance(__first, distance(__middle, __last)); 331797403Sobrien return __first; 331897403Sobrien } 331997403Sobrien } 332097403Sobrien 332197403Sobrien /** 332297403Sobrien * @if maint 332397403Sobrien * This is a helper function for the merge routines. 332497403Sobrien * @endif 332597403Sobrien */ 332697403Sobrien template<typename _BidirectionalIter1, typename _BidirectionalIter2, 332797403Sobrien typename _BidirectionalIter3> 332897403Sobrien _BidirectionalIter3 332997403Sobrien __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 333097403Sobrien _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 333197403Sobrien _BidirectionalIter3 __result) 333297403Sobrien { 333397403Sobrien if (__first1 == __last1) 333497403Sobrien return copy_backward(__first2, __last2, __result); 333597403Sobrien if (__first2 == __last2) 333697403Sobrien return copy_backward(__first1, __last1, __result); 333797403Sobrien --__last1; 333897403Sobrien --__last2; 333997403Sobrien while (true) { 334097403Sobrien if (*__last2 < *__last1) { 334197403Sobrien *--__result = *__last1; 334297403Sobrien if (__first1 == __last1) 334397403Sobrien return copy_backward(__first2, ++__last2, __result); 334497403Sobrien --__last1; 334597403Sobrien } 334697403Sobrien else { 334797403Sobrien *--__result = *__last2; 334897403Sobrien if (__first2 == __last2) 334997403Sobrien return copy_backward(__first1, ++__last1, __result); 335097403Sobrien --__last2; 335197403Sobrien } 335297403Sobrien } 335397403Sobrien } 335497403Sobrien 335597403Sobrien /** 335697403Sobrien * @if maint 335797403Sobrien * This is a helper function for the merge routines. 335897403Sobrien * @endif 335997403Sobrien */ 336097403Sobrien template<typename _BidirectionalIter1, typename _BidirectionalIter2, 336197403Sobrien typename _BidirectionalIter3, typename _Compare> 336297403Sobrien _BidirectionalIter3 336397403Sobrien __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 336497403Sobrien _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 336597403Sobrien _BidirectionalIter3 __result, 336697403Sobrien _Compare __comp) 336797403Sobrien { 336897403Sobrien if (__first1 == __last1) 336997403Sobrien return copy_backward(__first2, __last2, __result); 337097403Sobrien if (__first2 == __last2) 337197403Sobrien return copy_backward(__first1, __last1, __result); 337297403Sobrien --__last1; 337397403Sobrien --__last2; 337497403Sobrien while (true) { 337597403Sobrien if (__comp(*__last2, *__last1)) { 337697403Sobrien *--__result = *__last1; 337797403Sobrien if (__first1 == __last1) 337897403Sobrien return copy_backward(__first2, ++__last2, __result); 337997403Sobrien --__last1; 338097403Sobrien } 338197403Sobrien else { 338297403Sobrien *--__result = *__last2; 338397403Sobrien if (__first2 == __last2) 338497403Sobrien return copy_backward(__first1, ++__last1, __result); 338597403Sobrien --__last2; 338697403Sobrien } 338797403Sobrien } 338897403Sobrien } 338997403Sobrien 339097403Sobrien /** 339197403Sobrien * @if maint 339297403Sobrien * This is a helper function for the merge routines. 339397403Sobrien * @endif 339497403Sobrien */ 339597403Sobrien template<typename _BidirectionalIter, typename _Distance, typename _Pointer> 339697403Sobrien void 339797403Sobrien __merge_adaptive(_BidirectionalIter __first, 339897403Sobrien _BidirectionalIter __middle, 339997403Sobrien _BidirectionalIter __last, 340097403Sobrien _Distance __len1, _Distance __len2, 340197403Sobrien _Pointer __buffer, _Distance __buffer_size) 340297403Sobrien { 340397403Sobrien if (__len1 <= __len2 && __len1 <= __buffer_size) { 340497403Sobrien _Pointer __buffer_end = copy(__first, __middle, __buffer); 340597403Sobrien merge(__buffer, __buffer_end, __middle, __last, __first); 340697403Sobrien } 340797403Sobrien else if (__len2 <= __buffer_size) { 340897403Sobrien _Pointer __buffer_end = copy(__middle, __last, __buffer); 340997403Sobrien __merge_backward(__first, __middle, __buffer, __buffer_end, __last); 341097403Sobrien } 341197403Sobrien else { 341297403Sobrien _BidirectionalIter __first_cut = __first; 341397403Sobrien _BidirectionalIter __second_cut = __middle; 341497403Sobrien _Distance __len11 = 0; 341597403Sobrien _Distance __len22 = 0; 341697403Sobrien if (__len1 > __len2) { 341797403Sobrien __len11 = __len1 / 2; 341897403Sobrien advance(__first_cut, __len11); 341997403Sobrien __second_cut = lower_bound(__middle, __last, *__first_cut); 342097403Sobrien __len22 = distance(__middle, __second_cut); 342197403Sobrien } 342297403Sobrien else { 342397403Sobrien __len22 = __len2 / 2; 342497403Sobrien advance(__second_cut, __len22); 342597403Sobrien __first_cut = upper_bound(__first, __middle, *__second_cut); 342697403Sobrien __len11 = distance(__first, __first_cut); 342797403Sobrien } 342897403Sobrien _BidirectionalIter __new_middle = 342997403Sobrien __rotate_adaptive(__first_cut, __middle, __second_cut, 343097403Sobrien __len1 - __len11, __len22, __buffer, 343197403Sobrien __buffer_size); 343297403Sobrien __merge_adaptive(__first, __first_cut, __new_middle, __len11, 343397403Sobrien __len22, __buffer, __buffer_size); 343497403Sobrien __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 343597403Sobrien __len2 - __len22, __buffer, __buffer_size); 343697403Sobrien } 343797403Sobrien } 343897403Sobrien 343997403Sobrien /** 344097403Sobrien * @if maint 344197403Sobrien * This is a helper function for the merge routines. 344297403Sobrien * @endif 344397403Sobrien */ 344497403Sobrien template<typename _BidirectionalIter, typename _Distance, typename _Pointer, 344597403Sobrien typename _Compare> 344697403Sobrien void 344797403Sobrien __merge_adaptive(_BidirectionalIter __first, 344897403Sobrien _BidirectionalIter __middle, 344997403Sobrien _BidirectionalIter __last, 345097403Sobrien _Distance __len1, _Distance __len2, 345197403Sobrien _Pointer __buffer, _Distance __buffer_size, 345297403Sobrien _Compare __comp) 345397403Sobrien { 345497403Sobrien if (__len1 <= __len2 && __len1 <= __buffer_size) { 345597403Sobrien _Pointer __buffer_end = copy(__first, __middle, __buffer); 345697403Sobrien merge(__buffer, __buffer_end, __middle, __last, __first, __comp); 345797403Sobrien } 345897403Sobrien else if (__len2 <= __buffer_size) { 345997403Sobrien _Pointer __buffer_end = copy(__middle, __last, __buffer); 346097403Sobrien __merge_backward(__first, __middle, __buffer, __buffer_end, __last, 346197403Sobrien __comp); 346297403Sobrien } 346397403Sobrien else { 346497403Sobrien _BidirectionalIter __first_cut = __first; 346597403Sobrien _BidirectionalIter __second_cut = __middle; 346697403Sobrien _Distance __len11 = 0; 346797403Sobrien _Distance __len22 = 0; 346897403Sobrien if (__len1 > __len2) { 346997403Sobrien __len11 = __len1 / 2; 347097403Sobrien advance(__first_cut, __len11); 347197403Sobrien __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); 347297403Sobrien __len22 = distance(__middle, __second_cut); 347397403Sobrien } 347497403Sobrien else { 347597403Sobrien __len22 = __len2 / 2; 347697403Sobrien advance(__second_cut, __len22); 347797403Sobrien __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); 347897403Sobrien __len11 = distance(__first, __first_cut); 347997403Sobrien } 348097403Sobrien _BidirectionalIter __new_middle = 348197403Sobrien __rotate_adaptive(__first_cut, __middle, __second_cut, 348297403Sobrien __len1 - __len11, __len22, __buffer, 348397403Sobrien __buffer_size); 348497403Sobrien __merge_adaptive(__first, __first_cut, __new_middle, __len11, 348597403Sobrien __len22, __buffer, __buffer_size, __comp); 348697403Sobrien __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 348797403Sobrien __len2 - __len22, __buffer, __buffer_size, __comp); 348897403Sobrien } 348997403Sobrien } 349097403Sobrien 349197403Sobrien /** 349297403Sobrien * @brief Merges two sorted ranges in place. 349397403Sobrien * @param first An iterator. 349497403Sobrien * @param middle Another iterator. 349597403Sobrien * @param last Another iterator. 349697403Sobrien * @return Nothing. 349797403Sobrien * 349897403Sobrien * Merges two sorted and consecutive ranges, [first,middle) and 349997403Sobrien * [middle,last), and puts the result in [first,last). The output will 350097403Sobrien * be sorted. The sort is @e stable, that is, for equivalent 350197403Sobrien * elements in the two ranges, elements from the first range will always 350297403Sobrien * come before elements from the second. 350397403Sobrien * 350497403Sobrien * If enough additional memory is available, this takes (last-first)-1 350597403Sobrien * comparisons. Otherwise an NlogN algorithm is used, where N is 350697403Sobrien * distance(first,last). 350797403Sobrien */ 350897403Sobrien template<typename _BidirectionalIter> 350997403Sobrien void 351097403Sobrien inplace_merge(_BidirectionalIter __first, 351197403Sobrien _BidirectionalIter __middle, 351297403Sobrien _BidirectionalIter __last) 351397403Sobrien { 351497403Sobrien typedef typename iterator_traits<_BidirectionalIter>::value_type 351597403Sobrien _ValueType; 351697403Sobrien typedef typename iterator_traits<_BidirectionalIter>::difference_type 351797403Sobrien _DistanceType; 351897403Sobrien 351997403Sobrien // concept requirements 352097403Sobrien __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 352197403Sobrien _BidirectionalIter>) 352297403Sobrien __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 352397403Sobrien 352497403Sobrien if (__first == __middle || __middle == __last) 352597403Sobrien return; 352697403Sobrien 352797403Sobrien _DistanceType __len1 = distance(__first, __middle); 352897403Sobrien _DistanceType __len2 = distance(__middle, __last); 352997403Sobrien 353097403Sobrien _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last); 353197403Sobrien if (__buf.begin() == 0) 353297403Sobrien __merge_without_buffer(__first, __middle, __last, __len1, __len2); 353397403Sobrien else 353497403Sobrien __merge_adaptive(__first, __middle, __last, __len1, __len2, 353597403Sobrien __buf.begin(), _DistanceType(__buf.size())); 353697403Sobrien } 353797403Sobrien 353897403Sobrien /** 353997403Sobrien * @brief Merges two sorted ranges in place. 354097403Sobrien * @param first An iterator. 354197403Sobrien * @param middle Another iterator. 354297403Sobrien * @param last Another iterator. 354397403Sobrien * @param comp A functor to use for comparisons. 354497403Sobrien * @return Nothing. 354597403Sobrien * 354697403Sobrien * Merges two sorted and consecutive ranges, [first,middle) and 354797403Sobrien * [middle,last), and puts the result in [first,last). The output will 354897403Sobrien * be sorted. The sort is @e stable, that is, for equivalent 354997403Sobrien * elements in the two ranges, elements from the first range will always 355097403Sobrien * come before elements from the second. 355197403Sobrien * 355297403Sobrien * If enough additional memory is available, this takes (last-first)-1 355397403Sobrien * comparisons. Otherwise an NlogN algorithm is used, where N is 355497403Sobrien * distance(first,last). 355597403Sobrien * 355697403Sobrien * The comparison function should have the same effects on ordering as 355797403Sobrien * the function used for the initial sort. 355897403Sobrien */ 355997403Sobrien template<typename _BidirectionalIter, typename _Compare> 356097403Sobrien void 356197403Sobrien inplace_merge(_BidirectionalIter __first, 356297403Sobrien _BidirectionalIter __middle, 356397403Sobrien _BidirectionalIter __last, 356497403Sobrien _Compare __comp) 356597403Sobrien { 356697403Sobrien typedef typename iterator_traits<_BidirectionalIter>::value_type 356797403Sobrien _ValueType; 356897403Sobrien typedef typename iterator_traits<_BidirectionalIter>::difference_type 356997403Sobrien _DistanceType; 357097403Sobrien 357197403Sobrien // concept requirements 357297403Sobrien __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 357397403Sobrien _BidirectionalIter>) 357497403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 357597403Sobrien _ValueType, _ValueType>) 357697403Sobrien 357797403Sobrien if (__first == __middle || __middle == __last) 357897403Sobrien return; 357997403Sobrien 358097403Sobrien _DistanceType __len1 = distance(__first, __middle); 358197403Sobrien _DistanceType __len2 = distance(__middle, __last); 358297403Sobrien 358397403Sobrien _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last); 358497403Sobrien if (__buf.begin() == 0) 358597403Sobrien __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp); 358697403Sobrien else 358797403Sobrien __merge_adaptive(__first, __middle, __last, __len1, __len2, 358897403Sobrien __buf.begin(), _DistanceType(__buf.size()), 358997403Sobrien __comp); 359097403Sobrien } 359197403Sobrien 359297403Sobrien // Set algorithms: includes, set_union, set_intersection, set_difference, 359397403Sobrien // set_symmetric_difference. All of these algorithms have the precondition 359497403Sobrien // that their input ranges are sorted and the postcondition that their output 359597403Sobrien // ranges are sorted. 359697403Sobrien 359797403Sobrien template<typename _InputIter1, typename _InputIter2> 359897403Sobrien bool 359997403Sobrien includes(_InputIter1 __first1, _InputIter1 __last1, 360097403Sobrien _InputIter2 __first2, _InputIter2 __last2) 360197403Sobrien { 360297403Sobrien // concept requirements 360397403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 360497403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 360597403Sobrien __glibcpp_function_requires(_SameTypeConcept< 360697403Sobrien typename iterator_traits<_InputIter1>::value_type, 360797403Sobrien typename iterator_traits<_InputIter2>::value_type>) 360897403Sobrien __glibcpp_function_requires(_LessThanComparableConcept< 360997403Sobrien typename iterator_traits<_InputIter1>::value_type>) 361097403Sobrien 361197403Sobrien while (__first1 != __last1 && __first2 != __last2) 361297403Sobrien if (*__first2 < *__first1) 361397403Sobrien return false; 361497403Sobrien else if(*__first1 < *__first2) 361597403Sobrien ++__first1; 361697403Sobrien else 361797403Sobrien ++__first1, ++__first2; 361897403Sobrien 361997403Sobrien return __first2 == __last2; 362097403Sobrien } 362197403Sobrien 362297403Sobrien template<typename _InputIter1, typename _InputIter2, typename _Compare> 362397403Sobrien bool 362497403Sobrien includes(_InputIter1 __first1, _InputIter1 __last1, 362597403Sobrien _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) 362697403Sobrien { 362797403Sobrien // concept requirements 362897403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 362997403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 363097403Sobrien __glibcpp_function_requires(_SameTypeConcept< 363197403Sobrien typename iterator_traits<_InputIter1>::value_type, 363297403Sobrien typename iterator_traits<_InputIter2>::value_type>) 363397403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 363497403Sobrien typename iterator_traits<_InputIter1>::value_type, 363597403Sobrien typename iterator_traits<_InputIter2>::value_type>) 363697403Sobrien 363797403Sobrien while (__first1 != __last1 && __first2 != __last2) 363897403Sobrien if (__comp(*__first2, *__first1)) 363997403Sobrien return false; 364097403Sobrien else if(__comp(*__first1, *__first2)) 364197403Sobrien ++__first1; 364297403Sobrien else 364397403Sobrien ++__first1, ++__first2; 364497403Sobrien 364597403Sobrien return __first2 == __last2; 364697403Sobrien } 364797403Sobrien 364897403Sobrien template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 364997403Sobrien _OutputIter 365097403Sobrien set_union(_InputIter1 __first1, _InputIter1 __last1, 365197403Sobrien _InputIter2 __first2, _InputIter2 __last2, 365297403Sobrien _OutputIter __result) 365397403Sobrien { 365497403Sobrien // concept requirements 365597403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 365697403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 365797403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 365897403Sobrien typename iterator_traits<_InputIter1>::value_type>) 365997403Sobrien __glibcpp_function_requires(_SameTypeConcept< 366097403Sobrien typename iterator_traits<_InputIter1>::value_type, 366197403Sobrien typename iterator_traits<_InputIter2>::value_type>) 366297403Sobrien __glibcpp_function_requires(_LessThanComparableConcept< 366397403Sobrien typename iterator_traits<_InputIter1>::value_type>) 366497403Sobrien 366597403Sobrien while (__first1 != __last1 && __first2 != __last2) { 366697403Sobrien if (*__first1 < *__first2) { 366797403Sobrien *__result = *__first1; 366897403Sobrien ++__first1; 366997403Sobrien } 367097403Sobrien else if (*__first2 < *__first1) { 367197403Sobrien *__result = *__first2; 367297403Sobrien ++__first2; 367397403Sobrien } 367497403Sobrien else { 367597403Sobrien *__result = *__first1; 367697403Sobrien ++__first1; 367797403Sobrien ++__first2; 367897403Sobrien } 367997403Sobrien ++__result; 368097403Sobrien } 368197403Sobrien return copy(__first2, __last2, copy(__first1, __last1, __result)); 368297403Sobrien } 368397403Sobrien 368497403Sobrien template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 368597403Sobrien typename _Compare> 368697403Sobrien _OutputIter 368797403Sobrien set_union(_InputIter1 __first1, _InputIter1 __last1, 368897403Sobrien _InputIter2 __first2, _InputIter2 __last2, 368997403Sobrien _OutputIter __result, _Compare __comp) 369097403Sobrien { 369197403Sobrien // concept requirements 369297403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 369397403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 369497403Sobrien __glibcpp_function_requires(_SameTypeConcept< 369597403Sobrien typename iterator_traits<_InputIter1>::value_type, 369697403Sobrien typename iterator_traits<_InputIter2>::value_type>) 369797403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 369897403Sobrien typename iterator_traits<_InputIter1>::value_type>) 369997403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 370097403Sobrien typename iterator_traits<_InputIter1>::value_type, 370197403Sobrien typename iterator_traits<_InputIter2>::value_type>) 370297403Sobrien 370397403Sobrien while (__first1 != __last1 && __first2 != __last2) { 370497403Sobrien if (__comp(*__first1, *__first2)) { 370597403Sobrien *__result = *__first1; 370697403Sobrien ++__first1; 370797403Sobrien } 370897403Sobrien else if (__comp(*__first2, *__first1)) { 370997403Sobrien *__result = *__first2; 371097403Sobrien ++__first2; 371197403Sobrien } 371297403Sobrien else { 371397403Sobrien *__result = *__first1; 371497403Sobrien ++__first1; 371597403Sobrien ++__first2; 371697403Sobrien } 371797403Sobrien ++__result; 371897403Sobrien } 371997403Sobrien return copy(__first2, __last2, copy(__first1, __last1, __result)); 372097403Sobrien } 372197403Sobrien 372297403Sobrien template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 372397403Sobrien _OutputIter 372497403Sobrien set_intersection(_InputIter1 __first1, _InputIter1 __last1, 372597403Sobrien _InputIter2 __first2, _InputIter2 __last2, 372697403Sobrien _OutputIter __result) 372797403Sobrien { 372897403Sobrien // concept requirements 372997403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 373097403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 373197403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 373297403Sobrien typename iterator_traits<_InputIter1>::value_type>) 373397403Sobrien __glibcpp_function_requires(_SameTypeConcept< 373497403Sobrien typename iterator_traits<_InputIter1>::value_type, 373597403Sobrien typename iterator_traits<_InputIter2>::value_type>) 373697403Sobrien __glibcpp_function_requires(_LessThanComparableConcept< 373797403Sobrien typename iterator_traits<_InputIter1>::value_type>) 373897403Sobrien 373997403Sobrien while (__first1 != __last1 && __first2 != __last2) 374097403Sobrien if (*__first1 < *__first2) 374197403Sobrien ++__first1; 374297403Sobrien else if (*__first2 < *__first1) 374397403Sobrien ++__first2; 374497403Sobrien else { 374597403Sobrien *__result = *__first1; 374697403Sobrien ++__first1; 374797403Sobrien ++__first2; 374897403Sobrien ++__result; 374997403Sobrien } 375097403Sobrien return __result; 375197403Sobrien } 375297403Sobrien 375397403Sobrien template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 375497403Sobrien typename _Compare> 375597403Sobrien _OutputIter 375697403Sobrien set_intersection(_InputIter1 __first1, _InputIter1 __last1, 375797403Sobrien _InputIter2 __first2, _InputIter2 __last2, 375897403Sobrien _OutputIter __result, _Compare __comp) 375997403Sobrien { 376097403Sobrien // concept requirements 376197403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 376297403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 376397403Sobrien __glibcpp_function_requires(_SameTypeConcept< 376497403Sobrien typename iterator_traits<_InputIter1>::value_type, 376597403Sobrien typename iterator_traits<_InputIter2>::value_type>) 376697403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 376797403Sobrien typename iterator_traits<_InputIter1>::value_type>) 376897403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 376997403Sobrien typename iterator_traits<_InputIter1>::value_type, 377097403Sobrien typename iterator_traits<_InputIter2>::value_type>) 377197403Sobrien 377297403Sobrien while (__first1 != __last1 && __first2 != __last2) 377397403Sobrien if (__comp(*__first1, *__first2)) 377497403Sobrien ++__first1; 377597403Sobrien else if (__comp(*__first2, *__first1)) 377697403Sobrien ++__first2; 377797403Sobrien else { 377897403Sobrien *__result = *__first1; 377997403Sobrien ++__first1; 378097403Sobrien ++__first2; 378197403Sobrien ++__result; 378297403Sobrien } 378397403Sobrien return __result; 378497403Sobrien } 378597403Sobrien 378697403Sobrien template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 378797403Sobrien _OutputIter 378897403Sobrien set_difference(_InputIter1 __first1, _InputIter1 __last1, 378997403Sobrien _InputIter2 __first2, _InputIter2 __last2, 379097403Sobrien _OutputIter __result) 379197403Sobrien { 379297403Sobrien // concept requirements 379397403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 379497403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 379597403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 379697403Sobrien typename iterator_traits<_InputIter1>::value_type>) 379797403Sobrien __glibcpp_function_requires(_SameTypeConcept< 379897403Sobrien typename iterator_traits<_InputIter1>::value_type, 379997403Sobrien typename iterator_traits<_InputIter2>::value_type>) 380097403Sobrien __glibcpp_function_requires(_LessThanComparableConcept< 380197403Sobrien typename iterator_traits<_InputIter1>::value_type>) 380297403Sobrien 380397403Sobrien while (__first1 != __last1 && __first2 != __last2) 380497403Sobrien if (*__first1 < *__first2) { 380597403Sobrien *__result = *__first1; 380697403Sobrien ++__first1; 380797403Sobrien ++__result; 380897403Sobrien } 380997403Sobrien else if (*__first2 < *__first1) 381097403Sobrien ++__first2; 381197403Sobrien else { 381297403Sobrien ++__first1; 381397403Sobrien ++__first2; 381497403Sobrien } 381597403Sobrien return copy(__first1, __last1, __result); 381697403Sobrien } 381797403Sobrien 381897403Sobrien template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 381997403Sobrien typename _Compare> 382097403Sobrien _OutputIter 382197403Sobrien set_difference(_InputIter1 __first1, _InputIter1 __last1, 382297403Sobrien _InputIter2 __first2, _InputIter2 __last2, 382397403Sobrien _OutputIter __result, _Compare __comp) 382497403Sobrien { 382597403Sobrien // concept requirements 382697403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 382797403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 382897403Sobrien __glibcpp_function_requires(_SameTypeConcept< 382997403Sobrien typename iterator_traits<_InputIter1>::value_type, 383097403Sobrien typename iterator_traits<_InputIter2>::value_type>) 383197403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 383297403Sobrien typename iterator_traits<_InputIter1>::value_type>) 383397403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 383497403Sobrien typename iterator_traits<_InputIter1>::value_type, 383597403Sobrien typename iterator_traits<_InputIter2>::value_type>) 383697403Sobrien 383797403Sobrien while (__first1 != __last1 && __first2 != __last2) 383897403Sobrien if (__comp(*__first1, *__first2)) { 383997403Sobrien *__result = *__first1; 384097403Sobrien ++__first1; 384197403Sobrien ++__result; 384297403Sobrien } 384397403Sobrien else if (__comp(*__first2, *__first1)) 384497403Sobrien ++__first2; 384597403Sobrien else { 384697403Sobrien ++__first1; 384797403Sobrien ++__first2; 384897403Sobrien } 384997403Sobrien return copy(__first1, __last1, __result); 385097403Sobrien } 385197403Sobrien 385297403Sobrien template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 385397403Sobrien _OutputIter 385497403Sobrien set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 385597403Sobrien _InputIter2 __first2, _InputIter2 __last2, 385697403Sobrien _OutputIter __result) 385797403Sobrien { 385897403Sobrien // concept requirements 385997403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 386097403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 386197403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 386297403Sobrien typename iterator_traits<_InputIter1>::value_type>) 386397403Sobrien __glibcpp_function_requires(_SameTypeConcept< 386497403Sobrien typename iterator_traits<_InputIter1>::value_type, 386597403Sobrien typename iterator_traits<_InputIter2>::value_type>) 386697403Sobrien __glibcpp_function_requires(_LessThanComparableConcept< 386797403Sobrien typename iterator_traits<_InputIter1>::value_type>) 386897403Sobrien 386997403Sobrien while (__first1 != __last1 && __first2 != __last2) 387097403Sobrien if (*__first1 < *__first2) { 387197403Sobrien *__result = *__first1; 387297403Sobrien ++__first1; 387397403Sobrien ++__result; 387497403Sobrien } 387597403Sobrien else if (*__first2 < *__first1) { 387697403Sobrien *__result = *__first2; 387797403Sobrien ++__first2; 387897403Sobrien ++__result; 387997403Sobrien } 388097403Sobrien else { 388197403Sobrien ++__first1; 388297403Sobrien ++__first2; 388397403Sobrien } 388497403Sobrien return copy(__first2, __last2, copy(__first1, __last1, __result)); 388597403Sobrien } 388697403Sobrien 388797403Sobrien template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 388897403Sobrien typename _Compare> 388997403Sobrien _OutputIter 389097403Sobrien set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 389197403Sobrien _InputIter2 __first2, _InputIter2 __last2, 389297403Sobrien _OutputIter __result, 389397403Sobrien _Compare __comp) 389497403Sobrien { 389597403Sobrien // concept requirements 389697403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 389797403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 389897403Sobrien __glibcpp_function_requires(_SameTypeConcept< 389997403Sobrien typename iterator_traits<_InputIter1>::value_type, 390097403Sobrien typename iterator_traits<_InputIter2>::value_type>) 390197403Sobrien __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 390297403Sobrien typename iterator_traits<_InputIter1>::value_type>) 390397403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 390497403Sobrien typename iterator_traits<_InputIter1>::value_type, 390597403Sobrien typename iterator_traits<_InputIter2>::value_type>) 390697403Sobrien 390797403Sobrien while (__first1 != __last1 && __first2 != __last2) 390897403Sobrien if (__comp(*__first1, *__first2)) { 390997403Sobrien *__result = *__first1; 391097403Sobrien ++__first1; 391197403Sobrien ++__result; 391297403Sobrien } 391397403Sobrien else if (__comp(*__first2, *__first1)) { 391497403Sobrien *__result = *__first2; 391597403Sobrien ++__first2; 391697403Sobrien ++__result; 391797403Sobrien } 391897403Sobrien else { 391997403Sobrien ++__first1; 392097403Sobrien ++__first2; 392197403Sobrien } 392297403Sobrien return copy(__first2, __last2, copy(__first1, __last1, __result)); 392397403Sobrien } 392497403Sobrien 392597403Sobrien // min_element and max_element, with and without an explicitly supplied 392697403Sobrien // comparison function. 392797403Sobrien 392897403Sobrien template<typename _ForwardIter> 392997403Sobrien _ForwardIter 393097403Sobrien max_element(_ForwardIter __first, _ForwardIter __last) 393197403Sobrien { 393297403Sobrien // concept requirements 393397403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 393497403Sobrien __glibcpp_function_requires(_LessThanComparableConcept< 393597403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 393697403Sobrien 393797403Sobrien if (__first == __last) return __first; 393897403Sobrien _ForwardIter __result = __first; 393997403Sobrien while (++__first != __last) 394097403Sobrien if (*__result < *__first) 394197403Sobrien __result = __first; 394297403Sobrien return __result; 394397403Sobrien } 394497403Sobrien 394597403Sobrien template<typename _ForwardIter, typename _Compare> 394697403Sobrien _ForwardIter 394797403Sobrien max_element(_ForwardIter __first, _ForwardIter __last, 394897403Sobrien _Compare __comp) 394997403Sobrien { 395097403Sobrien // concept requirements 395197403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 395297403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 395397403Sobrien typename iterator_traits<_ForwardIter>::value_type, 395497403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 395597403Sobrien 395697403Sobrien if (__first == __last) return __first; 395797403Sobrien _ForwardIter __result = __first; 395897403Sobrien while (++__first != __last) 395997403Sobrien if (__comp(*__result, *__first)) __result = __first; 396097403Sobrien return __result; 396197403Sobrien } 396297403Sobrien 396397403Sobrien template<typename _ForwardIter> 396497403Sobrien _ForwardIter 396597403Sobrien min_element(_ForwardIter __first, _ForwardIter __last) 396697403Sobrien { 396797403Sobrien // concept requirements 396897403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 396997403Sobrien __glibcpp_function_requires(_LessThanComparableConcept< 397097403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 397197403Sobrien 397297403Sobrien if (__first == __last) return __first; 397397403Sobrien _ForwardIter __result = __first; 397497403Sobrien while (++__first != __last) 397597403Sobrien if (*__first < *__result) 397697403Sobrien __result = __first; 397797403Sobrien return __result; 397897403Sobrien } 397997403Sobrien 398097403Sobrien template<typename _ForwardIter, typename _Compare> 398197403Sobrien _ForwardIter 398297403Sobrien min_element(_ForwardIter __first, _ForwardIter __last, 398397403Sobrien _Compare __comp) 398497403Sobrien { 398597403Sobrien // concept requirements 398697403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 398797403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 398897403Sobrien typename iterator_traits<_ForwardIter>::value_type, 398997403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 399097403Sobrien 399197403Sobrien if (__first == __last) return __first; 399297403Sobrien _ForwardIter __result = __first; 399397403Sobrien while (++__first != __last) 399497403Sobrien if (__comp(*__first, *__result)) 399597403Sobrien __result = __first; 399697403Sobrien return __result; 399797403Sobrien } 399897403Sobrien 399997403Sobrien // next_permutation and prev_permutation, with and without an explicitly 400097403Sobrien // supplied comparison function. 400197403Sobrien 400297403Sobrien template<typename _BidirectionalIter> 400397403Sobrien bool 400497403Sobrien next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) 400597403Sobrien { 400697403Sobrien // concept requirements 400797403Sobrien __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 400897403Sobrien __glibcpp_function_requires(_LessThanComparableConcept< 400997403Sobrien typename iterator_traits<_BidirectionalIter>::value_type>) 401097403Sobrien 401197403Sobrien if (__first == __last) 401297403Sobrien return false; 401397403Sobrien _BidirectionalIter __i = __first; 401497403Sobrien ++__i; 401597403Sobrien if (__i == __last) 401697403Sobrien return false; 401797403Sobrien __i = __last; 401897403Sobrien --__i; 401997403Sobrien 402097403Sobrien for(;;) { 402197403Sobrien _BidirectionalIter __ii = __i; 402297403Sobrien --__i; 402397403Sobrien if (*__i < *__ii) { 402497403Sobrien _BidirectionalIter __j = __last; 402597403Sobrien while (!(*__i < *--__j)) 402697403Sobrien {} 402797403Sobrien iter_swap(__i, __j); 402897403Sobrien reverse(__ii, __last); 402997403Sobrien return true; 403097403Sobrien } 403197403Sobrien if (__i == __first) { 403297403Sobrien reverse(__first, __last); 403397403Sobrien return false; 403497403Sobrien } 403597403Sobrien } 403697403Sobrien } 403797403Sobrien 403897403Sobrien template<typename _BidirectionalIter, typename _Compare> 403997403Sobrien bool 404097403Sobrien next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 404197403Sobrien _Compare __comp) 404297403Sobrien { 404397403Sobrien // concept requirements 404497403Sobrien __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 404597403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 404697403Sobrien typename iterator_traits<_BidirectionalIter>::value_type, 404797403Sobrien typename iterator_traits<_BidirectionalIter>::value_type>) 404897403Sobrien 404997403Sobrien if (__first == __last) 405097403Sobrien return false; 405197403Sobrien _BidirectionalIter __i = __first; 405297403Sobrien ++__i; 405397403Sobrien if (__i == __last) 405497403Sobrien return false; 405597403Sobrien __i = __last; 405697403Sobrien --__i; 405797403Sobrien 405897403Sobrien for(;;) { 405997403Sobrien _BidirectionalIter __ii = __i; 406097403Sobrien --__i; 406197403Sobrien if (__comp(*__i, *__ii)) { 406297403Sobrien _BidirectionalIter __j = __last; 406397403Sobrien while (!__comp(*__i, *--__j)) 406497403Sobrien {} 406597403Sobrien iter_swap(__i, __j); 406697403Sobrien reverse(__ii, __last); 406797403Sobrien return true; 406897403Sobrien } 406997403Sobrien if (__i == __first) { 407097403Sobrien reverse(__first, __last); 407197403Sobrien return false; 407297403Sobrien } 407397403Sobrien } 407497403Sobrien } 407597403Sobrien 407697403Sobrien template<typename _BidirectionalIter> 407797403Sobrien bool 407897403Sobrien prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) 407997403Sobrien { 408097403Sobrien // concept requirements 408197403Sobrien __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 408297403Sobrien __glibcpp_function_requires(_LessThanComparableConcept< 408397403Sobrien typename iterator_traits<_BidirectionalIter>::value_type>) 408497403Sobrien 408597403Sobrien if (__first == __last) 408697403Sobrien return false; 408797403Sobrien _BidirectionalIter __i = __first; 408897403Sobrien ++__i; 408997403Sobrien if (__i == __last) 409097403Sobrien return false; 409197403Sobrien __i = __last; 409297403Sobrien --__i; 409397403Sobrien 409497403Sobrien for(;;) { 409597403Sobrien _BidirectionalIter __ii = __i; 409697403Sobrien --__i; 409797403Sobrien if (*__ii < *__i) { 409897403Sobrien _BidirectionalIter __j = __last; 409997403Sobrien while (!(*--__j < *__i)) 410097403Sobrien {} 410197403Sobrien iter_swap(__i, __j); 410297403Sobrien reverse(__ii, __last); 410397403Sobrien return true; 410497403Sobrien } 410597403Sobrien if (__i == __first) { 410697403Sobrien reverse(__first, __last); 410797403Sobrien return false; 410897403Sobrien } 410997403Sobrien } 411097403Sobrien } 411197403Sobrien 411297403Sobrien template<typename _BidirectionalIter, typename _Compare> 411397403Sobrien bool 411497403Sobrien prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 411597403Sobrien _Compare __comp) 411697403Sobrien { 411797403Sobrien // concept requirements 411897403Sobrien __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 411997403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 412097403Sobrien typename iterator_traits<_BidirectionalIter>::value_type, 412197403Sobrien typename iterator_traits<_BidirectionalIter>::value_type>) 412297403Sobrien 412397403Sobrien if (__first == __last) 412497403Sobrien return false; 412597403Sobrien _BidirectionalIter __i = __first; 412697403Sobrien ++__i; 412797403Sobrien if (__i == __last) 412897403Sobrien return false; 412997403Sobrien __i = __last; 413097403Sobrien --__i; 413197403Sobrien 413297403Sobrien for(;;) { 413397403Sobrien _BidirectionalIter __ii = __i; 413497403Sobrien --__i; 413597403Sobrien if (__comp(*__ii, *__i)) { 413697403Sobrien _BidirectionalIter __j = __last; 413797403Sobrien while (!__comp(*--__j, *__i)) 413897403Sobrien {} 413997403Sobrien iter_swap(__i, __j); 414097403Sobrien reverse(__ii, __last); 414197403Sobrien return true; 414297403Sobrien } 414397403Sobrien if (__i == __first) { 414497403Sobrien reverse(__first, __last); 414597403Sobrien return false; 414697403Sobrien } 414797403Sobrien } 414897403Sobrien } 414997403Sobrien 415097403Sobrien // find_first_of, with and without an explicitly supplied comparison function. 415197403Sobrien 415297403Sobrien template<typename _InputIter, typename _ForwardIter> 415397403Sobrien _InputIter 415497403Sobrien find_first_of(_InputIter __first1, _InputIter __last1, 415597403Sobrien _ForwardIter __first2, _ForwardIter __last2) 415697403Sobrien { 415797403Sobrien // concept requirements 415897403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 415997403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 416097403Sobrien __glibcpp_function_requires(_EqualOpConcept< 416197403Sobrien typename iterator_traits<_InputIter>::value_type, 416297403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 416397403Sobrien 416497403Sobrien for ( ; __first1 != __last1; ++__first1) 416597403Sobrien for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) 416697403Sobrien if (*__first1 == *__iter) 416797403Sobrien return __first1; 416897403Sobrien return __last1; 416997403Sobrien } 417097403Sobrien 417197403Sobrien template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate> 417297403Sobrien _InputIter 417397403Sobrien find_first_of(_InputIter __first1, _InputIter __last1, 417497403Sobrien _ForwardIter __first2, _ForwardIter __last2, 417597403Sobrien _BinaryPredicate __comp) 417697403Sobrien { 417797403Sobrien // concept requirements 417897403Sobrien __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 417997403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 418097403Sobrien __glibcpp_function_requires(_EqualOpConcept< 418197403Sobrien typename iterator_traits<_InputIter>::value_type, 418297403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 418397403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 418497403Sobrien typename iterator_traits<_InputIter>::value_type, 418597403Sobrien typename iterator_traits<_ForwardIter>::value_type>) 418697403Sobrien 418797403Sobrien for ( ; __first1 != __last1; ++__first1) 418897403Sobrien for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) 418997403Sobrien if (__comp(*__first1, *__iter)) 419097403Sobrien return __first1; 419197403Sobrien return __last1; 419297403Sobrien } 419397403Sobrien 419497403Sobrien 419597403Sobrien // find_end, with and without an explicitly supplied comparison function. 419697403Sobrien // Search [first2, last2) as a subsequence in [first1, last1), and return 419797403Sobrien // the *last* possible match. Note that find_end for bidirectional iterators 419897403Sobrien // is much faster than for forward iterators. 419997403Sobrien 420097403Sobrien // find_end for forward iterators. 420197403Sobrien template<typename _ForwardIter1, typename _ForwardIter2> 420297403Sobrien _ForwardIter1 420397403Sobrien __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 420497403Sobrien _ForwardIter2 __first2, _ForwardIter2 __last2, 420597403Sobrien forward_iterator_tag, forward_iterator_tag) 420697403Sobrien { 420797403Sobrien if (__first2 == __last2) 420897403Sobrien return __last1; 420997403Sobrien else { 421097403Sobrien _ForwardIter1 __result = __last1; 421197403Sobrien while (1) { 421297403Sobrien _ForwardIter1 __new_result 421397403Sobrien = search(__first1, __last1, __first2, __last2); 421497403Sobrien if (__new_result == __last1) 421597403Sobrien return __result; 421697403Sobrien else { 421797403Sobrien __result = __new_result; 421897403Sobrien __first1 = __new_result; 421997403Sobrien ++__first1; 422097403Sobrien } 422197403Sobrien } 422297403Sobrien } 422397403Sobrien } 422497403Sobrien 422597403Sobrien template<typename _ForwardIter1, typename _ForwardIter2, 422697403Sobrien typename _BinaryPredicate> 422797403Sobrien _ForwardIter1 422897403Sobrien __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 422997403Sobrien _ForwardIter2 __first2, _ForwardIter2 __last2, 423097403Sobrien forward_iterator_tag, forward_iterator_tag, 423197403Sobrien _BinaryPredicate __comp) 423297403Sobrien { 423397403Sobrien if (__first2 == __last2) 423497403Sobrien return __last1; 423597403Sobrien else { 423697403Sobrien _ForwardIter1 __result = __last1; 423797403Sobrien while (1) { 423897403Sobrien _ForwardIter1 __new_result 423997403Sobrien = search(__first1, __last1, __first2, __last2, __comp); 424097403Sobrien if (__new_result == __last1) 424197403Sobrien return __result; 424297403Sobrien else { 424397403Sobrien __result = __new_result; 424497403Sobrien __first1 = __new_result; 424597403Sobrien ++__first1; 424697403Sobrien } 424797403Sobrien } 424897403Sobrien } 424997403Sobrien } 425097403Sobrien 425197403Sobrien // find_end for bidirectional iterators. Requires partial specialization. 425297403Sobrien template<typename _BidirectionalIter1, typename _BidirectionalIter2> 425397403Sobrien _BidirectionalIter1 425497403Sobrien __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 425597403Sobrien _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 425697403Sobrien bidirectional_iterator_tag, bidirectional_iterator_tag) 425797403Sobrien { 425897403Sobrien // concept requirements 425997403Sobrien __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>) 426097403Sobrien __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>) 426197403Sobrien 426297403Sobrien typedef reverse_iterator<_BidirectionalIter1> _RevIter1; 426397403Sobrien typedef reverse_iterator<_BidirectionalIter2> _RevIter2; 426497403Sobrien 426597403Sobrien _RevIter1 __rlast1(__first1); 426697403Sobrien _RevIter2 __rlast2(__first2); 426797403Sobrien _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, 426897403Sobrien _RevIter2(__last2), __rlast2); 426997403Sobrien 427097403Sobrien if (__rresult == __rlast1) 427197403Sobrien return __last1; 427297403Sobrien else { 427397403Sobrien _BidirectionalIter1 __result = __rresult.base(); 427497403Sobrien advance(__result, -distance(__first2, __last2)); 427597403Sobrien return __result; 427697403Sobrien } 427797403Sobrien } 427897403Sobrien 427997403Sobrien template<typename _BidirectionalIter1, typename _BidirectionalIter2, 428097403Sobrien typename _BinaryPredicate> 428197403Sobrien _BidirectionalIter1 428297403Sobrien __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 428397403Sobrien _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 428497403Sobrien bidirectional_iterator_tag, bidirectional_iterator_tag, 428597403Sobrien _BinaryPredicate __comp) 428697403Sobrien { 428797403Sobrien // concept requirements 428897403Sobrien __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>) 428997403Sobrien __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>) 429097403Sobrien 429197403Sobrien typedef reverse_iterator<_BidirectionalIter1> _RevIter1; 429297403Sobrien typedef reverse_iterator<_BidirectionalIter2> _RevIter2; 429397403Sobrien 429497403Sobrien _RevIter1 __rlast1(__first1); 429597403Sobrien _RevIter2 __rlast2(__first2); 429697403Sobrien _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, 429797403Sobrien _RevIter2(__last2), __rlast2, 429897403Sobrien __comp); 429997403Sobrien 430097403Sobrien if (__rresult == __rlast1) 430197403Sobrien return __last1; 430297403Sobrien else { 430397403Sobrien _BidirectionalIter1 __result = __rresult.base(); 430497403Sobrien advance(__result, -distance(__first2, __last2)); 430597403Sobrien return __result; 430697403Sobrien } 430797403Sobrien } 430897403Sobrien 430997403Sobrien // Dispatching functions for find_end. 431097403Sobrien 431197403Sobrien template<typename _ForwardIter1, typename _ForwardIter2> 431297403Sobrien inline _ForwardIter1 431397403Sobrien find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 431497403Sobrien _ForwardIter2 __first2, _ForwardIter2 __last2) 431597403Sobrien { 431697403Sobrien // concept requirements 431797403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 431897403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 431997403Sobrien __glibcpp_function_requires(_EqualOpConcept< 432097403Sobrien typename iterator_traits<_ForwardIter1>::value_type, 432197403Sobrien typename iterator_traits<_ForwardIter2>::value_type>) 432297403Sobrien 432397403Sobrien return __find_end(__first1, __last1, __first2, __last2, 432497403Sobrien __iterator_category(__first1), 432597403Sobrien __iterator_category(__first2)); 432697403Sobrien } 432797403Sobrien 432897403Sobrien template<typename _ForwardIter1, typename _ForwardIter2, 432997403Sobrien typename _BinaryPredicate> 433097403Sobrien inline _ForwardIter1 433197403Sobrien find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 433297403Sobrien _ForwardIter2 __first2, _ForwardIter2 __last2, 433397403Sobrien _BinaryPredicate __comp) 433497403Sobrien { 433597403Sobrien // concept requirements 433697403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 433797403Sobrien __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 433897403Sobrien __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 433997403Sobrien typename iterator_traits<_ForwardIter1>::value_type, 434097403Sobrien typename iterator_traits<_ForwardIter2>::value_type>) 434197403Sobrien 434297403Sobrien return __find_end(__first1, __last1, __first2, __last2, 434397403Sobrien __iterator_category(__first1), 434497403Sobrien __iterator_category(__first2), 434597403Sobrien __comp); 434697403Sobrien } 434797403Sobrien 434897403Sobrien} // namespace std 434997403Sobrien 435097403Sobrien#endif /* __GLIBCPP_INTERNAL_ALGO_H */ 435197403Sobrien 4352