CVS difference for ai05s/ai05-0136-1.txt

Differences between 1.13 and version 1.14
Log of other versions for file ai05s/ai05-0136-1.txt

--- ai05s/ai05-0136-1.txt	2010/05/29 05:28:20	1.13
+++ ai05s/ai05-0136-1.txt	2010/06/03 04:37:06	1.14
@@ -1,4 +1,4 @@
-!standard  A.18.10(0)                                10-05-28    AI05-0136-1/07
+!standard  A.18.10(0)                                10-06-02    AI05-0136-1/07
 !standard  A.18.17(0)
 !standard  A.18.25(0)
 !class Amendment 09-02-04
@@ -65,7 +65,7 @@
 (successor) sibling, and previous (predecessor) sibling internal nodes. A cursor
 designates a particular node within a tree (and by extension the element
 contained in that node, if any). A cursor keeps designating the same node (and element)
-as long as the node is part of the container, even if the node is moved in the
+as long as the node is part of the container, even if the node is moved within the
 container.
 
 A *subtree* is a particular node (which *roots the subtree*) and all of its child
@@ -273,12 +273,12 @@
 
    procedure Iterate_Children
      (Container : in Tree;
-      Parent    : in     Cursor;
+      Parent    : in Cursor;
       Process   : not null access procedure (Position : in Cursor));
 
    procedure Reverse_Iterate_Children
      (Container : in Tree;
-      Parent    : in     Cursor;
+      Parent    : in Cursor;
       Process   : not null access procedure (Position : in Cursor));
 
 private
@@ -288,10 +288,10 @@
 The actual function for the generic formal function "=" on Element_Type values
 is expected to define a reflexive and symmetric relationship and return the same
 result value each time it is called with a particular pair of values. If it
-behaves in some other manner, the functions Find, Reverse_Find, Equal_Subtrees,
+behaves in some other manner, the functions Find, Reverse_Find, Equal_Subtree,
 and "=" on tree values return an unspecified value. The exact arguments and
 number of calls of this generic formal function by the functions Find,
-Reverse_Find, Equal_Subtrees, and "=" on tree values are unspecified.
+Reverse_Find, Equal_Subtree, and "=" on tree values are unspecified.
 
 The type Tree is used to represent trees. The type Tree needs finalization (see
 7.6).
@@ -385,10 +385,10 @@
       correct answer. Similarly, a global rule (see the introduction of Annex A)
       says that language-defined routines are not affected by overriding of
       other language-defined routines. This means that no reasonable program can
-      tell how many times Equal_Subtrees is called, and thus an implementation
+      tell how many times Equal_Subtree is called, and thus an implementation
       can call it as many or as few times as it needs to get the correct answer.
       Specifically, there is no requirement to call the formal equality or
-      Equal_Subtrees additional times once the answer has been determined.
+      Equal_Subtree additional times once the answer has been determined.
 
    function "=" (Left, Right : Tree) return Boolean;
 
@@ -398,7 +398,7 @@
       the evaluation of Equal_Subtree is propagated.
 
       AARM Implementation Note: Similar considerations apply here as apply to
-      Equal_Subtrees. The actual number of calls performed is unspecified.
+      Equal_Subtree. The actual number of calls performed is unspecified.
 
    function Node_Count (Container : Tree) return Count_Type;
 
@@ -634,8 +634,8 @@
    function Has_Element (Position : Cursor) return Boolean;
 
       Returns True if Position designates an element, and returns False
-      otherwise. Redundant[This returns False if the cursor designates the root node
-      or equals No_Element.]
+      otherwise. Redundant[In particular, Has_Element returns False if the cursor designates
+      the root node or equals No_Element.]
 
       AARM To Be Honest: This function might not detect cursors that designate
       deleted elements; such cursors are invalid (see below) and the result of
