This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [patch] : Continue simplifying <algorithm>
- From: Paolo Carlini <pcarlini at suse dot de>
- To: Paolo Carlini <pcarlini at suse dot de>
- Cc: Chris Jefferson <caj at cs dot york dot ac dot uk>,libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Sun, 27 Feb 2005 13:19:57 +0100
- Subject: Re: [patch] : Continue simplifying <algorithm>
- References: <422118CA.2020006@cs.york.ac.uk> <42211A0B.9040304@suse.de>
Paolo Carlini wrote:
Great! ;) Tomorrow, I'll have a quick look and then commit it.
... actually, you really wanted me to add the testcases and complete the
work ;)
1- __is_heap was still broken.
2- Same for the testcase.
3- Please remember to use either -u or -p for your diffs.
The below is what I have committed to the branch. Regtested x86-linux
Paolo.
///////////////
2005-02-27 Christopher Jefferson <chris@bubblescope.net>
Paolo Carlini <pcarlini@suse.de>
* include/bits/stl_heap.h (__is_heap, __push_heap, push_heap,
pop_heap, make_heap, sort_heap): Make non-predicated version call
predicated version.
* include/bits/stl_algobase.h (min, max): Likewise.
* testsuite/ext/is_heap/check_type.cc : New.
2005-02-27 Paolo Carlini <pcarlini@suse.de>
* testsuite/ext/is_heap/1.cc: New.diff -prN libstdc++-v3-orig/include/bits/stl_algobase.h libstdc++-v3/include/bits/stl_algobase.h
*** libstdc++-v3-orig/include/bits/stl_algobase.h Tue Feb 1 17:06:59 2005
--- libstdc++-v3/include/bits/stl_algobase.h Sun Feb 27 11:10:07 2005
*************** namespace std
*** 169,186 ****
* @param b Another thing of arbitrary type.
* @return The lesser of the parameters.
*
! * This is the simple classic generic implementation. It will work on
! * temporary expressions, since they are only evaluated once, unlike a
! * preprocessor macro.
*/
! template<typename _Tp>
inline const _Tp&
! min(const _Tp& __a, const _Tp& __b)
{
! // concept requirements
! __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
! //return __b < __a ? __b : __a;
! if (__b < __a)
return __b;
return __a;
}
--- 169,183 ----
* @param b Another thing of arbitrary type.
* @return The lesser of the parameters.
*
! * This will work on temporary expressions, since they are only evaluated
! * once, unlike a preprocessor macro.
*/
! template<typename _Tp, typename _Compare>
inline const _Tp&
! min(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
! //return __comp(__b, __a) ? __b : __a;
! if (__comp(__b, __a))
return __b;
return __a;
}
*************** namespace std
*** 189,208 ****
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
* @return The greater of the parameters.
*
! * This is the simple classic generic implementation. It will work on
! * temporary expressions, since they are only evaluated once, unlike a
! * preprocessor macro.
*/
! template<typename _Tp>
inline const _Tp&
! max(const _Tp& __a, const _Tp& __b)
{
! // concept requirements
! __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
! //return __a < __b ? __b : __a;
! if (__a < __b)
return __b;
return __a;
}
--- 186,203 ----
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
+ * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
* @return The greater of the parameters.
*
! * This will work on temporary expressions, since they are only evaluated
! * once, unlike a preprocessor macro.
*/
! template<typename _Tp, typename _Compare>
inline const _Tp&
! max(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
! //return __comp(__a, __b) ? __b : __a;
! if (__comp(__a, __b))
return __b;
return __a;
}
*************** namespace std
*** 211,250 ****
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
- * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
* @return The lesser of the parameters.
*
! * This will work on temporary expressions, since they are only evaluated
! * once, unlike a preprocessor macro.
*/
! template<typename _Tp, typename _Compare>
inline const _Tp&
! min(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
! //return __comp(__b, __a) ? __b : __a;
! if (__comp(__b, __a))
! return __b;
! return __a;
}
/**
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
- * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
* @return The greater of the parameters.
*
! * This will work on temporary expressions, since they are only evaluated
! * once, unlike a preprocessor macro.
*/
! template<typename _Tp, typename _Compare>
inline const _Tp&
! max(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
! //return __comp(__a, __b) ? __b : __a;
! if (__comp(__a, __b))
! return __b;
! return __a;
}
// All of these auxiliary structs serve two purposes. (1) Replace
--- 206,243 ----
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
* @return The lesser of the parameters.
*
! * This is the simple classic generic implementation. It will work on
! * temporary expressions, since they are only evaluated once, unlike a
! * preprocessor macro.
*/
! template<typename _Tp>
inline const _Tp&
! min(const _Tp& __a, const _Tp& __b)
{
! // concept requirements
! __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
! return min(__a, __b, __gnu_cxx::__ops::less());
}
/**
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
* @return The greater of the parameters.
*
! * This is the simple classic generic implementation. It will work on
! * temporary expressions, since they are only evaluated once, unlike a
! * preprocessor macro.
*/
! template<typename _Tp>
inline const _Tp&
! max(const _Tp& __a, const _Tp& __b)
{
! // concept requirements
! __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
! return max(__a, __b, __gnu_cxx::__ops::less());
}
// All of these auxiliary structs serve two purposes. (1) Replace
diff -prN libstdc++-v3-orig/include/bits/stl_heap.h libstdc++-v3/include/bits/stl_heap.h
*** libstdc++-v3-orig/include/bits/stl_heap.h Sun Feb 8 05:46:42 2004
--- libstdc++-v3/include/bits/stl_heap.h Sun Feb 27 11:20:23 2005
***************
*** 1,6 ****
// Heap implementation -*- C++ -*-
! // Copyright (C) 2001, 2004 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
--- 1,6 ----
// Heap implementation -*- C++ -*-
! // Copyright (C) 2001, 2004, 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
***************
*** 61,87 ****
#define _STL_HEAP_H 1
#include <debug/debug.h>
namespace std
{
// is_heap, a predicate testing whether or not a range is
// a heap. This function is an extension, not part of the C++
// standard.
- template<typename _RandomAccessIterator, typename _Distance>
- bool
- __is_heap(_RandomAccessIterator __first, _Distance __n)
- {
- _Distance __parent = 0;
- for (_Distance __child = 1; __child < __n; ++__child)
- {
- if (__first[__parent] < __first[__child])
- return false;
- if ((__child & 1) == 0)
- ++__parent;
- }
- return true;
- }
-
template<typename _RandomAccessIterator, typename _Distance,
typename _StrictWeakOrdering>
bool
--- 61,73 ----
#define _STL_HEAP_H 1
#include <debug/debug.h>
+ #include <bits/predefined_ops.h>
namespace std
{
// is_heap, a predicate testing whether or not a range is
// a heap. This function is an extension, not part of the C++
// standard.
template<typename _RandomAccessIterator, typename _Distance,
typename _StrictWeakOrdering>
bool
*************** namespace std
*** 99,104 ****
--- 85,95 ----
return true;
}
+ template<typename _RandomAccessIterator, typename _Distance>
+ bool
+ __is_heap(_RandomAccessIterator __first, _Distance __n)
+ { return std::__is_heap(__first, __gnu_cxx::__ops::less(), __n); }
+
template<typename _RandomAccessIterator>
bool
__is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
*************** namespace std
*** 112,161 ****
// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
- template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
- void
- __push_heap(_RandomAccessIterator __first,
- _Distance __holeIndex, _Distance __topIndex, _Tp __value)
- {
- _Distance __parent = (__holeIndex - 1) / 2;
- while (__holeIndex > __topIndex && *(__first + __parent) < __value)
- {
- *(__first + __holeIndex) = *(__first + __parent);
- __holeIndex = __parent;
- __parent = (__holeIndex - 1) / 2;
- }
- *(__first + __holeIndex) = __value;
- }
-
- /**
- * @brief Push an element onto a heap.
- * @param first Start of heap.
- * @param last End of heap + element.
- * @ingroup heap
- *
- * This operation pushes the element at last-1 onto the valid heap over the
- * range [first,last-1). After completion, [first,last) is a valid heap.
- */
- template<typename _RandomAccessIterator>
- inline void
- push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
- {
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
-
- // concept requirements
- __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- __glibcxx_requires_valid_range(__first, __last);
- // __glibcxx_requires_heap(__first, __last - 1);
-
- std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _ValueType(*(__last - 1)));
- }
-
template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
typename _Compare>
void
--- 103,108 ----
*************** namespace std
*** 204,269 ****
_DistanceType(0), _ValueType(*(__last - 1)), __comp);
}
- template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
- void
- __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
- _Distance __len, _Tp __value)
- {
- const _Distance __topIndex = __holeIndex;
- _Distance __secondChild = 2 * __holeIndex + 2;
- while (__secondChild < __len)
- {
- if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
- __secondChild--;
- *(__first + __holeIndex) = *(__first + __secondChild);
- __holeIndex = __secondChild;
- __secondChild = 2 * (__secondChild + 1);
- }
- if (__secondChild == __len)
- {
- *(__first + __holeIndex) = *(__first + (__secondChild - 1));
- __holeIndex = __secondChild - 1;
- }
- std::__push_heap(__first, __holeIndex, __topIndex, __value);
- }
-
- template<typename _RandomAccessIterator, typename _Tp>
- inline void
- __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _RandomAccessIterator __result, _Tp __value)
- {
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _Distance;
- *__result = *__first;
- std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
- __value);
- }
-
/**
! * @brief Pop an element off a heap.
* @param first Start of heap.
! * @param last End of heap.
* @ingroup heap
*
! * This operation pops the top of the heap. The elements first and last-1
! * are swapped and [first,last-1) is made into a heap.
*/
template<typename _RandomAccessIterator>
inline void
! pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
! _ValueType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
- __glibcxx_requires_heap(__first, __last);
! std::__pop_heap(__first, __last - 1, __last - 1,
! _ValueType(*(__last - 1)));
}
template<typename _RandomAccessIterator, typename _Distance,
--- 151,183 ----
_DistanceType(0), _ValueType(*(__last - 1)), __comp);
}
/**
! * @brief Push an element onto a heap.
* @param first Start of heap.
! * @param last End of heap + element.
* @ingroup heap
*
! * This operation pushes the element at last-1 onto the valid heap over the
! * range [first,last-1). After completion, [first,last) is a valid heap.
*/
template<typename _RandomAccessIterator>
inline void
! push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
! _ValueType;
! typedef typename iterator_traits<_RandomAccessIterator>::difference_type
! _DistanceType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
! std::__push_heap(__first, _DistanceType((__last - __first) - 1),
! _DistanceType(0), _ValueType(*(__last - 1)),
! __gnu_cxx::__ops::less());
}
template<typename _RandomAccessIterator, typename _Distance,
*************** namespace std
*** 332,372 ****
}
/**
! * @brief Construct a heap over a range.
* @param first Start of heap.
* @param last End of heap.
* @ingroup heap
*
! * This operation makes the elements in [first,last) into a heap.
*/
template<typename _RandomAccessIterator>
! void
! make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
! _ValueType;
! typedef typename iterator_traits<_RandomAccessIterator>::difference_type
! _DistanceType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
! if (__last - __first < 2)
! return;
!
! const _DistanceType __len = __last - __first;
! _DistanceType __parent = (__len - 2) / 2;
! while (true)
! {
! std::__adjust_heap(__first, __parent, __len,
! _ValueType(*(__first + __parent)));
! if (__parent == 0)
! return;
! __parent--;
! }
}
/**
--- 246,275 ----
}
/**
! * @brief Pop an element off a heap.
* @param first Start of heap.
* @param last End of heap.
* @ingroup heap
*
! * This operation pops the top of the heap. The elements first and last-1
! * are swapped and [first,last-1) is made into a heap.
*/
template<typename _RandomAccessIterator>
! inline void
! pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
! _ValueType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
+ __glibcxx_requires_heap(__first, __last);
! std::__pop_heap(__first, __last - 1, __last - 1,
! _ValueType(*(__last - 1)), __gnu_cxx::__ops::less());
}
/**
*************** namespace std
*** 410,436 ****
}
/**
! * @brief Sort a heap.
* @param first Start of heap.
* @param last End of heap.
* @ingroup heap
*
! * This operation sorts the valid heap in the range [first,last).
*/
template<typename _RandomAccessIterator>
void
! sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
! __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
! _RandomAccessIterator>)
! __glibcxx_function_requires(_LessThanComparableConcept<
! typename iterator_traits<_RandomAccessIterator>::value_type>)
! __glibcxx_requires_valid_range(__first, __last);
! // __glibcxx_requires_heap(__first, __last);
! while (__last - __first > 1)
! std::pop_heap(__first, __last--);
}
/**
--- 313,338 ----
}
/**
! * @brief Construct a heap over a range.
* @param first Start of heap.
* @param last End of heap.
* @ingroup heap
*
! * This operation makes the elements in [first,last) into a heap.
*/
template<typename _RandomAccessIterator>
void
! make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+ _DistanceType;
+
// concept requirements
! __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
! std::make_heap(__first, __last, __gnu_cxx::__ops::less());
}
/**
*************** namespace std
*** 458,463 ****
--- 360,384 ----
std::pop_heap(__first, __last--, __comp);
}
+ /**
+ * @brief Sort a heap.
+ * @param first Start of heap.
+ * @param last End of heap.
+ * @ingroup heap
+ *
+ * This operation sorts the valid heap in the range [first,last).
+ */
+ template<typename _RandomAccessIterator>
+ void
+ sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_LessThanComparableConcept<
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
+
+ std::sort_heap(__first, __last, __gnu_cxx::__ops::less());
+ }
+
} // namespace std
#endif /* _STL_HEAP_H */
diff -prN libstdc++-v3-orig/testsuite/ext/is_heap/1.cc libstdc++-v3/testsuite/ext/is_heap/1.cc
*** libstdc++-v3-orig/testsuite/ext/is_heap/1.cc Thu Jan 1 01:00:00 1970
--- libstdc++-v3/testsuite/ext/is_heap/1.cc Sun Feb 27 12:17:50 2005
***************
*** 0 ****
--- 1,46 ----
+ // Copyright (C) 2005 Free Software Foundation, Inc.
+ //
+ // This file is part of the GNU ISO C++ Library. This library is free
+ // software; you can redistribute it and/or modify it under the
+ // terms of the GNU General Public License as published by the
+ // Free Software Foundation; either version 2, or (at your option)
+ // any later version.
+
+ // This library is distributed in the hope that it will be useful,
+ // but WITHOUT ANY WARRANTY; without even the implied warranty of
+ // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ // GNU General Public License for more details.
+
+ // You should have received a copy of the GNU General Public License along
+ // with this library; see the file COPYING. If not, write to the Free
+ // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+ // USA.
+
+ #include <algorithm>
+ #include <testsuite_hooks.h>
+ #include <testsuite_iterators.h>
+
+ using __gnu_test::test_container;
+ using __gnu_test::random_access_iterator_wrapper;
+
+ typedef test_container<int, random_access_iterator_wrapper> container;
+
+ void
+ test1()
+ {
+ int array[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+ for(int i = 0; i < 10; ++i)
+ {
+ container con(array, array + i);
+ std::make_heap(con.begin(), con.end());
+ VERIFY(std::__is_heap(con.begin(), con.end()));
+ VERIFY(std::__is_heap(con.begin(), i));
+ }
+ }
+
+ int
+ main()
+ {
+ test1();
+ return 0;
+ }
diff -prN libstdc++-v3-orig/testsuite/ext/is_heap/check_type.cc libstdc++-v3/testsuite/ext/is_heap/check_type.cc
*** libstdc++-v3-orig/testsuite/ext/is_heap/check_type.cc Thu Jan 1 01:00:00 1970
--- libstdc++-v3/testsuite/ext/is_heap/check_type.cc Sun Feb 27 11:13:55 2005
***************
*** 0 ****
--- 1,47 ----
+ // Copyright (C) 2005 Free Software Foundation, Inc.
+ //
+ // This file is part of the GNU ISO C++ Library. This library is free
+ // software; you can redistribute it and/or modify it under the
+ // terms of the GNU General Public License as published by the
+ // Free Software Foundation; either version 2, or (at your option)
+ // any later version.
+
+ // This library is distributed in the hope that it will be useful,
+ // but WITHOUT ANY WARRANTY; without even the implied warranty of
+ // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ // GNU General Public License for more details.
+
+ // You should have received a copy of the GNU General Public License along
+ // with this library; see the file COPYING. If not, write to the Free
+ // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+ // USA.
+
+ // { dg-do compile }
+
+ #include <algorithm>
+ #include <testsuite_iterators.h>
+
+ using __gnu_test::random_access_iterator_wrapper;
+
+ struct S { };
+
+ bool
+ operator<(const S&, const S&) {return true;}
+
+ struct X { };
+
+ bool
+ predicate(const X&, const X&) {return true;}
+
+ bool
+ test1(random_access_iterator_wrapper<S>& start,
+ random_access_iterator_wrapper<S>& end)
+ { return std::__is_heap(start, end) && std::__is_heap(start, 1); }
+
+ bool
+ test2(random_access_iterator_wrapper<X>& start,
+ random_access_iterator_wrapper<X>& end)
+ {
+ return std::__is_heap(start, end, predicate) &&
+ std::__is_heap(start, predicate, 1);
+ }