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

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

--- ai05s/ai05-0136-1.txt	2009/02/05 05:21:23	1.2
+++ ai05s/ai05-0136-1.txt	2009/05/30 05:13:20	1.3
@@ -1,4 +1,4 @@
-!standard  A.18.18(1)                                09-02-04    AI05-0136-1/02
+!standard  A.18.18(1)                                09-05-28    AI05-0136-1/03
 !class Amendment 09-02-04
 !status work item 09-02-04
 !status received 09-01-27
@@ -18,16 +18,16 @@
 types such as class-wide types.
 
 However, Ada 2005 does not provide any way to create a tree structure out of
-existing containers without requiring memory management. Consider representing a
-multiway tree using only the existing containers. Clearly, the list of child
-nodes of an element can easily be represented as a list container. That list
-would have to be part of the element as inserted in the tree - which of course
-is also the type of the elements in the list. Thus, the container has to appear
-in its own elements; implementing that necesarily includes an 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
+existing containers without requiring explicit memory management. Consider
+representing a multiway tree using only the existing containers. Clearly, the
+list of child nodes of an element can easily be represented as a list container.
+That list would have to be part of the element as inserted in the tree - which
+of course is also the type of the elements in the list. Thus, the container has
+to appear in its own elements; implementing that necesarily includes an
+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.
@@ -44,6 +44,8 @@
 
 !wording
 
+A.18.xx The Package Containers.Multiway_Trees
+
 The language-defined generic package Containers.Multiway_Trees provides private
 types List and Cursor, and a set of operations for each type. A multiway tree
 container is well-suited to represent nested structures.
@@ -56,6 +58,32 @@
 as long as the node is part of the container, even if the node is moved in the
 container.
 
+A *subtree* is a particular node (which *roots the subtree*) and all of its child
+nodes (including all of the children of the child nodes, recursively). A node
+with no parent node is called an *orphan node*. A particular orphan node can be
+designated as the *root node* of the tree. The subtree rooted by the designated
+root node is the *active portion* of the tree; some operations only operate on
+the active portion of the tree.
+
+A node that has no children is called a *leaf node*. The *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 *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
+*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.
+
+[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
@@ -78,10 +106,34 @@
 
    No_Element : constant Cursor;
 
+   No_Parent : constant Cursor := No_Element;
+
+   function Equal_Subtree (Left_Position : Cursor;
+                           Right_Position: Cursor) return Boolean;
+
    function "=" (Left, Right : Tree) return Boolean;
 
    function Is_Empty (Container : Tree) return Boolean;
 
+   function Count (Container : Tree) return Count_Type;
+
+   function Overall_Count (Container : Tree) return Count_Type;
+
+   function Subtree_Count (Container : Tree; Position : Cursor) return Count_Type;
+
+   function Depth (Position : Cursor) return Count_Type;
+
+   function Is_Root (Position : Cursor) return Boolean;
+
+   function Is_Orphan (Position : Cursor) return Boolean;
+
+   function Is_Leaf (Position : Cursor) return Boolean;
+
+   function Root (Container : Tree) return Cursor;
+
+   procedure Set_Root (Container : in out Tree;
+                       Position  : in     Cursor);
+
    procedure Clear (Container : in out Tree);
 
    function Element (Position : Cursor)
@@ -101,33 +153,54 @@
       Process   : not null access procedure
                       (Element : in out Element_Type));
 
+   procedure Assign (Target : in out Tree; Source : Tree);
+
+   function Copy (Source : Tree) return Tree;
+
    procedure Move (Target : in out Tree;
                    Source : in out Tree);
 
    procedure Delete (Container : in out Tree;
                      Position  : in out Cursor);
 
+   procedure Delete_Subtree (Container : in out Tree;
+                             Position  : in out Cursor);
+
+   procedure Swap (Container : in out Tree;
+                   I, J      : in     Cursor);
+
    function Find (Container : Tree;
                   Item      : Element_Type;
                   Position  : Cursor := No_Element)
       return Cursor;
 
-   function Reverse_Find (Container : Tree;
-                          Item      : Element_Type;
-                          Position  : Cursor := No_Element)
+   function Overall_Find (Container : Tree;
+                          Item      : Element_Type)
       return Cursor;
 
+   function Ancestor_Find (Container : Tree;
+                           Item      : Element_Type;
+                           Position  : Cursor)
+      return Cursor;
+
    function Contains (Container : Tree;
                       Item      : Element_Type) return Boolean;
 
+   function Overall_Contains (Container : Tree;
+                              Item      : Element_Type) return Boolean;
+
    function Has_Element (Position : Cursor) return Boolean;
 
    procedure Iterate
      (Container : in Tree;
       Process   : not null access procedure (Position : in Cursor));
 
-   function Child_Length (Container : Tree; Parent : Cursor) return Count_Type;
+   procedure Overall_Iterate
+     (Container : in Tree;
+      Process   : not null access procedure (Position : in Cursor));
 
+   function Child_Count (Container : Tree; Parent : Cursor) return Count_Type;
+
    function Child_Depth (Parent, Child : Cursor) return Count_Type;
 
    procedure Insert_Child (Container : in out Tree;
@@ -158,51 +231,38 @@
                            Parent    : in     Cursor;
                            New_Item  : in     Element_Type;
                            Count     : in     Count_Type := 1);
-
-   procedure Delete_Child (Container : in out Tree;
-                           Parent    : in     Cursor;
-                           Position  : in out Cursor;
-                           Count     : in     Count_Type := 1);
-
-   procedure Delete_First_Child (Container : in out Tree;
-                                 Parent    : in     Cursor;
-                                 Count     : in     Count_Type := 1);
-
-   procedure Delete_Last_Child (Container : in out Tree;
-                                Parent    : in     Cursor;
-                                Count     : in     Count_Type := 1);
-
-   procedure Splice (Target   : in out Tree;
-                     Parent   : in     Cursor;
-                     Before   : in     Cursor;
-                     Source   : in out Tree);
-
-   procedure Splice (Target   : in out Tree;
-                     Parent   : in     Cursor;
-                     Before   : in     Cursor;
-                     Source   : in out Tree;
-                     Position : in out Cursor);
-
-   procedure Splice (Container: in out Tree;
-                     Parent   : in     Cursor;
-                     Before   : in     Cursor;
-                     Position : in     Cursor);
-
-   procedure Splice_Children (Target   : in out Tree;
-                              Parent   : in     Cursor;
-                              Before   : in     Cursor;
-                              Source   : in out Tree);
-
-   procedure Splice_Children (Target   : in out Tree;
-                              Parent   : in     Cursor;
-                              Before   : in     Cursor;
-                              Source   : in out Tree;
-                              Position : in out Cursor);
 
-   procedure Splice_Children (Container: in out Tree;
-                              Parent   : in     Cursor;
-                              Before   : in     Cursor;
-                              Position : in     Cursor);
+   procedure Delete_Child_Subtree (Container : in out Tree;
+                                   Parent    : in     Cursor;
+                                   Position  : in out Cursor;
+                                   Count     : in     Count_Type := 1);
+
+   procedure Splice_Subtree (Target   : in out Tree;
+                             Parent   : in     Cursor;
+                             Before   : in     Cursor;
+                             Source   : in out Tree);
+
+   procedure Splice_Subtree (Target   : in out Tree;
+                             Parent   : in     Cursor;
+                             Before   : in     Cursor;
+                             Source   : in out Tree;
+                             Position : in out Cursor);
+
+   procedure Splice_Subtree (Container: in out Tree;
+                             Parent   : in     Cursor;
+                             Before   : in     Cursor;
+                             Position : in     Cursor);
+
+   procedure Splice_Children (Target          : in out Tree;
+                              Target_Parent   : in     Cursor;
+                              Before          : in     Cursor;
+                              Source          : in out Tree;
+                              Source_Parent   : in     Cursor);
+
+   procedure Splice_Children (Container       : in out Tree;
+                              Target_Parent   : in     Cursor;
+                              Before          : in     Cursor;
+                              Source_Parent   : in     Cursor);
 
    function Parent (Position : Cursor) return Cursor;
 
@@ -224,12 +284,12 @@
 
    procedure Previous_Sibling (Position : in out Cursor);
 
-   procedure Iterate_Child
+   procedure Iterate_Children
      (Container : in Tree;
       Parent    : in     Cursor;
       Process   : not null access procedure (Position : in Cursor));
 
-   procedure Reverse_Iterate_Child
+   procedure Reverse_Iterate_Children
      (Container : in Tree;
       Parent    : in     Cursor;
       Process   : not null access procedure (Position : in Cursor));
@@ -238,577 +298,2473 @@
    ... -- not specified by the language
 end Ada.Containers.Multiway_Trees;
 
-[** Rest of the wording TBD. See the discussion for a discussion of the model
-and some notes. **]
+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
+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 List needs finalization (see 7.6).
+
+Empty_Tree represents the empty Tree object. It contains no nodes (Count (Empty_Tree)
+returns 0). 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.
+
+No_Parent represents a cursor that represents the parent of an orphan 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.
+
+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 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
+
+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 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 finalizes T; or
+
+* it calls Assign with T as the Target parameter; or
+
+* it calls the Move procedure with T as a parameter. 
+
+AARM Reason: Swap copies elements rather than reordering them, so it doesn't tamper
+with cursors.
+
+A subprogram is said to tamper with elements of a tree object T if:
+
+* it tampers with cursors of T; or
+
+* it replaces one or more elements of T, that is, it calls the Replace_Element or Swap
+  procedures with T as a parameter.
+
+AARM Reason: Complete replacement of an element can cause its memory to be deallocated
+while another operation is holding onto a reference to it. That can't be allowed.
+However, a simple modification of (part of) an element is not a problem, so Update_Element
+does not cause a problem. 
+
+   function Equal_Subtree (Left_Position : Cursor;
+                           Right_Position: Cursor) return Boolean;
+      If Left_Position or Right_Position equals No_Element, raises Constraint_Error.
+      If the number of child nodes of the element designated by Left_Position is
+      different than the number of child modes of the element designated by
+      Right_Position, 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 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 call
+      returns False, the function returns False; otherwise it returns True. Any
+      exception raised during the evaluation of element equality is propagated.
+
+      [Editor's note: I needed this to define "=" on Trees. We don't support comparing
+      No_Element here, as that doesn't represent a "particular node" and doing so would
+      require passing two container parameters as well. If you need want to compare the
+      entire active tree of a container to some other subtree, pass Root.]
+
+      AARM Ramification: Left_Position and Right_Position do not need to be from the same
+      container.
+
+      AARM Implementation Note: This wording describes the canonical semantics. However,
+      the order and number of calls on the formal equality function is unspecified for
+      all of the operations that use it in this package, so an implementation can call
+      it as many or as few times as it needs to get the correct answer. Similarly, a global
+      rule (see the introduction of Annex A) says that language-defined routines are not
+      affected by overriding of other language-defined routines. This means that no
+      reasonable program can tell how many times Equal_Subtrees is called, and thus an
+      implementation can call it as many or as few times as it needs to get the correct
+      answer. Specifically, there is no requirement to call the formal equality or
+      Equal_Subtrees additional times once the answer has been determined. 
 
-[An indefinite version would be provided with similar differences as the
-existing indefinite containers.]
+   function "=" (Left, Right : Tree) return Boolean;
 
-!discussion
+      If Left and Right denote the same tree object, then the function returns True. If
+      Child_Count (Left, No_Element) does not equal Child_Count (Right, No_Element), then
+      the function returns False. If Left has a designated root element and Right does not,
+      or vice versa, the function returns False. Otherwise, it calls Equal_Subtree with a cursor
+      designating each orphan element of Left and a cursor designating the corresponding
+      orphan element of Right. 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.
+
+      AARM Discussion: We test that the number of orphan elements is the same in each container.
+      We also check that either both or neither of the trees has a designated root.
+      Otherwise, we recursively test that all of the orphan subtrees are equivalent. We
+      don't need to explicitly check the contents of the roots, since a designated root
+      (if present) is always the first orphan node.
+
+      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;
+      If there is no designated root element of Container, Count returns 0; otherwise
+      Count returns the number of elements in the active subtree of Container. 
+
+   function Overall_Count (Container : Tree) return Count_Type;
+      Overall_Count returns the number of elements in the entire tree Container,
+      including orphan elements and their children.
+
+   function Subtree_Count (Container : Tree; Position : Cursor) return Count_Type;
+      If Position equals No_Parent, and there is no designated root element,
+      Subtree_Count returns 0; otherwise Subtree_Count returns the number
+      of elements in the subtree rooted by the designated root element of Container.
+      If Position is not No_Parent, Subtree_Count returns the number of elements in
+      the subtree that is rooted by Position. 
 
-The author has found that almost all of his large projects contained a least one
-multiway tree, as it is an ideal structure for representing nesting. Flatter
-structures such as the existing containers do not handle nesting well.
+   function Is_Empty (Container : Tree) return Boolean;
 
-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".)
+      Equivalent to Overall_Count (Container) = 0.
 
-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
-by the Ada Containers library) is probably more appropriate.
+      AARM Discussion: We use Overall_Count to ensure that all elements are counted;
+      Count (Container) only counts the active subtree. This routine, of course,
+      should be implemented a O(1), while Overall_Count is probably O(N).
 
-Model:
+   function Depth (Position : Cursor) return Count_Type;
 
-The 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.
+      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). 
 
-Having "_Child" as part of the names also opens up the possibility of operations
-not having the "_Child" suffix. These would naturally operate on the entire tree.
-We're taken advantage of this to define operations like Find and Iterate over the
-entire tree.
+      [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 usefully default
+      the Parent parameter in Child_Depth because it is first; putting the parameters
+      in the other order would be inconsistent with all other routines (where the
+      parent comes first) and thus would be confusing in positional calls.]
 
-Note that the root of the tree is also a list of elements. (Thus the tree is
-multirooted as well as multiway.) We considered allowing only a single root
-node, but it seemed inconsistent for no important reason, and moreover, allowing
-additional roots allows bottom-up tree creation where subtrees are stashed in
-the root until their parent is created (at which time Slice_Child would be used
-to make it a subtree of the appropriate parent).
+   function Is_Root (Position : Cursor) return Boolean;
 