@@ -814,7 +814,7 @@
       rooted by Source (which can be from any tree; it does not have to be a
       subtree of Target) is copied (new nodes are allocated to create a new subtree
       with the same structure as the Source subtree, with each element initialized
-      from the corresponding element of the Source subtree) and and inserted
+      from the corresponding element of the Source subtree) and inserted
       into Target as a child of Parent. If Parent already has child nodes
       then the new nodes are inserted prior to the node designated by Before,
       or, if Before equals No_Element, the new nodes are inserted after the
@@ -828,7 +828,7 @@
       and between containers.
 
       AARM Ramification: We do not allow copying a subtree that includes a
-      root node, as that would requiring inserting a node with no value
+      root node, as that would require inserting a node with no value
       in the middle of the target tree. To copy an entire tree to another
       tree object, use Copy.
 
@@ -850,7 +850,7 @@
       Constraint_Error is propagated. If Position equals No_Element, Constraint_Error
       is propagated. If Position does not designate a node in Source or designates
       a root node, then Program_Error is propagated. If Source denotes the same
-      object as Target, then there is no effect; if Position designates an ancestor
+      object as Target, then if Position designates an ancestor
       of Parent or is equal to Parent, Constraint_Error is propagated; else
       the subtree rooted by the element designated by Position is moved to be
       a child of Parent. If Parent already has child nodes
@@ -867,7 +867,8 @@
       though such a check is O(Depth(Source)).
       End AARM Reason.
 
-      Otherwise, the subtree designated by Position is removed from Source and
+      Otherwise (if Source does not denote the same object as Target), the subtree
+      designated by Position is removed from Source and
       moved to Target. The subtree is inserted as a child of Parent. If Parent
       already has child nodes then the moved nodes are inserted prior to the node
       designated by Before, or, if Before equals No_Element, the moved nodes are
@@ -881,7 +882,7 @@
       does not have to move to meet the postcondition.
 
       We do not allow splicing a subtree that includes a root node, as that
-      would requiring inserting a node with no value in the middle of the
+      would require inserting a node with no value in the middle of the
       target tree. Splice the children of the root node instead.
 
       For this reason there is no operation to splice an entire tree, as that would
@@ -971,7 +972,7 @@
       If Target_Parent does not designate a node in Container, then Program_Error
       is propagated. If Before is not equal to No_Element, and does not designate
       an element in Container, then Program_Error is propagated. If Source_Parent
-      equals No_Element, Constraint_Error is propagated. If Source_Parent does not
+      equals No_Element, then Constraint_Error is propagated. If Source_Parent does not
       designate a node in Container, then Program_Error is propagated. If Before
       is not equal to No_Element, and Container.Parent (Before) is not equal to
       Target_Parent, then Constraint_Error is propagated. If Target_Parent equals
@@ -1036,7 +1037,7 @@
 
    procedure Iterate_Children
      (Container : in Tree;
-      Parent    : in     Cursor;
+      Parent    : in Cursor;
       Process   : not null access procedure (Position : in Cursor));
 
       If Parent equals No_Element, then Constraint_Error is propagated.
@@ -1045,23 +1046,23 @@
 
       Iterate_Children calls Process.all with a cursor that designates each
       child node of Parent, starting with the first child node and moving the
-      cursor as per the Next_Sibling function.
+      cursor as per the function Next_Sibling.
 
       Program_Error is propagated if Process.all tampers with the cursors of
       Container. Any exception raised by Process.all is propagated.
 
    procedure Reverse_Iterate_Children
      (Container : in Tree;
-      Parent    : in     Cursor;
+      Parent    : in Cursor;
       Process   : not null access procedure (Position : in Cursor));
 
       If Parent equals No_Element, then Constraint_Error is propagated.
       If Parent does not designate a node in Container, then Program_Error is
       propagated.
 
-      Iterate_Children calls Process.all with a cursor that designates each
+      Reverse_Iterate_Children calls Process.all with a cursor that designates each
       child node of Parent, starting with the last child node and moving the
-      cursor as per the Previous_Sibling function.
+      cursor as per the function Previous_Sibling.
 
       Program_Error is propagated if Process.all tampers with the cursors of
       Container. Any exception raised by Process.all is propagated.
