algorithm

/*	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.h>
#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