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

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

--- ai05s/ai05-0136-1.txt	2010/01/09 01:31:29	1.9
+++ ai05s/ai05-0136-1.txt	2010/01/16 05:11:07	1.10
@@ -1,5 +1,6 @@
-!standard  A.18.18(1)                                09-07-08    AI05-0136-1/05
+!standard  A.18.18(1)                                10-01-15    AI05-0136-1/06
 !class Amendment 09-02-04
+!status ARG Approved 9-0-3  09-11-07
 !status work item 09-02-04
 !status received 09-01-27
 !priority Medium
@@ -60,7 +61,7 @@
 contains an element and pointers to the parent, first child, last child, next
 (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). A cursor keeps designating the same node (and 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
 container.
 
@@ -119,9 +120,9 @@
 
    function Is_Empty (Container : Tree) return Boolean;
 
-   function Count (Container : Tree) return Count_Type;
+   function Node_Count (Container : Tree) return Count_Type;
 
-   function Subtree_Count (Position : Cursor) return Count_Type;
+   function Subtree_Node_Count (Position : Cursor) return Count_Type;
 
    function Depth (Position : Cursor) return Count_Type;
 
@@ -156,8 +157,8 @@
    procedure Move (Target : in out Tree;
                    Source : in out Tree);
 
-   procedure Delete (Container : in out Tree;
-                     Position  : in out Cursor);
+   procedure Delete_Leaf (Container : in out Tree;
+                          Position  : in out Cursor);
 
    procedure Delete_Subtree (Container : in out Tree;
                              Position  : in out Cursor);
@@ -166,10 +167,14 @@
                    I, J      : in     Cursor);
 
    function Find (Container : Tree;
-                  Item      : Element_Type;
-                  Position  : Cursor := No_Element)
+                  Item      : Element_Type)
       return Cursor;
 
+   function Find_In_Subtree (Container : Tree;
+                             Item      : Element_Type;
+                             Position  : Cursor)
+      return Cursor;
+
    function Ancestor_Find (Container : Tree;
                            Item      : Element_Type;
                            Position  : Cursor)
@@ -217,10 +222,8 @@
                            New_Item  : in     Element_Type;
                            Count     : in     Count_Type := 1);
 
-   procedure Delete_Child_Subtrees (Container : in out Tree;
-                                    Parent    : in     Cursor;
-                                    Position  : in out Cursor;
-                                    Count     : in     Count_Type := 1);
+   procedure Delete_Children (Container : in out Tree;
+                              Parent    : in     Cursor);
 
    procedure Copy_Subtree (Target   : in out Tree;
                            Parent   : in     Cursor;
@@ -317,8 +320,8 @@
 a container because they depend on elements of the container not being replaced.
 
 A subprogram is said to tamper with cursors of a tree object T if:
-* it inserts or deletes elements of T, that is, it calls the Clear, Delete,
-  Insert_Child, or Delete_Child procedures with T as a parameter; or
+* 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; or
 
 AARM To be honest: Operations which are defined to be equivalent to a call on
 one of these operations also are included. Similarly, operations which call one
@@ -351,16 +354,16 @@
    function Equal_Subtree (Left_Position : Cursor;
                            Right_Position: Cursor) return Boolean;
 
-      If Left_Position or Right_Position equals No_Element, propogates
+      If Left_Position or Right_Position equals No_Element, propagates
       Constraint_Error. If the number of child nodes of the element designated
       by Left_Position is different than the number of child nodes of the
       element designated by Right_Position, the function returns False. If
       Left_Position designates a root node and Right_Position does not,
       the function returns False. If Right_Position designates a
       root node and Left_Position does not, the function returns False.
-      If comparing the element designated by Left_Position with the element
-      designated by Right_Position using the generic formal equality operator
-      returns False, the function returns False. Otherwise, it calls
+      Unless both cursors designate a root node, the elements are compared
+      using the generic formal equality operator. If the result is False, the
+      function returns False. Otherwise, it calls
       Equal_Subtree on a cursor designating each child element of the element
       designated by Left_Position and a cursor designated the corresponding
       child element of the element deisgnated by Right_Position. If any such
@@ -396,24 +399,20 @@
       AARM Implementation Note: Similar considerations apply here as apply to
       Equal_Subtrees. The actual number of calls performed is unspecified.
 
-   function Count (Container : Tree) return Count_Type;
+   function Node_Count (Container : Tree) return Count_Type;
 
-      Count returns the number of nodes in Container.
+      Node_Count returns the number of nodes in Container.
 
       AARM Ramification: Since all tree objects have a root node, this can never
-      return a value of 0. Count (Some_Tree) should always equal
-      Subtree_Count (Root (Some_Tree)).
+      return a value of 0. Node_Count (Some_Tree) should always equal
+      Subtree_Node_Count (Root (Some_Tree)).
 
-      [Editor's Note: The Count of an empty tree being 1 is a bit weird. Should
-      we skip the root node here and return a count of 0 instead? Note that would
-      be inconsistent with Subtree_Count (and it would be very strange to skip the
-      root node there).]
+   function Subtree_Node_Count (Position : Cursor) return Count_Type;
 
-   function Subtree_Count (Position : Cursor) return Count_Type;
+      If Position is No_Element, Subtree_Count returns 0; otherwise,
+      Subtree_Node_Count returns the number of nodes in the subtree that is rooted
+      by Position.
 
-      If Position is No_Element, Subtree_Count returns 0; otherwise, Subtree_Count
-      returns the number of nodes in the subtree that is rooted by Position.
-
    function Is_Empty (Container : Tree) return Boolean;
 
       Equivalent to Count (Container) = 1.
@@ -464,8 +463,9 @@
 
    function Element (Position : Cursor) return Element_Type;
 
-      If Position equals No_Element or designates the root node, then Constraint_Error
-      is propagated. Otherwise, Element returns the element designated by Position.
+      If Position equals No_Element, then Constraint_Error is propagated; if
+      Position designates the root node of a tree, then Program_Error is propagated.
+      Otherwise, Element returns the element designated by Position.
 
       AARM Ramification: The root node does not contain an element, so that value cannot
       be read or written.
@@ -474,17 +474,18 @@
                               Position  : in     Cursor;
                               New_Item  : in     Element_Type);
 