@@ -1280,7 +1281,7 @@
 
 Having "_Child" as part of the names also opens up the possibility of operations
 not having the "_Child" suffix. These would naturally operate on the entire
-tree. We're taken advantage of this to define operations like Find and Iterate
+tree. We've taken advantage of this to define operations like Find and Iterate
 over the entire tree.
 
 We've added the suffix "_Subtree" to a few operations to make it clear that they
@@ -1372,11 +1373,11 @@
 But this is somewhat silly, given that the first operation on every tree object would
 have to be to insert the one-and-only root.
 
-The alternative of having a root node that is always present, but has an optional value.
-In this case, inserting any node at the root is always illegal (and can easily be prevented
-by simply not allowing the Parent parameter to ever be No_Element). But then, we would have
-to define the idea of an uninitialized element for just this one node, and we would probably
-want a way to "unset" the value of this node.
+The alternative to allowing the insertion of exactly one root node is to have a root node that
+is always present, but has an optional value. In this case, inserting any node at the root is always
+illegal (and can easily be prevented by simply not allowing the Parent parameter to be No_Element).
+But then, we would have to define the idea of an uninitialized element for just this one node, and
+we would probably want a way to "unset" the value of this node.
 
 Another alternative is to have the root node always present, and have it be default initialized.
 This would not have as much wording complication, but it would have some annoying effects:
@@ -1688,7 +1689,7 @@
 (successor) sibling, and previous (predecessor) sibling internal nodes. A cursor
 designates a particular node within a tree (and by extension the element
 contained in that node, if any). A cursor keeps designating the same node (and element)
-as long as the node is part of the container, even if the node is moved in the
+as long as the node is part of the container, even if the node is moved within the
 container.
 
 A @i<subtree> is a particular node (which @i<roots the subtree>) and all of its child
@@ -1910,10 +1911,10 @@
 The actual function for the generic formal function "=" on Element_Type values
 is expected to define a reflexive and symmetric relationship and return the same
 result value each time it is called with a particular pair of values. If it
-behaves in some other manner, the functions Find, Reverse_Find, Equal_Subtrees,
-and "=" on tree values @b<return> an unspecified value. The exact arguments and
+behaves in some other manner, the functions Find, Reverse_Find, Equal_Subtree,
+and "=" on tree values return an unspecified value. The exact arguments and
 number of calls of this generic formal function by the functions Find,
-Reverse_Find, Equal_Subtrees, and "=" on tree values are unspecified.
+Reverse_Find, Equal_Subtree, and "=" on tree values are unspecified.
 
 The type Tree is used to represent trees. The type Tree needs finalization (see
 7.6).
@@ -1943,8 +1944,8 @@
 a container because they depend on elements of the container not being replaced.
 
 A subprogram is said to @i<tamper with cursors> of a tree object @i<T> if:
-@xbullet<it inserts or deletes elements of T, that is, it calls the Clear,
-Delete_Leaf, Insert_Child, or Delete_Children procedures with T as a parameter;
+@xbullet<it inserts or deletes elements of @i<T>, that is, it calls the Clear,
+Delete_Leaf, Insert_Child, or Delete_Children procedures with @i<T> as a parameter;
 or>
 
 @xbullet<it reorders the elements of @i<T>, that is, it calls the Splice_Subtree
@@ -2162,8 +2163,8 @@
 @xcode<@b<function> Has_Element (Position : Cursor) @b<return> Boolean;>
 
 @xindent<Returns True if Position designates an element, and returns False
-otherwise. This returns False if the cursor designates the root node or equals
-No_Element.>
+otherwise. In particular, Has_Element returns False if the cursor designates
+the root node or equals No_Element.>
 
 @xcode<@b<procedure> Iterate
   (Container : @b<in> Tree;
@@ -2295,7 +2296,7 @@
 Otherwise, the subtree rooted by Source (which can be from any tree; it does not
 have to be a subtree of Target) is copied (new nodes are allocated to create a
 new subtree with the same structure as the Source subtree, with each element
-initialized from the corresponding element of the Source subtree) and and
+initialized from the corresponding element of the Source subtree) and
 inserted into Target as a child of Parent. If Parent already has child nodes
 then the new nodes are inserted prior to the node designated by Before, or, if
 Before equals No_Element, the new nodes are inserted after the last existing
