algorithm

mpeg4 video codec mpeg4 video codec

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

#ifndef __STD_HEADER_ALGORITHM
#define __STD_HEADER_ALGORITHM 1

//Elliminate any previously defined macro
#undef min
#undef max

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