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

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

--- ai05s/ai05-0136-1.txt	2010/05/20 06:38:00	1.12
+++ ai05s/ai05-0136-1.txt	2010/05/29 05:28:20	1.13
@@ -1,4 +1,6 @@
-!standard  A.18.18(1)                                10-01-15    AI05-0136-1/06
+!standard  A.18.10(0)                                10-05-28    AI05-0136-1/07
+!standard  A.18.17(0)
+!standard  A.18.25(0)
 !class Amendment 09-02-04
 !status Amendment 201Z 10-01-15
 !status ARG Approved 9-0-3  09-11-07
@@ -10,7 +12,7 @@
 
 !summary
 
-Add a multiway tree container.
+Multiway tree containers are added.
 
 !problem
 
@@ -29,10 +31,10 @@
 incomplete type and an access type (which could be anonymous). (If Ada did not
 require that, then the implementation of the containers would be significantly
 constrained; in particular, bounded forms would be incompatible with direct
-inclusion in the elements). The use of an access type here necessarily requires the use of
-allocators and thus hand-written memory management. Indeed, it probably harder
-to use one of the existing container in this way than it is to write the
-operations directly.
+inclusion in the elements). The use of an access type here necessarily requires
+the use of allocators and thus hand-written memory management. Indeed, it is
+probably harder to use one of the existing container in this way than it is to
+write the operations directly.
 
 This situation cries out for a solution, and the easiest one is to provide one
 or more appropriate containers.
@@ -40,7 +42,7 @@
 !proposal
 
 Add a multiway tree container. A multiway tree allows multiple child elements
-for each parent element. (Such a tree is sometimes known as parent-child-sibling
+for each parent element. (Such a tree is sometimes known as a parent-child-sibling
 tree.) A multiway tree is the most general tree; many problems map directly into
 it (see examples for a number of such cases).
 
@@ -49,11 +51,10 @@
 Add the multiway tree to the list of containers defined in A.18(4.j).
 
 
-A.18.xx The Package Containers.Multiway_Trees
+A.18.10 The Package Containers.Multiway_Trees
 
-[Editor's Note: What should the actual clause numbers be for these containers?
-A natural insertion would require renumbering all of the indefinite containers. The
-ARG said that yes, we should renumber all of the indefinite containers.]
+[Editor's Note: The full ARG decided to use a natural insertion that requires
+renumbering all of the indefinite containers.]
 
 The language-defined generic package Containers.Multiway_Trees provides private
 types Tree and Cursor, and a set of operations for each type. A multiway tree
@@ -86,12 +87,6 @@
 the child list of the child node is visited before the next sibling of the child
 node is visited.
 
-[Editor's note: I didn't define a breadth-first order. Such an order requires
-two trips through the child list (one to visit the child nodes, and once to to
-visit the children of those nodes. It also doesn't make sense for
-debugging/output applications, so it wasn't clear that it was very useful. Thus
-I didn't use it in any of the defined operations.]
-
 Static Semantics
 
 The generic library package Containers.Multiway_Trees has the following
@@ -152,7 +147,7 @@
       Process   : not null access procedure
                       (Element : in out Element_Type));
 
-   procedure Assign (Target : in out Tree; Source : Tree);
+   procedure Assign (Target : in out Tree; Source : in Tree);
 
    function Copy (Source : Tree) return Tree;
 
@@ -191,6 +186,10 @@
      (Container : in Tree;
       Process   : not null access procedure (Position : in Cursor));
 
+   procedure Iterate_Subtree
+     (Position  : in Cursor;
+      Process   : not null access procedure (Position : in Cursor));
+
    function Child_Count (Parent : Cursor) return Count_Type;
 
    function Child_Depth (Parent, Child : Cursor) return Count_Type;
@@ -329,8 +328,8 @@
 one of these operations also are included. Similarly, operations which call one
 of these as part of their definition are included.
 
-* it reorders the elements of T, that is, it calls the Splice or Splice_Children
-  procedures; or
+* it reorders the elements of T, that is, it calls the Splice_Subtree or
+  Splice_Children procedures; or
 
 * it finalizes T; or
 
@@ -368,7 +367,7 @@
       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
+      child element of the element designated by Right_Position. If any such
       call returns False, the function returns False; otherwise it returns True.
       Any exception raised during the evaluation of element equality is
       propagated.
@@ -424,17 +423,11 @@
    function Depth (Position : Cursor) return Count_Type;
 
       If Position equals No_Element, Depth returns 0; otherwise Depth returns
-      the number of ancestor nodes of the element at Position (including the
-      element itself).
+      the number of ancestor nodes of the node designated by Position (including
+      the node itself).
 
       AARM Ramification: Depth (Root (Some_Tree)) = 1.
 
-      [Editor's note: Matt suggests that we have this function as well as
-      Child_Depth because this is the most common case. We can't default the
-      Parent parameter in Child_Depth since the correct value depends on the
-      container. Should we ignore the root node here and return a Depth of 0
-      in the previous case?]
-
    function Is_Root (Position : Cursor) return Boolean;
 
       Is_Root returns True if the Position designates the root node of the
@@ -442,11 +435,11 @@
 
    function Is_Leaf (Position : Cursor) return Boolean;
 
-      Is_Leaf returns True if Position designates an element that does not have
+      Is_Leaf returns True if Position designates a node that does not have
       any child nodes; and returns False otherwise.
 
-      AARM Ramification: Is_Leaf returns False if passed No_Element, as
-      No_Element does not designate an element. Is_Leaf can be passed a cursor
+      AARM Ramification: Is_Leaf returns False if passed No_Element, since
+      No_Element does not designate a node. Is_Leaf can be passed a cursor
       that designates the root node; Is_Leaf will return True if passed
       the root node of an empty tree.
 
@@ -508,7 +501,7 @@
       If Element_Type is unconstrained and definite, then the actual Element
       parameter of Process.all shall be unconstrained.
 
-   procedure Assign (Target : in out Tree; Source : Tree);
+   procedure Assign (Target : in out Tree; Source : in Tree);
 
       If Target denotes the same object as Source, the operation has no
       effect. Otherwise, it calls Clear (Target), and then each element of Source is
@@ -575,8 +568,8 @@
 
       AARM Ramification: After a call to Swap, I designates the element value
       previously designated by J, and J designates the element value previously
-      designated by I. The elements position do not change; for instance, the
-      parent node and the first child node of I are unchanged by the operation.
+      designated by I. The position of the elements do not change; for instance,
+      the parent node and the first child node of I are unchanged by the operation.
 
       The root nodes do not contain element values, so they cannot be swapped
       End AARM Ramification.
@@ -590,18 +583,18 @@
       return Cursor;
 
       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 generic formal equality operator). The search starts at the root node.
       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;
 
       If Position equals No_Element, then Constraint_Error is propagated; if Position
-      does not designate a node in Container, then Program_Error is propagated. 
+      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
@@ -663,7 +656,8 @@
       [Editor's note: It is a bit weird to skip the root node, but it seems better
       that every cursor has an associated element. The alternative that the root
       node is returned would require most Process implementations to test Is_Root
-      explicitly before doing any element operations.]
+      explicitly before doing any element operations; that would be a tripping
+      hazard (very easy to forget).]
 
       AARM Implementation Note: The purpose of the tamper with cursors check is
       to prevent erroneous execution from the Position parameter of Process.all
@@ -677,6 +671,21 @@
       check.
       End AARM Implementation Note.
 
+   procedure Iterate_Subtree
+     (Position  : in Cursor;
+      Process   : not null access procedure (Position : in Cursor));
+
+      If Position equals No_Element, then Constraint_Error is propagated.
+      Iterate calls Process.all with a cursor that designates each element in
+      the subtree rooted by the node designated by Position, starting with the
+      node designated by Position and proceeding in a depth-first order. Program_Error
+      is propagated if Process.all tampers with the cursors of Container. Any
+      exception raised by Process.all is propagated.
+
+      AARM Ramification: Position can be passed a cursor designating the root
+      node; in that case, Process is not called with the root node, which does
+      not have an associated element.
+
    function Child_Count (Parent : Cursor) return Count_Type;
 
       Child_Count returns the number of child nodes of the node designated
