| // -*- C++ -*- |
| /*************************************************************************** |
| * |
| * algorithm - declarations and inline definitions of the C++ Standard |
| * Library algorithms |
| * |
| * $Id$ |
| * |
| *************************************************************************** |
| * |
| * Copyright (c) 1994 |
| * Hewlett-Packard Company |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Hewlett-Packard Company makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| * |
| *************************************************************************** |
| * |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed |
| * with this work for additional information regarding copyright |
| * ownership. The ASF licenses this file to you under the Apache |
| * License, Version 2.0 (the "License"); you may not use this file |
| * except in compliance with the License. You may obtain a copy of |
| * the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or |
| * implied. See the License for the specific language governing |
| * permissions and limitations under the License. |
| * |
| * Copyright 1994-2006 Rogue Wave Software. |
| * |
| **************************************************************************/ |
| |
| #ifndef _RWSTD_ALGORITHM_INCLUDED |
| #define _RWSTD_ALGORITHM_INCLUDED |
| |
| #include <rw/_algobase.h> |
| #include <rw/_iterbase.h> |
| #include <rw/_heap.h> |
| #include <rw/_pair.h> |
| #include <rw/_rawiter.h> |
| #include <rw/_defs.h> |
| |
| |
| #ifdef _INLINE_RECURSIVE |
| # define _INLINE inline |
| #else |
| # define _INLINE |
| #endif |
| |
| |
| _RWSTD_NAMESPACE (__rw) { |
| |
| _RWSTD_EXPORT _RWSTD_SIZE_T __rw_rand (_RWSTD_SIZE_T); |
| |
| } // namespace __rw |
| |
| |
| _RWSTD_NAMESPACE (std) { |
| |
| |
| // 25.1 - Non-modifying sequence operations [lib.alg.nonmodifying] |
| |
| // 25.1.1 - For Each [lib.alg.foreach] |
| template <class _InputIter, class _Function> |
| inline _Function |
| for_each (_InputIter __first, _InputIter __last, _Function __fun) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for ( ; !(__first == __last); ++__first) |
| __fun (*__first); |
| |
| return __fun; |
| } |
| |
| |
| // 25.1.2 - Find [lib.alg.find] |
| |
| template <class _InputIter, class _TypeT> |
| inline _InputIter |
| find (_InputIter __first, _InputIter __last, const _TypeT &__val) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for (; !(__first == __last) && !(*__first == __val); ++__first); |
| |
| return __first; |
| } |
| |
| |
| template <class _InputIter, class _Predicate> |
| inline _InputIter |
| find_if (_InputIter __first, _InputIter __last, _Predicate __pred) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for (; !(__first == __last) && __pred (*__first) == false; ++__first); |
| |
| return __first; |
| } |
| |
| |
| // helpers to work around the lack of iterator_traits |
| _EXPORT |
| template <class _FwdIter1, class _FwdIter2, class _Dist> |
| _FwdIter1 __find_end (_FwdIter1, _FwdIter1, _FwdIter2, _FwdIter2, _Dist*); |
| |
| _EXPORT |
| template <class _FwdIter1, class _FwdIter2, |
| class _BinaryPredicate, class _Dist> |
| _FwdIter1 __find_end (_FwdIter1, _FwdIter1, _FwdIter2, _FwdIter2, |
| _BinaryPredicate, _Dist*); |
| |
| |
| // 25.1.3 - Find End [lib.alg.find.end] |
| |
| template <class _FwdIter1, class _FwdIter2> |
| inline _FwdIter1 find_end (_FwdIter1 __first1, _FwdIter1 __last1, |
| _FwdIter2 __first2, _FwdIter2 __last2) |
| { |
| _RWSTD_ASSERT_RANGE (__first1, __last1); |
| _RWSTD_ASSERT_RANGE (__first2, __last2); |
| |
| return __find_end (__first1, __last1, __first2, __last2, |
| _RWSTD_DIFFERENCE_TYPE (_FwdIter1)); |
| } |
| |
| |
| template <class _FwdIter1, class _FwdIter2, class _BinaryPredicate> |
| inline _FwdIter1 find_end (_FwdIter1 __first1, _FwdIter1 __last1, |
| _FwdIter2 __first2, _FwdIter2 __last2, |
| _BinaryPredicate __pred) |
| { |
| _RWSTD_ASSERT_RANGE (__first1, __last1); |
| _RWSTD_ASSERT_RANGE (__first2, __last2); |
| |
| return __find_end (__first1, __last1, __first2, __last2, |
| __pred, _RWSTD_DIFFERENCE_TYPE (_FwdIter1)); |
| } |
| |
| // 25.1.4 - Find First [lib.alg.find.first.of] |
| |
| _EXPORT |
| template <class _FwdIter1, class _FwdIter2> |
| _FwdIter1 find_first_of (_FwdIter1, _FwdIter1, _FwdIter2, _FwdIter2); |
| |
| _EXPORT |
| template <class _FwdIter1, class _FwdIter2, class _BinaryPred> |
| _FwdIter1 find_first_of (_FwdIter1,_FwdIter1, _FwdIter2, _FwdIter2, |
| _BinaryPred); |
| |
| |
| // 25.1.5 - Adjacent Find [lib.alg.adjacent.find] |
| |
| _EXPORT |
| template <class _FwdIter> |
| _FwdIter adjacent_find (_FwdIter, _FwdIter); |
| |
| _EXPORT |
| template <class _FwdIter, class _BinaryPredicate> |
| _FwdIter adjacent_find (_FwdIter, _FwdIter, _BinaryPredicate); |
| |
| |
| #ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC |
| |
| // 25.1.6 - Count [lib.alg.count] |
| |
| template <class _InputIter, class _TypeT> |
| inline _TYPENAME iterator_traits<_InputIter>::difference_type |
| count (_InputIter __first, _InputIter __last, const _TypeT &__val) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| _TYPENAME iterator_traits<_InputIter>::difference_type __n = 0; |
| for ( ; !(__first == __last); ++__first) |
| if (*__first == __val) |
| ++__n; |
| return __n; |
| } |
| |
| |
| template <class _InputIter, class _Predicate> |
| inline _TYPENAME iterator_traits<_InputIter>::difference_type |
| count_if (_InputIter __first, _InputIter __last, _Predicate __pred) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| _TYPENAME iterator_traits<_InputIter>::difference_type __n = 0; |
| for ( ; !(__first == __last); ++__first) |
| if (!(__pred (*__first) == false)) |
| ++__n; |
| return __n; |
| } |
| |
| #endif // _RWSTD_NO_CLASS_PARTIAL_SPEC |
| |
| |
| // provided as a backward-compatibility extension (or as a workaround) |
| #if !defined (_RWSTD_NO_EXT_VOID_COUNT) \ |
| || defined (_RWSTD_NO_CLASS_PARTIAL_SPEC) |
| |
| template <class _InputIter, class _TypeT, class _Size> |
| inline void count (_InputIter __first, _InputIter __last, |
| const _TypeT &__val, _Size& __n) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for ( ; !(__first == __last); ++__first) |
| if (*__first == __val) |
| ++__n; |
| } |
| |
| |
| template <class _InputIter, class _Predicate, class _Size> |
| inline void count_if (_InputIter __first, _InputIter __last, |
| _Predicate __pred, _Size& __n) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for ( ; !(__first == __last); ++__first) |
| if (!(__pred (*__first) == false)) |
| ++__n; |
| } |
| |
| #endif // !_RWSTD_NO_EXT_VOID_COUNT || _RWSTD_NO_CLASS_PARTIAL_SPEC |
| |
| |
| // 25.1.7 - Mismatch [lib.mismatch] |
| // 25.1.8 - Equal [lib.alg.equal] |
| // defined in <rw/_algobase.h> |
| |
| |
| // helpers to work around the lack of iterator_traits |
| _EXPORT |
| template <class _FwdIter1, class _FwdIter2, class _Dist1, class _Dist2> |
| _FwdIter1 __search (_FwdIter1, _FwdIter1, _FwdIter2, _FwdIter2, |
| _Dist1*, _Dist2*); |
| |
| _EXPORT |
| template <class _FwdIter1, class _FwdIter2, |
| class _BinaryPredicate, class Distance1, class Distance2> |
| _FwdIter1 __search (_FwdIter1, _FwdIter1, _FwdIter2, _FwdIter2, |
| _BinaryPredicate, Distance1*, Distance2*); |
| |
| // 25.1.9 - Search [lib.alg.search] |
| |
| // 25.1.9, p1 |
| template <class _FwdIter1, class _FwdIter2> |
| inline _FwdIter1 search (_FwdIter1 __first1, _FwdIter1 __last1, |
| _FwdIter2 __first2, _FwdIter2 __last2) |
| { |
| return __search (__first1, __last1, __first2, __last2, |
| _RWSTD_DIFFERENCE_TYPE (_FwdIter1), |
| _RWSTD_DIFFERENCE_TYPE (_FwdIter2)); |
| } |
| |
| |
| template <class _FwdIter1, class _FwdIter2, class _BinaryPredicate> |
| inline _FwdIter1 search (_FwdIter1 __first1,_FwdIter1 __last1, |
| _FwdIter2 __first2,_FwdIter2 __last2, |
| _BinaryPredicate __pred) |
| { |
| return __search (__first1, __last1, __first2, __last2, __pred, |
| _RWSTD_DIFFERENCE_TYPE (_FwdIter1), |
| _RWSTD_DIFFERENCE_TYPE (_FwdIter2)); |
| } |
| |
| |
| // helper to work around the lack of iterator_traits |
| _EXPORT |
| template <class _FwdIter, class _Dist, class _Size, class _TypeT> |
| _FwdIter __search_n (_FwdIter, _FwdIter, _Dist*, _Size, const _TypeT&); |
| |
| _EXPORT |
| template <class _FwdIter, class _Dist, class _Size, class _TypeT, |
| class _BinaryPredicate> |
| _FwdIter __search_n (_FwdIter, _FwdIter, _Dist*, _Size, |
| const _TypeT&, _BinaryPredicate); |
| |
| // 25.1.9, p4 |
| template <class _FwdIter, class _Size, class _TypeT> |
| inline _FwdIter search_n (_FwdIter __first, _FwdIter __last, |
| _Size __count, const _TypeT &__val) |
| { |
| if (__count) |
| return __search_n (__first, __last, _RWSTD_DIFFERENCE_TYPE (_FwdIter), |
| __count, __val); |
| return __first; |
| } |
| |
| |
| template <class _FwdIter, class _Size, class _TypeT, class _BinaryPredicate> |
| inline _FwdIter search_n (_FwdIter __first, _FwdIter __last, |
| _Size __count, const _TypeT &__val, |
| _BinaryPredicate __pred) |
| { |
| if (__count) |
| return __search_n (__first, __last, |
| _RWSTD_DIFFERENCE_TYPE (_FwdIter), |
| __count, __val, __pred); |
| return __first; |
| } |
| |
| |
| // 25.2 - Mutating sequence operations [lib.alg.modifying,operations] |
| |
| // 25.2.1 - Copy [lib.alg.copy] |
| // 25.2.2, p1 swap |
| // defined in <rw/_algobase.h> |
| |
| // 25.2.2, p3 |
| template <class _FwdIter1, class _FwdIter2> |
| inline _FwdIter2 |
| swap_ranges (_FwdIter1 __first1, _FwdIter1 __last1, _FwdIter2 __first2) |
| { |
| _RWSTD_ASSERT_RANGE (__first1, __last1); |
| |
| for (; !(__first1 == __last1); ++__first1, ++__first2) |
| _STD::iter_swap (__first1, __first2); |
| return __first2; |
| } |
| |
| |
| // 25.2.3 - Transform [lib.alg.transform] |
| |
| template <class _InputIter, class _OutputIter, class _UnaryOperation> |
| inline _OutputIter |
| transform (_InputIter __first, _InputIter __last, _OutputIter __res, |
| _UnaryOperation __unary_op) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for (; !(__first == __last); ++__res, ++__first) |
| *__res = __unary_op (*__first); |
| return __res; |
| } |
| |
| |
| template <class _InputIter1, class _InputIter2, |
| class _OutputIter, class _BinaryOperation> |
| inline _OutputIter |
| transform (_InputIter1 __first1, _InputIter1 __last1, |
| _InputIter2 __first2, _OutputIter __res, |
| _BinaryOperation __binary_op) |
| { |
| _RWSTD_ASSERT_RANGE (__first1, __last1); |
| |
| for (; !(__first1 == __last1); ++__res, ++__first1, ++__first2) |
| *__res = __binary_op (*__first1, *__first2); |
| return __res; |
| } |
| |
| |
| // 25.2.4 - Replace [lib.alg.replace] |
| |
| template <class _FwdIter, class _TypeT> |
| inline void replace (_FwdIter __first, _FwdIter __last, |
| const _TypeT& __old_value, const _TypeT& __new_value) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for (; !(__first == __last); ++__first) |
| if (*__first == __old_value) |
| *__first = __new_value; |
| } |
| |
| |
| template <class _FwdIter, class _Predicate, class _TypeT> |
| inline void replace_if (_FwdIter __first, _FwdIter __last, |
| _Predicate __pred, const _TypeT& __new_value) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for (; !(__first == __last); ++__first) |
| if (!(__pred (*__first) == false)) |
| *__first = __new_value; |
| } |
| |
| |
| template <class _InputIter, class _OutputIter, class _TypeT> |
| inline _OutputIter |
| replace_copy (_InputIter __first, _InputIter __last, _OutputIter __res, |
| const _TypeT& __old_value, const _TypeT& __new_value) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for (; !(__first == __last); ++__first, ++__res) |
| *__res = *__first == __old_value ? __new_value : *__first; |
| return __res; |
| } |
| |
| _EXPORT |
| template <class _Iter, class _OutputIter, class _Predicate, class _TypeT> |
| _OutputIter replace_copy_if (_Iter, _Iter, _OutputIter, _Predicate, |
| const _TypeT&); |
| |
| // 25.2.5 - Fill [lib.alg.fill] |
| // defined in <rw/_algobase.h> |
| |
| // 25.2.6 - Generate [lib.alg.generate] |
| |
| template <class _FwdIter, class _Generator> |
| inline void generate (_FwdIter __first, _FwdIter __last, _Generator __gen) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for (; !(__first == __last); ++__first) |
| *__first = __gen (); |
| } |
| |
| |
| template <class _OutputIter, class _Size, class _Generator> |
| inline void generate_n (_OutputIter __first, _Size __n, _Generator __gen) |
| { |
| // Size must be convertible to integral type but need not itself be one |
| // Complexity: |
| // Exactly n if n is positive, or 0 otherwise, assignments. |
| // (see lwg issue 426 for the complexity when n is not positive) |
| for (_RWSTD_PTRDIFF_T __inx = __n; 0 < __inx; --__inx, ++__first) |
| *__first = __gen (); |
| } |
| |
| |
| // 25.2.7 - Remove [lib.alg.remove] |
| _EXPORT |
| template <class _InputIter, class _OutputIter, class _TypeT> |
| _OutputIter remove_copy (_InputIter, _InputIter, _OutputIter, |
| const _TypeT&); |
| |
| _EXPORT |
| template <class _InputIter, class _OutputIter, class _Predicate> |
| _OutputIter remove_copy_if (_InputIter, _InputIter, _OutputIter, _Predicate); |
| |
| |
| template <class _FwdIter, class _TypeT> |
| inline _FwdIter |
| remove (_FwdIter __first, _FwdIter __last, const _TypeT &__val) |
| { |
| __first = _STD::find (__first, __last, __val); |
| _FwdIter __next = __first; |
| return __first == __last ? |
| __first : _STD::remove_copy (++__next, __last, __first, __val); |
| } |
| |
| |
| template <class _FwdIter, class _Predicate> |
| inline _FwdIter remove_if (_FwdIter __first, _FwdIter __last, _Predicate __pred) |
| { |
| __first = _STD::find_if (__first, __last, __pred); |
| _FwdIter __next = __first; |
| return __first == __last ? |
| __first : _STD::remove_copy_if (++__next, __last, __first, __pred); |
| } |
| |
| |
| _EXPORT |
| template <class _InputIter, class _FwdIter> |
| _FwdIter __unique_copy (_InputIter, _InputIter, _FwdIter, forward_iterator_tag); |
| |
| |
| template <class _InputIter, class _BidirIter> |
| inline _BidirIter |
| __unique_copy (_InputIter __first, _InputIter __last, _BidirIter __res, |
| bidirectional_iterator_tag) |
| { |
| return __unique_copy (__first, __last, __res, forward_iterator_tag ()); |
| } |
| |
| |
| template <class _InputIter, class _RandomAccessIter> |
| inline _RandomAccessIter |
| __unique_copy (_InputIter __first, _InputIter __last, |
| _RandomAccessIter __res, random_access_iterator_tag) |
| { |
| return __unique_copy (__first, __last, __res, forward_iterator_tag ()); |
| } |
| |
| _EXPORT |
| template <class _InputIter, class _OutputIter, class _TypeT> |
| _OutputIter __unique_copy (_InputIter, _InputIter, _OutputIter, _TypeT*); |
| |
| |
| template <class _InputIter, class _OutputIter> |
| inline _OutputIter __unique_copy (_InputIter __first, _InputIter __last, |
| _OutputIter __res, output_iterator_tag) |
| { |
| return __unique_copy (__first, __last, __res, |
| _RWSTD_VALUE_TYPE (_InputIter)); |
| } |
| |
| |
| _EXPORT |
| template <class _InputIter, class _FwdIter, class _BinaryPredicate> |
| _FwdIter __unique_copy (_InputIter, _InputIter, _FwdIter, _BinaryPredicate, |
| forward_iterator_tag); |
| |
| |
| template <class _InputIter, class _BidirIter, class _BinaryPredicate> |
| inline _BidirIter |
| __unique_copy (_InputIter __first, _InputIter __last, _BidirIter __res, |
| _BinaryPredicate __pred, bidirectional_iterator_tag) |
| { |
| return __unique_copy (__first, __last, __res, __pred, |
| forward_iterator_tag ()); |
| } |
| |
| |
| template <class _InputIter, class _RandomAccessIter, class _BinaryPredicate> |
| inline _RandomAccessIter |
| __unique_copy (_InputIter __first, _InputIter __last, _RandomAccessIter __res, |
| _BinaryPredicate __pred, random_access_iterator_tag) |
| { |
| return __unique_copy (__first, __last, __res, __pred, |
| forward_iterator_tag ()); |
| } |
| |
| |
| _EXPORT |
| template <class _InputIter, class _OutputIter, class _BinaryPredicate, |
| class _TypeT> |
| _OutputIter __unique_copy (_InputIter, _InputIter, _OutputIter, |
| _BinaryPredicate, _TypeT*); |
| |
| template <class _InputIter, class _OutputIter, class _BinaryPredicate> |
| inline _OutputIter |
| __unique_copy (_InputIter __first, _InputIter __last, _OutputIter __res, |
| _BinaryPredicate __pred, output_iterator_tag) |
| { |
| return __unique_copy (__first, __last, __res, __pred, |
| _RWSTD_VALUE_TYPE (_InputIter)); |
| } |
| |
| |
| // 25.2.8 - Unique [lib.alg.unique] |
| |
| _EXPORT |
| template <class _FwdIter> |
| _FwdIter |
| unique (_FwdIter, _FwdIter); |
| |
| |
| _EXPORT |
| template <class _FwdIter, class _BinaryPredicate> |
| _FwdIter |
| unique (_FwdIter, _FwdIter, _BinaryPredicate); |
| |
| |
| template <class _InputIter, class _OutputIter> |
| inline _OutputIter |
| unique_copy (_InputIter __first, _InputIter __last, _OutputIter __res) |
| { |
| return __unique_copy (__first, __last, __res, |
| _RWSTD_ITERATOR_CATEGORY (_OutputIter, __res)); |
| } |
| |
| |
| template <class _InputIter, class _OutputIter, class _BinaryPredicate> |
| inline _OutputIter |
| unique_copy (_InputIter __first, _InputIter __last, _OutputIter __res, |
| _BinaryPredicate __pred) |
| { |
| return __unique_copy (__first, __last, __res, __pred, |
| _RWSTD_ITERATOR_CATEGORY (_OutputIter, __res)); |
| } |
| |
| |
| template <class _BidirIter> |
| inline void |
| __reverse (_BidirIter __first, _BidirIter __last, |
| bidirectional_iterator_tag) |
| { |
| // 25.2.9, p2: Complexity: exactly (last - first) / 2 calls |
| // to std::iter_swap() |
| for (; !(__first == __last) && !(__first == --__last); ++__first) |
| _STD::iter_swap (__first, __last); |
| } |
| |
| |
| template <class _RandomAccessIter> |
| inline void |
| __reverse (_RandomAccessIter __first, _RandomAccessIter __last, |
| random_access_iterator_tag) |
| { |
| // 25.2.9, p2: Complexity: exactly (last - first) / 2 calls |
| // to std::iter_swap() |
| if (!(__first == __last)) |
| for (; __first < --__last; ++__first) |
| _STD::iter_swap (__first, __last); |
| } |
| |
| |
| template <class _BidirIter> |
| inline void |
| reverse (_BidirIter __first, _BidirIter __last) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| __reverse (__first, __last, _RWSTD_ITERATOR_CATEGORY (_BidirIter, __first)); |
| } |
| |
| |
| template <class _BidirIter, class _OutputIter> |
| inline _OutputIter |
| reverse_copy (_BidirIter __first, _BidirIter __last, _OutputIter __res) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for (; !(__first == __last); ++__res) |
| *__res = *--__last; |
| return __res; |
| } |
| |
| |
| _EXPORT |
| template <class _FwdIter, class _Dist> |
| void __rotate (_FwdIter, _FwdIter, _FwdIter, _Dist*, forward_iterator_tag); |
| |
| |
| template <class _BidirIter, class _Dist> |
| inline void |
| __rotate (_BidirIter __first, _BidirIter __middle, _BidirIter __last, |
| _Dist*, bidirectional_iterator_tag) |
| { |
| _STD::reverse (__first, __middle); |
| _STD::reverse (__middle, __last); |
| _STD::reverse (__first, __last); |
| } |
| |
| |
| _EXPORT |
| template <class _EuclideanRingElement> |
| _EuclideanRingElement |
| __gcd (_EuclideanRingElement, _EuclideanRingElement); |
| |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _Dist, class _TypeT> |
| void __rotate_cycle (_RandomAccessIter, _RandomAccessIter, _RandomAccessIter, |
| _Dist, _TypeT*); |
| |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _Dist> |
| void __rotate (_RandomAccessIter, _RandomAccessIter, _RandomAccessIter, |
| _Dist*, random_access_iterator_tag); |
| |
| |
| template <class _FwdIter> |
| inline void rotate (_FwdIter __first, _FwdIter __middle, _FwdIter __last) |
| { |
| if (!(__first == __middle || __middle == __last)) |
| __rotate (__first, __middle, __last, |
| _RWSTD_DIFFERENCE_TYPE (_FwdIter), |
| _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first)); |
| } |
| |
| |
| template <class _FwdIter, class _OutputIter> |
| inline _OutputIter |
| rotate_copy (_FwdIter __first, _FwdIter __middle, _FwdIter __last, |
| _OutputIter __res) |
| { |
| return _STD::copy (__first, __middle, _STD::copy (__middle, __last, __res)); |
| } |
| |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _RandomNumberGenerator> |
| void random_shuffle (_RandomAccessIter, _RandomAccessIter, |
| _RandomNumberGenerator&); |
| |
| |
| template <class _RandomAccessIter> |
| inline void |
| random_shuffle (_RandomAccessIter __first, _RandomAccessIter __last) |
| { |
| _RWSTD_SIZE_T (*__rand) (_RWSTD_SIZE_T) = _RW::__rw_rand; |
| |
| _STD::random_shuffle (__first, __last, __rand); |
| } |
| |
| |
| _EXPORT |
| template <class _BidirIter, class _Predicate> |
| _BidirIter partition (_BidirIter, _BidirIter, _Predicate); |
| |
| |
| _EXPORT |
| template <class _BidirIter, class _Predicate, class _TypeT, class _Dist> |
| _BidirIter |
| __stable_partition (_BidirIter, _BidirIter, _Predicate, _TypeT*, _Dist*); |
| |
| template <class _BidirIter, class _Predicate> |
| inline _BidirIter |
| stable_partition (_BidirIter __first, _BidirIter __last, _Predicate __pred) |
| { |
| return __stable_partition (__first, __last, __pred, |
| _RWSTD_VALUE_TYPE (_BidirIter), |
| _RWSTD_DIFFERENCE_TYPE (_BidirIter)); |
| } |
| |
| |
| // 25.3.1 - Sorting [lib.alg.sort] |
| |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _TypeT, class _Compare> |
| void __unguarded_linear_insert (_RandomAccessIter, _TypeT, _Compare); |
| |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _Compare> |
| void __insertion_sort (_RandomAccessIter, _RandomAccessIter, _Compare); |
| |
| template <class _RandomAccessIter, class _Compare> |
| inline void |
| __unguarded_insertion_sort (_RandomAccessIter __first, _RandomAccessIter __last, |
| _Compare __comp) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| |
| for (_RandomAccessIter __i = __first; !(__i == __last); ++__i) |
| __unguarded_linear_insert (__i, *__i, __comp); |
| } |
| |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _Dist, class _Compare> |
| void __introsort_loop (_RandomAccessIter, _RandomAccessIter, _Dist, _Compare); |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _Compare> |
| void __final_insertion_sort (_RandomAccessIter, _RandomAccessIter, _Compare); |
| |
| |
| // 25.3.1.1 |
| template <class _RandomAccessIter, class _Compare> |
| inline void |
| sort (_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) |
| { |
| if (!(__first == __last)) { |
| // introsort guarantees O(N * log(N)) in the worst case |
| __introsort_loop (__first, __last, __last - __first, __comp); |
| __final_insertion_sort (__first, __last, __comp); |
| } |
| } |
| |
| |
| template <class _RandomAccessIter> |
| inline void sort (_RandomAccessIter __first, _RandomAccessIter __last) |
| { |
| _STD::sort (__first, __last, _RWSTD_LESS (_RandomAccessIter)); |
| } |
| |
| |
| _EXPORT |
| template <class _BidirIter, class _Dist, class _Compare> |
| void __merge_without_buffer (_BidirIter, _BidirIter, _BidirIter, |
| _Dist, _Dist, _Compare); |
| |
| template <class _RandomAccessIter, class _Compare> |
| _INLINE void |
| __inplace_stable_sort (_RandomAccessIter __first, _RandomAccessIter __last, |
| _Compare __comp) |
| { |
| if (__last - __first < 15) |
| __insertion_sort (__first, __last, __comp); |
| else { |
| _RandomAccessIter __middle = __first + (__last - __first) / 2; |
| __inplace_stable_sort (__first, __middle, __comp); |
| __inplace_stable_sort (__middle, __last, __comp); |
| __merge_without_buffer (__first, __middle, __last, |
| __middle - __first, __last - __middle, __comp); |
| } |
| } |
| |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _TypeT, class _Dist, class _Compare> |
| void |
| __stable_sort (_RandomAccessIter, _RandomAccessIter, _TypeT*, _Dist*, _Compare); |
| |
| |
| // 25.3.1.2 |
| template <class _RandomAccessIter, class _Compare> |
| inline void stable_sort (_RandomAccessIter __first, _RandomAccessIter __last, |
| _Compare __comp) |
| { |
| if (!(__first == __last)) |
| __stable_sort (__first, __last, |
| _RWSTD_VALUE_TYPE (_RandomAccessIter), |
| _RWSTD_DIFFERENCE_TYPE (_RandomAccessIter), __comp); |
| } |
| |
| |
| template <class _RandomAccessIter> |
| inline void stable_sort (_RandomAccessIter __first, _RandomAccessIter __last) |
| { |
| _STD::stable_sort (__first, __last, _RWSTD_LESS (_RandomAccessIter)); |
| } |
| |
| |
| // helper to work around the lack of iterator_traits |
| _EXPORT |
| template <class _RandomAccessIter, class _TypeT, class _Compare> |
| void __partial_sort (_RandomAccessIter, _RandomAccessIter, |
| _RandomAccessIter, _TypeT*, _Compare); |
| |
| // 25.3.1.3 |
| template <class _RandomAccessIter, class _Compare> |
| inline void partial_sort (_RandomAccessIter __first, |
| _RandomAccessIter __middle, |
| _RandomAccessIter __last, _Compare __comp) |
| { |
| _RWSTD_ASSERT_RANGE (__first, __last); |
| _RWSTD_ASSERT_RANGE (__first, __middle); |
| |
| if (!(__first == __middle)) |
| __partial_sort (__first, __middle, __last, |
| _RWSTD_VALUE_TYPE(_RandomAccessIter), |
| __comp); |
| } |
| |
| template <class _RandomAccessIter> |
| inline void |
| partial_sort (_RandomAccessIter __first, _RandomAccessIter __middle, |
| _RandomAccessIter __last) |
| { |
| _STD::partial_sort (__first, __middle, __last, |
| _RWSTD_LESS (_RandomAccessIter)); |
| } |
| |
| |
| // helper to work around the lack of iterator_traits |
| _EXPORT |
| template <class _InputIter, class _RandomAccessIter, class _Compare, |
| class _Dist, class _TypeT> |
| _RandomAccessIter |
| __partial_sort_copy (_InputIter, _InputIter, |
| _RandomAccessIter, _RandomAccessIter, |
| _Compare, _Dist*, _TypeT*); |
| |
| |
| // 25.3.1.4 |
| template <class _InputIter, class _RandomAccessIter, class _Compare> |
| inline _RandomAccessIter |
| partial_sort_copy (_InputIter __first, _InputIter __last, |
| _RandomAccessIter __res_first, |
| _RandomAccessIter __res_last, _Compare __comp) |
| { |
| return __first == __last ? __res_first : |
| __partial_sort_copy (__first, __last, __res_first, __res_last, __comp, |
| _RWSTD_DIFFERENCE_TYPE (_RandomAccessIter), |
| _RWSTD_VALUE_TYPE (_RandomAccessIter)); |
| } |
| |
| |
| template <class _InputIter, class _RandomAccessIter> |
| inline _RandomAccessIter |
| partial_sort_copy (_InputIter __first1, _InputIter __last1, |
| _RandomAccessIter __first2, _RandomAccessIter __last2) |
| { |
| return _STD::partial_sort_copy (__first1, __last1, __first2, __last2, |
| _RWSTD_LESS (_InputIter)); |
| } |
| |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _TypeT, class _Compare> |
| void __nth_element (_RandomAccessIter, _RandomAccessIter, |
| _RandomAccessIter, _TypeT*, _Compare); |
| |
| // 25.3.2 - Nth element [lib.alg.nth.element] |
| |
| template <class _RandomAccessIter, class _Compare> |
| inline void nth_element (_RandomAccessIter __first, _RandomAccessIter __nth, |
| _RandomAccessIter __last, _Compare __comp) |
| { |
| if (!(__first == __last)) |
| __nth_element (__first, __nth, __last, |
| _RWSTD_VALUE_TYPE (_RandomAccessIter), __comp); |
| } |
| |
| template <class _RandomAccessIter> |
| inline void nth_element (_RandomAccessIter __first, _RandomAccessIter __nth, |
| _RandomAccessIter __last) |
| { |
| _STD::nth_element (__first, __nth, __last, _RWSTD_LESS (_RandomAccessIter)); |
| } |
| |
| |
| // 25.3.3 - Binary search [lib.alg.binary.search] |
| |
| _EXPORT |
| template <class _FwdIter, class _TypeT, class _Compare, class _Dist> |
| _FwdIter __lower_bound (_FwdIter, _FwdIter, const _TypeT&, _Compare, |
| _Dist*, forward_iterator_tag); |
| |
| |
| template <class _FwdIter, class _TypeT, class _Compare, class _Dist> |
| inline _FwdIter |
| __lower_bound (_FwdIter __first, _FwdIter __last, |
| const _TypeT &__val, _Compare __comp, _Dist*, |
| bidirectional_iterator_tag) |
| { |
| return __lower_bound (__first, __last, __val, __comp, |
| (_Dist*)0, forward_iterator_tag ()); |
| } |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _TypeT, class _Compare, class _Dist> |
| _RandomAccessIter __lower_bound (_RandomAccessIter, _RandomAccessIter, |
| const _TypeT&, _Compare, _Dist*, |
| random_access_iterator_tag); |
| |
| // 25.3.3.1 |
| template <class _FwdIter, class _TypeT, class _Compare> |
| inline _FwdIter |
| lower_bound (_FwdIter __first,_FwdIter __last, |
| const _TypeT &__val, _Compare __comp) |
| { |
| return __lower_bound (__first, __last, __val, __comp, |
| _RWSTD_DIFFERENCE_TYPE (_FwdIter), |
| _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first)); |
| } |
| |
| |
| template <class _FwdIter, class _TypeT> |
| inline _FwdIter |
| lower_bound (_FwdIter __first, _FwdIter __last, const _TypeT &__val) |
| { |
| return _STD::lower_bound (__first, __last, __val, |
| _RWSTD_LESS (_FwdIter)); |
| } |
| |
| |
| _EXPORT |
| template <class _FwdIter, class _TypeT, class _Compare, class _Dist> |
| _FwdIter __upper_bound (_FwdIter, _FwdIter, const _TypeT&, _Compare, |
| _Dist*, forward_iterator_tag); |
| |
| |
| template <class _FwdIter, class _TypeT, class _Compare, class _Dist> |
| inline _FwdIter |
| __upper_bound (_FwdIter __first, _FwdIter __last, const _TypeT &__val, |
| _Compare __comp, _Dist*, bidirectional_iterator_tag) |
| { |
| return __upper_bound (__first, __last, __val, __comp, |
| (_Dist*)0, forward_iterator_tag ()); |
| } |
| |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _TypeT, class _Compare, |
| class _Dist> |
| _RandomAccessIter __upper_bound (_RandomAccessIter, _RandomAccessIter, |
| const _TypeT&, _Compare, _Dist*, |
| random_access_iterator_tag); |
| |
| // 25.3.3.2 |
| template <class _FwdIter, class _TypeT, class _Compare> |
| inline _FwdIter |
| upper_bound (_FwdIter __first,_FwdIter __last, |
| const _TypeT &__val, _Compare __comp) |
| { |
| return __upper_bound (__first, __last, __val, __comp, |
| _RWSTD_DIFFERENCE_TYPE (_FwdIter), |
| _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first)); |
| } |
| |
| |
| template <class _FwdIter, class _TypeT> |
| inline _FwdIter |
| upper_bound (_FwdIter __first, _FwdIter __last, const _TypeT &__val) |
| { |
| return _STD::upper_bound (__first, __last, __val, |
| _RWSTD_LESS (_FwdIter)); |
| } |
| |
| |
| _EXPORT |
| template <class _FwdIter, class _TypeT, class _Compare, class _Dist> |
| pair<_FwdIter, _FwdIter> |
| __equal_range (_FwdIter, _FwdIter, const _TypeT&, |
| _Compare, _Dist*, forward_iterator_tag); |
| |
| |
| template <class _FwdIter, class _TypeT, class _Compare, class _Dist> |
| inline pair<_FwdIter, _FwdIter> |
| __equal_range (_FwdIter __first, _FwdIter __last, const _TypeT &__val, |
| _Compare __comp, _Dist*, bidirectional_iterator_tag) |
| { |
| return __equal_range (__first, __last, __val, __comp, |
| (_Dist*)0, forward_iterator_tag()); |
| } |
| |
| |
| _EXPORT |
| template <class _RandomAccessIter, class _TypeT, class _Compare, class _Dist> |
| pair<_RandomAccessIter, _RandomAccessIter> |
| __equal_range (_RandomAccessIter, _RandomAccessIter, |
| const _TypeT&, _Compare, _Dist*, random_access_iterator_tag); |
| |
| |
| // 25.3.3.3 |
| template <class _FwdIter, class _TypeT, class _Compare> |
| inline pair<_FwdIter, _FwdIter> |
| equal_range (_FwdIter __first, _FwdIter __last, |
| const _TypeT &__val, _Compare __comp) |
| { |
| return __equal_range (__first, __last, __val, __comp, |
| _RWSTD_DIFFERENCE_TYPE (_FwdIter), |
| _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first)); |
| } |
| |
| template <class _FwdIter, class _TypeT> |
| inline pair<_FwdIter, _FwdIter> |
| equal_range (_FwdIter __first, _FwdIter __last, const _TypeT &__val) |
| { |
| return _STD::equal_range (__first, __last, __val, _RWSTD_LESS (_FwdIter)); |
| } |
| |
| |
| // 25.3.3.4 |
| template <class _FwdIter, class _TypeT, class _Compare> |
| inline bool binary_search (_FwdIter __first, _FwdIter __last, |
| const _TypeT &__val, _Compare __comp) |
| { |
| _FwdIter __i = _STD::lower_bound (__first, __last, __val, __comp); |
| return !(__i == __last) && !__comp(__val, *__i); |
| } |
| |
| |
| template <class _FwdIter, class _TypeT> |
| inline bool |
| binary_search (_FwdIter __first, _FwdIter __last, const _TypeT &__val) |
| { |
| return _STD::binary_search (__first, __last, __val, _RWSTD_LESS (_FwdIter)); |
| } |
| |
| |
| // 25.3.4 - Merge [lib.alg.merge] |
| |
| _EXPORT |
| template <class _InputIter1, class _InputIter2, class _OutputIter, |
| class _Compare> |
| _OutputIter merge (_InputIter1 __first1, _InputIter1 __last1, |
| _InputIter2 __first2, _InputIter2 __last2, |
| _OutputIter __res, _Compare __comp); |
| |
| template <class _InputIter1, class _InputIter2, class _OutputIter> |
| inline _OutputIter merge (_InputIter1 __first1, _InputIter1 __last1, |
| _InputIter2 __first2, _InputIter2 __last2, |
| _OutputIter __res) |
| { |
| return _STD::merge (__first1, __last1, __first2, __last2, __res, |
| _RWSTD_LESS (_InputIter1)); |
| } |
| |
| |
| _EXPORT |
| template <class _BidirIter, class _Dist, class _TypeT, class _Compare> |
| void __inplace_merge (_BidirIter, _BidirIter, _BidirIter, |
| _Dist*, _TypeT*, _Compare); |
| |
| // 25.3.4, p6 |
| template <class _BidirIter, class _Compare> |
| inline void |
| inplace_merge (_BidirIter __first, _BidirIter __middle, _BidirIter __last, |
| _Compare __comp) |
| { |
| if (!(__first == __middle || __middle == __last)) |
| __inplace_merge (__first, __middle, __last, |
| _RWSTD_DIFFERENCE_TYPE (_BidirIter), |
| _RWSTD_VALUE_TYPE (_BidirIter), __comp); |
| } |
| |
| |
| |
| // 25.3.4, p6 |
| template <class _BidirIter> |
| inline void |
| inplace_merge (_BidirIter __first, _BidirIter __middle, _BidirIter __last) |
| { |
| _STD::inplace_merge (__first, __middle, __last, _RWSTD_LESS (_BidirIter)); |
| } |
| |
| // 25.3.5 - Set operations on sorted structures |
| |
| // 25.3.5.1 |
| _EXPORT |
| template <class _InputIter1, class _InputIter2, class _Compare> |
| bool includes (_InputIter1, _InputIter1, _InputIter2, _InputIter2, _Compare); |
| |
| template <class _InputIter1, class _InputIter2> |
| inline bool includes (_InputIter1 __first1, _InputIter1 __last1, |
| _InputIter2 __first2, _InputIter2 __last2) |
| { |
| return _STD::includes (__first1, __last1, __first2, __last2, |
| _RWSTD_LESS (_InputIter1)); |
| } |
| |
| |
| // 25.3.5.2 |
| _EXPORT |
| template <class _InputIter1, class _InputIter2, class _OutputIter, |
| class _Compare> |
| _OutputIter |
| set_union (_InputIter1, _InputIter1, _InputIter2, _InputIter2, |
| _OutputIter, _Compare); |
| |
| template <class _InputIter1, class _InputIter2, class _OutputIter> |
| inline _OutputIter |
| set_union (_InputIter1 __first1, _InputIter1 __last1, |
| _InputIter2 __first2, _InputIter2 __last2, _OutputIter __res) |
| { |
| return _STD::set_union (__first1, __last1, __first2, __last2, __res, |
| _RWSTD_LESS (_InputIter1)); |
| } |
| |
| |
| // 25.3.5.3 |
| _EXPORT |
| template <class _InputIter1, class _InputIter2, class _OutputIter, |
| class _Compare> |
| _OutputIter |
| set_intersection (_InputIter1, _InputIter1, _InputIter2, _InputIter2, |
| _OutputIter, _Compare); |
| |
| template <class _InputIter1, class _InputIter2, class _OutputIter> |
| inline _OutputIter |
| set_intersection (_InputIter1 __first1, _InputIter1 __last1, |
| _InputIter2 __first2, _InputIter2 __last2, _OutputIter __res) |
| { |
| return _STD::set_intersection (__first1, __last1, __first2, __last2, |
| __res, _RWSTD_LESS (_InputIter1)); |
| } |
| |
| |
| // 25.3.5.4 |
| _EXPORT |
| template <class _InputIter1, class _InputIter2, class _OutputIter, |
| class _Compare> |
| _OutputIter |
| set_difference (_InputIter1, _InputIter1, _InputIter2, _InputIter2, |
| _OutputIter, _Compare); |
| |
| template <class _InputIter1, class _InputIter2, class _OutputIter> |
| inline _OutputIter |
| set_difference (_InputIter1 __first1, _InputIter1 __last1, |
| _InputIter2 __first2, _InputIter2 __last2, _OutputIter __res) |
| { |
| return _STD::set_difference (__first1, __last1, __first2, __last2, |
| __res, _RWSTD_LESS (_InputIter1)); |
| } |
| |
| |
| // 25.3.5.5 |
| _EXPORT |
| template <class _InputIter1, class _InputIter2, class _OutputIter, |
| class _Compare> |
| _OutputIter |
| set_symmetric_difference (_InputIter1, _InputIter1, _InputIter2, _InputIter2, |
| _OutputIter, _Compare); |
| |
| template <class _InputIter1, class _InputIter2, class _OutputIter> |
| inline _OutputIter |
| set_symmetric_difference (_InputIter1 __first1, _InputIter1 __last1, |
| _InputIter2 __first2, _InputIter2 __last2, |
| _OutputIter __res) |
| { |
| return _STD::set_symmetric_difference (__first1, __last1, |
| __first2, __last2, |
| __res, _RWSTD_LESS (_InputIter1)); |
| } |
| |
| |
| // 25.3.6 - Heap operations |
| // defined in <rw/_heap.h> |
| |
| // 25.3.7 - Minimum and maximum |
| |
| // 25.3.7, p7 |
| _EXPORT |
| template <class _FwdIter, class _Compare> |
| _FwdIter min_element (_FwdIter, _FwdIter, _Compare); |
| |
| template <class _FwdIter> |
| inline _FwdIter min_element (_FwdIter __first, _FwdIter __last) |
| { |
| return _STD::min_element (__first, __last, _RWSTD_LESS (_FwdIter)); |
| } |
| |
| |
| // 25.3.7, p9 |
| _EXPORT |
| template <class _FwdIter, class _Compare> |
| _FwdIter max_element (_FwdIter, _FwdIter, _Compare); |
| |
| |
| template <class _FwdIter> |
| inline _FwdIter max_element (_FwdIter __first, _FwdIter __last) |
| { |
| return _STD::max_element (__first, __last, _RWSTD_LESS (_FwdIter)); |
| } |
| |
| |
| // 25.3.9 - Permutation generators [lib.alg.permutation.generators] |
| |
| // 25.3.9, p1 |
| _EXPORT |
| template <class _BidirIter, class _Compare> |
| bool next_permutation (_BidirIter, _BidirIter, _Compare); |
| |
| template <class _BidirIter> |
| inline bool next_permutation (_BidirIter __first, _BidirIter __last) |
| { |
| return _STD::next_permutation (__first, __last, _RWSTD_LESS (_BidirIter)); |
| } |
| |
| |
| // 25.3.9, p3 |
| _EXPORT |
| template <class _BidirIter, class _Compare> |
| bool prev_permutation (_BidirIter, _BidirIter, _Compare); |
| |
| template <class _BidirIter> |
| inline bool prev_permutation (_BidirIter __first, _BidirIter __last) |
| { |
| return _STD::prev_permutation (__first, __last, _RWSTD_LESS (_BidirIter)); |
| } |
| |
| |
| } // namespace std |
| |
| |
| #undef _INLINE |
| |
| |
| #ifdef _RWSTD_NO_IMPLICIT_INCLUSION |
| # include <algorithm.cc> |
| #endif |
| |
| |
| #endif // _RWSTD_ALGORITHM_INCLUDED |
