197403Sobrien// Algorithm implementation -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 597403Sobrien// 697403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 797403Sobrien// software; you can redistribute it and/or modify it under the 897403Sobrien// terms of the GNU General Public License as published by the 997403Sobrien// Free Software Foundation; either version 2, or (at your option) 1097403Sobrien// any later version. 1197403Sobrien 1297403Sobrien// This library is distributed in the hope that it will be useful, 1397403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1497403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1597403Sobrien// GNU General Public License for more details. 1697403Sobrien 1797403Sobrien// You should have received a copy of the GNU General Public License along 1897403Sobrien// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2097403Sobrien// USA. 2197403Sobrien 2297403Sobrien// As a special exception, you may use this file as part of a free software 2397403Sobrien// library without restriction. Specifically, if other files instantiate 2497403Sobrien// templates or use macros or inline functions from this file, or you compile 2597403Sobrien// this file and link it with other files to produce an executable, this 2697403Sobrien// file does not by itself cause the resulting executable to be covered by 2797403Sobrien// the GNU General Public License. This exception does not however 2897403Sobrien// invalidate any other reasons why the executable file might be covered by 2997403Sobrien// the GNU General Public License. 3097403Sobrien 3197403Sobrien/* 3297403Sobrien * 3397403Sobrien * Copyright (c) 1994 3497403Sobrien * Hewlett-Packard Company 3597403Sobrien * 3697403Sobrien * Permission to use, copy, modify, distribute and sell this software 3797403Sobrien * and its documentation for any purpose is hereby granted without fee, 3897403Sobrien * provided that the above copyright notice appear in all copies and 3997403Sobrien * that both that copyright notice and this permission notice appear 4097403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4197403Sobrien * representations about the suitability of this software for any 4297403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4397403Sobrien * 4497403Sobrien * 4597403Sobrien * Copyright (c) 1996 4697403Sobrien * Silicon Graphics Computer Systems, Inc. 4797403Sobrien * 4897403Sobrien * Permission to use, copy, modify, distribute and sell this software 4997403Sobrien * and its documentation for any purpose is hereby granted without fee, 5097403Sobrien * provided that the above copyright notice appear in all copies and 5197403Sobrien * that both that copyright notice and this permission notice appear 5297403Sobrien * in supporting documentation. Silicon Graphics makes no 5397403Sobrien * representations about the suitability of this software for any 5497403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5597403Sobrien */ 5697403Sobrien 5797403Sobrien/** @file stl_algo.h 5897403Sobrien * This is an internal header file, included by other library headers. 5997403Sobrien * You should not attempt to use it directly. 6097403Sobrien */ 6197403Sobrien 62132720Skan#ifndef _ALGO_H 63132720Skan#define _ALGO_H 1 6497403Sobrien 6597403Sobrien#include <bits/stl_heap.h> 6697403Sobrien#include <bits/stl_tempbuf.h> // for _Temporary_buffer 67132720Skan#include <debug/debug.h> 6897403Sobrien 69132720Skan// See concept_check.h for the __glibcxx_*_requires macros. 7097403Sobrien 71169691Skan_GLIBCXX_BEGIN_NAMESPACE(std) 72169691Skan 7397403Sobrien /** 7497403Sobrien * @brief Find the median of three values. 7597403Sobrien * @param a A value. 7697403Sobrien * @param b A value. 7797403Sobrien * @param c A value. 7897403Sobrien * @return One of @p a, @p b or @p c. 7997403Sobrien * 8097403Sobrien * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n 8197403Sobrien * then the value returned will be @c m. 8297403Sobrien * This is an SGI extension. 8397403Sobrien * @ingroup SGIextensions 8497403Sobrien */ 8597403Sobrien template<typename _Tp> 86132720Skan inline const _Tp& 8797403Sobrien __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) 8897403Sobrien { 8997403Sobrien // concept requirements 90132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 9197403Sobrien if (__a < __b) 9297403Sobrien if (__b < __c) 9397403Sobrien return __b; 9497403Sobrien else if (__a < __c) 9597403Sobrien return __c; 9697403Sobrien else 9797403Sobrien return __a; 9897403Sobrien else if (__a < __c) 9997403Sobrien return __a; 10097403Sobrien else if (__b < __c) 10197403Sobrien return __c; 10297403Sobrien else 10397403Sobrien return __b; 10497403Sobrien } 10597403Sobrien 10697403Sobrien /** 10797403Sobrien * @brief Find the median of three values using a predicate for comparison. 10897403Sobrien * @param a A value. 10997403Sobrien * @param b A value. 11097403Sobrien * @param c A value. 11197403Sobrien * @param comp A binary predicate. 11297403Sobrien * @return One of @p a, @p b or @p c. 11397403Sobrien * 11497403Sobrien * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) 11597403Sobrien * and @p comp(m,n) are both true then the value returned will be @c m. 11697403Sobrien * This is an SGI extension. 11797403Sobrien * @ingroup SGIextensions 11897403Sobrien */ 11997403Sobrien template<typename _Tp, typename _Compare> 12097403Sobrien inline const _Tp& 12197403Sobrien __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) 12297403Sobrien { 12397403Sobrien // concept requirements 124132720Skan __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>) 12597403Sobrien if (__comp(__a, __b)) 12697403Sobrien if (__comp(__b, __c)) 12797403Sobrien return __b; 12897403Sobrien else if (__comp(__a, __c)) 12997403Sobrien return __c; 13097403Sobrien else 13197403Sobrien return __a; 13297403Sobrien else if (__comp(__a, __c)) 13397403Sobrien return __a; 13497403Sobrien else if (__comp(__b, __c)) 13597403Sobrien return __c; 13697403Sobrien else 13797403Sobrien return __b; 13897403Sobrien } 13997403Sobrien 14097403Sobrien /** 14197403Sobrien * @brief Apply a function to every element of a sequence. 14297403Sobrien * @param first An input iterator. 14397403Sobrien * @param last An input iterator. 14497403Sobrien * @param f A unary function object. 14597403Sobrien * @return @p f. 14697403Sobrien * 14797403Sobrien * Applies the function object @p f to each element in the range 14897403Sobrien * @p [first,last). @p f must not modify the order of the sequence. 14997403Sobrien * If @p f has a return value it is ignored. 15097403Sobrien */ 151132720Skan template<typename _InputIterator, typename _Function> 15297403Sobrien _Function 153132720Skan for_each(_InputIterator __first, _InputIterator __last, _Function __f) 15497403Sobrien { 15597403Sobrien // concept requirements 156132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 157132720Skan __glibcxx_requires_valid_range(__first, __last); 15897403Sobrien for ( ; __first != __last; ++__first) 15997403Sobrien __f(*__first); 16097403Sobrien return __f; 16197403Sobrien } 16297403Sobrien 16397403Sobrien /** 16497403Sobrien * @if maint 16597403Sobrien * This is an overload used by find() for the Input Iterator case. 16697403Sobrien * @endif 16797403Sobrien */ 168132720Skan template<typename _InputIterator, typename _Tp> 169132720Skan inline _InputIterator 170169691Skan __find(_InputIterator __first, _InputIterator __last, 171169691Skan const _Tp& __val, input_iterator_tag) 17297403Sobrien { 17397403Sobrien while (__first != __last && !(*__first == __val)) 17497403Sobrien ++__first; 17597403Sobrien return __first; 17697403Sobrien } 17797403Sobrien 17897403Sobrien /** 17997403Sobrien * @if maint 18097403Sobrien * This is an overload used by find_if() for the Input Iterator case. 18197403Sobrien * @endif 18297403Sobrien */ 183132720Skan template<typename _InputIterator, typename _Predicate> 184132720Skan inline _InputIterator 185169691Skan __find_if(_InputIterator __first, _InputIterator __last, 186169691Skan _Predicate __pred, 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 */ 198132720Skan template<typename _RandomAccessIterator, typename _Tp> 199132720Skan _RandomAccessIterator 200169691Skan __find(_RandomAccessIterator __first, _RandomAccessIterator __last, 201169691Skan const _Tp& __val, random_access_iterator_tag) 20297403Sobrien { 203132720Skan typename iterator_traits<_RandomAccessIterator>::difference_type 204132720Skan __trip_count = (__last - __first) >> 2; 20597403Sobrien 206132720Skan for ( ; __trip_count > 0 ; --__trip_count) 207132720Skan { 208132720Skan if (*__first == __val) 209132720Skan return __first; 210132720Skan ++__first; 21197403Sobrien 212132720Skan if (*__first == __val) 213132720Skan return __first; 214132720Skan ++__first; 21597403Sobrien 216132720Skan if (*__first == __val) 217132720Skan return __first; 218132720Skan ++__first; 21997403Sobrien 220132720Skan if (*__first == __val) 221132720Skan return __first; 222132720Skan ++__first; 223132720Skan } 22497403Sobrien 225132720Skan switch (__last - __first) 226132720Skan { 227132720Skan case 3: 228132720Skan if (*__first == __val) 229132720Skan return __first; 230132720Skan ++__first; 231132720Skan case 2: 232132720Skan if (*__first == __val) 233132720Skan return __first; 234132720Skan ++__first; 235132720Skan case 1: 236132720Skan if (*__first == __val) 237132720Skan return __first; 238132720Skan ++__first; 239132720Skan case 0: 240132720Skan default: 241132720Skan return __last; 242132720Skan } 24397403Sobrien } 24497403Sobrien 24597403Sobrien /** 24697403Sobrien * @if maint 24797403Sobrien * This is an overload used by find_if() for the RAI case. 24897403Sobrien * @endif 24997403Sobrien */ 250132720Skan template<typename _RandomAccessIterator, typename _Predicate> 251132720Skan _RandomAccessIterator 252169691Skan __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, 253169691Skan _Predicate __pred, random_access_iterator_tag) 25497403Sobrien { 255132720Skan typename iterator_traits<_RandomAccessIterator>::difference_type 256132720Skan __trip_count = (__last - __first) >> 2; 25797403Sobrien 258132720Skan for ( ; __trip_count > 0 ; --__trip_count) 259132720Skan { 260132720Skan if (__pred(*__first)) 261132720Skan return __first; 262132720Skan ++__first; 26397403Sobrien 264132720Skan if (__pred(*__first)) 265132720Skan return __first; 266132720Skan ++__first; 26797403Sobrien 268132720Skan if (__pred(*__first)) 269132720Skan return __first; 270132720Skan ++__first; 27197403Sobrien 272132720Skan if (__pred(*__first)) 273132720Skan return __first; 274132720Skan ++__first; 275132720Skan } 27697403Sobrien 277132720Skan switch (__last - __first) 278132720Skan { 279132720Skan case 3: 280132720Skan if (__pred(*__first)) 281132720Skan return __first; 282132720Skan ++__first; 283132720Skan case 2: 284132720Skan if (__pred(*__first)) 285132720Skan return __first; 286132720Skan ++__first; 287132720Skan case 1: 288132720Skan if (__pred(*__first)) 289132720Skan return __first; 290132720Skan ++__first; 291132720Skan case 0: 292132720Skan default: 293132720Skan return __last; 294132720Skan } 29597403Sobrien } 29697403Sobrien 29797403Sobrien /** 298169691Skan * @if maint 299169691Skan * This is an overload of find() for streambuf iterators. 300169691Skan * @endif 301169691Skan */ 302169691Skan template<typename _CharT> 303169691Skan typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 304169691Skan istreambuf_iterator<_CharT> >::__type 305169691Skan find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, 306169691Skan const _CharT&); 307169691Skan 308169691Skan /** 30997403Sobrien * @brief Find the first occurrence of a value in a sequence. 31097403Sobrien * @param first An input iterator. 31197403Sobrien * @param last An input iterator. 31297403Sobrien * @param val The value to find. 31397403Sobrien * @return The first iterator @c i in the range @p [first,last) 31497403Sobrien * such that @c *i == @p val, or @p last if no such iterator exists. 31597403Sobrien */ 316132720Skan template<typename _InputIterator, typename _Tp> 317132720Skan inline _InputIterator 318132720Skan find(_InputIterator __first, _InputIterator __last, 31997403Sobrien const _Tp& __val) 32097403Sobrien { 32197403Sobrien // concept requirements 322132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 323132720Skan __glibcxx_function_requires(_EqualOpConcept< 324132720Skan typename iterator_traits<_InputIterator>::value_type, _Tp>) 325132720Skan __glibcxx_requires_valid_range(__first, __last); 326169691Skan return std::__find(__first, __last, __val, 327169691Skan std::__iterator_category(__first)); 32897403Sobrien } 32997403Sobrien 33097403Sobrien /** 33197403Sobrien * @brief Find the first element in a sequence for which a predicate is true. 33297403Sobrien * @param first An input iterator. 33397403Sobrien * @param last An input iterator. 33497403Sobrien * @param pred A predicate. 33597403Sobrien * @return The first iterator @c i in the range @p [first,last) 33697403Sobrien * such that @p pred(*i) is true, or @p last if no such iterator exists. 33797403Sobrien */ 338132720Skan template<typename _InputIterator, typename _Predicate> 339132720Skan inline _InputIterator 340132720Skan find_if(_InputIterator __first, _InputIterator __last, 34197403Sobrien _Predicate __pred) 34297403Sobrien { 34397403Sobrien // concept requirements 344132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 345132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 346132720Skan typename iterator_traits<_InputIterator>::value_type>) 347132720Skan __glibcxx_requires_valid_range(__first, __last); 348169691Skan return std::__find_if(__first, __last, __pred, 349169691Skan std::__iterator_category(__first)); 35097403Sobrien } 35197403Sobrien 35297403Sobrien /** 35397403Sobrien * @brief Find two adjacent values in a sequence that are equal. 35497403Sobrien * @param first A forward iterator. 35597403Sobrien * @param last A forward iterator. 35697403Sobrien * @return The first iterator @c i such that @c i and @c i+1 are both 35797403Sobrien * valid iterators in @p [first,last) and such that @c *i == @c *(i+1), 35897403Sobrien * or @p last if no such iterator exists. 35997403Sobrien */ 360132720Skan template<typename _ForwardIterator> 361132720Skan _ForwardIterator 362132720Skan adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 36397403Sobrien { 36497403Sobrien // concept requirements 365132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 366132720Skan __glibcxx_function_requires(_EqualityComparableConcept< 367132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 368132720Skan __glibcxx_requires_valid_range(__first, __last); 36997403Sobrien if (__first == __last) 37097403Sobrien return __last; 371132720Skan _ForwardIterator __next = __first; 372132720Skan while(++__next != __last) 373132720Skan { 374132720Skan if (*__first == *__next) 375132720Skan return __first; 376132720Skan __first = __next; 377132720Skan } 37897403Sobrien return __last; 37997403Sobrien } 38097403Sobrien 38197403Sobrien /** 38297403Sobrien * @brief Find two adjacent values in a sequence using a predicate. 38397403Sobrien * @param first A forward iterator. 38497403Sobrien * @param last A forward iterator. 38597403Sobrien * @param binary_pred A binary predicate. 38697403Sobrien * @return The first iterator @c i such that @c i and @c i+1 are both 38797403Sobrien * valid iterators in @p [first,last) and such that 38897403Sobrien * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator 38997403Sobrien * exists. 39097403Sobrien */ 391132720Skan template<typename _ForwardIterator, typename _BinaryPredicate> 392132720Skan _ForwardIterator 393132720Skan adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 39497403Sobrien _BinaryPredicate __binary_pred) 39597403Sobrien { 39697403Sobrien // concept requirements 397132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 398132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 399132720Skan typename iterator_traits<_ForwardIterator>::value_type, 400132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 401132720Skan __glibcxx_requires_valid_range(__first, __last); 40297403Sobrien if (__first == __last) 40397403Sobrien return __last; 404132720Skan _ForwardIterator __next = __first; 405132720Skan while(++__next != __last) 406132720Skan { 407132720Skan if (__binary_pred(*__first, *__next)) 408132720Skan return __first; 409132720Skan __first = __next; 410132720Skan } 41197403Sobrien return __last; 41297403Sobrien } 41397403Sobrien 41497403Sobrien /** 41597403Sobrien * @brief Count the number of copies of a value in a sequence. 41697403Sobrien * @param first An input iterator. 41797403Sobrien * @param last An input iterator. 41897403Sobrien * @param value The value to be counted. 41997403Sobrien * @return The number of iterators @c i in the range @p [first,last) 42097403Sobrien * for which @c *i == @p value 42197403Sobrien */ 422132720Skan template<typename _InputIterator, typename _Tp> 423132720Skan typename iterator_traits<_InputIterator>::difference_type 424132720Skan count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 42597403Sobrien { 42697403Sobrien // concept requirements 427132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 428169691Skan __glibcxx_function_requires(_EqualOpConcept< 429169691Skan typename iterator_traits<_InputIterator>::value_type, _Tp>) 430132720Skan __glibcxx_requires_valid_range(__first, __last); 431132720Skan typename iterator_traits<_InputIterator>::difference_type __n = 0; 43297403Sobrien for ( ; __first != __last; ++__first) 43397403Sobrien if (*__first == __value) 43497403Sobrien ++__n; 43597403Sobrien return __n; 43697403Sobrien } 43797403Sobrien 43897403Sobrien /** 43997403Sobrien * @brief Count the elements of a sequence for which a predicate is true. 44097403Sobrien * @param first An input iterator. 44197403Sobrien * @param last An input iterator. 44297403Sobrien * @param pred A predicate. 44397403Sobrien * @return The number of iterators @c i in the range @p [first,last) 44497403Sobrien * for which @p pred(*i) is true. 44597403Sobrien */ 446132720Skan template<typename _InputIterator, typename _Predicate> 447132720Skan typename iterator_traits<_InputIterator>::difference_type 448132720Skan count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 44997403Sobrien { 45097403Sobrien // concept requirements 451132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 452132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 453132720Skan typename iterator_traits<_InputIterator>::value_type>) 454132720Skan __glibcxx_requires_valid_range(__first, __last); 455132720Skan typename iterator_traits<_InputIterator>::difference_type __n = 0; 45697403Sobrien for ( ; __first != __last; ++__first) 45797403Sobrien if (__pred(*__first)) 45897403Sobrien ++__n; 45997403Sobrien return __n; 46097403Sobrien } 46197403Sobrien 46297403Sobrien /** 46397403Sobrien * @brief Search a sequence for a matching sub-sequence. 46497403Sobrien * @param first1 A forward iterator. 46597403Sobrien * @param last1 A forward iterator. 46697403Sobrien * @param first2 A forward iterator. 46797403Sobrien * @param last2 A forward iterator. 46897403Sobrien * @return The first iterator @c i in the range 46997403Sobrien * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) 47097403Sobrien * for each @c N in the range @p [0,last2-first2), or @p last1 if no 47197403Sobrien * such iterator exists. 47297403Sobrien * 47397403Sobrien * Searches the range @p [first1,last1) for a sub-sequence that compares 47497403Sobrien * equal value-by-value with the sequence given by @p [first2,last2) and 47597403Sobrien * returns an iterator to the first element of the sub-sequence, or 47697403Sobrien * @p last1 if the sub-sequence is not found. 47797403Sobrien * 47897403Sobrien * Because the sub-sequence must lie completely within the range 47997403Sobrien * @p [first1,last1) it must start at a position less than 48097403Sobrien * @p last1-(last2-first2) where @p last2-first2 is the length of the 48197403Sobrien * sub-sequence. 48297403Sobrien * This means that the returned iterator @c i will be in the range 48397403Sobrien * @p [first1,last1-(last2-first2)) 48497403Sobrien */ 485132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 486132720Skan _ForwardIterator1 487132720Skan search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 488132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2) 48997403Sobrien { 49097403Sobrien // concept requirements 491132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 492132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 493132720Skan __glibcxx_function_requires(_EqualOpConcept< 494132720Skan typename iterator_traits<_ForwardIterator1>::value_type, 495132720Skan typename iterator_traits<_ForwardIterator2>::value_type>) 496132720Skan __glibcxx_requires_valid_range(__first1, __last1); 497132720Skan __glibcxx_requires_valid_range(__first2, __last2); 49897403Sobrien // Test for empty ranges 49997403Sobrien if (__first1 == __last1 || __first2 == __last2) 50097403Sobrien return __first1; 50197403Sobrien 50297403Sobrien // Test for a pattern of length 1. 503132720Skan _ForwardIterator2 __tmp(__first2); 50497403Sobrien ++__tmp; 50597403Sobrien if (__tmp == __last2) 506132720Skan return std::find(__first1, __last1, *__first2); 50797403Sobrien 50897403Sobrien // General case. 509132720Skan _ForwardIterator2 __p1, __p; 51097403Sobrien __p1 = __first2; ++__p1; 511132720Skan _ForwardIterator1 __current = __first1; 51297403Sobrien 513132720Skan while (__first1 != __last1) 514132720Skan { 515132720Skan __first1 = std::find(__first1, __last1, *__first2); 516132720Skan if (__first1 == __last1) 517132720Skan return __last1; 51897403Sobrien 519132720Skan __p = __p1; 520132720Skan __current = __first1; 52197403Sobrien if (++__current == __last1) 52297403Sobrien return __last1; 523132720Skan 524132720Skan while (*__current == *__p) 525132720Skan { 526132720Skan if (++__p == __last2) 527132720Skan return __first1; 528132720Skan if (++__current == __last1) 529132720Skan return __last1; 530132720Skan } 531132720Skan ++__first1; 53297403Sobrien } 53397403Sobrien return __first1; 53497403Sobrien } 53597403Sobrien 53697403Sobrien /** 53797403Sobrien * @brief Search a sequence for a matching sub-sequence using a predicate. 53897403Sobrien * @param first1 A forward iterator. 53997403Sobrien * @param last1 A forward iterator. 54097403Sobrien * @param first2 A forward iterator. 54197403Sobrien * @param last2 A forward iterator. 54297403Sobrien * @param predicate A binary predicate. 54397403Sobrien * @return The first iterator @c i in the range 54497403Sobrien * @p [first1,last1-(last2-first2)) such that 54597403Sobrien * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range 54697403Sobrien * @p [0,last2-first2), or @p last1 if no such iterator exists. 54797403Sobrien * 54897403Sobrien * Searches the range @p [first1,last1) for a sub-sequence that compares 54997403Sobrien * equal value-by-value with the sequence given by @p [first2,last2), 55097403Sobrien * using @p predicate to determine equality, and returns an iterator 55197403Sobrien * to the first element of the sub-sequence, or @p last1 if no such 55297403Sobrien * iterator exists. 55397403Sobrien * 55497403Sobrien * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 55597403Sobrien */ 556132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2, 557132720Skan typename _BinaryPredicate> 558132720Skan _ForwardIterator1 559132720Skan search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 560132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2, 561132720Skan _BinaryPredicate __predicate) 56297403Sobrien { 56397403Sobrien // concept requirements 564132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 565132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 566132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 567132720Skan typename iterator_traits<_ForwardIterator1>::value_type, 568132720Skan typename iterator_traits<_ForwardIterator2>::value_type>) 569132720Skan __glibcxx_requires_valid_range(__first1, __last1); 570132720Skan __glibcxx_requires_valid_range(__first2, __last2); 57197403Sobrien 57297403Sobrien // Test for empty ranges 57397403Sobrien if (__first1 == __last1 || __first2 == __last2) 57497403Sobrien return __first1; 57597403Sobrien 57697403Sobrien // Test for a pattern of length 1. 577132720Skan _ForwardIterator2 __tmp(__first2); 57897403Sobrien ++__tmp; 579132720Skan if (__tmp == __last2) 580132720Skan { 581132720Skan while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 582132720Skan ++__first1; 583132720Skan return __first1; 584132720Skan } 58597403Sobrien 58697403Sobrien // General case. 587132720Skan _ForwardIterator2 __p1, __p; 58897403Sobrien __p1 = __first2; ++__p1; 589132720Skan _ForwardIterator1 __current = __first1; 59097403Sobrien 591132720Skan while (__first1 != __last1) 592132720Skan { 593132720Skan while (__first1 != __last1) 594132720Skan { 595132720Skan if (__predicate(*__first1, *__first2)) 596132720Skan break; 597132720Skan ++__first1; 598132720Skan } 599132720Skan while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 600132720Skan ++__first1; 601132720Skan if (__first1 == __last1) 602132720Skan return __last1; 60397403Sobrien 604132720Skan __p = __p1; 605132720Skan __current = __first1; 60697403Sobrien if (++__current == __last1) 60797403Sobrien return __last1; 608132720Skan 609132720Skan while (__predicate(*__current, *__p)) 610132720Skan { 611132720Skan if (++__p == __last2) 612132720Skan return __first1; 613132720Skan if (++__current == __last1) 614132720Skan return __last1; 615132720Skan } 616132720Skan ++__first1; 61797403Sobrien } 61897403Sobrien return __first1; 61997403Sobrien } 62097403Sobrien 62197403Sobrien /** 622169691Skan * @if maint 623169691Skan * This is an uglified 624169691Skan * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) 625169691Skan * overloaded for forward iterators. 626169691Skan * @endif 627169691Skan */ 628169691Skan template<typename _ForwardIterator, typename _Integer, typename _Tp> 629169691Skan _ForwardIterator 630169691Skan __search_n(_ForwardIterator __first, _ForwardIterator __last, 631169691Skan _Integer __count, const _Tp& __val, 632169691Skan std::forward_iterator_tag) 633169691Skan { 634169691Skan __first = std::find(__first, __last, __val); 635169691Skan while (__first != __last) 636169691Skan { 637169691Skan typename iterator_traits<_ForwardIterator>::difference_type 638169691Skan __n = __count; 639169691Skan _ForwardIterator __i = __first; 640169691Skan ++__i; 641169691Skan while (__i != __last && __n != 1 && *__i == __val) 642169691Skan { 643169691Skan ++__i; 644169691Skan --__n; 645169691Skan } 646169691Skan if (__n == 1) 647169691Skan return __first; 648169691Skan if (__i == __last) 649169691Skan return __last; 650169691Skan __first = std::find(++__i, __last, __val); 651169691Skan } 652169691Skan return __last; 653169691Skan } 654169691Skan 655169691Skan /** 656169691Skan * @if maint 657169691Skan * This is an uglified 658169691Skan * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) 659169691Skan * overloaded for random access iterators. 660169691Skan * @endif 661169691Skan */ 662169691Skan template<typename _RandomAccessIter, typename _Integer, typename _Tp> 663169691Skan _RandomAccessIter 664169691Skan __search_n(_RandomAccessIter __first, _RandomAccessIter __last, 665169691Skan _Integer __count, const _Tp& __val, 666169691Skan std::random_access_iterator_tag) 667169691Skan { 668169691Skan 669169691Skan typedef typename std::iterator_traits<_RandomAccessIter>::difference_type 670169691Skan _DistanceType; 671169691Skan 672169691Skan _DistanceType __tailSize = __last - __first; 673169691Skan const _DistanceType __pattSize = __count; 674169691Skan 675169691Skan if (__tailSize < __pattSize) 676169691Skan return __last; 677169691Skan 678169691Skan const _DistanceType __skipOffset = __pattSize - 1; 679169691Skan _RandomAccessIter __lookAhead = __first + __skipOffset; 680169691Skan __tailSize -= __pattSize; 681169691Skan 682169691Skan while (1) // the main loop... 683169691Skan { 684169691Skan // __lookAhead here is always pointing to the last element of next 685169691Skan // possible match. 686169691Skan while (!(*__lookAhead == __val)) // the skip loop... 687169691Skan { 688169691Skan if (__tailSize < __pattSize) 689169691Skan return __last; // Failure 690169691Skan __lookAhead += __pattSize; 691169691Skan __tailSize -= __pattSize; 692169691Skan } 693169691Skan _DistanceType __remainder = __skipOffset; 694169691Skan for (_RandomAccessIter __backTrack = __lookAhead - 1; 695169691Skan *__backTrack == __val; --__backTrack) 696169691Skan { 697169691Skan if (--__remainder == 0) 698169691Skan return (__lookAhead - __skipOffset); // Success 699169691Skan } 700169691Skan if (__remainder > __tailSize) 701169691Skan return __last; // Failure 702169691Skan __lookAhead += __remainder; 703169691Skan __tailSize -= __remainder; 704169691Skan } 705169691Skan } 706169691Skan 707169691Skan /** 70897403Sobrien * @brief Search a sequence for a number of consecutive values. 70997403Sobrien * @param first A forward iterator. 71097403Sobrien * @param last A forward iterator. 71197403Sobrien * @param count The number of consecutive values. 71297403Sobrien * @param val The value to find. 71397403Sobrien * @return The first iterator @c i in the range @p [first,last-count) 71497403Sobrien * such that @c *(i+N) == @p val for each @c N in the range @p [0,count), 71597403Sobrien * or @p last if no such iterator exists. 71697403Sobrien * 71797403Sobrien * Searches the range @p [first,last) for @p count consecutive elements 71897403Sobrien * equal to @p val. 71997403Sobrien */ 720132720Skan template<typename _ForwardIterator, typename _Integer, typename _Tp> 721132720Skan _ForwardIterator 722132720Skan search_n(_ForwardIterator __first, _ForwardIterator __last, 72397403Sobrien _Integer __count, const _Tp& __val) 72497403Sobrien { 72597403Sobrien // concept requirements 726132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 727169691Skan __glibcxx_function_requires(_EqualOpConcept< 728169691Skan typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 729132720Skan __glibcxx_requires_valid_range(__first, __last); 73097403Sobrien 73197403Sobrien if (__count <= 0) 73297403Sobrien return __first; 733169691Skan if (__count == 1) 734169691Skan return std::find(__first, __last, __val); 735169691Skan return std::__search_n(__first, __last, __count, __val, 736169691Skan std::__iterator_category(__first)); 737169691Skan } 738169691Skan 739169691Skan /** 740169691Skan * @if maint 741169691Skan * This is an uglified 742169691Skan * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, 743169691Skan * _BinaryPredicate) 744169691Skan * overloaded for forward iterators. 745169691Skan * @endif 746169691Skan */ 747169691Skan template<typename _ForwardIterator, typename _Integer, typename _Tp, 748169691Skan typename _BinaryPredicate> 749169691Skan _ForwardIterator 750169691Skan __search_n(_ForwardIterator __first, _ForwardIterator __last, 751169691Skan _Integer __count, const _Tp& __val, 752169691Skan _BinaryPredicate __binary_pred, std::forward_iterator_tag) 753169691Skan { 754169691Skan while (__first != __last && !__binary_pred(*__first, __val)) 755169691Skan ++__first; 756169691Skan 757169691Skan while (__first != __last) 758132720Skan { 759169691Skan typename iterator_traits<_ForwardIterator>::difference_type 760169691Skan __n = __count; 761169691Skan _ForwardIterator __i = __first; 762169691Skan ++__i; 763169691Skan while (__i != __last && __n != 1 && __binary_pred(*__i, __val)) 764132720Skan { 765132720Skan ++__i; 766169691Skan --__n; 767132720Skan } 768169691Skan if (__n == 1) 769169691Skan return __first; 770169691Skan if (__i == __last) 771169691Skan return __last; 772169691Skan __first = ++__i; 773169691Skan while (__first != __last && !__binary_pred(*__first, __val)) 774169691Skan ++__first; 77597403Sobrien } 776169691Skan return __last; 77797403Sobrien } 77897403Sobrien 77997403Sobrien /** 780169691Skan * @if maint 781169691Skan * This is an uglified 782169691Skan * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, 783169691Skan * _BinaryPredicate) 784169691Skan * overloaded for random access iterators. 785169691Skan * @endif 786169691Skan */ 787169691Skan template<typename _RandomAccessIter, typename _Integer, typename _Tp, 788169691Skan typename _BinaryPredicate> 789169691Skan _RandomAccessIter 790169691Skan __search_n(_RandomAccessIter __first, _RandomAccessIter __last, 791169691Skan _Integer __count, const _Tp& __val, 792169691Skan _BinaryPredicate __binary_pred, std::random_access_iterator_tag) 793169691Skan { 794169691Skan 795169691Skan typedef typename std::iterator_traits<_RandomAccessIter>::difference_type 796169691Skan _DistanceType; 797169691Skan 798169691Skan _DistanceType __tailSize = __last - __first; 799169691Skan const _DistanceType __pattSize = __count; 800169691Skan 801169691Skan if (__tailSize < __pattSize) 802169691Skan return __last; 803169691Skan 804169691Skan const _DistanceType __skipOffset = __pattSize - 1; 805169691Skan _RandomAccessIter __lookAhead = __first + __skipOffset; 806169691Skan __tailSize -= __pattSize; 807169691Skan 808169691Skan while (1) // the main loop... 809169691Skan { 810169691Skan // __lookAhead here is always pointing to the last element of next 811169691Skan // possible match. 812169691Skan while (!__binary_pred(*__lookAhead, __val)) // the skip loop... 813169691Skan { 814169691Skan if (__tailSize < __pattSize) 815169691Skan return __last; // Failure 816169691Skan __lookAhead += __pattSize; 817169691Skan __tailSize -= __pattSize; 818169691Skan } 819169691Skan _DistanceType __remainder = __skipOffset; 820169691Skan for (_RandomAccessIter __backTrack = __lookAhead - 1; 821169691Skan __binary_pred(*__backTrack, __val); --__backTrack) 822169691Skan { 823169691Skan if (--__remainder == 0) 824169691Skan return (__lookAhead - __skipOffset); // Success 825169691Skan } 826169691Skan if (__remainder > __tailSize) 827169691Skan return __last; // Failure 828169691Skan __lookAhead += __remainder; 829169691Skan __tailSize -= __remainder; 830169691Skan } 831169691Skan } 832169691Skan 833169691Skan /** 83497403Sobrien * @brief Search a sequence for a number of consecutive values using a 83597403Sobrien * predicate. 83697403Sobrien * @param first A forward iterator. 83797403Sobrien * @param last A forward iterator. 83897403Sobrien * @param count The number of consecutive values. 83997403Sobrien * @param val The value to find. 84097403Sobrien * @param binary_pred A binary predicate. 84197403Sobrien * @return The first iterator @c i in the range @p [first,last-count) 84297403Sobrien * such that @p binary_pred(*(i+N),val) is true for each @c N in the 84397403Sobrien * range @p [0,count), or @p last if no such iterator exists. 84497403Sobrien * 84597403Sobrien * Searches the range @p [first,last) for @p count consecutive elements 84697403Sobrien * for which the predicate returns true. 84797403Sobrien */ 848132720Skan template<typename _ForwardIterator, typename _Integer, typename _Tp, 849132720Skan typename _BinaryPredicate> 850132720Skan _ForwardIterator 851132720Skan search_n(_ForwardIterator __first, _ForwardIterator __last, 85297403Sobrien _Integer __count, const _Tp& __val, 853132720Skan _BinaryPredicate __binary_pred) 85497403Sobrien { 85597403Sobrien // concept requirements 856132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 857132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 858132720Skan typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 859132720Skan __glibcxx_requires_valid_range(__first, __last); 86097403Sobrien 86197403Sobrien if (__count <= 0) 86297403Sobrien return __first; 863169691Skan if (__count == 1) 864132720Skan { 865169691Skan while (__first != __last && !__binary_pred(*__first, __val)) 866169691Skan ++__first; 867169691Skan return __first; 86897403Sobrien } 869169691Skan return std::__search_n(__first, __last, __count, __val, __binary_pred, 870169691Skan std::__iterator_category(__first)); 87197403Sobrien } 87297403Sobrien 87397403Sobrien /** 87497403Sobrien * @brief Swap the elements of two sequences. 87597403Sobrien * @param first1 A forward iterator. 87697403Sobrien * @param last1 A forward iterator. 87797403Sobrien * @param first2 A forward iterator. 87897403Sobrien * @return An iterator equal to @p first2+(last1-first1). 87997403Sobrien * 88097403Sobrien * Swaps each element in the range @p [first1,last1) with the 88197403Sobrien * corresponding element in the range @p [first2,(last1-first1)). 88297403Sobrien * The ranges must not overlap. 88397403Sobrien */ 884132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 885132720Skan _ForwardIterator2 886132720Skan swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 887132720Skan _ForwardIterator2 __first2) 88897403Sobrien { 88997403Sobrien // concept requirements 890132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 891132720Skan _ForwardIterator1>) 892132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 893132720Skan _ForwardIterator2>) 894132720Skan __glibcxx_function_requires(_ConvertibleConcept< 895132720Skan typename iterator_traits<_ForwardIterator1>::value_type, 896132720Skan typename iterator_traits<_ForwardIterator2>::value_type>) 897132720Skan __glibcxx_function_requires(_ConvertibleConcept< 898132720Skan typename iterator_traits<_ForwardIterator2>::value_type, 899132720Skan typename iterator_traits<_ForwardIterator1>::value_type>) 900132720Skan __glibcxx_requires_valid_range(__first1, __last1); 90197403Sobrien 90297403Sobrien for ( ; __first1 != __last1; ++__first1, ++__first2) 903132720Skan std::iter_swap(__first1, __first2); 90497403Sobrien return __first2; 90597403Sobrien } 90697403Sobrien 90797403Sobrien /** 90897403Sobrien * @brief Perform an operation on a sequence. 90997403Sobrien * @param first An input iterator. 91097403Sobrien * @param last An input iterator. 91197403Sobrien * @param result An output iterator. 91297403Sobrien * @param unary_op A unary operator. 91397403Sobrien * @return An output iterator equal to @p result+(last-first). 91497403Sobrien * 91597403Sobrien * Applies the operator to each element in the input range and assigns 91697403Sobrien * the results to successive elements of the output sequence. 91797403Sobrien * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the 91897403Sobrien * range @p [0,last-first). 91997403Sobrien * 92097403Sobrien * @p unary_op must not alter its argument. 92197403Sobrien */ 922132720Skan template<typename _InputIterator, typename _OutputIterator, 923132720Skan typename _UnaryOperation> 924132720Skan _OutputIterator 925132720Skan transform(_InputIterator __first, _InputIterator __last, 926132720Skan _OutputIterator __result, _UnaryOperation __unary_op) 92797403Sobrien { 92897403Sobrien // concept requirements 929132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 930132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 93197403Sobrien // "the type returned by a _UnaryOperation" 93297403Sobrien __typeof__(__unary_op(*__first))>) 933132720Skan __glibcxx_requires_valid_range(__first, __last); 93497403Sobrien 93597403Sobrien for ( ; __first != __last; ++__first, ++__result) 93697403Sobrien *__result = __unary_op(*__first); 93797403Sobrien return __result; 93897403Sobrien } 93997403Sobrien 94097403Sobrien /** 94197403Sobrien * @brief Perform an operation on corresponding elements of two sequences. 94297403Sobrien * @param first1 An input iterator. 94397403Sobrien * @param last1 An input iterator. 94497403Sobrien * @param first2 An input iterator. 94597403Sobrien * @param result An output iterator. 94697403Sobrien * @param binary_op A binary operator. 94797403Sobrien * @return An output iterator equal to @p result+(last-first). 94897403Sobrien * 94997403Sobrien * Applies the operator to the corresponding elements in the two 95097403Sobrien * input ranges and assigns the results to successive elements of the 95197403Sobrien * output sequence. 95297403Sobrien * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each 95397403Sobrien * @c N in the range @p [0,last1-first1). 95497403Sobrien * 95597403Sobrien * @p binary_op must not alter either of its arguments. 95697403Sobrien */ 957132720Skan template<typename _InputIterator1, typename _InputIterator2, 958132720Skan typename _OutputIterator, typename _BinaryOperation> 959132720Skan _OutputIterator 960132720Skan transform(_InputIterator1 __first1, _InputIterator1 __last1, 961132720Skan _InputIterator2 __first2, _OutputIterator __result, 96297403Sobrien _BinaryOperation __binary_op) 96397403Sobrien { 96497403Sobrien // concept requirements 965132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 966132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 967132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 96897403Sobrien // "the type returned by a _BinaryOperation" 96997403Sobrien __typeof__(__binary_op(*__first1,*__first2))>) 970132720Skan __glibcxx_requires_valid_range(__first1, __last1); 97197403Sobrien 97297403Sobrien for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) 97397403Sobrien *__result = __binary_op(*__first1, *__first2); 97497403Sobrien return __result; 97597403Sobrien } 97697403Sobrien 97797403Sobrien /** 97897403Sobrien * @brief Replace each occurrence of one value in a sequence with another 97997403Sobrien * value. 98097403Sobrien * @param first A forward iterator. 98197403Sobrien * @param last A forward iterator. 98297403Sobrien * @param old_value The value to be replaced. 98397403Sobrien * @param new_value The replacement value. 98497403Sobrien * @return replace() returns no value. 98597403Sobrien * 98697403Sobrien * For each iterator @c i in the range @p [first,last) if @c *i == 98797403Sobrien * @p old_value then the assignment @c *i = @p new_value is performed. 98897403Sobrien */ 989132720Skan template<typename _ForwardIterator, typename _Tp> 99097403Sobrien void 991132720Skan replace(_ForwardIterator __first, _ForwardIterator __last, 99297403Sobrien const _Tp& __old_value, const _Tp& __new_value) 99397403Sobrien { 99497403Sobrien // concept requirements 995132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 996132720Skan _ForwardIterator>) 997132720Skan __glibcxx_function_requires(_EqualOpConcept< 998132720Skan typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 999132720Skan __glibcxx_function_requires(_ConvertibleConcept<_Tp, 1000132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1001132720Skan __glibcxx_requires_valid_range(__first, __last); 100297403Sobrien 100397403Sobrien for ( ; __first != __last; ++__first) 100497403Sobrien if (*__first == __old_value) 100597403Sobrien *__first = __new_value; 100697403Sobrien } 100797403Sobrien 100897403Sobrien /** 100997403Sobrien * @brief Replace each value in a sequence for which a predicate returns 101097403Sobrien * true with another value. 101197403Sobrien * @param first A forward iterator. 101297403Sobrien * @param last A forward iterator. 101397403Sobrien * @param pred A predicate. 101497403Sobrien * @param new_value The replacement value. 101597403Sobrien * @return replace_if() returns no value. 101697403Sobrien * 101797403Sobrien * For each iterator @c i in the range @p [first,last) if @p pred(*i) 101897403Sobrien * is true then the assignment @c *i = @p new_value is performed. 101997403Sobrien */ 1020132720Skan template<typename _ForwardIterator, typename _Predicate, typename _Tp> 102197403Sobrien void 1022132720Skan replace_if(_ForwardIterator __first, _ForwardIterator __last, 102397403Sobrien _Predicate __pred, const _Tp& __new_value) 102497403Sobrien { 102597403Sobrien // concept requirements 1026132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1027132720Skan _ForwardIterator>) 1028132720Skan __glibcxx_function_requires(_ConvertibleConcept<_Tp, 1029132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1030132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 1031132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1032132720Skan __glibcxx_requires_valid_range(__first, __last); 103397403Sobrien 103497403Sobrien for ( ; __first != __last; ++__first) 103597403Sobrien if (__pred(*__first)) 103697403Sobrien *__first = __new_value; 103797403Sobrien } 103897403Sobrien 103997403Sobrien /** 104097403Sobrien * @brief Copy a sequence, replacing each element of one value with another 104197403Sobrien * value. 104297403Sobrien * @param first An input iterator. 104397403Sobrien * @param last An input iterator. 104497403Sobrien * @param result An output iterator. 104597403Sobrien * @param old_value The value to be replaced. 104697403Sobrien * @param new_value The replacement value. 104797403Sobrien * @return The end of the output sequence, @p result+(last-first). 104897403Sobrien * 104997403Sobrien * Copies each element in the input range @p [first,last) to the 105097403Sobrien * output range @p [result,result+(last-first)) replacing elements 105197403Sobrien * equal to @p old_value with @p new_value. 105297403Sobrien */ 1053132720Skan template<typename _InputIterator, typename _OutputIterator, typename _Tp> 1054132720Skan _OutputIterator 1055132720Skan replace_copy(_InputIterator __first, _InputIterator __last, 1056132720Skan _OutputIterator __result, 105797403Sobrien const _Tp& __old_value, const _Tp& __new_value) 105897403Sobrien { 105997403Sobrien // concept requirements 1060132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1061132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1062132720Skan typename iterator_traits<_InputIterator>::value_type>) 1063132720Skan __glibcxx_function_requires(_EqualOpConcept< 1064132720Skan typename iterator_traits<_InputIterator>::value_type, _Tp>) 1065132720Skan __glibcxx_requires_valid_range(__first, __last); 106697403Sobrien 106797403Sobrien for ( ; __first != __last; ++__first, ++__result) 1068169691Skan if (*__first == __old_value) 1069169691Skan *__result = __new_value; 1070169691Skan else 1071169691Skan *__result = *__first; 107297403Sobrien return __result; 107397403Sobrien } 107497403Sobrien 107597403Sobrien /** 107697403Sobrien * @brief Copy a sequence, replacing each value for which a predicate 107797403Sobrien * returns true with another value. 107897403Sobrien * @param first An input iterator. 107997403Sobrien * @param last An input iterator. 108097403Sobrien * @param result An output iterator. 108197403Sobrien * @param pred A predicate. 108297403Sobrien * @param new_value The replacement value. 108397403Sobrien * @return The end of the output sequence, @p result+(last-first). 108497403Sobrien * 108597403Sobrien * Copies each element in the range @p [first,last) to the range 108697403Sobrien * @p [result,result+(last-first)) replacing elements for which 108797403Sobrien * @p pred returns true with @p new_value. 108897403Sobrien */ 1089132720Skan template<typename _InputIterator, typename _OutputIterator, 1090132720Skan typename _Predicate, typename _Tp> 1091132720Skan _OutputIterator 1092132720Skan replace_copy_if(_InputIterator __first, _InputIterator __last, 1093132720Skan _OutputIterator __result, 109497403Sobrien _Predicate __pred, const _Tp& __new_value) 109597403Sobrien { 109697403Sobrien // concept requirements 1097132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1098132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1099132720Skan typename iterator_traits<_InputIterator>::value_type>) 1100132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 1101132720Skan typename iterator_traits<_InputIterator>::value_type>) 1102132720Skan __glibcxx_requires_valid_range(__first, __last); 110397403Sobrien 110497403Sobrien for ( ; __first != __last; ++__first, ++__result) 1105169691Skan if (__pred(*__first)) 1106169691Skan *__result = __new_value; 1107169691Skan else 1108169691Skan *__result = *__first; 110997403Sobrien return __result; 111097403Sobrien } 111197403Sobrien 111297403Sobrien /** 111397403Sobrien * @brief Assign the result of a function object to each value in a 111497403Sobrien * sequence. 111597403Sobrien * @param first A forward iterator. 111697403Sobrien * @param last A forward iterator. 111797403Sobrien * @param gen A function object taking no arguments. 111897403Sobrien * @return generate() returns no value. 111997403Sobrien * 112097403Sobrien * Performs the assignment @c *i = @p gen() for each @c i in the range 112197403Sobrien * @p [first,last). 112297403Sobrien */ 1123132720Skan template<typename _ForwardIterator, typename _Generator> 112497403Sobrien void 1125132720Skan generate(_ForwardIterator __first, _ForwardIterator __last, 1126132720Skan _Generator __gen) 112797403Sobrien { 112897403Sobrien // concept requirements 1129132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 1130132720Skan __glibcxx_function_requires(_GeneratorConcept<_Generator, 1131132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1132132720Skan __glibcxx_requires_valid_range(__first, __last); 113397403Sobrien 113497403Sobrien for ( ; __first != __last; ++__first) 113597403Sobrien *__first = __gen(); 113697403Sobrien } 113797403Sobrien 113897403Sobrien /** 113997403Sobrien * @brief Assign the result of a function object to each value in a 114097403Sobrien * sequence. 114197403Sobrien * @param first A forward iterator. 114297403Sobrien * @param n The length of the sequence. 114397403Sobrien * @param gen A function object taking no arguments. 114497403Sobrien * @return The end of the sequence, @p first+n 114597403Sobrien * 114697403Sobrien * Performs the assignment @c *i = @p gen() for each @c i in the range 114797403Sobrien * @p [first,first+n). 114897403Sobrien */ 1149132720Skan template<typename _OutputIterator, typename _Size, typename _Generator> 1150132720Skan _OutputIterator 1151132720Skan generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 115297403Sobrien { 115397403Sobrien // concept requirements 1154132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 115597403Sobrien // "the type returned by a _Generator" 1156132720Skan __typeof__(__gen())>) 115797403Sobrien 115897403Sobrien for ( ; __n > 0; --__n, ++__first) 115997403Sobrien *__first = __gen(); 116097403Sobrien return __first; 116197403Sobrien } 116297403Sobrien 116397403Sobrien /** 116497403Sobrien * @brief Copy a sequence, removing elements of a given value. 116597403Sobrien * @param first An input iterator. 116697403Sobrien * @param last An input iterator. 116797403Sobrien * @param result An output iterator. 116897403Sobrien * @param value The value to be removed. 116997403Sobrien * @return An iterator designating the end of the resulting sequence. 117097403Sobrien * 117197403Sobrien * Copies each element in the range @p [first,last) not equal to @p value 117297403Sobrien * to the range beginning at @p result. 117397403Sobrien * remove_copy() is stable, so the relative order of elements that are 117497403Sobrien * copied is unchanged. 117597403Sobrien */ 1176132720Skan template<typename _InputIterator, typename _OutputIterator, typename _Tp> 1177132720Skan _OutputIterator 1178132720Skan remove_copy(_InputIterator __first, _InputIterator __last, 1179132720Skan _OutputIterator __result, const _Tp& __value) 118097403Sobrien { 118197403Sobrien // concept requirements 1182132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1183132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1184132720Skan typename iterator_traits<_InputIterator>::value_type>) 1185132720Skan __glibcxx_function_requires(_EqualOpConcept< 1186132720Skan typename iterator_traits<_InputIterator>::value_type, _Tp>) 1187132720Skan __glibcxx_requires_valid_range(__first, __last); 118897403Sobrien 118997403Sobrien for ( ; __first != __last; ++__first) 1190132720Skan if (!(*__first == __value)) 1191132720Skan { 1192132720Skan *__result = *__first; 1193132720Skan ++__result; 1194132720Skan } 119597403Sobrien return __result; 119697403Sobrien } 119797403Sobrien 119897403Sobrien /** 119997403Sobrien * @brief Copy a sequence, removing elements for which a predicate is true. 120097403Sobrien * @param first An input iterator. 120197403Sobrien * @param last An input iterator. 120297403Sobrien * @param result An output iterator. 120397403Sobrien * @param pred A predicate. 120497403Sobrien * @return An iterator designating the end of the resulting sequence. 120597403Sobrien * 120697403Sobrien * Copies each element in the range @p [first,last) for which 120797403Sobrien * @p pred returns true to the range beginning at @p result. 120897403Sobrien * 120997403Sobrien * remove_copy_if() is stable, so the relative order of elements that are 121097403Sobrien * copied is unchanged. 121197403Sobrien */ 1212132720Skan template<typename _InputIterator, typename _OutputIterator, 1213132720Skan typename _Predicate> 1214132720Skan _OutputIterator 1215132720Skan remove_copy_if(_InputIterator __first, _InputIterator __last, 1216132720Skan _OutputIterator __result, _Predicate __pred) 121797403Sobrien { 121897403Sobrien // concept requirements 1219132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1220132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1221132720Skan typename iterator_traits<_InputIterator>::value_type>) 1222132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 1223132720Skan typename iterator_traits<_InputIterator>::value_type>) 1224132720Skan __glibcxx_requires_valid_range(__first, __last); 122597403Sobrien 122697403Sobrien for ( ; __first != __last; ++__first) 1227132720Skan if (!__pred(*__first)) 1228132720Skan { 1229132720Skan *__result = *__first; 1230132720Skan ++__result; 1231132720Skan } 123297403Sobrien return __result; 123397403Sobrien } 123497403Sobrien 123597403Sobrien /** 123697403Sobrien * @brief Remove elements from a sequence. 123797403Sobrien * @param first An input iterator. 123897403Sobrien * @param last An input iterator. 123997403Sobrien * @param value The value to be removed. 124097403Sobrien * @return An iterator designating the end of the resulting sequence. 124197403Sobrien * 124297403Sobrien * All elements equal to @p value are removed from the range 124397403Sobrien * @p [first,last). 124497403Sobrien * 124597403Sobrien * remove() is stable, so the relative order of elements that are 124697403Sobrien * not removed is unchanged. 124797403Sobrien * 124897403Sobrien * Elements between the end of the resulting sequence and @p last 124997403Sobrien * are still present, but their value is unspecified. 125097403Sobrien */ 1251132720Skan template<typename _ForwardIterator, typename _Tp> 1252132720Skan _ForwardIterator 1253132720Skan remove(_ForwardIterator __first, _ForwardIterator __last, 125497403Sobrien const _Tp& __value) 125597403Sobrien { 125697403Sobrien // concept requirements 1257132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1258132720Skan _ForwardIterator>) 1259132720Skan __glibcxx_function_requires(_EqualOpConcept< 1260132720Skan typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 1261132720Skan __glibcxx_requires_valid_range(__first, __last); 126297403Sobrien 1263132720Skan __first = std::find(__first, __last, __value); 1264132720Skan _ForwardIterator __i = __first; 126597403Sobrien return __first == __last ? __first 1266132720Skan : std::remove_copy(++__i, __last, 1267132720Skan __first, __value); 126897403Sobrien } 126997403Sobrien 127097403Sobrien /** 127197403Sobrien * @brief Remove elements from a sequence using a predicate. 127297403Sobrien * @param first A forward iterator. 127397403Sobrien * @param last A forward iterator. 127497403Sobrien * @param pred A predicate. 127597403Sobrien * @return An iterator designating the end of the resulting sequence. 127697403Sobrien * 127797403Sobrien * All elements for which @p pred returns true are removed from the range 127897403Sobrien * @p [first,last). 127997403Sobrien * 128097403Sobrien * remove_if() is stable, so the relative order of elements that are 128197403Sobrien * not removed is unchanged. 128297403Sobrien * 128397403Sobrien * Elements between the end of the resulting sequence and @p last 128497403Sobrien * are still present, but their value is unspecified. 128597403Sobrien */ 1286132720Skan template<typename _ForwardIterator, typename _Predicate> 1287132720Skan _ForwardIterator 1288132720Skan remove_if(_ForwardIterator __first, _ForwardIterator __last, 128997403Sobrien _Predicate __pred) 129097403Sobrien { 129197403Sobrien // concept requirements 1292132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1293132720Skan _ForwardIterator>) 1294132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 1295132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1296132720Skan __glibcxx_requires_valid_range(__first, __last); 129797403Sobrien 1298132720Skan __first = std::find_if(__first, __last, __pred); 1299132720Skan _ForwardIterator __i = __first; 130097403Sobrien return __first == __last ? __first 1301132720Skan : std::remove_copy_if(++__i, __last, 1302132720Skan __first, __pred); 130397403Sobrien } 130497403Sobrien 130597403Sobrien /** 130697403Sobrien * @if maint 1307132720Skan * This is an uglified unique_copy(_InputIterator, _InputIterator, 1308132720Skan * _OutputIterator) 1309169691Skan * overloaded for forward iterators and output iterator as result. 131097403Sobrien * @endif 131197403Sobrien */ 1312169691Skan template<typename _ForwardIterator, typename _OutputIterator> 1313169691Skan _OutputIterator 1314169691Skan __unique_copy(_ForwardIterator __first, _ForwardIterator __last, 1315169691Skan _OutputIterator __result, 1316169691Skan forward_iterator_tag, output_iterator_tag) 1317169691Skan { 1318169691Skan // concept requirements -- taken care of in dispatching function 1319169691Skan _ForwardIterator __next = __first; 1320169691Skan *__result = *__first; 1321169691Skan while (++__next != __last) 1322169691Skan if (!(*__first == *__next)) 1323169691Skan { 1324169691Skan __first = __next; 1325169691Skan *++__result = *__first; 1326169691Skan } 1327169691Skan return ++__result; 1328169691Skan } 1329169691Skan 1330169691Skan /** 1331169691Skan * @if maint 1332169691Skan * This is an uglified unique_copy(_InputIterator, _InputIterator, 1333169691Skan * _OutputIterator) 1334169691Skan * overloaded for input iterators and output iterator as result. 1335169691Skan * @endif 1336169691Skan */ 1337132720Skan template<typename _InputIterator, typename _OutputIterator> 1338132720Skan _OutputIterator 1339132720Skan __unique_copy(_InputIterator __first, _InputIterator __last, 1340132720Skan _OutputIterator __result, 1341169691Skan input_iterator_tag, output_iterator_tag) 134297403Sobrien { 134397403Sobrien // concept requirements -- taken care of in dispatching function 1344132720Skan typename iterator_traits<_InputIterator>::value_type __value = *__first; 134597403Sobrien *__result = __value; 134697403Sobrien while (++__first != __last) 1347132720Skan if (!(__value == *__first)) 1348132720Skan { 1349132720Skan __value = *__first; 1350132720Skan *++__result = __value; 1351132720Skan } 135297403Sobrien return ++__result; 135397403Sobrien } 135497403Sobrien 135597403Sobrien /** 135697403Sobrien * @if maint 1357132720Skan * This is an uglified unique_copy(_InputIterator, _InputIterator, 1358132720Skan * _OutputIterator) 1359169691Skan * overloaded for input iterators and forward iterator as result. 136097403Sobrien * @endif 136197403Sobrien */ 1362132720Skan template<typename _InputIterator, typename _ForwardIterator> 1363132720Skan _ForwardIterator 1364132720Skan __unique_copy(_InputIterator __first, _InputIterator __last, 1365132720Skan _ForwardIterator __result, 1366169691Skan input_iterator_tag, forward_iterator_tag) 136797403Sobrien { 136897403Sobrien // concept requirements -- taken care of in dispatching function 136997403Sobrien *__result = *__first; 137097403Sobrien while (++__first != __last) 137197403Sobrien if (!(*__result == *__first)) 137297403Sobrien *++__result = *__first; 137397403Sobrien return ++__result; 137497403Sobrien } 137597403Sobrien 137697403Sobrien /** 137797403Sobrien * @if maint 137897403Sobrien * This is an uglified 1379132720Skan * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 1380132720Skan * _BinaryPredicate) 1381169691Skan * overloaded for forward iterators and output iterator as result. 138297403Sobrien * @endif 138397403Sobrien */ 1384169691Skan template<typename _ForwardIterator, typename _OutputIterator, 1385169691Skan typename _BinaryPredicate> 1386169691Skan _OutputIterator 1387169691Skan __unique_copy(_ForwardIterator __first, _ForwardIterator __last, 1388169691Skan _OutputIterator __result, _BinaryPredicate __binary_pred, 1389169691Skan forward_iterator_tag, output_iterator_tag) 1390169691Skan { 1391169691Skan // concept requirements -- iterators already checked 1392169691Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1393169691Skan typename iterator_traits<_ForwardIterator>::value_type, 1394169691Skan typename iterator_traits<_ForwardIterator>::value_type>) 1395169691Skan 1396169691Skan _ForwardIterator __next = __first; 1397169691Skan *__result = *__first; 1398169691Skan while (++__next != __last) 1399169691Skan if (!__binary_pred(*__first, *__next)) 1400169691Skan { 1401169691Skan __first = __next; 1402169691Skan *++__result = *__first; 1403169691Skan } 1404169691Skan return ++__result; 1405169691Skan } 1406169691Skan 1407169691Skan /** 1408169691Skan * @if maint 1409169691Skan * This is an uglified 1410169691Skan * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 1411169691Skan * _BinaryPredicate) 1412169691Skan * overloaded for input iterators and output iterator as result. 1413169691Skan * @endif 1414169691Skan */ 1415132720Skan template<typename _InputIterator, typename _OutputIterator, 1416132720Skan typename _BinaryPredicate> 1417132720Skan _OutputIterator 1418132720Skan __unique_copy(_InputIterator __first, _InputIterator __last, 1419169691Skan _OutputIterator __result, _BinaryPredicate __binary_pred, 1420169691Skan input_iterator_tag, output_iterator_tag) 142197403Sobrien { 142297403Sobrien // concept requirements -- iterators already checked 1423132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1424132720Skan typename iterator_traits<_InputIterator>::value_type, 1425132720Skan typename iterator_traits<_InputIterator>::value_type>) 142697403Sobrien 1427132720Skan typename iterator_traits<_InputIterator>::value_type __value = *__first; 142897403Sobrien *__result = __value; 142997403Sobrien while (++__first != __last) 1430132720Skan if (!__binary_pred(__value, *__first)) 1431132720Skan { 1432132720Skan __value = *__first; 1433132720Skan *++__result = __value; 1434132720Skan } 143597403Sobrien return ++__result; 143697403Sobrien } 143797403Sobrien 143897403Sobrien /** 143997403Sobrien * @if maint 144097403Sobrien * This is an uglified 1441132720Skan * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 1442132720Skan * _BinaryPredicate) 1443169691Skan * overloaded for input iterators and forward iterator as result. 144497403Sobrien * @endif 144597403Sobrien */ 1446132720Skan template<typename _InputIterator, typename _ForwardIterator, 1447132720Skan typename _BinaryPredicate> 1448132720Skan _ForwardIterator 1449132720Skan __unique_copy(_InputIterator __first, _InputIterator __last, 1450169691Skan _ForwardIterator __result, _BinaryPredicate __binary_pred, 1451169691Skan input_iterator_tag, forward_iterator_tag) 145297403Sobrien { 145397403Sobrien // concept requirements -- iterators already checked 1454132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1455169691Skan typename iterator_traits<_ForwardIterator>::value_type, 1456169691Skan typename iterator_traits<_InputIterator>::value_type>) 145797403Sobrien 145897403Sobrien *__result = *__first; 145997403Sobrien while (++__first != __last) 1460169691Skan if (!__binary_pred(*__result, *__first)) 1461169691Skan *++__result = *__first; 146297403Sobrien return ++__result; 146397403Sobrien } 146497403Sobrien 146597403Sobrien /** 1466132720Skan * @brief Copy a sequence, removing consecutive duplicate values. 1467132720Skan * @param first An input iterator. 1468132720Skan * @param last An input iterator. 1469132720Skan * @param result An output iterator. 1470132720Skan * @return An iterator designating the end of the resulting sequence. 1471132720Skan * 1472132720Skan * Copies each element in the range @p [first,last) to the range 1473132720Skan * beginning at @p result, except that only the first element is copied 1474132720Skan * from groups of consecutive elements that compare equal. 1475132720Skan * unique_copy() is stable, so the relative order of elements that are 1476132720Skan * copied is unchanged. 1477169691Skan * 1478169691Skan * @if maint 1479169691Skan * _GLIBCXX_RESOLVE_LIB_DEFECTS 1480169691Skan * DR 241. Does unique_copy() require CopyConstructible and Assignable? 1481169691Skan * 1482169691Skan * _GLIBCXX_RESOLVE_LIB_DEFECTS 1483169691Skan * DR 538. 241 again: Does unique_copy() require CopyConstructible and 1484169691Skan * Assignable? 1485169691Skan * @endif 1486132720Skan */ 1487132720Skan template<typename _InputIterator, typename _OutputIterator> 1488132720Skan inline _OutputIterator 1489132720Skan unique_copy(_InputIterator __first, _InputIterator __last, 1490132720Skan _OutputIterator __result) 1491132720Skan { 1492132720Skan // concept requirements 1493132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1494132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1495132720Skan typename iterator_traits<_InputIterator>::value_type>) 1496132720Skan __glibcxx_function_requires(_EqualityComparableConcept< 1497132720Skan typename iterator_traits<_InputIterator>::value_type>) 1498132720Skan __glibcxx_requires_valid_range(__first, __last); 1499132720Skan 1500169691Skan if (__first == __last) 1501169691Skan return __result; 1502169691Skan return std::__unique_copy(__first, __last, __result, 1503169691Skan std::__iterator_category(__first), 1504169691Skan std::__iterator_category(__result)); 1505132720Skan } 1506132720Skan 1507132720Skan /** 150897403Sobrien * @brief Copy a sequence, removing consecutive values using a predicate. 150997403Sobrien * @param first An input iterator. 151097403Sobrien * @param last An input iterator. 151197403Sobrien * @param result An output iterator. 151297403Sobrien * @param binary_pred A binary predicate. 151397403Sobrien * @return An iterator designating the end of the resulting sequence. 151497403Sobrien * 151597403Sobrien * Copies each element in the range @p [first,last) to the range 151697403Sobrien * beginning at @p result, except that only the first element is copied 151797403Sobrien * from groups of consecutive elements for which @p binary_pred returns 151897403Sobrien * true. 151997403Sobrien * unique_copy() is stable, so the relative order of elements that are 152097403Sobrien * copied is unchanged. 1521169691Skan * 1522169691Skan * @if maint 1523169691Skan * _GLIBCXX_RESOLVE_LIB_DEFECTS 1524169691Skan * DR 241. Does unique_copy() require CopyConstructible and Assignable? 1525169691Skan * @endif 152697403Sobrien */ 1527132720Skan template<typename _InputIterator, typename _OutputIterator, 1528132720Skan typename _BinaryPredicate> 1529132720Skan inline _OutputIterator 1530132720Skan unique_copy(_InputIterator __first, _InputIterator __last, 1531132720Skan _OutputIterator __result, 153297403Sobrien _BinaryPredicate __binary_pred) 153397403Sobrien { 153497403Sobrien // concept requirements -- predicates checked later 1535132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1536132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1537132720Skan typename iterator_traits<_InputIterator>::value_type>) 1538132720Skan __glibcxx_requires_valid_range(__first, __last); 153997403Sobrien 1540169691Skan if (__first == __last) 1541169691Skan return __result; 1542169691Skan return std::__unique_copy(__first, __last, __result, __binary_pred, 1543169691Skan std::__iterator_category(__first), 1544169691Skan std::__iterator_category(__result)); 154597403Sobrien } 154697403Sobrien 154797403Sobrien /** 154897403Sobrien * @brief Remove consecutive duplicate values from a sequence. 154997403Sobrien * @param first A forward iterator. 155097403Sobrien * @param last A forward iterator. 155197403Sobrien * @return An iterator designating the end of the resulting sequence. 155297403Sobrien * 155397403Sobrien * Removes all but the first element from each group of consecutive 155497403Sobrien * values that compare equal. 155597403Sobrien * unique() is stable, so the relative order of elements that are 155697403Sobrien * not removed is unchanged. 155797403Sobrien * Elements between the end of the resulting sequence and @p last 155897403Sobrien * are still present, but their value is unspecified. 155997403Sobrien */ 1560132720Skan template<typename _ForwardIterator> 1561132720Skan _ForwardIterator 1562132720Skan unique(_ForwardIterator __first, _ForwardIterator __last) 156397403Sobrien { 1564132720Skan // concept requirements 1565132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1566132720Skan _ForwardIterator>) 1567132720Skan __glibcxx_function_requires(_EqualityComparableConcept< 1568132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1569132720Skan __glibcxx_requires_valid_range(__first, __last); 157097403Sobrien 1571132720Skan // Skip the beginning, if already unique. 1572132720Skan __first = std::adjacent_find(__first, __last); 1573132720Skan if (__first == __last) 1574132720Skan return __last; 1575132720Skan 1576132720Skan // Do the real copy work. 1577132720Skan _ForwardIterator __dest = __first; 1578132720Skan ++__first; 1579132720Skan while (++__first != __last) 1580132720Skan if (!(*__dest == *__first)) 1581132720Skan *++__dest = *__first; 1582132720Skan return ++__dest; 158397403Sobrien } 158497403Sobrien 158597403Sobrien /** 158697403Sobrien * @brief Remove consecutive values from a sequence using a predicate. 158797403Sobrien * @param first A forward iterator. 158897403Sobrien * @param last A forward iterator. 158997403Sobrien * @param binary_pred A binary predicate. 159097403Sobrien * @return An iterator designating the end of the resulting sequence. 159197403Sobrien * 159297403Sobrien * Removes all but the first element from each group of consecutive 159397403Sobrien * values for which @p binary_pred returns true. 159497403Sobrien * unique() is stable, so the relative order of elements that are 159597403Sobrien * not removed is unchanged. 159697403Sobrien * Elements between the end of the resulting sequence and @p last 159797403Sobrien * are still present, but their value is unspecified. 159897403Sobrien */ 1599132720Skan template<typename _ForwardIterator, typename _BinaryPredicate> 1600132720Skan _ForwardIterator 1601132720Skan unique(_ForwardIterator __first, _ForwardIterator __last, 160297403Sobrien _BinaryPredicate __binary_pred) 160397403Sobrien { 160497403Sobrien // concept requirements 1605132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1606132720Skan _ForwardIterator>) 1607132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1608132720Skan typename iterator_traits<_ForwardIterator>::value_type, 1609132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1610132720Skan __glibcxx_requires_valid_range(__first, __last); 161197403Sobrien 1612132720Skan // Skip the beginning, if already unique. 1613132720Skan __first = std::adjacent_find(__first, __last, __binary_pred); 1614132720Skan if (__first == __last) 1615132720Skan return __last; 1616132720Skan 1617132720Skan // Do the real copy work. 1618132720Skan _ForwardIterator __dest = __first; 1619132720Skan ++__first; 1620132720Skan while (++__first != __last) 1621132720Skan if (!__binary_pred(*__dest, *__first)) 1622132720Skan *++__dest = *__first; 1623132720Skan return ++__dest; 162497403Sobrien } 162597403Sobrien 162697403Sobrien /** 162797403Sobrien * @if maint 1628132720Skan * This is an uglified reverse(_BidirectionalIterator, 1629132720Skan * _BidirectionalIterator) 163097403Sobrien * overloaded for bidirectional iterators. 163197403Sobrien * @endif 163297403Sobrien */ 1633132720Skan template<typename _BidirectionalIterator> 163497403Sobrien void 1635132720Skan __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, 1636169691Skan bidirectional_iterator_tag) 163797403Sobrien { 1638132720Skan while (true) 1639132720Skan if (__first == __last || __first == --__last) 1640132720Skan return; 1641132720Skan else 1642169691Skan { 1643169691Skan std::iter_swap(__first, __last); 1644169691Skan ++__first; 1645169691Skan } 164697403Sobrien } 164797403Sobrien 164897403Sobrien /** 164997403Sobrien * @if maint 1650132720Skan * This is an uglified reverse(_BidirectionalIterator, 1651132720Skan * _BidirectionalIterator) 1652169691Skan * overloaded for random access iterators. 165397403Sobrien * @endif 165497403Sobrien */ 1655132720Skan template<typename _RandomAccessIterator> 165697403Sobrien void 1657132720Skan __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, 1658169691Skan random_access_iterator_tag) 165997403Sobrien { 1660169691Skan if (__first == __last) 1661169691Skan return; 1662169691Skan --__last; 1663132720Skan while (__first < __last) 1664169691Skan { 1665169691Skan std::iter_swap(__first, __last); 1666169691Skan ++__first; 1667169691Skan --__last; 1668169691Skan } 166997403Sobrien } 167097403Sobrien 167197403Sobrien /** 167297403Sobrien * @brief Reverse a sequence. 167397403Sobrien * @param first A bidirectional iterator. 167497403Sobrien * @param last A bidirectional iterator. 167597403Sobrien * @return reverse() returns no value. 167697403Sobrien * 167797403Sobrien * Reverses the order of the elements in the range @p [first,last), 167897403Sobrien * so that the first element becomes the last etc. 167997403Sobrien * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse() 168097403Sobrien * swaps @p *(first+i) and @p *(last-(i+1)) 168197403Sobrien */ 1682132720Skan template<typename _BidirectionalIterator> 168397403Sobrien inline void 1684132720Skan reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) 168597403Sobrien { 1686132720Skan // concept requirements 1687132720Skan __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 1688169691Skan _BidirectionalIterator>) 1689132720Skan __glibcxx_requires_valid_range(__first, __last); 1690132720Skan std::__reverse(__first, __last, std::__iterator_category(__first)); 169197403Sobrien } 169297403Sobrien 169397403Sobrien /** 169497403Sobrien * @brief Copy a sequence, reversing its elements. 169597403Sobrien * @param first A bidirectional iterator. 169697403Sobrien * @param last A bidirectional iterator. 169797403Sobrien * @param result An output iterator. 169897403Sobrien * @return An iterator designating the end of the resulting sequence. 169997403Sobrien * 170097403Sobrien * Copies the elements in the range @p [first,last) to the range 170197403Sobrien * @p [result,result+(last-first)) such that the order of the 170297403Sobrien * elements is reversed. 170397403Sobrien * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy() 170497403Sobrien * performs the assignment @p *(result+(last-first)-i) = *(first+i). 170597403Sobrien * The ranges @p [first,last) and @p [result,result+(last-first)) 170697403Sobrien * must not overlap. 170797403Sobrien */ 1708132720Skan template<typename _BidirectionalIterator, typename _OutputIterator> 1709132720Skan _OutputIterator 1710132720Skan reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, 1711132720Skan _OutputIterator __result) 171297403Sobrien { 171397403Sobrien // concept requirements 1714132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 1715132720Skan _BidirectionalIterator>) 1716132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1717132720Skan typename iterator_traits<_BidirectionalIterator>::value_type>) 1718132720Skan __glibcxx_requires_valid_range(__first, __last); 171997403Sobrien 1720132720Skan while (__first != __last) 1721132720Skan { 1722132720Skan --__last; 1723132720Skan *__result = *__last; 1724132720Skan ++__result; 1725132720Skan } 172697403Sobrien return __result; 172797403Sobrien } 172897403Sobrien 172997403Sobrien 173097403Sobrien /** 173197403Sobrien * @if maint 173297403Sobrien * This is a helper function for the rotate algorithm specialized on RAIs. 173397403Sobrien * It returns the greatest common divisor of two integer values. 173497403Sobrien * @endif 173597403Sobrien */ 173697403Sobrien template<typename _EuclideanRingElement> 173797403Sobrien _EuclideanRingElement 173897403Sobrien __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) 173997403Sobrien { 1740132720Skan while (__n != 0) 1741132720Skan { 1742132720Skan _EuclideanRingElement __t = __m % __n; 1743132720Skan __m = __n; 1744132720Skan __n = __t; 1745132720Skan } 174697403Sobrien return __m; 174797403Sobrien } 174897403Sobrien 174997403Sobrien /** 175097403Sobrien * @if maint 175197403Sobrien * This is a helper function for the rotate algorithm. 175297403Sobrien * @endif 175397403Sobrien */ 1754132720Skan template<typename _ForwardIterator> 175597403Sobrien void 1756132720Skan __rotate(_ForwardIterator __first, 1757132720Skan _ForwardIterator __middle, 1758132720Skan _ForwardIterator __last, 1759169691Skan forward_iterator_tag) 176097403Sobrien { 1761169691Skan if (__first == __middle || __last == __middle) 176297403Sobrien return; 176397403Sobrien 1764132720Skan _ForwardIterator __first2 = __middle; 1765132720Skan do 1766132720Skan { 1767169691Skan swap(*__first, *__first2); 1768169691Skan ++__first; 1769169691Skan ++__first2; 1770132720Skan if (__first == __middle) 1771132720Skan __middle = __first2; 1772132720Skan } 1773132720Skan while (__first2 != __last); 177497403Sobrien 177597403Sobrien __first2 = __middle; 177697403Sobrien 1777132720Skan while (__first2 != __last) 1778132720Skan { 1779169691Skan swap(*__first, *__first2); 1780169691Skan ++__first; 1781169691Skan ++__first2; 1782132720Skan if (__first == __middle) 1783132720Skan __middle = __first2; 1784132720Skan else if (__first2 == __last) 1785132720Skan __first2 = __middle; 1786132720Skan } 178797403Sobrien } 178897403Sobrien 178997403Sobrien /** 179097403Sobrien * @if maint 179197403Sobrien * This is a helper function for the rotate algorithm. 179297403Sobrien * @endif 179397403Sobrien */ 1794132720Skan template<typename _BidirectionalIterator> 179597403Sobrien void 1796132720Skan __rotate(_BidirectionalIterator __first, 1797132720Skan _BidirectionalIterator __middle, 1798132720Skan _BidirectionalIterator __last, 179997403Sobrien bidirectional_iterator_tag) 180097403Sobrien { 180197403Sobrien // concept requirements 1802132720Skan __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 1803169691Skan _BidirectionalIterator>) 180497403Sobrien 1805169691Skan if (__first == __middle || __last == __middle) 180697403Sobrien return; 180797403Sobrien 1808132720Skan std::__reverse(__first, __middle, bidirectional_iterator_tag()); 1809132720Skan std::__reverse(__middle, __last, bidirectional_iterator_tag()); 181097403Sobrien 181197403Sobrien while (__first != __middle && __middle != __last) 1812169691Skan { 1813169691Skan swap(*__first, *--__last); 1814169691Skan ++__first; 1815169691Skan } 181697403Sobrien 1817132720Skan if (__first == __middle) 1818132720Skan std::__reverse(__middle, __last, bidirectional_iterator_tag()); 1819132720Skan else 1820132720Skan std::__reverse(__first, __middle, bidirectional_iterator_tag()); 182197403Sobrien } 182297403Sobrien 182397403Sobrien /** 182497403Sobrien * @if maint 182597403Sobrien * This is a helper function for the rotate algorithm. 182697403Sobrien * @endif 182797403Sobrien */ 1828132720Skan template<typename _RandomAccessIterator> 182997403Sobrien void 1830132720Skan __rotate(_RandomAccessIterator __first, 1831132720Skan _RandomAccessIterator __middle, 1832132720Skan _RandomAccessIterator __last, 183397403Sobrien random_access_iterator_tag) 183497403Sobrien { 183597403Sobrien // concept requirements 1836132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 1837169691Skan _RandomAccessIterator>) 183897403Sobrien 1839169691Skan if (__first == __middle || __last == __middle) 184097403Sobrien return; 184197403Sobrien 1842132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 1843132720Skan _Distance; 1844132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 1845132720Skan _ValueType; 184697403Sobrien 1847132720Skan const _Distance __n = __last - __first; 1848132720Skan const _Distance __k = __middle - __first; 1849132720Skan const _Distance __l = __n - __k; 185097403Sobrien 1851132720Skan if (__k == __l) 1852132720Skan { 1853132720Skan std::swap_ranges(__first, __middle, __middle); 1854132720Skan return; 1855132720Skan } 185697403Sobrien 1857132720Skan const _Distance __d = __gcd(__n, __k); 185897403Sobrien 1859132720Skan for (_Distance __i = 0; __i < __d; __i++) 1860132720Skan { 1861169691Skan _ValueType __tmp = *__first; 1862132720Skan _RandomAccessIterator __p = __first; 186397403Sobrien 1864132720Skan if (__k < __l) 1865132720Skan { 1866132720Skan for (_Distance __j = 0; __j < __l / __d; __j++) 1867132720Skan { 1868132720Skan if (__p > __first + __l) 1869132720Skan { 1870132720Skan *__p = *(__p - __l); 1871132720Skan __p -= __l; 1872132720Skan } 187397403Sobrien 1874132720Skan *__p = *(__p + __k); 1875132720Skan __p += __k; 1876132720Skan } 187797403Sobrien } 1878132720Skan else 1879132720Skan { 1880132720Skan for (_Distance __j = 0; __j < __k / __d - 1; __j ++) 1881132720Skan { 1882132720Skan if (__p < __last - __k) 1883132720Skan { 1884132720Skan *__p = *(__p + __k); 1885132720Skan __p += __k; 1886132720Skan } 1887132720Skan *__p = * (__p - __l); 1888132720Skan __p -= __l; 1889132720Skan } 1890132720Skan } 189197403Sobrien 1892132720Skan *__p = __tmp; 1893132720Skan ++__first; 189497403Sobrien } 189597403Sobrien } 189697403Sobrien 189797403Sobrien /** 189897403Sobrien * @brief Rotate the elements of a sequence. 189997403Sobrien * @param first A forward iterator. 190097403Sobrien * @param middle A forward iterator. 190197403Sobrien * @param last A forward iterator. 190297403Sobrien * @return Nothing. 190397403Sobrien * 190497403Sobrien * Rotates the elements of the range @p [first,last) by @p (middle-first) 190597403Sobrien * positions so that the element at @p middle is moved to @p first, the 190697403Sobrien * element at @p middle+1 is moved to @first+1 and so on for each element 190797403Sobrien * in the range @p [first,last). 190897403Sobrien * 190997403Sobrien * This effectively swaps the ranges @p [first,middle) and 191097403Sobrien * @p [middle,last). 191197403Sobrien * 191297403Sobrien * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for 191397403Sobrien * each @p n in the range @p [0,last-first). 191497403Sobrien */ 1915132720Skan template<typename _ForwardIterator> 191697403Sobrien inline void 1917132720Skan rotate(_ForwardIterator __first, _ForwardIterator __middle, 1918132720Skan _ForwardIterator __last) 191997403Sobrien { 192097403Sobrien // concept requirements 1921132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1922132720Skan _ForwardIterator>) 1923132720Skan __glibcxx_requires_valid_range(__first, __middle); 1924132720Skan __glibcxx_requires_valid_range(__middle, __last); 192597403Sobrien 1926132720Skan typedef typename iterator_traits<_ForwardIterator>::iterator_category 1927132720Skan _IterType; 1928132720Skan std::__rotate(__first, __middle, __last, _IterType()); 192997403Sobrien } 193097403Sobrien 193197403Sobrien /** 193297403Sobrien * @brief Copy a sequence, rotating its elements. 193397403Sobrien * @param first A forward iterator. 193497403Sobrien * @param middle A forward iterator. 193597403Sobrien * @param last A forward iterator. 193697403Sobrien * @param result An output iterator. 193797403Sobrien * @return An iterator designating the end of the resulting sequence. 193897403Sobrien * 193997403Sobrien * Copies the elements of the range @p [first,last) to the range 194097403Sobrien * beginning at @result, rotating the copied elements by @p (middle-first) 194197403Sobrien * positions so that the element at @p middle is moved to @p result, the 194297403Sobrien * element at @p middle+1 is moved to @result+1 and so on for each element 194397403Sobrien * in the range @p [first,last). 194497403Sobrien * 194597403Sobrien * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for 194697403Sobrien * each @p n in the range @p [0,last-first). 194797403Sobrien */ 1948132720Skan template<typename _ForwardIterator, typename _OutputIterator> 1949132720Skan _OutputIterator 1950132720Skan rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, 1951132720Skan _ForwardIterator __last, _OutputIterator __result) 195297403Sobrien { 195397403Sobrien // concept requirements 1954132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 1955132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1956132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1957132720Skan __glibcxx_requires_valid_range(__first, __middle); 1958132720Skan __glibcxx_requires_valid_range(__middle, __last); 195997403Sobrien 1960169691Skan return std::copy(__first, __middle, 1961169691Skan std::copy(__middle, __last, __result)); 196297403Sobrien } 196397403Sobrien 196497403Sobrien /** 196597403Sobrien * @brief Randomly shuffle the elements of a sequence. 196697403Sobrien * @param first A forward iterator. 196797403Sobrien * @param last A forward iterator. 196897403Sobrien * @return Nothing. 196997403Sobrien * 197097403Sobrien * Reorder the elements in the range @p [first,last) using a random 197197403Sobrien * distribution, so that every possible ordering of the sequence is 197297403Sobrien * equally likely. 197397403Sobrien */ 1974132720Skan template<typename _RandomAccessIterator> 197597403Sobrien inline void 1976132720Skan random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 197797403Sobrien { 197897403Sobrien // concept requirements 1979132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 1980132720Skan _RandomAccessIterator>) 1981132720Skan __glibcxx_requires_valid_range(__first, __last); 198297403Sobrien 1983132720Skan if (__first != __last) 1984132720Skan for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 1985132720Skan std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1))); 198697403Sobrien } 198797403Sobrien 198897403Sobrien /** 198997403Sobrien * @brief Shuffle the elements of a sequence using a random number 199097403Sobrien * generator. 199197403Sobrien * @param first A forward iterator. 199297403Sobrien * @param last A forward iterator. 199397403Sobrien * @param rand The RNG functor or function. 199497403Sobrien * @return Nothing. 199597403Sobrien * 199697403Sobrien * Reorders the elements in the range @p [first,last) using @p rand to 199797403Sobrien * provide a random distribution. Calling @p rand(N) for a positive 199897403Sobrien * integer @p N should return a randomly chosen integer from the 199997403Sobrien * range [0,N). 200097403Sobrien */ 2001132720Skan template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 200297403Sobrien void 2003132720Skan random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 200497403Sobrien _RandomNumberGenerator& __rand) 200597403Sobrien { 200697403Sobrien // concept requirements 2007132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 2008132720Skan _RandomAccessIterator>) 2009132720Skan __glibcxx_requires_valid_range(__first, __last); 201097403Sobrien 2011132720Skan if (__first == __last) 2012132720Skan return; 2013132720Skan for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 2014132720Skan std::iter_swap(__i, __first + __rand((__i - __first) + 1)); 201597403Sobrien } 201697403Sobrien 201797403Sobrien 201897403Sobrien /** 201997403Sobrien * @if maint 202097403Sobrien * This is a helper function... 202197403Sobrien * @endif 202297403Sobrien */ 2023132720Skan template<typename _ForwardIterator, typename _Predicate> 2024132720Skan _ForwardIterator 2025132720Skan __partition(_ForwardIterator __first, _ForwardIterator __last, 2026132720Skan _Predicate __pred, 202797403Sobrien forward_iterator_tag) 202897403Sobrien { 2029132720Skan if (__first == __last) 2030132720Skan return __first; 203197403Sobrien 203297403Sobrien while (__pred(*__first)) 2033132720Skan if (++__first == __last) 2034132720Skan return __first; 203597403Sobrien 2036132720Skan _ForwardIterator __next = __first; 203797403Sobrien 203897403Sobrien while (++__next != __last) 2039132720Skan if (__pred(*__next)) 2040132720Skan { 2041132720Skan swap(*__first, *__next); 2042132720Skan ++__first; 2043132720Skan } 204497403Sobrien 204597403Sobrien return __first; 204697403Sobrien } 204797403Sobrien 204897403Sobrien /** 204997403Sobrien * @if maint 205097403Sobrien * This is a helper function... 205197403Sobrien * @endif 205297403Sobrien */ 2053132720Skan template<typename _BidirectionalIterator, typename _Predicate> 2054132720Skan _BidirectionalIterator 2055132720Skan __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, 205697403Sobrien _Predicate __pred, 205797403Sobrien bidirectional_iterator_tag) 205897403Sobrien { 2059132720Skan while (true) 2060132720Skan { 2061132720Skan while (true) 2062132720Skan if (__first == __last) 2063132720Skan return __first; 2064132720Skan else if (__pred(*__first)) 2065132720Skan ++__first; 2066132720Skan else 2067132720Skan break; 2068132720Skan --__last; 2069132720Skan while (true) 2070132720Skan if (__first == __last) 2071132720Skan return __first; 2072132720Skan else if (!__pred(*__last)) 2073132720Skan --__last; 2074132720Skan else 2075132720Skan break; 2076132720Skan std::iter_swap(__first, __last); 2077132720Skan ++__first; 2078132720Skan } 207997403Sobrien } 208097403Sobrien 208197403Sobrien /** 208297403Sobrien * @brief Move elements for which a predicate is true to the beginning 208397403Sobrien * of a sequence. 208497403Sobrien * @param first A forward iterator. 208597403Sobrien * @param last A forward iterator. 208697403Sobrien * @param pred A predicate functor. 208797403Sobrien * @return An iterator @p middle such that @p pred(i) is true for each 208897403Sobrien * iterator @p i in the range @p [first,middle) and false for each @p i 208997403Sobrien * in the range @p [middle,last). 2090132720Skan * 209197403Sobrien * @p pred must not modify its operand. @p partition() does not preserve 209297403Sobrien * the relative ordering of elements in each group, use 209397403Sobrien * @p stable_partition() if this is needed. 209497403Sobrien */ 2095132720Skan template<typename _ForwardIterator, typename _Predicate> 2096132720Skan inline _ForwardIterator 2097132720Skan partition(_ForwardIterator __first, _ForwardIterator __last, 209897403Sobrien _Predicate __pred) 209997403Sobrien { 210097403Sobrien // concept requirements 2101132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 2102132720Skan _ForwardIterator>) 2103132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 2104132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 2105132720Skan __glibcxx_requires_valid_range(__first, __last); 210697403Sobrien 2107132720Skan return std::__partition(__first, __last, __pred, 2108132720Skan std::__iterator_category(__first)); 210997403Sobrien } 211097403Sobrien 211197403Sobrien 211297403Sobrien /** 211397403Sobrien * @if maint 211497403Sobrien * This is a helper function... 211597403Sobrien * @endif 211697403Sobrien */ 2117132720Skan template<typename _ForwardIterator, typename _Predicate, typename _Distance> 2118132720Skan _ForwardIterator 2119132720Skan __inplace_stable_partition(_ForwardIterator __first, 2120132720Skan _ForwardIterator __last, 212197403Sobrien _Predicate __pred, _Distance __len) 212297403Sobrien { 212397403Sobrien if (__len == 1) 212497403Sobrien return __pred(*__first) ? __last : __first; 2125132720Skan _ForwardIterator __middle = __first; 2126132720Skan std::advance(__middle, __len / 2); 2127132720Skan _ForwardIterator __begin = std::__inplace_stable_partition(__first, 2128132720Skan __middle, 2129132720Skan __pred, 2130132720Skan __len / 2); 2131132720Skan _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last, 2132132720Skan __pred, 2133132720Skan __len 2134132720Skan - __len / 2); 2135132720Skan std::rotate(__begin, __middle, __end); 2136132720Skan std::advance(__begin, std::distance(__middle, __end)); 213797403Sobrien return __begin; 213897403Sobrien } 213997403Sobrien 214097403Sobrien /** 214197403Sobrien * @if maint 214297403Sobrien * This is a helper function... 214397403Sobrien * @endif 214497403Sobrien */ 2145132720Skan template<typename _ForwardIterator, typename _Pointer, typename _Predicate, 214697403Sobrien typename _Distance> 2147132720Skan _ForwardIterator 2148132720Skan __stable_partition_adaptive(_ForwardIterator __first, 2149132720Skan _ForwardIterator __last, 215097403Sobrien _Predicate __pred, _Distance __len, 215197403Sobrien _Pointer __buffer, 215297403Sobrien _Distance __buffer_size) 215397403Sobrien { 2154132720Skan if (__len <= __buffer_size) 2155132720Skan { 2156132720Skan _ForwardIterator __result1 = __first; 2157132720Skan _Pointer __result2 = __buffer; 2158132720Skan for ( ; __first != __last ; ++__first) 2159132720Skan if (__pred(*__first)) 2160132720Skan { 2161132720Skan *__result1 = *__first; 2162132720Skan ++__result1; 2163132720Skan } 2164132720Skan else 2165132720Skan { 2166132720Skan *__result2 = *__first; 2167132720Skan ++__result2; 2168132720Skan } 2169132720Skan std::copy(__buffer, __result2, __result1); 2170132720Skan return __result1; 2171132720Skan } 2172132720Skan else 2173132720Skan { 2174132720Skan _ForwardIterator __middle = __first; 2175132720Skan std::advance(__middle, __len / 2); 2176132720Skan _ForwardIterator __begin = 2177132720Skan std::__stable_partition_adaptive(__first, __middle, __pred, 2178132720Skan __len / 2, __buffer, 2179132720Skan __buffer_size); 2180132720Skan _ForwardIterator __end = 2181132720Skan std::__stable_partition_adaptive(__middle, __last, __pred, 2182132720Skan __len - __len / 2, 2183132720Skan __buffer, __buffer_size); 2184132720Skan std::rotate(__begin, __middle, __end); 2185132720Skan std::advance(__begin, std::distance(__middle, __end)); 2186132720Skan return __begin; 2187132720Skan } 218897403Sobrien } 218997403Sobrien 219097403Sobrien /** 219197403Sobrien * @brief Move elements for which a predicate is true to the beginning 219297403Sobrien * of a sequence, preserving relative ordering. 219397403Sobrien * @param first A forward iterator. 219497403Sobrien * @param last A forward iterator. 219597403Sobrien * @param pred A predicate functor. 219697403Sobrien * @return An iterator @p middle such that @p pred(i) is true for each 219797403Sobrien * iterator @p i in the range @p [first,middle) and false for each @p i 219897403Sobrien * in the range @p [middle,last). 2199132720Skan * 220097403Sobrien * Performs the same function as @p partition() with the additional 220197403Sobrien * guarantee that the relative ordering of elements in each group is 220297403Sobrien * preserved, so any two elements @p x and @p y in the range 220397403Sobrien * @p [first,last) such that @p pred(x)==pred(y) will have the same 220497403Sobrien * relative ordering after calling @p stable_partition(). 220597403Sobrien */ 2206132720Skan template<typename _ForwardIterator, typename _Predicate> 2207132720Skan _ForwardIterator 2208132720Skan stable_partition(_ForwardIterator __first, _ForwardIterator __last, 220997403Sobrien _Predicate __pred) 221097403Sobrien { 221197403Sobrien // concept requirements 2212132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 2213132720Skan _ForwardIterator>) 2214132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 2215132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 2216132720Skan __glibcxx_requires_valid_range(__first, __last); 221797403Sobrien 221897403Sobrien if (__first == __last) 221997403Sobrien return __first; 222097403Sobrien else 2221132720Skan { 2222132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 2223132720Skan _ValueType; 2224132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 2225132720Skan _DistanceType; 222697403Sobrien 2227132720Skan _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, 2228132720Skan __last); 222997403Sobrien if (__buf.size() > 0) 2230132720Skan return 2231132720Skan std::__stable_partition_adaptive(__first, __last, __pred, 2232132720Skan _DistanceType(__buf.requested_size()), 2233132720Skan __buf.begin(), __buf.size()); 223497403Sobrien else 2235132720Skan return 2236132720Skan std::__inplace_stable_partition(__first, __last, __pred, 2237132720Skan _DistanceType(__buf.requested_size())); 2238132720Skan } 223997403Sobrien } 224097403Sobrien 224197403Sobrien /** 224297403Sobrien * @if maint 224397403Sobrien * This is a helper function... 224497403Sobrien * @endif 224597403Sobrien */ 2246132720Skan template<typename _RandomAccessIterator, typename _Tp> 2247132720Skan _RandomAccessIterator 2248132720Skan __unguarded_partition(_RandomAccessIterator __first, 2249132720Skan _RandomAccessIterator __last, _Tp __pivot) 225097403Sobrien { 2251132720Skan while (true) 2252132720Skan { 2253132720Skan while (*__first < __pivot) 2254132720Skan ++__first; 2255132720Skan --__last; 2256132720Skan while (__pivot < *__last) 2257132720Skan --__last; 2258132720Skan if (!(__first < __last)) 2259132720Skan return __first; 2260132720Skan std::iter_swap(__first, __last); 226197403Sobrien ++__first; 2262132720Skan } 226397403Sobrien } 226497403Sobrien 226597403Sobrien /** 226697403Sobrien * @if maint 226797403Sobrien * This is a helper function... 226897403Sobrien * @endif 226997403Sobrien */ 2270132720Skan template<typename _RandomAccessIterator, typename _Tp, typename _Compare> 2271132720Skan _RandomAccessIterator 2272132720Skan __unguarded_partition(_RandomAccessIterator __first, 2273132720Skan _RandomAccessIterator __last, 227497403Sobrien _Tp __pivot, _Compare __comp) 227597403Sobrien { 2276132720Skan while (true) 2277132720Skan { 2278132720Skan while (__comp(*__first, __pivot)) 2279132720Skan ++__first; 2280132720Skan --__last; 2281132720Skan while (__comp(__pivot, *__last)) 2282132720Skan --__last; 2283132720Skan if (!(__first < __last)) 2284132720Skan return __first; 2285132720Skan std::iter_swap(__first, __last); 228697403Sobrien ++__first; 2287132720Skan } 228897403Sobrien } 228997403Sobrien 229097403Sobrien /** 229197403Sobrien * @if maint 229297403Sobrien * @doctodo 229397403Sobrien * This controls some aspect of the sort routines. 229497403Sobrien * @endif 229597403Sobrien */ 2296132720Skan enum { _S_threshold = 16 }; 229797403Sobrien 229897403Sobrien /** 229997403Sobrien * @if maint 230097403Sobrien * This is a helper function for the sort routine. 230197403Sobrien * @endif 230297403Sobrien */ 2303132720Skan template<typename _RandomAccessIterator, typename _Tp> 230497403Sobrien void 2305132720Skan __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val) 230697403Sobrien { 2307132720Skan _RandomAccessIterator __next = __last; 230897403Sobrien --__next; 2309132720Skan while (__val < *__next) 2310132720Skan { 2311132720Skan *__last = *__next; 2312132720Skan __last = __next; 2313132720Skan --__next; 2314132720Skan } 231597403Sobrien *__last = __val; 231697403Sobrien } 231797403Sobrien 231897403Sobrien /** 231997403Sobrien * @if maint 232097403Sobrien * This is a helper function for the sort routine. 232197403Sobrien * @endif 232297403Sobrien */ 2323132720Skan template<typename _RandomAccessIterator, typename _Tp, typename _Compare> 232497403Sobrien void 2325132720Skan __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val, 2326132720Skan _Compare __comp) 232797403Sobrien { 2328132720Skan _RandomAccessIterator __next = __last; 232997403Sobrien --__next; 2330132720Skan while (__comp(__val, *__next)) 2331132720Skan { 2332132720Skan *__last = *__next; 2333132720Skan __last = __next; 2334132720Skan --__next; 2335132720Skan } 233697403Sobrien *__last = __val; 233797403Sobrien } 233897403Sobrien 233997403Sobrien /** 234097403Sobrien * @if maint 234197403Sobrien * This is a helper function for the sort routine. 234297403Sobrien * @endif 234397403Sobrien */ 2344132720Skan template<typename _RandomAccessIterator> 234597403Sobrien void 2346132720Skan __insertion_sort(_RandomAccessIterator __first, 2347132720Skan _RandomAccessIterator __last) 234897403Sobrien { 2349132720Skan if (__first == __last) 2350132720Skan return; 235197403Sobrien 2352132720Skan for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 2353132720Skan { 2354132720Skan typename iterator_traits<_RandomAccessIterator>::value_type 2355132720Skan __val = *__i; 2356132720Skan if (__val < *__first) 2357132720Skan { 2358132720Skan std::copy_backward(__first, __i, __i + 1); 2359132720Skan *__first = __val; 2360132720Skan } 2361132720Skan else 2362132720Skan std::__unguarded_linear_insert(__i, __val); 236397403Sobrien } 236497403Sobrien } 236597403Sobrien 236697403Sobrien /** 236797403Sobrien * @if maint 236897403Sobrien * This is a helper function for the sort routine. 236997403Sobrien * @endif 237097403Sobrien */ 2371132720Skan template<typename _RandomAccessIterator, typename _Compare> 237297403Sobrien void 2373132720Skan __insertion_sort(_RandomAccessIterator __first, 2374132720Skan _RandomAccessIterator __last, _Compare __comp) 237597403Sobrien { 237697403Sobrien if (__first == __last) return; 237797403Sobrien 2378132720Skan for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 2379132720Skan { 2380132720Skan typename iterator_traits<_RandomAccessIterator>::value_type 2381132720Skan __val = *__i; 2382132720Skan if (__comp(__val, *__first)) 2383132720Skan { 2384132720Skan std::copy_backward(__first, __i, __i + 1); 2385132720Skan *__first = __val; 2386132720Skan } 2387132720Skan else 2388132720Skan std::__unguarded_linear_insert(__i, __val, __comp); 238997403Sobrien } 239097403Sobrien } 239197403Sobrien 239297403Sobrien /** 239397403Sobrien * @if maint 239497403Sobrien * This is a helper function for the sort routine. 239597403Sobrien * @endif 239697403Sobrien */ 2397132720Skan template<typename _RandomAccessIterator> 239897403Sobrien inline void 2399132720Skan __unguarded_insertion_sort(_RandomAccessIterator __first, 2400132720Skan _RandomAccessIterator __last) 240197403Sobrien { 2402132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2403132720Skan _ValueType; 240497403Sobrien 2405132720Skan for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 2406132720Skan std::__unguarded_linear_insert(__i, _ValueType(*__i)); 240797403Sobrien } 240897403Sobrien 240997403Sobrien /** 241097403Sobrien * @if maint 241197403Sobrien * This is a helper function for the sort routine. 241297403Sobrien * @endif 241397403Sobrien */ 2414132720Skan template<typename _RandomAccessIterator, typename _Compare> 241597403Sobrien inline void 2416132720Skan __unguarded_insertion_sort(_RandomAccessIterator __first, 2417132720Skan _RandomAccessIterator __last, _Compare __comp) 241897403Sobrien { 2419132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2420132720Skan _ValueType; 242197403Sobrien 2422132720Skan for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 2423132720Skan std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp); 242497403Sobrien } 242597403Sobrien 242697403Sobrien /** 242797403Sobrien * @if maint 242897403Sobrien * This is a helper function for the sort routine. 242997403Sobrien * @endif 243097403Sobrien */ 2431132720Skan template<typename _RandomAccessIterator> 243297403Sobrien void 2433132720Skan __final_insertion_sort(_RandomAccessIterator __first, 2434132720Skan _RandomAccessIterator __last) 243597403Sobrien { 2436169691Skan if (__last - __first > int(_S_threshold)) 2437132720Skan { 2438169691Skan std::__insertion_sort(__first, __first + int(_S_threshold)); 2439169691Skan std::__unguarded_insertion_sort(__first + int(_S_threshold), __last); 2440132720Skan } 244197403Sobrien else 2442132720Skan std::__insertion_sort(__first, __last); 244397403Sobrien } 244497403Sobrien 244597403Sobrien /** 244697403Sobrien * @if maint 244797403Sobrien * This is a helper function for the sort routine. 244897403Sobrien * @endif 244997403Sobrien */ 2450132720Skan template<typename _RandomAccessIterator, typename _Compare> 245197403Sobrien void 2452132720Skan __final_insertion_sort(_RandomAccessIterator __first, 2453132720Skan _RandomAccessIterator __last, _Compare __comp) 245497403Sobrien { 2455169691Skan if (__last - __first > int(_S_threshold)) 2456132720Skan { 2457169691Skan std::__insertion_sort(__first, __first + int(_S_threshold), __comp); 2458169691Skan std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, 2459132720Skan __comp); 2460132720Skan } 246197403Sobrien else 2462132720Skan std::__insertion_sort(__first, __last, __comp); 246397403Sobrien } 246497403Sobrien 246597403Sobrien /** 246697403Sobrien * @if maint 2467169691Skan * This is a helper function for the sort routines. 246897403Sobrien * @endif 246997403Sobrien */ 2470169691Skan template<typename _RandomAccessIterator> 2471169691Skan void 2472169691Skan __heap_select(_RandomAccessIterator __first, 2473169691Skan _RandomAccessIterator __middle, 2474169691Skan _RandomAccessIterator __last) 2475169691Skan { 2476169691Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2477169691Skan _ValueType; 2478169691Skan 2479169691Skan std::make_heap(__first, __middle); 2480169691Skan for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 2481169691Skan if (*__i < *__first) 2482169691Skan std::__pop_heap(__first, __middle, __i, _ValueType(*__i)); 2483169691Skan } 2484169691Skan 2485169691Skan /** 2486169691Skan * @if maint 2487169691Skan * This is a helper function for the sort routines. 2488169691Skan * @endif 2489169691Skan */ 2490169691Skan template<typename _RandomAccessIterator, typename _Compare> 2491169691Skan void 2492169691Skan __heap_select(_RandomAccessIterator __first, 2493169691Skan _RandomAccessIterator __middle, 2494169691Skan _RandomAccessIterator __last, _Compare __comp) 2495169691Skan { 2496169691Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2497169691Skan _ValueType; 2498169691Skan 2499169691Skan std::make_heap(__first, __middle, __comp); 2500169691Skan for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 2501169691Skan if (__comp(*__i, *__first)) 2502169691Skan std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp); 2503169691Skan } 2504169691Skan 2505169691Skan /** 2506169691Skan * @if maint 2507169691Skan * This is a helper function for the sort routines. 2508169691Skan * @endif 2509169691Skan */ 251097403Sobrien template<typename _Size> 251197403Sobrien inline _Size 251297403Sobrien __lg(_Size __n) 251397403Sobrien { 251497403Sobrien _Size __k; 2515132720Skan for (__k = 0; __n != 1; __n >>= 1) 2516132720Skan ++__k; 251797403Sobrien return __k; 251897403Sobrien } 251997403Sobrien 252097403Sobrien /** 252197403Sobrien * @brief Sort the smallest elements of a sequence. 252297403Sobrien * @param first An iterator. 252397403Sobrien * @param middle Another iterator. 252497403Sobrien * @param last Another iterator. 252597403Sobrien * @return Nothing. 252697403Sobrien * 252797403Sobrien * Sorts the smallest @p (middle-first) elements in the range 252897403Sobrien * @p [first,last) and moves them to the range @p [first,middle). The 252997403Sobrien * order of the remaining elements in the range @p [middle,last) is 253097403Sobrien * undefined. 253197403Sobrien * After the sort if @p i and @j are iterators in the range 253297403Sobrien * @p [first,middle) such that @i precedes @j and @k is an iterator in 253397403Sobrien * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false. 253497403Sobrien */ 2535132720Skan template<typename _RandomAccessIterator> 2536169691Skan inline void 2537132720Skan partial_sort(_RandomAccessIterator __first, 2538132720Skan _RandomAccessIterator __middle, 2539132720Skan _RandomAccessIterator __last) 254097403Sobrien { 2541132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2542132720Skan _ValueType; 254397403Sobrien 254497403Sobrien // concept requirements 2545132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 2546132720Skan _RandomAccessIterator>) 2547132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 2548132720Skan __glibcxx_requires_valid_range(__first, __middle); 2549132720Skan __glibcxx_requires_valid_range(__middle, __last); 255097403Sobrien 2551169691Skan std::__heap_select(__first, __middle, __last); 2552132720Skan std::sort_heap(__first, __middle); 255397403Sobrien } 255497403Sobrien 255597403Sobrien /** 255697403Sobrien * @brief Sort the smallest elements of a sequence using a predicate 255797403Sobrien * for comparison. 255897403Sobrien * @param first An iterator. 255997403Sobrien * @param middle Another iterator. 256097403Sobrien * @param last Another iterator. 256197403Sobrien * @param comp A comparison functor. 256297403Sobrien * @return Nothing. 256397403Sobrien * 256497403Sobrien * Sorts the smallest @p (middle-first) elements in the range 256597403Sobrien * @p [first,last) and moves them to the range @p [first,middle). The 256697403Sobrien * order of the remaining elements in the range @p [middle,last) is 256797403Sobrien * undefined. 256897403Sobrien * After the sort if @p i and @j are iterators in the range 256997403Sobrien * @p [first,middle) such that @i precedes @j and @k is an iterator in 257097403Sobrien * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i) 257197403Sobrien * are both false. 257297403Sobrien */ 2573132720Skan template<typename _RandomAccessIterator, typename _Compare> 2574169691Skan inline void 2575132720Skan partial_sort(_RandomAccessIterator __first, 2576132720Skan _RandomAccessIterator __middle, 2577132720Skan _RandomAccessIterator __last, 257897403Sobrien _Compare __comp) 257997403Sobrien { 2580132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2581132720Skan _ValueType; 258297403Sobrien 258397403Sobrien // concept requirements 2584132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 2585132720Skan _RandomAccessIterator>) 2586132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2587132720Skan _ValueType, _ValueType>) 2588132720Skan __glibcxx_requires_valid_range(__first, __middle); 2589132720Skan __glibcxx_requires_valid_range(__middle, __last); 259097403Sobrien 2591169691Skan std::__heap_select(__first, __middle, __last, __comp); 2592132720Skan std::sort_heap(__first, __middle, __comp); 259397403Sobrien } 259497403Sobrien 259597403Sobrien /** 259697403Sobrien * @brief Copy the smallest elements of a sequence. 259797403Sobrien * @param first An iterator. 259897403Sobrien * @param last Another iterator. 259997403Sobrien * @param result_first A random-access iterator. 260097403Sobrien * @param result_last Another random-access iterator. 260197403Sobrien * @return An iterator indicating the end of the resulting sequence. 260297403Sobrien * 260397403Sobrien * Copies and sorts the smallest N values from the range @p [first,last) 260497403Sobrien * to the range beginning at @p result_first, where the number of 260597403Sobrien * elements to be copied, @p N, is the smaller of @p (last-first) and 260697403Sobrien * @p (result_last-result_first). 260797403Sobrien * After the sort if @p i and @j are iterators in the range 260897403Sobrien * @p [result_first,result_first+N) such that @i precedes @j then 260997403Sobrien * @p *j<*i is false. 261097403Sobrien * The value returned is @p result_first+N. 261197403Sobrien */ 2612132720Skan template<typename _InputIterator, typename _RandomAccessIterator> 2613132720Skan _RandomAccessIterator 2614132720Skan partial_sort_copy(_InputIterator __first, _InputIterator __last, 2615132720Skan _RandomAccessIterator __result_first, 2616132720Skan _RandomAccessIterator __result_last) 261797403Sobrien { 2618132720Skan typedef typename iterator_traits<_InputIterator>::value_type 2619132720Skan _InputValueType; 2620132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2621132720Skan _OutputValueType; 2622132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 2623132720Skan _DistanceType; 262497403Sobrien 262597403Sobrien // concept requirements 2626132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 2627132720Skan __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 2628132720Skan _OutputValueType>) 2629169691Skan __glibcxx_function_requires(_LessThanOpConcept<_InputValueType, 2630169691Skan _OutputValueType>) 2631132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) 2632132720Skan __glibcxx_requires_valid_range(__first, __last); 2633132720Skan __glibcxx_requires_valid_range(__result_first, __result_last); 263497403Sobrien 2635132720Skan if (__result_first == __result_last) 2636132720Skan return __result_last; 2637132720Skan _RandomAccessIterator __result_real_last = __result_first; 2638132720Skan while(__first != __last && __result_real_last != __result_last) 2639132720Skan { 2640132720Skan *__result_real_last = *__first; 2641132720Skan ++__result_real_last; 2642132720Skan ++__first; 2643132720Skan } 2644132720Skan std::make_heap(__result_first, __result_real_last); 2645132720Skan while (__first != __last) 2646132720Skan { 2647132720Skan if (*__first < *__result_first) 2648132720Skan std::__adjust_heap(__result_first, _DistanceType(0), 2649132720Skan _DistanceType(__result_real_last 2650132720Skan - __result_first), 2651132720Skan _InputValueType(*__first)); 2652132720Skan ++__first; 2653132720Skan } 2654132720Skan std::sort_heap(__result_first, __result_real_last); 265597403Sobrien return __result_real_last; 265697403Sobrien } 265797403Sobrien 265897403Sobrien /** 265997403Sobrien * @brief Copy the smallest elements of a sequence using a predicate for 266097403Sobrien * comparison. 266197403Sobrien * @param first An input iterator. 266297403Sobrien * @param last Another input iterator. 266397403Sobrien * @param result_first A random-access iterator. 266497403Sobrien * @param result_last Another random-access iterator. 266597403Sobrien * @param comp A comparison functor. 266697403Sobrien * @return An iterator indicating the end of the resulting sequence. 266797403Sobrien * 266897403Sobrien * Copies and sorts the smallest N values from the range @p [first,last) 266997403Sobrien * to the range beginning at @p result_first, where the number of 267097403Sobrien * elements to be copied, @p N, is the smaller of @p (last-first) and 267197403Sobrien * @p (result_last-result_first). 267297403Sobrien * After the sort if @p i and @j are iterators in the range 267397403Sobrien * @p [result_first,result_first+N) such that @i precedes @j then 267497403Sobrien * @p comp(*j,*i) is false. 267597403Sobrien * The value returned is @p result_first+N. 267697403Sobrien */ 2677132720Skan template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare> 2678132720Skan _RandomAccessIterator 2679132720Skan partial_sort_copy(_InputIterator __first, _InputIterator __last, 2680132720Skan _RandomAccessIterator __result_first, 2681132720Skan _RandomAccessIterator __result_last, 268297403Sobrien _Compare __comp) 268397403Sobrien { 2684132720Skan typedef typename iterator_traits<_InputIterator>::value_type 2685132720Skan _InputValueType; 2686132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2687132720Skan _OutputValueType; 2688132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 2689132720Skan _DistanceType; 269097403Sobrien 269197403Sobrien // concept requirements 2692132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 2693132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 2694132720Skan _RandomAccessIterator>) 2695132720Skan __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 2696132720Skan _OutputValueType>) 2697132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2698169691Skan _InputValueType, _OutputValueType>) 2699169691Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 270097403Sobrien _OutputValueType, _OutputValueType>) 2701132720Skan __glibcxx_requires_valid_range(__first, __last); 2702132720Skan __glibcxx_requires_valid_range(__result_first, __result_last); 270397403Sobrien 2704132720Skan if (__result_first == __result_last) 2705132720Skan return __result_last; 2706132720Skan _RandomAccessIterator __result_real_last = __result_first; 2707132720Skan while(__first != __last && __result_real_last != __result_last) 2708132720Skan { 2709132720Skan *__result_real_last = *__first; 2710132720Skan ++__result_real_last; 2711132720Skan ++__first; 2712132720Skan } 2713132720Skan std::make_heap(__result_first, __result_real_last, __comp); 2714132720Skan while (__first != __last) 2715132720Skan { 2716132720Skan if (__comp(*__first, *__result_first)) 2717132720Skan std::__adjust_heap(__result_first, _DistanceType(0), 2718132720Skan _DistanceType(__result_real_last 2719132720Skan - __result_first), 2720132720Skan _InputValueType(*__first), 2721132720Skan __comp); 2722132720Skan ++__first; 2723132720Skan } 2724132720Skan std::sort_heap(__result_first, __result_real_last, __comp); 272597403Sobrien return __result_real_last; 272697403Sobrien } 272797403Sobrien 272897403Sobrien /** 2729132720Skan * @if maint 2730132720Skan * This is a helper function for the sort routine. 2731132720Skan * @endif 2732132720Skan */ 2733132720Skan template<typename _RandomAccessIterator, typename _Size> 2734132720Skan void 2735132720Skan __introsort_loop(_RandomAccessIterator __first, 2736132720Skan _RandomAccessIterator __last, 2737132720Skan _Size __depth_limit) 2738132720Skan { 2739132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2740132720Skan _ValueType; 2741132720Skan 2742169691Skan while (__last - __first > int(_S_threshold)) 2743132720Skan { 2744132720Skan if (__depth_limit == 0) 2745132720Skan { 2746132720Skan std::partial_sort(__first, __last, __last); 2747132720Skan return; 2748132720Skan } 2749132720Skan --__depth_limit; 2750132720Skan _RandomAccessIterator __cut = 2751132720Skan std::__unguarded_partition(__first, __last, 2752132720Skan _ValueType(std::__median(*__first, 2753132720Skan *(__first 2754132720Skan + (__last 2755132720Skan - __first) 2756132720Skan / 2), 2757132720Skan *(__last 2758132720Skan - 1)))); 2759132720Skan std::__introsort_loop(__cut, __last, __depth_limit); 2760132720Skan __last = __cut; 2761132720Skan } 2762132720Skan } 2763132720Skan 2764132720Skan /** 2765132720Skan * @if maint 2766132720Skan * This is a helper function for the sort routine. 2767132720Skan * @endif 2768132720Skan */ 2769132720Skan template<typename _RandomAccessIterator, typename _Size, typename _Compare> 2770132720Skan void 2771132720Skan __introsort_loop(_RandomAccessIterator __first, 2772132720Skan _RandomAccessIterator __last, 2773132720Skan _Size __depth_limit, _Compare __comp) 2774132720Skan { 2775132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2776132720Skan _ValueType; 2777132720Skan 2778169691Skan while (__last - __first > int(_S_threshold)) 2779132720Skan { 2780132720Skan if (__depth_limit == 0) 2781132720Skan { 2782132720Skan std::partial_sort(__first, __last, __last, __comp); 2783132720Skan return; 2784132720Skan } 2785132720Skan --__depth_limit; 2786132720Skan _RandomAccessIterator __cut = 2787132720Skan std::__unguarded_partition(__first, __last, 2788132720Skan _ValueType(std::__median(*__first, 2789132720Skan *(__first 2790132720Skan + (__last 2791132720Skan - __first) 2792132720Skan / 2), 2793132720Skan *(__last - 1), 2794132720Skan __comp)), 2795132720Skan __comp); 2796132720Skan std::__introsort_loop(__cut, __last, __depth_limit, __comp); 2797132720Skan __last = __cut; 2798132720Skan } 2799132720Skan } 2800132720Skan 2801132720Skan /** 2802132720Skan * @brief Sort the elements of a sequence. 280397403Sobrien * @param first An iterator. 280497403Sobrien * @param last Another iterator. 280597403Sobrien * @return Nothing. 280697403Sobrien * 2807132720Skan * Sorts the elements in the range @p [first,last) in ascending order, 2808132720Skan * such that @p *(i+1)<*i is false for each iterator @p i in the range 2809132720Skan * @p [first,last-1). 2810132720Skan * 2811132720Skan * The relative ordering of equivalent elements is not preserved, use 2812132720Skan * @p stable_sort() if this is needed. 281397403Sobrien */ 2814132720Skan template<typename _RandomAccessIterator> 2815132720Skan inline void 2816132720Skan sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 281797403Sobrien { 2818132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2819132720Skan _ValueType; 282097403Sobrien 282197403Sobrien // concept requirements 2822132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 2823132720Skan _RandomAccessIterator>) 2824132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 2825132720Skan __glibcxx_requires_valid_range(__first, __last); 282697403Sobrien 2827132720Skan if (__first != __last) 2828132720Skan { 2829169691Skan std::__introsort_loop(__first, __last, 2830169691Skan std::__lg(__last - __first) * 2); 2831132720Skan std::__final_insertion_sort(__first, __last); 2832132720Skan } 283397403Sobrien } 283497403Sobrien 283597403Sobrien /** 2836132720Skan * @brief Sort the elements of a sequence using a predicate for comparison. 283797403Sobrien * @param first An iterator. 283897403Sobrien * @param last Another iterator. 283997403Sobrien * @param comp A comparison functor. 284097403Sobrien * @return Nothing. 284197403Sobrien * 2842132720Skan * Sorts the elements in the range @p [first,last) in ascending order, 2843132720Skan * such that @p comp(*(i+1),*i) is false for every iterator @p i in the 2844132720Skan * range @p [first,last-1). 2845132720Skan * 2846132720Skan * The relative ordering of equivalent elements is not preserved, use 2847132720Skan * @p stable_sort() if this is needed. 284897403Sobrien */ 2849132720Skan template<typename _RandomAccessIterator, typename _Compare> 2850132720Skan inline void 2851132720Skan sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 2852132720Skan _Compare __comp) 285397403Sobrien { 2854132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2855132720Skan _ValueType; 285697403Sobrien 285797403Sobrien // concept requirements 2858132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 2859132720Skan _RandomAccessIterator>) 2860132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, 2861132720Skan _ValueType>) 2862132720Skan __glibcxx_requires_valid_range(__first, __last); 286397403Sobrien 2864132720Skan if (__first != __last) 2865132720Skan { 2866169691Skan std::__introsort_loop(__first, __last, 2867169691Skan std::__lg(__last - __first) * 2, __comp); 2868132720Skan std::__final_insertion_sort(__first, __last, __comp); 2869132720Skan } 287097403Sobrien } 287197403Sobrien 287297403Sobrien /** 287397403Sobrien * @brief Finds the first position in which @a val could be inserted 287497403Sobrien * without changing the ordering. 287597403Sobrien * @param first An iterator. 287697403Sobrien * @param last Another iterator. 287797403Sobrien * @param val The search term. 2878132720Skan * @return An iterator pointing to the first element "not less than" @a val, 2879132720Skan * or end() if every element is less than @a val. 288097403Sobrien * @ingroup binarysearch 288197403Sobrien */ 2882132720Skan template<typename _ForwardIterator, typename _Tp> 2883132720Skan _ForwardIterator 2884132720Skan lower_bound(_ForwardIterator __first, _ForwardIterator __last, 2885132720Skan const _Tp& __val) 288697403Sobrien { 2887132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 2888132720Skan _ValueType; 2889132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 2890132720Skan _DistanceType; 289197403Sobrien 289297403Sobrien // concept requirements 2893132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2894169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) 2895132720Skan __glibcxx_requires_partitioned(__first, __last, __val); 289697403Sobrien 2897132720Skan _DistanceType __len = std::distance(__first, __last); 289897403Sobrien _DistanceType __half; 2899132720Skan _ForwardIterator __middle; 290097403Sobrien 2901132720Skan while (__len > 0) 2902132720Skan { 2903132720Skan __half = __len >> 1; 2904132720Skan __middle = __first; 2905132720Skan std::advance(__middle, __half); 2906132720Skan if (*__middle < __val) 2907132720Skan { 2908132720Skan __first = __middle; 2909132720Skan ++__first; 2910132720Skan __len = __len - __half - 1; 2911132720Skan } 2912132720Skan else 2913132720Skan __len = __half; 291497403Sobrien } 291597403Sobrien return __first; 291697403Sobrien } 291797403Sobrien 291897403Sobrien /** 291997403Sobrien * @brief Finds the first position in which @a val could be inserted 292097403Sobrien * without changing the ordering. 292197403Sobrien * @param first An iterator. 292297403Sobrien * @param last Another iterator. 292397403Sobrien * @param val The search term. 292497403Sobrien * @param comp A functor to use for comparisons. 2925132720Skan * @return An iterator pointing to the first element "not less than" @a val, 2926132720Skan * or end() if every element is less than @a val. 292797403Sobrien * @ingroup binarysearch 292897403Sobrien * 292997403Sobrien * The comparison function should have the same effects on ordering as 293097403Sobrien * the function used for the initial sort. 293197403Sobrien */ 2932132720Skan template<typename _ForwardIterator, typename _Tp, typename _Compare> 2933132720Skan _ForwardIterator 2934132720Skan lower_bound(_ForwardIterator __first, _ForwardIterator __last, 293597403Sobrien const _Tp& __val, _Compare __comp) 293697403Sobrien { 2937132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 2938132720Skan _ValueType; 2939132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 2940132720Skan _DistanceType; 294197403Sobrien 294297403Sobrien // concept requirements 2943132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2944132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2945132720Skan _ValueType, _Tp>) 2946132720Skan __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 294797403Sobrien 2948132720Skan _DistanceType __len = std::distance(__first, __last); 294997403Sobrien _DistanceType __half; 2950132720Skan _ForwardIterator __middle; 295197403Sobrien 2952132720Skan while (__len > 0) 2953132720Skan { 2954132720Skan __half = __len >> 1; 2955132720Skan __middle = __first; 2956132720Skan std::advance(__middle, __half); 2957132720Skan if (__comp(*__middle, __val)) 2958132720Skan { 2959132720Skan __first = __middle; 2960132720Skan ++__first; 2961132720Skan __len = __len - __half - 1; 2962132720Skan } 2963132720Skan else 2964132720Skan __len = __half; 296597403Sobrien } 296697403Sobrien return __first; 296797403Sobrien } 296897403Sobrien 296997403Sobrien /** 297097403Sobrien * @brief Finds the last position in which @a val could be inserted 297197403Sobrien * without changing the ordering. 297297403Sobrien * @param first An iterator. 297397403Sobrien * @param last Another iterator. 297497403Sobrien * @param val The search term. 2975132720Skan * @return An iterator pointing to the first element greater than @a val, 2976132720Skan * or end() if no elements are greater than @a val. 297797403Sobrien * @ingroup binarysearch 297897403Sobrien */ 2979132720Skan template<typename _ForwardIterator, typename _Tp> 2980132720Skan _ForwardIterator 2981132720Skan upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2982132720Skan const _Tp& __val) 298397403Sobrien { 2984132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 2985132720Skan _ValueType; 2986132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 2987132720Skan _DistanceType; 298897403Sobrien 298997403Sobrien // concept requirements 2990132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2991169691Skan __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) 2992132720Skan __glibcxx_requires_partitioned(__first, __last, __val); 299397403Sobrien 2994132720Skan _DistanceType __len = std::distance(__first, __last); 299597403Sobrien _DistanceType __half; 2996132720Skan _ForwardIterator __middle; 299797403Sobrien 2998132720Skan while (__len > 0) 2999132720Skan { 3000132720Skan __half = __len >> 1; 3001132720Skan __middle = __first; 3002132720Skan std::advance(__middle, __half); 3003132720Skan if (__val < *__middle) 3004132720Skan __len = __half; 3005132720Skan else 3006132720Skan { 3007132720Skan __first = __middle; 3008132720Skan ++__first; 3009132720Skan __len = __len - __half - 1; 3010132720Skan } 301197403Sobrien } 301297403Sobrien return __first; 301397403Sobrien } 301497403Sobrien 301597403Sobrien /** 301697403Sobrien * @brief Finds the last position in which @a val could be inserted 301797403Sobrien * without changing the ordering. 301897403Sobrien * @param first An iterator. 301997403Sobrien * @param last Another iterator. 302097403Sobrien * @param val The search term. 302197403Sobrien * @param comp A functor to use for comparisons. 3022132720Skan * @return An iterator pointing to the first element greater than @a val, 3023132720Skan * or end() if no elements are greater than @a val. 302497403Sobrien * @ingroup binarysearch 302597403Sobrien * 302697403Sobrien * The comparison function should have the same effects on ordering as 302797403Sobrien * the function used for the initial sort. 302897403Sobrien */ 3029132720Skan template<typename _ForwardIterator, typename _Tp, typename _Compare> 3030132720Skan _ForwardIterator 3031132720Skan upper_bound(_ForwardIterator __first, _ForwardIterator __last, 303297403Sobrien const _Tp& __val, _Compare __comp) 303397403Sobrien { 3034132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 3035132720Skan _ValueType; 3036132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 3037132720Skan _DistanceType; 303897403Sobrien 303997403Sobrien // concept requirements 3040132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3041132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3042132720Skan _Tp, _ValueType>) 3043132720Skan __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 304497403Sobrien 3045132720Skan _DistanceType __len = std::distance(__first, __last); 304697403Sobrien _DistanceType __half; 3047132720Skan _ForwardIterator __middle; 304897403Sobrien 3049132720Skan while (__len > 0) 3050132720Skan { 3051132720Skan __half = __len >> 1; 3052132720Skan __middle = __first; 3053132720Skan std::advance(__middle, __half); 3054132720Skan if (__comp(__val, *__middle)) 3055132720Skan __len = __half; 3056132720Skan else 3057132720Skan { 3058132720Skan __first = __middle; 3059132720Skan ++__first; 3060132720Skan __len = __len - __half - 1; 3061132720Skan } 306297403Sobrien } 306397403Sobrien return __first; 306497403Sobrien } 306597403Sobrien 306697403Sobrien /** 3067132720Skan * @if maint 3068132720Skan * This is a helper function for the merge routines. 3069132720Skan * @endif 307097403Sobrien */ 3071132720Skan template<typename _BidirectionalIterator, typename _Distance> 3072132720Skan void 3073132720Skan __merge_without_buffer(_BidirectionalIterator __first, 3074132720Skan _BidirectionalIterator __middle, 3075132720Skan _BidirectionalIterator __last, 3076132720Skan _Distance __len1, _Distance __len2) 307797403Sobrien { 3078132720Skan if (__len1 == 0 || __len2 == 0) 3079132720Skan return; 3080132720Skan if (__len1 + __len2 == 2) 3081132720Skan { 3082132720Skan if (*__middle < *__first) 3083132720Skan std::iter_swap(__first, __middle); 3084132720Skan return; 308597403Sobrien } 3086132720Skan _BidirectionalIterator __first_cut = __first; 3087132720Skan _BidirectionalIterator __second_cut = __middle; 3088132720Skan _Distance __len11 = 0; 3089132720Skan _Distance __len22 = 0; 3090132720Skan if (__len1 > __len2) 3091132720Skan { 3092132720Skan __len11 = __len1 / 2; 3093132720Skan std::advance(__first_cut, __len11); 3094132720Skan __second_cut = std::lower_bound(__middle, __last, *__first_cut); 3095132720Skan __len22 = std::distance(__middle, __second_cut); 309697403Sobrien } 3097132720Skan else 3098132720Skan { 3099132720Skan __len22 = __len2 / 2; 3100132720Skan std::advance(__second_cut, __len22); 3101132720Skan __first_cut = std::upper_bound(__first, __middle, *__second_cut); 3102132720Skan __len11 = std::distance(__first, __first_cut); 3103132720Skan } 3104132720Skan std::rotate(__first_cut, __middle, __second_cut); 3105132720Skan _BidirectionalIterator __new_middle = __first_cut; 3106132720Skan std::advance(__new_middle, std::distance(__middle, __second_cut)); 3107132720Skan std::__merge_without_buffer(__first, __first_cut, __new_middle, 3108132720Skan __len11, __len22); 3109132720Skan std::__merge_without_buffer(__new_middle, __second_cut, __last, 3110132720Skan __len1 - __len11, __len2 - __len22); 311197403Sobrien } 311297403Sobrien 311397403Sobrien /** 3114132720Skan * @if maint 3115132720Skan * This is a helper function for the merge routines. 3116132720Skan * @endif 311797403Sobrien */ 3118132720Skan template<typename _BidirectionalIterator, typename _Distance, 3119132720Skan typename _Compare> 3120132720Skan void 3121132720Skan __merge_without_buffer(_BidirectionalIterator __first, 3122132720Skan _BidirectionalIterator __middle, 3123132720Skan _BidirectionalIterator __last, 3124132720Skan _Distance __len1, _Distance __len2, 3125132720Skan _Compare __comp) 312697403Sobrien { 3127132720Skan if (__len1 == 0 || __len2 == 0) 3128132720Skan return; 3129132720Skan if (__len1 + __len2 == 2) 3130132720Skan { 3131132720Skan if (__comp(*__middle, *__first)) 3132132720Skan std::iter_swap(__first, __middle); 3133132720Skan return; 313497403Sobrien } 3135132720Skan _BidirectionalIterator __first_cut = __first; 3136132720Skan _BidirectionalIterator __second_cut = __middle; 3137132720Skan _Distance __len11 = 0; 3138132720Skan _Distance __len22 = 0; 3139132720Skan if (__len1 > __len2) 3140132720Skan { 3141132720Skan __len11 = __len1 / 2; 3142132720Skan std::advance(__first_cut, __len11); 3143132720Skan __second_cut = std::lower_bound(__middle, __last, *__first_cut, 3144132720Skan __comp); 3145132720Skan __len22 = std::distance(__middle, __second_cut); 314697403Sobrien } 3147132720Skan else 3148132720Skan { 3149132720Skan __len22 = __len2 / 2; 3150132720Skan std::advance(__second_cut, __len22); 3151132720Skan __first_cut = std::upper_bound(__first, __middle, *__second_cut, 3152132720Skan __comp); 3153132720Skan __len11 = std::distance(__first, __first_cut); 3154132720Skan } 3155132720Skan std::rotate(__first_cut, __middle, __second_cut); 3156132720Skan _BidirectionalIterator __new_middle = __first_cut; 3157132720Skan std::advance(__new_middle, std::distance(__middle, __second_cut)); 3158132720Skan std::__merge_without_buffer(__first, __first_cut, __new_middle, 3159132720Skan __len11, __len22, __comp); 3160132720Skan std::__merge_without_buffer(__new_middle, __second_cut, __last, 3161132720Skan __len1 - __len11, __len2 - __len22, __comp); 316297403Sobrien } 316397403Sobrien 316497403Sobrien /** 3165132720Skan * @if maint 3166132720Skan * This is a helper function for the stable sorting routines. 3167132720Skan * @endif 316897403Sobrien */ 3169132720Skan template<typename _RandomAccessIterator> 3170132720Skan void 3171132720Skan __inplace_stable_sort(_RandomAccessIterator __first, 3172132720Skan _RandomAccessIterator __last) 317397403Sobrien { 3174132720Skan if (__last - __first < 15) 3175132720Skan { 3176132720Skan std::__insertion_sort(__first, __last); 3177132720Skan return; 3178132720Skan } 3179132720Skan _RandomAccessIterator __middle = __first + (__last - __first) / 2; 3180132720Skan std::__inplace_stable_sort(__first, __middle); 3181132720Skan std::__inplace_stable_sort(__middle, __last); 3182132720Skan std::__merge_without_buffer(__first, __middle, __last, 3183132720Skan __middle - __first, 3184132720Skan __last - __middle); 318597403Sobrien } 318697403Sobrien 318797403Sobrien /** 3188132720Skan * @if maint 3189132720Skan * This is a helper function for the stable sorting routines. 3190132720Skan * @endif 319197403Sobrien */ 3192132720Skan template<typename _RandomAccessIterator, typename _Compare> 3193132720Skan void 3194132720Skan __inplace_stable_sort(_RandomAccessIterator __first, 3195132720Skan _RandomAccessIterator __last, _Compare __comp) 319697403Sobrien { 3197132720Skan if (__last - __first < 15) 3198132720Skan { 3199132720Skan std::__insertion_sort(__first, __last, __comp); 3200132720Skan return; 3201132720Skan } 3202132720Skan _RandomAccessIterator __middle = __first + (__last - __first) / 2; 3203132720Skan std::__inplace_stable_sort(__first, __middle, __comp); 3204132720Skan std::__inplace_stable_sort(__middle, __last, __comp); 3205132720Skan std::__merge_without_buffer(__first, __middle, __last, 3206132720Skan __middle - __first, 3207132720Skan __last - __middle, 3208132720Skan __comp); 320997403Sobrien } 321097403Sobrien 321197403Sobrien /** 321297403Sobrien * @brief Merges two sorted ranges. 321397403Sobrien * @param first1 An iterator. 321497403Sobrien * @param first2 Another iterator. 321597403Sobrien * @param last1 Another iterator. 321697403Sobrien * @param last2 Another iterator. 321797403Sobrien * @param result An iterator pointing to the end of the merged range. 321897403Sobrien * @return An iterator pointing to the first element "not less than" @a val. 321997403Sobrien * 322097403Sobrien * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 322197403Sobrien * [result, result + (last1-first1) + (last2-first2)). Both input ranges 322297403Sobrien * must be sorted, and the output range must not overlap with either of 322397403Sobrien * the input ranges. The sort is @e stable, that is, for equivalent 322497403Sobrien * elements in the two ranges, elements from the first range will always 322597403Sobrien * come before elements from the second. 322697403Sobrien */ 3227132720Skan template<typename _InputIterator1, typename _InputIterator2, 3228132720Skan typename _OutputIterator> 3229132720Skan _OutputIterator 3230132720Skan merge(_InputIterator1 __first1, _InputIterator1 __last1, 3231132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 3232132720Skan _OutputIterator __result) 323397403Sobrien { 3234169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 3235169691Skan _ValueType1; 3236169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 3237169691Skan _ValueType2; 3238169691Skan 323997403Sobrien // concept requirements 3240132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 3241132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 3242132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3243169691Skan _ValueType1>) 3244169691Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3245169691Skan _ValueType2>) 3246169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 3247132720Skan __glibcxx_requires_sorted(__first1, __last1); 3248132720Skan __glibcxx_requires_sorted(__first2, __last2); 324997403Sobrien 3250132720Skan while (__first1 != __last1 && __first2 != __last2) 3251132720Skan { 3252132720Skan if (*__first2 < *__first1) 3253132720Skan { 3254132720Skan *__result = *__first2; 3255132720Skan ++__first2; 3256132720Skan } 3257132720Skan else 3258132720Skan { 3259132720Skan *__result = *__first1; 3260132720Skan ++__first1; 3261132720Skan } 3262132720Skan ++__result; 326397403Sobrien } 3264132720Skan return std::copy(__first2, __last2, std::copy(__first1, __last1, 3265132720Skan __result)); 326697403Sobrien } 326797403Sobrien 326897403Sobrien /** 326997403Sobrien * @brief Merges two sorted ranges. 327097403Sobrien * @param first1 An iterator. 327197403Sobrien * @param first2 Another iterator. 327297403Sobrien * @param last1 Another iterator. 327397403Sobrien * @param last2 Another iterator. 327497403Sobrien * @param result An iterator pointing to the end of the merged range. 327597403Sobrien * @param comp A functor to use for comparisons. 327697403Sobrien * @return An iterator pointing to the first element "not less than" @a val. 327797403Sobrien * 327897403Sobrien * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 327997403Sobrien * [result, result + (last1-first1) + (last2-first2)). Both input ranges 328097403Sobrien * must be sorted, and the output range must not overlap with either of 328197403Sobrien * the input ranges. The sort is @e stable, that is, for equivalent 328297403Sobrien * elements in the two ranges, elements from the first range will always 328397403Sobrien * come before elements from the second. 328497403Sobrien * 328597403Sobrien * The comparison function should have the same effects on ordering as 328697403Sobrien * the function used for the initial sort. 328797403Sobrien */ 3288132720Skan template<typename _InputIterator1, typename _InputIterator2, 3289132720Skan typename _OutputIterator, typename _Compare> 3290132720Skan _OutputIterator 3291132720Skan merge(_InputIterator1 __first1, _InputIterator1 __last1, 3292132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 3293132720Skan _OutputIterator __result, _Compare __comp) 329497403Sobrien { 3295169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 3296169691Skan _ValueType1; 3297169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 3298169691Skan _ValueType2; 3299169691Skan 330097403Sobrien // concept requirements 3301132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 3302132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 3303132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3304169691Skan _ValueType1>) 3305169691Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3306169691Skan _ValueType2>) 3307132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3308169691Skan _ValueType2, _ValueType1>) 3309132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 3310132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 331197403Sobrien 3312132720Skan while (__first1 != __last1 && __first2 != __last2) 3313132720Skan { 3314132720Skan if (__comp(*__first2, *__first1)) 3315132720Skan { 3316132720Skan *__result = *__first2; 3317132720Skan ++__first2; 3318132720Skan } 3319132720Skan else 3320132720Skan { 3321132720Skan *__result = *__first1; 3322132720Skan ++__first1; 3323132720Skan } 3324132720Skan ++__result; 332597403Sobrien } 3326132720Skan return std::copy(__first2, __last2, std::copy(__first1, __last1, 3327132720Skan __result)); 3328132720Skan } 3329132720Skan 3330132720Skan template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 3331132720Skan typename _Distance> 3332132720Skan void 3333132720Skan __merge_sort_loop(_RandomAccessIterator1 __first, 3334132720Skan _RandomAccessIterator1 __last, 3335132720Skan _RandomAccessIterator2 __result, 3336132720Skan _Distance __step_size) 3337132720Skan { 3338132720Skan const _Distance __two_step = 2 * __step_size; 3339132720Skan 3340132720Skan while (__last - __first >= __two_step) 3341132720Skan { 3342132720Skan __result = std::merge(__first, __first + __step_size, 3343132720Skan __first + __step_size, __first + __two_step, 3344132720Skan __result); 3345132720Skan __first += __two_step; 334697403Sobrien } 3347132720Skan 3348132720Skan __step_size = std::min(_Distance(__last - __first), __step_size); 3349132720Skan std::merge(__first, __first + __step_size, __first + __step_size, __last, 3350132720Skan __result); 335197403Sobrien } 335297403Sobrien 3353132720Skan template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 3354132720Skan typename _Distance, typename _Compare> 335597403Sobrien void 3356132720Skan __merge_sort_loop(_RandomAccessIterator1 __first, 3357132720Skan _RandomAccessIterator1 __last, 3358132720Skan _RandomAccessIterator2 __result, _Distance __step_size, 3359132720Skan _Compare __comp) 336097403Sobrien { 3361132720Skan const _Distance __two_step = 2 * __step_size; 3362132720Skan 3363132720Skan while (__last - __first >= __two_step) 3364132720Skan { 3365132720Skan __result = std::merge(__first, __first + __step_size, 3366132720Skan __first + __step_size, __first + __two_step, 3367132720Skan __result, 3368132720Skan __comp); 3369132720Skan __first += __two_step; 3370132720Skan } 3371132720Skan __step_size = std::min(_Distance(__last - __first), __step_size); 3372132720Skan 3373132720Skan std::merge(__first, __first + __step_size, 3374132720Skan __first + __step_size, __last, 3375132720Skan __result, 3376132720Skan __comp); 337797403Sobrien } 337897403Sobrien 3379132720Skan enum { _S_chunk_size = 7 }; 3380132720Skan 3381132720Skan template<typename _RandomAccessIterator, typename _Distance> 338297403Sobrien void 3383132720Skan __chunk_insertion_sort(_RandomAccessIterator __first, 3384132720Skan _RandomAccessIterator __last, 3385132720Skan _Distance __chunk_size) 338697403Sobrien { 3387132720Skan while (__last - __first >= __chunk_size) 3388132720Skan { 3389132720Skan std::__insertion_sort(__first, __first + __chunk_size); 3390132720Skan __first += __chunk_size; 3391132720Skan } 3392132720Skan std::__insertion_sort(__first, __last); 339397403Sobrien } 339497403Sobrien 3395132720Skan template<typename _RandomAccessIterator, typename _Distance, typename _Compare> 3396132720Skan void 3397132720Skan __chunk_insertion_sort(_RandomAccessIterator __first, 3398132720Skan _RandomAccessIterator __last, 3399132720Skan _Distance __chunk_size, _Compare __comp) 340097403Sobrien { 3401132720Skan while (__last - __first >= __chunk_size) 3402132720Skan { 3403132720Skan std::__insertion_sort(__first, __first + __chunk_size, __comp); 3404132720Skan __first += __chunk_size; 3405132720Skan } 3406132720Skan std::__insertion_sort(__first, __last, __comp); 340797403Sobrien } 340897403Sobrien 3409132720Skan template<typename _RandomAccessIterator, typename _Pointer> 3410132720Skan void 3411132720Skan __merge_sort_with_buffer(_RandomAccessIterator __first, 3412132720Skan _RandomAccessIterator __last, 3413132720Skan _Pointer __buffer) 3414132720Skan { 3415132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3416132720Skan _Distance; 3417132720Skan 3418132720Skan const _Distance __len = __last - __first; 3419132720Skan const _Pointer __buffer_last = __buffer + __len; 3420132720Skan 3421132720Skan _Distance __step_size = _S_chunk_size; 3422132720Skan std::__chunk_insertion_sort(__first, __last, __step_size); 3423132720Skan 3424132720Skan while (__step_size < __len) 3425132720Skan { 3426132720Skan std::__merge_sort_loop(__first, __last, __buffer, __step_size); 3427132720Skan __step_size *= 2; 3428132720Skan std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size); 3429132720Skan __step_size *= 2; 3430132720Skan } 3431132720Skan } 3432132720Skan 3433132720Skan template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> 3434132720Skan void 3435132720Skan __merge_sort_with_buffer(_RandomAccessIterator __first, 3436132720Skan _RandomAccessIterator __last, 3437132720Skan _Pointer __buffer, _Compare __comp) 3438132720Skan { 3439132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3440132720Skan _Distance; 3441132720Skan 3442132720Skan const _Distance __len = __last - __first; 3443132720Skan const _Pointer __buffer_last = __buffer + __len; 3444132720Skan 3445132720Skan _Distance __step_size = _S_chunk_size; 3446132720Skan std::__chunk_insertion_sort(__first, __last, __step_size, __comp); 3447132720Skan 3448132720Skan while (__step_size < __len) 3449132720Skan { 3450132720Skan std::__merge_sort_loop(__first, __last, __buffer, 3451132720Skan __step_size, __comp); 3452132720Skan __step_size *= 2; 3453132720Skan std::__merge_sort_loop(__buffer, __buffer_last, __first, 3454132720Skan __step_size, __comp); 3455132720Skan __step_size *= 2; 3456132720Skan } 3457132720Skan } 3458132720Skan 345997403Sobrien /** 346097403Sobrien * @if maint 346197403Sobrien * This is a helper function for the merge routines. 346297403Sobrien * @endif 346397403Sobrien */ 3464132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 3465132720Skan typename _BidirectionalIterator3> 3466132720Skan _BidirectionalIterator3 3467132720Skan __merge_backward(_BidirectionalIterator1 __first1, 3468132720Skan _BidirectionalIterator1 __last1, 3469132720Skan _BidirectionalIterator2 __first2, 3470132720Skan _BidirectionalIterator2 __last2, 3471132720Skan _BidirectionalIterator3 __result) 347297403Sobrien { 347397403Sobrien if (__first1 == __last1) 3474132720Skan return std::copy_backward(__first2, __last2, __result); 347597403Sobrien if (__first2 == __last2) 3476132720Skan return std::copy_backward(__first1, __last1, __result); 347797403Sobrien --__last1; 347897403Sobrien --__last2; 3479132720Skan while (true) 3480132720Skan { 3481132720Skan if (*__last2 < *__last1) 3482132720Skan { 3483132720Skan *--__result = *__last1; 3484132720Skan if (__first1 == __last1) 3485132720Skan return std::copy_backward(__first2, ++__last2, __result); 3486132720Skan --__last1; 3487132720Skan } 3488132720Skan else 3489132720Skan { 3490132720Skan *--__result = *__last2; 3491132720Skan if (__first2 == __last2) 3492132720Skan return std::copy_backward(__first1, ++__last1, __result); 3493132720Skan --__last2; 3494132720Skan } 349597403Sobrien } 349697403Sobrien } 349797403Sobrien 349897403Sobrien /** 349997403Sobrien * @if maint 350097403Sobrien * This is a helper function for the merge routines. 350197403Sobrien * @endif 350297403Sobrien */ 3503132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 3504132720Skan typename _BidirectionalIterator3, typename _Compare> 3505132720Skan _BidirectionalIterator3 3506132720Skan __merge_backward(_BidirectionalIterator1 __first1, 3507132720Skan _BidirectionalIterator1 __last1, 3508132720Skan _BidirectionalIterator2 __first2, 3509132720Skan _BidirectionalIterator2 __last2, 3510132720Skan _BidirectionalIterator3 __result, 351197403Sobrien _Compare __comp) 351297403Sobrien { 351397403Sobrien if (__first1 == __last1) 3514132720Skan return std::copy_backward(__first2, __last2, __result); 351597403Sobrien if (__first2 == __last2) 3516132720Skan return std::copy_backward(__first1, __last1, __result); 351797403Sobrien --__last1; 351897403Sobrien --__last2; 3519132720Skan while (true) 3520132720Skan { 3521132720Skan if (__comp(*__last2, *__last1)) 3522132720Skan { 3523132720Skan *--__result = *__last1; 3524132720Skan if (__first1 == __last1) 3525132720Skan return std::copy_backward(__first2, ++__last2, __result); 3526132720Skan --__last1; 3527132720Skan } 3528132720Skan else 3529132720Skan { 3530132720Skan *--__result = *__last2; 3531132720Skan if (__first2 == __last2) 3532132720Skan return std::copy_backward(__first1, ++__last1, __result); 3533132720Skan --__last2; 3534132720Skan } 353597403Sobrien } 3536132720Skan } 3537132720Skan 3538132720Skan /** 3539132720Skan * @if maint 3540132720Skan * This is a helper function for the merge routines. 3541132720Skan * @endif 3542132720Skan */ 3543132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 3544132720Skan typename _Distance> 3545132720Skan _BidirectionalIterator1 3546132720Skan __rotate_adaptive(_BidirectionalIterator1 __first, 3547132720Skan _BidirectionalIterator1 __middle, 3548132720Skan _BidirectionalIterator1 __last, 3549132720Skan _Distance __len1, _Distance __len2, 3550132720Skan _BidirectionalIterator2 __buffer, 3551132720Skan _Distance __buffer_size) 3552132720Skan { 3553132720Skan _BidirectionalIterator2 __buffer_end; 3554132720Skan if (__len1 > __len2 && __len2 <= __buffer_size) 3555132720Skan { 3556132720Skan __buffer_end = std::copy(__middle, __last, __buffer); 3557132720Skan std::copy_backward(__first, __middle, __last); 3558132720Skan return std::copy(__buffer, __buffer_end, __first); 355997403Sobrien } 3560132720Skan else if (__len1 <= __buffer_size) 3561132720Skan { 3562132720Skan __buffer_end = std::copy(__first, __middle, __buffer); 3563132720Skan std::copy(__middle, __last, __first); 3564132720Skan return std::copy_backward(__buffer, __buffer_end, __last); 3565132720Skan } 3566132720Skan else 3567132720Skan { 3568132720Skan std::rotate(__first, __middle, __last); 3569132720Skan std::advance(__first, std::distance(__middle, __last)); 3570132720Skan return __first; 3571132720Skan } 357297403Sobrien } 357397403Sobrien 357497403Sobrien /** 357597403Sobrien * @if maint 357697403Sobrien * This is a helper function for the merge routines. 357797403Sobrien * @endif 357897403Sobrien */ 3579132720Skan template<typename _BidirectionalIterator, typename _Distance, 3580132720Skan typename _Pointer> 358197403Sobrien void 3582132720Skan __merge_adaptive(_BidirectionalIterator __first, 3583132720Skan _BidirectionalIterator __middle, 3584132720Skan _BidirectionalIterator __last, 358597403Sobrien _Distance __len1, _Distance __len2, 358697403Sobrien _Pointer __buffer, _Distance __buffer_size) 358797403Sobrien { 3588132720Skan if (__len1 <= __len2 && __len1 <= __buffer_size) 3589132720Skan { 3590132720Skan _Pointer __buffer_end = std::copy(__first, __middle, __buffer); 3591132720Skan std::merge(__buffer, __buffer_end, __middle, __last, __first); 3592132720Skan } 3593132720Skan else if (__len2 <= __buffer_size) 3594132720Skan { 3595132720Skan _Pointer __buffer_end = std::copy(__middle, __last, __buffer); 3596132720Skan std::__merge_backward(__first, __middle, __buffer, 3597132720Skan __buffer_end, __last); 3598132720Skan } 3599132720Skan else 3600132720Skan { 3601132720Skan _BidirectionalIterator __first_cut = __first; 3602132720Skan _BidirectionalIterator __second_cut = __middle; 3603132720Skan _Distance __len11 = 0; 3604132720Skan _Distance __len22 = 0; 3605132720Skan if (__len1 > __len2) 3606132720Skan { 3607132720Skan __len11 = __len1 / 2; 3608132720Skan std::advance(__first_cut, __len11); 3609132720Skan __second_cut = std::lower_bound(__middle, __last, 3610132720Skan *__first_cut); 3611132720Skan __len22 = std::distance(__middle, __second_cut); 361297403Sobrien } 3613132720Skan else 3614132720Skan { 3615132720Skan __len22 = __len2 / 2; 3616132720Skan std::advance(__second_cut, __len22); 3617132720Skan __first_cut = std::upper_bound(__first, __middle, 3618132720Skan *__second_cut); 3619132720Skan __len11 = std::distance(__first, __first_cut); 362097403Sobrien } 3621132720Skan _BidirectionalIterator __new_middle = 3622132720Skan std::__rotate_adaptive(__first_cut, __middle, __second_cut, 3623132720Skan __len1 - __len11, __len22, __buffer, 3624132720Skan __buffer_size); 3625132720Skan std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 3626132720Skan __len22, __buffer, __buffer_size); 3627132720Skan std::__merge_adaptive(__new_middle, __second_cut, __last, 3628132720Skan __len1 - __len11, 3629132720Skan __len2 - __len22, __buffer, __buffer_size); 3630132720Skan } 363197403Sobrien } 363297403Sobrien 363397403Sobrien /** 363497403Sobrien * @if maint 363597403Sobrien * This is a helper function for the merge routines. 363697403Sobrien * @endif 363797403Sobrien */ 3638132720Skan template<typename _BidirectionalIterator, typename _Distance, typename _Pointer, 363997403Sobrien typename _Compare> 364097403Sobrien void 3641132720Skan __merge_adaptive(_BidirectionalIterator __first, 3642132720Skan _BidirectionalIterator __middle, 3643132720Skan _BidirectionalIterator __last, 364497403Sobrien _Distance __len1, _Distance __len2, 364597403Sobrien _Pointer __buffer, _Distance __buffer_size, 364697403Sobrien _Compare __comp) 364797403Sobrien { 3648132720Skan if (__len1 <= __len2 && __len1 <= __buffer_size) 3649132720Skan { 3650132720Skan _Pointer __buffer_end = std::copy(__first, __middle, __buffer); 3651132720Skan std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp); 3652132720Skan } 3653132720Skan else if (__len2 <= __buffer_size) 3654132720Skan { 3655132720Skan _Pointer __buffer_end = std::copy(__middle, __last, __buffer); 3656132720Skan std::__merge_backward(__first, __middle, __buffer, __buffer_end, 3657132720Skan __last, __comp); 3658132720Skan } 3659132720Skan else 3660132720Skan { 3661132720Skan _BidirectionalIterator __first_cut = __first; 3662132720Skan _BidirectionalIterator __second_cut = __middle; 3663132720Skan _Distance __len11 = 0; 3664132720Skan _Distance __len22 = 0; 3665132720Skan if (__len1 > __len2) 3666132720Skan { 3667132720Skan __len11 = __len1 / 2; 3668132720Skan std::advance(__first_cut, __len11); 3669132720Skan __second_cut = std::lower_bound(__middle, __last, *__first_cut, 3670132720Skan __comp); 3671132720Skan __len22 = std::distance(__middle, __second_cut); 3672132720Skan } 3673132720Skan else 3674132720Skan { 3675132720Skan __len22 = __len2 / 2; 3676132720Skan std::advance(__second_cut, __len22); 3677132720Skan __first_cut = std::upper_bound(__first, __middle, *__second_cut, 367897403Sobrien __comp); 3679132720Skan __len11 = std::distance(__first, __first_cut); 368097403Sobrien } 3681132720Skan _BidirectionalIterator __new_middle = 3682132720Skan std::__rotate_adaptive(__first_cut, __middle, __second_cut, 3683132720Skan __len1 - __len11, __len22, __buffer, 3684132720Skan __buffer_size); 3685132720Skan std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 3686132720Skan __len22, __buffer, __buffer_size, __comp); 3687132720Skan std::__merge_adaptive(__new_middle, __second_cut, __last, 3688132720Skan __len1 - __len11, 3689132720Skan __len2 - __len22, __buffer, 3690132720Skan __buffer_size, __comp); 3691132720Skan } 369297403Sobrien } 369397403Sobrien 369497403Sobrien /** 369597403Sobrien * @brief Merges two sorted ranges in place. 369697403Sobrien * @param first An iterator. 369797403Sobrien * @param middle Another iterator. 369897403Sobrien * @param last Another iterator. 369997403Sobrien * @return Nothing. 370097403Sobrien * 370197403Sobrien * Merges two sorted and consecutive ranges, [first,middle) and 370297403Sobrien * [middle,last), and puts the result in [first,last). The output will 370397403Sobrien * be sorted. The sort is @e stable, that is, for equivalent 370497403Sobrien * elements in the two ranges, elements from the first range will always 370597403Sobrien * come before elements from the second. 370697403Sobrien * 370797403Sobrien * If enough additional memory is available, this takes (last-first)-1 370897403Sobrien * comparisons. Otherwise an NlogN algorithm is used, where N is 370997403Sobrien * distance(first,last). 371097403Sobrien */ 3711132720Skan template<typename _BidirectionalIterator> 371297403Sobrien void 3713132720Skan inplace_merge(_BidirectionalIterator __first, 3714132720Skan _BidirectionalIterator __middle, 3715132720Skan _BidirectionalIterator __last) 371697403Sobrien { 3717132720Skan typedef typename iterator_traits<_BidirectionalIterator>::value_type 371897403Sobrien _ValueType; 3719132720Skan typedef typename iterator_traits<_BidirectionalIterator>::difference_type 372097403Sobrien _DistanceType; 372197403Sobrien 372297403Sobrien // concept requirements 3723132720Skan __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 3724132720Skan _BidirectionalIterator>) 3725132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 3726132720Skan __glibcxx_requires_sorted(__first, __middle); 3727132720Skan __glibcxx_requires_sorted(__middle, __last); 372897403Sobrien 372997403Sobrien if (__first == __middle || __middle == __last) 373097403Sobrien return; 373197403Sobrien 3732132720Skan _DistanceType __len1 = std::distance(__first, __middle); 3733132720Skan _DistanceType __len2 = std::distance(__middle, __last); 373497403Sobrien 3735132720Skan _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, 3736132720Skan __last); 373797403Sobrien if (__buf.begin() == 0) 3738132720Skan std::__merge_without_buffer(__first, __middle, __last, __len1, __len2); 373997403Sobrien else 3740132720Skan std::__merge_adaptive(__first, __middle, __last, __len1, __len2, 3741132720Skan __buf.begin(), _DistanceType(__buf.size())); 374297403Sobrien } 374397403Sobrien 374497403Sobrien /** 374597403Sobrien * @brief Merges two sorted ranges in place. 374697403Sobrien * @param first An iterator. 374797403Sobrien * @param middle Another iterator. 374897403Sobrien * @param last Another iterator. 374997403Sobrien * @param comp A functor to use for comparisons. 375097403Sobrien * @return Nothing. 375197403Sobrien * 375297403Sobrien * Merges two sorted and consecutive ranges, [first,middle) and 375397403Sobrien * [middle,last), and puts the result in [first,last). The output will 375497403Sobrien * be sorted. The sort is @e stable, that is, for equivalent 375597403Sobrien * elements in the two ranges, elements from the first range will always 375697403Sobrien * come before elements from the second. 375797403Sobrien * 375897403Sobrien * If enough additional memory is available, this takes (last-first)-1 375997403Sobrien * comparisons. Otherwise an NlogN algorithm is used, where N is 376097403Sobrien * distance(first,last). 376197403Sobrien * 376297403Sobrien * The comparison function should have the same effects on ordering as 376397403Sobrien * the function used for the initial sort. 376497403Sobrien */ 3765132720Skan template<typename _BidirectionalIterator, typename _Compare> 376697403Sobrien void 3767132720Skan inplace_merge(_BidirectionalIterator __first, 3768132720Skan _BidirectionalIterator __middle, 3769132720Skan _BidirectionalIterator __last, 377097403Sobrien _Compare __comp) 377197403Sobrien { 3772132720Skan typedef typename iterator_traits<_BidirectionalIterator>::value_type 377397403Sobrien _ValueType; 3774132720Skan typedef typename iterator_traits<_BidirectionalIterator>::difference_type 377597403Sobrien _DistanceType; 377697403Sobrien 377797403Sobrien // concept requirements 3778132720Skan __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 3779132720Skan _BidirectionalIterator>) 3780132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 378197403Sobrien _ValueType, _ValueType>) 3782132720Skan __glibcxx_requires_sorted_pred(__first, __middle, __comp); 3783132720Skan __glibcxx_requires_sorted_pred(__middle, __last, __comp); 378497403Sobrien 378597403Sobrien if (__first == __middle || __middle == __last) 378697403Sobrien return; 378797403Sobrien 3788132720Skan const _DistanceType __len1 = std::distance(__first, __middle); 3789132720Skan const _DistanceType __len2 = std::distance(__middle, __last); 379097403Sobrien 3791132720Skan _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, 3792132720Skan __last); 379397403Sobrien if (__buf.begin() == 0) 3794132720Skan std::__merge_without_buffer(__first, __middle, __last, __len1, 3795132720Skan __len2, __comp); 379697403Sobrien else 3797132720Skan std::__merge_adaptive(__first, __middle, __last, __len1, __len2, 3798132720Skan __buf.begin(), _DistanceType(__buf.size()), 3799132720Skan __comp); 380097403Sobrien } 380197403Sobrien 3802132720Skan template<typename _RandomAccessIterator, typename _Pointer, 3803132720Skan typename _Distance> 3804132720Skan void 3805132720Skan __stable_sort_adaptive(_RandomAccessIterator __first, 3806132720Skan _RandomAccessIterator __last, 3807132720Skan _Pointer __buffer, _Distance __buffer_size) 3808132720Skan { 3809132720Skan const _Distance __len = (__last - __first + 1) / 2; 3810132720Skan const _RandomAccessIterator __middle = __first + __len; 3811132720Skan if (__len > __buffer_size) 3812132720Skan { 3813132720Skan std::__stable_sort_adaptive(__first, __middle, 3814132720Skan __buffer, __buffer_size); 3815132720Skan std::__stable_sort_adaptive(__middle, __last, 3816132720Skan __buffer, __buffer_size); 3817132720Skan } 3818132720Skan else 3819132720Skan { 3820132720Skan std::__merge_sort_with_buffer(__first, __middle, __buffer); 3821132720Skan std::__merge_sort_with_buffer(__middle, __last, __buffer); 3822132720Skan } 3823132720Skan std::__merge_adaptive(__first, __middle, __last, 3824132720Skan _Distance(__middle - __first), 3825132720Skan _Distance(__last - __middle), 3826132720Skan __buffer, __buffer_size); 3827132720Skan } 3828132720Skan 3829132720Skan template<typename _RandomAccessIterator, typename _Pointer, 3830132720Skan typename _Distance, typename _Compare> 3831132720Skan void 3832132720Skan __stable_sort_adaptive(_RandomAccessIterator __first, 3833132720Skan _RandomAccessIterator __last, 3834132720Skan _Pointer __buffer, _Distance __buffer_size, 3835132720Skan _Compare __comp) 3836132720Skan { 3837132720Skan const _Distance __len = (__last - __first + 1) / 2; 3838132720Skan const _RandomAccessIterator __middle = __first + __len; 3839132720Skan if (__len > __buffer_size) 3840132720Skan { 3841132720Skan std::__stable_sort_adaptive(__first, __middle, __buffer, 3842132720Skan __buffer_size, __comp); 3843132720Skan std::__stable_sort_adaptive(__middle, __last, __buffer, 3844132720Skan __buffer_size, __comp); 3845132720Skan } 3846132720Skan else 3847132720Skan { 3848132720Skan std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); 3849132720Skan std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); 3850132720Skan } 3851132720Skan std::__merge_adaptive(__first, __middle, __last, 3852132720Skan _Distance(__middle - __first), 3853132720Skan _Distance(__last - __middle), 3854132720Skan __buffer, __buffer_size, 3855132720Skan __comp); 3856132720Skan } 3857132720Skan 3858132720Skan /** 3859132720Skan * @brief Sort the elements of a sequence, preserving the relative order 3860132720Skan * of equivalent elements. 3861132720Skan * @param first An iterator. 3862132720Skan * @param last Another iterator. 3863132720Skan * @return Nothing. 3864132720Skan * 3865132720Skan * Sorts the elements in the range @p [first,last) in ascending order, 3866132720Skan * such that @p *(i+1)<*i is false for each iterator @p i in the range 3867132720Skan * @p [first,last-1). 3868132720Skan * 3869132720Skan * The relative ordering of equivalent elements is preserved, so any two 3870132720Skan * elements @p x and @p y in the range @p [first,last) such that 3871132720Skan * @p x<y is false and @p y<x is false will have the same relative 3872132720Skan * ordering after calling @p stable_sort(). 3873132720Skan */ 3874132720Skan template<typename _RandomAccessIterator> 3875132720Skan inline void 3876132720Skan stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 3877132720Skan { 3878132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 3879132720Skan _ValueType; 3880132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3881132720Skan _DistanceType; 3882132720Skan 3883132720Skan // concept requirements 3884132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 3885132720Skan _RandomAccessIterator>) 3886132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 3887132720Skan __glibcxx_requires_valid_range(__first, __last); 3888132720Skan 3889169691Skan _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first, 3890169691Skan __last); 3891169691Skan if (__buf.begin() == 0) 3892132720Skan std::__inplace_stable_sort(__first, __last); 3893132720Skan else 3894169691Skan std::__stable_sort_adaptive(__first, __last, __buf.begin(), 3895169691Skan _DistanceType(__buf.size())); 3896132720Skan } 3897132720Skan 3898132720Skan /** 3899132720Skan * @brief Sort the elements of a sequence using a predicate for comparison, 3900132720Skan * preserving the relative order of equivalent elements. 3901132720Skan * @param first An iterator. 3902132720Skan * @param last Another iterator. 3903132720Skan * @param comp A comparison functor. 3904132720Skan * @return Nothing. 3905132720Skan * 3906132720Skan * Sorts the elements in the range @p [first,last) in ascending order, 3907132720Skan * such that @p comp(*(i+1),*i) is false for each iterator @p i in the 3908132720Skan * range @p [first,last-1). 3909132720Skan * 3910132720Skan * The relative ordering of equivalent elements is preserved, so any two 3911132720Skan * elements @p x and @p y in the range @p [first,last) such that 3912132720Skan * @p comp(x,y) is false and @p comp(y,x) is false will have the same 3913132720Skan * relative ordering after calling @p stable_sort(). 3914132720Skan */ 3915132720Skan template<typename _RandomAccessIterator, typename _Compare> 3916132720Skan inline void 3917132720Skan stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 3918132720Skan _Compare __comp) 3919132720Skan { 3920132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 3921132720Skan _ValueType; 3922132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3923132720Skan _DistanceType; 3924132720Skan 3925132720Skan // concept requirements 3926132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 3927132720Skan _RandomAccessIterator>) 3928132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3929132720Skan _ValueType, 3930132720Skan _ValueType>) 3931132720Skan __glibcxx_requires_valid_range(__first, __last); 3932132720Skan 3933169691Skan _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first, 3934169691Skan __last); 3935169691Skan if (__buf.begin() == 0) 3936132720Skan std::__inplace_stable_sort(__first, __last, __comp); 3937132720Skan else 3938169691Skan std::__stable_sort_adaptive(__first, __last, __buf.begin(), 3939169691Skan _DistanceType(__buf.size()), __comp); 3940132720Skan } 3941132720Skan 3942169691Skan 3943169691Skan template<typename _RandomAccessIterator, typename _Size> 3944169691Skan void 3945169691Skan __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, 3946169691Skan _RandomAccessIterator __last, _Size __depth_limit) 3947169691Skan { 3948169691Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 3949169691Skan _ValueType; 3950169691Skan 3951169691Skan while (__last - __first > 3) 3952169691Skan { 3953169691Skan if (__depth_limit == 0) 3954169691Skan { 3955169691Skan std::__heap_select(__first, __nth + 1, __last); 3956169691Skan // Place the nth largest element in its final position. 3957169691Skan std::iter_swap(__first, __nth); 3958169691Skan return; 3959169691Skan } 3960169691Skan --__depth_limit; 3961169691Skan _RandomAccessIterator __cut = 3962169691Skan std::__unguarded_partition(__first, __last, 3963169691Skan _ValueType(std::__median(*__first, 3964169691Skan *(__first 3965169691Skan + (__last 3966169691Skan - __first) 3967169691Skan / 2), 3968169691Skan *(__last 3969169691Skan - 1)))); 3970169691Skan if (__cut <= __nth) 3971169691Skan __first = __cut; 3972169691Skan else 3973169691Skan __last = __cut; 3974169691Skan } 3975169691Skan std::__insertion_sort(__first, __last); 3976169691Skan } 3977169691Skan 3978169691Skan template<typename _RandomAccessIterator, typename _Size, typename _Compare> 3979169691Skan void 3980169691Skan __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, 3981169691Skan _RandomAccessIterator __last, _Size __depth_limit, 3982169691Skan _Compare __comp) 3983169691Skan { 3984169691Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 3985169691Skan _ValueType; 3986169691Skan 3987169691Skan while (__last - __first > 3) 3988169691Skan { 3989169691Skan if (__depth_limit == 0) 3990169691Skan { 3991169691Skan std::__heap_select(__first, __nth + 1, __last, __comp); 3992169691Skan // Place the nth largest element in its final position. 3993169691Skan std::iter_swap(__first, __nth); 3994169691Skan return; 3995169691Skan } 3996169691Skan --__depth_limit; 3997169691Skan _RandomAccessIterator __cut = 3998169691Skan std::__unguarded_partition(__first, __last, 3999169691Skan _ValueType(std::__median(*__first, 4000169691Skan *(__first 4001169691Skan + (__last 4002169691Skan - __first) 4003169691Skan / 2), 4004169691Skan *(__last - 1), 4005169691Skan __comp)), 4006169691Skan __comp); 4007169691Skan if (__cut <= __nth) 4008169691Skan __first = __cut; 4009169691Skan else 4010169691Skan __last = __cut; 4011169691Skan } 4012169691Skan std::__insertion_sort(__first, __last, __comp); 4013169691Skan } 4014169691Skan 4015132720Skan /** 4016132720Skan * @brief Sort a sequence just enough to find a particular position. 4017132720Skan * @param first An iterator. 4018132720Skan * @param nth Another iterator. 4019132720Skan * @param last Another iterator. 4020132720Skan * @return Nothing. 4021132720Skan * 4022132720Skan * Rearranges the elements in the range @p [first,last) so that @p *nth 4023132720Skan * is the same element that would have been in that position had the 4024132720Skan * whole sequence been sorted. 4025132720Skan * whole sequence been sorted. The elements either side of @p *nth are 4026132720Skan * not completely sorted, but for any iterator @i in the range 4027132720Skan * @p [first,nth) and any iterator @j in the range @p [nth,last) it 4028132720Skan * holds that @p *j<*i is false. 4029132720Skan */ 4030132720Skan template<typename _RandomAccessIterator> 4031169691Skan inline void 4032169691Skan nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 4033132720Skan _RandomAccessIterator __last) 4034132720Skan { 4035132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 4036132720Skan _ValueType; 4037132720Skan 4038132720Skan // concept requirements 4039132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4040132720Skan _RandomAccessIterator>) 4041132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 4042132720Skan __glibcxx_requires_valid_range(__first, __nth); 4043132720Skan __glibcxx_requires_valid_range(__nth, __last); 4044132720Skan 4045169691Skan if (__first == __last || __nth == __last) 4046169691Skan return; 4047169691Skan 4048169691Skan std::__introselect(__first, __nth, __last, 4049169691Skan std::__lg(__last - __first) * 2); 4050132720Skan } 4051132720Skan 4052132720Skan /** 4053132720Skan * @brief Sort a sequence just enough to find a particular position 4054132720Skan * using a predicate for comparison. 4055132720Skan * @param first An iterator. 4056132720Skan * @param nth Another iterator. 4057132720Skan * @param last Another iterator. 4058132720Skan * @param comp A comparison functor. 4059132720Skan * @return Nothing. 4060132720Skan * 4061132720Skan * Rearranges the elements in the range @p [first,last) so that @p *nth 4062132720Skan * is the same element that would have been in that position had the 4063132720Skan * whole sequence been sorted. The elements either side of @p *nth are 4064132720Skan * not completely sorted, but for any iterator @i in the range 4065132720Skan * @p [first,nth) and any iterator @j in the range @p [nth,last) it 4066132720Skan * holds that @p comp(*j,*i) is false. 4067132720Skan */ 4068132720Skan template<typename _RandomAccessIterator, typename _Compare> 4069169691Skan inline void 4070169691Skan nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 4071169691Skan _RandomAccessIterator __last, _Compare __comp) 4072132720Skan { 4073132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 4074132720Skan _ValueType; 4075132720Skan 4076132720Skan // concept requirements 4077132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4078132720Skan _RandomAccessIterator>) 4079132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4080132720Skan _ValueType, _ValueType>) 4081132720Skan __glibcxx_requires_valid_range(__first, __nth); 4082132720Skan __glibcxx_requires_valid_range(__nth, __last); 4083132720Skan 4084169691Skan if (__first == __last || __nth == __last) 4085169691Skan return; 4086169691Skan 4087169691Skan std::__introselect(__first, __nth, __last, 4088169691Skan std::__lg(__last - __first) * 2, __comp); 4089132720Skan } 4090132720Skan 4091132720Skan /** 4092132720Skan * @brief Finds the largest subrange in which @a val could be inserted 4093132720Skan * at any place in it without changing the ordering. 4094132720Skan * @param first An iterator. 4095132720Skan * @param last Another iterator. 4096132720Skan * @param val The search term. 4097132720Skan * @return An pair of iterators defining the subrange. 4098132720Skan * @ingroup binarysearch 4099132720Skan * 4100132720Skan * This is equivalent to 4101132720Skan * @code 4102132720Skan * std::make_pair(lower_bound(first, last, val), 4103132720Skan * upper_bound(first, last, val)) 4104132720Skan * @endcode 4105132720Skan * but does not actually call those functions. 4106132720Skan */ 4107132720Skan template<typename _ForwardIterator, typename _Tp> 4108132720Skan pair<_ForwardIterator, _ForwardIterator> 4109132720Skan equal_range(_ForwardIterator __first, _ForwardIterator __last, 4110132720Skan const _Tp& __val) 4111132720Skan { 4112132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 4113132720Skan _ValueType; 4114132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 4115132720Skan _DistanceType; 4116132720Skan 4117132720Skan // concept requirements 4118132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4119169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) 4120169691Skan __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) 4121132720Skan __glibcxx_requires_partitioned(__first, __last, __val); 4122132720Skan 4123132720Skan _DistanceType __len = std::distance(__first, __last); 4124132720Skan _DistanceType __half; 4125132720Skan _ForwardIterator __middle, __left, __right; 4126132720Skan 4127132720Skan while (__len > 0) 4128132720Skan { 4129132720Skan __half = __len >> 1; 4130132720Skan __middle = __first; 4131132720Skan std::advance(__middle, __half); 4132132720Skan if (*__middle < __val) 4133132720Skan { 4134132720Skan __first = __middle; 4135132720Skan ++__first; 4136132720Skan __len = __len - __half - 1; 4137132720Skan } 4138132720Skan else if (__val < *__middle) 4139132720Skan __len = __half; 4140132720Skan else 4141132720Skan { 4142132720Skan __left = std::lower_bound(__first, __middle, __val); 4143132720Skan std::advance(__first, __len); 4144132720Skan __right = std::upper_bound(++__middle, __first, __val); 4145132720Skan return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 4146132720Skan } 4147132720Skan } 4148132720Skan return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 4149132720Skan } 4150132720Skan 4151132720Skan /** 4152132720Skan * @brief Finds the largest subrange in which @a val could be inserted 4153132720Skan * at any place in it without changing the ordering. 4154132720Skan * @param first An iterator. 4155132720Skan * @param last Another iterator. 4156132720Skan * @param val The search term. 4157132720Skan * @param comp A functor to use for comparisons. 4158132720Skan * @return An pair of iterators defining the subrange. 4159132720Skan * @ingroup binarysearch 4160132720Skan * 4161132720Skan * This is equivalent to 4162132720Skan * @code 4163132720Skan * std::make_pair(lower_bound(first, last, val, comp), 4164132720Skan * upper_bound(first, last, val, comp)) 4165132720Skan * @endcode 4166132720Skan * but does not actually call those functions. 4167132720Skan */ 4168132720Skan template<typename _ForwardIterator, typename _Tp, typename _Compare> 4169132720Skan pair<_ForwardIterator, _ForwardIterator> 4170132720Skan equal_range(_ForwardIterator __first, _ForwardIterator __last, 4171132720Skan const _Tp& __val, 4172132720Skan _Compare __comp) 4173132720Skan { 4174132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 4175132720Skan _ValueType; 4176132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 4177132720Skan _DistanceType; 4178132720Skan 4179132720Skan // concept requirements 4180132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4181132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4182132720Skan _ValueType, _Tp>) 4183132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4184132720Skan _Tp, _ValueType>) 4185132720Skan __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 4186132720Skan 4187132720Skan _DistanceType __len = std::distance(__first, __last); 4188132720Skan _DistanceType __half; 4189132720Skan _ForwardIterator __middle, __left, __right; 4190132720Skan 4191132720Skan while (__len > 0) 4192132720Skan { 4193132720Skan __half = __len >> 1; 4194132720Skan __middle = __first; 4195132720Skan std::advance(__middle, __half); 4196132720Skan if (__comp(*__middle, __val)) 4197132720Skan { 4198132720Skan __first = __middle; 4199132720Skan ++__first; 4200132720Skan __len = __len - __half - 1; 4201132720Skan } 4202132720Skan else if (__comp(__val, *__middle)) 4203132720Skan __len = __half; 4204132720Skan else 4205132720Skan { 4206132720Skan __left = std::lower_bound(__first, __middle, __val, __comp); 4207132720Skan std::advance(__first, __len); 4208132720Skan __right = std::upper_bound(++__middle, __first, __val, __comp); 4209132720Skan return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 4210132720Skan } 4211132720Skan } 4212132720Skan return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 4213132720Skan } 4214132720Skan 4215132720Skan /** 4216132720Skan * @brief Determines whether an element exists in a range. 4217132720Skan * @param first An iterator. 4218132720Skan * @param last Another iterator. 4219132720Skan * @param val The search term. 4220132720Skan * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 4221132720Skan * @ingroup binarysearch 4222132720Skan * 4223132720Skan * Note that this does not actually return an iterator to @a val. For 4224132720Skan * that, use std::find or a container's specialized find member functions. 4225132720Skan */ 4226132720Skan template<typename _ForwardIterator, typename _Tp> 4227132720Skan bool 4228132720Skan binary_search(_ForwardIterator __first, _ForwardIterator __last, 4229132720Skan const _Tp& __val) 4230132720Skan { 4231169691Skan typedef typename iterator_traits<_ForwardIterator>::value_type 4232169691Skan _ValueType; 4233169691Skan 4234132720Skan // concept requirements 4235132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4236169691Skan __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) 4237132720Skan __glibcxx_requires_partitioned(__first, __last, __val); 4238132720Skan 4239132720Skan _ForwardIterator __i = std::lower_bound(__first, __last, __val); 4240132720Skan return __i != __last && !(__val < *__i); 4241132720Skan } 4242132720Skan 4243132720Skan /** 4244132720Skan * @brief Determines whether an element exists in a range. 4245132720Skan * @param first An iterator. 4246132720Skan * @param last Another iterator. 4247132720Skan * @param val The search term. 4248132720Skan * @param comp A functor to use for comparisons. 4249132720Skan * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 4250132720Skan * @ingroup binarysearch 4251132720Skan * 4252132720Skan * Note that this does not actually return an iterator to @a val. For 4253132720Skan * that, use std::find or a container's specialized find member functions. 4254132720Skan * 4255132720Skan * The comparison function should have the same effects on ordering as 4256132720Skan * the function used for the initial sort. 4257132720Skan */ 4258132720Skan template<typename _ForwardIterator, typename _Tp, typename _Compare> 4259132720Skan bool 4260132720Skan binary_search(_ForwardIterator __first, _ForwardIterator __last, 4261132720Skan const _Tp& __val, _Compare __comp) 4262132720Skan { 4263169691Skan typedef typename iterator_traits<_ForwardIterator>::value_type 4264169691Skan _ValueType; 4265169691Skan 4266132720Skan // concept requirements 4267132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4268132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4269169691Skan _Tp, _ValueType>) 4270132720Skan __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 4271132720Skan 4272132720Skan _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp); 4273132720Skan return __i != __last && !__comp(__val, *__i); 4274132720Skan } 4275132720Skan 427697403Sobrien // Set algorithms: includes, set_union, set_intersection, set_difference, 427797403Sobrien // set_symmetric_difference. All of these algorithms have the precondition 427897403Sobrien // that their input ranges are sorted and the postcondition that their output 427997403Sobrien // ranges are sorted. 428097403Sobrien 4281132720Skan /** 4282132720Skan * @brief Determines whether all elements of a sequence exists in a range. 4283132720Skan * @param first1 Start of search range. 4284132720Skan * @param last1 End of search range. 4285132720Skan * @param first2 Start of sequence 4286132720Skan * @param last2 End of sequence. 4287132720Skan * @return True if each element in [first2,last2) is contained in order 4288132720Skan * within [first1,last1). False otherwise. 4289132720Skan * @ingroup setoperations 4290132720Skan * 4291132720Skan * This operation expects both [first1,last1) and [first2,last2) to be 4292132720Skan * sorted. Searches for the presence of each element in [first2,last2) 4293132720Skan * within [first1,last1). The iterators over each range only move forward, 4294132720Skan * so this is a linear algorithm. If an element in [first2,last2) is not 4295132720Skan * found before the search iterator reaches @a last2, false is returned. 4296132720Skan */ 4297132720Skan template<typename _InputIterator1, typename _InputIterator2> 429897403Sobrien bool 4299132720Skan includes(_InputIterator1 __first1, _InputIterator1 __last1, 4300132720Skan _InputIterator2 __first2, _InputIterator2 __last2) 430197403Sobrien { 4302169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 4303169691Skan _ValueType1; 4304169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 4305169691Skan _ValueType2; 4306169691Skan 430797403Sobrien // concept requirements 4308132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4309132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4310169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 4311169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 4312132720Skan __glibcxx_requires_sorted(__first1, __last1); 4313132720Skan __glibcxx_requires_sorted(__first2, __last2); 431497403Sobrien 431597403Sobrien while (__first1 != __last1 && __first2 != __last2) 431697403Sobrien if (*__first2 < *__first1) 431797403Sobrien return false; 431897403Sobrien else if(*__first1 < *__first2) 431997403Sobrien ++__first1; 432097403Sobrien else 432197403Sobrien ++__first1, ++__first2; 432297403Sobrien 432397403Sobrien return __first2 == __last2; 432497403Sobrien } 432597403Sobrien 4326132720Skan /** 4327132720Skan * @brief Determines whether all elements of a sequence exists in a range 4328132720Skan * using comparison. 4329132720Skan * @param first1 Start of search range. 4330132720Skan * @param last1 End of search range. 4331132720Skan * @param first2 Start of sequence 4332132720Skan * @param last2 End of sequence. 4333132720Skan * @param comp Comparison function to use. 4334132720Skan * @return True if each element in [first2,last2) is contained in order 4335132720Skan * within [first1,last1) according to comp. False otherwise. 4336132720Skan * @ingroup setoperations 4337132720Skan * 4338132720Skan * This operation expects both [first1,last1) and [first2,last2) to be 4339132720Skan * sorted. Searches for the presence of each element in [first2,last2) 4340132720Skan * within [first1,last1), using comp to decide. The iterators over each 4341132720Skan * range only move forward, so this is a linear algorithm. If an element 4342132720Skan * in [first2,last2) is not found before the search iterator reaches @a 4343132720Skan * last2, false is returned. 4344132720Skan */ 4345132720Skan template<typename _InputIterator1, typename _InputIterator2, 4346132720Skan typename _Compare> 434797403Sobrien bool 4348132720Skan includes(_InputIterator1 __first1, _InputIterator1 __last1, 4349132720Skan _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 435097403Sobrien { 4351169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 4352169691Skan _ValueType1; 4353169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 4354169691Skan _ValueType2; 4355169691Skan 435697403Sobrien // concept requirements 4357132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4358132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4359132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4360169691Skan _ValueType1, _ValueType2>) 4361169691Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4362169691Skan _ValueType2, _ValueType1>) 4363132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 4364132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 436597403Sobrien 436697403Sobrien while (__first1 != __last1 && __first2 != __last2) 436797403Sobrien if (__comp(*__first2, *__first1)) 436897403Sobrien return false; 436997403Sobrien else if(__comp(*__first1, *__first2)) 437097403Sobrien ++__first1; 437197403Sobrien else 437297403Sobrien ++__first1, ++__first2; 437397403Sobrien 437497403Sobrien return __first2 == __last2; 437597403Sobrien } 437697403Sobrien 4377132720Skan /** 4378132720Skan * @brief Return the union of two sorted ranges. 4379132720Skan * @param first1 Start of first range. 4380132720Skan * @param last1 End of first range. 4381132720Skan * @param first2 Start of second range. 4382132720Skan * @param last2 End of second range. 4383132720Skan * @return End of the output range. 4384132720Skan * @ingroup setoperations 4385132720Skan * 4386132720Skan * This operation iterates over both ranges, copying elements present in 4387132720Skan * each range in order to the output range. Iterators increment for each 4388132720Skan * range. When the current element of one range is less than the other, 4389132720Skan * that element is copied and the iterator advanced. If an element is 4390132720Skan * contained in both ranges, the element from the first range is copied and 4391132720Skan * both ranges advance. The output range may not overlap either input 4392132720Skan * range. 4393132720Skan */ 4394132720Skan template<typename _InputIterator1, typename _InputIterator2, 4395132720Skan typename _OutputIterator> 4396132720Skan _OutputIterator 4397132720Skan set_union(_InputIterator1 __first1, _InputIterator1 __last1, 4398132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4399132720Skan _OutputIterator __result) 440097403Sobrien { 4401169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 4402169691Skan _ValueType1; 4403169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 4404169691Skan _ValueType2; 4405169691Skan 440697403Sobrien // concept requirements 4407132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4408132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4409132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4410169691Skan _ValueType1>) 4411169691Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4412169691Skan _ValueType2>) 4413169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 4414169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 4415132720Skan __glibcxx_requires_sorted(__first1, __last1); 4416132720Skan __glibcxx_requires_sorted(__first2, __last2); 441797403Sobrien 4418132720Skan while (__first1 != __last1 && __first2 != __last2) 4419132720Skan { 4420132720Skan if (*__first1 < *__first2) 4421132720Skan { 4422132720Skan *__result = *__first1; 4423132720Skan ++__first1; 4424132720Skan } 4425132720Skan else if (*__first2 < *__first1) 4426132720Skan { 4427132720Skan *__result = *__first2; 4428132720Skan ++__first2; 4429132720Skan } 4430132720Skan else 4431132720Skan { 4432132720Skan *__result = *__first1; 4433132720Skan ++__first1; 4434132720Skan ++__first2; 4435132720Skan } 4436132720Skan ++__result; 443797403Sobrien } 4438132720Skan return std::copy(__first2, __last2, std::copy(__first1, __last1, 4439132720Skan __result)); 444097403Sobrien } 444197403Sobrien 4442132720Skan /** 4443132720Skan * @brief Return the union of two sorted ranges using a comparison functor. 4444132720Skan * @param first1 Start of first range. 4445132720Skan * @param last1 End of first range. 4446132720Skan * @param first2 Start of second range. 4447132720Skan * @param last2 End of second range. 4448132720Skan * @param comp The comparison functor. 4449132720Skan * @return End of the output range. 4450132720Skan * @ingroup setoperations 4451132720Skan * 4452132720Skan * This operation iterates over both ranges, copying elements present in 4453132720Skan * each range in order to the output range. Iterators increment for each 4454132720Skan * range. When the current element of one range is less than the other 4455132720Skan * according to @a comp, that element is copied and the iterator advanced. 4456132720Skan * If an equivalent element according to @a comp is contained in both 4457132720Skan * ranges, the element from the first range is copied and both ranges 4458132720Skan * advance. The output range may not overlap either input range. 4459132720Skan */ 4460132720Skan template<typename _InputIterator1, typename _InputIterator2, 4461132720Skan typename _OutputIterator, typename _Compare> 4462132720Skan _OutputIterator 4463132720Skan set_union(_InputIterator1 __first1, _InputIterator1 __last1, 4464132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4465132720Skan _OutputIterator __result, _Compare __comp) 446697403Sobrien { 4467169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 4468169691Skan _ValueType1; 4469169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 4470169691Skan _ValueType2; 4471169691Skan 447297403Sobrien // concept requirements 4473132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4474132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4475132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4476169691Skan _ValueType1>) 4477169691Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4478169691Skan _ValueType2>) 4479132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4480169691Skan _ValueType1, _ValueType2>) 4481169691Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4482169691Skan _ValueType2, _ValueType1>) 4483132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 4484132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 448597403Sobrien 4486132720Skan while (__first1 != __last1 && __first2 != __last2) 4487132720Skan { 4488132720Skan if (__comp(*__first1, *__first2)) 4489132720Skan { 4490132720Skan *__result = *__first1; 4491132720Skan ++__first1; 4492132720Skan } 4493132720Skan else if (__comp(*__first2, *__first1)) 4494132720Skan { 4495132720Skan *__result = *__first2; 4496132720Skan ++__first2; 4497132720Skan } 4498132720Skan else 4499132720Skan { 4500132720Skan *__result = *__first1; 4501132720Skan ++__first1; 4502132720Skan ++__first2; 4503132720Skan } 4504132720Skan ++__result; 450597403Sobrien } 4506132720Skan return std::copy(__first2, __last2, std::copy(__first1, __last1, 4507132720Skan __result)); 450897403Sobrien } 450997403Sobrien 4510132720Skan /** 4511132720Skan * @brief Return the intersection of two sorted ranges. 4512132720Skan * @param first1 Start of first range. 4513132720Skan * @param last1 End of first range. 4514132720Skan * @param first2 Start of second range. 4515132720Skan * @param last2 End of second range. 4516132720Skan * @return End of the output range. 4517132720Skan * @ingroup setoperations 4518132720Skan * 4519132720Skan * This operation iterates over both ranges, copying elements present in 4520132720Skan * both ranges in order to the output range. Iterators increment for each 4521132720Skan * range. When the current element of one range is less than the other, 4522132720Skan * that iterator advances. If an element is contained in both ranges, the 4523132720Skan * element from the first range is copied and both ranges advance. The 4524132720Skan * output range may not overlap either input range. 4525132720Skan */ 4526132720Skan template<typename _InputIterator1, typename _InputIterator2, 4527132720Skan typename _OutputIterator> 4528132720Skan _OutputIterator 4529132720Skan set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 4530132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4531132720Skan _OutputIterator __result) 453297403Sobrien { 4533169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 4534169691Skan _ValueType1; 4535169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 4536169691Skan _ValueType2; 4537169691Skan 453897403Sobrien // concept requirements 4539132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4540132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4541132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4542169691Skan _ValueType1>) 4543169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 4544169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 4545132720Skan __glibcxx_requires_sorted(__first1, __last1); 4546132720Skan __glibcxx_requires_sorted(__first2, __last2); 454797403Sobrien 454897403Sobrien while (__first1 != __last1 && __first2 != __last2) 454997403Sobrien if (*__first1 < *__first2) 455097403Sobrien ++__first1; 455197403Sobrien else if (*__first2 < *__first1) 455297403Sobrien ++__first2; 4553132720Skan else 4554132720Skan { 4555132720Skan *__result = *__first1; 4556132720Skan ++__first1; 4557132720Skan ++__first2; 4558132720Skan ++__result; 4559132720Skan } 456097403Sobrien return __result; 456197403Sobrien } 456297403Sobrien 4563132720Skan /** 4564132720Skan * @brief Return the intersection of two sorted ranges using comparison 4565132720Skan * functor. 4566132720Skan * @param first1 Start of first range. 4567132720Skan * @param last1 End of first range. 4568132720Skan * @param first2 Start of second range. 4569132720Skan * @param last2 End of second range. 4570132720Skan * @param comp The comparison functor. 4571132720Skan * @return End of the output range. 4572132720Skan * @ingroup setoperations 4573132720Skan * 4574132720Skan * This operation iterates over both ranges, copying elements present in 4575132720Skan * both ranges in order to the output range. Iterators increment for each 4576132720Skan * range. When the current element of one range is less than the other 4577132720Skan * according to @a comp, that iterator advances. If an element is 4578132720Skan * contained in both ranges according to @a comp, the element from the 4579132720Skan * first range is copied and both ranges advance. The output range may not 4580132720Skan * overlap either input range. 4581132720Skan */ 4582132720Skan template<typename _InputIterator1, typename _InputIterator2, 4583132720Skan typename _OutputIterator, typename _Compare> 4584132720Skan _OutputIterator 4585132720Skan set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 4586132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4587132720Skan _OutputIterator __result, _Compare __comp) 458897403Sobrien { 4589169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 4590169691Skan _ValueType1; 4591169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 4592169691Skan _ValueType2; 4593169691Skan 459497403Sobrien // concept requirements 4595132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4596132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4597132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4598169691Skan _ValueType1>) 4599132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4600169691Skan _ValueType1, _ValueType2>) 4601169691Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4602169691Skan _ValueType2, _ValueType1>) 4603132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 4604132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 460597403Sobrien 460697403Sobrien while (__first1 != __last1 && __first2 != __last2) 460797403Sobrien if (__comp(*__first1, *__first2)) 460897403Sobrien ++__first1; 460997403Sobrien else if (__comp(*__first2, *__first1)) 461097403Sobrien ++__first2; 4611132720Skan else 4612132720Skan { 4613132720Skan *__result = *__first1; 4614132720Skan ++__first1; 4615132720Skan ++__first2; 4616132720Skan ++__result; 4617132720Skan } 461897403Sobrien return __result; 461997403Sobrien } 462097403Sobrien 4621132720Skan /** 4622132720Skan * @brief Return the difference of two sorted ranges. 4623132720Skan * @param first1 Start of first range. 4624132720Skan * @param last1 End of first range. 4625132720Skan * @param first2 Start of second range. 4626132720Skan * @param last2 End of second range. 4627132720Skan * @return End of the output range. 4628132720Skan * @ingroup setoperations 4629132720Skan * 4630132720Skan * This operation iterates over both ranges, copying elements present in 4631132720Skan * the first range but not the second in order to the output range. 4632132720Skan * Iterators increment for each range. When the current element of the 4633132720Skan * first range is less than the second, that element is copied and the 4634132720Skan * iterator advances. If the current element of the second range is less, 4635132720Skan * the iterator advances, but no element is copied. If an element is 4636132720Skan * contained in both ranges, no elements are copied and both ranges 4637132720Skan * advance. The output range may not overlap either input range. 4638132720Skan */ 4639132720Skan template<typename _InputIterator1, typename _InputIterator2, 4640132720Skan typename _OutputIterator> 4641132720Skan _OutputIterator 4642132720Skan set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 4643132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4644132720Skan _OutputIterator __result) 464597403Sobrien { 4646169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 4647169691Skan _ValueType1; 4648169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 4649169691Skan _ValueType2; 4650169691Skan 465197403Sobrien // concept requirements 4652132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4653132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4654132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4655169691Skan _ValueType1>) 4656169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 4657169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 4658132720Skan __glibcxx_requires_sorted(__first1, __last1); 4659132720Skan __glibcxx_requires_sorted(__first2, __last2); 466097403Sobrien 466197403Sobrien while (__first1 != __last1 && __first2 != __last2) 4662132720Skan if (*__first1 < *__first2) 4663132720Skan { 4664132720Skan *__result = *__first1; 4665132720Skan ++__first1; 4666132720Skan ++__result; 4667132720Skan } 466897403Sobrien else if (*__first2 < *__first1) 466997403Sobrien ++__first2; 4670132720Skan else 4671132720Skan { 4672132720Skan ++__first1; 4673132720Skan ++__first2; 4674132720Skan } 4675132720Skan return std::copy(__first1, __last1, __result); 467697403Sobrien } 467797403Sobrien 4678132720Skan /** 4679132720Skan * @brief Return the difference of two sorted ranges using comparison 4680132720Skan * functor. 4681132720Skan * @param first1 Start of first range. 4682132720Skan * @param last1 End of first range. 4683132720Skan * @param first2 Start of second range. 4684132720Skan * @param last2 End of second range. 4685132720Skan * @param comp The comparison functor. 4686132720Skan * @return End of the output range. 4687132720Skan * @ingroup setoperations 4688132720Skan * 4689132720Skan * This operation iterates over both ranges, copying elements present in 4690132720Skan * the first range but not the second in order to the output range. 4691132720Skan * Iterators increment for each range. When the current element of the 4692132720Skan * first range is less than the second according to @a comp, that element 4693132720Skan * is copied and the iterator advances. If the current element of the 4694132720Skan * second range is less, no element is copied and the iterator advances. 4695132720Skan * If an element is contained in both ranges according to @a comp, no 4696132720Skan * elements are copied and both ranges advance. The output range may not 4697132720Skan * overlap either input range. 4698132720Skan */ 4699132720Skan template<typename _InputIterator1, typename _InputIterator2, 4700132720Skan typename _OutputIterator, typename _Compare> 4701132720Skan _OutputIterator 4702132720Skan set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 4703132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4704132720Skan _OutputIterator __result, _Compare __comp) 470597403Sobrien { 4706169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 4707169691Skan _ValueType1; 4708169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 4709169691Skan _ValueType2; 4710169691Skan 471197403Sobrien // concept requirements 4712132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4713132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4714132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4715169691Skan _ValueType1>) 4716132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4717169691Skan _ValueType1, _ValueType2>) 4718169691Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4719169691Skan _ValueType2, _ValueType1>) 4720132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 4721132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 472297403Sobrien 472397403Sobrien while (__first1 != __last1 && __first2 != __last2) 4724132720Skan if (__comp(*__first1, *__first2)) 4725132720Skan { 4726132720Skan *__result = *__first1; 4727132720Skan ++__first1; 4728132720Skan ++__result; 4729132720Skan } 473097403Sobrien else if (__comp(*__first2, *__first1)) 473197403Sobrien ++__first2; 4732132720Skan else 4733132720Skan { 4734132720Skan ++__first1; 4735132720Skan ++__first2; 4736132720Skan } 4737132720Skan return std::copy(__first1, __last1, __result); 473897403Sobrien } 473997403Sobrien 4740132720Skan /** 4741132720Skan * @brief Return the symmetric difference of two sorted ranges. 4742132720Skan * @param first1 Start of first range. 4743132720Skan * @param last1 End of first range. 4744132720Skan * @param first2 Start of second range. 4745132720Skan * @param last2 End of second range. 4746132720Skan * @return End of the output range. 4747132720Skan * @ingroup setoperations 4748132720Skan * 4749132720Skan * This operation iterates over both ranges, copying elements present in 4750132720Skan * one range but not the other in order to the output range. Iterators 4751132720Skan * increment for each range. When the current element of one range is less 4752132720Skan * than the other, that element is copied and the iterator advances. If an 4753132720Skan * element is contained in both ranges, no elements are copied and both 4754132720Skan * ranges advance. The output range may not overlap either input range. 4755132720Skan */ 4756132720Skan template<typename _InputIterator1, typename _InputIterator2, 4757132720Skan typename _OutputIterator> 4758132720Skan _OutputIterator 4759132720Skan set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 4760132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4761132720Skan _OutputIterator __result) 476297403Sobrien { 4763169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 4764169691Skan _ValueType1; 4765169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 4766169691Skan _ValueType2; 4767169691Skan 476897403Sobrien // concept requirements 4769132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4770132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4771132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4772169691Skan _ValueType1>) 4773169691Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4774169691Skan _ValueType2>) 4775169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 4776169691Skan __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 4777132720Skan __glibcxx_requires_sorted(__first1, __last1); 4778132720Skan __glibcxx_requires_sorted(__first2, __last2); 477997403Sobrien 478097403Sobrien while (__first1 != __last1 && __first2 != __last2) 4781132720Skan if (*__first1 < *__first2) 4782132720Skan { 4783132720Skan *__result = *__first1; 4784132720Skan ++__first1; 4785132720Skan ++__result; 4786132720Skan } 4787132720Skan else if (*__first2 < *__first1) 4788132720Skan { 4789132720Skan *__result = *__first2; 4790132720Skan ++__first2; 4791132720Skan ++__result; 4792132720Skan } 4793132720Skan else 4794132720Skan { 4795132720Skan ++__first1; 4796132720Skan ++__first2; 4797132720Skan } 4798132720Skan return std::copy(__first2, __last2, std::copy(__first1, 4799132720Skan __last1, __result)); 480097403Sobrien } 480197403Sobrien 4802132720Skan /** 4803132720Skan * @brief Return the symmetric difference of two sorted ranges using 4804132720Skan * comparison functor. 4805132720Skan * @param first1 Start of first range. 4806132720Skan * @param last1 End of first range. 4807132720Skan * @param first2 Start of second range. 4808132720Skan * @param last2 End of second range. 4809132720Skan * @param comp The comparison functor. 4810132720Skan * @return End of the output range. 4811132720Skan * @ingroup setoperations 4812132720Skan * 4813132720Skan * This operation iterates over both ranges, copying elements present in 4814132720Skan * one range but not the other in order to the output range. Iterators 4815132720Skan * increment for each range. When the current element of one range is less 4816132720Skan * than the other according to @a comp, that element is copied and the 4817132720Skan * iterator advances. If an element is contained in both ranges according 4818132720Skan * to @a comp, no elements are copied and both ranges advance. The output 4819132720Skan * range may not overlap either input range. 4820132720Skan */ 4821132720Skan template<typename _InputIterator1, typename _InputIterator2, 4822132720Skan typename _OutputIterator, typename _Compare> 4823132720Skan _OutputIterator 4824132720Skan set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 4825132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4826132720Skan _OutputIterator __result, 482797403Sobrien _Compare __comp) 482897403Sobrien { 4829169691Skan typedef typename iterator_traits<_InputIterator1>::value_type 4830169691Skan _ValueType1; 4831169691Skan typedef typename iterator_traits<_InputIterator2>::value_type 4832169691Skan _ValueType2; 4833169691Skan 483497403Sobrien // concept requirements 4835132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4836132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4837132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4838169691Skan _ValueType1>) 4839169691Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4840169691Skan _ValueType2>) 4841132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4842169691Skan _ValueType1, _ValueType2>) 4843169691Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4844169691Skan _ValueType2, _ValueType1>) 4845132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 4846132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 484797403Sobrien 484897403Sobrien while (__first1 != __last1 && __first2 != __last2) 4849132720Skan if (__comp(*__first1, *__first2)) 4850132720Skan { 4851132720Skan *__result = *__first1; 4852132720Skan ++__first1; 4853132720Skan ++__result; 4854132720Skan } 4855132720Skan else if (__comp(*__first2, *__first1)) 4856132720Skan { 4857132720Skan *__result = *__first2; 4858132720Skan ++__first2; 4859132720Skan ++__result; 4860132720Skan } 4861132720Skan else 4862132720Skan { 4863132720Skan ++__first1; 4864132720Skan ++__first2; 4865132720Skan } 4866132720Skan return std::copy(__first2, __last2, std::copy(__first1, 4867132720Skan __last1, __result)); 486897403Sobrien } 486997403Sobrien 487097403Sobrien // min_element and max_element, with and without an explicitly supplied 487197403Sobrien // comparison function. 487297403Sobrien 4873132720Skan /** 4874132720Skan * @brief Return the maximum element in a range. 4875132720Skan * @param first Start of range. 4876132720Skan * @param last End of range. 4877132720Skan * @return Iterator referencing the first instance of the largest value. 4878132720Skan */ 4879132720Skan template<typename _ForwardIterator> 4880132720Skan _ForwardIterator 4881132720Skan max_element(_ForwardIterator __first, _ForwardIterator __last) 488297403Sobrien { 488397403Sobrien // concept requirements 4884132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4885132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 4886132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 4887132720Skan __glibcxx_requires_valid_range(__first, __last); 488897403Sobrien 4889132720Skan if (__first == __last) 4890132720Skan return __first; 4891132720Skan _ForwardIterator __result = __first; 489297403Sobrien while (++__first != __last) 489397403Sobrien if (*__result < *__first) 489497403Sobrien __result = __first; 489597403Sobrien return __result; 489697403Sobrien } 489797403Sobrien 4898132720Skan /** 4899132720Skan * @brief Return the maximum element in a range using comparison functor. 4900132720Skan * @param first Start of range. 4901132720Skan * @param last End of range. 4902132720Skan * @param comp Comparison functor. 4903132720Skan * @return Iterator referencing the first instance of the largest value 4904132720Skan * according to comp. 4905132720Skan */ 4906132720Skan template<typename _ForwardIterator, typename _Compare> 4907132720Skan _ForwardIterator 4908132720Skan max_element(_ForwardIterator __first, _ForwardIterator __last, 490997403Sobrien _Compare __comp) 491097403Sobrien { 491197403Sobrien // concept requirements 4912132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4913132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4914132720Skan typename iterator_traits<_ForwardIterator>::value_type, 4915132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 4916132720Skan __glibcxx_requires_valid_range(__first, __last); 491797403Sobrien 491897403Sobrien if (__first == __last) return __first; 4919132720Skan _ForwardIterator __result = __first; 492097403Sobrien while (++__first != __last) 492197403Sobrien if (__comp(*__result, *__first)) __result = __first; 492297403Sobrien return __result; 492397403Sobrien } 492497403Sobrien 4925132720Skan /** 4926132720Skan * @brief Return the minimum element in a range. 4927132720Skan * @param first Start of range. 4928132720Skan * @param last End of range. 4929132720Skan * @return Iterator referencing the first instance of the smallest value. 4930132720Skan */ 4931132720Skan template<typename _ForwardIterator> 4932132720Skan _ForwardIterator 4933132720Skan min_element(_ForwardIterator __first, _ForwardIterator __last) 493497403Sobrien { 493597403Sobrien // concept requirements 4936132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4937132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 4938132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 4939132720Skan __glibcxx_requires_valid_range(__first, __last); 494097403Sobrien 4941132720Skan if (__first == __last) 4942132720Skan return __first; 4943132720Skan _ForwardIterator __result = __first; 494497403Sobrien while (++__first != __last) 494597403Sobrien if (*__first < *__result) 494697403Sobrien __result = __first; 494797403Sobrien return __result; 494897403Sobrien } 494997403Sobrien 4950132720Skan /** 4951132720Skan * @brief Return the minimum element in a range using comparison functor. 4952132720Skan * @param first Start of range. 4953132720Skan * @param last End of range. 4954132720Skan * @param comp Comparison functor. 4955132720Skan * @return Iterator referencing the first instance of the smallest value 4956132720Skan * according to comp. 4957132720Skan */ 4958132720Skan template<typename _ForwardIterator, typename _Compare> 4959132720Skan _ForwardIterator 4960132720Skan min_element(_ForwardIterator __first, _ForwardIterator __last, 496197403Sobrien _Compare __comp) 496297403Sobrien { 496397403Sobrien // concept requirements 4964132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4965132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4966132720Skan typename iterator_traits<_ForwardIterator>::value_type, 4967132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 4968132720Skan __glibcxx_requires_valid_range(__first, __last); 496997403Sobrien 4970132720Skan if (__first == __last) 4971132720Skan return __first; 4972132720Skan _ForwardIterator __result = __first; 497397403Sobrien while (++__first != __last) 497497403Sobrien if (__comp(*__first, *__result)) 497597403Sobrien __result = __first; 497697403Sobrien return __result; 497797403Sobrien } 497897403Sobrien 497997403Sobrien // next_permutation and prev_permutation, with and without an explicitly 498097403Sobrien // supplied comparison function. 498197403Sobrien 4982132720Skan /** 4983132720Skan * @brief Permute range into the next "dictionary" ordering. 4984132720Skan * @param first Start of range. 4985132720Skan * @param last End of range. 4986132720Skan * @return False if wrapped to first permutation, true otherwise. 4987132720Skan * 4988132720Skan * Treats all permutations of the range as a set of "dictionary" sorted 4989132720Skan * sequences. Permutes the current sequence into the next one of this set. 4990132720Skan * Returns true if there are more sequences to generate. If the sequence 4991132720Skan * is the largest of the set, the smallest is generated and false returned. 4992132720Skan */ 4993132720Skan template<typename _BidirectionalIterator> 499497403Sobrien bool 4995132720Skan next_permutation(_BidirectionalIterator __first, 4996132720Skan _BidirectionalIterator __last) 499797403Sobrien { 499897403Sobrien // concept requirements 4999132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5000132720Skan _BidirectionalIterator>) 5001132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 5002132720Skan typename iterator_traits<_BidirectionalIterator>::value_type>) 5003132720Skan __glibcxx_requires_valid_range(__first, __last); 500497403Sobrien 500597403Sobrien if (__first == __last) 500697403Sobrien return false; 5007132720Skan _BidirectionalIterator __i = __first; 500897403Sobrien ++__i; 500997403Sobrien if (__i == __last) 501097403Sobrien return false; 501197403Sobrien __i = __last; 501297403Sobrien --__i; 501397403Sobrien 5014132720Skan for(;;) 5015132720Skan { 5016132720Skan _BidirectionalIterator __ii = __i; 5017132720Skan --__i; 5018132720Skan if (*__i < *__ii) 5019132720Skan { 5020132720Skan _BidirectionalIterator __j = __last; 5021132720Skan while (!(*__i < *--__j)) 5022132720Skan {} 5023132720Skan std::iter_swap(__i, __j); 5024132720Skan std::reverse(__ii, __last); 5025132720Skan return true; 5026132720Skan } 5027132720Skan if (__i == __first) 5028132720Skan { 5029132720Skan std::reverse(__first, __last); 5030132720Skan return false; 5031132720Skan } 503297403Sobrien } 503397403Sobrien } 503497403Sobrien 5035132720Skan /** 5036132720Skan * @brief Permute range into the next "dictionary" ordering using 5037132720Skan * comparison functor. 5038132720Skan * @param first Start of range. 5039132720Skan * @param last End of range. 5040132720Skan * @param comp 5041132720Skan * @return False if wrapped to first permutation, true otherwise. 5042132720Skan * 5043132720Skan * Treats all permutations of the range [first,last) as a set of 5044132720Skan * "dictionary" sorted sequences ordered by @a comp. Permutes the current 5045132720Skan * sequence into the next one of this set. Returns true if there are more 5046132720Skan * sequences to generate. If the sequence is the largest of the set, the 5047132720Skan * smallest is generated and false returned. 5048132720Skan */ 5049132720Skan template<typename _BidirectionalIterator, typename _Compare> 505097403Sobrien bool 5051132720Skan next_permutation(_BidirectionalIterator __first, 5052132720Skan _BidirectionalIterator __last, _Compare __comp) 505397403Sobrien { 505497403Sobrien // concept requirements 5055132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5056132720Skan _BidirectionalIterator>) 5057132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5058132720Skan typename iterator_traits<_BidirectionalIterator>::value_type, 5059132720Skan typename iterator_traits<_BidirectionalIterator>::value_type>) 5060132720Skan __glibcxx_requires_valid_range(__first, __last); 506197403Sobrien 506297403Sobrien if (__first == __last) 506397403Sobrien return false; 5064132720Skan _BidirectionalIterator __i = __first; 506597403Sobrien ++__i; 506697403Sobrien if (__i == __last) 506797403Sobrien return false; 506897403Sobrien __i = __last; 506997403Sobrien --__i; 507097403Sobrien 5071132720Skan for(;;) 5072132720Skan { 5073132720Skan _BidirectionalIterator __ii = __i; 5074132720Skan --__i; 5075132720Skan if (__comp(*__i, *__ii)) 5076132720Skan { 5077132720Skan _BidirectionalIterator __j = __last; 5078132720Skan while (!__comp(*__i, *--__j)) 5079132720Skan {} 5080132720Skan std::iter_swap(__i, __j); 5081132720Skan std::reverse(__ii, __last); 5082132720Skan return true; 5083132720Skan } 5084132720Skan if (__i == __first) 5085132720Skan { 5086132720Skan std::reverse(__first, __last); 5087132720Skan return false; 5088132720Skan } 508997403Sobrien } 509097403Sobrien } 509197403Sobrien 5092132720Skan /** 5093132720Skan * @brief Permute range into the previous "dictionary" ordering. 5094132720Skan * @param first Start of range. 5095132720Skan * @param last End of range. 5096132720Skan * @return False if wrapped to last permutation, true otherwise. 5097132720Skan * 5098132720Skan * Treats all permutations of the range as a set of "dictionary" sorted 5099132720Skan * sequences. Permutes the current sequence into the previous one of this 5100132720Skan * set. Returns true if there are more sequences to generate. If the 5101132720Skan * sequence is the smallest of the set, the largest is generated and false 5102132720Skan * returned. 5103132720Skan */ 5104132720Skan template<typename _BidirectionalIterator> 510597403Sobrien bool 5106132720Skan prev_permutation(_BidirectionalIterator __first, 5107132720Skan _BidirectionalIterator __last) 510897403Sobrien { 510997403Sobrien // concept requirements 5110132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5111132720Skan _BidirectionalIterator>) 5112132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 5113132720Skan typename iterator_traits<_BidirectionalIterator>::value_type>) 5114132720Skan __glibcxx_requires_valid_range(__first, __last); 511597403Sobrien 511697403Sobrien if (__first == __last) 511797403Sobrien return false; 5118132720Skan _BidirectionalIterator __i = __first; 511997403Sobrien ++__i; 512097403Sobrien if (__i == __last) 512197403Sobrien return false; 512297403Sobrien __i = __last; 512397403Sobrien --__i; 512497403Sobrien 5125132720Skan for(;;) 5126132720Skan { 5127132720Skan _BidirectionalIterator __ii = __i; 5128132720Skan --__i; 5129132720Skan if (*__ii < *__i) 5130132720Skan { 5131132720Skan _BidirectionalIterator __j = __last; 5132132720Skan while (!(*--__j < *__i)) 5133132720Skan {} 5134132720Skan std::iter_swap(__i, __j); 5135132720Skan std::reverse(__ii, __last); 5136132720Skan return true; 5137132720Skan } 5138132720Skan if (__i == __first) 5139132720Skan { 5140132720Skan std::reverse(__first, __last); 5141132720Skan return false; 5142132720Skan } 514397403Sobrien } 514497403Sobrien } 514597403Sobrien 5146132720Skan /** 5147132720Skan * @brief Permute range into the previous "dictionary" ordering using 5148132720Skan * comparison functor. 5149132720Skan * @param first Start of range. 5150132720Skan * @param last End of range. 5151132720Skan * @param comp 5152132720Skan * @return False if wrapped to last permutation, true otherwise. 5153132720Skan * 5154132720Skan * Treats all permutations of the range [first,last) as a set of 5155132720Skan * "dictionary" sorted sequences ordered by @a comp. Permutes the current 5156132720Skan * sequence into the previous one of this set. Returns true if there are 5157132720Skan * more sequences to generate. If the sequence is the smallest of the set, 5158132720Skan * the largest is generated and false returned. 5159132720Skan */ 5160132720Skan template<typename _BidirectionalIterator, typename _Compare> 516197403Sobrien bool 5162132720Skan prev_permutation(_BidirectionalIterator __first, 5163132720Skan _BidirectionalIterator __last, _Compare __comp) 516497403Sobrien { 516597403Sobrien // concept requirements 5166132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5167132720Skan _BidirectionalIterator>) 5168132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5169132720Skan typename iterator_traits<_BidirectionalIterator>::value_type, 5170132720Skan typename iterator_traits<_BidirectionalIterator>::value_type>) 5171132720Skan __glibcxx_requires_valid_range(__first, __last); 517297403Sobrien 517397403Sobrien if (__first == __last) 517497403Sobrien return false; 5175132720Skan _BidirectionalIterator __i = __first; 517697403Sobrien ++__i; 517797403Sobrien if (__i == __last) 517897403Sobrien return false; 517997403Sobrien __i = __last; 518097403Sobrien --__i; 518197403Sobrien 5182132720Skan for(;;) 5183132720Skan { 5184132720Skan _BidirectionalIterator __ii = __i; 5185132720Skan --__i; 5186132720Skan if (__comp(*__ii, *__i)) 5187132720Skan { 5188132720Skan _BidirectionalIterator __j = __last; 5189132720Skan while (!__comp(*--__j, *__i)) 5190132720Skan {} 5191132720Skan std::iter_swap(__i, __j); 5192132720Skan std::reverse(__ii, __last); 5193132720Skan return true; 5194132720Skan } 5195132720Skan if (__i == __first) 5196132720Skan { 5197132720Skan std::reverse(__first, __last); 5198132720Skan return false; 5199132720Skan } 520097403Sobrien } 520197403Sobrien } 520297403Sobrien 520397403Sobrien // find_first_of, with and without an explicitly supplied comparison function. 520497403Sobrien 5205132720Skan /** 5206132720Skan * @brief Find element from a set in a sequence. 5207132720Skan * @param first1 Start of range to search. 5208132720Skan * @param last1 End of range to search. 5209132720Skan * @param first2 Start of match candidates. 5210132720Skan * @param last2 End of match candidates. 5211132720Skan * @return The first iterator @c i in the range 5212132720Skan * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an 5213132720Skan * interator in [first2,last2), or @p last1 if no such iterator exists. 5214132720Skan * 5215132720Skan * Searches the range @p [first1,last1) for an element that is equal to 5216132720Skan * some element in the range [first2,last2). If found, returns an iterator 5217132720Skan * in the range [first1,last1), otherwise returns @p last1. 5218132720Skan */ 5219132720Skan template<typename _InputIterator, typename _ForwardIterator> 5220132720Skan _InputIterator 5221132720Skan find_first_of(_InputIterator __first1, _InputIterator __last1, 5222132720Skan _ForwardIterator __first2, _ForwardIterator __last2) 522397403Sobrien { 522497403Sobrien // concept requirements 5225132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 5226132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5227132720Skan __glibcxx_function_requires(_EqualOpConcept< 5228132720Skan typename iterator_traits<_InputIterator>::value_type, 5229132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 5230132720Skan __glibcxx_requires_valid_range(__first1, __last1); 5231132720Skan __glibcxx_requires_valid_range(__first2, __last2); 523297403Sobrien 523397403Sobrien for ( ; __first1 != __last1; ++__first1) 5234132720Skan for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 523597403Sobrien if (*__first1 == *__iter) 523697403Sobrien return __first1; 523797403Sobrien return __last1; 523897403Sobrien } 523997403Sobrien 5240132720Skan /** 5241132720Skan * @brief Find element from a set in a sequence using a predicate. 5242132720Skan * @param first1 Start of range to search. 5243132720Skan * @param last1 End of range to search. 5244132720Skan * @param first2 Start of match candidates. 5245132720Skan * @param last2 End of match candidates. 5246132720Skan * @param comp Predicate to use. 5247132720Skan * @return The first iterator @c i in the range 5248132720Skan * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an 5249132720Skan * interator in [first2,last2), or @p last1 if no such iterator exists. 5250132720Skan * 5251132720Skan * Searches the range @p [first1,last1) for an element that is equal to 5252132720Skan * some element in the range [first2,last2). If found, returns an iterator in 5253132720Skan * the range [first1,last1), otherwise returns @p last1. 5254132720Skan */ 5255132720Skan template<typename _InputIterator, typename _ForwardIterator, 5256132720Skan typename _BinaryPredicate> 5257132720Skan _InputIterator 5258132720Skan find_first_of(_InputIterator __first1, _InputIterator __last1, 5259132720Skan _ForwardIterator __first2, _ForwardIterator __last2, 526097403Sobrien _BinaryPredicate __comp) 526197403Sobrien { 526297403Sobrien // concept requirements 5263132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 5264132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5265132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 5266132720Skan typename iterator_traits<_InputIterator>::value_type, 5267132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 5268132720Skan __glibcxx_requires_valid_range(__first1, __last1); 5269132720Skan __glibcxx_requires_valid_range(__first2, __last2); 527097403Sobrien 527197403Sobrien for ( ; __first1 != __last1; ++__first1) 5272132720Skan for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 527397403Sobrien if (__comp(*__first1, *__iter)) 527497403Sobrien return __first1; 527597403Sobrien return __last1; 527697403Sobrien } 527797403Sobrien 527897403Sobrien 527997403Sobrien // find_end, with and without an explicitly supplied comparison function. 528097403Sobrien // Search [first2, last2) as a subsequence in [first1, last1), and return 528197403Sobrien // the *last* possible match. Note that find_end for bidirectional iterators 528297403Sobrien // is much faster than for forward iterators. 528397403Sobrien 528497403Sobrien // find_end for forward iterators. 5285132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 5286132720Skan _ForwardIterator1 5287132720Skan __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 5288132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2, 528997403Sobrien forward_iterator_tag, forward_iterator_tag) 529097403Sobrien { 529197403Sobrien if (__first2 == __last2) 529297403Sobrien return __last1; 5293132720Skan else 5294132720Skan { 5295132720Skan _ForwardIterator1 __result = __last1; 5296132720Skan while (1) 5297132720Skan { 5298132720Skan _ForwardIterator1 __new_result 5299132720Skan = std::search(__first1, __last1, __first2, __last2); 5300132720Skan if (__new_result == __last1) 5301132720Skan return __result; 5302132720Skan else 5303132720Skan { 5304132720Skan __result = __new_result; 5305132720Skan __first1 = __new_result; 5306132720Skan ++__first1; 5307132720Skan } 5308132720Skan } 530997403Sobrien } 531097403Sobrien } 531197403Sobrien 5312132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2, 531397403Sobrien typename _BinaryPredicate> 5314132720Skan _ForwardIterator1 5315132720Skan __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 5316132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2, 531797403Sobrien forward_iterator_tag, forward_iterator_tag, 531897403Sobrien _BinaryPredicate __comp) 531997403Sobrien { 532097403Sobrien if (__first2 == __last2) 532197403Sobrien return __last1; 5322132720Skan else 5323132720Skan { 5324132720Skan _ForwardIterator1 __result = __last1; 5325132720Skan while (1) 5326132720Skan { 5327132720Skan _ForwardIterator1 __new_result 5328132720Skan = std::search(__first1, __last1, __first2, __last2, __comp); 5329132720Skan if (__new_result == __last1) 5330132720Skan return __result; 5331132720Skan else 5332132720Skan { 5333132720Skan __result = __new_result; 5334132720Skan __first1 = __new_result; 5335132720Skan ++__first1; 5336132720Skan } 5337132720Skan } 533897403Sobrien } 533997403Sobrien } 534097403Sobrien 534197403Sobrien // find_end for bidirectional iterators. Requires partial specialization. 5342132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2> 5343132720Skan _BidirectionalIterator1 5344132720Skan __find_end(_BidirectionalIterator1 __first1, 5345132720Skan _BidirectionalIterator1 __last1, 5346132720Skan _BidirectionalIterator2 __first2, 5347132720Skan _BidirectionalIterator2 __last2, 534897403Sobrien bidirectional_iterator_tag, bidirectional_iterator_tag) 534997403Sobrien { 535097403Sobrien // concept requirements 5351132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5352132720Skan _BidirectionalIterator1>) 5353132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5354132720Skan _BidirectionalIterator2>) 535597403Sobrien 5356132720Skan typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; 5357132720Skan typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; 535897403Sobrien 5359132720Skan _RevIterator1 __rlast1(__first1); 5360132720Skan _RevIterator2 __rlast2(__first2); 5361132720Skan _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1, 5362132720Skan _RevIterator2(__last2), __rlast2); 536397403Sobrien 536497403Sobrien if (__rresult == __rlast1) 536597403Sobrien return __last1; 5366132720Skan else 5367132720Skan { 5368132720Skan _BidirectionalIterator1 __result = __rresult.base(); 5369132720Skan std::advance(__result, -std::distance(__first2, __last2)); 5370132720Skan return __result; 5371132720Skan } 537297403Sobrien } 537397403Sobrien 5374132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 537597403Sobrien typename _BinaryPredicate> 5376132720Skan _BidirectionalIterator1 5377132720Skan __find_end(_BidirectionalIterator1 __first1, 5378132720Skan _BidirectionalIterator1 __last1, 5379132720Skan _BidirectionalIterator2 __first2, 5380132720Skan _BidirectionalIterator2 __last2, 538197403Sobrien bidirectional_iterator_tag, bidirectional_iterator_tag, 538297403Sobrien _BinaryPredicate __comp) 538397403Sobrien { 538497403Sobrien // concept requirements 5385132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5386132720Skan _BidirectionalIterator1>) 5387132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5388132720Skan _BidirectionalIterator2>) 538997403Sobrien 5390132720Skan typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; 5391132720Skan typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; 539297403Sobrien 5393132720Skan _RevIterator1 __rlast1(__first1); 5394132720Skan _RevIterator2 __rlast2(__first2); 5395132720Skan _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1, 5396132720Skan _RevIterator2(__last2), __rlast2, 5397132720Skan __comp); 539897403Sobrien 539997403Sobrien if (__rresult == __rlast1) 540097403Sobrien return __last1; 5401132720Skan else 5402132720Skan { 5403132720Skan _BidirectionalIterator1 __result = __rresult.base(); 5404132720Skan std::advance(__result, -std::distance(__first2, __last2)); 5405132720Skan return __result; 5406132720Skan } 540797403Sobrien } 540897403Sobrien 540997403Sobrien // Dispatching functions for find_end. 541097403Sobrien 5411132720Skan /** 5412132720Skan * @brief Find last matching subsequence in a sequence. 5413132720Skan * @param first1 Start of range to search. 5414132720Skan * @param last1 End of range to search. 5415132720Skan * @param first2 Start of sequence to match. 5416132720Skan * @param last2 End of sequence to match. 5417132720Skan * @return The last iterator @c i in the range 5418132720Skan * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) 5419132720Skan * for each @c N in the range @p [0,last2-first2), or @p last1 if no 5420132720Skan * such iterator exists. 5421132720Skan * 5422132720Skan * Searches the range @p [first1,last1) for a sub-sequence that compares 5423132720Skan * equal value-by-value with the sequence given by @p [first2,last2) and 5424132720Skan * returns an iterator to the first element of the sub-sequence, or 5425132720Skan * @p last1 if the sub-sequence is not found. The sub-sequence will be the 5426132720Skan * last such subsequence contained in [first,last1). 5427132720Skan * 5428132720Skan * Because the sub-sequence must lie completely within the range 5429132720Skan * @p [first1,last1) it must start at a position less than 5430132720Skan * @p last1-(last2-first2) where @p last2-first2 is the length of the 5431132720Skan * sub-sequence. 5432132720Skan * This means that the returned iterator @c i will be in the range 5433132720Skan * @p [first1,last1-(last2-first2)) 5434132720Skan */ 5435132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 5436132720Skan inline _ForwardIterator1 5437132720Skan find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 5438132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2) 543997403Sobrien { 544097403Sobrien // concept requirements 5441132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 5442132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 5443132720Skan __glibcxx_function_requires(_EqualOpConcept< 5444132720Skan typename iterator_traits<_ForwardIterator1>::value_type, 5445132720Skan typename iterator_traits<_ForwardIterator2>::value_type>) 5446132720Skan __glibcxx_requires_valid_range(__first1, __last1); 5447132720Skan __glibcxx_requires_valid_range(__first2, __last2); 544897403Sobrien 5449132720Skan return std::__find_end(__first1, __last1, __first2, __last2, 5450132720Skan std::__iterator_category(__first1), 5451132720Skan std::__iterator_category(__first2)); 545297403Sobrien } 545397403Sobrien 5454132720Skan /** 5455132720Skan * @brief Find last matching subsequence in a sequence using a predicate. 5456132720Skan * @param first1 Start of range to search. 5457132720Skan * @param last1 End of range to search. 5458132720Skan * @param first2 Start of sequence to match. 5459132720Skan * @param last2 End of sequence to match. 5460132720Skan * @param comp The predicate to use. 5461132720Skan * @return The last iterator @c i in the range 5462132720Skan * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p 5463132720Skan * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or 5464132720Skan * @p last1 if no such iterator exists. 5465132720Skan * 5466132720Skan * Searches the range @p [first1,last1) for a sub-sequence that compares 5467132720Skan * equal value-by-value with the sequence given by @p [first2,last2) using 5468132720Skan * comp as a predicate and returns an iterator to the first element of the 5469132720Skan * sub-sequence, or @p last1 if the sub-sequence is not found. The 5470132720Skan * sub-sequence will be the last such subsequence contained in 5471132720Skan * [first,last1). 5472132720Skan * 5473132720Skan * Because the sub-sequence must lie completely within the range 5474132720Skan * @p [first1,last1) it must start at a position less than 5475132720Skan * @p last1-(last2-first2) where @p last2-first2 is the length of the 5476132720Skan * sub-sequence. 5477132720Skan * This means that the returned iterator @c i will be in the range 5478132720Skan * @p [first1,last1-(last2-first2)) 5479132720Skan */ 5480132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2, 548197403Sobrien typename _BinaryPredicate> 5482132720Skan inline _ForwardIterator1 5483132720Skan find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 5484132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2, 548597403Sobrien _BinaryPredicate __comp) 548697403Sobrien { 548797403Sobrien // concept requirements 5488132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 5489132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 5490132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 5491132720Skan typename iterator_traits<_ForwardIterator1>::value_type, 5492132720Skan typename iterator_traits<_ForwardIterator2>::value_type>) 5493132720Skan __glibcxx_requires_valid_range(__first1, __last1); 5494132720Skan __glibcxx_requires_valid_range(__first2, __last2); 549597403Sobrien 5496132720Skan return std::__find_end(__first1, __last1, __first2, __last2, 5497132720Skan std::__iterator_category(__first1), 5498132720Skan std::__iterator_category(__first2), 5499132720Skan __comp); 550097403Sobrien } 550197403Sobrien 5502169691Skan_GLIBCXX_END_NAMESPACE 550397403Sobrien 5504132720Skan#endif /* _ALGO_H */ 5505