-      If Position equals No_Element or designates the root node, then Constraint_Error
-      is propagated; if Position does not designate an element in Container, then
-      Program_Error is propagated. Otherwise Replace_Element assigns the value New_Item
+      If Position equals No_Element, then Constraint_Error is propagated; if Position
+      does not designate an element in Container (including if it designates the root
+      node), then Program_Error is propagated. Otherwise Replace_Element assigns the value New_Item
       to the element designated by Position.
 
    procedure Query_Element
      (Position : in Cursor;
       Process  : not null access procedure (Element : in Element_Type));
 
-      If Position equals No_Element or designates the root node, then Constraint_Error
-      is propagated. Otherwise, Query_Element calls Process.all with the element
+      If Position equals No_Element, then Constraint_Error is propagated; if
+      Position designates the root node of a tree, then Program_Error is propagated.
+      Otherwise, Query_Element calls Process.all with the element
       designated by Position as the argument. Program_Error is propagated if Process.all
       tampers with the elements of Container. Any exception raised by
       Process.all is propagated.
@@ -495,9 +496,9 @@
       Process   : not null access procedure
                       (Element : in out Element_Type));
 
-      If Position equals No_Element or designates the root node, then Constraint_Error
-      is propagated; if Position does not designate an element in Container, then
-      Program_Error is propagated. Otherwise Update_Element calls Process.all with
+      If Position equals No_Element, then Constraint_Error is propagated; if Position
+      does not designate an element in Container (including if it designates the root
+      node), then Program_Error is propagated. Otherwise Update_Element calls Process.all with
       the element designated by Position as the argument. Program_Error is propagated
       if Process.all tampers with the elements of Container. Any exception raised
       by Process.all is propagated.
@@ -530,13 +531,13 @@
       completes, Count(Target) is the number of nodes originally in Source, and
       Count(Source) is 1.
 
-   procedure Delete (Container : in out Tree;
-                     Position  : in out Cursor);
+   procedure Delete_Leaf (Container : in out Tree;
+                          Position  : in out Cursor);
 
-      If Position equals No_Element or designates the root node, then Constraint_Error
-      is propagated. If Position does not designate an element in Container, then
-      Program_Error is propagated. If the element designated by position has any
-      child elements, then Constraint_Error is propagated. Otherwise Delete removes
+      If Position equals No_Element, then Constraint_Error is propagated; if Position
+      does not designate an element in Container (including if it designates the root
+      node), then Program_Error is propagated. If the element designated by position has any
+      child elements, then Constraint_Error is propagated. Otherwise Delete_Leaf removes
       (from Container) the element designated by Position. Finally, Position is set to
       No_Element.
 
