2001-07-17 Stephen M. Webb <stephen@bregmasoft.com>r

	All occurrences of the __value_type() and __distance_type()
	functions, which were required to support the HP STL, have been
	removed along with all the auxiliary forwarding functions that
	were required to support their use.

	The __iterator_category() function was pretty much left alone
	because there was no benefit to removing it and its use made code
	just a little more readable.

	Incidences of distance() with nonstandard argument list were
	replaced by calls to the standard function (only in the files
	affected by the removal of the other HP functions).

	The signature of the rotate() algorithm was changed to match the
	standard.

	Headers were reformatted under C++STYLE guidelines (indentation,
	linebreaks, typename keyword).

	* include/bits/stl_algo.h: replaced __value_type() and
	__distance_type() with iterator_traits, eliminated auxiliary
	support functions required to support said function usage.
	Changed nonstandard distance() call to standard call.

	* include/bits/stl_algobase.h: Same.
	* include/bits/stl_heap.h: Same.
	* include/bits/stl_numeric.h: Same.
	* include/bits/stl_uninitialized.h: Same.
	* include/bits/stl_iterator_base_types.h (__value_type()):
	Removed.
	(__distance_type()): Removed.
	(value_type()): Gone.
	(distance_type()): Done in.
	(iterator_category()): Hasta la vista, baby.

	* include/bits/stl_iterator_base_funcs.h (iterator_category()):
	Replaced with __iterator_category().
	* include/backward/iterator.h: moved definition of value_type(),
	distance_type(), and iterator_category() out of std:: and into
	here.
	* testsuite/23_containers/vector_ctor.cc (test03): New testcases.
	* testsuite/23_containers/vector_modifiers.cc (test03): New testcases.
	* testsuite/25_algorithms/rotate.cc: New testcase.
	* testsuite/25_algorithms/copy.cc: New testcase.
	* testsuite/25_algorithms/sort.cc: Same.
	* testsuite/25_algorithms/heap.cc: Same.
	* testsuite/25_algorithms/partition.cc: Same.
	* testsuite/25_algorithms/binary_search.cc: Same.
	* testsuite/26_numerics/sum_diff.cc: Ditto.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@44117 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 235 insertions, 271 deletions

