algorithm

mpeg4 video codec mpeg4 video codec

			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;
			}
		}

	}

}

#endif