-Note that AI05-0001-1 proposes to add some new routines to all of the existing
-containers; these weren't included in this proposal but presumably would be
-included. Similarly, we expect that a bounded form would be provided if
-AI05-0001-1 is adopted.
+      Is_Root returns True if the Position designates the element that is designated
+      as the root of the tree; and returns False otherwise.
 
-For all of the subprograms that take a Parent parameter, if the parameter is
-No_Element, the node is inserted at the root of the tree. This is consistent
-with the meaning of the Before parameter in the Insert routines in the existing
-list containers.
+   function Is_Orphan (Position : Cursor) return Boolean;
 
-Notes on specific subprograms:
+      Is_Orphan returns True if Position designates an element that does not
+      have a parent node; and returns False otherwise.
 
-Operations that were dropped are: Swap and Swap_List; Reverse_Elements; and the
-sorting operations. These could have been defined, but they seem strange operating
-on a single list of children; they seem more like operations for an entire
-container (where they make no sense).
+      AARM Ramification: Is_Orphan returns False if passed No_Element, as
+      No_Element does not designate an element.
 
-Delete is provided to delete an arbitrary node from the tree. We don't provide a
-Count parameter on that routine, because it is not obvious what is being counted
-(sibling nodes only? child nodes only? both sibling and child nodes?)
+   function Is_Leaf (Position : Cursor) return Boolean;
 
-Iterate walks the entire tree starting with the root list of nodes. Each node in
-every child list is visited in order; after each node is visited, the child list
-of that of that node are visited. This is done recursively.
+      Is_Leaf returns True if Position designates an element that does not have
+      any child nodes; and returns False otherwise.
 
-Child_Length returns the number of Children nodes of Parent.
+      AARM Ramification: Is_Leaf returns False if passed No_Element, as
+      No_Element does not designate an element.
 
-Child_Depth returns the number of ancestor nodes of Child, up to (but not
-including Parent). If Parent is No_Element, returns the number of ancestor nodes
-of Child. Raises Program_Error if Parent is not No_Element, and is not an
-ancestor of Child.
+   function Root (Container : Tree) return Cursor;
 
-For Insert_Child, if the Before parameter is not a child of Parent,
-Program_Error is propagated.
+      Root returns a cursor that designates the element that is the designated root
+      element of Container; it returns No_Element if there is no designated root
+      element of Container.
 
-Delete_Child is similar to Delete, but (a) the node to delete must be a child of
-the Parent; (b) a Count is provided to delete several children.
+   procedure Set_Root (Container : in out Tree;
+                       Position  : in     Cursor);
 
-We didn't add "_Child" to Splice, as it usually will be splicing entire
-subtrees. As with Insert_Child, if Before is not a child of Parent,
-Program_Error is propagated. Splice moves the node(s) and all child nodes of the
-node to the new position in the (new) tree. Splice_Children moves only the child
-nodes of the position to the new position.
+      If Position equals No_Element, then Container is set to have no designated
+      root element. If Is_Orphan (Position) is False, Constraint_Error is propagated.
+      Otherwise, the element designated by Position is set as the designated root
+      element designated of Container. The newly designated element becomes the
+      first orphan element of Container.
 
-Selector function Parent returns the parent of the node represented by the given
-cursor.
+      AARM Ramification: If Root (Container) /= No_Element, then
+      First_Child (Container, No_Parent) = Root (Container).
 
-Next and Previous were renamed Next_Sibling and Previous_Sibling to make the
-meaning clearer (they work just like the list versions).
+   procedure Clear (Container : in out Tree);
 
-Note that we left the Container parameter in routines like First_Child, because
-the Parent parameter can be No_Element to represent the root, and we need to
-know where to look for that root. An alternative design would be to have a
-separate set of routines for accessing the root, but that would clutter the
-package and complicate use (a lot of insertion code would have to explicitly
-check to see if it is inserting at the root: a scourge of hand-written code that
-we don't want to duplicate in the containers!).
+      Removes all the elements from Container.
 
-Iterate_Child and Iterate_Reverse_Child just iterate over the child nodes of
-Parent (and no others).
+   function Element (Position : Cursor)
+      return Element_Type;
 
+      If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+      Element returns the element designated by Position.
 
-Further ideas:
+   procedure Replace_Element (Container : in out Tree;
+                              Position  : in     Cursor;
+                              New_Item  : in     Element_Type);
 
-* 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.
+      If Position equals No_Element, 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 to the element designated
+      by Position.
 
-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
-example below.) This would look something like:
+   procedure Query_Element
+     (Position : in Cursor;
+      Process  : not null access procedure (Element : in Element_Type));
 
-   procedure Iterate
-     (Container : in Tree;
-      Process_Before_Children : access procedure (Position : in Cursor);
-      Process_After_Children : access procedure (Position : in Cursor));
+      If Position equals No_Element, then Constraint_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.
 
-(Note that these subprograms are allowed to be null, so that if one or the other
-isn't needed, it can be skipped.)
+   procedure Update_Element
+     (Container : in out Tree;
+      Position  : in     Cursor;
+      Process   : not null access procedure
+                      (Element : in out Element_Type));
 
-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).
+      If Position equals No_Element, 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 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.
 
+      If Element_Type is unconstrained and definite, then the actual Element parameter of
+      Process.all shall be unconstrained.
 
-Advantages of the multiway tree container over hand-created trees:
+   procedure Assign (Target : in out Tree; Source : Tree);
 
-(1) Complete memory management, including for indefinite elements.
+      If Target denotes the same object as Source, the operation has no
+      effect. Otherwise, it clears Target, and then each element of Source is
+      assigned to a corresponding element in Target.
 
-(2) Avoidance of linking mistakes during operations like insertions and
-    deletions.
+      AARM To Be Honest: The "corresponding element in Target" has a parent element
+      that corresponds to the parent element of the Source element, and has child
+      elements that correspond to the child elements of the Source element.
 
-(3) More safety than hand-built structures -- tampering checks and possible
-    dangling pointer (cursor) detection.
+   function Copy (Source : Tree) return Tree;
 
-(4) Completely linked (doubly-linked sibling lists; complete parent and child
-    pointers), so walking in any direction in the tree is always O(1).
+      Returns a tree with the same structure as Source and whose elements are initialized
+      from the corresponding elements of Source.
 
-(5) Built-in iterators.
+   procedure Move (Target : in out Tree;
+                   Source : in out Tree);
 
-(6) Container users get streaming for free; streaming of a tree is fairly hard
-    to do correctly.
+      If Target denotes the same object as Source, then Move has no effect. Otherwise, Move
+      first calls Clear (Target). Then, the nodes in Source are moved to Target (in the same
+      positions). After Move completes, Overall_Count(Target) is the number of nodes originally
+      in Source, and Overall_Count(Source) is 0.
 
-Disadvantages of the multiway tree container:
+   procedure Delete (Container : in out Tree;
+                     Position  : in out Cursor);
 
-(1) Not as familiar as some other containers; may not be used as much for that
-    reason. (Authors can help aleviate this situation somewhat.)
+      If Position equals No_Element, 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 (from Container) the element designated by Position. Finally,
+      Position is set to No_Element.
+
+      AARM Ramification: The check on Position checks that the cursor does not belong to some
+      other Container. This check implies that a reference to the container is included in the
+      cursor value. This wording is not meant to require detection of dangling cursors; such
+      cursors are defined to be invalid, which means that execution is erroneous, and any result
+      is allowed (including not raising an exception). 
+
+   procedure Delete_Subtree (Container : in out Tree;
+                             Position  : in out Cursor);
+
+      If Position equals No_Element, 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 element
+      designated by Position along with all of the descendant elements of that element.
+      Finally, Position is set to No_Element.
+
+   procedure Swap (Container : in out Tree;
+                   I, J      : in     Cursor);
+
+      If either I or J is No_Element, 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.
+
+      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.
 