@@ -553,34 +554,22 @@
    procedure Delete_Subtree (Container : in out Tree;
                              Position  : in out Cursor);
 
-      If Position equals No_Element or designates the root node, then Constraint_Error
-      is propagated. If Position does not designate an element in Container, then
-      Program_Error is propagated. Otherwise Delete removes (from Container) the subtree
-      designated by Position (that is, the node designated by Position and all of the
-      descendant nodes of that node), and Position is set to No_Element.
+      If Position equals No_Element, then Constraint_Error is propagated. If Position
+      does not designate an element in Container (including if it designates the root
+      node), then Program_Error is propagated. Otherwise Delete removes (from Container)
+      the subtree designated by Position (that is, the node designated by Position and
+      all of the descendant nodes of that node), and Position is set to No_Element.
 
       AARM Ramification: The root node cannot be deleted. To delete the entire contents
       of the tree, call Clear(Container).
 
-      [Editor's note: We could allow Delete_Subtree on the root node instead,
-      leaving the root node behind. But that's pretty weird. I worded that originally
-      as:
-
-        If Position designates the root node of the tree, Delete removes
-        (from Container) the subtrees represented each child node of the root node
-        (the child node along with all of the descendant nodes of that node), and
-        Position is not changed. Otherwise Delete removes (from Container) the subtree
-        designated by Position, and Position is set to No_Element.
-
-      but abandoned it as not really meeting the postcondition.]
-
    procedure Swap (Container : in out Tree;
                    I, J      : in     Cursor);
 
-      If either I or J equals No_Element or designates the root node, then
-      Constraint_Error is propagated. If either I or J do not designate an element in
-      Container, then Program_Error is propagated. Otherwise, Swap exchanges the values
-      of the elements designated by I and J.
+      If either I or J equals No_Element, then Constraint_Error is propagated. If
+      either I or J do not designate an element in Container (including if either
+      designates the root node), then Program_Error is propagated. Otherwise, Swap
+      exchanges the values of the elements designated by I and J.
 
       AARM Ramification: After a call to Swap, I designates the element value
       previously designated by J, and J designates the element value previously
@@ -595,31 +584,37 @@
       the elements if needed.
 
    function Find (Container : Tree;
-                  Item      : Element_Type;
-                  Position  : Cursor := No_Element)
+                  Item      : Element_Type)
       return Cursor;
 
-      If Position is not No_Element, and does not designate a node in Container,
-      then Program_Error is propagated. Find searches a subtree of
-      the elements of Container for an element equal to Item (using the generic
-      formal equality operator). The search starts at the element designated by
-      Position, or at the root node if Position equals No_Element. The search
-      checks the subtree rooted by Position (or the root node) in a depth-first
-      order. If no equal element is found, then Find returns No_Element. Otherwise,
-      it returns a cursor designating the first equal element encountered.
+      Find searches the elements of Container for an element equal to Item (using
+      the generic formal equality operator). The search starts at the root node. The
+      The search checks the tree in a depth-first order. If no equal element is
+      found, then Find returns No_Element. Otherwise, it returns a cursor designating
+      the first equal element encountered.
+      
+   function Find_In_Subtree (Container : Tree;
+                             Item      : Element_Type;
+                             Position  : Cursor)
+      return Cursor;
 
-      AARM Ramification: Find does not check any siblings of the element
+      If Position equals No_Element, then Constraint_Error is propagated; if Position
+      does not designate a node in Container, then Program_Error is propagated. 
+      Find_In_Subtree searches a subtree of the elements of Container for an element
+      equal to Item (using the generic formal equality operator). The search starts
+      at the element designated by Position. The search checks the subtree rooted by
+      Position in a depth-first order. If no equal element is found, then Find
+      returns No_Element. Otherwise, it returns a cursor designating the first
+      equal element encountered.
+
+      AARM Ramification: Find_In_Subtree does not check any siblings of the element
       designated by Position. The root node does not contain an element, and
       therefore it can never be returned, but it can be explicitly passed to
       Position.
 
