[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