[Boost-commit] svn:boost r48793 - sandbox/committee/concepts/stdlib

Subject: [Boost-commit] svn:boost r48793 - sandbox/committee/concepts/stdlib
From: dgregor_at_[hidden]
Date: 2008-09-16 02:40:06

Author: dgregor
Date: 2008-09-16 02:40:05 EDT (Tue, 16 Sep 2008)
New Revision: 48793
URL: http://svn.boost.org/trac/boost/changeset/48793

Log:
Resolve issues brought up by LWG in iterator concepts and algorithms papers
Text files modified: 
   sandbox/committee/concepts/stdlib/clib-algorithms.tex   |    76 +++++++++++++++++---------------------- 
   sandbox/committee/concepts/stdlib/clib-iterconcepts.tex |    61 ++++++++++++++++---------------         
   2 files changed, 65 insertions(+), 72 deletions(-)

Modified: sandbox/committee/concepts/stdlib/clib-algorithms.tex
==============================================================================
--- sandbox/committee/concepts/stdlib/clib-algorithms.tex	(original)
+++ sandbox/committee/concepts/stdlib/clib-algorithms.tex	2008-09-16 02:40:05 EDT (Tue, 16 Sep 2008)
@@ -78,6 +78,10 @@
   referring to the appropriate iterator concept
   (Clause~\ref{alg.algorithms}). Thanks to Alisdair Meredith for
   pointing out the inconsistency.
+\item Added a placeholder \tcode{UniformRandomNumberGenerator}
+  concept, which is used to constrain the third \tcode{random_shuffle}
+  overload. Made the third \tcode{random_shuffle} accept its random
+  number generator by rvalue reference.
 \end{itemize}
 
 \end{titlepage}
