[uClibc-cvs] CVS update of uClibc++ (include/algorithm include/list include/vector tests/algotest.cpp tests/listtest.cpp)
Garrett Kajmowicz
gkajmowi at codepoet.org
Sun Sep 12 02:20:34 UTC 2004
Date: Saturday, September 11, 2004 @ 20:20:34
Author: gkajmowi
Path: /var/cvs/uClibc++
Modified: include/algorithm (1.6 -> 1.7) include/list (1.3 -> 1.4)
include/vector (1.5 -> 1.6) tests/algotest.cpp (1.3 -> 1.4)
tests/listtest.cpp (1.2 -> 1.3)
Added:
- Set operations
- vector operators
- List unique and remove
Index: uClibc++/include/algorithm
diff -u uClibc++/include/algorithm:1.6 uClibc++/include/algorithm:1.7
--- uClibc++/include/algorithm:1.6 Sat Sep 11 13:15:06 2004
+++ uClibc++/include/algorithm Sat Sep 11 20:20:32 2004
@@ -500,6 +500,7 @@
++first;
++result;
}
+ return result;
}
template<class ForwardIterator, class T>
@@ -1091,29 +1092,27 @@
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){
+ while( first1 != last1 && first2 != last2){
+ //If in this order so first1 elements which are equal come first
+ if( comp(*first2, *first1) ){
*result = *first2;
++first2;
- ++result;
+ }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;
}
@@ -1173,15 +1172,210 @@
return true;
}
- template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
- template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
+ template<class InputIterator1, class InputIterator2, class OutputIterator>
+ 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>
+ OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
+ {
+ while( first1 != last1 && first2 != last2){
+ if( comp(*first2, *first1) ){
+ *result = *first2;
+
+ //Elliminate duplicates
+ InputIterator2 temp = first2;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }else{
+ *result = *first1;
+ //Elliminate duplicates
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }
+ ++result;
+ }
+
+ //Clean up remaining elements
+ while(first1 != last1){
+ *result = *first1;
+ ++result;
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ }
+
+ while(first2 != last2){
+ *result = *first2;
+ ++result;
+ InputIterator2 temp = first2;
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }
+ return result;
+ }
+
+ template<class InputIterator1, class InputIterator2, class OutputIterator>
+ OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result)
+ {
+ less<typename iterator_traits<InputIterator1>::value_type> c;
+ return set_intersection(first1, last1, first2, last2, result, c);
+ }
+ template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
+ OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
+ {
+ while( first1 != last1 && first2 != last2){
+ if( comp(*first2, *first1) ){
+ ++first2;
+ }else if( comp(*first1, *first2) ) {
+ ++first1;
+ }else{
+ *result = *first1;
+ ++result;
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ ++first2;
+ }
+ }
+ return result;
+ }
+ template<class InputIterator1, class InputIterator2, class OutputIterator>
+ OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result)
+ {
+ less<typename iterator_traits<InputIterator1>::value_type> c;
+ return set_difference(first1, last1, first2, last2, result, c);
+ }
+ template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
+ OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
+ {
+ while( first1 != last1 && first2 != last2){
+ if( comp(*first1, *first2) ){
+ *result = *first1;
+ ++result;
+
+ //Elliminate duplicates
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ }else if( comp(*first2, *first1) ){
+
+ //Elliminate duplicates
+ InputIterator2 temp = first2;
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+
+ }else{ //They are identical - skip
+ //Elliminate duplicates
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }
+ }
+
+ //Clean up remaining elements
+ while(first1 != last1){
+ *result = *first1;
+ ++result;
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ }
+
+ return result;
+ }
+ template<class InputIterator1, class InputIterator2, class OutputIterator>
+ OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result)
+ {
+ less<typename iterator_traits<InputIterator1>::value_type> c;
+ return set_symmetric_difference(first1, last1, first2, last2, result, c);
+ }
+ template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
+ OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
+ InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)
+ {
+ while( first1 != last1 && first2 != last2){
+ if( comp(*first1, *first2) ){
+ *result = *first1;
+ ++result;
+
+ //Elliminate duplicates
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ }else if( comp(*first2, *first1) ){
+ *result = *first2;
+ ++result;
+
+ //Elliminate duplicates
+ InputIterator2 temp = first2;
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+
+ }else{ //They are identical - skip
+ //Elliminate duplicates
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }
+ }
+
+ //Clean up remaining elements
+ while(first1 != last1){
+ *result = *first1;
+ ++result;
+ InputIterator1 temp = first1;
+ while( first1 != last1 && !comp( *temp, *first1) ){
+ ++first1;
+ }
+ }
+
+ while(first2 != last2){
+ *result = *first2;
+ ++result;
+ InputIterator2 temp = first2;
+ while( first2 != last2 && !comp( *temp, *first2) ){
+ ++first2;
+ }
+ }
- template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
- template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
- template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
- template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
- template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
- template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
+ return result;
+ }
// _lib.alg.heap.operations_, heap operations:
Index: uClibc++/include/list
diff -u uClibc++/include/list:1.3 uClibc++/include/list:1.4
--- uClibc++/include/list:1.3 Wed Sep 8 08:27:06 2004
+++ uClibc++/include/list Sat Sep 11 20:20:32 2004
@@ -605,6 +605,50 @@
}
+ template<class T, class Allocator> void list<T, Allocator>::remove(const T& value){
+ iterator temp = begin();
+ while( temp != end() ){
+ if(*temp == value){
+ erase(temp);
+ }
+ ++temp;
+ }
+ }
+
+
+ template<class T, class Allocator> template <class Predicate> void list<T, Allocator>::remove_if(Predicate pred){
+ iterator temp = begin();
+ while( temp != end() ){
+ if( pred(*temp) ){
+ erase(temp);
+ }
+ ++temp;
+ }
+ }
+
+
+ template<class T, class Allocator> void list<T, Allocator>::unique(){
+ equal_to<typename iterator_traits<iterator>::value_type> p;
+ unique(p);
+ }
+
+ template<class T, class Allocator> template <class BinaryPredicate>
+ void list<T, Allocator>::unique(BinaryPredicate binary_pred)
+ {
+ iterator temp1 = begin();
+ iterator temp2;
+ ++temp1;
+ while( temp1 != end() ){
+ temp2 = temp1;
+ --temp2;
+ if( binary_pred(*temp1, *temp2) ){
+ erase(temp1);
+ temp1 = temp2;
+ }
+ ++temp1;
+ }
+ }
+
template<class T, class Allocator> void list<T, Allocator>::merge(list<T,Allocator>& x){
less<typename iterator_traits<typename list<T, Allocator>::iterator>::value_type> c;
merge(x, c);
Index: uClibc++/include/vector
diff -u uClibc++/include/vector:1.5 uClibc++/include/vector:1.6
--- uClibc++/include/vector:1.5 Wed Sep 8 08:27:06 2004
+++ uClibc++/include/vector Sat Sep 11 20:20:32 2004
@@ -23,6 +23,7 @@
#include <iterator>
#include <func_exception>
#include <vector_helpers>
+#include <algorithm>
#ifndef __STD_HEADER_VECTOR
@@ -39,13 +40,13 @@
template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
template <class T, class Allocator> void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
- template <class Allocator> bool operator==(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
- template <class Allocator> bool operator< (const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
- template <class Allocator> bool operator!=(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
- template <class Allocator> bool operator> (const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
- template <class Allocator> bool operator>=(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
- template <class Allocator> bool operator<=(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
- template <class Allocator> void swap(vector<bool,Allocator>& x, vector<bool,Allocator>& y);
+// template <class Allocator> bool operator==(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
+// template <class Allocator> bool operator< (const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
+// template <class Allocator> bool operator!=(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
+// template <class Allocator> bool operator> (const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
+// template <class Allocator> bool operator>=(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
+// template <class Allocator> bool operator<=(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
+// template <class Allocator> void swap(vector<bool,Allocator>& x, vector<bool,Allocator>& y);
template <class T, class Allocator> class vector {
@@ -381,14 +382,30 @@
}
return true;
}
- template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
- template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
- template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
- template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
- template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
- template <class T, class Allocator> void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
+ template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y){
+ less<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
+ return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
+ }
+ template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y){
+ return !(x == y);
+ }
+ template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y){
+ greater<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
+ return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
+ }
+ template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y){
+ greater_equal<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
+ return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
+ }
+ template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y){
+ less_equal<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
+ return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
+ }
+ template <class T, class Allocator> void swap(vector<T,Allocator>& x, vector<T,Allocator>& y){
+ x.swap(y);
+ }
}
Index: uClibc++/tests/algotest.cpp
diff -u uClibc++/tests/algotest.cpp:1.3 uClibc++/tests/algotest.cpp:1.4
--- uClibc++/tests/algotest.cpp:1.3 Sat Sep 11 13:15:07 2004
+++ uClibc++/tests/algotest.cpp Sat Sep 11 20:20:33 2004
@@ -15,7 +15,7 @@
int main(){
std::cout << "Begining algorithm test" << std::endl;
- std::vector<double> a, b;
+ std::vector<double> a, b, c;
std::vector<double>::iterator i, j;
a.push_back(12.5);
@@ -329,8 +329,6 @@
std::cout << std::endl;
-
-
std::cout << "Merge test\n";
a.clear();
a.push_back(10.8);
@@ -360,5 +358,132 @@
std::cout << std::endl;
+ std::cout << "Set union\n";
+ a.clear();
+ a.push_back(10.8);
+ a.push_back(12.5);
+ a.push_back(32.7);
+ a.push_back(52.9);
+ a.push_back(72.3);
+
+ b.clear();
+ b.push_back(12.5);
+ b.push_back(19.6);
+ b.push_back(22.7);
+ b.push_back(32.7);
+ b.push_back(38.4);
+ b.push_back(52.9);
+ b.push_back(92.7);
+
+ c.assign(20, 0.0);
+
+ std::cout << "The following two lines should be identical:\n";
+ std::cout << "10.8 12.5 19.6 22.7 32.7 38.4 52.9 72.3 92.7 " << std::endl;
+
+ j = std::set_union(a.begin(), a.end(), b.begin(), b.end(), c.begin() );
+ i = c.begin();
+ while(i != j){
+ std::cout << *i << " " ;
+ ++i;
+ }
+ std::cout << std::endl;
+
+
+ std::cout << "Set intersection\n";
+ a.clear();
+ a.push_back(10.8);
+ a.push_back(12.5);
+ a.push_back(32.7);
+ a.push_back(52.9);
+ a.push_back(72.3);
+
+ b.clear();
+ b.push_back(12.5);
+ b.push_back(19.6);
+ b.push_back(22.7);
+ b.push_back(32.7);
+ b.push_back(38.4);
+ b.push_back(52.9);
+ b.push_back(92.7);
+
+ c.assign(20, 0.0);
+
+ std::cout << "The following two lines should be identical:\n";
+ std::cout << "12.5 32.7 52.9 " << std::endl;
+
+ j = std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), c.begin() );
+ i = c.begin();
+ while(i != j){
+ std::cout << *i << " " ;
+ ++i;
+ }
+ std::cout << std::endl;
+
+
+
+ std::cout << "Set difference\n";
+ a.clear();
+ a.push_back(10.8);
+ a.push_back(12.5);
+ a.push_back(12.5);
+ a.push_back(32.7);
+ a.push_back(52.9);
+ a.push_back(72.3);
+
+ b.clear();
+ b.push_back(12.5);
+ b.push_back(19.6);
+ b.push_back(22.7);
+ b.push_back(32.7);
+ b.push_back(38.4);
+ b.push_back(52.9);
+ b.push_back(92.7);
+
+ c.assign(20, 0.0);
+
+ std::cout << "The following two lines should be identical:\n";
+ std::cout << "10.8 72.3 " << std::endl;
+
+ j = std::set_difference(a.begin(), a.end(), b.begin(), b.end(), c.begin() );
+ i = c.begin();
+ while(i != j){
+ std::cout << *i << " " ;
+ ++i;
+ }
+ std::cout << std::endl;
+
+
+ std::cout << "Set symmetric difference\n";
+ a.clear();
+ a.push_back(10.8);
+ a.push_back(12.5);
+ a.push_back(12.5);
+ a.push_back(32.7);
+ a.push_back(52.9);
+ a.push_back(72.3);
+
+ b.clear();
+ b.push_back(12.5);
+ b.push_back(19.6);
+ b.push_back(22.7);
+ b.push_back(32.7);
+ b.push_back(38.4);
+ b.push_back(52.9);
+ b.push_back(92.7);
+
+ c.assign(20, 0.0);
+
+ std::cout << "The following two lines should be identical:\n";
+ std::cout << "10.8 19.6 22.7 38.4 72.3 92.7 " << std::endl;
+
+ j = std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), c.begin() );
+ i = c.begin();
+ while(i != j){
+ std::cout << *i << " " ;
+ ++i;
+ }
+ std::cout << std::endl;
+
+
return 0;
}
Index: uClibc++/tests/listtest.cpp
diff -u uClibc++/tests/listtest.cpp:1.2 uClibc++/tests/listtest.cpp:1.3
--- uClibc++/tests/listtest.cpp:1.2 Wed Sep 8 08:27:08 2004
+++ uClibc++/tests/listtest.cpp Sat Sep 11 20:20:33 2004
@@ -316,5 +316,57 @@
+ std::cout << "Testing remove\n";
+
+ temp.clear();
+ temp.push_back(12.8);
+ temp.push_back(22.4);
+ temp.push_back(37.9);
+ temp.push_back(48.5);
+ temp.push_back(11.7);
+ temp.push_back(29.1);
+ temp.push_back(37.9);
+ temp.push_back(99.9);
+
+ temp.remove(37.9);
+ std::cout << "The following two lines should be identical:\n";
+ std::cout << "12.8 22.4 48.5 11.7 29.7 99.9 \n";
+ i = temp.begin();
+ while(i != temp.end()){
+ std::cout << *i << " ";
+ ++i;
+ }
+ std::cout << std::endl;
+
+
+
+ std::cout << "Testing unique\n";
+
+ temp.clear();
+ temp.push_back(11.7);
+ temp.push_back(12.8);
+ temp.push_back(12.8);
+ temp.push_back(22.4);
+ temp.push_back(29.1);
+ temp.push_back(37.9);
+ temp.push_back(37.9);
+ temp.push_back(37.9);
+ temp.push_back(37.9);
+ temp.push_back(48.5);
+ temp.push_back(99.9);
+
+ temp.unique();
+ std::cout << "The following two lines should be identical:\n";
+ std::cout << "11.7 12.8 22.4 29.1 37.9 48.5 99.9 \n";
+ i = temp.begin();
+ while(i != temp.end()){
+ std::cout << *i << " ";
+ ++i;
+ }
+ std::cout << std::endl;
+
+
+
+
return 0;
}
More information about the uClibc-cvs
mailing list