197403Sobrien// Bits and pieces used in algorithms -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 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-1998 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_algobase.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 _ALGOBASE_H 63132720Skan#define _ALGOBASE_H 1 6497403Sobrien 6597403Sobrien#include <bits/c++config.h> 6697403Sobrien#include <cstring> 6797403Sobrien#include <climits> 6897403Sobrien#include <cstdlib> 6997403Sobrien#include <cstddef> 7097403Sobrien#include <iosfwd> 7197403Sobrien#include <bits/stl_pair.h> 72169691Skan#include <bits/cpp_type_traits.h> 73169691Skan#include <ext/type_traits.h> 7497403Sobrien#include <bits/stl_iterator_base_types.h> 7597403Sobrien#include <bits/stl_iterator_base_funcs.h> 7697403Sobrien#include <bits/stl_iterator.h> 7797403Sobrien#include <bits/concept_check.h> 78132720Skan#include <debug/debug.h> 7997403Sobrien 80169691Skan_GLIBCXX_BEGIN_NAMESPACE(std) 81169691Skan 8297403Sobrien /** 83169691Skan * @brief Swaps two values. 84169691Skan * @param a A thing of arbitrary type. 85169691Skan * @param b Another thing of arbitrary type. 86169691Skan * @return Nothing. 87169691Skan * 88169691Skan * This is the simple classic generic implementation. It will work on 89169691Skan * any type which has a copy constructor and an assignment operator. 90169691Skan */ 91169691Skan template<typename _Tp> 92169691Skan inline void 93169691Skan swap(_Tp& __a, _Tp& __b) 94169691Skan { 95169691Skan // concept requirements 96169691Skan __glibcxx_function_requires(_SGIAssignableConcept<_Tp>) 97169691Skan 98169691Skan _Tp __tmp = __a; 99169691Skan __a = __b; 100169691Skan __b = __tmp; 101169691Skan } 102169691Skan 103169691Skan // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a 104169691Skan // nutshell, we are partially implementing the resolution of DR 187, 105169691Skan // when it's safe, i.e., the value_types are equal. 106169691Skan template<bool _BoolType> 107169691Skan struct __iter_swap 108169691Skan { 109169691Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 110169691Skan static void 111169691Skan iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 112169691Skan { 113169691Skan typedef typename iterator_traits<_ForwardIterator1>::value_type 114169691Skan _ValueType1; 115169691Skan _ValueType1 __tmp = *__a; 116169691Skan *__a = *__b; 117169691Skan *__b = __tmp; 118169691Skan } 119169691Skan }; 120169691Skan 121169691Skan template<> 122169691Skan struct __iter_swap<true> 123169691Skan { 124169691Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 125169691Skan static void 126169691Skan iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 127169691Skan { 128169691Skan swap(*__a, *__b); 129169691Skan } 130169691Skan }; 131169691Skan 132169691Skan /** 13397403Sobrien * @brief Swaps the contents of two iterators. 13497403Sobrien * @param a An iterator. 13597403Sobrien * @param b Another iterator. 13697403Sobrien * @return Nothing. 13797403Sobrien * 13897403Sobrien * This function swaps the values pointed to by two iterators, not the 13997403Sobrien * iterators themselves. 14097403Sobrien */ 141132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 14297403Sobrien inline void 143132720Skan iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 14497403Sobrien { 145132720Skan typedef typename iterator_traits<_ForwardIterator1>::value_type 146132720Skan _ValueType1; 147132720Skan typedef typename iterator_traits<_ForwardIterator2>::value_type 148132720Skan _ValueType2; 14997403Sobrien 15097403Sobrien // concept requirements 151132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 152132720Skan _ForwardIterator1>) 153132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 154132720Skan _ForwardIterator2>) 155132720Skan __glibcxx_function_requires(_ConvertibleConcept<_ValueType1, 156132720Skan _ValueType2>) 157132720Skan __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, 158132720Skan _ValueType1>) 15997403Sobrien 160169691Skan typedef typename iterator_traits<_ForwardIterator1>::reference 161169691Skan _ReferenceType1; 162169691Skan typedef typename iterator_traits<_ForwardIterator2>::reference 163169691Skan _ReferenceType2; 164169691Skan std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value && 165169691Skan __are_same<_ValueType1 &, _ReferenceType1>::__value && 166169691Skan __are_same<_ValueType2 &, _ReferenceType2>::__value>:: 167169691Skan iter_swap(__a, __b); 16897403Sobrien } 16997403Sobrien 17097403Sobrien /** 17197403Sobrien * @brief This does what you think it does. 17297403Sobrien * @param a A thing of arbitrary type. 17397403Sobrien * @param b Another thing of arbitrary type. 17497403Sobrien * @return The lesser of the parameters. 17597403Sobrien * 17697403Sobrien * This is the simple classic generic implementation. It will work on 17797403Sobrien * temporary expressions, since they are only evaluated once, unlike a 17897403Sobrien * preprocessor macro. 17997403Sobrien */ 18097403Sobrien template<typename _Tp> 18197403Sobrien inline const _Tp& 18297403Sobrien min(const _Tp& __a, const _Tp& __b) 18397403Sobrien { 18497403Sobrien // concept requirements 185132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 18697403Sobrien //return __b < __a ? __b : __a; 187132720Skan if (__b < __a) 188132720Skan return __b; 189132720Skan return __a; 19097403Sobrien } 19197403Sobrien 19297403Sobrien /** 19397403Sobrien * @brief This does what you think it does. 19497403Sobrien * @param a A thing of arbitrary type. 19597403Sobrien * @param b Another thing of arbitrary type. 19697403Sobrien * @return The greater of the parameters. 19797403Sobrien * 19897403Sobrien * This is the simple classic generic implementation. It will work on 19997403Sobrien * temporary expressions, since they are only evaluated once, unlike a 20097403Sobrien * preprocessor macro. 20197403Sobrien */ 20297403Sobrien template<typename _Tp> 20397403Sobrien inline const _Tp& 204132720Skan max(const _Tp& __a, const _Tp& __b) 20597403Sobrien { 20697403Sobrien // concept requirements 207132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 20897403Sobrien //return __a < __b ? __b : __a; 209132720Skan if (__a < __b) 210132720Skan return __b; 211132720Skan return __a; 21297403Sobrien } 21397403Sobrien 21497403Sobrien /** 21597403Sobrien * @brief This does what you think it does. 21697403Sobrien * @param a A thing of arbitrary type. 21797403Sobrien * @param b Another thing of arbitrary type. 21897403Sobrien * @param comp A @link s20_3_3_comparisons comparison functor@endlink. 21997403Sobrien * @return The lesser of the parameters. 22097403Sobrien * 22197403Sobrien * This will work on temporary expressions, since they are only evaluated 22297403Sobrien * once, unlike a preprocessor macro. 22397403Sobrien */ 22497403Sobrien template<typename _Tp, typename _Compare> 22597403Sobrien inline const _Tp& 22697403Sobrien min(const _Tp& __a, const _Tp& __b, _Compare __comp) 22797403Sobrien { 22897403Sobrien //return __comp(__b, __a) ? __b : __a; 229132720Skan if (__comp(__b, __a)) 230132720Skan return __b; 231132720Skan return __a; 23297403Sobrien } 23397403Sobrien 23497403Sobrien /** 23597403Sobrien * @brief This does what you think it does. 23697403Sobrien * @param a A thing of arbitrary type. 23797403Sobrien * @param b Another thing of arbitrary type. 23897403Sobrien * @param comp A @link s20_3_3_comparisons comparison functor@endlink. 23997403Sobrien * @return The greater of the parameters. 24097403Sobrien * 24197403Sobrien * This will work on temporary expressions, since they are only evaluated 24297403Sobrien * once, unlike a preprocessor macro. 24397403Sobrien */ 24497403Sobrien template<typename _Tp, typename _Compare> 24597403Sobrien inline const _Tp& 24697403Sobrien max(const _Tp& __a, const _Tp& __b, _Compare __comp) 24797403Sobrien { 24897403Sobrien //return __comp(__a, __b) ? __b : __a; 249132720Skan if (__comp(__a, __b)) 250132720Skan return __b; 251132720Skan return __a; 25297403Sobrien } 25397403Sobrien 254169691Skan // All of these auxiliary structs serve two purposes. (1) Replace 25597403Sobrien // calls to copy with memmove whenever possible. (Memmove, not memcpy, 25697403Sobrien // because the input and output ranges are permitted to overlap.) 25797403Sobrien // (2) If we're using random access iterators, then write the loop as 25897403Sobrien // a for loop with an explicit count. 25997403Sobrien 260169691Skan template<bool, typename> 261169691Skan struct __copy 26297403Sobrien { 263169691Skan template<typename _II, typename _OI> 264169691Skan static _OI 265169691Skan copy(_II __first, _II __last, _OI __result) 266169691Skan { 267169691Skan for (; __first != __last; ++__result, ++__first) 268169691Skan *__result = *__first; 269169691Skan return __result; 270169691Skan } 271169691Skan }; 27297403Sobrien 273169691Skan template<bool _BoolType> 274169691Skan struct __copy<_BoolType, random_access_iterator_tag> 27597403Sobrien { 276169691Skan template<typename _II, typename _OI> 277169691Skan static _OI 278169691Skan copy(_II __first, _II __last, _OI __result) 279169691Skan { 280169691Skan typedef typename iterator_traits<_II>::difference_type _Distance; 281169691Skan for(_Distance __n = __last - __first; __n > 0; --__n) 282169691Skan { 283169691Skan *__result = *__first; 284169691Skan ++__first; 285169691Skan ++__result; 286169691Skan } 287169691Skan return __result; 288132720Skan } 289169691Skan }; 29097403Sobrien 291169691Skan template<> 292169691Skan struct __copy<true, random_access_iterator_tag> 29397403Sobrien { 294169691Skan template<typename _Tp> 295169691Skan static _Tp* 296169691Skan copy(const _Tp* __first, const _Tp* __last, _Tp* __result) 297169691Skan { 298169691Skan std::memmove(__result, __first, sizeof(_Tp) * (__last - __first)); 299169691Skan return __result + (__last - __first); 300169691Skan } 301169691Skan }; 302169691Skan 303169691Skan template<typename _II, typename _OI> 304169691Skan inline _OI 305169691Skan __copy_aux(_II __first, _II __last, _OI __result) 306169691Skan { 307169691Skan typedef typename iterator_traits<_II>::value_type _ValueTypeI; 308169691Skan typedef typename iterator_traits<_OI>::value_type _ValueTypeO; 309169691Skan typedef typename iterator_traits<_II>::iterator_category _Category; 310169691Skan const bool __simple = (__is_scalar<_ValueTypeI>::__value 311169691Skan && __is_pointer<_II>::__value 312169691Skan && __is_pointer<_OI>::__value 313169691Skan && __are_same<_ValueTypeI, _ValueTypeO>::__value); 314169691Skan 315169691Skan return std::__copy<__simple, _Category>::copy(__first, __last, __result); 31697403Sobrien } 31797403Sobrien 318169691Skan // Helpers for streambuf iterators (either istream or ostream). 319169691Skan template<typename _CharT> 320169691Skan typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 321169691Skan ostreambuf_iterator<_CharT> >::__type 322169691Skan __copy_aux(_CharT*, _CharT*, ostreambuf_iterator<_CharT>); 32397403Sobrien 324169691Skan template<typename _CharT> 325169691Skan typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 326169691Skan ostreambuf_iterator<_CharT> >::__type 327169691Skan __copy_aux(const _CharT*, const _CharT*, ostreambuf_iterator<_CharT>); 32897403Sobrien 329169691Skan template<typename _CharT> 330169691Skan typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, _CharT*>::__type 331169691Skan __copy_aux(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, 332169691Skan _CharT*); 33397403Sobrien 334169691Skan template<bool, bool> 335169691Skan struct __copy_normal 33697403Sobrien { 337169691Skan template<typename _II, typename _OI> 338169691Skan static _OI 339169691Skan __copy_n(_II __first, _II __last, _OI __result) 340169691Skan { return std::__copy_aux(__first, __last, __result); } 341169691Skan }; 34297403Sobrien 343169691Skan template<> 344169691Skan struct __copy_normal<true, false> 34597403Sobrien { 346169691Skan template<typename _II, typename _OI> 347169691Skan static _OI 348169691Skan __copy_n(_II __first, _II __last, _OI __result) 349169691Skan { return std::__copy_aux(__first.base(), __last.base(), __result); } 350169691Skan }; 35197403Sobrien 352169691Skan template<> 353169691Skan struct __copy_normal<false, true> 35497403Sobrien { 355169691Skan template<typename _II, typename _OI> 356169691Skan static _OI 357169691Skan __copy_n(_II __first, _II __last, _OI __result) 358169691Skan { return _OI(std::__copy_aux(__first, __last, __result.base())); } 359169691Skan }; 36097403Sobrien 361169691Skan template<> 362169691Skan struct __copy_normal<true, true> 36397403Sobrien { 364169691Skan template<typename _II, typename _OI> 365169691Skan static _OI 366169691Skan __copy_n(_II __first, _II __last, _OI __result) 367169691Skan { return _OI(std::__copy_aux(__first.base(), __last.base(), 368169691Skan __result.base())); } 369169691Skan }; 37097403Sobrien 37197403Sobrien /** 37297403Sobrien * @brief Copies the range [first,last) into result. 37397403Sobrien * @param first An input iterator. 37497403Sobrien * @param last An input iterator. 37597403Sobrien * @param result An output iterator. 376258429Spfg * @return result + (last - first) 37797403Sobrien * 37897403Sobrien * This inline function will boil down to a call to @c memmove whenever 37997403Sobrien * possible. Failing that, if random access iterators are passed, then the 38097403Sobrien * loop count will be known (and therefore a candidate for compiler 381132720Skan * optimizations such as unrolling). Result may not be contained within 382132720Skan * [first,last); the copy_backward function should be used instead. 383132720Skan * 384132720Skan * Note that the end of the output range is permitted to be contained 385132720Skan * within [first,last). 38697403Sobrien */ 387132720Skan template<typename _InputIterator, typename _OutputIterator> 388132720Skan inline _OutputIterator 389132720Skan copy(_InputIterator __first, _InputIterator __last, 390132720Skan _OutputIterator __result) 39197403Sobrien { 39297403Sobrien // concept requirements 393132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 394132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 395132720Skan typename iterator_traits<_InputIterator>::value_type>) 396132720Skan __glibcxx_requires_valid_range(__first, __last); 39797403Sobrien 398169691Skan const bool __in = __is_normal_iterator<_InputIterator>::__value; 399169691Skan const bool __out = __is_normal_iterator<_OutputIterator>::__value; 400169691Skan return std::__copy_normal<__in, __out>::__copy_n(__first, __last, 401169691Skan __result); 40297403Sobrien } 40397403Sobrien 404169691Skan // Overload for streambuf iterators. 405169691Skan template<typename _CharT> 406169691Skan typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 407169691Skan ostreambuf_iterator<_CharT> >::__type 408169691Skan copy(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, 409169691Skan ostreambuf_iterator<_CharT>); 41097403Sobrien 411169691Skan template<bool, typename> 412169691Skan struct __copy_backward 41397403Sobrien { 414169691Skan template<typename _BI1, typename _BI2> 415169691Skan static _BI2 416169691Skan __copy_b(_BI1 __first, _BI1 __last, _BI2 __result) 417169691Skan { 418169691Skan while (__first != __last) 419169691Skan *--__result = *--__last; 420169691Skan return __result; 421169691Skan } 42297403Sobrien }; 42397403Sobrien 424169691Skan template<bool _BoolType> 425169691Skan struct __copy_backward<_BoolType, random_access_iterator_tag> 42697403Sobrien { 427169691Skan template<typename _BI1, typename _BI2> 428169691Skan static _BI2 429169691Skan __copy_b(_BI1 __first, _BI1 __last, _BI2 __result) 430169691Skan { 431169691Skan typename iterator_traits<_BI1>::difference_type __n; 432169691Skan for (__n = __last - __first; __n > 0; --__n) 433169691Skan *--__result = *--__last; 434169691Skan return __result; 435169691Skan } 43697403Sobrien }; 43797403Sobrien 438169691Skan template<> 439169691Skan struct __copy_backward<true, random_access_iterator_tag> 44097403Sobrien { 441169691Skan template<typename _Tp> 442169691Skan static _Tp* 443169691Skan __copy_b(const _Tp* __first, const _Tp* __last, _Tp* __result) 444169691Skan { 445169691Skan const ptrdiff_t _Num = __last - __first; 446169691Skan std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num); 447169691Skan return __result - _Num; 448169691Skan } 44997403Sobrien }; 45097403Sobrien 45197403Sobrien template<typename _BI1, typename _BI2> 45297403Sobrien inline _BI2 45397403Sobrien __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) 45497403Sobrien { 455169691Skan typedef typename iterator_traits<_BI1>::value_type _ValueType1; 456169691Skan typedef typename iterator_traits<_BI2>::value_type _ValueType2; 457169691Skan typedef typename iterator_traits<_BI1>::iterator_category _Category; 458169691Skan const bool __simple = (__is_scalar<_ValueType1>::__value 459169691Skan && __is_pointer<_BI1>::__value 460169691Skan && __is_pointer<_BI2>::__value 461169691Skan && __are_same<_ValueType1, _ValueType2>::__value); 462169691Skan 463169691Skan return std::__copy_backward<__simple, _Category>::__copy_b(__first, 464169691Skan __last, 465169691Skan __result); 46697403Sobrien } 46797403Sobrien 468169691Skan template<bool, bool> 469169691Skan struct __copy_backward_normal 470169691Skan { 471169691Skan template<typename _BI1, typename _BI2> 472169691Skan static _BI2 473169691Skan __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result) 474169691Skan { return std::__copy_backward_aux(__first, __last, __result); } 475169691Skan }; 47697403Sobrien 477169691Skan template<> 478169691Skan struct __copy_backward_normal<true, false> 479169691Skan { 480169691Skan template<typename _BI1, typename _BI2> 481169691Skan static _BI2 482169691Skan __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result) 483169691Skan { return std::__copy_backward_aux(__first.base(), __last.base(), 484169691Skan __result); } 485169691Skan }; 48697403Sobrien 487169691Skan template<> 488169691Skan struct __copy_backward_normal<false, true> 48997403Sobrien { 490169691Skan template<typename _BI1, typename _BI2> 491169691Skan static _BI2 492169691Skan __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result) 493169691Skan { return _BI2(std::__copy_backward_aux(__first, __last, 494169691Skan __result.base())); } 495169691Skan }; 49697403Sobrien 497169691Skan template<> 498169691Skan struct __copy_backward_normal<true, true> 49997403Sobrien { 500169691Skan template<typename _BI1, typename _BI2> 501169691Skan static _BI2 502169691Skan __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result) 503169691Skan { return _BI2(std::__copy_backward_aux(__first.base(), __last.base(), 504169691Skan __result.base())); } 505169691Skan }; 50697403Sobrien 50797403Sobrien /** 50897403Sobrien * @brief Copies the range [first,last) into result. 509132720Skan * @param first A bidirectional iterator. 510132720Skan * @param last A bidirectional iterator. 511132720Skan * @param result A bidirectional iterator. 51297403Sobrien * @return result - (first - last) 51397403Sobrien * 51497403Sobrien * The function has the same effect as copy, but starts at the end of the 51597403Sobrien * range and works its way to the start, returning the start of the result. 51697403Sobrien * This inline function will boil down to a call to @c memmove whenever 51797403Sobrien * possible. Failing that, if random access iterators are passed, then the 51897403Sobrien * loop count will be known (and therefore a candidate for compiler 51997403Sobrien * optimizations such as unrolling). 520132720Skan * 521132720Skan * Result may not be in the range [first,last). Use copy instead. Note 522132720Skan * that the start of the output range may overlap [first,last). 52397403Sobrien */ 52497403Sobrien template <typename _BI1, typename _BI2> 52597403Sobrien inline _BI2 52697403Sobrien copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) 52797403Sobrien { 52897403Sobrien // concept requirements 529132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 530132720Skan __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 531132720Skan __glibcxx_function_requires(_ConvertibleConcept< 53297403Sobrien typename iterator_traits<_BI1>::value_type, 53397403Sobrien typename iterator_traits<_BI2>::value_type>) 534132720Skan __glibcxx_requires_valid_range(__first, __last); 53597403Sobrien 536169691Skan const bool __bi1 = __is_normal_iterator<_BI1>::__value; 537169691Skan const bool __bi2 = __is_normal_iterator<_BI2>::__value; 538169691Skan return std::__copy_backward_normal<__bi1, __bi2>::__copy_b_n(__first, 539169691Skan __last, 540169691Skan __result); 54197403Sobrien } 54297403Sobrien 543169691Skan template<bool> 544169691Skan struct __fill 545169691Skan { 546169691Skan template<typename _ForwardIterator, typename _Tp> 547169691Skan static void 548169691Skan fill(_ForwardIterator __first, _ForwardIterator __last, 549169691Skan const _Tp& __value) 550169691Skan { 551169691Skan for (; __first != __last; ++__first) 552169691Skan *__first = __value; 553169691Skan } 554169691Skan }; 55597403Sobrien 556169691Skan template<> 557169691Skan struct __fill<true> 558169691Skan { 559169691Skan template<typename _ForwardIterator, typename _Tp> 560169691Skan static void 561169691Skan fill(_ForwardIterator __first, _ForwardIterator __last, 562169691Skan const _Tp& __value) 563169691Skan { 564169691Skan const _Tp __tmp = __value; 565169691Skan for (; __first != __last; ++__first) 566169691Skan *__first = __tmp; 567169691Skan } 568169691Skan }; 569169691Skan 57097403Sobrien /** 57197403Sobrien * @brief Fills the range [first,last) with copies of value. 57297403Sobrien * @param first A forward iterator. 57397403Sobrien * @param last A forward iterator. 57497403Sobrien * @param value A reference-to-const of arbitrary type. 57597403Sobrien * @return Nothing. 57697403Sobrien * 57797403Sobrien * This function fills a range with copies of the same value. For one-byte 57897403Sobrien * types filling contiguous areas of memory, this becomes an inline call to 57997403Sobrien * @c memset. 58097403Sobrien */ 581132720Skan template<typename _ForwardIterator, typename _Tp> 58297403Sobrien void 583132720Skan fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 58497403Sobrien { 58597403Sobrien // concept requirements 586132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 587132720Skan _ForwardIterator>) 588132720Skan __glibcxx_requires_valid_range(__first, __last); 58997403Sobrien 590169691Skan const bool __scalar = __is_scalar<_Tp>::__value; 591169691Skan std::__fill<__scalar>::fill(__first, __last, __value); 59297403Sobrien } 59397403Sobrien 59497403Sobrien // Specialization: for one-byte types we can use memset. 59597403Sobrien inline void 59697403Sobrien fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c) 59797403Sobrien { 598132720Skan __glibcxx_requires_valid_range(__first, __last); 599132720Skan const unsigned char __tmp = __c; 600132720Skan std::memset(__first, __tmp, __last - __first); 60197403Sobrien } 60297403Sobrien 60397403Sobrien inline void 60497403Sobrien fill(signed char* __first, signed char* __last, const signed char& __c) 60597403Sobrien { 606132720Skan __glibcxx_requires_valid_range(__first, __last); 607132720Skan const signed char __tmp = __c; 608132720Skan std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first); 60997403Sobrien } 61097403Sobrien 61197403Sobrien inline void 61297403Sobrien fill(char* __first, char* __last, const char& __c) 61397403Sobrien { 614132720Skan __glibcxx_requires_valid_range(__first, __last); 615132720Skan const char __tmp = __c; 616132720Skan std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first); 61797403Sobrien } 61897403Sobrien 619169691Skan template<bool> 620169691Skan struct __fill_n 621169691Skan { 622169691Skan template<typename _OutputIterator, typename _Size, typename _Tp> 623169691Skan static _OutputIterator 624169691Skan fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) 625169691Skan { 626169691Skan for (; __n > 0; --__n, ++__first) 627169691Skan *__first = __value; 628169691Skan return __first; 629169691Skan } 630169691Skan }; 631169691Skan 632169691Skan template<> 633169691Skan struct __fill_n<true> 634169691Skan { 635169691Skan template<typename _OutputIterator, typename _Size, typename _Tp> 636169691Skan static _OutputIterator 637169691Skan fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) 638169691Skan { 639169691Skan const _Tp __tmp = __value; 640169691Skan for (; __n > 0; --__n, ++__first) 641169691Skan *__first = __tmp; 642169691Skan return __first; 643169691Skan } 644169691Skan }; 645169691Skan 646169691Skan /** 647169691Skan * @brief Fills the range [first,first+n) with copies of value. 648169691Skan * @param first An output iterator. 649169691Skan * @param n The count of copies to perform. 650169691Skan * @param value A reference-to-const of arbitrary type. 651169691Skan * @return The iterator at first+n. 652169691Skan * 653169691Skan * This function fills a range with copies of the same value. For one-byte 654169691Skan * types filling contiguous areas of memory, this becomes an inline call to 655169691Skan * @c memset. 656169691Skan */ 657169691Skan template<typename _OutputIterator, typename _Size, typename _Tp> 658169691Skan _OutputIterator 659169691Skan fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) 660169691Skan { 661169691Skan // concept requirements 662169691Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _Tp>) 663169691Skan 664169691Skan const bool __scalar = __is_scalar<_Tp>::__value; 665169691Skan return std::__fill_n<__scalar>::fill_n(__first, __n, __value); 666169691Skan } 667169691Skan 66897403Sobrien template<typename _Size> 66997403Sobrien inline unsigned char* 67097403Sobrien fill_n(unsigned char* __first, _Size __n, const unsigned char& __c) 67197403Sobrien { 672132720Skan std::fill(__first, __first + __n, __c); 67397403Sobrien return __first + __n; 67497403Sobrien } 67597403Sobrien 67697403Sobrien template<typename _Size> 67797403Sobrien inline signed char* 678169691Skan fill_n(signed char* __first, _Size __n, const signed char& __c) 67997403Sobrien { 680132720Skan std::fill(__first, __first + __n, __c); 68197403Sobrien return __first + __n; 68297403Sobrien } 68397403Sobrien 68497403Sobrien template<typename _Size> 68597403Sobrien inline char* 68697403Sobrien fill_n(char* __first, _Size __n, const char& __c) 68797403Sobrien { 688132720Skan std::fill(__first, __first + __n, __c); 68997403Sobrien return __first + __n; 69097403Sobrien } 69197403Sobrien 69297403Sobrien /** 69397403Sobrien * @brief Finds the places in ranges which don't match. 69497403Sobrien * @param first1 An input iterator. 69597403Sobrien * @param last1 An input iterator. 69697403Sobrien * @param first2 An input iterator. 69797403Sobrien * @return A pair of iterators pointing to the first mismatch. 69897403Sobrien * 69997403Sobrien * This compares the elements of two ranges using @c == and returns a pair 70097403Sobrien * of iterators. The first iterator points into the first range, the 70197403Sobrien * second iterator points into the second range, and the elements pointed 70297403Sobrien * to by the iterators are not equal. 70397403Sobrien */ 704132720Skan template<typename _InputIterator1, typename _InputIterator2> 705132720Skan pair<_InputIterator1, _InputIterator2> 706132720Skan mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 707132720Skan _InputIterator2 __first2) 70897403Sobrien { 70997403Sobrien // concept requirements 710132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 711132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 712146897Skan __glibcxx_function_requires(_EqualOpConcept< 713146897Skan typename iterator_traits<_InputIterator1>::value_type, 714132720Skan typename iterator_traits<_InputIterator2>::value_type>) 715132720Skan __glibcxx_requires_valid_range(__first1, __last1); 71697403Sobrien 717132720Skan while (__first1 != __last1 && *__first1 == *__first2) 718132720Skan { 719132720Skan ++__first1; 720132720Skan ++__first2; 721132720Skan } 722132720Skan return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 72397403Sobrien } 72497403Sobrien 72597403Sobrien /** 72697403Sobrien * @brief Finds the places in ranges which don't match. 72797403Sobrien * @param first1 An input iterator. 72897403Sobrien * @param last1 An input iterator. 72997403Sobrien * @param first2 An input iterator. 73097403Sobrien * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink. 73197403Sobrien * @return A pair of iterators pointing to the first mismatch. 73297403Sobrien * 73397403Sobrien * This compares the elements of two ranges using the binary_pred 73497403Sobrien * parameter, and returns a pair 73597403Sobrien * of iterators. The first iterator points into the first range, the 73697403Sobrien * second iterator points into the second range, and the elements pointed 73797403Sobrien * to by the iterators are not equal. 73897403Sobrien */ 739132720Skan template<typename _InputIterator1, typename _InputIterator2, 740132720Skan typename _BinaryPredicate> 741132720Skan pair<_InputIterator1, _InputIterator2> 742132720Skan mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 743132720Skan _InputIterator2 __first2, _BinaryPredicate __binary_pred) 74497403Sobrien { 74597403Sobrien // concept requirements 746132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 747132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 748132720Skan __glibcxx_requires_valid_range(__first1, __last1); 74997403Sobrien 750132720Skan while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) 751132720Skan { 752132720Skan ++__first1; 753132720Skan ++__first2; 754132720Skan } 755132720Skan return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 75697403Sobrien } 75797403Sobrien 75897403Sobrien /** 75997403Sobrien * @brief Tests a range for element-wise equality. 76097403Sobrien * @param first1 An input iterator. 76197403Sobrien * @param last1 An input iterator. 76297403Sobrien * @param first2 An input iterator. 76397403Sobrien * @return A boolean true or false. 76497403Sobrien * 76597403Sobrien * This compares the elements of two ranges using @c == and returns true or 76697403Sobrien * false depending on whether all of the corresponding elements of the 76797403Sobrien * ranges are equal. 76897403Sobrien */ 769132720Skan template<typename _InputIterator1, typename _InputIterator2> 77097403Sobrien inline bool 771132720Skan equal(_InputIterator1 __first1, _InputIterator1 __last1, 772132720Skan _InputIterator2 __first2) 77397403Sobrien { 77497403Sobrien // concept requirements 775132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 776132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 777132720Skan __glibcxx_function_requires(_EqualOpConcept< 778132720Skan typename iterator_traits<_InputIterator1>::value_type, 779132720Skan typename iterator_traits<_InputIterator2>::value_type>) 780132720Skan __glibcxx_requires_valid_range(__first1, __last1); 781169691Skan 782169691Skan for (; __first1 != __last1; ++__first1, ++__first2) 78397403Sobrien if (!(*__first1 == *__first2)) 78497403Sobrien return false; 78597403Sobrien return true; 78697403Sobrien } 78797403Sobrien 78897403Sobrien /** 78997403Sobrien * @brief Tests a range for element-wise equality. 79097403Sobrien * @param first1 An input iterator. 79197403Sobrien * @param last1 An input iterator. 79297403Sobrien * @param first2 An input iterator. 79397403Sobrien * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink. 79497403Sobrien * @return A boolean true or false. 79597403Sobrien * 79697403Sobrien * This compares the elements of two ranges using the binary_pred 79797403Sobrien * parameter, and returns true or 79897403Sobrien * false depending on whether all of the corresponding elements of the 79997403Sobrien * ranges are equal. 80097403Sobrien */ 801132720Skan template<typename _InputIterator1, typename _InputIterator2, 802132720Skan typename _BinaryPredicate> 80397403Sobrien inline bool 804132720Skan equal(_InputIterator1 __first1, _InputIterator1 __last1, 805132720Skan _InputIterator2 __first2, 80697403Sobrien _BinaryPredicate __binary_pred) 80797403Sobrien { 80897403Sobrien // concept requirements 809132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 810132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 811132720Skan __glibcxx_requires_valid_range(__first1, __last1); 81297403Sobrien 813169691Skan for (; __first1 != __last1; ++__first1, ++__first2) 81497403Sobrien if (!__binary_pred(*__first1, *__first2)) 81597403Sobrien return false; 81697403Sobrien return true; 81797403Sobrien } 81897403Sobrien 81997403Sobrien /** 82097403Sobrien * @brief Performs "dictionary" comparison on ranges. 82197403Sobrien * @param first1 An input iterator. 82297403Sobrien * @param last1 An input iterator. 82397403Sobrien * @param first2 An input iterator. 82497403Sobrien * @param last2 An input iterator. 82597403Sobrien * @return A boolean true or false. 82697403Sobrien * 82797403Sobrien * "Returns true if the sequence of elements defined by the range 82897403Sobrien * [first1,last1) is lexicographically less than the sequence of elements 82997403Sobrien * defined by the range [first2,last2). Returns false otherwise." 83097403Sobrien * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, 83197403Sobrien * then this is an inline call to @c memcmp. 83297403Sobrien */ 833132720Skan template<typename _InputIterator1, typename _InputIterator2> 83497403Sobrien bool 835132720Skan lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 836132720Skan _InputIterator2 __first2, _InputIterator2 __last2) 83797403Sobrien { 83897403Sobrien // concept requirements 839132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 840132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 841146897Skan __glibcxx_function_requires(_LessThanOpConcept< 842146897Skan typename iterator_traits<_InputIterator1>::value_type, 843146897Skan typename iterator_traits<_InputIterator2>::value_type>) 844146897Skan __glibcxx_function_requires(_LessThanOpConcept< 845146897Skan typename iterator_traits<_InputIterator2>::value_type, 846132720Skan typename iterator_traits<_InputIterator1>::value_type>) 847132720Skan __glibcxx_requires_valid_range(__first1, __last1); 848132720Skan __glibcxx_requires_valid_range(__first2, __last2); 84997403Sobrien 850169691Skan for (; __first1 != __last1 && __first2 != __last2; 851169691Skan ++__first1, ++__first2) 852132720Skan { 853132720Skan if (*__first1 < *__first2) 854132720Skan return true; 855132720Skan if (*__first2 < *__first1) 856132720Skan return false; 857132720Skan } 85897403Sobrien return __first1 == __last1 && __first2 != __last2; 85997403Sobrien } 86097403Sobrien 86197403Sobrien /** 86297403Sobrien * @brief Performs "dictionary" comparison on ranges. 86397403Sobrien * @param first1 An input iterator. 86497403Sobrien * @param last1 An input iterator. 86597403Sobrien * @param first2 An input iterator. 86697403Sobrien * @param last2 An input iterator. 86797403Sobrien * @param comp A @link s20_3_3_comparisons comparison functor@endlink. 86897403Sobrien * @return A boolean true or false. 86997403Sobrien * 87097403Sobrien * The same as the four-parameter @c lexigraphical_compare, but uses the 87197403Sobrien * comp parameter instead of @c <. 87297403Sobrien */ 873132720Skan template<typename _InputIterator1, typename _InputIterator2, 874132720Skan typename _Compare> 87597403Sobrien bool 876132720Skan lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 877132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 87897403Sobrien _Compare __comp) 87997403Sobrien { 88097403Sobrien // concept requirements 881132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 882132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 883132720Skan __glibcxx_requires_valid_range(__first1, __last1); 884132720Skan __glibcxx_requires_valid_range(__first2, __last2); 88597403Sobrien 886169691Skan for (; __first1 != __last1 && __first2 != __last2; 887169691Skan ++__first1, ++__first2) 888132720Skan { 889132720Skan if (__comp(*__first1, *__first2)) 890132720Skan return true; 891132720Skan if (__comp(*__first2, *__first1)) 892132720Skan return false; 893132720Skan } 89497403Sobrien return __first1 == __last1 && __first2 != __last2; 89597403Sobrien } 89697403Sobrien 897132720Skan inline bool 898132720Skan lexicographical_compare(const unsigned char* __first1, 899132720Skan const unsigned char* __last1, 900132720Skan const unsigned char* __first2, 901132720Skan const unsigned char* __last2) 90297403Sobrien { 903132720Skan __glibcxx_requires_valid_range(__first1, __last1); 904132720Skan __glibcxx_requires_valid_range(__first2, __last2); 905132720Skan 90697403Sobrien const size_t __len1 = __last1 - __first1; 90797403Sobrien const size_t __len2 = __last2 - __first2; 908132720Skan const int __result = std::memcmp(__first1, __first2, 909132720Skan std::min(__len1, __len2)); 91097403Sobrien return __result != 0 ? __result < 0 : __len1 < __len2; 91197403Sobrien } 91297403Sobrien 91397403Sobrien inline bool 91497403Sobrien lexicographical_compare(const char* __first1, const char* __last1, 91597403Sobrien const char* __first2, const char* __last2) 91697403Sobrien { 917132720Skan __glibcxx_requires_valid_range(__first1, __last1); 918132720Skan __glibcxx_requires_valid_range(__first2, __last2); 919132720Skan 92097403Sobrien#if CHAR_MAX == SCHAR_MAX 921132720Skan return std::lexicographical_compare((const signed char*) __first1, 922132720Skan (const signed char*) __last1, 923132720Skan (const signed char*) __first2, 924132720Skan (const signed char*) __last2); 92597403Sobrien#else /* CHAR_MAX == SCHAR_MAX */ 926132720Skan return std::lexicographical_compare((const unsigned char*) __first1, 927132720Skan (const unsigned char*) __last1, 928132720Skan (const unsigned char*) __first2, 929132720Skan (const unsigned char*) __last2); 93097403Sobrien#endif /* CHAR_MAX == SCHAR_MAX */ 93197403Sobrien } 93297403Sobrien 933169691Skan_GLIBCXX_END_NAMESPACE 93497403Sobrien 935132720Skan#endif 936