[uClibc-cvs] CVS update of uClibc++ (ChangeLog Makefile bin/Makefile include/Makefile include/algorithm include/deque include/iterator_base include/valarray tests/algotest.cpp)
Garrett Kajmowicz
gkajmowi at codepoet.org
Fri Sep 10 04:27:19 UTC 2004
Date: Thursday, September 9, 2004 @ 22:27:18
Author: gkajmowi
Path: /var/cvs/uClibc++
Modified: ChangeLog (1.2 -> 1.3) Makefile (1.5 -> 1.6) bin/Makefile (1.3
-> 1.4) include/Makefile (1.3 -> 1.4) include/algorithm (1.4 ->
1.5) include/deque (1.6 -> 1.7) include/iterator_base (1.1 ->
1.2) include/valarray (1.1 -> 1.2) tests/algotest.cpp (1.1 ->
1.2)
Minor changes. Fix bugs. Add heap functions.
Index: uClibc++/ChangeLog
diff -u uClibc++/ChangeLog:1.2 uClibc++/ChangeLog:1.3
--- uClibc++/ChangeLog:1.2 Wed Sep 8 08:27:03 2004
+++ uClibc++/ChangeLog Thu Sep 9 22:27:16 2004
@@ -1,4 +1,11 @@
-0.1.3 - 2004.09.06
+0.1.4 - 2004-09-10
+- Fixed minor previous errors
+- Added <algorithm> heap functions. Just treat as a descending sorted list
+- Added more code to <valarray>
+- Added <, <=, >, >= comparisons to deque iterators (don't kow why I missed them in the first place)
+- Making Makefiles a little bit better.
+
+0.1.3 - 2004-09-06
- Compiles with gcc 3.4, thus it is far more "correct" than previously
- Started adding code for valarray
Index: uClibc++/Makefile
diff -u uClibc++/Makefile:1.5 uClibc++/Makefile:1.6
--- uClibc++/Makefile:1.5 Wed Sep 8 08:27:03 2004
+++ uClibc++/Makefile Thu Sep 9 22:27:16 2004
@@ -80,9 +80,7 @@
cp -fa src/*.so $(PREFIX)$(UCLIBCXX_RUNTIME_PREFIX)/lib
cp -fa src/*.so.$(MAJOR_VERSION) $(PREFIX)$(UCLIBCXX_RUNTIME_PREFIX)/lib
cp -fa src/*.so.$(MAJOR_VERSION).$(MINOR_VERSION) $(PREFIX)$(UCLIBCXX_RUNTIME_PREFIX)/lib
- $(INSTALL) -d $(PREFIX)$(UCLIBCXX_RUNTIME_PREFIX)/include
- $(INSTALL) -m 644 include/* \
- $(PREFIX)$(UCLIBCXX_RUNTIME_PREFIX)/include
+ $(MAKE) -C include install
$(INSTALL) -d $(PREFIX)$(UCLIBCXX_RUNTIME_PREFIX)/bin
$(INSTALL) -m 755 bin/g++-uc $(PREFIX)$(UCLIBCXX_RUNTIME_PREFIX)/bin
Index: uClibc++/bin/Makefile
diff -u uClibc++/bin/Makefile:1.3 uClibc++/bin/Makefile:1.4
--- uClibc++/bin/Makefile:1.3 Wed Sep 8 08:27:04 2004
+++ uClibc++/bin/Makefile Thu Sep 9 22:27:17 2004
@@ -23,7 +23,7 @@
all: wrapper
clean:
- rm $(WRAPPERNAME)
+ rm -f $(WRAPPERNAME)
wrapper:
echo "#!/bin/bash" > $(WRAPPERNAME)
Index: uClibc++/include/Makefile
diff -u uClibc++/include/Makefile:1.3 uClibc++/include/Makefile:1.4
--- uClibc++/include/Makefile:1.3 Wed Sep 8 08:27:06 2004
+++ uClibc++/include/Makefile Thu Sep 9 22:27:17 2004
@@ -6,6 +6,11 @@
clean:
distclean: clean
+
+install:
+ $(INSTALL) -d $(PREFIX)$(UCLIBCXX_RUNTIME_PREFIX)/include
+ $(INSTALL) -m 644 `ls --color=never --ignore="CVS"` $(PREFIX)$(UCLIBCXX_RUNTIME_PREFIX)/include
+
.cpp.o:
$(CXX) -c $(CXXFLAGS) -o $@ $<
Index: uClibc++/include/algorithm
diff -u uClibc++/include/algorithm:1.4 uClibc++/include/algorithm:1.5
--- uClibc++/include/algorithm:1.4 Wed Sep 8 08:27:06 2004
+++ uClibc++/include/algorithm Thu Sep 9 22:27:17 2004
@@ -863,12 +863,44 @@
}
}
- template<class RandomAccessIterator> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
+ template<class RandomAccessIterator>
+ 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>
+ 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> 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 RandomAccessIterator> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
+ template<class RandomAccessIterator>
+ 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>
+ void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
+ RandomAccessIterator last, Compare comp)
+ {
+ partial_sort(first, nth, last, comp);
+ }
template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
@@ -1080,15 +1112,73 @@
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
-
+ // *(last - 1) is the last element
+ RandomAccessIterator begin, middle, end;
+ begin = first;
+ end = last - 2;
+ if(last - first < 2){ //Empty heap
+ return;
+ }
+ if ( comp(*(last-1), *end) ){ //Belongs past the end - already in place
+ return;
+ }
+ while(end - begin > 1){
+ middle = begin + ((end - begin)/2);
+ if( comp(*middle, *(last-1) ) ){
+ end = middle;
+ }else{
+ begin = middle;
+ }
+ }
+
+ if( comp(*begin, *(last-1)) ){
+ middle = begin;
+ }else{
+ middle = end;
+ }
+
+ //Now all we do is swap the elements up to the begining
+ --last;
+
+ while(last > middle){
+ iter_swap(last, last-1);
+ --last;
+ }
+ }
+
+ template<class RandomAccessIterator> void pop_heap(RandomAccessIterator first, RandomAccessIterator last){
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ pop_heap(first, last, c);
+ }
+ template<class RandomAccessIterator, class Compare>
+ void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare)
+ {
+ --last;
+ while(first < last){
+ iter_swap( first, first+1);
+ ++first;
+ }
+ }
+
+ template<class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last){
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ sort_heap(first, last, c);
+ }
+ template<class RandomAccessIterator, class Compare>
+ void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
+ {
+ sort( reverse_iterator<RandomAccessIterator>(last), reverse_iterator<RandomAccessIterator>(first), comp);
+ }
+ template<class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last){
+ less<typename iterator_traits<RandomAccessIterator>::value_type> c;
+ sort_heap(first, last, c);
+ }
+ template<class RandomAccessIterator, class Compare>
+ void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
+ {
+ sort( reverse_iterator<RandomAccessIterator>(last), reverse_iterator<RandomAccessIterator>(first), comp);
}
- template<class RandomAccessIterator> void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare> void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
- template<class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare> void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
- template<class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare> void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
// _lib.alg.min.max_, minimum and maximum:
template<class T> const T& min(const T& a, const T& b){
Index: uClibc++/include/deque
diff -u uClibc++/include/deque:1.6 uClibc++/include/deque:1.7
--- uClibc++/include/deque:1.6 Wed Sep 8 08:27:06 2004
+++ uClibc++/include/deque Thu Sep 9 22:27:17 2004
@@ -179,6 +179,30 @@
}
return false;
}
+ bool operator<(const deque_iter & d){
+ if(element < d.element){
+ return true;
+ }
+ return false;
+ }
+ bool operator<=(const deque_iter & d){
+ if(element <= d.element){
+ return true;
+ }
+ return false;
+ }
+ bool operator>(const deque_iter & d){
+ if(element > d.element){
+ return true;
+ }
+ return false;
+ }
+ bool operator>=(const deque_iter & d){
+ if(element >= d.element){
+ return true;
+ }
+ return false;
+ }
deque_iter & operator++(){
++element;
return *this;
Index: uClibc++/include/iterator_base
diff -u uClibc++/include/iterator_base:1.1 uClibc++/include/iterator_base:1.2
--- uClibc++/include/iterator_base:1.1 Thu Sep 9 12:43:52 2004
+++ uClibc++/include/iterator_base Thu Sep 9 22:27:17 2004
@@ -153,14 +153,18 @@
reverse_iterator operator--(int) {reverse_iterator tmp = *this; ++current; return tmp; }
reverse_iterator operator+ (typename iterator_traits<Iterator>::difference_type n) const{
- return reverse_iterator(current-n);
+ reverse_iterator retval( *this );
+ retval+=n;
+ return retval;
}
reverse_iterator& operator+=(typename iterator_traits<Iterator>::difference_type n){
current -= n;
return *this;
}
- reverse_iterator operator- (typename iterator_traits<Iterator>::difference_type n) const{
- return reverse_iterator(current+n);
+ reverse_iterator operator- (typename iterator_traits<Iterator>::difference_type n) const{
+ reverse_iterator retval( *this );
+ retval-=n;
+ return retval;
}
reverse_iterator& operator-=(typename iterator_traits<Iterator>::difference_type n){
current += n;
Index: uClibc++/include/valarray
diff -u uClibc++/include/valarray:1.1 uClibc++/include/valarray:1.2
--- uClibc++/include/valarray:1.1 Thu Sep 9 12:43:52 2004
+++ uClibc++/include/valarray Thu Sep 9 22:27:17 2004
@@ -406,6 +406,52 @@
+ class slice {
+ protected:
+ size_t sta;
+ size_t siz;
+ size_t str;
+
+ public:
+ slice() : sta(0), siz(0), str(0){ }
+ slice(size_t a, size_t b, size_t c) : sta(a), siz(b), str(c) { }
+ ~slice() { }
+ size_t start() const{
+ return sta;
+ }
+ size_t size() const{
+ return siz;
+ }
+ size_t stride() const{
+ return str;
+ }
+ };
+
+
+ template <class T> class slice_array {
+ public:
+ typedef T value_type;
+
+ void operator= (const valarray<T>&) const;
+ void operator*= (const valarray<T>&) const;
+ void operator/= (const valarray<T>&) const;
+ void operator%= (const valarray<T>&) const;
+ void operator+= (const valarray<T>&) const;
+ void operator-= (const valarray<T>&) const;
+ void operator^= (const valarray<T>&) const;
+ void operator&= (const valarray<T>&) const;
+ void operator|= (const valarray<T>&) const;
+ void operator<<=(const valarray<T>&) const;
+ void operator>>=(const valarray<T>&) const;
+ void fill(const T&);
+ ~slice_array();
+ private:
+ slice_array();
+ slice_array(const slice_array&);
+ slice_array& operator=(const slice_array&);
+ };
+
+
}
Index: uClibc++/tests/algotest.cpp
diff -u uClibc++/tests/algotest.cpp:1.1 uClibc++/tests/algotest.cpp:1.2
--- uClibc++/tests/algotest.cpp:1.1 Thu Sep 9 12:42:52 2004
+++ uClibc++/tests/algotest.cpp Thu Sep 9 22:27:18 2004
@@ -191,6 +191,143 @@
+ std::cout << "Push heap\n";
+
+ a.clear();
+ a.push_back(12.5);
+
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ std::cout << "The following two lines should be identical:\n";
+ std::cout << "12.5 " << std::endl;
+ i = a.begin();
+ while(i != a.end()){
+ std::cout << *i << " ";
+ ++i;
+ }
+ std::cout << std::endl;
+
+ a.clear();
+ a.push_back(12.5);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(7.2);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(27.4);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(21.8);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(93.4);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(36.3);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(55.5);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(5.2);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(67.9);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+
+ std::cout << "The following two lines should be identical:\n";
+ std::cout << "93.4 67.9 55.5 36.6 27.4 21.8 12.5 7.2 5.2 " << std::endl;
+ i = a.begin();
+ while(i != a.end()){
+ std::cout << *i << " ";
+ ++i;
+ }
+ std::cout << std::endl;
+
+
+ std::cout << "Push heap\n";
+ a.clear();
+ a.push_back(12.5);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(7.2);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(27.4);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(21.8);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(93.4);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(36.3);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(55.5);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(5.2);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(67.9);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+
+ std::pop_heap<std::vector<double>::iterator>(a.begin(), a.end());
+
+ std::cout << "The following two lines should be identical:\n";
+ std::cout << "67.9 55.5 36.6 27.4 21.8 12.5 7.2 5.2 93.4 " << std::endl;
+ i = a.begin();
+ while(i != a.end()){
+ std::cout << *i << " ";
+ ++i;
+ }
+ std::cout << std::endl;
+
+
+ std::cout << "Sort Heap\n";
+ a.clear();
+ a.push_back(12.5);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(7.2);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(27.4);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(21.8);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(93.4);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(36.3);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(55.5);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(5.2);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+ a.push_back(67.9);
+ std::push_heap<std::vector<double>::iterator>(a.begin(), a.end());
+
+ std::sort_heap<std::vector<double>::iterator, std::greater<double> >(a.begin(), a.end(), std::greater<double>() );
+
+ std::cout << "The following two lines should be identical:\n";
+ std::cout << "5.2 7.2 12.5 21.8 27.4 36.6 55.5 67.9 93.4" << std::endl;
+ i = a.begin();
+ while(i != a.end()){
+ std::cout << *i << " ";
+ ++i;
+ }
+ std::cout << std::endl;
+
+
+ std::cout << "Partial sort test\n";
+ a.clear();
+ a.push_back(12.5);
+ a.push_back(32.7);
+ a.push_back(10.8);
+ a.push_back(92.7);
+ a.push_back(12.5);
+ a.push_back(22.7);
+ a.push_back(38.4);
+ a.push_back(52.9);
+ a.push_back(72.3);
+ a.push_back(19.6);
+
+ i = a.begin();
+ i+=4;
+
+ std::partial_sort<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 " << std::endl;
+
+ for(int k = 0; k < 5; ++k){
+ std::cout << a[k] << " ";
+ }
+ std::cout << std::endl;
+
+
return 0;
}
-
More information about the uClibc-cvs
mailing list