This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[patch] : Continue simplifying <algorithm>
- From: Chris Jefferson <caj at cs dot york dot ac dot uk>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Sun, 27 Feb 2005 00:48:10 +0000
- Subject: [patch] : Continue simplifying <algorithm>
OK, here is another patch for algorithm. This one is correct, honest (I
really hope!)
I still haven't added min/max and make_heap / sort_heap patches, as they
already exist.
Chris
2005-02-27 Christopher Jefferson <chris@bubblescope.net>
* 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_heap.h (__push_heap, __pop_heap, __adjust_heap) :
Remove unused overloads.
* include/bits/stl_algobase.h (min, max) : Make non-predicated version
call predicated version.
* testsuite/ext/is_heap/1.cc : New.
* testsuite/ext/is_heap/check_type.cc : New.
diff -x '*CVS*' -rN libstdc++-v3.so_7.clean/include/bits/stl_algobase.h libstdc++-v3.so_7/include/bits/stl_algobase.h
169a170
> * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
172,174c173,174
< * This is the simple classic generic implementation. It will work on
< * temporary expressions, since they are only evaluated once, unlike a
< * preprocessor macro.
---
> * This will work on temporary expressions, since they are only evaluated
> * once, unlike a preprocessor macro.
176c176
< template<typename _Tp>
---
> template<typename _Tp, typename _Compare>
178c178
< min(const _Tp& __a, const _Tp& __b)
---
> min(const _Tp& __a, const _Tp& __b, _Compare __comp)
180,183c180,181
< // concept requirements
< __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
< //return __b < __a ? __b : __a;
< if (__b < __a)
---
> //return __comp(__b, __a) ? __b : __a;
> if (__comp(__b, __a))
191a190
> * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
194,196c193,194
< * This is the simple classic generic implementation. It will work on
< * temporary expressions, since they are only evaluated once, unlike a
< * preprocessor macro.
---
> * This will work on temporary expressions, since they are only evaluated
> * once, unlike a preprocessor macro.
198c196
< template<typename _Tp>
---
> template<typename _Tp, typename _Compare>
200c198
< max(const _Tp& __a, const _Tp& __b)
---
> max(const _Tp& __a, const _Tp& __b, _Compare __comp)
202,205c200,201
< // concept requirements
< __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
< //return __a < __b ? __b : __a;
< if (__a < __b)
---
> //return __comp(__a, __b) ? __b : __a;
> if (__comp(__a, __b))
214d209
< * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
217,218c212,214
< * This will work on temporary expressions, since they are only evaluated
< * once, unlike a preprocessor macro.
---
> * This is the simple classic generic implementation. It will work on
> * temporary expressions, since they are only evaluated once, unlike a
> * preprocessor macro.
220c216
< template<typename _Tp, typename _Compare>
---
> template<typename _Tp>
222c218
< min(const _Tp& __a, const _Tp& __b, _Compare __comp)
---
> min(const _Tp& __a, const _Tp& __b)
224,227c220,222
< //return __comp(__b, __a) ? __b : __a;
< if (__comp(__b, __a))
< return __b;
< return __a;
---
> // concept requirements
> __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
> return min(__a, __b, __gnu_cxx::__ops::less());
234d228
< * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
237,238c231,233
< * This will work on temporary expressions, since they are only evaluated
< * once, unlike a preprocessor macro.
---
> * This is the simple classic generic implementation. It will work on
> * temporary expressions, since they are only evaluated once, unlike a
> * preprocessor macro.
240c235
< template<typename _Tp, typename _Compare>
---
> template<typename _Tp>
242c237
< max(const _Tp& __a, const _Tp& __b, _Compare __comp)
---
> max(const _Tp& __a, const _Tp& __b)
244,247c239,241
< //return __comp(__a, __b) ? __b : __a;
< if (__comp(__a, __b))
< return __b;
< return __a;
---
> // concept requirements
> __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
> return max(__a, __b, __gnu_cxx::__ops::less());
diff -x '*CVS*' -rN libstdc++-v3.so_7.clean/include/bits/stl_heap.h libstdc++-v3.so_7/include/bits/stl_heap.h
3c3
< // Copyright (C) 2001, 2004 Free Software Foundation, Inc.
---
> // Copyright (C) 2001, 2004, 2005 Free Software Foundation, Inc.
63a64
> #include <bits/predefined_ops.h>
70,84d70
< 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;
< }
<
101a88,92
> template<typename _RandomAccessIterator, typename _Distance>
> bool
> __is_heap(_RandomAccessIterator __first, _Distance __n)
> { return std::__is_heap(__first, __n, __gnu_cxx::__ops::less()); }
>
115,158d105
< 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)));
< }
<
207,241d153
< 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);
< }
<
243c155
< * @brief Pop an element off a heap.
---
> * @brief Push an element onto a heap.
245c157
< * @param last End of heap.
---
> * @param last End of heap + element.
248,249c160,161
< * 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.
---
> * 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.
253c165
< pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
---
> push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
256c168,170
< _ValueType;
---
> _ValueType;
> typedef typename iterator_traits<_RandomAccessIterator>::difference_type
> _DistanceType;
263d176
< __glibcxx_requires_heap(__first, __last);
265,266c178,180
< std::__pop_heap(__first, __last - 1, __last - 1,
< _ValueType(*(__last - 1)));
---
> std::__push_heap(__first, _DistanceType((__last - __first) - 1),
> _DistanceType(0), _ValueType(*(__last - 1)),
> __gnu_cxx::__ops::less());
335c249
< * @brief Construct a heap over a range.
---
> * @brief Pop an element off a heap.
340c254,255
< * This operation makes the elements in [first,last) into a 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.
343,344c258,259
< void
< make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
---
> inline void
> pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
347,349c262
< _ValueType;
< typedef typename iterator_traits<_RandomAccessIterator>::difference_type
< _DistanceType;
---
> _ValueType;
355a269
> __glibcxx_requires_heap(__first, __last);
357,369c271,272
< 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--;
< }
---
> std::__pop_heap(__first, __last - 1, __last - 1,
> _ValueType(*(__last - 1)), __gnu_cxx::__ops::less());
413c316
< * @brief Sort a heap.
---
> * @brief Construct a heap over a range.
418c321
< * This operation sorts the valid heap in the range [first,last).
---
> * This operation makes the elements in [first,last) into a heap.
422c325
< sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
---
> make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
423a327,331
> typedef typename iterator_traits<_RandomAccessIterator>::value_type
> _ValueType;
> typedef typename iterator_traits<_RandomAccessIterator>::difference_type
> _DistanceType;
>
425,430c333
< __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);
---
> __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
432,433c335
< while (__last - __first > 1)
< std::pop_heap(__first, __last--);
---
> std::make_heap(__first, __last, __gnu_cxx::__ops::less());
460a363,381
> /**
> * @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());
> }
>
diff -x '*CVS*' -rN libstdc++-v3.so_7.clean/testsuite/ext/is_heap/1.cc libstdc++-v3.so_7/testsuite/ext/is_heap/1.cc
0a1,58
> // 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[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
> for(int i = 0; i < 9; ++i)
> {
> container con(array, array + i);
> VERIFY(std::__is_heap(array.begin(), array.end()));
> VERIFY(std::__is_heap(array.begin(), i));
> }
> }
>
> void
> test2()
> {
> int array1[]={9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
> for(int i = 1; i < 9; ++i)
> {
> container con(array, array + i);
> VERIFY(!std::__is_heap(array.begin(), array.end()));
> VERIFY(!std::__is_heap(array.begin(), i));
> }
> }
>
> int
> main()
> {
> test1();
> test2();
> }
diff -x '*CVS*' -rN libstdc++-v3.so_7.clean/testsuite/ext/is_heap/check_type.cc libstdc++-v3.so_7/testsuite/ext/is_heap/check_type.cc
0a1,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.
>
> // { 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);
> }