@@ -2318,7 +2319,7 @@
 propagated. If Position equals No_Element, Constraint_Error is propagated. If
 Position does not designate a node in Source or designates a root node, then
 Program_Error is propagated. If Source denotes the same object as Target, then
-there is no effect; if Position designates an ancestor of Parent or is equal to
+if Position designates an ancestor of Parent or is equal to
 Parent, Constraint_Error is propagated; else the subtree rooted by the element
 designated by Position is moved to be a child of Parent. If Parent already has
 child nodes then the moved nodes are inserted prior to the node designated by
@@ -2327,7 +2328,8 @@
 count of Target are unchanged, and the parent of the element designated by
 Position is set to Parent.>
 
-@xindent<Otherwise, the subtree designated by Position is removed from Source
+@xindent<Otherwise (if Source does not denote the same object as Target), the
+subtree designated by Position is removed from Source
 and moved to Target. The subtree is inserted as a child of Parent. If Parent
 already has child nodes then the moved nodes are inserted prior to the node
 designated by Before, or, if Before equals No_Element, the moved nodes are
@@ -2402,7 +2404,7 @@
 propagated. If Target_Parent does not designate a node in Container, then
 Program_Error is propagated. If Before is not equal to No_Element, and does not
 designate an element in Container, then Program_Error is propagated. If
-Source_Parent equals No_Element, Constraint_Error is propagated. If
+Source_Parent equals No_Element, then Constraint_Error is propagated. If
 Source_Parent does not designate a node in Container, then Program_Error is
 propagated. If Before is not equal to No_Element, and Container.Parent (Before)
 is not equal to Target_Parent, then Constraint_Error is propagated. If
@@ -2465,7 +2467,7 @@
 
 @xcode<@b<procedure> Iterate_Children
   (Container : @b<in> Tree;
-   Parent    : @b<in>     Cursor;
+   Parent    : @b<in> Cursor;
    Process   : @b<not null access rocedure> (Position : @b<in> Cursor));>
 
 @xindent<If Parent equals No_Element, then Constraint_Error is propagated. If
@@ -2480,13 +2482,13 @@
 
 @xcode<@b<procedure> Reverse_Iterate_Children
   (Container : @b<in> Tree;
-   Parent    : @b<in>     Cursor;
+   Parent    : @b<in> Cursor;
    Process   : @b<not null access procedure> (Position : @b<in> Cursor));>
 
 @xindent<If Parent equals No_Element, then Constraint_Error is propagated. If
 Parent does not designate a node in Container, then Program_Error is propagated.>
 
-@xindent<Iterate_Children calls Process.@b<all> with a cursor that designates each
+@xindent<Reverse_Iterate_Children calls Process.@b<all> with a cursor that designates each
 child node of Parent, starting with the last child node and moving the cursor as
 per the Previous_Sibling function.>
 
@@ -2534,9 +2536,9 @@
 @s8<@i<Implementation Advice>>
 
 Containers.Multiway_Trees should be implemented similarly to a multiway tree. In
-particular, if N is the overall number of nodes for a particular tree, then the
+particular, if @i<N> is the overall number of nodes for a particular tree, then the
 worst-case time complexity of Element, Parent, First_Child, Last_Child,
-Insert_Child with Count=1, and Delete should be O(log N).
+Insert_Child with Count=1, and Delete should be @i<O>(log @i<N>).
 
 Move should not copy elements, and should minimize copying of internal data structures.
 
@@ -2625,7 +2627,7 @@
 
 It is a bounded error to use a bounded tree if it was the target of an
 assignment_statement whose source was in the middle of an operation
-that disallows tampering with cursors [Redundant: or elements].
+that disallows tampering with cursors or elements.
 Either Program_Error is raised, or the operation proceeds as defined.
 
 @s8<@i<Implementation Advice>>

Questions? Ask the ACAA Technical Agent