algorithm

mpeg4 video codec mpeg4 video codec

	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)
	{
		unstable_sort(first, last, comp);
	}

 namespace SortPrivate{
  template <class Iter, unsigned int size,class Compare> struct SelectionSorter;

  template <class Iter,class Compare> struct SelectionSorter<Iter, 1, Compare>
  {
   static Iter MinElement(Iter b,Compare)
   {
    return b;
   }

   static pair<Iter, Iter> MinMaxElement(Iter b,Compare)
   {
    return make_pair(b, b);
   }

   static void Run(Iter,Compare)
   {
    // Nothing to do
   }

   static void Run(Iter, size_t,Compare)
   {
    assert(false);
   }
  };

  template <class Iter,class Compare> struct SelectionSorter<Iter, 0, Compare>
  {
   static void Run(Iter,Compare)
   {
    // Nothing to do
   }

   static void Run(Iter, size_t,Compare)
	{
    assert(false);
				}
  };

  template <class Iter, unsigned int size,class Compare> struct SelectionSorter
  {
   static Iter MinElement(Iter b,Compare comp)
   {
    const Iter candidate = 
     SelectionSorter<Iter, size - 1,Compare>::MinElement(b + 1,comp);
    return comp(*candidate,*b) ? candidate : b;
			}

   static pair<Iter, Iter> MinMaxElement(Iter b,Compare comp)
   {
    pair<Iter, Iter> candidate = 
     SelectionSorter<Iter, size - 1,Compare>::MinMaxElement(b + 1, comp);
    if (!(comp(*candidate.first, *b))) candidate.first = b;
    else if (comp(*candidate.second , *b)) candidate.second = b;
    return candidate;
		}

   static void Run(Iter b,Compare comp)
   {
    typedef SelectionSorter<Iter, size - 1, Compare> Reduced;
    Iter afterB = b; ++afterB;
    const Iter candidate = Reduced::MinElement(afterB,comp);
    if (comp(*candidate,*b)) std::iter_swap(b, candidate);
    Reduced::Run(afterB,comp);
    /*
    // Alternate algorithm (proved to be slower in practice)
    const pair<Iter, Iter> i = MinMaxElement(b);
    if (b != i.first) std::iter_swap(b, i.first);
    std::iter_swap(b + (size - 1), 
    b == i.second ? i.first : i.second);
    SelectionSorter<Iter, size - 2>::Run(b + 1);
    */
   }

   static void Run(Iter b, size_t length,Compare comp)
                {
    assert(length <= size);
    if (length == size) Run(b,comp);
    else SelectionSorter<Iter, size - 1,Compare>::Run(b, length,comp);
                }
  };

  template <class Iter,class Compare> std::pair<Iter, Iter> Partition(Iter b, Iter e, Iter pivot, Compare comp)
  {
   using namespace std;

   assert(e - b > 1);
   assert(b <= pivot && pivot < e);

   for (;;)
   {
    const Iter bOld = b;

    // Find the first element strictly greater than the pivot, from left
    while (!(comp(*pivot , *b))) 
    {
     if (++b != e) continue; 

     // *pivot is the largest element
     --b;
     // move the pivot to the end of the array
     iter_swap(pivot, b);
     return make_pair(b, e);
    }

    assert(comp(*pivot , *b)); // found one element greater than the pivot
    assert(pivot != b); // this fires => badly implemented operator<

    // Find the first element strictly smaller than the pivot, from right
    for (--e; !(comp(*e , *pivot)); --e)
    {
     if (bOld != e) continue;

     // *pivot is the smallest element
     // return the range between the beginning and the first
     // element strictly larger than the pivot
     iter_swap(pivot, bOld);
     if (b == bOld) ++b;
     return make_pair(bOld, b);
    }

    assert(comp(*e , *pivot)); // found one element greater than the pivot
    assert(pivot != e); // this fires => badly implemented operator<
    assert(b != e); // this fires => badly implemented operator<

    // If they crossed, end of story
    if (e < b)
    {
     if (b == ++e)
     {
      // hoist the pivot in between b and e
      if (pivot > b) 
      {
       iter_swap(pivot, b);
       return make_pair(b, b + 1);
      }
      --e;
      assert(pivot < e);
      iter_swap(e, pivot);
     }
     return make_pair(e, b);
    }

    // Swap the elements and go on
    iter_swap(b, e);
    assert(pivot != b);
    assert(pivot != e);

    // Always keep the pivot in between b and e
    if (pivot > e)
    {
     iter_swap(pivot, e);
     pivot = e;
     ++e;
     ++b;