diff --git a/libstdc++-v3/include/bits/stl_heap.h b/libstdc++-v3/include/bits/stl_heap.h
index 20d0f000d1a..eebf2ca3b7e 100644
--- a/libstdc++-v3/include/bits/stl_heap.h
+++ b/libstdc++-v3/include/bits/stl_heap.h
@@ -62,277 +62,241 @@
 namespace std
 {
 
-// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
-
-template <class _RandomAccessIterator, class _Distance, class _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;
-}
-
-template <class _RandomAccessIterator, class _Distance, class _Tp>
-inline void 
-__push_heap_aux(_RandomAccessIterator __first,
-                _RandomAccessIterator __last, _Distance*, _Tp*)
-{
-  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
-              _Tp(*(__last - 1)));
-}
-
-template <class _RandomAccessIterator>
-inline void 
-push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
-  // concept requirements
-  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
-        _RandomAccessIterator>);
-  __glibcpp_function_requires(_LessThanComparableConcept<
-        typename iterator_traits<_RandomAccessIterator>::value_type>);
-
-  __push_heap_aux(__first, __last,
-                  __distance_type(__first), __value_type(__first));
-}
-
-template <class _RandomAccessIterator, class _Distance, class _Tp, 
-          class _Compare>
-void
-__push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
-            _Distance __topIndex, _Tp __value, _Compare __comp)
-{
-  _Distance __parent = (__holeIndex - 1) / 2;
-  while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
-    *(__first + __holeIndex) = *(__first + __parent);
-    __holeIndex = __parent;
-    __parent = (__holeIndex - 1) / 2;
-  }
-  *(__first + __holeIndex) = __value;
-}
-
-template <class _RandomAccessIterator, class _Compare,
-          class _Distance, class _Tp>
-inline void 
-__push_heap_aux(_RandomAccessIterator __first,
-                _RandomAccessIterator __last, _Compare __comp,
-                _Distance*, _Tp*) 
-{
-  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
-              _Tp(*(__last - 1)), __comp);
-}
-
-template <class _RandomAccessIterator, class _Compare>
-inline void 
-push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
-          _Compare __comp)
-{
-  // concept requirements
-  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
-        _RandomAccessIterator>);
-
-  __push_heap_aux(__first, __last, __comp,
-                  __distance_type(__first), __value_type(__first));
-}
-
-template <class _RandomAccessIterator, class _Distance, class _Tp>
-void 
-__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
-              _Distance __len, _Tp __value)
-{
-  _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;
-  }
-  __push_heap(__first, __holeIndex, __topIndex, __value);
-}
-
-template <class _RandomAccessIterator, class _Tp, class _Distance>
-inline void 
-__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
-           _RandomAccessIterator __result, _Tp __value, _Distance*)
-{
-  *__result = *__first;
-  __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
-}
-
-template <class _RandomAccessIterator, class _Tp>
-inline void 
-__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
-               _Tp*)
-{
-  __pop_heap(__first, __last - 1, __last - 1, 
-             _Tp(*(__last - 1)), __distance_type(__first));
-}
-
-template <class _RandomAccessIterator>
-inline void pop_heap(_RandomAccessIterator __first, 
-                     _RandomAccessIterator __last)
-{
-  // concept requirements
-  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
-        _RandomAccessIterator>);
-  __glibcpp_function_requires(_LessThanComparableConcept<
-        typename iterator_traits<_RandomAccessIterator>::value_type>);
-
-  __pop_heap_aux(__first, __last, __value_type(__first));
-}
-
-template <class _RandomAccessIterator, class _Distance,
-          class _Tp, class _Compare>
-void
-__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
-              _Distance __len, _Tp __value, _Compare __comp)
-{
-  _Distance __topIndex = __holeIndex;
-  _Distance __secondChild = 2 * __holeIndex + 2;
-  while (__secondChild < __len) {
-    if (__comp(*(__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;
-  }
-  __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
-}
-
-template <class _RandomAccessIterator, class _Tp, class _Compare, 
-          class _Distance>
-inline void 
-__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
-           _RandomAccessIterator __result, _Tp __value, _Compare __comp,
-           _Distance*)
-{
-  *__result = *__first;
-  __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
-                __value, __comp);
-}
-
-template <class _RandomAccessIterator, class _Tp, class _Compare>
-inline void 
-__pop_heap_aux(_RandomAccessIterator __first,
-               _RandomAccessIterator __last, _Tp*, _Compare __comp)
-{
-  __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
-             __distance_type(__first));
-}
-
-template <class _RandomAccessIterator, class _Compare>
-inline void 
-pop_heap(_RandomAccessIterator __first,
-         _RandomAccessIterator __last, _Compare __comp)
-{
-  // concept requirements
-  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
-        _RandomAccessIterator>);
-
-  __pop_heap_aux(__first, __last, __value_type(__first), __comp);
-}
-
-template <class _RandomAccessIterator, class _Tp, class _Distance>
-void 
-__make_heap(_RandomAccessIterator __first,
-            _RandomAccessIterator __last, _Tp*, _Distance*)
-{
-  if (__last - __first < 2) return;
-  _Distance __len = __last - __first;
-  _Distance __parent = (__len - 2)/2;
-    
-  while (true) {
-    __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
-    if (__parent == 0) return;
-    __parent--;
-  }
-}
-
-template <class _RandomAccessIterator>
-inline void 
-make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
-  // concept requirements
-  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
-        _RandomAccessIterator>);
-  __glibcpp_function_requires(_LessThanComparableConcept<
-        typename iterator_traits<_RandomAccessIterator>::value_type>);
-
-  __make_heap(__first, __last,
-              __value_type(__first), __distance_type(__first));
-}
-
-template <class _RandomAccessIterator, class _Compare,
-          class _Tp, class _Distance>
-void
-__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
-            _Compare __comp, _Tp*, _Distance*)
-{
-  if (__last - __first < 2) return;
-  _Distance __len = __last - __first;
-  _Distance __parent = (__len - 2)/2;
-    
-  while (true) {
-    __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
-                  __comp);
-    if (__parent == 0) return;
-    __parent--;
-  }
-}
-
-template <class _RandomAccessIterator, class _Compare>
-inline void 
-make_heap(_RandomAccessIterator __first, 
-          _RandomAccessIterator __last, _Compare __comp)
-{
-  // concept requirements
-  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
-        _RandomAccessIterator>);
-
-  __make_heap(__first, __last, __comp,
-              __value_type(__first), __distance_type(__first));
-}
-
-template <class _RandomAccessIterator>
-void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
-  // concept requirements
-  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
-        _RandomAccessIterator>);
-  __glibcpp_function_requires(_LessThanComparableConcept<
-        typename iterator_traits<_RandomAccessIterator>::value_type>);
-
-  while (__last - __first > 1)
-    pop_heap(__first, __last--);
-}
-
-template <class _RandomAccessIterator, class _Compare>
-void 
-sort_heap(_RandomAccessIterator __first,
-          _RandomAccessIterator __last, _Compare __comp)
-{
-  // concept requirements
-  __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
-        _RandomAccessIterator>);
-
-  while (__last - __first > 1)
-    pop_heap(__first, __last--, __comp);
-}
+  // 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;
+    }
+
+  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
+      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+	    _RandomAccessIterator>);
+      __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>);
+
+      __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
+		  _ValueType(*(__last - 1)));
+    }
+
+  template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 
+	    typename _Compare>
+    void
+    __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
+		_Distance __topIndex, _Tp __value, _Compare __comp)
+    {
+      _Distance __parent = (__holeIndex - 1) / 2;
+      while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
+	*(__first + __holeIndex) = *(__first + __parent);
+	__holeIndex = __parent;
+	__parent = (__holeIndex - 1) / 2;
+      }
+      *(__first + __holeIndex) = __value;
+    }
+
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline void 
+    push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+	      _Compare __comp)
+    {
+      typedef typename iterator_traits<_RandomAccessIterator>::value_type
+	  _ValueType;
+      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+	  _DistanceType;
+
+      // concept requirements
+      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+	    _RandomAccessIterator>);
+
+      __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 
+		  _ValueType(*(__last - 1)), __comp);
+    }
+
+  template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
+    void 
+    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
+		  _Distance __len, _Tp __value)
+    {
+      _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;
+      }
+      __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;
+      __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
+    }
+
+  template<typename _RandomAccessIterator>
+    inline void
+    pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+    {
+      typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
+
+      // concept requirements
+      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+	    _RandomAccessIterator>);
+      __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>);
+
+      __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)));
+    }
+
+  template<typename _RandomAccessIterator, typename _Distance,
+	   typename _Tp, typename _Compare>
+    void
+    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
+		  _Distance __len, _Tp __value, _Compare __comp)
+    {
+      _Distance __topIndex = __holeIndex;
+      _Distance __secondChild = 2 * __holeIndex + 2;
+      while (__secondChild < __len) {
+	if (__comp(*(__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;
+      }
+      __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
+    }
+
+  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
+    inline void 
+    __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+	       _RandomAccessIterator __result, _Tp __value, _Compare __comp)
+    {
+      typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
+      *__result = *__first;
+      __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
+		    __value, __comp);
+    }
+
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline void 
+    pop_heap(_RandomAccessIterator __first,
+	     _RandomAccessIterator __last, _Compare __comp)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+	    _RandomAccessIterator>);
+
+      typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
+      __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp);
+    }
+
+  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
+      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+	    _RandomAccessIterator>);
+      __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>);
+
+      if (__last - __first < 2) return;
+      _DistanceType __len = __last - __first;
+      _DistanceType __parent = (__len - 2)/2;
+	
+      while (true) {
+	__adjust_heap(__first, __parent, __len, _ValueType(*(__first + __parent)));
+	if (__parent == 0) return;
+	__parent--;
+      }
+    }
+
+  template<typename _RandomAccessIterator, typename _Compare>
+    inline void 
+    make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+	      _Compare __comp)
+    {
+      typedef typename iterator_traits<_RandomAccessIterator>::value_type
+	  _ValueType;
+      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+	  _DistanceType;
+
+      // concept requirements
+      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+	    _RandomAccessIterator>);
+
+      if (__last - __first < 2) return;
+      _DistanceType __len = __last - __first;
+      _DistanceType __parent = (__len - 2)/2;
+	
+      while (true) {
+	__adjust_heap(__first, __parent, __len,
+	              _ValueType(*(__first + __parent)), __comp);
+	if (__parent == 0) return;
+	__parent--;
+      }
+    }
+
+  template<typename _RandomAccessIterator>
+    void
+    sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+	    _RandomAccessIterator>);
+      __glibcpp_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_RandomAccessIterator>::value_type>);
+
+      while (__last - __first > 1)
+	pop_heap(__first, __last--);
+    }
+
+  template<typename _RandomAccessIterator, typename _Compare>
+    void 
+    sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
+	      _Compare __comp)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+	    _RandomAccessIterator>);
+
+      while (__last - __first > 1)
+	pop_heap(__first, __last--, __comp);
+    }
 
 } // namespace std