@@ -687,7 +696,7 @@
       If Child or Parent is equal to No_Element, then Constraint_Error is
       propagated. Otherwise, Child_Depth returns the number of ancestor nodes
       of Child (including Child itself), up to but not including Parent;
-      in this case Program_Error is propagated if Parent is not an 
+      in this case Program_Error is propagated if Parent is not an
       ancestor of Child.
 
       AARM Ramification: Program_Error is propagated if Parent and Child are
@@ -703,15 +712,16 @@
                            New_Item  : in     Element_Type;
                            Count     : in     Count_Type := 1);
 
-      If Parent equals No_Element, the Constraint_Error is propagated. If Parent
+      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 Before is not equal to No_Element, and 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 Parent, then
       Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes
-      containing copies of New_Item and inserts them as children of Parent prior
-      to the element designated by Before. If Before equals No_Element, the new
-      nodes are inserted after the last child node of Parent (if any). Any
+      containing copies of New_Item and inserts them as children 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 child node of Parent. Any
       exception raised during allocation of internal storage is propagated,
       and Container is not modified.
 
@@ -722,17 +732,18 @@
                            Position  :    out Cursor;
                            Count     : in     Count_Type := 1);
 
-      If Parent equals No_Element, the Constraint_Error is propagated. If Parent
+      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 Before is not equal to No_Element, and 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 Parent, then
       Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes
-      containing copies of New_Item and inserts them as children of Parent prior
-      to the element designated by Before. If Before equals No_Element, the new
-      nodes are inserted after the last child node of Parent (if any).
-      Position designates the first newly-inserted node. Any exception raised
-      during allocation of internal storage is propagated, and Container is not modified.
+      containing copies of New_Item and inserts them as children 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 child node of Parent. Position designates
+      the first newly-inserted node. Any exception raised during allocation of
+      internal storage is propagated, and Container is not modified.
 
    procedure Insert_Child (Container : in out Tree;
                            Parent    : in     Cursor;
@@ -740,18 +751,20 @@
                            Position  :    out Cursor;
                            Count     : in     Count_Type := 1);
 
-      If Parent equals No_Element, the Constraint_Error is propagated. If Parent
+      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 Before is not equal to No_Element, and 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 Parent, then
-      Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes
-      and inserts them as children of Parent prior to the element designated by Before.
-      If Before equals No_Element, the new elements are inserted after the last child
-      node of Parent (if any). The elements contained in the new nodes are
-      initialized by default (see 3.3.1). Position designates the first newly-inserted node.
-      Any exception raised during allocation of internal storage is propagated, and
-      Container is not modified.
+      Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes,
+      the elements contained in the new nodes are initialized by default
+      (see 3.3.1), and the new nodes are inserted as children 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 child node of Parent.
+      Position designates the first newly-inserted node. Any exception raised
+      during allocation of internal storage is propagated, and Container is not
+      modified.
 
    procedure Prepend_Child (Container : in out Tree;
                             Parent    : in     Cursor;
@@ -790,22 +803,25 @@
                            Before   : in     Cursor;
                            Source   : in     Cursor);
 
-      If Parent equals No_Element, the Constraint_Error is propagated. If Parent
+      If Parent equals No_Element, then Constraint_Error is propagated. If Parent
       does not designate a node in Target, then Program_Error is propagated.
       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 Source designates a root node,
-      Constraint_Error is propagated. If Source is equal to No_Element,
+      then Constraint_Error is propagated. If Source is equal to No_Element,
       then the operation has no effect. 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 inserted
-      into Target immediately prior to Before, or, if Before equals No_Element,
-      after the last child node of Parent (if any). The parent of the newly created
+      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 child node of Parent. The parent of the newly created
       subtree is set to Parent, and the overall count of Target is incremented
-      by Subtree_Count (Source).
+      by Subtree_Count (Source). Any exception raised during allocation of
+      internal storage is propagated, and Container is not modified.
 
       AARM Discussion: We only need one routine here, as the source object
       is not modified, so we can use the same routine for both copying within
@@ -826,7 +842,7 @@
                              Source   : in out Tree;
                              Position : in out Cursor);
 
-      If Parent equals No_Element, the Constraint_Error is propagated. If Parent
+      If Parent equals No_Element, then Constraint_Error is propagated. If Parent
       does not designate a node in Target, then Program_Error is propagated.
       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
@@ -836,9 +852,11 @@
       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
-      immediately prior to Before, or, if Before equals No_Element, after the
-      last child node of Parent (if any). In each of these cases, Position and the
+      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 Before,
+      or, if Before equals No_Element, the moved nodes are inserted after the
+      last existing child node of Parent. In each of these cases, Position and the
       count of Target are unchanged, and the parent of the element designated
       by Position is set to Parent.
 
@@ -850,9 +868,10 @@
       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
-      element designated by Before. If Before equals No_Element, the subtree is
-      inserted after the last child node of Parent (if any). In each of these cases,
+      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
+      inserted after the last existing child node of Parent. In each of these cases,
       the count of Target is incremented by Subtree_Count (Position), and the
       count of Source is decremented by Subtree_Count (Position), Position is
       updated to represent an element in Target.
@@ -874,7 +893,7 @@
                              Before   : in     Cursor;
                              Position : in     Cursor);
 
-      If Parent equals No_Element, the Constraint_Error is propagated. If Parent
+      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 Before is not equal to No_Element, and does not designate a node in
       Container, then Program_Error is propagated. If Before is not equal to
@@ -884,9 +903,11 @@
       a node in Container, then Program_Error is propagated. If Position equals
       Before, there is no effect. If Position designates an ancestor of Parent
       or is equal to Parent, Constraint_Error is propagated. Otherwise, the subtree
-      rooted by the element designated by Position is moved immediately prior to
-      Before, or, if Before equals No_Element, after the last child node of Parent
-      (if any). The parent of the element designated by Position is set to Parent.
+      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 Before, or, if Before equals No_Element, the moved nodes
+      are inserted after the last existing child node of Parent.
+      The parent of the element designated by Position is set to Parent.
 
       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
@@ -903,20 +924,22 @@
       If Target_Parent does not designate a node in Target, then Program_Error
       is propagated. If Before is not equal to No_Element, and does not designate
       an element in Target, then Program_Error is propagated. If Source_Parent
-      equals No_Element, Constraint_Error is propagated. If Source_Parent does not
-      designate a node in Source, then Program_Error is propagated. If Before
-      is not equal to No_Element, and Target.Parent (Before) is not equal to
-      Target_Parent, then Constraint_Error is propagated.
+      equals No_Element, then Constraint_Error is propagated. If Source_Parent
+      does not designate a node in Source, then Program_Error is propagated. If
+      Before is not equal to No_Element, and Target.Parent (Before) is not equal
+      to Target_Parent, then Constraint_Error is propagated.
 
       If Source denotes the same object as Target, then:
         * if Target_Parent equals Source_Parent there is no effect; else
         * if Source_Parent is an ancestor of Target_Parent, then Constraint_Error
           is propagated; else
         * the child elements (and their descendants) of Source_Parent are moved
-	  to be child elements of Target_Parent immediately prior to Before, or,
-	  if Before equals No_Element, after the last child node of
-	  Target_Parent (if any). The parent of each moved child element is
-	  set to Target_Parent.
+	  to be child elements of Target_Parent. If Target_Parent already has
+          child elements then the moved elements are inserted prior to the node
+          designated by Before, or, if Before equals No_Element, the moved
+          elements are inserted after the last existing child node of
+          Target_Parent. The parent of each moved child element is set to
+          Target_Parent.
 
       AARM Reason: We can't allow moving the children of Source_Parent to a
       descendant node, as the descendant node will be part of one of the
@@ -924,13 +947,13 @@
 
       Otherwise (if Source does not denote the same object as Target), the child
       elements (and their descendants) of Source_Parent are removed from Source
