summaryrefslogtreecommitdiff
path: root/misc/uClibc++/include/cxx/algorithm
diff options
context:
space:
mode:
Diffstat (limited to 'misc/uClibc++/include/cxx/algorithm')
-rw-r--r--misc/uClibc++/include/cxx/algorithm1695
1 files changed, 1695 insertions, 0 deletions
diff --git a/misc/uClibc++/include/cxx/algorithm b/misc/uClibc++/include/cxx/algorithm
new file mode 100644
index 000000000..5e8f139c0
--- /dev/null
+++ b/misc/uClibc++/include/cxx/algorithm
@@ -0,0 +1,1695 @@
+/* Copyright (C) 2004 Garrett A. Kajmowicz
+ This file is part of the uClibc++ Library.
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+
+#include <cstdlib>
+#include <iterator>
+#include <utility>
+#include <functional>
+
+#ifndef __STD_HEADER_ALGORITHM
+#define __STD_HEADER_ALGORITHM 1
+
+//Elliminate any previously defined macro
+#undef min
+#undef max
+
+#pragma GCC visibility push(default)
+
+namespace std{
+
+ // subclause _lib.alg.nonmodifying_, non-modifying sequence operations:
+ template<class InputIterator, class Function> _UCXXEXPORT
+ Function for_each(InputIterator first, InputIterator last, Function f)
+ {
+ while(first !=last){
+ f(*first);
+ ++first;
+ }
+ return f;
+ }
+
+
+ template<class InputIterator, class T> _UCXXEXPORT
+ InputIterator find(InputIterator first, InputIterator last, const T& value)
+ {
+ while(first !=last && *first != value){
+ ++first;
+ }
+ return first;
+ }
+
+ template<class InputIterator, class Predicate> _UCXXEXPORT
+ InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
+ {
+ while(first !=last && !pred(*first)){
+ ++first;
+ }
+ return first;
+ }
+
+ template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT ForwardIterator1
+ find_end(ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2)
+ {
+ ForwardIterator1 retval = last1;
+ while(first1 !=last1){
+ ForwardIterator1 temp1(first1);
+ ForwardIterator2 temp2(first2);
+ while(temp2!=last2 && temp1!= last1){
+ if(*temp1 != *temp2){
+ break; //Exit while loop
+ }
+ ++temp1;
+ ++temp2;
+ if(temp2 == last2){ //Have successfully checked the whole sequence
+ retval = first1;
+ }
+ }
+ }
+ return retval;
+ }
+
+ template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> _UCXXEXPORT
+ ForwardIterator1
+ find_end(ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2,
+ BinaryPredicate pred)
+ {
+ ForwardIterator1 retval = last1;
+ while(first1 !=last1){
+ ForwardIterator1 temp1(first1);
+ ForwardIterator2 temp2(first2);
+ while(temp2!=last2 && temp1!= last1){
+ if( ! pred(*temp1, *temp2)){
+ break; //Exit while loop
+ }
+ ++temp1;
+ ++temp2;
+ if(temp2 == last2){ //Have successfully checked the whole sequence
+ retval = first1;
+ }
+ }
+ }
+ return retval;
+ }
+
+ template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT
+ ForwardIterator1
+ find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2)
+ {
+ while(first1 != last1){
+ ForwardIterator2 temp2(first2);
+ while(temp2 != last2 ){
+ if(*temp2 == first1){
+ return first1;
+ }
+ ++temp2;
+ }
+
+ }
+ return last1;
+ }
+
+ template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> _UCXXEXPORT
+ ForwardIterator1
+ find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2,
+ BinaryPredicate pred)
+ {
+ while(first1 != last1){
+ ForwardIterator2 temp2(first2);
+ while(temp2 != last2 ){
+ if(*temp2 == first1){
+ return first1;
+ }
+ ++temp2;
+ }
+
+ }
+ return last1;
+ }
+
+ template<class ForwardIterator> _UCXXEXPORT ForwardIterator
+ adjacent_find(ForwardIterator first, ForwardIterator last)
+ {
+ ForwardIterator temp;
+ while(first != last){
+ temp = first;
+ ++temp;
+ if(*temp == *first){
+ return first;
+ }
+ ++first;
+ }
+ return first;
+ }
+
+ template<class ForwardIterator, class BinaryPredicate> _UCXXEXPORT
+ ForwardIterator
+ adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
+ {
+ ForwardIterator temp;
+ while(first != last){
+ temp = first;
+ ++temp;
+ if( pred(*temp, *first)){
+ return first;
+ }
+ ++first;
+ }
+ return first;
+ }
+
+ template<class InputIterator, class T> _UCXXEXPORT
+ typename iterator_traits<InputIterator>::difference_type
+ count(InputIterator first, InputIterator last, const T& value)
+ {
+ typename iterator_traits<InputIterator>::difference_type i = 0;
+ while(first!=last){
+ if(*first == value){
+ ++i;
+ }
+ ++first;
+ }
+ return i;
+ }
+
+ template<class InputIterator, class Predicate> _UCXXEXPORT
+ typename iterator_traits<InputIterator>::difference_type
+ count_if(InputIterator first, InputIterator last, Predicate pred)
+ {
+ typename iterator_traits<InputIterator>::difference_type i = 0;
+ while(first!=last){
+ if( pred(*first) ){
+ ++i;
+ }
+ ++first;
+ }
+ return i;
+ }
+
+ template<class InputIterator1, class InputIterator2> _UCXXEXPORT
+ pair<InputIterator1, InputIterator2>
+ mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
+ {
+ while(first1 != last1){
+ if(*first1 != *first2){
+ break;
+ }
+ ++first1;
+ ++first2;
+ }
+
+ pair<InputIterator1, InputIterator2> retval;
+ retval.first = first1;
+ retval.second = first2;
+ return retval;
+ }
+
+ template<class InputIterator1, class InputIterator2, class BinaryPredicate> _UCXXEXPORT
+ pair<InputIterator1, InputIterator2>
+ mismatch(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, BinaryPredicate pred)
+ {
+ while(first1 != last1){
+ if( !pred(*first1, *first2) ){
+ break;
+ }
+ ++first1;
+ ++first2;
+ }
+
+ pair<InputIterator1, InputIterator2> retval;
+ retval.first = first1;
+ retval.second = first2;
+ return retval;
+ }
+
+ template<class InputIterator1, class InputIterator2> _UCXXEXPORT
+ bool
+ equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
+ {
+ while(first1 !=last1){
+ if(*first1 != *first2){
+ return false;
+ }
+ ++first1;
+ ++first2;
+ }
+ return true;
+ }
+
+ template<class InputIterator1, class InputIterator2, class BinaryPredicate> _UCXXEXPORT
+ bool
+ equal(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, BinaryPredicate pred)
+ {
+ while(first1 !=last1){
+ if( !pred(*first1, *first2) ){
+ return false;
+ }
+ ++first1;
+ ++first2;
+ }
+ return true;
+ }
+
+ template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT
+ ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2)
+ {
+ equal_to<typename iterator_traits<ForwardIterator1>::value_type> c;
+ return search(first1, last1, first2, last2, c);
+ }
+
+
+ template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> _UCXXEXPORT
+ ForwardIterator1
+ search(ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2,
+ BinaryPredicate pred)
+ {
+ while(first1 != last1){
+ ForwardIterator1 temp1(first1);
+ ForwardIterator2 temp2(first2);
+ while(temp2 != last2 && temp1 != last1){
+ if( !pred(*temp2, *temp1) ){
+ break;
+ }
+ ++temp1;
+ ++temp2;
+ if(temp2 == last2){
+ return first1;
+ }
+ }
+ ++first1;
+ }
+ return last1;
+ }
+
+
+ template<class ForwardIterator, class Size, class T> _UCXXEXPORT
+ ForwardIterator
+ search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value)
+ {
+ while( first != last ){
+ if(*first == value){
+ ForwardIterator temp(first);
+ Size i = 1;
+ ++first; //Avoid doing the same comparison over again
+ while(i < count && *temp == value){
+ ++first;
+ ++i;
+ }
+ if(i == count){
+ return first;
+ }
+ }
+ ++first;
+ }
+ return first;
+ }
+
+
+ template<class ForwardIterator, class Size, class T, class BinaryPredicate> _UCXXEXPORT
+ ForwardIterator
+ search_n(ForwardIterator first, ForwardIterator last,
+ Size count, const T& value, BinaryPredicate pred)
+ {
+ while( first != last ){
+ if( pred(*first, value) ){
+ ForwardIterator temp(first);
+ Size i = 1;
+ ++first; //Avoid doing the same comparison over again
+ while(i < count && pred(*temp, value) ){
+ ++first;
+ ++i;
+ }
+ if(i == count){
+ return first;
+ }
+ }
+ ++first;
+ }
+ return first;
+
+ }
+
+ // subclause _lib.alg.modifying.operations_, modifying sequence operations:
+
+ template<class InputIterator, class OutputIterator> _UCXXEXPORT
+ OutputIterator
+ copy(InputIterator first, InputIterator last, OutputIterator result)
+ {
+ while(first != last){
+ *result = *first;
+ ++first;
+ ++result;
+ }
+ return result;
+ }
+
+ template<class BidirectionalIterator1, class BidirectionalIterator2> _UCXXEXPORT
+ BidirectionalIterator2
+ copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
+ BidirectionalIterator2 result)
+ {
+ while(first !=last ){
+ --result;
+ --last;
+ *result = *last;
+ }
+ return result;
+ }
+
+ template<class T> _UCXXEXPORT void swap(T& a, T& b){
+ T temp(a);
+ a = b;
+ b = temp;
+ }
+
+ template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT
+ ForwardIterator2
+ swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
+ {
+ while(first1 != last1){
+ iter_swap(first1, first2);
+ ++first1;
+ ++first2;
+ }
+ return first2;
+ }
+
+
+ template<class ForwardIterator1, class ForwardIterator2> _UCXXEXPORT
+ void
+ iter_swap(ForwardIterator1 a, ForwardIterator2 b)
+ {
+ typename iterator_traits<ForwardIterator1>::value_type temp(*a);
+ *a = *b;
+ *b = temp;
+ }
+
+
+ template<class InputIterator, class OutputIterator, class UnaryOperation> _UCXXEXPORT
+ OutputIterator
+ transform(InputIterator first, InputIterator last,
+ OutputIterator result, UnaryOperation op)
+ {
+ while(first != last){
+ *result = op(*first);
+ ++first;
+ ++result;
+ }
+ return result;
+ }
+
+
+ template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> _UCXXEXPORT
+ OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, OutputIterator result,
+ BinaryOperation binary_op)
+ {
+ while(first1 != last1){
+ *result = binary_op(*first1, *first2);
+ ++first1;
+ ++first2;
+ ++result;
+ }
+ return result;
+ }
+
+
+ template<class ForwardIterator, class T> _UCXXEXPORT
+ void
+ replace(ForwardIterator first, ForwardIterator last,
+ const T& old_value, const T& new_value)
+ {
+ while(first != last){
+ if(*first == old_value){
+ *first = new_value;
+ }
+ ++first;
+ }
+ }
+
+ template<class ForwardIterator, class Predicate, class T> _UCXXEXPORT
+ void
+ replace_if(ForwardIterator first, ForwardIterator last,
+ Predicate pred, const T& new_value)
+ {
+ while(first != last){
+ if( pred(*first) ){
+ *first = new_value;
+ }
+ ++first;
+ }
+ }
+
+
+ template<class InputIterator, class OutputIterator, class T> _UCXXEXPORT
+ OutputIterator
+ replace_copy(InputIterator first, InputIterator last,
+ OutputIterator result, const T& old_value, const T& new_value)
+ {
+ while(first != last){
+ if(*first == old_value){
+ *result = new_value;
+ }else{
+ *result = *first;
+ }
+ ++first;
+ ++result;
+ }
+ return result;
+ }
+
+ template<class Iterator, class OutputIterator, class Predicate, class T> _UCXXEXPORT
+ OutputIterator
+ replace_copy_if(Iterator first, Iterator last,
+ OutputIterator result, Predicate pred, const T& new_value)
+ {
+ while(first != last){
+ if( pred(*first) ){
+ *result = new_value;
+ }else{
+ *result = *first;
+ }
+ ++first;
+ ++result;
+ }
+ return result;
+ }
+
+ template<class ForwardIterator, class T> _UCXXEXPORT
+ void
+ fill(ForwardIterator first, ForwardIterator last, const T& value)
+ {
+ while(first != last){
+ *first = value;
+ ++first;
+ }
+ }
+
+ template<class OutputIterator, class Size, class T> _UCXXEXPORT
+ void
+ fill_n(OutputIterator first, Size n, const T& value)
+ {
+ while(n != 0){
+ *first = value;
+ --n;
+ ++first;
+ }
+ }
+
+ template<class ForwardIterator, class Generator> _UCXXEXPORT
+ void
+ generate(ForwardIterator first, ForwardIterator last, Generator gen)
+ {
+ while(first != last){
+ *first = gen();
+ ++first;
+ }
+ }
+
+ template<class OutputIterator, class Size, class Generator> _UCXXEXPORT
+ void
+ generate_n(OutputIterator first, Size n, Generator gen)
+ {
+ while(n !=0){
+ *first = gen();
+ --n;
+ ++first;
+ }
+ }
+
+ template<class ForwardIterator, class T> _UCXXEXPORT
+ ForwardIterator
+ remove(ForwardIterator first, ForwardIterator last, const T& value)
+ {
+ ForwardIterator temp(first);
+ while(temp !=last){
+ if(*temp == value){
+
+ }else{
+ *first = *temp;
+ ++first;
+ }
+ ++temp;
+ }
+ return first;
+ }
+
+ template<class ForwardIterator, class Predicate> _UCXXEXPORT
+ ForwardIterator
+ remove_if(ForwardIterator first, ForwardIterator last, Predicate pred)
+ {
+ ForwardIterator temp(first);
+ while(temp !=last){
+ if( pred(*temp) ){
+
+ }else{
+ *first = *temp;
+ ++first;
+ }
+ ++temp;
+ }
+ return first;
+ }
+
+
+ template<class InputIterator, class OutputIterator, class T> _UCXXEXPORT
+ OutputIterator
+ remove_copy(InputIterator first, InputIterator last,
+ OutputIterator result, const T& value)
+ {
+ while(first !=last){
+ if(*first != value){
+ *result = *first;
+ ++result;
+ }
+ ++first;
+ }
+ return result;
+ }
+
+ template<class InputIterator, class OutputIterator, class Predicate> _UCXXEXPORT
+ OutputIterator
+ remove_copy_if(InputIterator first, InputIterator last,
+ OutputIterator result, Predicate pred)
+ {
+ while(first !=last){
+ if( !pred(*first) ){
+ *result = *first;
+ ++result;
+ }
+ ++first;
+ }
+ return result;
+ }
+
+ template<class ForwardIterator> _UCXXEXPORT
+ ForwardIterator
+ unique(ForwardIterator first, ForwardIterator last)
+ {
+ ForwardIterator new_val(first);
+ ForwardIterator old_val(first);
+
+ while(new_val !=last){
+ if(*new_val == *old_val && new_val != old_val){
+
+ }else{
+ *first = *new_val;
+ old_val = new_val;
+ ++first;
+ }
+ ++new_val;
+ }
+ return first;
+ }
+
+ template<class ForwardIterator, class BinaryPredicate> _UCXXEXPORT
+ ForwardIterator
+ unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
+ {
+ ForwardIterator new_val(first);
+ ForwardIterator old_val(first);
+
+ while(new_val !=last){
+ if( pred(*new_val, *old_val) && new_val != old_val){
+
+ }else{
+ *first = *new_val;
+ old_val = new_val;
+ ++first;
+ }
+ ++new_val;
+ }
+ return first;
+ }
+
+ template<class InputIterator, class OutputIterator> _UCXXEXPORT
+ OutputIterator
+ unique_copy(InputIterator first, InputIterator last, OutputIterator result)
+ {
+ InputIterator temp(first);
+ while(first !=last ){
+ if(*first == *temp && first != temp){
+
+ }else{
+ *result = *first;
+ temp = first;
+ ++result;
+ }
+ ++first;
+ }
+ return result;
+ }
+
+ template<class InputIterator, class OutputIterator, class BinaryPredicate> _UCXXEXPORT
+ OutputIterator
+ unique_copy(InputIterator first, InputIterator last,
+ OutputIterator result, BinaryPredicate pred)
+ {
+ InputIterator temp(first);
+ while(first !=last ){
+ if( pred(*first, *temp) && first != temp){
+
+ }else{
+ *result = *first;
+ temp = first;
+ ++result;
+ }
+ ++first;
+ }
+ return result;
+ }
+
+ template<class BidirectionalIterator> _UCXXEXPORT
+ void
+ reverse(BidirectionalIterator first, BidirectionalIterator last)
+ {
+ --last; //Don't work with one past the end element
+ while(first < last){
+ iter_swap(first, last);
+ ++first;
+ --last;
+ }
+ }
+
+ template<class BidirectionalIterator, class OutputIterator> _UCXXEXPORT
+ OutputIterator
+ reverse_copy(BidirectionalIterator first, BidirectionalIterator last,
+ OutputIterator result)
+ {
+ while(last > first){
+ --last;
+ *result = *last;
+ ++result;
+ }
+ return result;
+ }
+
+ template<class ForwardIterator> _UCXXEXPORT
+ void
+ rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
+ {
+ if ((first == middle) || (last == middle)){
+ return;
+ }
+
+ ForwardIterator first2 = middle;
+
+ do {
+ swap(*first, *first2);
+ first++;
+ first2++;
+ if(first == middle){
+ middle = first2;
+ }
+ } while(first2 != last);
+
+ first2 = middle;
+
+ while (first2 != last) {
+ swap(*first, *first2);
+ first++;
+ first2++;
+ if (first == middle){
+ middle = first2;
+ }else if (first2 == last){
+ first2 = middle;
+ }
+ }
+ }
+
+ template<class ForwardIterator, class OutputIterator> _UCXXEXPORT
+ OutputIterator
+ rotate_copy(ForwardIterator first, ForwardIterator middle,
+ ForwardIterator last, OutputIterator result)
+ {
+ ForwardIterator temp(middle);
+ while(temp !=last){
+ *result = *temp;
+ ++temp;
+ ++result;
+ }
+ while(first != middle){
+ *result = *first;
+ ++first;
+ ++result;
+ }
+ return result;
+ }
+
+
+ template<class RandomAccessIterator> _UCXXEXPORT
+ void
+ random_shuffle(RandomAccessIterator first, RandomAccessIterator last)
+ {
+ --last;
+ while(first != last){
+ iter_swap(first, (first + (rand() % (last - first) ) ) );
+ ++first;
+ }
+ }
+
+ template<class RandomAccessIterator, class RandomNumberGenerator> _UCXXEXPORT
+ void
+ random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
+ RandomNumberGenerator& rand)
+ {
+ --last;
+ while(first != last){
+ iter_swap(first, (first + (rand(last - first) ) ) );
+ ++first;
+ }
+ }
+
+ // _lib.alg.partitions_, partitions:
+ template<class BidirectionalIterator, class Predicate> _UCXXEXPORT BidirectionalIterator
+ partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred)
+ {
+ return stable_partition(first, last, pred);
+ }
+
+ template<class BidirectionalIterator, class Predicate> _UCXXEXPORT BidirectionalIterator
+ stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred)
+ {
+ //first now points to the first non-desired element
+ while( first != last && pred(*first) ){
+ ++first;
+ }
+
+ BidirectionalIterator tempb;
+ BidirectionalIterator tempe = first;
+
+ while( tempe != last ){
+ //Find the next desired element
+ while( !pred(*tempe) ){
+ ++tempe;
+
+ //See if we should exit
+ if(tempe == last){
+ return first;
+ }
+ }
+
+ //Rotate the element back to the begining
+ tempb = tempe;
+ while(tempb != first){
+ iter_swap(tempb, tempb-1 );
+ --tempb;
+ }
+ //First now has a desired element
+ ++first;
+ }
+
+ return first;
+ }
+
+ template<class RandomAccessIterator> _UCXXEXPORT
+ void sort(RandomAccessIterator first, RandomAccessIterator last)
+ {
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ sort(first, last, c );
+ }
+
+ template<class RandomAccessIterator, class Compare> _UCXXEXPORT
+ void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
+ {
+ stable_sort(first, last, comp);
+ }
+
+ template<class RandomAccessIterator> _UCXXEXPORT
+ void stable_sort(RandomAccessIterator first, RandomAccessIterator last)
+ {
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ stable_sort(first, last, c);
+ }
+
+ template<class RandomAccessIterator, class Compare> _UCXXEXPORT
+ void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
+ {
+ //FIXME - bubble sort
+ RandomAccessIterator temp;
+ --last;
+ while(last - first > 0){
+ temp = last;
+ while(temp != first){
+ if( comp( *temp, *(temp-1) ) ){
+ iter_swap( temp-1, temp);
+ }
+ --temp;
+ }
+ ++first;
+ }
+ }
+
+ template<class RandomAccessIterator> _UCXXEXPORT
+ void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
+ {
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ partial_sort(first, middle, last, c);
+ }
+ template<class RandomAccessIterator, class Compare> _UCXXEXPORT
+ void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
+ RandomAccessIterator last, Compare comp)
+ {
+ //Fixme - partial bubble sort
+ RandomAccessIterator temp;
+ --last;
+ while(first < middle){
+ temp = last;
+ while(temp != first){
+ if( comp(*temp, *(temp -1 ) ) ) {
+ iter_swap( temp-1, temp);
+ }
+ --temp;
+ }
+ ++first;
+ }
+ }
+ template<class InputIterator, class RandomAccessIterator> _UCXXEXPORT
+ RandomAccessIterator
+ partial_sort_copy(InputIterator first, InputIterator last,
+ RandomAccessIterator result_first, RandomAccessIterator result_last)
+ {
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ return partial_sort_copy(first, last, result_first, result_last, c);
+ }
+ template<class InputIterator, class RandomAccessIterator, class Compare> _UCXXEXPORT
+ RandomAccessIterator
+ partial_sort_copy(InputIterator first, InputIterator last,
+ RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp)
+ {
+ size_t output_size = last-first;
+ size_t temp_size = result_last - result_first;
+ if(temp_size < output_size){
+ output_size = temp_size;
+ }
+
+ RandomAccessIterator middle = result_first + output_size;
+ RandomAccessIterator temp = result_first;
+
+ while(temp != middle){
+ *temp = *first;
+ ++temp;
+ ++first;
+ }
+ sort(result_first, middle, comp);
+
+ while( first != last){
+ if( comp( *first, *(middle-1) ) ){
+ *(middle-1) = *first;
+ sort(result_first, middle, comp);
+ }
+ ++first;
+ }
+
+ return middle;
+ }
+ template<class RandomAccessIterator> _UCXXEXPORT
+ void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
+ {
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ nth_element(first, nth, last, c);
+ }
+ template<class RandomAccessIterator, class Compare> _UCXXEXPORT
+ void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
+ RandomAccessIterator last, Compare comp)
+ {
+ partial_sort(first, nth, last, comp);
+ }
+
+ template<class ForwardIterator, class T> _UCXXEXPORT
+ ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
+ const T& value)
+ {
+ less<typename iterator_traits<ForwardIterator>::value_type> c;
+ return lower_bound(first, last, value, c);
+ }
+
+ template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
+ ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
+ const T& value, Compare comp)
+ {
+ if(first == last){
+ return last;
+ }
+ //If below or equal to the first element
+ if( comp(*first, value) == false){
+ return first;
+ }
+ ForwardIterator middle;
+
+ //If greater than the top element
+ middle = first;
+ advance(middle, distance(first, last) - 1);
+ if( comp(*middle, value) ){
+ return last;
+ }
+
+ //Now begin the actual search for the begining
+ while( distance(first, last) > 1 ){
+ //Find middle
+ middle = first;
+ advance(middle, (distance(first, last)/2) );
+ if( !comp(*middle, value) ){
+ last = middle;
+ }else{
+ first = middle;
+ }
+ }
+
+ if( !comp(*first, value) ){
+ return first;
+ }
+ return last;
+ }
+
+ template<class ForwardIterator, class T> _UCXXEXPORT
+ ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
+ const T& value)
+ {
+ less<typename iterator_traits<ForwardIterator>::value_type> c;
+ return upper_bound(first, last, value, c);
+ }
+
+
+ template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
+ ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
+ const T& value, Compare comp)
+ {
+ if(first == last){
+ return last;
+ }
+ //If below the first element
+ if( comp(value, *first) == true){
+ return first;
+ }
+
+ ForwardIterator middle;
+
+ //If greater than the top element
+ middle = first;
+ advance(middle, distance(first, last) - 1);
+ if( comp(*middle, value) ){
+ return last;
+ }
+
+ //Now begin the actual search for the end
+ while( distance(first, last) > 1 ){
+ //Find middle
+ middle = first;
+ advance(middle, (distance(first, last)/2) );
+ if( comp(value, *middle) ){
+ last = middle;
+ }else{
+ first = middle;
+ }
+ }
+
+ if( comp(value, *first) ){
+ return first;
+ }
+ return last;
+ }
+
+
+ template<class ForwardIterator, class T> _UCXXEXPORT
+ pair<ForwardIterator, ForwardIterator>
+ equal_range(ForwardIterator first, ForwardIterator last, const T& value)
+ {
+ less<typename iterator_traits<ForwardIterator>::value_type> c;
+ return equal_range(first, last, value, c);
+ }
+
+ template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
+ pair<ForwardIterator, ForwardIterator>
+ equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
+ {
+ pair<ForwardIterator, ForwardIterator> retval;
+ retval.first = lower_bound(first, last, value, comp);
+ //Reuse retval.first in order to (possibly) save a few comparisons
+ retval.second = upper_bound(retval.first, last, value, comp);
+ return retval;
+
+ }
+
+ template<class ForwardIterator, class T> _UCXXEXPORT
+ bool binary_search(ForwardIterator first, ForwardIterator last,
+ const T& value)
+ {
+ less<typename iterator_traits<ForwardIterator>::value_type> c;
+ return binary_search(first, last, value, c);
+ }
+
+ template<class ForwardIterator, class T, class Compare> _UCXXEXPORT
+ bool binary_search(ForwardIterator first, ForwardIterator last,
+ const T& value, Compare comp)
+ {
+ if( distance(first, last) == 0){
+ return false;
+ }
+
+ ForwardIterator middle;
+
+ while( distance(first, last) > 1 ){
+ //Set middle between first and last
+ middle = first;
+ advance(middle, distance(first, last)/2 );
+
+ if( comp(*middle, value ) == true){
+ first = middle;
+ }else{
+ last = middle;
+ }
+ }
+
+ if( !comp(*first, value) && !comp(value, *first) ){
+ return true;
+ }
+ if( !comp(*last, value) && !comp(value, *last) ){
+ return true;
+ }
+
+ return false;
+ }
+
+ // _lib.alg.merge_, merge:
+ template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
+ OutputIterator
+ merge(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result)
+ {
+ less<typename iterator_traits<InputIterator1>::value_type> c;
+ return merge(first1, last1, first2, last2, result, c);
+ }
+ template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
+ OutputIterator
+ merge(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
+ {
+ while( first1 != last1 && first2 != last2){
+ //If in this order so first1 elements which are equal come first
+ if( comp(*first2, *first1) ){
+ *result = *first2;
+ ++first2;
+ }else{
+ *result = *first1;
+ ++first1;
+ }
+ ++result;
+ }
+ //Clean up remaining elements
+ while(first1 != last1){
+ *result = *first1;
+ ++first1;
+ ++result;
+ }
+ while(first2 != last2){
+ *result = *first2;
+ ++first2;
+ ++result;
+ }
+ return result;
+ }
+ template<class BidirectionalIterator> _UCXXEXPORT
+ void inplace_merge(BidirectionalIterator first,
+ BidirectionalIterator middle, BidirectionalIterator last)
+ {
+ less<typename iterator_traits<BidirectionalIterator>::value_type> c;
+ inplace_merge(first, middle, last, c);
+ }
+ template<class BidirectionalIterator, class Compare> _UCXXEXPORT
+ void inplace_merge(BidirectionalIterator first,
+ BidirectionalIterator middle, BidirectionalIterator last, Compare comp)
+ {
+ //FIXME - using a bubble exchange method
+ while(first != middle && middle !=last){
+ if( comp(*middle, *first) ){
+ BidirectionalIterator temp(middle);
+ while( temp != first){
+ iter_swap(temp, temp-1);
+ --temp;
+ }
+ ++middle;
+ }
+ ++first;
+ }
+ }
+
+ // _lib.alg.set.operations_, set operations:
+ template<class InputIterator1, class InputIterator2> _UCXXEXPORT
+ bool includes(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2)
+ {
+ less<typename iterator_traits<InputIterator1>::value_type> c;
+ return includes(first1, last1, first2, last2, c );
+ }
+
+ template<class InputIterator1, class InputIterator2, class Compare> _UCXXEXPORT
+ bool includes(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, Compare comp)
+ {
+ while(first2 != last2){
+ //Advance the large set until no longer smaller than the element we are looking for
+ while( comp(*first1, *first2) ){
+ ++first1;
+ //If we are at the end of the list, we don't have the desired element
+ if(first1 == last1){
+ return false;
+ }
+ }
+ //If we are past the element we want, it isn't here
+ if( comp(*first2, *first1) ){
+ return false;
+ }
+ ++first2; //Move to next element
+ }
+ return true;
+ }
+
+ template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
+ OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result)
+ {
+ less<typename iterator_traits<InputIterator1>::value_type> c;
+ return set_union(first1, last1, first2, last2, result, c);
+ }
+
+ template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
+ OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
+ {
+ while( first1 != last1 && first2 != last2){
+ if( comp(*first2, *first1) ){
+ *result = *first2;
+
+ //Elliminate duplicates
+ InputIterator2 temp = first2;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }else{
+ *result = *first1;
+ //Elliminate duplicates
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }
+ ++result;
+ }
+
+ //Clean up remaining elements
+ while(first1 != last1){
+ *result = *first1;
+ ++result;
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ }
+
+ while(first2 != last2){
+ *result = *first2;
+ ++result;
+ InputIterator2 temp = first2;
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }
+ return result;
+ }
+
+ template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
+ OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result)
+ {
+ less<typename iterator_traits<InputIterator1>::value_type> c;
+ return set_intersection(first1, last1, first2, last2, result, c);
+ }
+ template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
+ OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
+ {
+ while( first1 != last1 && first2 != last2){
+ if( comp(*first2, *first1) ){
+ ++first2;
+ }else if( comp(*first1, *first2) ) {
+ ++first1;
+ }else{
+ *result = *first1;
+ ++result;
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ ++first2;
+ }
+ }
+ return result;
+ }
+ template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
+ OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result)
+ {
+ less<typename iterator_traits<InputIterator1>::value_type> c;
+ return set_difference(first1, last1, first2, last2, result, c);
+ }
+ template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
+ OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
+ {
+ while( first1 != last1 && first2 != last2){
+ if( comp(*first1, *first2) ){
+ *result = *first1;
+ ++result;
+
+ //Elliminate duplicates
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ }else if( comp(*first2, *first1) ){
+
+ //Elliminate duplicates
+ InputIterator2 temp = first2;
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+
+ }else{ //They are identical - skip
+ //Elliminate duplicates
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }
+ }
+
+ //Clean up remaining elements
+ while(first1 != last1){
+ *result = *first1;
+ ++result;
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ }
+
+ return result;
+ }
+ template<class InputIterator1, class InputIterator2, class OutputIterator> _UCXXEXPORT
+ OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result)
+ {
+ less<typename iterator_traits<InputIterator1>::value_type> c;
+ return set_symmetric_difference(first1, last1, first2, last2, result, c);
+ }
+ template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> _UCXXEXPORT
+ OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
+ {
+ while( first1 != last1 && first2 != last2){
+ if( comp(*first1, *first2) ){
+ *result = *first1;
+ ++result;
+
+ //Elliminate duplicates
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ }else if( comp(*first2, *first1) ){
+ *result = *first2;
+ ++result;
+
+ //Elliminate duplicates
+ InputIterator2 temp = first2;
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+
+ }else{ //They are identical - skip
+ //Elliminate duplicates
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }
+ }
+
+ //Clean up remaining elements
+ while(first1 != last1){
+ *result = *first1;
+ ++result;
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ }
+
+ while(first2 != last2){
+ *result = *first2;
+ ++result;
+ InputIterator2 temp = first2;
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }
+
+ return result;
+ }
+
+ // _lib.alg.heap.operations_, heap operations:
+
+ template<class RandomAccessIterator> _UCXXEXPORT
+ void push_heap(RandomAccessIterator first, RandomAccessIterator last)
+ {
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ push_heap(first, last, c);
+ }
+
+ template<class RandomAccessIterator, class Compare> _UCXXEXPORT
+ void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
+ {
+ // *(last - 1) is the last element
+ RandomAccessIterator begin, middle, end;
+ begin = first;
+ end = last - 2;
+ if(last - first < 2){ //Empty heap
+ return;
+ }
+ if ( comp(*(last-1), *end) ){ //Belongs past the end - already in place
+ return;
+ }
+ while(end - begin > 1){
+ middle = begin + ((end - begin)/2);
+ if( comp(*middle, *(last-1) ) ){
+ end = middle;
+ }else{
+ begin = middle;
+ }
+ }
+
+ if( comp(*begin, *(last-1)) ){
+ middle = begin;
+ }else{
+ middle = end;
+ }
+
+ //Now all we do is swap the elements up to the begining
+ --last;
+
+ while(last > middle){
+ iter_swap(last, last-1);
+ --last;
+ }
+ }
+
+ template<class RandomAccessIterator> _UCXXEXPORT
+ void pop_heap(RandomAccessIterator first, RandomAccessIterator last)
+ {
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ pop_heap(first, last, c);
+ }
+ template<class RandomAccessIterator, class Compare> _UCXXEXPORT
+ void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare)
+ {
+ --last;
+ while(first < last){
+ iter_swap( first, first+1);
+ ++first;
+ }
+ }
+
+ template<class RandomAccessIterator> _UCXXEXPORT
+ void make_heap(RandomAccessIterator first, RandomAccessIterator last)
+ {
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ make_heap(first, last, c);
+ }
+ template<class RandomAccessIterator, class Compare> _UCXXEXPORT
+ void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
+ {
+ sort( reverse_iterator<RandomAccessIterator>(last), reverse_iterator<RandomAccessIterator>(first), comp);
+ }
+ template<class RandomAccessIterator> _UCXXEXPORT
+ void sort_heap(RandomAccessIterator first, RandomAccessIterator last)
+ {
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ sort_heap(first, last, c);
+ }
+ template<class RandomAccessIterator, class Compare> _UCXXEXPORT
+ void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
+ {
+ sort( first, last, comp);
+ }
+
+
+ // _lib.alg.min.max_, minimum and maximum:
+ template<class T> _UCXXEXPORT
+ const T& min(const T& a, const T& b)
+ {
+ if(b < a){
+ return b;
+ }
+ return a;
+ }
+
+ template<class T, class Compare> _UCXXEXPORT
+ const T& min(const T& a, const T& b, Compare comp)
+ {
+ if( comp(b, a) == true){
+ return b;
+ }
+ return a;
+ }
+
+ template<class T> _UCXXEXPORT
+ const T& max(const T& a, const T& b)
+ {
+ if( a < b){
+ return b;
+ }
+ return a;
+ }
+
+ template<class T, class Compare> _UCXXEXPORT
+ const T& max(const T& a, const T& b, Compare comp)
+ {
+ if( comp(a, b) ){
+ return b;
+ }
+ return a;
+ }
+
+ template<class ForwardIterator> _UCXXEXPORT
+ ForwardIterator min_element(ForwardIterator first, ForwardIterator last)
+ {
+ less<typename iterator_traits<ForwardIterator>::value_type> c;
+ return min_element(first, last, c);
+ }
+
+ template<class ForwardIterator, class Compare> _UCXXEXPORT
+ ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp)
+ {
+ ForwardIterator retval = first;
+ ++first;
+ while(first != last){
+ if( comp( *first, *retval) ){
+ retval = first;
+ }
+ ++first;
+ }
+ return retval;
+ }
+
+ template<class ForwardIterator> _UCXXEXPORT
+ ForwardIterator max_element(ForwardIterator first, ForwardIterator last)
+ {
+ less<typename iterator_traits<ForwardIterator>::value_type> c;
+ return max_element(first, last, c);
+ }
+
+ template<class ForwardIterator, class Compare> _UCXXEXPORT
+ ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp)
+ {
+ ForwardIterator retval = first;
+ ++first;
+ while(first != last){
+ if( comp( *retval, *first ) ){
+ retval = first;
+ }
+ ++first;
+ }
+ return retval;
+ }
+
+ template<class InputIterator1, class InputIterator2> _UCXXEXPORT
+ bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2)
+ {
+ less<typename iterator_traits<InputIterator1>::value_type> c;
+ return lexicographical_compare(first1, last1, first2, last2, c);
+ }
+
+ template<class InputIterator1, class InputIterator2, class Compare> _UCXXEXPORT
+ bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, Compare comp)
+ {
+ while(first1 != last1 && first2 != last2){
+ if( comp(*first1, *first2) ){
+ return true;
+ }
+ if( comp(*first2, *first1) ){
+ return false;
+ }
+ ++first1;
+ ++first2;
+ }
+ return first1==last1 && first2 != last2;
+ }
+
+ // _lib.alg.permutation.generators_, permutations
+ template<class BidirectionalIterator> _UCXXEXPORT
+ bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
+ {
+ less<typename iterator_traits<BidirectionalIterator>::value_type> c;
+ return next_permutation(first, last, c);
+ }
+
+ template<class BidirectionalIterator, class Compare> _UCXXEXPORT
+ bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
+ {
+ if(first == last){
+ return false; // No data
+ }
+ BidirectionalIterator i = last;
+ --i;
+ if(i == first){
+ return false; //Only one element
+ }
+ BidirectionalIterator ii = i;
+ --ii;
+ //If the last two items are in order, swap them and call it done
+ if( comp(*ii, *i) ){
+ iter_swap(ii, i);
+ return true;
+ }
+
+
+ //This part of the algorithm copied from G++ header files ver. 3.4.2
+ i = last;
+ --i;
+ for(;;){
+ ii = i;
+ --i;
+ if ( comp(*i, *ii) ){
+ BidirectionalIterator j = last;
+ --j;
+ while ( !comp(*i, *j)){
+ --j;
+ }
+ iter_swap(i, j);
+ reverse(ii, last);
+ return true;
+ }
+ if (i == first){
+ reverse(first, last);
+ return false;
+ }
+ }
+
+
+ }
+
+ template<class BidirectionalIterator> _UCXXEXPORT
+ bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last)
+ {
+ less<typename iterator_traits<BidirectionalIterator>::value_type> c;
+ return prev_permutation(first, last, c);
+ }
+
+ template<class BidirectionalIterator, class Compare> _UCXXEXPORT
+ bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
+ {
+ if(first == last){
+ return false; // No data
+ }
+ BidirectionalIterator i = last;
+ --i;
+ if(i == first){
+ return false; //Only one element
+ }
+ BidirectionalIterator ii = i;
+ --ii;
+ //If the last two items are in reverse order, swap them and call it done
+ if( comp(*i, *ii) ){
+ iter_swap(ii, i);
+ return true;
+ }
+
+ //Copied from GNU GCC header files version 3.4.2
+ i = last;
+ --i;
+
+ for(;;){
+ ii = i;
+ --i;
+ if ( comp(*ii, *i)){
+ BidirectionalIterator j = last;
+ --j;
+ while ( !comp(*j, *i)){
+ --j;
+ }
+ iter_swap(i, j);
+ reverse(ii, last);
+ return true;
+ }
+ if (i == first){
+ reverse(first, last);
+ return false;
+ }
+ }
+
+ }
+
+}
+
+#pragma GCC visibility pop
+
+#endif
+
+
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-05 16:09:29 +0000