CVS difference for ai05s/ai05-0044-1.txt
--- ai05s/ai05-0044-1.txt 2007/07/26 02:58:06 1.2
+++ ai05s/ai05-0044-1.txt 2007/12/13 04:39:36 1.3
@@ -1,12 +1,13 @@
-!standard A.18(4/2) 07-07-17 AI05-0044-1/02
+!standard A.18(4/2) 07-11-29 AI05-0044-1/03
!standard A.18.2(231/2)
!standard A.18.3(145/2)
-!standard A.18.6(57/2)
-!standard A.18.8(65/2)
+!standard A.18.6(56/2)
+!standard A.18.8(66/2)
!standard A.18.9(79/2)
!standard A.18.16(5/2)
!standard A.18.16(9/2)
!class binding interpretation 07-04-02
+!status ARG Approved 7-0-2 06-11-10
!status work item 07-04-02
!status received 07-01-24
!priority Medium
@@ -18,8 +19,6 @@
The notion of "strict weak ordering" is defined. All "<" formal subprograms are
required to have a strict weak ordering.
-"Sorted smallest first" also is defined.
-
"=" formal functions for the Set containers are required to return False for non-equivalent
elements.
@@ -48,7 +47,7 @@
A related issue is that the requirements on "=" for sets are not related to equivalence. That
means that "=" on a set must take O(N**2), as checking only equivalent elements would be making
-an unwarrented assumption.
+an unwarranted assumption.
!recommendation
@@ -56,40 +55,37 @@
!wording
-Define "strict weak ordering" and "smallest first" after A.18(4/2):
+Define "strict weak ordering" after A.18(4/2):
-A *strict weaking ordering* for an operator "<" is one that is be irreflexive,
-asymmetric, and transitive. In addition, if x < y is True for any values x and y,
-then for all other values z, (x < z) or (z < y) is True.
-
-A container is sorted *smallest first* based on an operator "<" if, for any
-two elements of a container, Elem1 < Elem2 implies that the position of Elem1
-in the container is closer to the the first element than the position of Elem2.
+When a formal operator "<" is used to provide an ordering for a container,
+it is generally required to define a strict weak ordering. An operator "<"
+defines a *strict weak ordering* if it is irreflexive,
+asymmetric, transitive, and in addition, if x < y for any values x and y,
+then for all other values z, (x < z) or (z < y).
Replace the second sentence of A.18.2(231/2) by
It should define a strict weak ordering relationship (see A.18); it should not modify
Container.
-Make similar changes to A.18.3(145/2), A.18.6(57/2), A.18.9(79/2), A.18.16(5/2),
+Make similar changes to A.18.3(145/2), A.18.6(56/2), A.18.9(79/2), A.18.16(5/2),
and A.18.16(9/2).
-Add "If the actual for the generic formal function "=" returns True for any pair
+Add "If the actual function for the generic formal function "=" returns True for any pair
of non-equivalent elements, then the behavior of the container function "=" is unspecified."
-to A.18.8(65.2) and A.18.9(79/2).
-
+as a separate paragraph after A.18.8(66/2) and A.18.9(79/2).
!discussion
-A "<" actual function is required to be irreflexive, asymetric, and transitive. The
-formal definitions of these terms are:
+The existing wording requires a "<" actual function to be irreflexive, asymetric,
+and transitive. The formal definitions of these terms are:
- irreflexive: X < X is False for all X.
- asymmetric: if X < Y is True, then Y < X is False.
- transitive: if X < Y is True and Y < Z is True then X < Z is True.
Note that the latter two say nothing about the case where X < Y is False. Thus
it is OK to have both X < Y = False and Y < X = False and still be asymeteric. Indeed, this
-is the definition of equivalence, so it is clearly fine. What is not OK if for there to be
-a value which has is equivalent to two other values which are not equivalent (that is,
+is the definition of equivalence, so it is clearly fine. What is not OK is for there to be
+a value which is equivalent to two other values which are not equivalent (that is,
that have "<" returning True).
That is, we also need transitively of equivalence, or more precisely.
@@ -97,12 +93,156 @@
if x < y is True, then for all z, (x < z) or (z < y) is True.
---!corrigendum 10.1.2(20/2)
+!corrigendum A.18(4/2)
+@dinsa
+If the advice suggests that the complexity should be less than @i<O>(f(N)),
+then for any arbitrarily small positive real D, there should exist a positive
+integer M such that for all N > M, t(N)/f(N) < D.
+@dinst
+When a formal operator "<" is used to provide an ordering for a container,
+it is generally required to define a strict weak ordering. An operator "<"
+defines a @i<strict weak ordering> if it is irreflexive,
+asymmetric, transitive, and in addition, if @i<x> < @i<y> for
+any values @i<x> and @i<y>, then for all other values @i<z>,
+(@i<x> < @i<z>) or (@i<z> < @i<y>).
+
+!corrigendum A.18.2(231/2)
+
+@drepl
+The actual function for the generic formal function "<" of Generic_Sorting is
+expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict ordering relationship, that is, be
+irreflexive, asymmetric, and transitive; it should not modify Container. If the
+actual for "<" behaves in some other manner, the behavior of the subprograms of
+Generic_Sorting are unspecified. How many times the subprograms of Generic_Sorting
+call "<" is unspecified.
+@dby
+The actual function for the generic formal function "<" of Generic_Sorting is
+expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict weak ordering relationship (see A.18);
+it should not modify Container. If the
+actual for "<" behaves in some other manner, the behavior of the subprograms of
+Generic_Sorting are unspecified. How many times the subprograms of Generic_Sorting
+call "<" is unspecified.
+
+!corrigendum A.18.3(145/2)
+
+@drepl
+The actual function for the generic formal function "<" of Generic_Sorting is
+expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict ordering relationship, that is,
+be irreflexive, asymmetric, and transitive; it should not modify Container. If
+the actual for "<" behaves in some other manner, the behavior of the subprograms
+of Generic_Sorting are unspecified. How many times the subprograms of Generic_Sorting
+call "<" is unspecified.
+@dby
+The actual function for the generic formal function "<" of Generic_Sorting is
+expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict weak ordering relationship (see A.18);
+it should not modify Container. If
+the actual for "<" behaves in some other manner, the behavior of the subprograms
+of Generic_Sorting are unspecified. How many times the subprograms of Generic_Sorting
+call "<" is unspecified.
+
+!corrigendum A.18.6(56/2)
+
+@drepl
+The actual function for the generic formal function "<" on Key_Type values is
+expected to return the same value each time it is called with a particular pair
+of key values. It should define a strict ordering relationship, that is, be
+irreflexive, asymmetric, and transitive. If the actual for "<" behaves in
+some other manner, the behavior of this package is unspecified. Which
+subprograms of this package call "<" and how many times they call it, is unspecified.
+@dby
+The actual function for the generic formal function "<" on Key_Type values is
+expected to return the same value each time it is called with a particular pair
+of key values. It should define a strict weak ordering relationship (see A.18).
+If the actual for "<" behaves in
+some other manner, the behavior of this package is unspecified. Which
+subprograms of this package call "<" and how many times they call it, is unspecified.
+
+
+!corrigendum A.18.8(66/2)
+
+@dinsa
+The actual function for the generic formal function Equivalent_Elements is
+expected to return the same value each time it is called with a particular
+pair of Element values. It should define an equivalence relationship, that
+is, be reflexive, symmetric, and transitive. If the actual for
+Equivalent_Elements behaves in some other manner, the behavior of this package
+is unspecified. Which subprograms of this package call Equivalent_Elements, and
+how many times they call it, is unspecified.
+@dinst
+If the actual function for the generic formal function "=" returns True for any pair
+of non-equivalent elements, then the behavior of the container function "="
+is unspecified.
+
+!corrigendum A.18.9(79/2)
+
+@drepl
+The actual function for the generic formal function "<" on Element_Type values
+is expected to return the same value each time it is called with a particular
+pair of key values. It should define a strict ordering relationship, that is,
+be irreflexive, asymmetric, and transitive. If the actual for "<" behaves in
+some other manner, the behavior of this package is unspecified. Which
+subprograms of this package call "<" and how many times they call it, is
+unspecified.
+@dby
+The actual function for the generic formal function "<" on Element_Type values
+is expected to return the same value each time it is called with a particular
+pair of key values. It should define a strict weak ordering relationship (see A.18).
+If the actual for "<" behaves in
+some other manner, the behavior of this package is unspecified. Which
+subprograms of this package call "<" and how many times they call it, is
+unspecified.
+
+If the actual function for the generic formal function "=" returns True for any pair
+of non-equivalent elements, then the behavior of the container function "="
+is unspecified.
+
+!corrigendum A.18.16(5/2)
+
+@drepl
+The actual function for the generic formal function "<" of Generic_Array_Sort is
+expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict ordering relationship, that is,
+be irreflexive, asymmetric, and transitive; it should not modify Container.
+If the actual for "<" behaves in some other manner, the behavior of the instance
+of Generic_Array_Sort is unspecified. How many times Generic_Array_Sort calls
+"<" is unspecified.
+@dby
+The actual function for the generic formal function "<" of Generic_Array_Sort is
+expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict weak ordering relationship (see A.18);
+it should not modify Container.
+If the actual for "<" behaves in some other manner, the behavior of the instance
+of Generic_Array_Sort is unspecified. How many times Generic_Array_Sort calls
+"<" is unspecified.
+
+!corrigendum A.18.16(9/2)
+
+@drepl
+The actual function for the generic formal function "<" of Generic_Constrained_Array_Sort
+is expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict ordering relationship, that is,
+be irreflexive, asymmetric, and transitive; it should not modify Container.
+If the actual for "<" behaves in some other manner, the behavior of the instance
+of Generic_Constrained_Array_Sort is unspecified. How many times
+Generic_Constrained_Array_Sort calls "<" is unspecified.
+@dby
+The actual function for the generic formal function "<" of Generic_Constrained_Array_Sort
+is expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict weak ordering relationship (see A.18);
+it should not modify Container.
+If the actual for "<" behaves in some other manner, the behavior of the instance
+of Generic_Constrained_Array_Sort is unspecified. How many times
+Generic_Constrained_Array_Sort calls "<" is unspecified.
!ACATS test
-
+This just defines more generic actuals to provide unspecified behavior, and unspecified
+behavior is not testable.
!appendix
Questions? Ask the ACAA Technical Agent