-      and moved to Target. The child elements are
-      inserted as children of Target_Parent prior to the element designated by
-      Before. If Before equals No_Element, the child elements are
-      inserted after the last child node of Target_Parent (if any). In each of
-      these cases, the overall count of Target is incremented by Subtree_Count
-      (Source_Parent)-1, and overall count of Source is decremented by
-      Subtree_Count (Source_Parent)-1.
+      and moved to Target. The child elements are inserted as children of
+      Target_Parent. If Target_Parent already has child elements then the moved
+      elements are inserted prior to the node designated by Before, or, if Before
+      equals No_Element, the moved elements are inserted after the last existing
+      child node of Target_Parent. In each of these cases, the overall count of
+      Target is incremented by Subtree_Count (Source_Parent)-1, and overall count
+      of Source is decremented by Subtree_Count (Source_Parent)-1.
 
       AARM Ramification: The node designated by Source_Parent is not moved, thus
       we never need to update Source_Parent.
@@ -955,9 +978,11 @@
       Source_Parent there is no effect. If Source_Parent is an ancestor of
       Target_Parent, then Constraint_Error is propagated. Otherwise the child
       elements (and their descendants) of Source_Parent are moved to be child
-      elements of Target_Parent immediately prior to Before, or, if Before equals
-      No_Element, after the last child node of Target_Parent (if any). The
-      parent of each moved child element is set to Target_Parent.
+      elements of Target_Parent. If Target_Parent already has child elements then
+      the moved elements are inserted prior to the node designated by Before, or,
+      if Before equals No_Element, the moved elements are inserted after the last
+      existing child node of Target_Parent. The parent of each moved child element
+      is set to Target_Parent.
 
    function Parent (Position : Cursor) return Cursor;
 
@@ -1126,12 +1151,12 @@
 don't want to require heroic efforts, so we just require documentation of cases
 where this can't be accomplished.
 
-A.18.YY The Package Containers.Indefinite_Multiway_Trees
 
+A.18.17 The Package Containers.Indefinite_Multiway_Trees
+
 The language-defined generic package Containers.Indefinite_Multiway_Trees
-provides private types Tree and Cursor, and a set of operations for each type.
-It provides the same operations and semantics as the package
-Containers.Multiway_Trees (see A.18.xx), with the difference that the generic
+provides a multiway tree with the same operations as the package
+Containers.Multiway_Trees (see A.18.10), with the difference that the generic
 formal Element_Type is indefinite.
 
 Static Semantics
@@ -1153,19 +1178,19 @@
 default-initialized object of an indefinite type. We considered having this
 routine insert an empty element similar to the empty elements of a vector, but
 rejected this possibility because the semantics are fairly complex and very
-different from the existing case. That would make it more error-prone to convert
-a container from a definite type to an indefinite type; by omitting the routine
-completely, any problems will be diagnosed by the compiler.
+different from the existing definite container. That would make it more
+error-prone to convert a container from a definite type to an indefinite type;
+by omitting the routine completely, any problems will be diagnosed by the compiler.
 
 The actual Element parameter of access subprogram Process of Update_Element may
 be constrained even if Element_Type is unconstrained.
 
-A.18.ZZ The Package Containers.Bounded_Multiway_Trees
 
+A.18.25 The Package Containers.Bounded_Multiway_Trees
 
 The language-defined generic package Containers.Bounded_Multiway_Trees
 provides a private type Tree and a set of operations. It provides the same
-operations as the package Containers.Multiway_Trees (see A.18.XX), with the
+operations as the package Containers.Multiway_Trees (see A.18.10), with the
 difference that the maximum storage is bounded.
 
 Static Semantics
@@ -1197,8 +1222,8 @@
 
     * Function Copy is declared as follows:
 
-         function Copy (Source : Tree; Capacity : Count_Type := 0)
-	   return List;
+         function Copy (Source : Tree;
+                        Capacity : Count_Type := 0) return Tree;
 
       If Capacity is 0, then the tree capacity is the count of
       Source; if Capacity is equal to or greater than Source.Count,
@@ -1206,18 +1231,18 @@
       otherwise, the operation propagates Capacity_Error.
 
     * In the five-parameter procedure Splice_Subtree, if Source is
-      not the same object as Target, if the sum of Target.Count and
-      Subtree_Count (Position) is greater than Target.Capacity, then
-      Splice_Subtree propagates Capacity_Error.
+      not the same object as Target, and if the sum of Target.Count
+      and Subtree_Count (Position) is greater than Target.Capacity,
+      then Splice_Subtree propagates Capacity_Error.
 
     * In the five-parameter procedure Splice_Children, if Source is
-      not the same object as Target, if the sum of if Target.Count
+      not the same object as Target, and if the sum of Target.Count
       and Subtree_Count (Source_Parent)-1 is greater than Target.Capacity,
       then Splice_Children propagates Capacity_Error.
 
 Bounded Errors
 
-It is a bounded error to use a tree if it was the target of an
+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].
 Either Program_Error is raised, or the operation proceeds as defined.
@@ -1237,7 +1262,7 @@
 structures such as the existing containers do not handle nesting well.
 
 The name "multiway tree" seems to be the most common one for this data structure