-(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
-    commonly needed as a tree.
+      AARM To be honest: The implementation is not required to actually copy the elements if it
+      can do the swap some other way. But it is allowed to copy the elements if needed. 
 
-(3) More memory management options are available for hand-created code. But that
-    also provides a lot more opportunities for bugs.
+   function Find (Container : Tree;
+                  Item      : Element_Type;
+                  Position  : Cursor := No_Element)
+      return Cursor;
 
+      If Position is not No_Element, and does not designate an element 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 designated root element if Position
+      equals No_Element. 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 does not check any siblings of the element designated by Position.
+
+      [Editor's note: This would naturally be called "Find_Subtree", but that is a misleading
+      name, as what this does is Find *in* subtree (not finding a subtree). So we stick with
+      plain "Find".]
 
-!examples
+   function Overall_Find (Container : Tree;
+                          Item      : Element_Type)
+      return Cursor;
 
-(1) Representing HTML: (XML is similar)
+      Overall_Find searches all of the elements of Container for an element equal to Item (using
+      the generic formal equality operator). The search starts at the first orphan element. The
+      search checks each orphan subtree (including the active subtree, if any) in a depth-first order.
+      If no equal element is found, then Overall_Find returns No_Element. Otherwise, it returns
+      a cursor designating the first equal element encountered.
+
+   function Ancestor_Find (Container : Tree;
+                           Item      : Element_Type;
+                           Position  : Cursor)
+      return Cursor;
 
-   type Root_HTML_Element is tagged private;
-   function Init_Element return Root_HTML_Element;
-   procedure Output_Prefix (Element : Root_Element_Type);
-   procedure Output_Suffix (Element : Root_Element_Type);
+      If Position is No_Element, then Constraint_Error is propagated. If Position does not designate
+      an element 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 returns No_Element.
+      Otherwise, it returns a cursor designating the first equal element encountered.
 
-   type Text is Root_HTML_Element with record
-         The_Text : Unbounded_String;
-   end record;
-   procedure Output_Prefix (Element : Bold_Element_Type); -- Writes The_Text
-   procedure Output_Suffix (Element : Bold_Element_Type); -- Writes nothing.
+   function Contains (Container : Tree;
+                      Item      : Element_Type) return Boolean;
 
-   type Bold_HTML_Element is new Root_HTML_Element with null record;
-   procedure Output_Prefix (Element : Bold_Element_Type); -- Writes <B>
-   procedure Output_Suffix (Element : Bold_Element_Type); -- Writes </B>
+      Equivalent to Find (Container, Item) /= No_Element.
 
-   -- Similar overridings of Output_Prefix and Output_Suffix for each type;
-   -- we won't show them here.
-   type Italic_HTML_Element is new Root_HTML_Element with null record;
-   type Div_HTML_Element is new Root_HTML_Element with record
-         Class : Class_Name;
-         Style : Style_String;
-         -- other attributes.
-      end record;
-   type Span_HTML_Element is new Root_HTML_Element with record
-         Class : Class_Name;
-         Style : Style_String;
-         -- other attributes.
-      end record;
-   type Header_HTML_Element is new Root_HTML_Element with null record;
-   type Body_HTML_Element is new Root_HTML_Element with null record;
-   -- and so on.
+   function Overall_Contains (Container : Tree;
+                              Item      : Element_Type) return Boolean;
 
-   package HTML_Tree is new Ada.Containers.Multiway_Trees (Root_HTML_Element'Class);
+      Equivalent to Overall_Find (Container, Item) /= No_Element.
 
-   -- The following HTML code:
-   <html><body>
-   <div class="Text-Header">Sample HTML</div>
-   <div class="Text-Body">This is normal text; <b>this is bold text</b>; and
-   <i>this is italic text</i></div>
-   </body>
-   </html>
+   function Has_Element (Position : Cursor) return Boolean;
 
-   -- would be represented as the following operations:
-   Sample : HTML_Tree.Tree;
-   Header, HTML_Body, Paragraph, Working: HTML_Tree.Cursor;
+      Returns True if Position designates an element, and returns False otherwise.
 
-   HTML_Tree.Insert_Child (Sample, Parent => HTML_Tree.No_Element, Position => Header,
-     Before => HTML_Tree.No_Element,
-     New_Element => Header_HTML_Element'(Init_Element with null record));
-   HTML_Tree.Insert_Child (Sample, Parent => Header, Position => HTML_Body,
-     Before => HTML_Tree.No_Element,
-     New_Element => Body_HTML_Element'(Init_Element with null record));
-   HTML_Tree.Insert_Child (Sample, Parent => HTML_Body, Position => Paragraph,
-     Before => HTML_Tree.No_Element,
-     New_Element => Div_HTML_Element'(Init_Element with Class => "Text-Header", Style => ""));
-   HTML_Tree.Append_Child (Sample, Parent => Paragraph,
-     New_Element => Text'(Init_Element with The_Text => "Sample HTML"));
-   HTML_Tree.Insert_Child (Sample, Parent => HTML_Body, Position => Paragraph,
-     Before => HTML_Tree.No_Element,
-     New_Element => Div_HTML_Element'(Init_Element with Class => "Text-Body", Style => ""));
-   HTML_Tree.Append_Child (Sample, Parent => Paragraph,
-     New_Element => Text'(Init_Element with The_Text => "This is normal text; "));
-   HTML_Tree.Insert_Child (Sample, Parent => Paragraph, Position => Working,
-     Before => HTML_Tree.No_Element,
-     New_Element => Bold_HTML_Element'(Init_Element with null record));
-   HTML_Tree.Append_Child (Sample, Parent => Working,
-     New_Element => Text'(Init_Element with The_Text => "this is bold text"));
-   HTML_Tree.Insert_Child (Sample, Parent => Paragraph,
-     New_Element => Text'(Init_Element with The_Text => "; and "));
-   HTML_Tree.Insert_Child (Sample, Parent => Paragraph, Position => Working,
-     Before => HTML_Tree.No_Element,
-     New_Element => Italic_HTML_Element'(Init_Element with null record));
-   HTML_Tree.Append_Child (Sample, Parent => Working,
-     New_Element => Text'(Init_Element with The_Text => "this is italic text"));
+      AARM To be honest: This function may 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). 
 
-Outputing the original HTML could be accomplished as follows:
+   procedure Iterate
+     (Container : in Tree;
+      Process   : not null access procedure (Position : in Cursor));
 
-   procedure Output_Document (Document : in HTML_Tree.Tree) is
-      procedure Output_Node (Node : HTML_Tree.Cursor) is
-         Node_Element : Root_HTML_Element'Class := HTML_Tree.Element (Node);
-      begin
-         Output_Prefix (Node_Element); -- Dispatches.
-         Iterate_Children (Document, Parent => Node, Process => Output_Node'Access);
-         Output_Suffix (Node_Element); -- Dispatches.
-      end Output_Node;
-   begin
-      Output_Node (HTML_Tree.First (Parent => No_Element));
-   end Output_Document;
+      Iterate calls Process.all with a cursor that designates each node in the active portion
+      of Container, starting with the designated root node 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: If there is no designated root node, Iterate does nothing;
+      Process.all will not be called at all.
+
+      AARM Implementation Note: The purpose of the tamper with cursors check is to prevent
+      erroneous execution from the Position parameter of Process.all becoming invalid. This
+      check takes place when the operations that tamper with the cursors of the container are
+      called. The check cannot be made later (say in the body of Iterate), because that could
+      cause the Position cursor to be invalid and potentially cause execution to become erroneous
+      -- defeating the purpose of the check.
 
-(2) Windows in a GUI.
+      See Iterate for vectors (A.18.2) for a suggested implementation of the check. 
+      End AARM Implementation Note.
 
-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
-Microsoft Windows, controls like buttons, check boxes, and edit controls are
-child windows.
+   procedure Overall_Iterate
+     (Container : in Tree;
+      Process   : not null access procedure (Position : in Cursor));
 
-A program that manipulates a GUI in some way could represent the set of windows
-in an application as a multiway tree container, putting the burden of memory
-management on the container. [Author's note: sure would have liked that for the
-Claw GUI builder...]
+      Iterate calls Process.all with a cursor that designates each node in the Container
+      of Container, starting with the first orphan node and proceeding in a depth-first
+      order, visiting each orphan subtree (including the active subtree, if any) in order.
+      Program_Error is propagated if Process.all tampers with the cursors of Container.
+      Any exception raised by Process.all is propagated.
+
+   function Child_Count (Container : Tree; Parent : Cursor) return Count_Type;
+
+      If Parent is not equal to No_Parent, and does not designate an element in Container, then
+      Program_Error is propagated. If Parent is equal to No_Parent, then Child_Count
+      returns the number of orphan elements in Container (including the designated root
+      element, if any). Otherwise, Child_Count returns the number of child elements of
+      the element designated by Parent.
 
-(3) E-mail messages.
+   function Child_Depth (Parent, Child : Cursor) return Count_Type;
 
-The MIME RFCs that define how attachments are structured in an e-mail message
-define that a message is divided into a series of sections, each with their own
-headers. One possible content of an e-mail message section is an attached e-mail
-message -- which has its own set of headers and sections. Thus, an e-mail parser
-needs to be able to structure the message so that it can look into and process
-these nested messages. (That's especially important for anti-spam and
-anti-malware processing -- it would not do to allow a bad message through simply
-because of nesting.)
+      If Child is equal to No_Element, then Constraint_Error is propagated. If Child does not
+      designate and element in Container, then Program_Error is propagated. If Parent is not
+      equal to No_Parent, and does not designate an element in Container, then Program_Error
+      is propagated. If Parent is equal to No_Parent, Child_Depth returns the number of
+      ancestor nodes of Child (including Child itself). 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.
 
-An e-mail processor could be structured to represent each section as one node in
-a multiway tree. The top-level sections would be root nodes, but any nested
-messages would be child nodes of their parent. Here again, we would put the
-memory management burden on the container, rather than the programmer of the
-processor.
+   procedure Insert_Child (Container : in out Tree;
+                           Parent    : in     Cursor;
+                           Before    : in     Cursor;
+                           New_Item  : in     Element_Type;
+                           Count     : in     Count_Type := 1);
 
-(4) Compiler symboltable.
+      If Parent is not equal to No_Parent, and does not designate an element 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 Before is not equal to
+      No_Element, and Container.Parent (Before) is not equal to Parent, then Constraint_Error
+      is raised. If Parent is equal to No_Parent, Insert_Child inserts Count orphan copies of
+      New_Item prior to the (orphan) element designated by Before. If Before equals No_Element,
+      the new elements are inserted after the last orphan node (if any). Otherwise, Insert_Child
+      inserts Count copies of New_Item 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). Any exception raised during allocation of internal storage is
+      propagated, and Container is not modified.
 
-The symboltable in a compiler is also a multiway tree. Entities declared in a
-single declarative part are a list (including order). 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.
+   procedure Insert_Child (Container : in out Tree;
+                           Parent    : in     Cursor;
+                           Before    : in     Cursor;
+                           New_Item  : in     Element_Type;
+                           Position  :    out Cursor;
+                           Count     : in     Count_Type := 1);
 
-If a compiler needed to save a symboltable 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.]
+      If Parent is not equal to No_Parent, and does not designate an element 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 Before is not equal to
+      No_Element, and Container.Parent (Before) is not equal to Parent, then Constraint_Error
+      is raised. If Parent is equal to No_Parent, Insert_Child inserts Count orphan copies of
+      New_Item prior to the (orphan) element designated by Before. If Before equals No_Element,
+      the new elements are inserted after the last orphan node (if any). Otherwise, Insert_Child
+      inserts Count copies of New_Item 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). Position designated the first newly-inserted element. Any
+      exception raised during allocation of internal storage is propagated, and Container is
+      not modified.
 
-A debugging symboltable dump could be done as a simple iterator:
+   procedure Insert_Child (Container : in out Tree;
+                           Parent    : in     Cursor;
+                           Before    : in     Cursor;
+                           Position  :    out Cursor;
+                           Count     : in     Count_Type := 1);
 
-   procedure Dump_Symboltable (Table : Symbol.Tree) is
-     procedure Process (Node : Symbol_Cursor) is
-     begin
-        Put ((1 .. Child_Depth(Node)*2) => ' '); -- Indent based on the depth.
-        Dump_Symbol (Element (Node));
-     end Process;
-   begin
-     Iterate (Tree, Process'Access);
-   end Process;
+      If Parent is not equal to No_Parent, and does not designate an element 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 Before is not equal to
+      No_Element, and Container.Parent (Before) is not equal to Parent, then Constraint_Error
+      is raised. If Parent is equal to No_Parent, Insert_Child inserts Count orphan new elements
+      prior to the (orphan) element designated by Before. If Before equals No_Element,
+      the new elements are inserted after the last orphan node (if any). Otherwise, Insert_Child
+      inserts Count new elements 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 new elements are initialized by default (see 3.3.1). Position
+      designated the first newly-inserted element. 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;
+                            New_Item  : in     Element_Type;
+                            Count     : in     Count_Type := 1);
 
-!ACATS test
+      Equivalent to Insert_Child (Container, Parent, First_Child (Container, Parent), New_Item, Count).
 
+   procedure Append_Child (Container : in out Tree;
+                           Parent    : in     Cursor;
+                           New_Item  : in     Element_Type;
+                           Count     : in     Count_Type := 1);
 
-!appendix
+      Equivalent to Insert_Child (Container, Parent, Last_Child (Container, Parent), New_Item, Count).
 
-From: Randy Brukardt
-Date: Tuesday, January 27, 2009  12:39 AM
+   procedure Delete_Child_Subtree (Container : in out Tree;
+                                   Parent    : in     Cursor;
+                                   Position  : in out Cursor;
+                                   Count     : in     Count_Type := 1);
+
+      If Position equals No_Element, then Constraint_Error is propagated. If Position does not
+      designate an element in Container, then Program_Error is propagated. If Parent is not equal
+      to No_Parent, and 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 raised. 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 difference of this routine is providing of a Count. This 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 => Container.First_Child (My_Parent),
+      Count => 10000); will delete all of the child nodes.
+
+      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.]
+
+   procedure Splice_Subtree (Target   : in out Tree;
+                             Parent   : in     Cursor;
+                             Before   : in     Cursor;
+                             Source   : in out Tree);
+
+      If Parent is not equal to No_Parent, and does not designate an element 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 Before is not equal to
+      No_Element, and Target.Parent (Before) is not equal to Parent, then Constraint_Error
+      is raised. Otherwise, if Source denotes the same object as Target, or if there is no active
+      subtree in Source, the operation has no effect. Otherwise, Splice_Subtree reorders elements
+      such that the active subtree is removed from Source and moved to Target. The subtree is
+      inserted as a child of Parent (or, if Parent is equal to No_Parent, as an orphan subtree)
+      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), or if Parent is equal to No_Parent,
+      after the last orphan node (if any). The overall count of Target is incremented by
+      Count (Source), and Source is set to have no designated root element.
+
+      AARM Ramification: If Source contains non-root orphan nodes, Overall_Count (Source) may
+      not be zero after this operation, as they are not moved. However, the sum of the
+      overall counts for the source and target before Splice_Subtree will be the same as
+      the sum of the overall counts afterwards.
+
+   procedure Splice_Subtree (Target   : in out Tree;
+                             Parent   : in     Cursor;
+                             Before   : in     Cursor;
+                             Source   : in out Tree;
+                             Position : in out Cursor);
+
+      If Position is equal to No_Element then Constraint_Error is propagated. If Parent is not equal
+      to No_Parent, and does not designate an element 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 Position does not equal No_Element, and 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 Parent, then Constraint_Error
+      is raised. If Source denotes the same object as Target, then there is no effect if
+      Position equals Before, 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) or if Parent is equal to No_Parent, after the last orphan node. In
+      each of these cases, Position and the overall count of Target are unchanged, and the parent
+      of the element designated by Position is set to Parent. 
+
+      Otherwise, the subtree designated by Position is removed from Source and moved to Target.
+      The subtree is inserted as a child of Parent (or, if Parent is equal to No_Parent, as an
+      orphan subtree) 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), or if Parent is equal
+      to No_Parent, after the last orphan node (if any). In each of these cases, the overall
+      count of Target is incremented by Subtree_Count (Position), and overall count of Source is
+      decremented by Subtree_Count (Position), Position is updated to represent an element
+      in Target.
+
+      AARM Ramification: If Source is the same as Target, and Position = Before, or
+      Next_Sibling(Position) = Before, Splice has no effect, as the subtree does not have to move
+      to meet the postcondition. 
+
+   procedure Splice_Subtree (Container: in out Tree;
+                             Parent   : in     Cursor;
+                             Before   : in     Cursor;
+                             Position : in     Cursor);
+
+      If Position is equal to No_Element then Constraint_Error is propagated. If Parent is not equal
+      to No_Parent, and does not designate an element 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 Position does not equal 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 raised. If Position equals Before there is no effect. 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) or if Parent is equal to No_Parent,
+      after the last orphan node. The parent of the element designated by Position is set to Parent. 
+
+   procedure Splice_Children (Target          : in out Tree;
+                              Target_Parent   : in     Cursor;
+                              Before          : in     Cursor;
+                              Source          : in out Tree;
+                              Source_Parent   : in     Cursor);
+
+      If Target_Parent is not equal to No_Parent, and does not designate an element 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 is not equal
+      to No_Parent, and does not designate an element 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 raised.
+
+      If Source denotes the same object as Target, then:
+        * if Target_Parent equals Source_Parent there is no effect; else
+        * if Source_Parent is equal to No_Parent or 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) or if Target_Parent is equal to No_Parent, after
+          the last orphan node. 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 an descendant node, as
+      the descendant node will be part of one of the subtrees being moved.
+
+      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. If Source_Parent
+      is equal to No_Parent, all of the orphan elements of Source are moved.
+      The child (or orphan) elements are inserted as children of Target_Parent (or, if Target_Parent
+      is equal to No_Parent, as an orphan subtree) prior to the element designated by Before. If
+      Before equals No_Element, the child (or orphan) elements are inserted after the last child
+      node of Target_Parent (if any), or if Parent is equal to No_Parent, after the last orphan
+      node (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.
+
+      AARM Ramification: The node designated by Source_Parent is not moved, thus we never need to
+      update Source_Parent.
+
+      Move (Target, Source) could be written Splice_Children (Target, No_Parent, No_Element,
+      Source, No_Parent);
+      End AARM Ramification.
+
+   procedure Splice_Children (Container       : in out Tree;
+                              Target_Parent   : in     Cursor;
+                              Before          : in     Cursor;
+                              Source_Parent   : in     Cursor);
+
+      If Target_Parent is not equal to No_Parent, and does not designate an element 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 is not equal
+      to No_Parent, and does not designate an element 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 raised. If Target_Parent equals Source_Parent there is no effect.
+      If Source_Parent is equal to No_Parent or 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) or if
+      Target_Parent is equal to No_Parent, after the last orphan node. The parent of each moved child
+      element is set to Target_Parent.
 
-Back in November, Tucker and I had the following exchange:
+   function Parent (Position : Cursor) return Cursor;
 
-Tucker:
+      If Position is equal to No_Element then Constraint_Error is propagated. If the element designated
+      by Position is an orphan element, No_Parent is returned. Otherwise, a cursor designating the
+      parent element of the element designated by Position is returned.
 
-Tree structures are painful to work with without access types. Tagged types,
-access types, and heterogeneous trees are natural bedfellows.  In this era of
-XML everything, heterogeneous trees are not just for compiler writers anymore.
+   function First_Child (Container : Tree; Parent : Cursor) return Cursor;
 
-Randy:
-I surely agree that tagged types and heterogeneous trees are natural bedfellows.
-I'm not so certain about the access types, though.
+      If Parent is not equal to No_Parent, and does not designate an element in Container, then
+      Program_Error is propagated. If Parent is equal to No_Parent, First_Child returns a cursor
+      designating the first orphan element in Container; if there is no such element, No_Element is
+      returned. Otherwise, First_Child returns a cursor designating the first child element of the
+      element designated by Parent; if ther is no such element, No_Element is returned.
 
-I thought that the Set containers were supposed to cover a significant portion
-of the need for trees. If they don't, then I think we ought to discuss what
-containers will. (Let's work on tomorrow's ways to program, not yesterday's.)
+   function First_Child_Element (Container : Tree; Parent : Cursor)
+      return Element_Type;
 
-Tucker:
-You can use a tree to implement a set, but you can't really use a set to
-implement a tree.  You could implement a tree using a map, but that's pretty
-painful.  If I want to represent something that is tree like (e.g. an abstract
-syntax tree, an XML file, a CAD drawing, etc.) I really need pointers of some
-sort.
+      Equivalent to Element (First_Child (Container, Parent)).
 
-Randy (today):
-Having thought about this a lot more, I tend to agree that you can't use any of
-the existing containers to create a tree structure. But that means giving up the
-benefits of containers (storage management is done for you; correctness - links
-get made correctly; streaming is provided) in favor of doing things the same old
-way (with the same old set of bugs). In the past, Tucker has contended that it
-would be harder to use such a container than to write it yourself. I originally
-bought that argument, but I'm now more dubious, since memory management
-(especially of indefinite types) is hard to get right.
+   function Last_Child (Container : Tree; Parent : Cursor) return Cursor;
 
-So I decided to work out a definition of a multiway tree container. Having done
-that, and written some example code for an HTML processor, I've pretty decided
-that Tucker's position here is a load of MBE(*). But decide for yourself - I've
-attached trial ballon #4.
+      If Parent is not equal to No_Parent, and does not designate an element in Container, then
+      Program_Error is propagated. If Parent is equal to No_Parent, Last_Child returns a cursor
+      designating the last orphan element in Container; if there is no such element, No_Element is
+      returned. Otherwise, Last_Child returns a cursor designating the last child element of the
+      element designated by Parent; if there is no such element, No_Element is returned.
 
-(*) MBE => Male Bovine Excrement. :-)
+   function Last_Child_Element (Container : Tree; Parent : Cursor)
+      return Element_Type;
 
-[Attached was version /01 of this AI.]
+      Equivalent to Element (Last_Child (Container, Parent)).
 
-****************************************************************
+   function Next_Sibling (Position : Cursor) return Cursor;
 
-From: Randy Brukardt
-Date: Thursday, January 29, 2009  9:10 PM
+      If Position equals No_Element or designates the last child element 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.
 
-A couple of additions to my proposal for a Multiway_Tree container:
+   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 returns a cursor that designates
+      the predecessor (with the same parent) of the element designated by Position.
 
-Add after the definition of No_Element:
+   procedure Next_Sibling (Position : in out Cursor);
 
-Root : Cursor renames No_Element;
+      Equivalent to Position := Next_Sibling (Position);
 
-This will make adding to the root more readable (it doesn't change any
-semantics).
+   procedure Previous_Sibling (Position : in out Cursor);
 
-For instance, in the example:
+      Equivalent to Position := Previous_Sibling (Position);
 
-   HTML_Tree.Insert_Child (Sample, Parent => HTML_Tree.Root, Position => Header,
-      New_Element => Header_HTML_Element'(Init_Element with null record));
+   procedure Iterate_Children
+     (Container : in Tree;
+      Parent    : in     Cursor;
+      Process   : not null access procedure (Position : in Cursor));
 
-----
+     If Parent is not equal to No_Parent, and does not designate an element in Container, then
+     Program_Error is propagated. 
 
-The other two forms of Slice also should have Splice_Children variants:
+     If Parent is equal to No_Parent, Iterate_Children calls Process.all with a cursor that
+     designates each orphan node in Container, starting with the first orphan node and moving
+     the cursor as per the Next_Sibling function. Otherwise, Iterate_Children calls Process.all
+     with a cursor that designates each child node of Parent, starting with the first child node
+     and moving the cursor as per the Next_Sibling function. 
 
-    procedure Splice_Children (Target   : in out Tree;
-                               Parent   : in     Cursor;
-                               Before   : in     Cursor;
-                               Source   : in out Tree);
+     Program_Error is propagated if Process.all tampers with the cursors of Container. Any
+     exception raised by Process.all is propagated.
 
-    procedure Splice_Children (Target   : in out Tree;
-                               Parent   : in     Cursor;
-                               Before   : in     Cursor;
-                               Source   : in out Tree;
-                               Position : in out Cursor);
+   procedure Reverse_Iterate_Children
+     (Container : in Tree;
+      Parent    : in     Cursor;
+      Process   : not null access procedure (Position : in Cursor));
 
-Obviously, these operations should be consistent: it would be odd to find some
-possibilities missing for no obvious reason.
+     If Parent is not equal to No_Parent, and does not designate an element in Container, then
+     Program_Error is propagated. 
 
-These could come up quite a bit in practice. For instance, imagine an HTML
-editor based on the example code in the proposal. If you were to remove bold
-facing (for example), you would have to move the children of the bold node to up
-to the position of the bold node, then delete the bold node. That would use the
-original Splice_Children routine. If you have multiple HTML documents to operate
-on, it would make sense to move parts from one to another (cut-and-paste, for
-instance), and that could need moving the children.
+     If Parent is equal to No_Parent, Iterate_Children calls Process.all with a cursor that
+     designates each orphan node in Container, starting with the last orphan node and moving
+     the cursor as per the Previous_Sibling function. Otherwise, Iterate_Children calls Process.all
+     with a cursor that designates each child node of Parent, starting with the last child node
+     and moving the cursor as per the Previous_Sibling function. 
 
-****************************************************************
+     Program_Error is propagated if Process.all tampers with the cursors of Container. Any
+     exception raised by Process.all is propagated.
 
-From: Niklas Holsti
-Date: Friday, January 30, 2009  2:30 AM
+Bounded (Run-Time) Errors
 
-> Root : Cursor renames No_Element;
->
-> This will make adding to the root more readable (it doesn't change any
-> semantics).
+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.
 
-I find the name "Root" here quite confusing. More below.
+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 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. 
 
-> For instance, in the example:
->
->    HTML_Tree.Insert_Child (
- >        Sample,
- >        Parent => HTML_Tree.Root,
- >        Position => Header,
->        New_Element => Header_HTML_Element'(
- >           Init_Element with null record));
+Erroneous Execution
 
-If I read the above, without remembering the suggested definition of "Root" as
-"No_Element" and the special meaning of Parent => No_Element, it clearly seems
-to mean that the new child is inserted below the root, not as the (or a) new
-root.
+A Cursor value is invalid if any of the following have occurred since it was created:
+* The tree that contains the element it designates has been finalized;
+* The tree that contains the element it designates has been used as the Source or Target of a call to Move;
+* A subtree that contains the element it designated has been moved to a different tree by a call to
+  Splice_Children or Splice_Subtree; or 
+* The element it designates has been deleted.
 
-It is quite likely that application code that builds a (single-rooted) tree will
-have a variable called Root, and the nearly identical call
+[Editor's note: We have to include moving a subtree to a different container as a cause of invalidating
+a cursor. It appears that the case of a full list splice is missing from the list of A.18.3(153-156),
+as it should invalidate cursors that point into the source list.]
 
- >    HTML_Tree.Insert_Child (
- >        Sample,
- >        Parent => Root,   -- CHANGED
- >        Position => Header,
- >        New_Element => Header_HTML_Element'(
- >           Init_Element with null record));
+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.
 
-then has a very different effect. I think that defining Multiway_Tree.Root in
-this proposed way invites mistakes, and I find the original form "Parent =>
-No_Element" clearer.
+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.
 
-Another comment: In the call to Insert_Child in the above example, and in fact
-in all Insert_Child calls in the HTML example in the proposal, there is no
-actual for the "Before" parameter, which is required in all three forms of
-Insert_Child as defined in the proposal. I assume that "Before => No_Element" is
-intended.
+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 encouraged to check for as many of these cases as
+possible and raise Program_Error if detected. 
 
-I do welcome this Multiway_Tree suggestion. I think it fills a gap and will be
-useful.
+Implementation Requirements
 
-****************************************************************
+No storage associated with a multiway tree object shall be lost upon assignment or scope exit.
 
-From: Randy Brukardt
-Date: Friday, January 30, 2009  9:34 PM
+The execution of an assignment_statement for a list shall have the effect of copying the elements from the
+source tree object to the target tree object.
 
-...
-> > For instance, in the example:
-> >
-> >    HTML_Tree.Insert_Child (
->  >        Sample,
->  >        Parent => HTML_Tree.Root,
->  >        Position => Header,
-> >        New_Element => Header_HTML_Element'(
->  >           Init_Element with null record));
->
-> If I read the above, without remembering the suggested definition of
-> "Root" as "No_Element" and the special meaning of Parent =>
-> No_Element, it clearly seems to mean that the new child is inserted
-> below the root, not as the (or a) new root.
+AARM Implementation Note: An assignment of a Tree is a “deep” copy; that is the elements are copied as well
+as the data structures. We say “effect of” in order to allow the implementation to avoid copying elements
+immediately if it wishes. For instance, an implementation that avoided copying until one of the containers
+is modified would be allowed.
 
-Humm, I see your point. Perhaps it would be better named "As_Root" or something
-like that? I don't think that the use of Parent => No_Element is particularly
-understandable.
+Implementation Advice
 
-Originally, I had planned a second set of functions for accessing the root:
+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).
 