@@ -155,7 +159,7 @@
   template <InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
     requires CopyConstructible<Pred>
     bool any_of(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
-  template <InputIterator Iter, Predicate<auto, _Iter::value_type> Pred>
+  template <InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
     requires CopyConstructible<Pred>
     bool none_of(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
 
@@ -445,10 +449,12 @@
     void random_shuffle(Iter @\farg{first}@,
                         Iter @\farg{last}@,
                         Rand&& @\farg{rand}@);
-  @\removedConcepts{template<class RandomAccessIterator, class UniformRandomNumberGenerator>}@
-    @\removedConcepts{void random_shuffle(RandomAccessIterator \mbox{\farg{first}},}@
-                        @\removedConcepts{RandomAccessIterator \mbox{\farg{last}},}@
-                        @\removedConcepts{UniformRandomNumberGenerator\& \mbox{\farg{rand}});}@
+
+  concept UniformRandomNumberGenerator<typename Rand> { }
+  template<RandomAccessIterator Iter, UniformRandomNumberGenerator Rand>
+    void random_shuffle(Iter @\farg{first}@,
+                        Iter @\farg{last}@,
+                        Rand&& @\farg{g}@);
 
   @\textcolor{black}{// \ref{alg.partitions}, partitions:}@
   template <InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
@@ -1106,7 +1112,7 @@
 \index{none_of@\tcode{none_of}}%
 \color{addclr}
 \begin{itemdecl}
-template <InputIterator Iter, Predicate<auto, _Iter::value_type> Pred>
+template <InputIterator Iter, Predicate<auto, Iter::value_type> Pred>
   requires CopyConstructible<Pred>
   bool none_of(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
 \end{itemdecl}
@@ -2539,55 +2545,39 @@
                       Iter @\farg{last}@,
                       Rand&& @\farg{rand}@);
 
-  @\removedConcepts{template<class RandomAccessIterator, class UniformRandomNumberGenerator>}@
-    @\removedConcepts{void random_shuffle(RandomAccessIterator \mbox{\farg{first}},}@
-                        @\removedConcepts{RandomAccessIterator \mbox{\farg{last}},}@
-                        @\removedConcepts{UniformRandomNumberGenerator\& \mbox{\farg{rand}});}@
+concept UniformRandomNumberGenerator<typename Rand> { }
+
+template<RandomAccessIterator Iter, UniformRandomNumberGenerator Rand>
+  void random_shuffle(Iter @\farg{first}@,
+                      Iter @\farg{last}@,
+                      Rand&& @\farg{g}@);
 \end{itemdecl}\color{black}
 
-\editorial{The third overload of \tcode{random_shuffle} has been
-  removed, since it is ambiguous with the second and we do not have
-  concept constraints for it.}
+\editorial{In the third overload of \tcode{random_shuffle}, we use the
+  placeholder concept \tcode{UniformRandomNumberGenerator}. When
+  concepts are provided for this concept, the placeholder above will
+  be removed and the third \tcode{random_shuffle} will refer to that
+  \tcode{UniformRandomNumberGenerator}. Additionally, we have opted to
+  make the third argument an rvalue reference rather than an lvalue
+  reference, to synchronize it with the second
+  \tcode{random_shuffle}.}
 
 \begin{itemdescr}
 \pnum
 \effects\ 
-Shuffles the elements in the range
+Permutes the elements in the range
 \range{\farg{first}}{\farg{last}}\
-with uniform distribution.
+such that each possible permutation of those elements has equal
+probability of appearance. 
 
 \pnum
 \removedConcepts{Requires: 
 The type of *first shall satisfy the
-Swappable requirements (20.1.4).}
+Swappable requirements (Table 37).} \changedConcepts{The random 
+number generating function object \mbox{\tcode{rand}} shall have a return type that is convertible to \mbox{\tcode{iterator_traits<RandomAccessIterator>::difference_type}}, and the}{The} call \tcode{rand(n)} shall return a randomly 
+chosen value in the interval \tcode{[0,n)}, for \tcode{n > 0}\removedConcepts{ of type \mbox{\tcode{iterator_traits<RandomAccessIterator>::difference_type}}}. \removedConcepts{The function object \mbox{\tcode{g}} shall meet the requirements of uniform random number generator (\mbox{\ref{rand.req.urng}}).}
 
-\pnum
-\complexity\ 
-Exactly
-\tcode{(\farg{last}\ - \farg{first}) - 1}\
-swaps.
-
-\pnum
-\notes\ 
-The underlying source of random numbers for the first form of the function
-is implementation-defined. An implementation may use the
-\tcode{rand}\
-function from the standard C library.
-The second form of the function
-takes a random number generating function object
-\farg{rand}
-such that
-if
-\tcode{n} 
-is an argument for rand, with a positive value, that has
-type
-\changedConcepts{\mbox{\tcode{iterator_traits<RandomAccessIterator>::difference_type}}}{\mbox{\tcode{Iter::difference_type}}},
-then
-\tcode{rand(n)}
-returns a randomly chosen value,
-which lies in the interval \tcode{(0,n]}\removedConcepts{,
-and which has a type that is convertible to
-iterator_traits<RandomAccessIterator>:: difference_type}.
+\editorial{Paragraphs 3 and 4 are unchanged.}
 \end{itemdescr}
 
 \rSec2[alg.partitions]{Partitions}

Modified: sandbox/committee/concepts/stdlib/clib-iterconcepts.tex
==============================================================================
--- sandbox/committee/concepts/stdlib/clib-iterconcepts.tex	(original)
+++ sandbox/committee/concepts/stdlib/clib-iterconcepts.tex	2008-09-16 02:40:05 EDT (Tue, 16 Sep 2008)
@@ -275,6 +275,7 @@
   types that don't have all of the nested types, e.g., the
   instantiation of \tcode{iterator_traits<int>} should produce an
   empty class, not an error.
+\item Made a \tcode{ShuffleIterator} a \tcode{ForwardIterator}, and its value type both \tcode{MoveAssignable} and \tcode{Swappable}. 
 \end{itemize}
 \end{titlepage}
 
@@ -1159,15 +1160,17 @@
 \color{addclr}
 \begin{codeblock}
 auto concept ShuffleIterator<typename X> {
-  requires InputIterator<X>
-        && OutputIterator<X, RvalueOf<InputIterator<X>::value_type>::type>
-        && OutputIterator<X, RvalueOf<InputIterator<X>::reference>::type>
-        && Constructible<InputIterator<X>::value_type, 
-                         RvalueOf<InputIterator<X>::reference>::type>
-        && MoveConstructible<InputIterator<X>::value_type>
-        && HasAssign<InputIterator<X>::value_type, 
-                     RvalueOf<InputIterator<X>::reference>::type>
-        && HasSwap<InputIterator<X>::reference, InputIterator<X>::reference>;
+  requires ForwardIterator<X>
+        && OutputIterator<X, RvalueOf<ForwardIterator<X>::value_type>::type>
+        && OutputIterator<X, RvalueOf<ForwardIterator<X>::reference>::type>
+        && Constructible<ForwardIterator<X>::value_type, 
+                         RvalueOf<ForwardIterator<X>::reference>::type>
+        && MoveConstructible<ForwardIterator<X>::value_type>
+        && MoveAssignable<ForwardIterator<X>::value_type>
+        && Swappable<ForwardIterator<X>::value_type>
+        && HasAssign<ForwardIterator<X>::value_type, 
+                     RvalueOf<ForwardIterator<X>::reference>::type>
+        && HasSwap<ForwardIterator<X>::reference, ForwardIterator<X>::reference>;
 }
 \end{codeblock}
 \color{black}
@@ -1218,14 +1221,14 @@
 Accordingly, it is required that if}
 {Iterator traits provide an auxiliary mechanism for
 accessing the associated types of an iterator. If}
-\tcode{Iterator}\
+\tcode{Iter\removedConcepts{ator}}\
 is the type of an iterator,
 the types
 
 \begin{codeblock}
-iterator_traits<Iterator>::difference_type
-iterator_traits<Iterator>::value_type
-iterator_traits<Iterator>::iterator_category
+iterator_traits<Iter@\removedConcepts{ator}@>::difference_type
+iterator_traits<Iter@\removedConcepts{ator}@>::value_type
+iterator_traits<Iter@\removedConcepts{ator}@>::iterator_category
 \end{codeblock}
 
 \addedConcepts{shall} be defined as the iterator's difference type, value type and iterator
@@ -1233,8 +1236,8 @@
 In addition, the types
 
 \begin{codeblock}
-iterator_traits<Iterator>::reference
-iterator_traits<Iterator>::pointer
+iterator_traits<Iter@\removedConcepts{ator}@>::reference
+iterator_traits<Iter@\removedConcepts{ator}@>::pointer
 \end{codeblock}
 
 shall be defined as the iterator's reference and pointer types, that is, for an
@@ -1242,10 +1245,10 @@
 respectively. In the case of an output iterator, the types
 
 \begin{codeblock}
-iterator_traits<Iterator>::difference_type
-iterator_traits<Iterator>::value_type
-iterator_traits<Iterator>::reference
-iterator_traits<Iterator>::pointer
+iterator_traits<Iter@\removedConcepts{ator}@>::difference_type
+iterator_traits<Iter@\removedConcepts{ator}@>::value_type
+iterator_traits<Iter@\removedConcepts{ator}@>::reference
+iterator_traits<Iter@\removedConcepts{ator}@>::pointer
 \end{codeblock}
 
 may be defined as \tcode{void}.
@@ -1267,15 +1270,15 @@
   \mbox{\tcode{difference_type}}, \mbox{\tcode{value_type}},
   \mbox{\tcode{pointer}}, \mbox{\tcode{reference}}, and
   \mbox{\tcode{iterator_category}}, then the}
