2002-04-05 Jonathan Wakely <jw@kayari.org>

	* include/bits/stl_algo.h (unique_copy, __gcd, rotate, rotate_copy,
	random_shuffle, partition, stable_partition, sort, stable_sort,
	partial_sort, partial_sort_copy, nth_element):  Doxygenate.


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

2 files changed, 151 insertions, 41 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 01edcd9378d..97de30d917d 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,9 @@
+2002-04-05  Jonathan Wakely <jw@kayari.org>
+
+	* include/bits/stl_algo.h (unique_copy, __gcd, rotate, rotate_copy,
+	random_shuffle, partition, stable_partition, sort, stable_sort,
+	partial_sort, partial_sort_copy, nth_element):  Doxygenate.
+
 2002-04-05  David S. Miller  <davem@redhat.com>
 
 	* config/os/gnu-linux/bits/os_defines.h
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 35832c3e1d9..4263e7711e8 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -1139,6 +1139,8 @@ namespace std
    *  Copies each element in the range @p [first,last) to the range
    *  beginning at @p result, except that only the first element is copied
    *  from groups of consecutive elements that compare equal.
+   *  unique_copy() is stable, so the relative order of elements that are
+   *  copied is unchanged.
   */
   template<typename _InputIter, typename _OutputIter>
     inline _OutputIter
@@ -1391,6 +1393,7 @@ __result, __binary_pred, _IterType());
   /**
    *  @if maint
    *  This is a helper function for the rotate algorithm specialized on RAIs.
+   *  It returns the greatest common divisor of two integer values.
    *  @endif
   */
   template<typename _EuclideanRingElement>
@@ -1538,13 +1541,22 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Rotate the elements of a sequence.
    *  @param  first   A forward iterator.
    *  @param  middle  A forward iterator.
    *  @param  last    A forward iterator.
    *  @return  Nothing.
    *
-   *  @doctodo
+   *  Rotates the elements of the range @p [first,last) by @p (middle-first)
+   *  positions so that the element at @p middle is moved to @p first, the
+   *  element at @p middle+1 is moved to @first+1 and so on for each element
+   *  in the range @p [first,last).
+   *
+   *  This effectively swaps the ranges @p [first,middle) and
+   *  @p [middle,last).
+   *
+   *  Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
+   *  each @p n in the range @p [0,last-first).
   */
   template<typename _ForwardIter>
     inline void
@@ -1558,14 +1570,21 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Copy a sequence, rotating its elements.
    *  @param  first   A forward iterator.
    *  @param  middle  A forward iterator.
    *  @param  last    A forward iterator.
    *  @param  result  An output iterator.
-   *  @return  TODO
+   *  @return   An iterator designating the end of the resulting sequence.
    *
-   *  @doctodo
+   *  Copies the elements of the range @p [first,last) to the range
+   *  beginning at @result, rotating the copied elements by @p (middle-first)
+   *  positions so that the element at @p middle is moved to @p result, the
+   *  element at @p middle+1 is moved to @result+1 and so on for each element
+   *  in the range @p [first,last).
+   *
+   *  Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
+   *  each @p n in the range @p [0,last-first).
   */
   template<typename _ForwardIter, typename _OutputIter>
     _OutputIter
@@ -1603,12 +1622,14 @@ __result, __binary_pred, _IterType());
 
 
   /**
-   *  @brief TODO
+   *  @brief Randomly shuffle the elements of a sequence.
    *  @param  first   A forward iterator.
    *  @param  last    A forward iterator.
    *  @return  Nothing.
    *
-   *  @doctodo
+   *  Reorder the elements in the range @p [first,last) using a random
+   *  distribution, so that every possible ordering of the sequence is
+   *  equally likely.
   */
   template<typename _RandomAccessIter>
     inline void
@@ -1624,13 +1645,17 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Shuffle the elements of a sequence using a random number
+   *         generator.
    *  @param  first   A forward iterator.
    *  @param  last    A forward iterator.
    *  @param  rand    The RNG functor or function.
    *  @return  Nothing.
    *
-   *  @doctodo
+   *  Reorders the elements in the range @p [first,last) using @p rand to
+   *  provide a random distribution. Calling @p rand(N) for a positive
+   *  integer @p N should return a randomly chosen integer from the
+   *  range [0,N).
   */
   template<typename _RandomAccessIter, typename _RandomNumberGenerator>
     void
@@ -1707,13 +1732,18 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Move elements for which a predicate is true to the beginning
+   *         of a sequence.
    *  @param  first   A forward iterator.
    *  @param  last    A forward iterator.
    *  @param  pred    A predicate functor.