-      [Editor's note: This would naturally be called "Find_Subtree", but that is
-      a misleading name, as what this does is Find *in* a subtree (not finding a
-      subtree). So we stick with plain "Find".
-
-      The subtle difference in wording for belonging to the correct container
-      is needed as a cursor designating the root node is allowed here, and it does
-      not "designate an element" (anywhere), but it does "designate a node" in
+      [Editor's note: The subtle difference in wording for belonging to the correct
+      container is needed as a cursor designating the root node is allowed here, and
+      it does not "designate an element" (anywhere), but it does "designate a node" in
       Container.]
 
    function Ancestor_Find (Container : Tree;
@@ -627,12 +622,12 @@
                            Position  : Cursor)
       return Cursor;
 
-      If Position is No_Element, then Constraint_Error is propagated. If
-      Position does not designate a node in Container, then Program_Error is
-      propagated. Otherwise, Ancestor_Find searches for an element equal to Item
-      (using the generic formal equality operator). The search starts at the
-      element designated by Position, and checks each ancestor proceeding toward
-      the root of the subtree. If no equal element is found, then Ancestor_Find
+      If Position equals No_Element, then Constraint_Error is propagated; if Position
+      does not designate an element in Container (including if it designates the root
+      node), then Program_Error is propagated. Otherwise, Ancestor_Find searches for
+      an element equal to Item (using the generic formal equality operator). The search
+      starts at the element designated by Position, and checks each ancestor proceeding
+      toward the root of the subtree. If no equal element is found, then Ancestor_Find
       returns No_Element. Otherwise, it returns a cursor designating the first
       equal element encountered.
 
@@ -644,9 +639,10 @@
    function Has_Element (Position : Cursor) return Boolean;
 
       Returns True if Position designates an element, and returns False
-      otherwise.
+      otherwise. Redundant[This returns False if the cursor designates the root node
+      or equals No_Element.]
 
-      AARM To be honest: This function may not detect cursors that designate
+      AARM To Be Honest: This function might not detect cursors that designate
       deleted elements; such cursors are invalid (see below) and the result of
       Has_Element for an invalid cursor is unspecified (but not erroneous).
 
@@ -771,46 +767,21 @@
       Equivalent to Insert_Child (Container, Parent, Last_Child (Container,
       Parent), New_Item, Count).
 
-   procedure Delete_Child_Subtrees (Container : in out Tree;
-                                    Parent    : in     Cursor;
-                                    Position  : in out Cursor;
-                                    Count     : in     Count_Type := 1);
+   procedure Delete_Children (Container : in out Tree;
+                              Parent    : 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.
-      If Position designates the root node, then Constraint_Error is propagated.
-      If Position does not designate an element in Container, then Program_Error
-      is propagated. If Position is not equal to No_Element, and
-      Container.Parent (Position) is not equal to Parent, then Constraint_Error
-      is propagated. If Position is equal to No_Element, Delete removes (from
-      Container) the first Count child elements of Parent and their dependent
-      elements (or all of the child elements of Parent if there are fewer than
-      Count child elements of Parent). Otherwise Delete removes (from
-      Container) Count elements and their dependent elements starting at the
-      element designated by Position (or all of the elements starting at
-      Position if there are fewer than Count elements starting at Position).
-      Finally, Position is set to No_Element.
-
-      [Editor's note: The primary differences of this routine from Delete_Subtree
-      is providing of a Count and a Parent. The provision of a Parent allows
-      Position to to be No_Element to represent the first child of the Parent.
-      The provision of a Count allows the deletion of all of the children of
-      a node without having to write a loop with repeated tests.
-      Container.Delete_Child_Subtree (My_Parent, Position => No_Element, Count =>
-      10000); will delete all of the child nodes. But note that the Position
-      needs to be a variable (No_Element won't work directly). I did consider
-      dropping the Position parameter completely, giving Delete_First_Child_Subtrees.
-      But that seemed so speciallized that it would rarely be used.
-
-      I also considered making Position parameter an "in" parameter with a default
-      of No_Element. That would be more usable, but would be inconsistent with
-      all of the other container deletion routines (which kill off the cursor for
-      the deleted node, if possible).
-
-      We don't provide a Delete_Child that only deletes leaf nodes (as we do for
-      the entire container), as that would require pretesting the nodes to
-      verify that they are leaves before doing any deletions, eliminating any
-      performance advantage.]
+      does not designate a node in Container, Program_Error is propagated.
+      Otherwise, Delete_Children removes (from Container) all of the child elements
+      of Parent along with their dependent elements.
+
+      AARM Discussion: This routine deletes all of the child subtrees of Parent
+      at once. Use Delete_Subtree to delete an individual subtree.
+
+      [Editor's note:  We don't provide a Delete_Leaf_Children (which would only
+      delete leaf nodes), even though we do provide such a routine for the entire tree,
+      as it would require pretesting the nodes to verify that they are leaves before
+      doing any deletions, eliminating any performance advantage.]
 
    procedure Copy_Subtree (Target   : in out Tree;
                            Parent   : in     Cursor;
@@ -858,9 +829,9 @@
       If Before is not equal to No_Element, and does not designate a node in
       Target, then Program_Error is propagated. If Before is not equal to
       No_Element, and Target.Parent (Before) is not equal to Parent, then
-      Constraint_Error is propagated. If Position equals No_Element or designates
-      a root node, Constraint_Error is propagated. If Position does not designate
-      a node in Source, then Program_Error is propagated. If Source denotes the same
+      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
       of Parent or is equal to Parent, Constraint_Error is propagated; else
       the subtree rooted by the element designated by Position is moved
@@ -871,7 +842,10 @@
 
       AARM Reason: We can't allow moving the subtree of Position to a
       descendant node of the subtree, as the descendant node will be part of the
-      subtree being moved. Thus we have to check Position against Parent.
+      subtree being moved. The result would be a circularly linked tree, or one
+      with inaccessible nodes. Thus we have to check Position against Parent, even
+      though such a check is O(Depth(Source)).
+      End AARM Reason.
 
       Otherwise, the subtree designated by Position is removed from Source and
       moved to Target. The subtree is inserted as a child of Parent prior to the
@@ -891,7 +865,7 @@
 
       For this reason there is no operation to splice an entire tree, as that would
       necessarily involve splicing a root node.
-      End Ramification.
+      End AARM Ramification.
 
    procedure Splice_Subtree (Container: in out Tree;
                              Parent   : in     Cursor;
@@ -985,10 +959,9 @@
 
    function Parent (Position : Cursor) return Cursor;
 
-      If Position is equal to No_Element, then Constraint_Error is propagated.
-      If Position designates a root node, No_Element is returned. Otherwise,
-      a cursor designating the parent node of the node designated by Position
-      is returned.
+      If Position is equal to No_Element or designates a root node, No_Element
+      is returned. Otherwise, a cursor designating the parent node of the node
+      designated by Position is returned.
 
    function First_Child (Parent : Cursor) return Cursor;
 
@@ -1014,17 +987,17 @@
 
    function Next_Sibling (Position : Cursor) return Cursor;
 
-      If Position equals No_Element or designates the last child element of its
+      If Position equals No_Element or designates the last child node of its
       parent, then Next_Sibling returns the value No_Element. Otherwise, it
       returns a cursor that designates the successor (with the same parent) of
-      the element designated by Position.
+      the node designated by Position.
 
    function Previous_Sibling (Position : Cursor) return Cursor;
 
-      If Position equals No_Element or designates the last child element of its
-      parent, then Next_Sibling returns the value No_Element. Otherwise, it
+      If Position equals No_Element or designates the first child node of its
+      parent, then Previous_Sibling returns the value No_Element. Otherwise, it
       returns a cursor that designates the predecessor (with the same parent) of
-      the element designated by Position.
+      the node designated by Position.
 
    procedure Next_Sibling (Position : in out Cursor);
 
@@ -1093,15 +1066,15 @@
 AARM Discussion: We talk about which tree the element was removed from in order to handle
 splicing nodes from one tree to another. The node still exists, but any cursors that designate
 it in the original tree are now invalid. This bullet covers removals caused by calls to Clear,
-Delete, Delete_Subtree, Delete_Child_Subtree, Splice_Children, and Splice_Subtree.
+Delete_Leaf, Delete_Subtree, Delete_Children, Splice_Children, and Splice_Subtree.
 
 The result of "=" or Has_Element is unspecified if it is called with an invalid
 cursor parameter. Execution is erroneous if any other subprogram declared in
 Containers.Multiway_Trees is called with an invalid cursor parameter.
 
 AARM Discussion: The list above is intended to be exhaustive. In other cases, a
-cursor value continues to designate its original element. For instance, cursor
-values survive the insertion and deletion of other nodes.
+cursor value continues to designate its original element (or the root node). For
+instance, cursor values survive the insertion and deletion of other nodes.
 
 While it is possible to check for these cases, in many cases the overhead
 necessary to make the check is substantial in time or space. Implementations are

Questions? Ask the ACAA Technical Agent