-    HTML_Tree.Insert_Root (
-        Sample,
-        Position => Header,
-        New_Element => Header_HTML_Element'(
-           Init_Element with null record));
+AARM Reason: We do not mean to overly constrain implementation strategies here. However, it is important for
+portability that the performance of large containers has roughly the same factors on different implementations.
+If a program is moved to an implementation that takes O(N) time to access elements, that program could be
+unusable when the trees are large. We allow O(log N) access because the proportionality constant and
+caching effects are likely to be larger than the log factor, and we don't want to discourage innovative
+implementations. 
 
-But a lot of the time, you would end up making the code conditional on whether
-you're inserting at the root or in a child, which doesn't seem helpful.
+Move should not copy elements, and should minimize copying of internal data structures. 
 
-So I was looking for a way to make it clearer that you are inserting the root of
-the tree.
+AARM Implementation Note: Usually that can be accomplished simply by moving the pointer(s) to the internal
+data structures from the Source container to the Target container. 
 
-...
-> Another comment: In the call to Insert_Child in the above example, and
-> in fact in all Insert_Child calls in the HTML example in the proposal,
-> there is no actual for the "Before"
-> parameter, which is required in all three forms of Insert_Child as
+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. 
+
+AARM Reason: This is important so that programs can recover from errors. But we 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
+
+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 formal Element_Type
+is indefinite. 
+
+Static Semantics
+
+The declaration of the generic library package Containers.Indefinite_Multiway_Trees has the same contents as
+Containers.Multiway_Trees except:
+
+* The generic formal Element_Type is indefinite.
+* The procedure with the profile: 
+   procedure Insert_Child (Container : in out Tree;
+                           Parent    : in     Cursor;
+                           Before    : in     Cursor;
+                           Position  :    out Cursor;
+                           Count     : in     Count_Type := 1);
+   is omitted.
+
+AARM Discussion: This procedure is omitted because there is no way to create a 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.
+
+The actual Element parameter of access subprogram Process of Update_Element may be constrained even if
+Element_Type is unconstrained. 
+
+[** TBD** We need to define a bounded form similarly to the ones in AI05-0001-1. Copy the linked list
+to the extent possible.]
+
+!discussion
+
+The author has found that almost all of his large projects contained a least one
+multiway tree, as it is an ideal structure for representing nesting. Flatter
+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".)
+
+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
+by the Ada Containers library) is probably more appropriate.
+
+Model:
+
+The 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.
+
+Having "_Child" as part of the names also opens up the possibility of operations
+not having the "_Child" suffix. These would naturally operate on the entire tree.
+We're taken advantage of this to define operations like Find and Iterate over the
+entire tree.
+
+We've added the suffix "_Subtree" to a few operations to make it clear that they
+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). Nodes which
+do not have parents are called "orphan elements" (or possibly "orphan nodes", if
+we need that terminology in the actual wording. These also form a list of elements,
+and the normal "child" operations can be used on the list of orphan elements. One
+of the orphan elements can be designated the "root" of the tree. Some operations
+operate on the tree that starts at the root, but ignore other orphan elements
+and their children.
+
+Orphan elements allow bottom-up tree creation where subtrees are stashed as orphan
+elements until their parent is created (at which time Slice_Children or Slice_Subtree
+would be used to make it a subtree of the appropriate parent). Without this capability,
+bottom up tree creation would require the creation of many container objects (each
+with overhead) and potentially would require copying of the subtrees and elements
+from one container to another with each step (this is certainly the case for a
+bounded tree container).
+
+We considered making the tree multirooted rather than designating a particular
+root node. Some reviewers considered this too weird, in addition, designating a
+particular root node allows elements to be in the container without being in the
+primary tree, which can be useful in some circumstances.
+
+Most operations that act on the entire tree container only act on the active portion
+of the tree (that is the subtree rooted by the designated root element); those
+usually have a counter-part that has the prefix "Overall_" that act on the entire
+container including all orphan subtrees.
+
+Note that we added the Assign and Copy routines here as proposed in AI05-0001-1.
+If we decide not to do that for the other containers, they should be removed
+here as well.
+
+Similarly, we define a bounded form here; in the unlikely event that we decide not
+to adopt AI05-0001-1, it should be removed here.
+
+For all of the subprograms that take a Parent parameter, if the parameter is
+No_Element, the node is inserted at the root of the tree. This is consistent
+with the meaning of the Before parameter in the Insert routines in the existing
+list containers.
+
+Operations that were dropped are:
+  * Delete_First and Delete_Last: These seem unlikely to occur in the context of
+    a tree (as opposed to a sequence like a list), and they're very easy to
+    write yourself if necessary. [Editor's Note: Dropping these are all Matt's
+    idea. :-) Since the names aren't the same anyway (they'd be Delete_First_Child
+    and Delete_Last_Child) the consistency argument doesn't seem to hold much water.]
+  * Swap_Links: Swapping within a single sibling list doesn't seem very useful.
+    Swapping such that the parents get changed on the nodes can be a nightmare to
+    describe and implement correctly: consider swapping two nodes where one is the
+    parent of the other, and additional children are also involved. Exactly which
+    elements end up where?? We do provide Swap, which just swaps the elements and
+    leaves the nodes alone; that doesn't have definitional issues.
+  * Reverse_Find: This is a strange operation, which would be hard to define
+    sensibly. Rather, we provide Ancestor_Find, which has a clear definition.
+  * Reverse_Elements: This seems like a strange operation operating on a single
+    list of children. It makes no sense on the entire container. So we don't
+    provide it.
+  * Sorting operations: It seems weird to sort just a single list of child
+    elements. And it also doesn't make any sense on the entire container.
+
+
+Note that we left the Container parameter in routines like First_Child, because
+the Parent parameter can be No_Element to represent no parent (an orphan element,
+including the root), and we need to know in which container to look for that
+orphan element. An alternative design would be to have a separate set of routines
+for accessing orphan elements (including the designated root), but that would
+clutter the package and complicate use (a lot of insertion code would have to
+explicitly check to see if it is inserting at the root: a scourge of hand-written
+code that we don't want to duplicate in the containers!).
+
+
+More on the orphan/root model:
+
+The inclusion of orphan elements also allows an implementation of the XML DOM
+to be built directly using one of these tree containers; the XML DOM also
+includes the capability of inserting elements without including them in
+the main tree (we call it the active tree).
+
+The model as defined means that T.First_Child (No_Parent) [where T is a tree
+container] returns the designated root node (if any). If there is no
+designated root node, it returns the first orphan node. Next_Sibling (T.Root)
+returns a non-root orphan node (if any).
+
+This model is slightly annoying, in that T.Last_Child (No_Parent) is unlikely
+to return the designated root node (unless there are no other orphans in the
+container).
+
+We considered an alternative model where both T.First_Child (No_Parent) and
+T.Last_Child (No_Parent) always returns the designated root node (or No_Element
+if there is no root node). In that model, the root node is not an orphan node,
+and the orphan nodes have their own separate list. For that model, we would
+need additional functions First_Orphan and Last_Orphan to be able to access
+the list of non-root orphans. (The list *has* to exist in order to implement
+operations like "=" and Iterate_All; it would be weird not to provide access
+to it.) We also would require a full set of _Sibling operations, because
+T.First_Child (Parent (Some_Element)) would not always return the child list
+that contains Some_Element. Essentially, any code that could operate on an
+orphan subtree and needed to look at the parent would have to test for the
+possibility that the node is an orphan and handle the case of no parent
+specially. This could be very annoying in programs that do bottom-up tree
+construction.
+
+With either model, (individual) operations directly on elements or that
+involve the relationships between elements do not care whether they are operating
+on an orphan subtree or on
+
+
+With the model we selected, most operations do not care if they are working on
+a node that belongs to the active subtree or to some other node. But many
+operations on the entire container only operate on the active subtree.
+
+
+Further ideas:
+
+* Should we have a function to get the maximum depth of the tree?
+
+* Matt thought that we should add some additional sibling handling routines.
+  In particular, he suggested Sibling_Count, Iterate_Siblings, and First_Sibling,
+  among others. These would occasionally be convinient, but are easily written
+  using the existing routines:
+  Sibling_Count (Tree, Position) = Child_Count (Tree, Parent(Position))
+  First_Sibling (Tree, Position) = First_Child (Tree, Parent(Position))
+  and so on.
+
+  These could be added by defining them using the above equivalences, if desired.
+
+
+* 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
+example below.) This would look something like:
+
+   procedure Iterate
+     (Container : in Tree;
+      Process_Before_Children : access procedure (Position : in Cursor);
+      Process_After_Children : access procedure (Position : in Cursor));
+
+(Note that these subprograms are allowed to be null, so that if one or the other
+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).
+
+
+Advantages of the multiway tree container over hand-created trees:
+
+(1) Complete memory management, including for indefinite elements.
+
+(2) Avoidance of linking mistakes during operations like insertions and
+    deletions.
+
+(3) More safety than hand-built structures -- tampering checks and possible
+    dangling pointer (cursor) detection.
+
+(4) Completely linked (doubly-linked sibling lists; complete parent and child
+    pointers), so walking in any direction in the tree is always O(1).
+
+(5) Built-in iterators.
+
+(6) Container users get streaming for free; streaming of a tree is fairly hard
+    to do correctly.
+
+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.)
+
+(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
+    commonly needed as a tree.
+
+(3) More memory management options are available for hand-created code. But that
+    also provides a lot more opportunities for bugs.
+
+
+!examples
+
+(1) Representing HTML: (XML is similar)
+
+   type Root_HTML_Element is tagged private;
+   function Init_Element return Root_HTML_Element;
+   procedure Output_Prefix (Element : Root_Element_Type);
+   procedure Output_Suffix (Element : Root_Element_Type);
+
+   type Text is Root_HTML_Element with record
+         The_Text : Unbounded_String;
+   end record;
+   procedure Output_Prefix (Element : Bold_Element_Type); -- Writes The_Text
+   procedure Output_Suffix (Element : Bold_Element_Type); -- Writes nothing.
+
+   type Bold_HTML_Element is new Root_HTML_Element with null record;
+   procedure Output_Prefix (Element : Bold_Element_Type); -- Writes <B>
+   procedure Output_Suffix (Element : Bold_Element_Type); -- Writes </B>
+
+   -- Similar overridings of Output_Prefix and Output_Suffix for each type;
+   -- we won't show them here.
+   type Italic_HTML_Element is new Root_HTML_Element with null record;
+   type Div_HTML_Element is new Root_HTML_Element with record
+         Class : Class_Name;
+         Style : Style_String;
+         -- other attributes.
+      end record;
+   type Span_HTML_Element is new Root_HTML_Element with record
+         Class : Class_Name;
+         Style : Style_String;
+         -- other attributes.
+      end record;
+   type Header_HTML_Element is new Root_HTML_Element with null record;
+   type Body_HTML_Element is new Root_HTML_Element with null record;
+   -- and so on.
+
+   package HTML_Tree is new Ada.Containers.Multiway_Trees (Root_HTML_Element'Class);
+
+   -- The following HTML code:
+   <html><body>
+   <div class="Text-Header">Sample HTML</div>
+   <div class="Text-Body">This is normal text; <b>this is bold text</b>; and
+   <i>this is italic text</i></div>
+   </body>
+   </html>
+
+   -- would be represented as the following operations:
+   Sample : HTML_Tree.Tree;
+   Header, HTML_Body, Paragraph, Working: HTML_Tree.Cursor;
+
+   HTML_Tree.Insert_Child (Sample, Parent => HTML_Tree.No_Element, Position => Header,
+     Before => HTML_Tree.No_Element,
+     New_Element => Header_HTML_Element'(Init_Element with null record));
+   HTML_Tree.Insert_Child (Sample, Parent => Header, Position => HTML_Body,
+     Before => HTML_Tree.No_Element,
+     New_Element => Body_HTML_Element'(Init_Element with null record));
+   HTML_Tree.Insert_Child (Sample, Parent => HTML_Body, Position => Paragraph,
+     Before => HTML_Tree.No_Element,
+     New_Element => Div_HTML_Element'(Init_Element with Class => "Text-Header", Style => ""));
+   HTML_Tree.Append_Child (Sample, Parent => Paragraph,
+     New_Element => Text'(Init_Element with The_Text => "Sample HTML"));
+   HTML_Tree.Insert_Child (Sample, Parent => HTML_Body, Position => Paragraph,
+     Before => HTML_Tree.No_Element,
+     New_Element => Div_HTML_Element'(Init_Element with Class => "Text-Body", Style => ""));
+   HTML_Tree.Append_Child (Sample, Parent => Paragraph,
+     New_Element => Text'(Init_Element with The_Text => "This is normal text; "));
+   HTML_Tree.Insert_Child (Sample, Parent => Paragraph, Position => Working,
+     Before => HTML_Tree.No_Element,
+     New_Element => Bold_HTML_Element'(Init_Element with null record));
+   HTML_Tree.Append_Child (Sample, Parent => Working,
+     New_Element => Text'(Init_Element with The_Text => "this is bold text"));
+   HTML_Tree.Insert_Child (Sample, Parent => Paragraph,
+     New_Element => Text'(Init_Element with The_Text => "; and "));
+   HTML_Tree.Insert_Child (Sample, Parent => Paragraph, Position => Working,
+     Before => HTML_Tree.No_Element,
+     New_Element => Italic_HTML_Element'(Init_Element with null record));
+   HTML_Tree.Append_Child (Sample, Parent => Working,
+     New_Element => Text'(Init_Element with The_Text => "this is italic text"));
+
+Outputing the original HTML could be accomplished as follows:
+
+   procedure Output_Document (Document : in HTML_Tree.Tree) is
+      procedure Output_Node (Node : HTML_Tree.Cursor) is
+         Node_Element : Root_HTML_Element'Class := HTML_Tree.Element (Node);
+      begin
+         Output_Prefix (Node_Element); -- Dispatches.
+         Iterate_Children (Document, Parent => Node, Process => Output_Node'Access);
+         Output_Suffix (Node_Element); -- Dispatches.
+      end Output_Node;
+   begin
+      Output_Node (HTML_Tree.First (Parent => No_Element));
+   end Output_Document;
+
+(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
+Microsoft Windows, controls like buttons, check boxes, and edit controls are
+child windows.
+
+A program that manipulates a GUI in some way could represent the set of windows
+in an application as a multiway tree container, putting the burden of memory
+management on the container. [Author's note: sure would have liked that for the
+Claw GUI builder...]
+
+(3) E-mail messages.
+
+The MIME RFCs that define how attachments are structured in an e-mail message
+define that a message is divided into a series of sections, each with their own
+headers. One possible content of an e-mail message section is an attached e-mail
+message -- which has its own set of headers and sections. Thus, an e-mail parser
+needs to be able to structure the message so that it can look into and process
+these nested messages. (That's especially important for anti-spam and
+anti-malware processing -- it would not do to allow a bad message through simply
+because of nesting.)
+
+An e-mail processor could be structured to represent each section as one node in
+a multiway tree. The top-level sections would be root nodes, but any nested
+messages would be child nodes of their parent. Here again, we would put the
+memory management burden on the container, rather than the programmer of the
+processor.
+
+(4) Compiler symboltable.
+
+The symboltable 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
+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:
+
+   procedure Dump_Symboltable (Table : Symbol.Tree) is
+     procedure Process (Node : Symbol_Cursor) is
+     begin
+        Put ((1 .. Child_Depth(Node)*2) => ' '); -- Indent based on the depth.
+        Dump_Symbol (Element (Node));
+     end Process;
+   begin
+     Iterate (Tree, Process'Access);
+   end Process;
+
+
+!ACATS test
+
+
+!appendix
+
+From: Randy Brukardt
+Date: Tuesday, January 27, 2009  12:39 AM
+
+Back in November, Tucker and I had the following exchange:
+
+Tucker:
+
+Tree structures are painful to work with without access types. Tagged types,
+access types, and heterogeneous trees are natural bedfellows.  In this era of
+XML everything, heterogeneous trees are not just for compiler writers anymore.
+
+Randy:
+I surely agree that tagged types and heterogeneous trees are natural bedfellows.
+I'm not so certain about the access types, though.
+
+I thought that the Set containers were supposed to cover a significant portion
+of the need for trees. If they don't, then I think we ought to discuss what
+containers will. (Let's work on tomorrow's ways to program, not yesterday's.)
+
+Tucker:
+You can use a tree to implement a set, but you can't really use a set to
+implement a tree.  You could implement a tree using a map, but that's pretty
+painful.  If I want to represent something that is tree like (e.g. an abstract
+syntax tree, an XML file, a CAD drawing, etc.) I really need pointers of some
+sort.
+
+Randy (today):
+Having thought about this a lot more, I tend to agree that you can't use any of
+the existing containers to create a tree structure. But that means giving up the
+benefits of containers (storage management is done for you; correctness - links
+get made correctly; streaming is provided) in favor of doing things the same old
+way (with the same old set of bugs). In the past, Tucker has contended that it
+would be harder to use such a container than to write it yourself. I originally
+bought that argument, but I'm now more dubious, since memory management
+(especially of indefinite types) is hard to get right.
+
+So I decided to work out a definition of a multiway tree container. Having done
+that, and written some example code for an HTML processor, I've pretty decided
+that Tucker's position here is a load of MBE(*). But decide for yourself - I've
+attached trial ballon #4.
+
+(*) MBE => Male Bovine Excrement. :-)
+
+[Attached was version /01 of this AI.]
+
+****************************************************************
+
+From: Randy Brukardt
+Date: Thursday, January 29, 2009  9:10 PM
+
+A couple of additions to my proposal for a Multiway_Tree container:
+
+----
+
+Add after the definition of No_Element:
+
+Root : Cursor renames No_Element;
+
+This will make adding to the root more readable (it doesn't change any
+semantics).
+
+For instance, in the example:
+
+   HTML_Tree.Insert_Child (Sample, Parent => HTML_Tree.Root, Position => Header,
+      New_Element => Header_HTML_Element'(Init_Element with null record));
+
+----
+
+The other two forms of Slice also should have Splice_Children variants:
+
+    procedure Splice_Children (Target   : in out Tree;
+                               Parent   : in     Cursor;
+                               Before   : in     Cursor;
+                               Source   : in out Tree);
+
+    procedure Splice_Children (Target   : in out Tree;
+                               Parent   : in     Cursor;
+                               Before   : in     Cursor;
+                               Source   : in out Tree;
+                               Position : in out Cursor);
+
+Obviously, these operations should be consistent: it would be odd to find some
+possibilities missing for no obvious reason.
+
+These could come up quite a bit in practice. For instance, imagine an HTML
+editor based on the example code in the proposal. If you were to remove bold
+facing (for example), you would have to move the children of the bold node to up
+to the position of the bold node, then delete the bold node. That would use the
+original Splice_Children routine. If you have multiple HTML documents to operate
+on, it would make sense to move parts from one to another (cut-and-paste, for
+instance), and that could need moving the children.
+
+****************************************************************
+
+From: Niklas Holsti
+Date: Friday, January 30, 2009  2:30 AM
+
+> Root : Cursor renames No_Element;
+>
+> This will make adding to the root more readable (it doesn't change any
+> semantics).
+
+I find the name "Root" here quite confusing. More below.
+
+> For instance, in the example:
+>
+>    HTML_Tree.Insert_Child (
+ >        Sample,
+ >        Parent => HTML_Tree.Root,
+ >        Position => Header,
+>        New_Element => Header_HTML_Element'(
+ >           Init_Element with null record));
+
+If I read the above, without remembering the suggested definition of "Root" as
+"No_Element" and the special meaning of Parent => No_Element, it clearly seems
+to mean that the new child is inserted below the root, not as the (or a) new
+root.
+
+It is quite likely that application code that builds a (single-rooted) tree will
+have a variable called Root, and the nearly identical call
+
+ >    HTML_Tree.Insert_Child (
+ >        Sample,
+ >        Parent => Root,   -- CHANGED
+ >        Position => Header,
+ >        New_Element => Header_HTML_Element'(
+ >           Init_Element with null record));
+
+then has a very different effect. I think that defining Multiway_Tree.Root in
+this proposed way invites mistakes, and I find the original form "Parent =>
+No_Element" clearer.
+
+Another comment: In the call to Insert_Child in the above example, and in fact
+in all Insert_Child calls in the HTML example in the proposal, there is no
+actual for the "Before" parameter, which is required in all three forms of
+Insert_Child as defined in the proposal. I assume that "Before => No_Element" is
+intended.
+
+I do welcome this Multiway_Tree suggestion. I think it fills a gap and will be
+useful.
+
+****************************************************************
+
+From: Randy Brukardt
+Date: Friday, January 30, 2009  9:34 PM
+
+...
+> > For instance, in the example:
+> >
+> >    HTML_Tree.Insert_Child (
+>  >        Sample,
+>  >        Parent => HTML_Tree.Root,
+>  >        Position => Header,
+> >        New_Element => Header_HTML_Element'(
+>  >           Init_Element with null record));
+>
+> If I read the above, without remembering the suggested definition of
+> "Root" as "No_Element" and the special meaning of Parent =>
+> No_Element, it clearly seems to mean that the new child is inserted
+> below the root, not as the (or a) new root.
+
+Humm, I see your point. Perhaps it would be better named "As_Root" or something
+like that? I don't think that the use of Parent => No_Element is particularly
+understandable.
+
+Originally, I had planned a second set of functions for accessing the root:
+
+    HTML_Tree.Insert_Root (
+        Sample,
+        Position => Header,
+        New_Element => Header_HTML_Element'(
+           Init_Element with null record));
+
+But a lot of the time, you would end up making the code conditional on whether
+you're inserting at the root or in a child, which doesn't seem helpful.
+
+So I was looking for a way to make it clearer that you are inserting the root of
+the tree.
+
+...
+> Another comment: In the call to Insert_Child in the above example, and
+> in fact in all Insert_Child calls in the HTML example in the proposal,
+> there is no actual for the "Before"
+> parameter, which is required in all three forms of Insert_Child as
 > defined in the proposal. I assume that "Before => No_Element" is
 > intended.
+
+Yes, it is. I had really intended to use Append_Child, but since that doesn't
+return the position of the inserted element, it can't be used when it is
+intended to insert things on children.
+
+> I do welcome this Multiway_Tree suggestion. I think it fills a gap and
+> will be useful.
+
+Thanks, good to know I'm not alone on this one.
+
+****************************************************************
+
+From: Niklas Holsti
+Date: Saturday, January 31, 2009  3:17 AM
+
+> Humm, I see your point. Perhaps it would be better named "As_Root" or
+> something like that?
+
+I also thought about "As_Root", and that would be OK in a positional call:
+Insert_Child (Sample, As_Root, ...). The named form, "Parent => As_Root", is
+better than "Parent => Root", but I'm still not happy with it.
+
+> I don't think that the use of Parent => No_Element is particularly
+> understandable.
+
+I do. If you insert a node in a tree and specify that it shall have no parent
+node, obviously (to me) the node becomes a root.
+
+I would not object to defining "As_Root : Cursor renames No_Element", but I
+don't think it is very beneficial. Logically one would then expect also
+definitions like
+
+    As_Last : Cursor renames No_Element;
+
+for use as the Before parameter in Insert operations, but again I prefer "Before
+=> No_Element" to "Before => As_Last". It is again obvious (to me) that
+inserting an element in a list with the specification that it shall be before no
+other element means that the element is appended as the new last element in the
+list.
+
+> Originally, I had planned a second set of functions for accessing the root:
+>
+>     HTML_Tree.Insert_Root (
+>         Sample,
+>         Position => Header,
+>         New_Element => Header_HTML_Element'(
+>            Init_Element with null record));
+>
+> But a lot of the time, you would end up making the code conditional on
+> whether you're inserting at the root or in a child, which doesn't seem
+> helpful.
+
+I agree. I think the "Parent => No_Element" mechanism is a good solution.
+Perhaps it could be augmented by defining some root-specific operations, such as
+Insert_Root, analogously with the operations Prepend and Append and defined as
+equivalent to Insert_Child (.. Parent => No_Element ...). These could be used to
+increase clarity when it is statically known that the operation is on a root.
+
+To avoid cluttering the main package with these root-specific operations, why
+not define a child package, say Multiway_Trees.Roots, with operations such as
+Multiway_Trees.Roots.Insert and so on.
+
+****************************************************************
+
+From: Jean-Pierre Rosen
+Date: Saturday, January 31, 2009  7:38 PM
+
+> Humm, I see your point. Perhaps it would be better named "As_Root" or
+> something like that? I don't think that the use of Parent =>
+> No_Element is particularly understandable.
+
+Well, anybody using a tree should know that the only node without a parent is
+the root, so I doesn't seem illogical to say that you want to insert at the root
+by saying that you want to insert at the place that has no parent.
+
+Not a big deal anyway.
+
+****************************************************************
+
+From: Randy Brukardt
+Date: Thursday, May 28, 2009  10:45 PM
+
+[Replying to Matt's comments of April 6th, all gven below.]
+
+> I reviewed the AI for the multiway tree container.  My comments are
+> bracketed with "[MJH]" and "[END MJH]" pairs, and immediately follow
+> the normative text to which they refer.
+
+Note that I marked my comments on your comments with [RLB] and [End RLB] because
+I couldn't figure out a sane way to "quote" the entire thing. And please, whgen
+replying just quote the parts you are replying to and delete the rest, else no
+one will be able to figure out what is going on. Better yet, wait for my next
+version before commenting (it'll be done tomorrow, I think). - Randy.
+
+---
+
+!wording
+
+A multiway tree container object manages a tree of internal 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). 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.
+
+[MJH]
+If Swap and Splice are included, then that last sentence could say:
+ "...even if the node is moved in the container, or moved to another  container."
+[END MJH]
+[RLB]
+That isn't true for the existing containers, so I don't see why it would be
+here. For instance, in Lists, you get a *new* cursor if you splice nodes from
+one container into a different one. That makes sense, since the Cursor includes
+an indication of (usually an access to) the actual container. Besides, this
+wording was borrowed directly from the List container (A.18.3(2/2)). So I think
+this wording is correct.
+[END RLB]
+
+Static Semantics
+
+The generic library package Containers.Multiway_Trees has the following
+declaration:
+
+generic
+   type Element_Type is private;
+   with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Multiway_Trees is
+   pragma Preelaborate(Multiway_Trees);
+   pragma Remote_Types(Multiway_Trees);
+
+   type Tree is tagged private;
+   pragma Preelaborable_Initialization(Tree);
+
+   type Cursor is private;
+   pragma Preelaborable_Initialization(Cursor);
+
+   Empty_Tree : constant Tree;
+
+   No_Element : constant Cursor;
+
+   function "=" (Left, Right : Tree) return Boolean;
+
+   function Is_Empty (Container : Tree) return Boolean;
+
+[MJH]
+I don't see a length function here.  I would do this:
+
+   function Length
+     (Container : Tree;
+      Position  : Cursor := No_Element) return Count_Type;
+
+With the understanding that Length has O(n) time complexity, but that Is_Empty
+guarantees O(1) time complexity.
+
+Position = No_Element means count from the root of the tree; otherwise count
+from the subtree whose root is Position.
+
+You could always break these out as separate functions:
+
+   function Length (Container : Tree) return Count_Type;
+   function Length (Position  : Cursor) return Count_Type;
+[END MJH]
+[RLB]
+I didn't put one in because it isn't clear what "Length" you are talking about.
+Whenever that happened, I added a prefix to make it clear (which is why there is
+a Child_Length). Indeed, the function(s) you describe here is not "Length" at
+all; they're more like "Count". It seems useful, so I added this pair of
+functions. Note that we really need three functions: one to count all of the
+elements in the container, one to count all of the elements from the root (not
+including unattached subtrees), and one for other subtrees. We can't use your
+second function above for counting from the root, because No_Element doesn't
+contain a container indication. We could follow the model of Child_Length for
+that purpose, however.
+
+So I ended up with
+   function Count (Container : Tree) return Count_Type;
+   function Subtree_Count (Container : Tree; Position : Cursor) return Count_Type;
+
+You're welcome to complain in Brest. ;-) [END RLB]
+
+   procedure Clear (Container : in out Tree);
+
+   function Element (Position : Cursor)
+      return Element_Type;
+
+[MJH]
+
+Here and elsewhere we should include this function:
+
+   generic
+      type Item_Type (<>) is limited private;
+      with function Get_Item (Element : Element_Type) return Item_Type;
+   function Generic_Item (Position : Cursor) return Item_Type;
+
+Without this function, it's awkward to return just a component of an element,
+especially if the component has an indefinite subtype.  For example:
+
+   subtype Name_Length is Natural range 0 .. 80;
+
+   type Employee_Type (Length : Name_Length := 0) is record
+      Name : String (1 .. Length);
+      ...
+   end record;
+
+It would be nice to be able to say:
+
+   Name : constant String := Get_Name (Employee_Cursor);
+
+To implement Get_Name using function Element is awkward:
+
+  function Get_Name (C : Cursor) return String is
+     Result : String (1 .. Name_Length'Last);
+     Length : Name_Length;
+
+     procedure Process (E : Employee_Type) is
+     begin
+        Length := E.Length;
+	Result (1 .. Length) := E.Name;
+     end Process;
+
+  begin
+     Query_Element (C, Process'Access);
+     return Result (1 .. Length);
+  end Get_Name;
+
+Now consider the alternative:
+
+   function Get_Name (E : Employee_Type) return String is
+   begin
+      return E.Name;
+   end;
+
+   function Get_Name is new Generic_Item (String, Get_Name);
+
+[END MJH]
+[RLB]
+I realize that you haven't been following the accessibility subgroup's work, but
+we've worked out the semantics of a "safe" in-place accessor for the containers.
+Presuming that exists, it is unlikely that anyone will be using much more
+complex generics.
+
+You could implement function Get_Name as (you would need to pass the container
+here, as the access is modifiable):
+
+    function Get_Name (L : in out List; C : Cursor) return String is
+    begin
+        return L.Accessor(C).Element.Name;
+    end Get_Name;
+
+(Yes, we're planning to allow "in out" parameters on functions, with some
+limitations on calls.) But in actual fact you wouldn't bother with a function at
+all - and most likely you'd rename the result of the accessor and use it for a
+while.
+
+So I'm completely ignoring this idea.
+[END RLB]
+
+
+   procedure Replace_Element (Container : in out Tree;
+                              Position  : in     Cursor;
+                              New_Item  : in     Element_Type);
+
+   procedure Query_Element
+     (Position : in Cursor;
+      Process  : not null access procedure (Element : in Element_Type));
+
+   procedure Update_Element
+     (Container : in out Tree;
+      Position  : in     Cursor;
+      Process   : not null access procedure
+                      (Element : in out Element_Type));
+
+   procedure Move (Target : in out Tree;
+                   Source : in out Tree);
+
+   procedure Delete (Container : in out Tree;
+                     Position  : in out Cursor);
+
+   function Find (Container : Tree;
+                  Item      : Element_Type;
+                  Position  : Cursor := No_Element)
+      return Cursor;
+
+   function Reverse_Find (Container : Tree;
+                          Item      : Element_Type;
+                          Position  : Cursor := No_Element)
+      return Cursor;
+
+   function Contains (Container : Tree;
+                      Item      : Element_Type) return Boolean;
+
+   function Has_Element (Position : Cursor) return Boolean;
+
+   procedure Iterate
+     (Container : in Tree;
+      Process   : not null access procedure (Position : in Cursor));
+
+   function Child_Length (Container : Tree; Parent : Cursor) return Count_Type;
+
+[MJH]
+I've been calling this Child_Count.  Calling it Child_Length seems like we're
+advertising too many impl. details, e.g. ptrs to child nodes are implemented as
+a list.  But I dunno; maybe calling it length is more consistent with how we
+count things in containers.
+[END MJH]
+[RLB]
+Well, the number of nodes in the entire subtree seems more like "Count" to me.
+And, as you say, it is more consistent. I didn't make much effort to make the
+names make more sense.
+[END RLB]
+
+   function Child_Depth (Parent, Child : Cursor) return Count_Type;
+
+[MJH]
+
+I've been calling this just Depth, like this:
+
+   function Depth (Position : Cursor) return Count_Type;
+
+But I see you're passing in two params.  OK, so you want to be able to calculate
+the depth of a node from any subtree in the tree.  Yes, that's more flexible,
+but you're not designing around the common case (which is depth away from the
+root of the tree).
+
+[RLB]
+There was supposed to be a function Depth that works from the root. It appears I
+left it out by accident.
+
+Perhaps I was thinking that you don't need it, because you can always pass in
+No_Parent for Parent. But since we can't default that usefully (it's not the
+last parameter), I agree that it is clunky this way. So I added Depth. Note that
+Depth (Position => No_Element) ought to be defined to give you the depth of the
+entire tree (the depth of the deepest element).
+[END RLB]
+
+In the odd event someone wanted to compute depth for any arbitrary subtree, you
+could always splice the subtree into its own tree.  But that won't work exactly,
+because the tree identity has changed (because the cursor is still bound to
+original tree).
+
+[RLB]
+And it would make copies of the elements if the tree is in a bounded container.
+The performance would be dismal.
+[END RLB]
+
+Here and elsewhere (it would be useful for all of the containers) it might make
+sense to have a Rebind operation, to assign a cursor to a different tree.
+Something like:
+
+  procedure Rebind
+    (Source   : Tree;   -- not strictly necessary
+     Position : Cursor;
+     Target   : Tree);
+
+Position would be bound to Target, and away from Source.
+
+[RLB]
+This is a horrible idea: it wouldn't work for any container implementation not
+using discrete nodes, like the canonical implementation of Vector and all of the
+bounded forms. Please forget you ever had this idea. ;-)
+[END RLB]
+
+Alternatively, you could pass the parent node as a default param:
+
+   function Depth
+     (Position : Cursor;
+      Parent   : Cursor := No_Element) return Count_Type;
+
+With the interpretation that when Parent = No_Element, this would mean depth
+from root of tree.
+[RLB]
+That would work, but it would put the parameters in the "wrong" order. Since
+they have the same type, that would be really confusing in a positional call.
+I think two separate functions are a better idea (but of course we'll discuss
+it).
+[END RLB]
+
+[END MJH]
+
+   procedure Insert_Child (Container : in out Tree;
+                           Parent    : in     Cursor;
+                           Before    : in     Cursor;
+                           New_Item  : in     Element_Type;
+                           Count     : in     Count_Type := 1);
+
+   procedure Insert_Child (Container : in out Tree;
+                           Parent    : in     Cursor;
+                           Before    : in     Cursor;
+                           New_Item  : in     Element_Type;
+                           Position  :    out Cursor;
+                           Count     : in     Count_Type := 1);
+
+   procedure Insert_Child (Container : in out Tree;
+                           Parent    : in     Cursor;
+                           Before    : in     Cursor;
+                           Position  :    out Cursor;
+                           Count     : in     Count_Type := 1);
+
+   procedure Prepend_Child (Container : in out Tree;
+                            Parent    : in     Cursor;
+                            New_Item  : in     Element_Type;
+                            Count     : in     Count_Type := 1);
+
+   procedure Append_Child (Container : in out Tree;
+                           Parent    : in     Cursor;
+                           New_Item  : in     Element_Type;
+                           Count     : in     Count_Type := 1);
+
+   procedure Delete_Child (Container : in out Tree;
+                           Parent    : in     Cursor;
+                           Position  : in out Cursor;
+                           Count     : in     Count_Type := 1);
+
+[MJH]
+
+How is this different from Delete?
+
+[END MJH]
+[RLB]
+It supports a count, allowing deletion of part or all of a child list. It didn't
+make sense to include a count on the plain Delete,  because what precisely is
+being counted is completely unclear (if there are both child and sibling nodes,
+which ones get deleted first? Doesn't pay to define that). Note that I explained
+that in the !discussion section; it might have helped to read that before
+commenting here. (You probably should have read that first, then came back to
+the spec. Too late now.)
+[END RLB]
+
+
+   procedure Delete_First_Child (Container : in out Tree;
+                                 Parent    : in     Cursor;
+                                 Count     : in     Count_Type := 1);
+
+[MJH]
+All of these seem like overkill.  It makes sense to treat manipulation of the
+front or back element specially, for a sequence abstraction as a list or vector,
+because this models stacks and queues.
+
+However, a tree is different.  It is recursive: you have trees, and subtrees.  I
+can see iterating over the immediate children in a (sub) tree, but I see less
+usefulness for wanting to manipulate the first or last child specifically.
+[END MJH]
+[RLB]
+I wanted to stay as close to the existing List definition as possible. I think
+those procedures are overkill in the lists, for all of the reasons you give
+here. (They're easy to write yourself, and container deletion is rare to begin
+with.)
+
+But never mind that, I'll get rid of them. But I'm going to say that's because
+Matt wanted them gone. :-)
+[END RLB]
+
+   procedure Delete_Last_Child (Container : in out Tree;
+                                Parent    : in     Cursor;
+                                Count     : in     Count_Type := 1);
+
+[MJH]
+See above.  Both of these can be effected easily enough:
+
+   procedure Op (T : in out Tree) is
+     C : Cursor := ...;
+     C2 : Cursor;
+   begin
+     ... -- need to delete last subtree, so do this:
+     C2 := Last_Child (C);
+     T.Delete (C2);
+     ...
+   end Op;
+
+[END MJH]
+
+[MJH]
+I don't see these listed:
+
+   procedure Swap  -- swap element value
+     (Container : in out Tree;
+      I, J      : Cursor);
+
+   procedure Swap_Links
+     (Container : in out Tree;
+      I, J      : Cursor);
+
+I think you need these.  For example, in the canonical implementation of a
+red-black tree, during rebalancing an element on a leaf node is swapped with an
+element value high up near the root.
+
+I admit that reasoning about behavior when one node is the immediate parent of
+another is a bit of a brain-teaser, though.  I spent most of Sat afternoon
+implementing Swap and Swap_Links but still didn't finish it.
+[END MJH]
+[RLB]
+As I noted in the discussion, I left these out on purpose. I was thinking of
+these only in terms of a single sibling list, and in that case they don't seem
+very useful. In hindsight, I think I screwed up leaving Swap out; since it moves
+Elements (not nodes), it doesn't need to be limited to a single child list.
+
+Your problems figuring out what it means to swap the parents if you do a general
+Swap_Links convinces me that we don't want to bother. I'd hate to have to figure
+out what it is supposed to do in some of those cases! And I really don't relish
+wording it.
+[END RLB]
 
-Yes, it is. I had really intended to use Append_Child, but since that doesn't
-return the position of the inserted element, it can't be used when it is
-intended to insert things on children.
 
-> I do welcome this Multiway_Tree suggestion. I think it fills a gap and
-> will be useful.
+   procedure Splice (Target   : in out Tree;
+                     Parent   : in     Cursor;
+                     Before   : in     Cursor;
+                     Source   : in out Tree);
 
-Thanks, good to know I'm not alone on this one.
+   procedure Splice (Target   : in out Tree;
+                     Parent   : in     Cursor;
+                     Before   : in     Cursor;
+                     Source   : in out Tree;
+                     Position : in out Cursor);
 
-****************************************************************
+   procedure Splice (Container: in out Tree;
+                     Parent   : in     Cursor;
+                     Before   : in     Cursor;
+                     Position : in     Cursor);
 
-From: Niklas Holsti
-Date: Saturday, January 31, 2009  3:17 AM
+[MJH]
 
-> Humm, I see your point. Perhaps it would be better named "As_Root" or
-> something like that?
+I've been calling these Splice_Child, but Splice probably works just as well.
 
-I also thought about "As_Root", and that would be OK in a positional call:
-Insert_Child (Sample, As_Root, ...). The named form, "Parent => As_Root", is
-better than "Parent => Root", but I'm still not happy with it.
+[END MJH]
+[RLB]
+That might be more consistent, I guess.
+[END RLB]
 
-> I don't think that the use of Parent => No_Element is particularly
-> understandable.
+   procedure Splice_Children (Target   : in out Tree;
+                              Parent   : in     Cursor;
+                              Before   : in     Cursor;
+                              Source   : in out Tree);
 
-I do. If you insert a node in a tree and specify that it shall have no parent
-node, obviously (to me) the node becomes a root.
+   procedure Splice_Children (Target   : in out Tree;
+                              Parent   : in     Cursor;
+                              Before   : in     Cursor;
+                              Source   : in out Tree;
+                              Position : in out Cursor);
 
-I would not object to defining "As_Root : Cursor renames No_Element", but I
-don't think it is very beneficial. Logically one would then expect also
-definitions like
+   procedure Splice_Children (Container: in out Tree;
+                              Parent   : in     Cursor;
+                              Before   : in     Cursor;
+                              Position : in     Cursor);
 
-    As_Last : Cursor renames No_Element;
+[MJH]
+As with Delete_First, etc, you can do this by iterating over the children of
+Position and splicing them.  However, that turns the cost of the operation from
+O(1) to O(n).  I don't whether this is really a useful operation, but maybe you
+could make the argument for its inclusion based on efficiency grounds.
+
+It is a bit confusing though about what is being spliced.  In my implementation
+I had named as Splice_Child the things you're calling Splice.  One idea is to
+rename this operation, say, to Reparent_Children.  Another idea is to rename
+from Splice to Splice_Subtree.
+[END MJH]
 
-for use as the Before parameter in Insert operations, but again I prefer "Before
-=> No_Element" to "Before => As_Last". It is again obvious (to me) that
-inserting an element in a list with the specification that it shall be before no
-other element means that the element is appended as the new last element in the
-list.
+   function Parent (Position : Cursor) return Cursor;
 
-> Originally, I had planned a second set of functions for accessing the root:
->
->     HTML_Tree.Insert_Root (
->         Sample,
->         Position => Header,
->         New_Element => Header_HTML_Element'(
->            Init_Element with null record));
->
-> But a lot of the time, you would end up making the code conditional on
-> whether you're inserting at the root or in a child, which doesn't seem
-> helpful.
+[MJH]
+There are some implementation tricks you can play here.  Instead of Parent
+(Root) returning No_Element, it could return a special value, so that
+First_Child (Parent (C)) always works, even if C happens to designate the root.
+See the implementation for how to implement this.
+[END MJH]
+[RLB]
+I got the feeling from the Ada-Comment discussion that people really don't want
+to mess with special values. The container parameter provides the needed
+information, anyway.
 
-I agree. I think the "Parent => No_Element" mechanism is a good solution.
-Perhaps it could be augmented by defining some root-specific operations, such as
-Insert_Root, analogously with the operations Prepend and Append and defined as
-equivalent to Insert_Child (.. Parent => No_Element ...). These could be used to
-increase clarity when it is statically known that the operation is on a root.
+Note that First_Child is a dubious operation on the root (do you get Root or the
+first orphan node?)
 
-To avoid cluttering the main package with these root-specific operations, why
-not define a child package, say Multiway_Trees.Roots, with operations such as
-Multiway_Trees.Roots.Insert and so on.
+Might be worth discussion once the orphan/Root model is explained properly.
+[END RLB]
 
-****************************************************************
+   function First_Child (Container : Tree; Parent : Cursor) return Cursor;
 
-From: Jean-Pierre Rosen
-Date: Saturday, January 31, 2009  7:38 PM
+[MJH]
+This is a bit confusing: is it first child of root node of tree, or
+leftmost-node?
+[RLB] It's the first child of the parent. If the parent is
+No_Element, then it is ???. (I had intended it to be the first root, but since
+people don't like the multirooted model, that has to be discarded. Making it the
+first orphan is the natural change, but I'm not sure that is what is wanted. My
+gut feeling is that this ought to raise Constraint_Error if this is the root,
+but that's annoying in practice.)
+[END RLB]
+
+Why does First_Child accept a container parameter?  My implementation is
+declared this way:
+
+   function First_Child (Position : Cursor) return Cursor;
+
+[END MJH]
+[RLB]
+The above doesn't work for the root, because No_Element does not contain an
+indication of the container. So how do you figure out what container you are
+talking about?? There are a number of functions where I passed in the container
+for this reason.
+
+As noted above, one option is to have a separate function to get the first
+orphan node ("First_Orphan"?) (as there is for the root), but that seems like it
+would get clunky.
 
-> Humm, I see your point. Perhaps it would be better named "As_Root" or
-> something like that? I don't think that the use of Parent =>
-> No_Element is particularly understandable.
+   function First_Child_Element (Container : Tree; Parent : Cursor)
+      return Element_Type;
 
-Well, anybody using a tree should know that the only node without a parent is
-the root, so I doesn't seem illogical to say that you want to insert at the root
-by saying that you want to insert at the place that has no parent.
+[MJH]
 
-Not a big deal anyway.
+As with Delete_First_Child, etc, I don't know how useful this is. This is about
+trees and subtrees.  The emphasis should be on the value of the element at the
+root of some subtree.  I can always say:
+
+   E := Element (First_Child (C));
+
+[END MJH]
+[RLB]
+Again, I'm just following the lists. I don't think there is any reason for this
+function to exist in any of the other containers either. (I.e., I don't see the
+difference, and in this case there is no performance advantage either, for any
+container.) But here I'm leaving it, because there doesn't seem to be any good
+reason to *not* have it and remain consistent.
+[END RLB]
+
+   function Last_Child (Container : Tree; Parent : Cursor) return Cursor;
+
+[MJH]
+
+As with First_Child, I don't understand why this accepts two paramters.  My
+prototype has this:
+
+   function Last_Child (Position : Cursor) return Cursor;
+
+[END MJH]
+[RLB]
+How do you deal with No_Element?? It's clear that no one wants a magic value
+that we can't use in default parameters (which is what happens if you try to
+include the container in it).
+[END RLB]
+
+   function Last_Child_Element (Container : Tree; Parent : Cursor)
+      return Element_Type;
+
+[MJH]
+
+Same comment as for First_Child_Element.
+
+[END MJH]
+
+   function Next_Sibling (Position : Cursor) return Cursor;
+
+   function Previous_Sibling (Position : Cursor) return Cursor;
+
+   procedure Next_Sibling (Position : in out Cursor);
+
+   procedure Previous_Sibling (Position : in out Cursor);
+
+[MJH]
+
+I don't see these operations:
+
+   function Sibling_Count (Position : Cursor) return Count_Type;
+   function First_Sibling (Position : Cursor) return Cursor;
+   function Last_Sibling (Position : Cursor) return Cursor;
+
+You might think you could implement these by saying:
+
+   FS : Cursor := First_Child (Parent (C));
+
+but this won't work for the root -- unless you play tricks in the implementation
+of Parent (see the prototype for one way how to do this).
+
+[RLB]
+Right, but your implementation of First_Child cannot work for the root either:
+    First_Orphan := First_Child (No_Element); because you don't know what container to extract the root from!
+
+Once you add the container parameter to First_Child, this problem goes away.
+
+I don't see how your First_Child can work directly on the root, unless you use
+magic values (previously rejected).
+
+OIC, you are going to tell us that we *have* to have magic values, at every
+meeting from now until ISO publishes the Standard. :-) PLEASE learn to take no
+for an answer (not that you have to take it from me individually, but surely
+from the group).
+
+Anyway, I don't think there is any value to "sibling" operations other than the
+simple navigation ones. As you say, this is not a sequence per-se; usually you
+only care about the relationships of the nodes. And it has to be the case that
+going to the parent and then to the First_Child always works to get all of your
+siblings.
+[END RLB]
+
+Actually, that's not quite right -- you could play tricks with the value of
+cursors that designate the root.  Just as the cursor that designates the parent
+can have a special value, a cursor that designates the root itself can have a
+special value too.  See the implementation of function Root in the prototype.
+[END MJH]
+
+[MJH]
+   procedure Iterate_Child
+     (Container : in Tree;
+      Parent    : in     Cursor;
+      Process   : not null access procedure (Position : in Cursor));
+
+   procedure Reverse_Iterate_Child
+     (Container : in Tree;
+      Parent    : in     Cursor;
+      Process   : not null access procedure (Position : in Cursor));
+
+Do we really need Tree here?  I don't see why.
+
+[RLB]
+Same as always, if Parent = No_Element, you don't know the container to iterate
+over.
+[END RLB]
+
+Also, should this be Iterate_Children?
+[RLB]
+Yes, that does sound a bit better.
+[END RLB]
+
+It might also be useful to have passive iterators to iterate over siblings.
+
+   procedure Iterate_Siblings
+     (Container : in Tree;
+      Parent    : in     Cursor;
+      Process   : not null access procedure (Position : in Cursor));
+
+   procedure Reverse_Iterate_Siblings
+     (Container : in Tree;
+      Parent    : in     Cursor;
+      Process   : not null access procedure (Position : in Cursor));
+
+[END MJH]
+[RLB]
+I don't see the point, just get the parent and use Iterate_Children. That always
+has to work.
+
+Note that Iterate_Children will iterate the entire list of orphan nodes, not
+just the root when given No_Element.
+
+Iterate will iterate just from the Root.
+[END RLB]
+[MJH]
+
+The following operation is missing:
+
+   function Root (Container : Tree) return Cursor;
+
+This is the most important function in the whole API!
+
+See the functions Root and Parent in the prototype for some implementation
+ideas.
+
+[END MJH]
+[RLB]
+Not in the model I gave. In the model I had, there are many roots. That's still
+true, except that now they are called orphans (nodes with no parent). It is
+possible to designate one of them as the Root with Set_Root.
+
+This model is necessary so that it is possible to build subtrees bottom up in a
+bounded container without copying elements over and over. (Remember, a bounded
+container is an array.)
+[END RLB]
+
+[MJH]
+
+These are also useful:
+
+   function Is_Root (Position : Cursor) return Boolean;
+   function Is_Leaf (Position : Cursor) return Boolean;
+
+   function To_Tree (New_Item : Element_Type) return Tree;
+   -- or possibly New_Tree (NI : ET) return T;
+
+I see that you have a version of Insert that omits the element parameter, so you
+can create new node(s).  We would have to decide whether a constructor-style
+function as To_Tree should be overloaded with a parameter-less version, to
+create a root that has its element initialized to the default value for the
+type.
+
+[END MJH]
+[RLB]
+I suppose we need Is_Root and Is_Orphan (but I don't see any point in Is_Leaf =
+(not Is_Orphan)). There is no reason for To_Tree, because a tree with one
+element in it is silly; you're going to have to insert other elements anyway.
+Why have a special routine for the first one?? Besides, we don't have a To_List
+or To_Map, so I don't see why this one should be different.
+
+(Much later): I realize that by "Is_Leaf" you mean "does not have any children".
+I'm not sure I like this name, but the alternative of Has_No_Children will not
+cause a lot of excitement.
+[END RLB]
+
+
+private
+   ... -- not specified by the language
+end Ada.Containers.Multiway_Trees;
+
+The 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.
+
+[MJH]
+
+I've been referring to operations as XXX_Siblings and XXX_Children.
+The siblings versions aren't strictly necessary, if you refer call the XXX_Child
+operation on the Parent of the node of interest.
+
+(But I have to think about it -- you might have to play some tricks using
+distinguished cursor values, so that that always works, even when the node of
+iterest is the root.  What we definitely do not want is for the user to have to
+special-case the root -- but we don't want require him to pass the tree object
+as an extra parameter either.  All the information we need is carried in the
+cursor itself.  The only potential problem with distinguished cursor values is
+whether an equality test with No_Element is allowed to return False, if
+Has_Element also returns False.  Or perhaps you guys have solved the "does
+equality compose" problem.)
+
+[END MJH]
+[RLB]
+We're trying to fix the equality composition problem, but it hasn't been looking
+that good. Not sure what is going to happen there.
+
+But in any case there is a whole bunch of orphan nodes (one of which is
+designated the root). So anything based on "THE ROOT" is not going to work,
+because you have to be able to work on unattached subtrees as well.
+
+I do agree that First_Child, etc. have to work on orphans as well. That's why
+they have a container parameter!
+
+But I will try to think this some more, in case there is a problem.
+[END RLB]
+
+Having "_Child" as part of the names also opens up the possibility of operations
+not having the "_Child" suffix. These would naturally operate on the entire
+tree. We're taken advantage of this to define operations like Find and Iterate
+over the entire tree.
+
+[MJH]
+
+As above, it might be useful to distinguish between operations that apply to
+children, vs. operations that apply to siblings.
+
+[END MJH]
+[RLB]
+I don't think there is any major value to sibling operations beyond the basic
+navigation ones. Unless we just want to bulk up the Standard. :-)
+[END RLB]
+
+Note that the root of the tree is also a list of elements. (Thus the tree is
+multirooted as well as multiway.) We considered allowing only a single root
+node, but it seemed inconsistent for no important reason, and moreover, allowing
+additional roots allows bottom-up tree creation where subtrees are stashed in
+the root until their parent is created (at which time Slice_Child would be used
+to make it a subtree of the appropriate parent).
+
+[MJH]
+I don't agree with anything in the above paragraph.
+[END MJH]
+[RLB]
+The ARG changed this slightly, but we did agree that a list of unattached
+subtrees (I'm calling them orphans) is needed. So most of this is still true,
+but the terminology has changed.
+[END RLB]
+
+For all of the subprograms that take a Parent parameter, if the parameter is
+No_Element, the node is inserted at the root of the tree. This is consistent
+with the meaning of the Before parameter in the Insert routines in the existing
+list containers.
+
+[MJH]
+Well, I think that a tree should only have a single root (where do the multiple
+children of the parent of the root live???).  But note that:
+
+   C := Parent (T.Root);
+
+might return some distinguished value that is different from No_Element.
+(Assuming that behavior is allowed by this API.)
+
+See the functions Parent and Root in the prototype for some ideas.
+
+[END MJH]
+[RLB]
+Well, you'll just have to read the next version of the AI, because I am not
+going to waste my time writing it here, too.
+
+You seem to have missed the entire point of the discussion that Tucker and I had
+at the meeting. We must have multiple unattached subtrees, else the bounded tree
+will be too slow to use (you'd have to copy everything at every insertion of a
+parent).
+
+They obviously live in the top-level list. What's inconsistent is for every
+level to be a list, except the top one! That's what gets us into trouble.
+[END RLB]
+
+Notes on specific subprograms:
+
+Operations that were dropped are: Swap and Swap_List; Reverse_Elements; and the
+sorting operations. These could have been defined, but they seem strange
+operating on a single list of children; they seem more like operations for an
+entire container (where they make no sense).
+
+[MJH]
+Disagree.  In the canonical implementation of a red-black tree, an element is
+swapped from a leaf node with an element high up near the root.  We have to get
+all the corner cases right (e.g. one node is the immediate parent of another),
+but these operations should probably be included.
+[END MJH]
+
+Delete is provided to delete an arbitrary node from the tree. We don't provide a
+Count parameter on that routine, because it is not obvious what is being counted
+(sibling nodes only? child nodes only? both sibling and child nodes?)
+
+[MJH]
+Right: it means "delete this subtree".
+[END MJH]
+[RLB]
+Actually, I meant it specifically to delete a single node without having to
+figure out the parent node and such cruft. I didn't do a very good job of
+explaining how that would work if the node is a parent (forgot to think about
+it)! Deleting a subtree is also a good idea.
+[END RLB]
+
+Iterate walks the entire tree starting with the root list of nodes. Each node in
+every child list is visited in order; after each node is visited, the child list
+of that of that node are visited. This is done recursively.
+
+[MJH]
+
+I'm not clear whether you're describing a breadth-first traversal or a
+depth-first traversal.  Do we need two forms of passive iterator?
+
+[END MJH]
+[RLB]
+Work it out *very carefully*. It is depth-first (I think, I confuse the terms
+sometimes). I couldn't think of any use for breadth-first traversal, so I didn't
+provide it. (Among other things, you have to iterate the list twice, which is a
+silly thing to do.) But I'm willing to be convinced (but think of an actual use,
+not just that you could do it the other way). In any case, you can write it
+yourself using the child iterators.
+[END RLB]
+
+Child_Length returns the number of Children nodes of Parent.
+
+Child_Depth returns the number of ancestor nodes of Child, up to (but not
+including Parent). If Parent is No_Element, returns the number of ancestor nodes
+of Child. Raises Program_Error if Parent is not No_Element, and is not an
+ancestor of Child.
+
+[MJH]
+
+See my comments above about Child_Depth.
+
+[END MJH]
+
+For Insert_Child, if the Before parameter is not a child of Parent,
+Program_Error is propagated.
+
+Delete_Child is similar to Delete, but (a) the node to delete must be a child of
+the Parent; (b) a Count is provided to delete several children.
+
+[MJH]
+
+There's no real benefit to this operation.  It must be done iteratively (that
+is, O(n)) no matter what.
+
+[END MJH]
+[RLB]
+Are you sure? If so, it would again apply in the same way to the similar List
+operation. In any case, consistency suggests having it.
+[END RLB]
+
+We didn't add "_Child" to Splice, as it usually will be splicing entire
+subtrees. As with Insert_Child, if Before is not a child of Parent,
+Program_Error is propagated. Splice moves the node(s) and all child nodes of the
+node to the new position in the (new) tree. Splice_Children moves only the child
+nodes of the position to the new position.
+
+[MJH]
+Another way to say "moves the node(s) and all child nodes of the node"
+is "the subtree whose root is node".
+[RLB]
+We didn't define the term "subtree". We could, I suppose, it surely would make
+things more readable.
+[END RLB]
+
+As I state above, I mixed feelings about calling it "Splice_Children". (Not only
+that: the only real reason for Splice_Children to allow the splice to be O(1)
+instead of O(n).  Is it really worth it?  I dunno.)
+
+[END MJH]
+
+Selector function Parent returns the parent of the node represented by the given
+cursor.
+
+[MJH]
+As I allude to above (and in the prototype), it's not necessarily that simple --
+it all depends on what is permissible per this API.
+
+The cursor values T.Root and Parent (T.Root) could have distinguished values,
+that are useful treating the root as just another node, but these values don't
+necessarily compare equal to the distinguished cursor value No_Element.
+[END MJH]
+[RLB]
+I don't see the point; and if you do that, you can never default a parameter to
+No_Parent (equiv. No_Element). That seems bad at best.
+[END RLB]
+
+Next and Previous were renamed Next_Sibling and Previous_Sibling to make the
+meaning clearer (they work just like the list versions).
+
+[MJH]
+
+Right, and you could make that case for a few other operations as well.
+
+Even with dedicated XXX_Sibling(s) operations, it would be nice to have a
+guarantee that calls such as XXX_Children (Parent (T.Root)) just work -- even if
+the tree is empty.  For example, I would expect that:
+
+  First_Child (Parent (T.Root)) = T.Root
+  Last_Child (Parent (T.Root) = T.Root
+  First_Sibling (T.Root) = T.Root
+  Last_Sibling (T.Root) = T.Root
+
+Assuming
+
+  function Root (T : Tree) return Cursor;
+
+is defined.
+
+[END MJH]
+[RLB]
+None of this is necessarily true, because Root is just one orphan node. We could
+define the first orphan node to be the Root, so First_Child (Parent (T.Root)) =
+T.Root but surely Last_Child could be anything in that case.
+
+If we left the orphan nodes out of First_Child/Last_Child completely (and
+provided First_Orphan/Last_Orphan/etc to deal with them), then if you have a
+non-root orphan node, you would never find yourself on the sibling list of the
+top-level. That would make things very irregular.
+
+So I'm proposing that Root is only special for a few operations (mostly
+iterators). At least until I think about this more.
+[END RLB]
+
+Note that we left the Container parameter in routines like First_Child, because
+the Parent parameter can be No_Element to represent the root, and we need to
+know where to look for that root. An alternative design would be to have a
+separate set of routines for accessing the root, but that would clutter the
+package and complicate use (a lot of insertion code would have to explicitly
+check to see if it is inserting at the root: a scourge of hand-written code that
+we don't want to duplicate in the containers!).
+
+[MJH]
+Neither of these things is true.  First_Child and friends should only have a
+single cursor parameter.
+[END MJH]
+[RLB]
+But how do you find the root then? There surely can be more than one Tree in
+existence in a program!
+
+Looking at your implementation, you have First_Child (No_Element) = No_Element.
+But that is wrong, it has to return the first orphan node (in your
+implementation, it ought to return the Root node itself). First_Child
+(First_Child (No_Element)) needs to get the first grandchild element (first
+second-level element).
+[END RLB]
+
+
+Iterate_Child and Iterate_Reverse_Child just iterate over the child nodes of
+Parent (and no others).
+
+[MJH]
+
+See my comment above.  I don't think you need a container parameter. A cursor
+always points to the root of some subtree, so I don't see why you also need to
+pass the tree container.  The only reason an operation needs to specify a
+container parameter is to preserve constant/variable view semantics.
+
+(I'm not sure whether the formal cursor parameter should be named "Parent"
+either -- but I have to think about it.)
+[END MJH]
+
+
+Further ideas:
+
+* 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.
+
+[MJH]
+Right, and this is especially true for searching.
+[END MJH]
 
 ****************************************************************

Questions? Ask the ACAA Technical Agent