-in the literature. (It sometimes is written "multi-way tree".)
+in the literature. (It is sometimes written "multi-way tree".)
 
 We do not provide an indexing method in this tree; this is purely a structuring
 data structure. If indexing is needed, a set or map container (already provided
@@ -1248,10 +1273,10 @@
 The basic model is that every element in the tree has an associated doubly-linked
 list of children. Thus we provide almost all of the operations of the list container,
 each with an added Parent parameter. We did not change the basic names of the
-operations for familiarity. We added "_Child" to each name in order to describe
-clearly what is being accessed. We considered leaving the names the same
-(without the "_Child" suffix), but that seemed confusing, as it would be easy to
-believe that First always represents the first node of the root of the tree.
+operations as they are already familiar to programmers. We added "_Child" to each
+name in order to describe clearly what is being accessed. We considered leaving the
+names the same (without the "_Child" suffix), but that seemed confusing, as it would
+be easy to believe that First always represents the first node of the root of the tree.
 
 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
@@ -1262,7 +1287,7 @@
 operate on entire subtrees, as opposed to a single element. While this isn't
 strictly necessary, it should enhance readability of code.
 
-Elements are stored in internal nodes (as in the linked list container).
+Elements are stored in internal nodes (as in the linked list containers).
 
 There is a built-in root node in each container. The root node does not contain
 an element value (in order to avoid complications with uninitialized values
@@ -1320,18 +1345,18 @@
     elements. And it also doesn't make any sense on the entire container.
 
 
-More on the value-less root model:
+More on the valueless root model:
 
 Since the top-level subtrees can be thought of as a forest of trees, it would
 be easy to build an implementation of the XML DOM directly using one of these
 tree containers. The XML DOM includes the capability of inserting elements
-without including them in the main tree. Such "orphan" elements could be 
+without including them in the main tree. Such "orphan" elements could be
 modeled as children of the root node, with the first child representing
 the main tree.
 
 
 We hope that the valueless root model provides the right balance between the orphan
-model used by the XML DOM and a "classic" single-rooted tree. It appears to keep 
+model used by the XML DOM and a "classic" single-rooted tree. It appears to keep
 special cases to a minimum, while not straying too far from the typical terminology of
 trees.
 
@@ -1344,18 +1369,18 @@
 If we defined the tree using traditional node insertion, then we would have to have
 rules for an empty tree and in addition we would need rules to prevent inserting a
 second root (this would be necessary for at least the various Inserts, Splices, Copy_Subtree).
-But this somewhat silly, given that the first operation on every tree object would have
-to be to insert the one-and-only root.
+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. 
+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:
-* A empty tree would contain one valid element (which could be read);
+* An empty tree would contain one valid element (which could be read);
 * The value of this extra node would often need to be ignored (if a forest of subtrees is
   being used) or replaced - this would add many additional opportunities for errors;
 * The indefinite container form could not use this solution, as there is no default initial
@@ -1386,7 +1411,7 @@
 every operation to avoid this happening.
 
 When the root node does not have a value, it cannot be spliced or copied into any tree, so
-the problem with excess dummy nodes do not occur. 
+the problems with excess dummy nodes do not occur.
 
 Even more annoying would be the complications for doing tree transformations. Consider
 again the expression trees in an Ada compiler. One common transformation is to change
@@ -1406,7 +1431,7 @@
     end Change_Not_Equals;
 
 Since the current package does not allow the root node to have a value, Position cannot
-designate the root node (it cannot designate a call element, obviously). Thus Insert_Child
+designate the root node (the root cannot designate a call element, obviously). Thus Insert_Child
 will add a node somewhere in the tree, but it won't try to add a second root. More generally,
 tree transformations only involve nodes with values, so they will not (directly) involve
 the root node.
@@ -1432,15 +1457,14 @@
 complex if the number of children were not fixed as in this example - imagine a similar
 transformation on any function call.) It also ends up with the original cursor pointing
 to a different node than the original code (which might be significant).
- 
 
 
+Iterators:
 
-Further ideas:
+We considered having additional iterators. One could imagine wanting to visit the child
+nodes before their parents, as well as a straight breadth-first iteration. One could
+even imagine in-order iteration.
 
-* More iterators could be useful. One could imagine wanting to visit the child
-  nodes before their parents, as well as a straight breadth-first iteration.
-
 One possible way to (re)structure the overall iterator is to have two process
 routines, one that is called when a node is first visited, and the second after
 the children are visited. (That would allow a more direct mapping of the HTML
@@ -1455,10 +1479,24 @@
 isn't needed, it can be skipped.)
 
 The biggest objection to such an iterator is that it can't be mapped into
-for-loop-like syntax (one hopes that some future version of Ada will allow
-that).
+for-loop-like syntax as proposed in AI05-0139-2.
+
+One also could have a separate Breadth-First iterator. However, since that order
+requires two trips through the child list (one to visit the child nodes, and one to
+visit the children of those nodes, it is rather inefficient. It also doesn't make
+sense for debugging/output applications, so it wasn't clear that it was very useful.
+
+Similarly, one could define an In-Order iterator. However, that really only makes
+sense for binary trees with exactly two children, while a multiway tree can have more
+or less children. (The interpretation of a node with one child could depend on the
+node: contrast a "unary minus" node with a "First attribute" node.) So it seems
+likely that such an iterator would be confusing and not necessarily provide the
+intended semantics.
 
+Moreover, creating iterators by hand is relatively easy to do using cursors. So
+we don't provide additional iterators.
 
+
 Advantages of the multiway tree container over hand-created trees:
 
 (1) Complete memory management, including for indefinite elements.
@@ -1480,7 +1518,7 @@
 Disadvantages of the multiway tree container:
 
 (1) Not as familiar as some other containers; may not be used as much for that
-    reason. (Authors can help aleviate this situation somewhat.)
+    reason. (Authors can help alleviate this situation somewhat.)
 
 (2) Not as general as a general graph structure. But a general graph structure
     is much harder to describe, it is harder to manage memory for, and is not as
@@ -1586,7 +1624,7 @@
 (2) Windows in a GUI.
 
 Windows in a GUI typically are structured as a multiway tree: each window can
-have a (theroetically) unlimited number of child windows. For instance, in
+have a (theoretically) unlimited number of child windows. For instance, in
 Microsoft Windows, controls like buttons, check boxes, and edit controls are
 child windows.
 
@@ -1612,22 +1650,22 @@
 memory management burden on the container, rather than the programmer of the
 processor.
 
-(4) Compiler symboltable.
+(4) Compiler symbol table.
 
-The symboltable in a compiler is also a multiway tree. Entities declared in a
+The symbol table in a compiler is also a multiway tree. Entities declared in a
 single declarative part are a list (order of elements is significant). Of course,
 many kinds of entities have their own declarations (in Ada, records have components
 and discriminants; subprograms have parameters; blocks have declarative parts; etc.)
 This maps naturally into a multiway tree, where the entities that belong to a
 particular entity are represented as a child list of the tree.
 
-If a compiler needed to save a symboltable for some reason, it could easily be
+If a compiler needed to save a symbol table for some reason, it could easily be
 done using the streaming operations of the container. [Author's note: sure would
 have saved a lot of work for Janus/Ada...but perhaps wouldn't be fast enough.]
 
-A debugging symboltable dump could be done as a simple iterator:
+A debugging symbol table dump could be done as a simple iterator:
 
-   procedure Dump_Symboltable (Table : Symbol.Tree) is
+   procedure Dump_Symbol_Table (Table : Symbol.Tree) is
      procedure Process (Node : Symbol_Cursor) is
      begin
         Put ((1 .. Child_Depth(Node)*2) => ' '); -- Indent based on the depth.
@@ -1635,11 +1673,974 @@
      end Process;
    begin
      Iterate (Tree, Process'Access);
-   end Process;
+   end Dump_Symbol_Table;
+
+!corrigendum A.18.10(0)
+
+@dinsc
+
+The language-defined generic package Containers.Multiway_Trees provides private
+types Tree and Cursor, and a set of operations for each type. A multiway tree
+container is well-suited to represent nested structures.
+
+A multiway tree container object manages a tree of internal @i<nodes>, each of which
+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, 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.
+
+A @i<subtree> is a particular node (which @i<roots the subtree>) and all of its child
+nodes (including all of the children of the child nodes, recursively). There is
+a special node, the @i<root>, which is always present and has no associated element
+value. The root node provides a place to add nodes to an otherwise empty tree and
+represents the bottom of the tree.
+
+A node that has no children is called a @i<leaf node>. The @i<ancestors> of a node
+are the parent node, the parent of the parent node, and so on until a node with
+no parent is reached. Similarly, the @i<descendants> of a node are the child nodes,
+the children of each child node, and so on.
+
+The nodes of a subtree could be visited in several different orders. For a
+@i<depth-first order>, the last step of visiting a node is to visit the nodes of
+its child list in order, recursively.
+
+AARM Ramification: For the depth-first order, when each child node is visited,
+the child list of the child node is visited before the next sibling of the child
+node is visited.
+
+@s8<@i<Static Semantics>>
+
+The generic library package Containers.Multiway_Trees has the following
+declaration:
+
+@xcode<@b<generic>
+   @b<type> Element_Type @b<is private>;
+   @b<with function> "=" (Left, Right : Element_Type) @b<return> Boolean @b<is> <@>;
+@b<package> Ada.Containers.Multiway_Trees @b<is>
+   @b<pragma> Preelaborate(Multiway_Trees);
+   @b<pragma> Remote_Types(Multiway_Trees);
+
+   @b<type> Tree @b<is tagged private>;
+   @b<pragma> Preelaborable_Initialization(Tree);
+
+   @b<type> Cursor @b<is private>;
+   @b<pragma> Preelaborable_Initialization(Cursor);
+
+   Empty_Tree : @b<constant> Tree;
+
+   No_Element : @b<constant> Cursor;
+
+   @b<function> Equal_Subtree (Left_Position : Cursor;
+                           Right_Position: Cursor) @b<return> Boolean;
+
+   @b<function> "=" (Left, Right : Tree) @b<return> Boolean;
+
+   @b<function> Is_Empty (Container : Tree) @b<return> Boolean;
+
+   @b<function> Node_Count (Container : Tree) @b<return> Count_Type;
+
+   @b<function> Subtree_Node_Count (Position : Cursor) @b<return> Count_Type;
+
+   @b<function> Depth (Position : Cursor) @b<return> Count_Type;
+
+   @b<function> Is_Root (Position : Cursor) @b<return> Boolean;
 
+   @b<function> Is_Leaf (Position : Cursor) @b<return> Boolean;
 
+   @b<function> Root (Container : Tree) @b<return> Cursor;
+
+   @b<procedure> Clear (Container : @b<in out> Tree);
+
+   @b<function> Element (Position : Cursor) @b<return> Element_Type;
+
+   @b<procedure> Replace_Element (Container : @b<in out> Tree;
+                              Position  : @b<in>     Cursor;
+                              New_Item  : @b<in>     Element_Type);
+
+   @b<procedure> Query_Element
+     (Position : @b<in> Cursor;
+      Process  : @b<not null access procedure> (Element : @b<in> Element_Type));
+
+   @b<procedure> Update_Element
+     (Container : @b<in out> Tree;
+      Position  : @b<in>     Cursor;
+      Process   : @b<not null access procedure>
+                      (Element : @b<in out> Element_Type));
+
+   @b<procedure> Assign (Target : @b<in out> Tree; Source : @b<in> Tree);
+
+   @b<function> Copy (Source : Tree) @b<return> Tree;
+
+   @b<procedure> Move (Target : @b<in out> Tree;
+                   Source : @b<in out> Tree);
+
+   @b<procedure> Delete_Leaf (Container : @b<in out> Tree;
+                          Position  : @b<in out> Cursor);
+
+   @b<procedure> Delete_Subtree (Container : @b<in out> Tree;
+                             Position  : @b<in out> Cursor);
+
+   @b<procedure> Swap (Container : @b<in out> Tree;
+                   I, J      : @b<in>     Cursor);
+
+   @b<function> Find (Container : Tree;
+                  Item      : Element_Type)
+      @b<return> Cursor;
+
+   @b<function> Find_In_Subtree (Container : Tree;
+                             Item      : Element_Type;
+                             Position  : Cursor)
+      @b<return> Cursor;
+
+   @b<function> Ancestor_Find (Container : Tree;
+                           Item      : Element_Type;
+                           Position  : Cursor)
+      @b<return> Cursor;
+
+   @b<function> Contains (Container : Tree;
+                      Item      : Element_Type) @b<return> Boolean;
+
+   @b<function> Has_Element (Position : Cursor) @b<return> Boolean;
+
+   @b<procedure> Iterate
+     (Container : @b<in> Tree;
+      Process   : @b<not null access procedure> (Position : @b<in> Cursor));
+
+   @b<procedure> Iterate_Subtree
+     (Position  : @b<in> Cursor;
+      Process   : @b<not null access procedure> (Position : @b<in> Cursor));
+
+   @b<function> Child_Count (Parent : Cursor) @b<return> Count_Type;
+
+   @b<function> Child_Depth (Parent, Child : Cursor) @b<return> Count_Type;
+
+   @b<procedure> Insert_Child (Container : @b<in out> Tree;
+                           Parent    : @b<in>     Cursor;
+                           Before    : @b<in>     Cursor;
+                           New_Item  : @b<in>     Element_Type;
+                           Count     : @b<in>     Count_Type := 1);
+
+   @b<procedure> Insert_Child (Container : @b<in out> Tree;
+                           Parent    : @b<in>     Cursor;
+                           Before    : @b<in>     Cursor;
+                           New_Item  : @b<in>     Element_Type;
+                           Position  :    @b<out> Cursor;
+                           Count     : @b<in>     Count_Type := 1);
+
+   @b<procedure> Insert_Child (Container : @b<in out> Tree;
+                           Parent    : @b<in>     Cursor;
+                           Before    : @b<in>     Cursor;
+                           Position  :    @b<out> Cursor;
+                           Count     : @b<in>     Count_Type := 1);
+
+   @b<procedure> Prepend_Child (Container : @b<in out> Tree;
+                            Parent    : @b<in>     Cursor;
+                            New_Item  : @b<in>     Element_Type;
+                            Count     : @b<in>     Count_Type := 1);
+
+   @b<procedure> Append_Child (Container : @b<in out> Tree;
+                           Parent    : @b<in>     Cursor;
+                           New_Item  : @b<in>     Element_Type;
+                           Count     : @b<in>     Count_Type := 1);
+
+   @b<procedure> Delete_Children (Container : @b<in out> Tree;
+                              Parent    : @b<in>     Cursor);
+
+   @b<procedure> Copy_Subtree (Target   : @b<in out> Tree;
+                           Parent   : @b<in>     Cursor;
+                           Before   : @b<in>     Cursor;
+                           Source   : @b<in>     Cursor);
+
+   @b<procedure> Splice_Subtree (Target   : @b<in out> Tree;
+                             Parent   : @b<in>     Cursor;
+                             Before   : @b<in>     Cursor;
+                             Source   : @b<in out> Tree;
+                             Position : @b<in out> Cursor);
+
+   @b<procedure> Splice_Subtree (Container: @b<in out> Tree;
+                             Parent   : @b<in>     Cursor;
+                             Before   : @b<in>     Cursor;
+                             Position : @b<in>     Cursor);
+
+   @b<procedure> Splice_Children (Target          : @b<in out> Tree;
+                              Target_Parent   : @b<in>     Cursor;
+                              Before          : @b<in>     Cursor;
+                              Source          : @b<in out> Tree;
+                              Source_Parent   : @b<in>     Cursor);
+
+   @b<procedure> Splice_Children (Container       : @b<in out> Tree;
+                              Target_Parent   : @b<in>     Cursor;
+                              Before          : @b<in>     Cursor;
+                              Source_Parent   : @b<in>     Cursor);
+
+   @b<function> Parent (Position : Cursor) @b<return> Cursor;
+
+   @b<function> First_Child (Parent : Cursor) @b<return> Cursor;
+
+   @b<function> First_Child_Element (Parent : Cursor) @b<return> Element_Type;
+
+   @b<function> Last_Child (Parent : Cursor) @b<return> Cursor;
+
+   @b<function> Last_Child_Element (Parent : Cursor) @b<return> Element_Type;
+
+   @b<function> Next_Sibling (Position : Cursor) @b<return> Cursor;
+
+   @b<function> Previous_Sibling (Position : Cursor) @b<return> Cursor;
+
+   @b<procedure> Next_Sibling (Position : @b<in out> Cursor);
+
+   @b<procedure> Previous_Sibling (Position : @b<in out> Cursor);
+
+   @b<procedure> Iterate_Children
+     (Container : @b<in> Tree;
+      Parent    : @b<in>     Cursor;
+      Process   : @b<not null access procedure> (Position : @b<in> Cursor));
+
+   @b<procedure> Reverse_Iterate_Children
+     (Container : @b<in> Tree;
+      Parent    : @b<in>     Cursor;
+      Process   : @b<not null access procedure> (Position : @b<in> Cursor));
+
+@b<private>
+   ... -- not specified by the language
+@b<end> Ada.Containers.Multiway_Trees;>
+
+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
+number of calls of this generic formal function by the functions Find,
+Reverse_Find, Equal_Subtrees, and "=" on tree values are unspecified.
+
+The type Tree is used to represent trees. The type Tree needs finalization (see
+7.6).
+
+Empty_Tree represents the empty Tree object. It contains only the root node (Count
+(Empty_Tree) returns 1). If an object of type Tree is not otherwise initialized,
+it is initialized to the same value as Empty_Tree.
+
+No_Element represents a cursor that designates no element. If an object of type
+Cursor is not otherwise initialized, it is initialized to the same value as
+No_Element.
+
+The predefined "=" operator for type Cursor returns True if both cursors are
+No_Element, or designate the same element in the same container.
+
+Execution of the default implementation of the Input, Output, Read, or Write
+attribute of type Cursor raises Program_Error.
+
+Tree'Write writes Tree.Count-1 elements to the stream.
+Tree'Read reads Tree.Count-1 elements from the stream.
+
+Some operations of this generic package have access-to-subprogram parameters. To
+ensure such operations are well-defined, they guard against certain actions by
+the designated subprogram. In particular, some operations check for "tampering
+with cursors" of a container because they depend on the set of elements of the
+container remaining constant, and others check for "tampering with elements" of
+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;
+or>
+
+@xbullet<it reorders the elements of @i<T>, that is, it calls the Splice_Subtree
+or Splice_Children procedures; or>
+
+@xbullet<it finalizes @i<T>; or>
+
+@xbullet<it calls Assign with @i<T> as the Target parameter; or>
+
+@xbullet<it calls the Move procedure with @i<T> as a parameter.>
+
+A subprogram is said to @i<tamper with elements> of a tree object @i<T> if:
+
+@xbullet<it tampers with cursors of @i<T>; or>
+
+@xbullet<it replaces one or more elements of @i<T>, that is, it calls the
+Replace_Element or Swap procedures with @i<T> as a parameter.>
+
+@xcode<@b<function> Equal_Subtree (Left_Position : Cursor;
+                        Right_Position: Cursor) @b<return> Boolean;>
+
+@xindent<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. 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 designated by
+Right_Position. If any such call returns False, the function returns False;
+otherwise it returns True. Any exception raised during the evaluation of element
+equality is propagated.>
+
+@xcode<@b<function> "=" (Left, Right : Tree) @b<return> Boolean;>
+
+@xindent<If Left and Right denote the same tree object, then the function
+returns True. Otherwise, it calls Equal_Subtree with a cursor designating the
+root node of Left and Right; the result is returned. Any exception raised during
+the evaluation of Equal_Subtree is propagated.>
+
+@xcode<@b<function> Node_Count (Container : Tree) @b<return> Count_Type;>
+
+@xindent<Node_Count returns the number of nodes in Container.>
+
+@xcode<@b<function> Subtree_Node_Count (Position : Cursor) @b<return> Count_Type;>
+
+@xindent<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.>
+
+@xcode<@b<function> Is_Empty (Container : Tree) @b<return> Boolean;>
+
+@xindent<Equivalent to Count (Container) = 1.>
+
+@xcode<@b<function> Depth (Position : Cursor) @b<return> Count_Type;>
+
+@xindent<If Position equals No_Element, Depth returns 0; otherwise Depth returns
+the number of ancestor nodes of the node designated by Position (including the
+node itself).>
+
+@xcode<@b<function> Is_Root (Position : Cursor) @b<return> Boolean;>
+
+@xindent<Is_Root returns True if the Position designates the root node of the
+tree; and returns False otherwise.>
+
+@xcode<@b<function> Is_Leaf (Position : Cursor) @b<return> Boolean;>
+
+@xindent<Is_Leaf returns True if Position designates a node that does not have
+any child nodes; and returns False otherwise.>
+
+@xcode<@b<function> Root (Container : Tree) @b<return> Cursor;>
+
+@xindent<Root returns a cursor that designates the root node of Container.>
+
+@xcode<@b<procedure> Clear (Container : @b<in out> Tree);>
+
+@xindent<Removes all the elements from Container.>
+
+@xcode<@b<function> Element (Position : Cursor) @b<return> Element_Type;>
+
+@xindent<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.>
+
+@xcode<@b<procedure> Replace_Element (Container : @b<in out> Tree;
+                           Position  : @b<in>     Cursor;
+                           New_Item  : @b<in>     Element_Type);>
+
+@xindent<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.>
+
+@xcode<@b<procedure> Query_Element
+  (Position : @b<in> Cursor;
+   Process  : @b<not null access procedure> (Element : @b<in> Element_Type));>
+
+@xindent<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.@b<all> with the element designated by
+Position as the argument. Program_Error is propagated if Process.@b<all> tampers
+with the elements of Container. Any exception raised by Process.@b<all> is
+propagated.>
+
+@xcode<@b<procedure> Update_Element
+  (Container : @b<in out> Tree;
+   Position  : @b<in>     Cursor;
+   Process   : @b<not null access procedure>
+                      (Element : @b<in out> Element_Type));>
+
+@xindent<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.@b<all> with the element designated by Position as the argument.
+Program_Error is propagated if Process.@b<all> tampers with the elements of
+Container. Any exception raised by Process.@b<all> is propagated.>
+
+@xindent<If Element_Type is unconstrained and definite, then the actual Element
+parameter of Process.@b<all> shall be unconstrained.>
+
+@xcode<@b<procedure> Assign (Target : @b<in out> Tree; Source : @b<in> Tree);>
+
+@xindent<If Target denotes the same object as Source, the operation has no
+effect. Otherwise, it calls Clear (Target), and then each element of Source is
+assigned to a corresponding element in Target.>
+
+@xcode<@b<function> Copy (Source : Tree) @b<return> Tree;>
+
+@xindent<Returns a tree with the same structure as Source and whose elements are
+initialized from the corresponding elements of Source.>
+
+@xcode<@b<procedure> Move (Target : @b<in out> Tree;
+                Source : @b<in out> Tree);>
+
+@xindent<If Target denotes the same object as Source, then Move has no effect.
+Otherwise, Move first calls Clear (Target). Then, the nodes other than the root
+node in Source are moved to Target (in the same positions). After Move
+completes, Count(Target) is the number of nodes originally in Source, and
+Count(Source) is 1.>
+
+@xcode<@b<procedure> Delete_Leaf (Container : @b<in out> Tree;
+                       Position  : @b<in out> Cursor);>
+
+@xindent<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.>
+
+@xcode<@b<procedure> Delete_Subtree (Container : @b<in out> Tree;
+                          Position  : @b<in out> Cursor);>
+
+@xindent<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.>
+
+@xcode<@b<procedure> Swap (Container : @b<in out> Tree;
+                I, J      : @b<in>     Cursor);>
+
+@xindent<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.>
+
+@xcode<@b<function> Find (Container : Tree;
+               Item      : Element_Type)
+   @b<return> Cursor;>
+
+@xindent<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 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.>
+
+@xcode<@b<function> Find_In_Subtree (Container : Tree;
+                          Item      : Element_Type;
+                          Position  : Cursor)
+      @b<return> Cursor;>
+
+@xindent<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.>
+
+@xcode<@b<function> Ancestor_Find (Container : Tree;
+                        Item      : Element_Type;
+                        Position  : Cursor)
+   @b<return> Cursor;>
+
+@xindent<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.>
+
+@xcode<@b<function> Contains (Container : Tree;
+                   Item      : Element_Type) @b<return> Boolean;>
+
+@xindent<Equivalent to Find (Container, Item) /= No_Element.>
+
+@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.>
+
+@xcode<@b<procedure> Iterate
+  (Container : @b<in> Tree;
+   Process   : @b<not null access procedure> (Position : @b<in> Cursor));>
+
+@xindent<Iterate calls Process.@b<all> with a cursor that designates each
+element in Container, starting with the root node and proceeding in a
+depth-first order. Program_Error is propagated if Process.@b<all> tampers with
+the cursors of Container. Any exception raised by Process.@b<all> is propagated.>
+
+@xcode<@b<procedure> Iterate_Subtree
+  (Position  : @b<in> Cursor;
+   Process   : @b<not null access procedure> (Position : @b<in> Cursor));>
+
+@xindent<If Position equals No_Element, then Constraint_Error is propagated.
+Iterate calls Process.@b<all> with a cursor that designates each element in the
+subtree rooted by the node designated by Position, starting with the node
+designated by Position and proceeding in a depth-first order. Program_Error is
+propagated if Process.@b<all> tampers with the cursors of Container. Any
+exception raised by Process.@b<all> is propagated.>
+
+@xcode<@b<function> Child_Count (Parent : Cursor) @b<return> Count_Type;>
+
+@xindent<Child_Count returns the number of child nodes of the node designated by
+Parent.>
+
+@xcode<@b<function> Child_Depth (Parent, Child : Cursor) @b<return> Count_Type;>
+
+@xindent<If Child or Parent is equal to No_Element, then Constraint_Error is
+propagated. Otherwise, Child_Depth returns the number of ancestor nodes of Child
+(including Child itself), up to but not including Parent; in this case
+Program_Error is propagated if Parent is not an ancestor of Child.>
+
+@xcode<@b<procedure> Insert_Child (Container : @b<in out> Tree;
+                        Parent    : @b<in>     Cursor;
+                        Before    : @b<in>     Cursor;
+                        New_Item  : @b<in>     Element_Type;
+                        Count     : @b<in>     Count_Type := 1);>
+
+@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.
+If Before is not equal to No_Element, and 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 Parent, then
+Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes
+containing copies of New_Item and inserts them as children 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 child node of Parent. Any exception raised
+during allocation of internal storage is propagated, and Container is not
+modified.>
+
+@xcode<@b<procedure> Insert_Child (Container : @b<in out> Tree;
+                        Parent    : @b<in>     Cursor;
+                        Before    : @b<in>     Cursor;
+                        New_Item  : @b<in>     Element_Type;
+                        Position  :    @b<out> Cursor;
+                        Count     : @b<in>     Count_Type := 1);>
+
+@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.
+If Before is not equal to No_Element, and 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 Parent, then
+Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes
+containing copies of New_Item and inserts them as children 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 child node of Parent. Position designates the
+first newly-inserted node. Any exception raised during allocation of internal
+storage is propagated, and Container is not modified.>
+
+@xcode<@b<procedure> Insert_Child (Container : @b<in out> Tree;
+                        Parent    : @b<in>     Cursor;
+                        Before    : @b<in>     Cursor;
+                        Position  :    @b<out> Cursor;
+                        Count     : @b<in>     Count_Type := 1);>
+
+@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.
+If Before is not equal to No_Element, and 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 Parent, then
+Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes,
+the elements contained in the new nodes are initialized by default (see 3.3.1),
+and the new nodes are inserted as children 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 child node of Parent. Position designates the first newly-inserted
+node. Any exception raised during allocation of internal storage is propagated,
+and Container is not modified.>
+
+@xcode<@b<procedure> Prepend_Child (Container : @b<in out> Tree;
+                         Parent    : @b<in>     Cursor;
+                         New_Item  : @b<in>     Element_Type;
+                         Count     : @b<in>     Count_Type := 1);>
+
+@xindent<Equivalent to Insert_Child (Container, Parent, First_Child (Container,
+Parent), New_Item, Count).>
+
+@xcode<@b<procedure> Append_Child (Container : @b<in out> Tree;
+                        Parent    : @b<in>     Cursor;
+                        New_Item  : @b<in>     Element_Type;
+                        Count     : @b<in>     Count_Type := 1);>
+
+@xindent<Equivalent to Insert_Child (Container, Parent, Last_Child (Container,
+Parent), New_Item, Count).>
+
+@xcode<@b<procedure> Delete_Children (Container : @b<in out> Tree;
+                           Parent    : @b<in>     Cursor);>
+
+@xindent<If Parent equals No_Element, then Constraint_Error is propagated. If
+Parent 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.>
+
+@xcode<@b<procedure> Copy_Subtree (Target   : @b<in out> Tree;
+                        Parent   : @b<in>     Cursor;
+                        Before   : @b<in>     Cursor;
+                        Source   : @b<in>     Cursor);>
+
+@xindent<If Parent equals No_Element, then Constraint_Error is propagated. If
+Parent does not designate a node in Target, then Program_Error is propagated. 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 Source designates a root node, then Constraint_Error is
+propagated. If Source is equal to No_Element, then the operation has no effect.
+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
+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
+child node of Parent. The parent of the newly created subtree is set to Parent,
+and the overall count of Target is incremented by Subtree_Count (Source). Any
+exception raised during allocation of internal storage is propagated, and
+Container is not modified.>
+
+@xcode<@b<procedure> Splice_Subtree (Target   : @b<in out> Tree;
+                          Parent   : @b<in>     Cursor;
+                          Before   : @b<in>     Cursor;
+                          Source   : @b<in out> Tree;
+                          Position : @b<in out> Cursor);>
+
+@xindent<If Parent equals No_Element, then Constraint_Error is propagated. If
+Parent does not designate a node in Target, then Program_Error is propagated. 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, 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 to be 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 inserted after the
+last existing child node of Parent. In each of these cases, Position and the
+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
+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
+inserted after the last existing child node of Parent. In each of these cases,
+the count of Target is incremented by Subtree_Count (Position), and the count of
+Source is decremented by Subtree_Count (Position), Position is updated to
+represent an element in Target.>
+
+@xcode<@b<procedure> Splice_Subtree (Container: @b<in out> Tree;
+                          Parent   : @b<in>     Cursor;
+                          Before   : @b<in>     Cursor;
+                          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.
+If Before is not equal to No_Element, and does not designate a node in
+Container, 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 Container, then Program_Error is propagated. If Position equals Before, there
+is no effect. If Position designates an ancestor of Parent or is equal to
+Parent, Constraint_Error is propagated. Otherwise, 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 Before, or, if Before equals No_Element, the moved nodes are
+inserted after the last existing child node of Parent. The parent of the element
+designated by Position is set to Parent.>
+
+@xcode<@b<procedure> Splice_Children (Target          : @b<in out> Tree;
+                           Target_Parent   : @b<in>     Cursor;
+                           Before          : @b<in>     Cursor;
+                           Source          : @b<in out> Tree;
+                           Source_Parent   : @b<in>     Cursor);>
+
+@xindent<If Target_Parent equals No_Element, then Constraint_Error is
+propagated. If Target_Parent does not designate a node in Target, then
+Program_Error is propagated. If Before is not equal to No_Element, and does not
+designate an element in Target, then Program_Error is propagated. If
+Source_Parent equals No_Element, then Constraint_Error is propagated. If
+Source_Parent does not designate a node in Source, then Program_Error is
+propagated. If Before is not equal to No_Element, and Target.Parent (Before) is
+not equal to Target_Parent, then Constraint_Error is propagated.>
+
+@xindent<If Source denotes the same object as Target, then:>
+@xinbull<if Target_Parent equals Source_Parent there is no effect; else>
+@xinbull<if Source_Parent is an ancestor of Target_Parent, then Constraint_Error
+is propagated; else>
+@xinbull<the child elements (and their descendants) of Source_Parent are moved
+to be child elements of Target_Parent. If Target_Parent already has child
+elements then the moved elements are inserted prior to the node designated by
+Before, or, if Before equals No_Element, the moved elements are inserted after
+the last existing child node of Target_Parent. The parent of each moved child
+element is set to Target_Parent.>
+
+@xindent<Otherwise (if Source does not denote the same object as Target), the
+child elements (and their descendants) of Source_Parent are removed from Source
+and moved to Target. The child elements are inserted as children of
+Target_Parent. If Target_Parent already has child elements then the moved
+elements are inserted prior to the node designated by Before, or, if Before
+equals No_Element, the moved elements are inserted after the last existing child
+node of Target_Parent. In each of these cases, the overall count of Target is
+incremented by Subtree_Count (Source_Parent)-1, and overall count of Source is
+decremented by Subtree_Count (Source_Parent)-1.>
+
+@xcode<@b<procedure> Splice_Children (Container       : @b<in out> Tree;
+                           Target_Parent   : @b<in>     Cursor;
+                           Before          : @b<in>     Cursor;
+                           Source_Parent   : @b<in>     Cursor);>
+
+@xindent<If Target_Parent equals No_Element, then Constraint_Error is
+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 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 Source_Parent there is no effect. If Source_Parent is an
+ancestor of Target_Parent, then Constraint_Error is propagated. Otherwise the
+child elements (and their descendants) of Source_Parent are moved to be child
+elements of Target_Parent. If Target_Parent already has child elements then the
+moved elements are inserted prior to the node designated by Before, or, if
+Before equals No_Element, the moved elements are inserted after the last
+existing child node of Target_Parent. The parent of each moved child element is
+set to Target_Parent.>
+
+@xcode<@b<function> Parent (Position : Cursor) @b<return> Cursor;>
+
+@xindent<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.>
+
+@xcode<@b<function> First_Child (Parent : Cursor) @b<return> Cursor;>
+
+@xindent<If Parent is equal to No_Element, then Constraint_Error is propagated.
+Otherwise, First_Child returns a cursor designating the first child node of the
+node designated by Parent; if there is no such node, No_Element is returned.>
+
+@xcode<@b<function> First_Child_Element (Parent : Cursor) @b<return> Element_Type;>
+
+@xindent<Equivalent to Element (First_Child (Parent)).>
+
+@xcode<@b<function> Last_Child (Parent : Cursor) @b<return> Cursor;>
+
+@xindent<If Parent is equal to No_Element, then Constraint_Error is propagated.
+Otherwise, Last_Child returns a cursor designating the last child node of the
+node designated by Parent; if there is no such node, No_Element is returned.>
+
+@xcode<@b<function> Last_Child_Element (Parent : Cursor) @b<return> Element_Type;>
+
+@xindent<Equivalent to Element (Last_Child (Parent)).>
+
+@xcode<@b<function> Next_Sibling (Position : Cursor) @b<return> Cursor;>
+
+@xindent<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 node
+designated by Position.>
+
+@xcode<@b<function> Previous_Sibling (Position : Cursor) @b<return> Cursor;>
+
+@xindent<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
+node designated by Position.>
+
+@xcode<@b<procedure> Next_Sibling (Position : @b<in out> Cursor);>
+
+@xindent<Equivalent to Position := Next_Sibling (Position);>
+
+@xcode<@b<procedure> Previous_Sibling (Position : @b<in out> Cursor);>
+
+@xindent<Equivalent to Position := Previous_Sibling (Position);>
+
+@xcode<@b<procedure> Iterate_Children
+  (Container : @b<in> Tree;
+   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
+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 child node of Parent, starting with the first child node and moving the
+cursor as per the Next_Sibling function.>
+
+@xindent<Program_Error is propagated if Process.@b<all> tampers with the cursors
+of Container. Any exception raised by Process.@b<all> is propagated.>
+
+@xcode<@b<procedure> Reverse_Iterate_Children
+  (Container : @b<in> Tree;
+   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
+child node of Parent, starting with the last child node and moving the cursor as
+per the Previous_Sibling function.>
+
+@xindent<Program_Error is propagated if Process.@b<all> tampers with the cursors of
+Container. Any exception raised by Process.@b<all> is propagated.>
+
+
+@s8<@i<Bounded (Run-Time) Errors>>
+
+It is a bounded error for the actual function associated with a generic formal
+subprogram, when called as part of an operation of this package, to tamper with
+elements of any Tree parameter to the operation. Either Program_Error is raised,
+or the operation works as defined on the value of the Tree either prior to, or
+subsequent to, some or all of the modifications to the Tree.
+
+It is a bounded error to call any subprogram declared in the visible part of
+Containers.Multiway_Trees when the associated container has been finalized. If
+the operation takes Container as an @b<in out> parameter, then it raises
+Constraint_Error or Program_Error. Otherwise, the operation either proceeds as
+it would for an empty container, or it raises Constraint_Error or Program_Error.
+
+@s8<@i<Erroneous Execution>>
+
+A Cursor value is invalid if any of the following have occurred since it was created:
+@xbullet<The tree that contains the element it designates has been finalized;>
+@xbullet<The tree that contains the element it designates has been used as the Source or
+Target of a call to Move;>
+@xbullet<The tree that contains the element it designates has been used as the Target of
+a call to Assign or the target of an @fa<assignment_statement>;>
+@xbullet<The element it designates has been removed from the tree that previously
+contained the element.>
+
+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.
+
+@s8<@i<Implementation Requirements>>
+
+No storage associated with a multiway tree object shall be lost upon assignment
+or scope exit.
+
+The execution of an @fa<assignment_statement> for a tree shall have the effect of
+copying the elements from the source tree object to the target tree object.
+
+@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
+worst-case time complexity of Element, Parent, First_Child, Last_Child,
+Insert_Child with Count=1, and Delete should be O(log N).
+
+Move should not copy elements, and should minimize copying of internal data structures.
+
+If an exception is propagated from a tree operation, no storage should be lost,
+nor any elements removed from a tree unless specified by the operation.
+
+
+!corrigendum A.18.17(0)
+
+@dinsc
+
+The language-defined generic package Containers.Indefinite_Multiway_Trees
+provides a multiway tree with the same operations as the package
+Containers.Multiway_Trees (see A.18.10), with the difference that the generic
+formal Element_Type is indefinite.
+
+@s8<@i<Static Semantics>>
+
+The declaration of the generic library package
+Containers.Indefinite_Multiway_Trees has the same contents and
+semantics as Containers.Multiway_Trees except:
+
+@xbullet<The generic formal Element_Type is indefinite.>
+
+@xbullet<The procedure with the profile:>
+@xcode<     procedure Insert_Child (Container : @b<in out> Tree;
+                             Parent    : @b<in>     Cursor;
+                             Before    : @b<in>     Cursor;
+                             Position  :    @b<out> Cursor;
+                             Count     : @b<in>     Count_Type := 1);>
+@xindent<is omitted.>
+
+@xbullet<The actual Element parameter of access subprogram Process of
+Update_Element may be constrained even if Element_Type is unconstrained.>
+
+!corrigendum A.18.25(0)
+
+@dinsc
+
+The language-defined generic package Containers.Bounded_Multiway_Trees
+provides a private type Tree and a set of operations. It provides the same
+operations as the package Containers.Multiway_Trees (see A.18.10), with the
+difference that the maximum storage is bounded.
+
+@s8<@i<Static Semantics>>
+
+The declaration of the generic library package Containers.Bounded_Multiway_Trees
+has the same contents and semantics as Containers.Multiway_Trees except:
+
+@xbullet<pragma Preelaborate is replaced with pragma Pure.>
+
+@xbullet<The type Tree is declared with a discriminant that specifies the
+capacity (maximum number of elements) as follows:>
+@xcode<     @b<type> Tree (Capacity : Count_Type) @b<is tagged private>;>
+
+@xbullet<The type Tree needs finalization if and only if type
+Element_Type needs finalization.>
+
+@xbullet<The allocation of internal storage includes a check that the
+capacity is not exceeded, and Capacity_Error is raised if this check fails.>
+
+@xbullet<In procedure Assign, if Source length is greater than Target
+capacity, then Capacity_Error is propagated.>
+
+@xbullet<Function Copy is declared as follows:>
+
+@xcode<     @b<function> Copy (Source : Tree;
+                        Capacity : Count_Type := 0) @b<return> Tree;>
+
+@xindent<If Capacity is 0, then the tree capacity is the count of
+Source; if Capacity is equal to or greater than Source.Count,
+the tree capacity equals the value of the Capacity parameter;
+otherwise, the operation propagates Capacity_Error.>
+
+@xbullet<In the five-parameter procedure Splice_Subtree, if Source is
+not the same object as Target, and if the sum of Target.Count
+and Subtree_Count (Position) is greater than Target.Capacity,
+then Splice_Subtree propagates Capacity_Error.>
+
+@xbullet<In the five-parameter procedure Splice_Children, if Source is
+not the same object as Target, and if the sum of Target.Count
+and Subtree_Count (Source_Parent)-1 is greater than Target.Capacity,
+then Splice_Children propagates Capacity_Error.>
+
+@s8<@i<Bounded (Run-Time) Errors>>
+
+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].
+Either Program_Error is raised, or the operation proceeds as defined.
+
+@s8<@i<Implementation Advice>>
+
+Bounded tree objects should be implemented without implicit pointers or
+dynamic allocation.
+
+The implementation advice for procedure Move to minimize copying does not
+apply.
+
+
+
 !ACATS test
 
+ACATS C-Tests are needed to test these packages.
 
 !appendix
 
@@ -2935,9 +3936,9 @@
 
 [Answering some private mail from Matt:]
 
-> Well, I confess to not knowing what "bottom-up tree construction is" 
-> (unless we're talking about a B-tree).  I also assumed that Splice and 
-> Move would be appropriate mechanisms for moving trees and subtrees 
+> Well, I confess to not knowing what "bottom-up tree construction is"
+> (unless we're talking about a B-tree).  I also assumed that Splice and
+> Move would be appropriate mechanisms for moving trees and subtrees
 > across tree containers.
 
 It's the way trees are constructed when using a bottom-up parser - first
@@ -2949,12 +3950,12 @@
 required using them.)
 
 ...
-> > (It seems silly to have to create a special object solely for the 
-> > purpose of making a copy of some nodes, especially bad in a bounded 
+> > (It seems silly to have to create a special object solely for the
+> > purpose of making a copy of some nodes, especially bad in a bounded
 > > container type, where it would cause an extra set of copying.)
-> 
-> Well, that's where we disagree -- creating a separate (tree) object to 
-> hold (sub)trees you intend to splice onto another tree is *exactly* 
+>
+> Well, that's where we disagree -- creating a separate (tree) object to
+> hold (sub)trees you intend to splice onto another tree is *exactly*
 > what you want.
 
 It's way too expensive, especially for bounded forms. And it's not how you
@@ -2962,10 +3963,10 @@
 why should they be different here? We're probably going to have to agree to
 disagree on this one.
 
-> Concern about efficiency of a bounded form is also misplaced. 
->  It's better to optimize the design around the common case, which is 
-> an unbounded form.  We already accept that Move, Splice, etc is going 
-> to require a copy for other bounded forms, so I see no reason to treat 
+> Concern about efficiency of a bounded form is also misplaced.
+>  It's better to optimize the design around the common case, which is
+> an unbounded form.  We already accept that Move, Splice, etc is going
+> to require a copy for other bounded forms, so I see no reason to treat
 > a tree container any differently.
 
 For most (paying) Ada customers, the bounded form is the only one they'll

Questions? Ask the ACAA Technical Agent