--- 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