[uClibc-cvs] CVS update of uClibc++ (Rules.mak include/algorithm tests/algotest.cpp)

Garrett Kajmowicz gkajmowi at codepoet.org
Sat Sep 11 19:15:08 UTC 2004


    Date: Saturday, September 11, 2004 @ 13:15:08
  Author: gkajmowi
    Path: /var/cvs/uClibc++

Modified: Rules.mak (1.4 -> 1.5) include/algorithm (1.5 -> 1.6)
          tests/algotest.cpp (1.2 -> 1.3)

Added merge algorithms


Index: uClibc++/Rules.mak
diff -u uClibc++/Rules.mak:1.4 uClibc++/Rules.mak:1.5
--- uClibc++/Rules.mak:1.4	Wed Sep  8 08:27:03 2004
+++ uClibc++/Rules.mak	Sat Sep 11 13:15:05 2004
@@ -47,7 +47,7 @@
 # this stuff alone.
 MAJOR_VERSION:=0
 MINOR_VERSION:=1
-SUBLEVEL:=4
+SUBLEVEL:=5
 VERSION:=$(MAJOR_VERSION).$(MINOR_VERSION).$(SUBLEVEL)
 # Ensure consistent sort order, 'gcc -print-search-dirs' behavior, etc.
 # LC_ALL:= C
Index: uClibc++/include/algorithm
diff -u uClibc++/include/algorithm:1.5 uClibc++/include/algorithm:1.6
--- uClibc++/include/algorithm:1.5	Thu Sep  9 22:27:17 2004
+++ uClibc++/include/algorithm	Sat Sep 11 13:15:06 2004
@@ -887,8 +887,30 @@
 			++first;
 		}
 	}
-	template<class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);
-	template<class InputIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
+	template<class InputIterator, class RandomAccessIterator>
+		RandomAccessIterator
+		partial_sort_copy(InputIterator first, InputIterator last,
+			RandomAccessIterator result_first, RandomAccessIterator result_last)
+	{
+		less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+		partial_sort_copy(first, last, result_first, result_last, c);
+	}
+	template<class InputIterator, class RandomAccessIterator, class Compare>
+		RandomAccessIterator
+		partial_sort_copy(InputIterator first, InputIterator last,
+			RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp)
+	{
+		size_t output_size = last-first;
+		if(result_last - result_first < output_size){
+			output_size = result_last - result_first;
+		}
+		RandomAccessIterator middle = first;
+		first += output_size;
+		partial_sort(first, middle, last, comp);
+		for(size_t i =0; i < output_size; ++i){
+			result_first[i] = first[i];
+		}
+	}
 	template<class RandomAccessIterator>
 		void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
 	{
@@ -1056,10 +1078,69 @@
 	}
 
 	// _lib.alg.merge_, merge:
-	template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
-	template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
-	template<class BidirectionalIterator> void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);
-	template<class BidirectionalIterator, class Compare> void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);
+	template<class InputIterator1, class InputIterator2, class OutputIterator>
+		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>
+		OutputIterator
+		merge(InputIterator1 first1, InputIterator1 last1,
+			InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
+	{
+		while(first1 != last1 || first2 != last2){
+			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;
+					++fisrt1;
+				}
+				++result;
+			}
+			//Clean up remaining elements
+			while(first1 != last1){
+				*result = *first1;
+				++first1;
+				++result;
+			}
+			while(first2 != last2){
+				*result = *first2;
+				++first2;
+				++result;
+			}
+		}
+		return result;
+	}
+	template<class BidirectionalIterator>
+		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>
+		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> 
Index: uClibc++/tests/algotest.cpp
diff -u uClibc++/tests/algotest.cpp:1.2 uClibc++/tests/algotest.cpp:1.3
--- uClibc++/tests/algotest.cpp:1.2	Thu Sep  9 22:27:18 2004
+++ uClibc++/tests/algotest.cpp	Sat Sep 11 13:15:07 2004
@@ -329,5 +329,36 @@
 	std::cout << std::endl;
 
 
+
+
+	std::cout << "Merge test\n";
+	a.clear();
+	a.push_back(10.8);
+	a.push_back(12.5);
+	a.push_back(32.7);
+	a.push_back(72.3);
+
+	i = a.end();
+
+	a.push_back(12.5);
+	a.push_back(19.6);
+	a.push_back(22.7);
+	a.push_back(38.4);
+	a.push_back(52.9);
+	a.push_back(92.7);
+
+	std::inplace_merge<std::vector<double>::iterator>(a.begin(), i, a.end());
+
+	std::cout << "The following two lines should be identical:\n";
+	std::cout << "10.8 12.5 12.5 19.6 22.7 32.7 38.4 52.9 72.3 92.7 " << std::endl;
+
+	j = a.begin();
+	while(j != a.end()){
+		std::cout << *j << " ";
+		++j;
+	}
+	std::cout << std::endl;
+
+
 	return 0;
 }



More information about the uClibc-cvs mailing list