-   *  @return  TODO
-   *
-   *  @doctodo
+   *  @return  An iterator @p middle such that @p pred(i) is true for each
+   *  iterator @p i in the range @p [first,middle) and false for each @p i
+   *  in the range @p [middle,last).
+   *  
+   *  @p pred must not modify its operand. @p partition() does not preserve
+   *  the relative ordering of elements in each group, use
+   *  @p stable_partition() if this is needed.
   */
   template<typename _ForwardIter, typename _Predicate>
     inline _ForwardIter
@@ -1800,13 +1830,20 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Move elements for which a predicate is true to the beginning
+   *         of a sequence, preserving relative ordering.
    *  @param  first   A forward iterator.
    *  @param  last    A forward iterator.
    *  @param  pred    A predicate functor.
-   *  @return  TODO
-   *
-   *  @doctodo
+   *  @return  An iterator @p middle such that @p pred(i) is true for each
+   *  iterator @p i in the range @p [first,middle) and false for each @p i
+   *  in the range @p [middle,last).
+   *  
+   *  Performs the same function as @p partition() with the additional
+   *  guarantee that the relative ordering of elements in each group is
+   *  preserved, so any two elements @p x and @p y in the range
+   *  @p [first,last) such that @p pred(x)==pred(y) will have the same
+   *  relative ordering after calling @p stable_partition().
   */
   template<typename _ForwardIter, typename _Predicate>
     _ForwardIter
@@ -2114,12 +2151,17 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Sort the elements of a sequence.
    *  @param  first   An iterator.
    *  @param  last    Another iterator.
    *  @return  Nothing.
    *
-   *  @doctodo
+   *  Sorts the elements in the range @p [first,last) in ascending order,
+   *  such that @p *(i+1)<*i is false for each iterator @p i in the range
+   *  @p [first,last-1).
+   *
+   *  The relative ordering of equivalent elements is not preserved, use
+   *  @p stable_sort() if this is needed.
   */
   template<typename _RandomAccessIter>
     inline void
@@ -2139,13 +2181,18 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Sort the elements of a sequence using a predicate for comparison.
    *  @param  first   An iterator.
    *  @param  last    Another iterator.
    *  @param  comp    A comparison functor.
    *  @return  Nothing.
    *
-   *  @doctodo
+   *  Sorts the elements in the range @p [first,last) in ascending order,
+   *  such that @p comp(*(i+1),*i) is false for every iterator @p i in the
+   *  range @p [first,last-1).
+   *
+   *  The relative ordering of equivalent elements is not preserved, use
+   *  @p stable_sort() if this is needed.
   */
   template<typename _RandomAccessIter, typename _Compare>
     inline void
@@ -2365,12 +2412,20 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Sort the elements of a sequence, preserving the relative order
+   *         of equivalent elements.
    *  @param  first   An iterator.
    *  @param  last    Another iterator.
    *  @return  Nothing.
    *
-   *  @doctodo
+   *  Sorts the elements in the range @p [first,last) in ascending order,
+   *  such that @p *(i+1)<*i is false for each iterator @p i in the range
+   *  @p [first,last-1).
+   *
+   *  The relative ordering of equivalent elements is preserved, so any two
+   *  elements @p x and @p y in the range @p [first,last) such that
+   *  @p x<y is false and @p y<x is false will have the same relative
+   *  ordering after calling @p stable_sort().
   */
   template<typename _RandomAccessIter>
     inline void
@@ -2392,13 +2447,21 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Sort the elements of a sequence using a predicate for comparison,
+   *         preserving the relative order of equivalent elements.
    *  @param  first   An iterator.
    *  @param  last    Another iterator.
    *  @param  comp    A comparison functor.
    *  @return  Nothing.
    *
-   *  @doctodo
+   *  Sorts the elements in the range @p [first,last) in ascending order,
+   *  such that @p comp(*(i+1),*i) is false for each iterator @p i in the
+   *  range @p [first,last-1).
+   *
+   *  The relative ordering of equivalent elements is preserved, so any two
+   *  elements @p x and @p y in the range @p [first,last) such that
+   *  @p comp(x,y) is false and @p comp(y,x) is false will have the same
+   *  relative ordering after calling @p stable_sort().
   */
   template<typename _RandomAccessIter, typename _Compare>
     inline void
@@ -2422,13 +2485,19 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Sort the smallest elements of a sequence.
    *  @param  first   An iterator.
    *  @param  middle  Another iterator.
    *  @param  last    Another iterator.
    *  @return  Nothing.
    *