-template \tcode{iterator_traits<Iterator>} is defined as 
+template \tcode{iterator_traits<Iter\removedConcepts{ator}>} is defined as 
 \begin{itemdecl}
 namespace std { 
-  template<class Iterator> struct iterator_traits { 
-    typedef typename Iterator::difference_type   difference_type; 
-    typedef typename Iterator::value_type        value_type; 
-    typedef typename Iterator::pointer           pointer; 
-    typedef typename Iterator::reference         reference; 
-    typedef typename Iterator::iterator_category iterator_category; 
+  template<class Iter@\removedConcepts{ator}@> struct iterator_traits { 
+    typedef typename Iter@\removedConcepts{ator}@::difference_type   difference_type; 
+    typedef typename Iter@\removedConcepts{ator}@::value_type        value_type; 
+    typedef typename Iter@\removedConcepts{ator}@::pointer           pointer; 
+    typedef typename Iter@\removedConcepts{ator}@::reference         reference; 
+    typedef typename Iter@\removedConcepts{ator}@::iterator_category iterator_category; 
   }; 
 } 
 \end{itemdecl}
@@ -1283,7 +1286,7 @@
 \color{addclr}
 \begin{itemdecl}
 namespace std { 
-  template<class Iterator> struct iterator_traits { };
+  template<class Iter@\removedConcepts{ator}@> struct iterator_traits { };
 }
 \end{itemdecl}
 \color{black}
@@ -1413,8 +1416,8 @@
 and
 \tcode{random_access_iterator_tag}.
 For every iterator of type
-\tcode{Iterator},
-\tcode{iterator_traits<Iterator>::it\-er\-a\-tor_ca\-te\-go\-ry}
+\tcode{Iter@\removedConcepts{ator}@},
+\tcode{iterator_traits<Iter@\removedConcepts{ator}@>::it\-er\-a\-tor_ca\-te\-go\-ry}
 shall be defined to be the most specific category tag that describes the
 iterator's behavior.