algorithm

mpeg4 video codec mpeg4 video codec

    }
    else if (pivot < b)
    {
     iter_swap(pivot, b);
     pivot = b;
    }
    else
    {
     ++b;
    }

    if (b == e) 
    {
     assert(comp(*pivot , *b));
     if (pivot < b) 
     {
      iter_swap(pivot, --b);
      return make_pair(b, e);
     }
     assert(pivot > e);
     iter_swap(pivot, b);
     return make_pair(b, b + 1);
    }
   }
  }

  static inline unsigned short rand2(void)
  {
   static unsigned int a = 18000;   
   static unsigned int g_PrivateRandom2AlgoSeed = 521288629;
   return (unsigned short)(g_PrivateRandom2AlgoSeed = 
    a * (g_PrivateRandom2AlgoSeed & 65535) + 
    (g_PrivateRandom2AlgoSeed >> 16));
  }

  template <class Iter,class Compare> Iter SelectPivot(Iter b, Iter e,Compare comp)
  {
   assert(b < e);

   typedef typename iterator_traits<Iter>::difference_type difference_type; 
   const size_t size = size_t(e - b);

   assert(size >= 3);
   const size_t innerSize = size - 2;
   const size_t offset = (rand2() * innerSize) >> 16u;
   assert(offset < innerSize);
   const Iter m = b + offset + 1;
   assert(b < m && m < e);

   // Sort in-place b, m, and e
   --e;
   if (comp(*m , *b))
   {
    if (comp(*e , *m))
    {
     // *e < *m < *b
     iter_swap(b, e);
    }
    else
    {
     if (comp(*e , *b))
     {
      // *m <= *e < *b
      iter_swap(b, m);
      iter_swap(m, e);
     }
     else
     {
      // *m < *b <= *e
      iter_swap(b, m);
     }
    }
   }
   else
   {
    if (comp(*e , *b))
    {
     // *e < *b <= *m
     iter_swap(b, e);
     iter_swap(m, e);
    }
    else
    {
     if (comp(*e , *m))
     {
      // *b <= *e < *m
      iter_swap(m, e);
     }
     else
     {
      // *b <= *m <= *e
      // nothing to do
     }
    }
   }

   assert(!(comp(*m , *b)));
   assert(!(comp(*e , *m)));
   return m;
  }

 }

 template <class Iter, class Compare> void unstable_sort(Iter b, Iter e,Compare comp)
 {
  assert(e >= b);
  // The second branch of Quicksort's recursion is implemented through 
  //      iteration, hence the following loop
  size_t length; 
  while ((length = static_cast<size_t>(e - b)) > 1)
  {
   enum { threshold = 8 };
   if (length <= threshold)
   {
    //InsertionSorter<Iter, threshold, 1>::Run(b, length);
    SortPrivate::SelectionSorter<Iter, threshold,Compare>::Run(b, length, comp);
    return;
   }
   const pair<Iter, Iter> midRange = SortPrivate::Partition(b, e, SortPrivate::SelectPivot(b, e, comp), comp);
   assert(midRange.second - midRange.first > 0);
   assert(b <= midRange.first);
   assert(midRange.second <= e);
   if (midRange.first - b < e - midRange.second)
   {
    unstable_sort(b, midRange.first,comp);
    b = midRange.second;
   }
   else
   {
    unstable_sort(midRange.second, e,comp);
    e = midRange.first;
   }
  }
	}

	template<class RandomAccessIterator> 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){