-   *  @doctodo
+   *  Sorts the smallest @p (middle-first) elements in the range
+   *  @p [first,last) and moves them to the range @p [first,middle). The
+   *  order of the remaining elements in the range @p [middle,last) is
+   *  undefined.
+   *  After the sort if @p i and @j are iterators in the range
+   *  @p [first,middle) such that @i precedes @j and @k is an iterator in
+   *  the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
   */
   template<typename _RandomAccessIter>
     void
@@ -2451,14 +2520,22 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Sort the smallest elements of a sequence using a predicate
+   *         for comparison.
    *  @param  first   An iterator.
    *  @param  middle  Another iterator.
    *  @param  last    Another iterator.
    *  @param  comp    A comparison functor.
    *  @return  Nothing.
    *
-   *  @doctodo
+   *  Sorts the smallest @p (middle-first) elements in the range
+   *  @p [first,last) and moves them to the range @p [first,middle). The
+   *  order of the remaining elements in the range @p [middle,last) is
+   *  undefined.
+   *  After the sort if @p i and @j are iterators in the range
+   *  @p [first,middle) such that @i precedes @j and @k is an iterator in
+   *  the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
+   *  are both false.
   */
   template<typename _RandomAccessIter, typename _Compare>
     void
@@ -2483,14 +2560,21 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
-   *  @param  first   An input iterator.
-   *  @param  last    Another input iterator.
+   *  @brief Copy the smallest elements of a sequence.
+   *  @param  first   An iterator.
+   *  @param  last    Another iterator.
    *  @param  result_first   A random-access iterator.
    *  @param  result_last    Another random-access iterator.
-   *  @return  TODO
+   *  @return   An iterator indicating the end of the resulting sequence.
    *
-   *  @doctodo
+   *  Copies and sorts the smallest N values from the range @p [first,last)
+   *  to the range beginning at @p result_first, where the number of
+   *  elements to be copied, @p N, is the smaller of @p (last-first) and
+   *  @p (result_last-result_first).
+   *  After the sort if @p i and @j are iterators in the range
+   *  @p [result_first,result_first+N) such that @i precedes @j then
+   *  @p *j<*i is false.
+   *  The value returned is @p result_first+N.
   */
   template<typename _InputIter, typename _RandomAccessIter>
     _RandomAccessIter
@@ -2528,15 +2612,23 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Copy the smallest elements of a sequence using a predicate for
+   *         comparison.
    *  @param  first   An input iterator.
    *  @param  last    Another input iterator.
    *  @param  result_first   A random-access iterator.
    *  @param  result_last    Another random-access iterator.
    *  @param  comp    A comparison functor.
-   *  @return  TODO
+   *  @return   An iterator indicating the end of the resulting sequence.
    *
-   *  @doctodo
+   *  Copies and sorts the smallest N values from the range @p [first,last)
+   *  to the range beginning at @p result_first, where the number of
+   *  elements to be copied, @p N, is the smaller of @p (last-first) and
+   *  @p (result_last-result_first).
+   *  After the sort if @p i and @j are iterators in the range
+   *  @p [result_first,result_first+N) such that @i precedes @j then
+   *  @p comp(*j,*i) is false.
+   *  The value returned is @p result_first+N.
   */
   template<typename _InputIter, typename _RandomAccessIter, typename _Compare>
     _RandomAccessIter
@@ -2577,13 +2669,19 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Sort a sequence just enough to find a particular position.
    *  @param  first   An iterator.
    *  @param  nth     Another iterator.
    *  @param  last    Another iterator.
    *  @return  Nothing.
    *
-   *  @doctodo
+   *  Rearranges the elements in the range @p [first,last) so that @p *nth
+   *  is the same element that would have been in that position had the
+   *  whole sequence been sorted. 
+   *  whole sequence been sorted. The elements either side of @p *nth are
+   *  not completely sorted, but for any iterator @i in the range
+   *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
+   *  holds that @p *j<*i is false.
   */
   template<typename _RandomAccessIter>
     void
@@ -2612,14 +2710,20 @@ __result, __binary_pred, _IterType());
     }
 
   /**
-   *  @brief TODO
+   *  @brief Sort a sequence just enough to find a particular position
+   *         using a predicate for comparison.
    *  @param  first   An iterator.
    *  @param  nth     Another iterator.
    *  @param  last    Another iterator.
    *  @param  comp    A comparison functor.
    *  @return  Nothing.
    *
-   *  @doctodo
+   *  Rearranges the elements in the range @p [first,last) so that @p *nth
+   *  is the same element that would have been in that position had the
+   *  whole sequence been sorted. The elements either side of @p *nth are
+   *  not completely sorted, but for any iterator @i in the range
+   *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
+   *  holds that @p comp(*j,*i) is false.
   */
   template<typename _RandomAccessIter, typename _Compare>
     void