Ada Conformity Assessment Authority      Home Conformity Assessment   Test Suite ARGAda Standard
 
Annotated Ada Reference Manual (Ada 202x Draft 26)Legal Information
Contents   Index   References   Search   Previous   Next 

A.18.10 The Generic Package Containers.Multiway_Trees

1/3
{AI05-0136-1} The language-defined generic package Containers.Multiway_Trees provides private types Tree and Cursor, and a set of operations for each type. A multiway tree container is well-suited to represent nested structures.
1.a/3
Discussion: {AI05-0136-1} This tree just provides a basic structure, and make no promises about balancing or other automatic organization. In this sense, it is different than the indexed (Map, Set) forms. Rather, it provides a building block on which to construct more complex and more specialized tree containers.
2/4
{AI05-0136-1} {AI12-0078-1} {AI12-0159-1} A multiway tree container object manages a tree of internal nodes, consisting of a root node and a set of internal nodes; each internal node of which contains an element and pointers to the parent, first child, last child, next (successor) sibling, and previous (predecessor) sibling internal nodes. A cursor designates a particular node within a tree (and by extension the element contained in that node, if any). A cursor keeps designating the same node (and element) as long as the node is part of the container, even if the node is moved within the container.
3/4
{AI05-0136-1} {AI05-0269-1} {AI12-0078-1} 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). The root node There is a special node, the root, which is always present and has neither an associated element value nor any parent node; it has pointers to its first child and its last child, if any. The root node provides a place to add nodes to an otherwise empty tree and represents the base of the tree.
4/3
{AI05-0136-1} {AI05-0269-1} A node that has no children is called a leaf node. The ancestors of a node are the node itself, its 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 node itself, its child nodes, the children of each child node, and so on.
5/3
{AI05-0136-1} {AI05-0262-1} {AI05-0269-1} The nodes of a subtree can be visited in several different orders. For a depth-first order, after visiting a node, the nodes of its child list are each visited in depth-first order, with each child node visited in natural order (first child to last child).
5.a/3
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. 

Static Semantics

6/3
{AI05-0136-1} The generic library package Containers.Multiway_Trees has the following declaration: 
7/5
{AI05-0136-1} {AI05-0212-1} {AI12-0112-1} with Ada.Iterator_Interfaces;
generic
   type Element_Type is private;
   with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Multiway_Trees is
   with Preelaborate, Remote_Types,
        Nonblocking, Global => in out synchronized is

   pragma Preelaborate(Multiway_Trees);
   pragma Remote_Types(Multiway_Trees);
7.a/5
Discussion: {AI12-0112-1} For discussion on the reasons and meaning of the specifications of the Global and Nonblocking aspects in this generic package, see the notes on the equivalent operations in the specification of the Containers.Vectors package (see A.18.2).
8/5
{AI05-0136-1} {AI05-0212-1} {AI12-0111-1} {AI12-0112-1}    type Tree is tagged private
      with Constant_Indexing => Constant_Reference,
           Variable_Indexing => Reference,
           Default_Iterator  => Iterate,
           Iterator_Element  => Element_Type,
           Iterator_View     => Stable.Tree,
           Stable_Properties => (Node_Count,
                                 Tampering_With_Cursors_Prohibited,
                                 Tampering_With_Elements_Prohibited),
           Default_Initial_Condition =>
              Node_Count (Tree) = 1 and then
              (not Tampering_With_Cursors_Prohibited (Tree)) and then
              (not Tampering_With_Elements_Prohibited (Tree))
;
   pragma Preelaborable_Initialization(Tree);
9/3
   type Cursor is private;
   pragma Preelaborable_Initialization(Cursor);
10/3
   Empty_Tree : constant Tree;
11/3
   No_Element : constant Cursor;
11.1/5
{AI12-0112-1}    function Equal_Element (Left, Right : Element_Type)
      return Boolean renames "=";
12/5
{AI05-0212-1} {AI12-0112-1}    function Has_Element (Position : Cursor) return Boolean
      with Nonblocking, Global => in all, Use_Formal => null
;
12.1/5
{AI12-0112-1}    function Has_Element (Container : Tree; Position : Cursor)
      return Boolean
      with Nonblocking, Global => null, Use_Formal => null;
13/3
{AI05-0212-1}    package Tree_Iterator_Interfaces is new
      Ada.Iterator_Interfaces (Cursor, Has_Element);
14/3
   function Equal_Subtree (Left_Position : Cursor;
                           Right_Position: Cursor) return Boolean;
15/3
   function "=" (Left, Right : Tree) return Boolean;
15.1/5
{AI12-0112-1}    function Tampering_With_Cursors_Prohibited
      (Container : Tree) return Boolean
      with Nonblocking, Global => null, Use_Formal => null;
15.2/5
{AI12-0112-1}    function Tampering_With_Elements_Prohibited
      (Container : Tree) return Boolean
      with Nonblocking, Global => null, Use_Formal => null;
15.3/5
{AI12-0339-1}    function Empty return Tree
      is (Empty_Tree)
      with Post =>
            not Tampering_With_Elements_Prohibited (Empty'Result) and then
            not Tampering_With_Cursors_Prohibited (Empty'Result) and then
            Node_Count (Empty'Result) = 1;
16/5
{AI12-0112-1}    function Is_Empty (Container : Tree) return Boolean
      with Nonblocking, Global => null, Use_Formal => null,
           Post => Is_Empty'Result = (Node_Count (Container) = 1)
;
17/5
{AI12-0112-1}    function Node_Count (Container : Tree) return Count_Type
      with Nonblocking, Global => null, Use_Formal => null
;
18/5
{AI12-0112-1}    function Subtree_Node_Count (Position : Cursor) return Count_Type
      with Nonblocking, Global => in all, Use_Formal => null
;
18.1/5
{AI12-0112-1}    function Subtree_Node_Count (Container : Tree; Position : Cursor)
      return Count_Type
      with Pre => Meaningful_For (Container, Position)
                      or else raise Program_Error,
           Nonblocking, Global => null, Use_Formal => null;
19/5
{AI12-0112-1}    function Depth (Position : Cursor) return Count_Type
      with Nonblocking, Global => (in alluse null)
;
19.1/5
{AI12-0112-1}    function Depth (Container : Tree; Position : Cursor)
      return Count_Type
      with Pre => Meaningful_For (Container, Position)
                      or else raise Program_Error,
           Nonblocking, Global => null, Use_Formal => null;
20/5
{AI12-0112-1}    function Is_Root (Position : Cursor) return Boolean
      with Nonblocking, Global => (in alluse null)
;
20.1/5
{AI12-0112-1}    function Is_Root (Container : Tree; Position : Cursor)
      return Boolean
      with Nonblocking, Global => null, Use_Formal => null;
21/5
{AI12-0112-1}    function Is_Leaf (Position : Cursor) return Boolean
      with Nonblocking, Global => (in alluse null)
;
21.1/5
{AI12-0112-1}    function Is_Leaf (Container : Tree; Position : Cursor)
      return Boolean
      with Pre => Meaningful_For (Container, Position)
                      or else raise Program_Error,
           Nonblocking, Global => null, Use_Formal => null;
21.2/5
{AI12-0112-1}    function Is_Ancestor_Of (Container : Tree;
          Parent   : Cursor;
          Position : Cursor) return Boolean
      with Pre => (Meaningful_For (Container, Position)
                      or else raise Program_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error),
           Nonblocking, Global => null, Use_Formal => null;
22/5
{AI12-0112-1}    function Root (Container : Tree) return Cursor
      with Nonblocking, Global => null, Use_Formal => null,
           Post => Root'Result /= No_Element and then
                   not Has_Element (Container, Root'Result)
;
22.1/5
{AI12-0112-1}    function Meaningful_For
      (Container : Tree; Position : Cursor) return Boolean is
      (Position = No_Element or else
       Is_Root (Container, Position) or else
       Has_Element (Container, Position))
      with Nonblocking, Global => null, Use_Formal => null;
22.a/5
Reason: {AI12-0112-1} When this function is true, the Position can be meaningfully used with operations for Container. We define this because many operations allow the root (which does not have an element, so Has_Element returns False), so many preconditions get unwieldy. We allow No_Element as it is allowed by many queries, and for existing routines, it raises a different exception (Constraint_Error rather than Program_Error) than a cursor for the wrong container does. 
23/5
{AI12-0112-1}    procedure Clear (Container : in out Tree)
      with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                       or else raise Program_Error,
           Post => Node_Count (Container) = 1
;
24/5
{AI12-0112-1}    function Element (Position : Cursor) return Element_Type
      with Pre => (Position /= No_Element or else
                      raise Constraint_Error) and then
                   (Has_Element (Position) or else raise Program_Error),
           Nonblocking,
           Global => in all, Use_Formal => Element_Type
;
24.1/5
{AI12-0112-1}    function Element (Container : Tree;
                     Position  : Cursor) return Element_Type
      with Pre => (Position /= No_Element or else
                      raise Constraint_Error) and then
                   (Has_Element (Container, Position) 
                      or else raise Program_Error),
           Nonblocking,
           Global => null, Use_Formal => Element_Type;
25/5
{AI12-0112-1}    procedure Replace_Element (Container : in out Tree;
                              Position  : in     Cursor;
                              New_item  : in     Element_Type)
      with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Position /= No_Element 
                      or else raise Constraint_Error) and then
                   (Has_Element (Container, Position) 
                      or else raise Program_Error)
;
26/5
{AI12-0112-1}    procedure Query_Element
     (Position : in Cursor;
      Process  : not null access procedure (Element : in Element_Type))
      with Pre  => (Position /= No_Element 
                      or else raise Constraint_Error) and then
                   (Has_Element (Position) or else raise Program_Error),
           Global => in all
;
26.1/5
{AI12-0112-1}    procedure Query_Element
     (Container : in Tree;
      Position  : in Cursor;
      Process   : not null access procedure (Element : in Element_Type))
      with Pre  => (Position /= No_Element 
                      or else raise Constraint_Error) and then
                   (Has_Element (Container, Position) 
                      or else raise Program_Error);
27/5
{AI12-0112-1}    procedure Update_Element
     (Container : in out Tree;
      Position  : in     Cursor;
      Process   : not null access procedure
                      (Element : in out Element_Type))
      with Pre  => (Position /= No_Element 
                      or else raise Constraint_Error) and then
                   (Has_Element (Container, Position) 
                      or else raise Program_Error)
;
28/5
{AI05-0212-1} {AI12-0112-1}    type Constant_Reference_Type
         (Element : not null access constant Element_Type) is private
      with Implicit_Dereference => Element,
           Nonblocking, Global => in out synchronized,
           Default_Initial_Condition => (raise Program_Error)
;
29/5
{AI05-0212-1} {AI12-0112-1}    type Reference_Type (Element : not null access Element_Type) is private
      with Implicit_Dereference => Element,
           Nonblocking, Global => in out synchronized,
           Default_Initial_Condition => (raise Program_Error)
;
30/5
{AI05-0212-1} {AI12-0112-1}    function Constant_Reference (Container : aliased in Tree;
                                Position  : in Cursor)
      return Constant_Reference_Type
      with Pre  => (Position /= No_Element
                      or else raise Constraint_Error) and then
                   (Has_Element (Container, Position) 
                      or else raise Program_Error),
           Post   => Tampering_With_Cursors_Prohibited (Container),
           Nonblocking, Global => null, Use_Formal => null
;
31/5
{AI05-0212-1} {AI12-0112-1}    function Reference (Container : aliased in out Tree;
                       Position  : in Cursor)
      return Reference_Type
      with Pre  => (Position /= No_Element 
                      or else raise Constraint_Error) and then
                   (Has_Element (Container, Position) 
                      or else raise Program_Error),
           Post   => Tampering_With_Cursors_Prohibited (Container),
           Nonblocking, Global => null, Use_Formal => null
;
32/5
{AI12-0112-1}    procedure Assign (Target : in out Tree; Source : in Tree)
      with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                      or else raise Program_Error,
           Post => Node_Count (Source) = Node_Count (Target)
;
33/5
{AI12-0112-1}    function Copy (Source : Tree) return Tree
      with Post =>
              Node_Count (Copy'Result) = Node_Count (Source) and then
              not Tampering_With_Elements_Prohibited (Copy'Result) and then
              not Tampering_With_Cursors_Prohibited (Copy'Result)
;
34/5
{AI12-0112-1}    procedure Move (Target : in out Tree;
                   Source : in out Tree)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                      or else raise Program_Error) and then
                   (not Tampering_With_Cursors_Prohibited (Source)
                      or else raise Program_Error),
           Post => (if not Target'Has_Same_Storage (Source) then
                  Node_Count (Target) = Node_Count (Source'Old) and then
                  Node_Count (Source) = 1)
;
35/5
{AI12-0112-1}    procedure Delete_Leaf (Container : in out Tree;
                          Position  : in out Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Position /= No_Element 
                      or else raise Constraint_Error) and then
                   (Has_Element (Container, Position)
                      or else raise Program_Error) and then
                   (Is_Leaf (Container, Position)
                      or else raise Constraint_Error),
           Post =>
              Node_Count (Container)'Old = Node_Count (Container)+1 and then
              Position = No_Element
;
36/5
{AI12-0112-1}    procedure Delete_Subtree (Container : in out Tree;
                             Position  : in out Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Position /= No_Element 
                      or else raise Constraint_Error) and then
                   (Has_Element (Container, Position)
                      or else raise Program_Error),
           Post => Node_Count (Container)'Old = Node_Count (Container) +
                      Subtree_Node_Count (Container, Position)'Old and then
                   Position = No_Element
;
37/5
{AI12-0112-1}    procedure Swap (Container : in out Tree;
                   I, J      : in     Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (I /= No_Element or else Constraint_Error) and then
                   (J /= No_Element or else Constraint_Error) and then
                   (Has_Element (Container, I)
                      or else raise Program_Error) and then
                   (Has_Element (Container, J)
                      or else raise Program_Error)
;
38/5
{AI12-0112-1}    function Find (Container : Tree;
                  Item      : Element_Type)
      return Cursor
      with Post => (if Find'Result = No_Element then True
                    else Has_Element (Container, Find'Result))
;
39/5
{AI05-0136-1} {AI05-0248-1} {AI12-0112-1}    function Find_In_Subtree (Position : Cursor;
                             Item     : Element_Type)
      return Cursor
      with Pre  => Position /= No_Element or else raise Constraint_Error,
           Post => (if Find_In_Subtree'Result = No_Element then True
                    else Has_Element (Find_In_Subtree'Result)),
           Global => in all
;
39.1/5
{AI12-0112-1}    function Find_In_Subtree (Container : Tree;
                             Position  : Cursor;
                             Item      : Element_Type)
      return Cursor
      with Pre  => (Position /= No_Element 
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Position)
                      or else raise Program_Error),
           Post => (if Find_In_Subtree'Result = No_Element then True
                    else Has_Element (Container, Find_In_Subtree'Result));
40/5
{AI05-0136-1} {AI05-0248-1} {AI12-0112-1}    function Ancestor_Find (Position : Cursor;
                           Item     : Element_Type)
      return Cursor
      with Pre  => Position /= No_Element or else raise Constraint_Error,
           Post => (if Ancestor_Find'Result = No_Element then True
                    else Has_Element (Ancestor_Find'Result)),
           Global => in all
;
40.1/5
{AI12-0112-1}    function Ancestor_Find (Container : Tree;
                           Position  : Cursor;
                           Item      : Element_Type)
      return Cursor
      with Pre  => (Position /= No_Element 
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Position)
                      or else raise Program_Error),
           Post => (if Ancestor_Find'Result = No_Element then True
                    else Has_Element (Container, Ancestor_Find'Result));
41/3
   function Contains (Container : Tree;
                      Item      : Element_Type) return Boolean;
42/5
{AI12-0112-1}    procedure Iterate
     (Container : in Tree;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit
;
43/5
{AI12-0112-1}    procedure Iterate_Subtree
     (Position  : in Cursor;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit,
           Pre  => Position /= No_Element or else raise Constraint_Error,
           Global => in all
;
43.1/5
{AI12-0112-1}    procedure Iterate_Subtree
     (Container : in Tree;
      Position  : in Cursor;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit,
           Pre  => (Position /= No_Element 
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Position)
                      or else raise Program_Error);
44/5
{AI05-0212-1} {AI12-0112-1} {AI12-0266-1}    function Iterate (Container : in Tree)
      return Tree_Iterator_Interfaces.Parallel_Iterator Forward_Iterator'Class
      with Post => Tampering_With_Cursors_Prohibited (Container)
;
45/5
{AI05-0212-1} {AI12-0112-1} {AI12-0266-1}    function Iterate_Subtree (Position : in Cursor)
      return Tree_Iterator_Interfaces.Parallel_Iterator Forward_Iterator'Class
      with Pre    => Position /= No_Element or else raise Constraint_Error,
           Global => in all
;
45.1/5
{AI12-0112-1}    function Iterate_Subtree (Container : in Tree; Position : in Cursor)
      return Tree_Iterator_Interfaces.Parallel_Iterator'Class
      with Pre  => (Position /= No_Element 
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Position)
                      or else raise Program_Error),
           Post => Tampering_With_Cursors_Prohibited (Container);
46/5
{AI12-0112-1}    function Child_Count (Parent : Cursor) return Count_Type
      with Post => (if Parent = No_Element then Child_Count'Result = 0
                    else True),
            Nonblocking, Global => (in alluse null)
;
46.1/5
{AI12-0112-1}    function Child_Count (Container : Tree; Parent : Cursor)
      return Count_Type
      with Pre  => Meaningful_For (Container, Parent) 
                      or else raise Program_Error,
           Post => (if Parent = No_Element then Child_Count'Result = 0
                    else True),
           Nonblocking, Global => null, Use_Formal => null;
47/5
{AI12-0112-1}    function Child_Depth (Parent, Child : Cursor) return Count_Type
      with Pre  => (Parent = No_Element and then Child = No_Element)
                      or else raise Constraint_Error,
           Nonblocking, Global => (in alluse null)
;
47.1/5
{AI12-0112-1}    function Child_Depth (Container : Tree; Parent, Child : Cursor)
      return Count_Type
      with Pre  => ((Parent = No_Element and then Child = No_Element)
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error) and then
                   (Meaningful_For (Container, Child)
                      or else raise Program_Error),
           Nonblocking, Global => null, Use_Formal => null;
48/5
{AI12-0112-1}    procedure Insert_Child (Container : in out Tree;
                           Parent    : in     Cursor;
                           Before    : in     Cursor;
                           New_Item  : in     Element_Type;
                           Count     : in     Count_Type := 1)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Parent /= No_Element
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error) and then
                   (Meaningful_For (Container, Before)
                      or else raise Program_Error) and then
                   (Before = No_Element or else
                    Container.Parent (Before) = Parent
                      or else raise Constraint_Error),
           Post => Node_Count (Container) =
                   Node_Count (Container)'Old + Count
;
49/5
{AI12-0112-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)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Parent /= No_Element
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error) and then
                   (Meaningful_For (Container, Before)
                      or else raise Program_Error) and then
                   (Before = No_Element or else
                    Container.Parent (Before) = Parent
                      or else raise Constraint_Error),
           Post => (Node_Count (Container) =
                    Node_Count (Container)'Old + Count) and then
                   Has_Element (Container, Position)
;
50/5
{AI12-0112-1}    procedure Insert_Child (Container : in out Tree;
                           Parent    : in     Cursor;
                           Before    : in     Cursor;
                           Position  :    out Cursor;
                           Count     : in     Count_Type := 1)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Parent /= No_Element
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error) and then
                   (Meaningful_For (Container, Before)
                      or else raise Program_Error) and then
                   (Before = No_Element or else
                    Container.Parent (Before) = Parent
                      or else raise Constraint_Error),
           Post => (Node_Count (Container) =
                    Node_Count (Container)'Old + Count) and then
                   Has_Element (Container, Position)
;
51/5
{AI12-0112-1}    procedure Prepend_Child (Container : in out Tree;
                            Parent    : in     Cursor;
                            New_Item  : in     Element_Type;
                            Count     : in     Count_Type := 1)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Parent /= No_Element
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error),
           Post => Node_Count (Container) =
                   Node_Count (Container)'Old + Count
;
52/5
{AI12-0112-1}    procedure Append_Child (Container : in out Tree;
                           Parent    : in     Cursor;
                           New_Item  : in     Element_Type;
                           Count     : in     Count_Type := 1)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Parent /= No_Element
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error),
           Post => Node_Count (Container) =
                   Node_Count (Container)'Old + Count
;
53/5
{AI12-0112-1}    procedure Delete_Children (Container : in out Tree;
                              Parent    : in     Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Parent /= No_Element
                       or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error),
           Post => (Node_Count (Container) = Node_Count (Container)'Old -
                      Child_Count (Container, Parent)'Old) and then
                    Child_Count (Container, Parent) = 0
;
54/5
{AI12-0112-1}    procedure Copy_Subtree (Target   : in out Tree;
                           Parent   : in     Cursor;
                           Before   : in     Cursor;
                           Source   : in     Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                       or else raise Program_Error) and then
                    (Parent /= No_Element
                       or else raise Constraint_Error) and then
                    (Meaningful_For (Target, Parent)
                       or else raise Program_Error) and then
                    (Meaningful_For (Target, Before)
                       or else raise Program_Error) and then
                    (Before = No_Element or else
                       Target.Parent (Before) = Parent
                       or else raise Constraint_Error) and then
                    (not Is_Root (Source)
                       or else raise Constraint_Error),
           Post => Node_Count (Target) =
                   Node_Count (Target)'Old + Subtree_Node_Count (Source),
           Global => in all
;
54.1/5
{AI12-0112-1}    procedure Copy_Local_Subtree (Target   : in out Tree;
                                 Parent   : in     Cursor;
                                 Before   : in     Cursor;
                                 Source   : in     Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                       or else raise Program_Error) and then
                    (Parent /= No_Element
                       or else raise Constraint_Error) and then
                    (Meaningful_For (Target, Parent)
                       or else raise Program_Error) and then
                    (Meaningful_For (Target, Before)
                       or else raise Program_Error) and then
                    (Before = No_Element or else
                       Target.Parent (Before) = Parent
                       or else raise Constraint_Error) and then
                    (Meaningful_For (Target, Source)
                       or else raise Program_Error) and then
                    (not Is_Root (Source)
                       or else raise Constraint_Error),
           Post => Node_Count (Target) = Node_Count (Target)'Old +
                      Subtree_Node_Count (Target, Source);
54.2/5
{AI12-0112-1}    procedure Copy_Subtree (Target   : in out Tree;
                           Parent   : in     Cursor;
                           Before   : in     Cursor;
                           Source   : in     Tree;
                           Subtree  : in     Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                       or else raise Program_Error) and then
                    (Parent /= No_Element
                       or else raise Constraint_Error) and then
                    (Meaningful_For (Target, Parent)
                       or else raise Program_Error) and then
                    (Meaningful_For (Target, Before)
                       or else raise Program_Error) and then
                    (Before = No_Element or else
                       Target.Parent (Before) = Parent
                       or else raise Constraint_Error) and then
                    (Meaningful_For (Source, Subtree)
                       or else raise Program_Error) and then
                    (not Is_Root (Source, Subtree)
                       or else raise Constraint_Error),
           Post => Node_Count (Target) = Node_Count (Target)'Old +
                      Subtree_Node_Count (Source, Subtree);
55/5
{AI12-0112-1}    procedure Splice_Subtree (Target   : in out Tree;
                             Parent   : in     Cursor;
                             Before   : in     Cursor;
                             Source   : in out Tree;
                             Position : in out Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                       or else raise Program_Error) and then
                   (not Tampering_With_Cursors_Prohibited (Source)
                       or else raise Program_Error) and then
                   (Parent /= No_Element
                       or else raise Constraint_Error) and then
                   (Meaningful_For (Target, Parent)
                       or else raise Program_Error) and then
                   (Meaningful_For (Target, Before)
                       or else raise Program_Error) and then
                   (Before = No_Element or else
                    Target.Parent (Before) /= Parent
                       or else raise Constraint_Error) and then
                   (Position /= No_Element
                       or else raise Constraint_Error) and then
                   (Has_Element (Source, Position)
                       or else raise Program_Error) and then
                   (Target'Has_Same_Object (Source) or else
                    Position = Before or else
                    Is_Ancestor_Of (Target, Position, Parent)
                       or else raise Constraint_Error),
           Post => (declare
                       Org_Sub_Count renames 
                          Subtree_Node_Count (Source, Position)'Old;
                       Org_Target_Count renames Node_Count (Target)'Old;
                    begin
                      (if not Target'Has_Same_Object (Source) then
                          Node_Count (Target) = Org_Target_Count +
                             Org_Sub_Count and then
                          Node_Count (Source) = Node_Count (Source)'Old -
                             Org_Sub_Count and then
                          Has_Element (Target, Position)
                       else
                          Target.Parent (Position) = Parent and then
                          Node_Count (Target) = Org_Target_Count))
;
56/5
{AI12-0112-1}    procedure Splice_Subtree (Container: in out Tree;
                             Parent   : in     Cursor;
                             Before   : in     Cursor;
                             Position : in     Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                       or else raise Program_Error) and then
                   (Parent /= No_Element
                       or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error) and then
                   (Meaningful_For (Container, Before)
                      or else raise Program_Error) and then
                   (Before = No_Element or else
                    Container.Parent (Before) /= Parent
                      or else raise Constraint_Error) and then
                   (Position /= No_Element
                      or else raise Constraint_Error) and then
                   (Has_Element (Container, Position)
                      or else raise Program_Error) and then
                   (Position = Before or else
                    Is_Ancestor_Of (Container, Position, Parent)
                      or else raise Constraint_Error),
           Post => (Node_Count (Container) =
                      Node_Count (Container)'Old and then
                    Container.Parent (Position) = Parent)
;
57/5
{AI12-0112-1}    procedure Splice_Children (Target          : in out Tree;
                              Target_Parent   : in     Cursor;
                              Before          : in     Cursor;
                              Source          : in out Tree;
                              Source_Parent   : in     Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                       or else raise Program_Error) and then
                   (not Tampering_With_Cursors_Prohibited (Source)
                       or else raise Program_Error) and then
                   (Target_Parent /= No_Element
                       or else raise Constraint_Error) and then
                   (Meaningful_For (Target, Target_Parent)
                       or else raise Program_Error) and then
                   (Meaningful_For (Target, Before)
                       or else raise Program_Error) and then
                   (Source_Parent /= No_Element
                       or else raise Constraint_Error) and then
                   (Meaningful_For (Source, Source_Parent)
                       or else raise Program_Error) and then
                   (Before = No_Element or else
                    Parent (Target, Before) /= Target_Parent
                       or else raise Constraint_Error) and then
                   (Target'Has_Same_Object (Source) (Target, Source) or else
                    Target_Parent = Source_Parent or else
                    Is_Ancestor_Of (Target, Source_Parent, Target_Parent)
                       or else raise Constraint_Error),
           Post => (declare
                       Org_Child_Count renames
                          Child_Count (Source, Source_Parent)'Old;
                       Org_Target_Count renames Node_Count (Target)'Old;
                    begin
                      (if not Target'Has_Same_Object (Source) then
                          Node_Count (Target) = Org_Target_Count +
                             Org_Child_Count and then
                          Node_Count (Source) = Node_Count (Source)'Old -
                             Org_Child_Count
                       else
                          Node_Count (Target) = Org_Target_Count))
;
58/5
{AI12-0112-1}    procedure Splice_Children (Container       : in out Tree;
                              Target_Parent   : in     Cursor;
                              Before          : in     Cursor;
                              Source_Parent   : in     Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Target_Parent /= No_Element
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Target_Parent)
                      or else raise Program_Error) and then
                   (Meaningful_For (Container, Before)
                      or else raise Program_Error) and then
                   (Source_Parent /= No_Element
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Source_Parent)
                      or else raise Program_Error) and then
                   (Before = No_Element or else
                    Parent (Container, Before) /= Target_Parent
                      or else raise Constraint_Error) and then
                   (Target_Parent = Source_Parent or else
                    Is_Ancestor_Of (Container, Source_Parent, Target_Parent)
                      or else raise Constraint_Error),
           Post => Node_Count (Container) = Node_Count (Container)'Old
;
59/5
{AI12-0112-1}    function Parent (Position : Cursor) return Cursor
      with Nonblocking, Global => (in alluse null),
           Post => (if Position = No_Element or else
                       Is_Root (Position) then Parent'Result = No_Element
                    else True)
;
59.1/5
{AI12-0112-1}    function Parent (Container : Tree;
                    Position  : Cursor) return Cursor
      with Nonblocking, Global => null, Use_Formal => null,
           Pre  => Meaningful_For (Container, Position) 
                      or else raise Program_Error,
           Post => (if Position = No_Element or else
                      Is_Root (Container, Position)
                      then Parent'Result = No_Element
                    else Has_Element (Container, Parent'Result));
60/5
{AI12-0112-1}    function First_Child (Parent : Cursor) return Cursor
      with Nonblocking, Global => (in alluse null),
           Pre  => Parent /= No_Element or else raise Constraint_Error
;
60.1/5
{AI12-0112-1}    function First_Child (Container : Tree;
                         Parent    : Cursor) return Cursor
      with Nonblocking, Global => null, Use_Formal => null,
           Pre  => (Parent /= No_Element
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error),
           Post => First_Child'Result = No_Element or else
                   Has_Element (Container, First_Child'Result);
61/5
{AI12-0112-1}    function First_Child_Element (Parent : Cursor) return Element_Type
      with Nonblocking,
           Global => in all, Use_Formal => Element_Type,
           Pre  => (Parent /= No_Element and then
                    Last_Child (Parent) /= No_Element)
                        or else raise Constraint_Error
;
61.1/5
{AI12-0112-1}    function First_Child_Element (Container : Tree;
                                 Parent    : Cursor) return Element_Type
      with Nonblocking,
           Global => null, Use_Formal => Element_Type,
           Pre  => (Parent /= No_Element
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error) and then
                   (First_Child (Container, Parent) /= No_Element
                      or else raise Constraint_Error);
62/5
{AI12-0112-1}    function Last_Child (Parent : Cursor) return Cursor
      with Nonblocking, Global => (in alluse null),
           Pre  => Parent /= No_Element or else raise Constraint_Error
;
62.1/5
{AI12-0112-1}    function Last_Child (Container : Tree;
                        Parent    : Cursor) return Cursor
      with Nonblocking, Global => null, Use_Formal => null,
           Pre  => (Parent /= No_Element
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error),
           Post => Last_Child'Result = No_Element or else
                   Has_Element (Container, Last_Child'Result);
63/5
{AI12-0112-1}    function Last_Child_Element (Parent : Cursor) return Element_Type
      with Nonblocking =>,
           Global => in all, Use_Formal => Element_Type,
           Pre  => (Parent /= No_Element and then
                    Last_Child (Parent) /= No_Element)
                        or else raise Constraint_Error
;
63.1/5
{AI12-0112-1}    function Last_Child_Element (Container : Tree;
                                Parent    : Cursor) return Element_Type
      with Nonblocking,
           Global => null, Use_Formal => Element_Type,
           Pre  => (Parent /= No_Element
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error) and then
                   (Last_Child (Container, Parent) /= No_Element
                      or else raise Constraint_Error);
64/5
{AI12-0112-1}    function Next_Sibling (Position : Cursor) return Cursor
      with Nonblocking, Global => (in alluse null),
           Post => (if Position = No_Element
                       then Next_Sibling'Result = No_Element
                    else True)
;
64.1/5
{AI12-0112-1}    function Next_Sibling (Container : Tree;
                          Position  : Cursor) return Cursor
      with Nonblocking, Global => null, Use_Formal => null,
           Pre  => Meaningful_For (Container, Position)
                      or else raise Program_Error,
           Post => (if Next_Sibling'Result = No_Element then
                      Position = No_Element or else
                      Is_Root (Container, Position) or else
                      Last_Child (Container, Parent (Container, Position))
                         = Position
                    else Has_Element (Container, Next_Sibling'Result));
65/5
{AI12-0112-1}    procedure Next_Sibling (Position : in out Cursor)
      with Nonblocking, Global => (in alluse null)
;
65.1/5
{AI12-0112-1}    procedure Next_Sibling (Container : in     Tree;
                           Position  : in out Cursor)
      with Nonblocking, Global => null, Use_Formal => null,
           Pre  => Meaningful_For (Container, Position)
                      or else raise Program_Error,
           Post => (if Position /= No_Element
                    then Has_Element (Container, Position));
66/5
{AI12-0112-1}    function Previous_Sibling (Position : Cursor) return Cursor
      with Nonblocking, Global => (in alluse null),
           Post => (if Position = No_Element
                       then Previous_Sibling'Result = No_Element
                    else True)
;
66.1/5
{AI12-0112-1}    function Previous_Sibling (Container : Tree;
                              Position  : Cursor) return Cursor
      with Nonblocking, Global => null, Use_Formal => null,
           Pre  => Meaningful_For (Container, Position)
                      or else raise Program_Error,
           Post => (if Previous_Sibling'Result = No_Element then
                      Position = No_Element or else
                      Is_Root (Container, Position) or else
                      First_Child (Container, Parent (Container, Position))
                         = Position
                    else Has_Element (Container, Previous_Sibling'Result));
67/5
{AI12-0112-1}    procedure Previous_Sibling (Position : in out Cursor)
      with Nonblocking, Global => (in alluse null)
;
67.1/5
{AI12-0112-1}    procedure Previous_Sibling (Container : in     Tree;
                                  Position  : in out Cursor)
      with Nonblocking, Global => null, Use_Formal => null,
           Pre  => Meaningful_For (Container, Position)
                      or else raise Program_Error,
           Post => (if Position /= No_Element
                    then Has_Element (Container, Position));
68/5
{AI05-0136-1} {AI05-0248-1} {AI12-0112-1}    procedure Iterate_Children
     (Parent  : in Cursor;
      Process : not null access procedure (Position : in Cursor))
      with Allows_Exit,
           Pre    => Parent /= No_Element or else raise Constraint_Error,
           Global => (in alluse null)
;
68.1/5
{AI12-0112-1}    procedure Iterate_Children
     (Container : in Tree;
      Parent    : in Cursor;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit,
           Pre  => (Parent /= No_Element 
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error);
69/5
{AI05-0136-1} {AI05-0248-1} {AI12-0112-1}    procedure Reverse_Iterate_Children
     (Parent  : in Cursor;
      Process : not null access procedure (Position : in Cursor))
      with Allows_Exit,
           Pre    => Parent /= No_Element or else raise Constraint_Error,
           Global => (in alluse null)
;
69.1/5
{AI12-0112-1}    procedure Reverse_Iterate_Children
     (Container : in Tree;
      Parent    : in Cursor;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit,
           Pre  => (Parent /= No_Element 
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error);
70/5
{AI05-0212-1} {AI12-0112-1} {AI12-0266-1}    function Iterate_Children (Container : in Tree; Parent : in Cursor)
      return Tree_Iterator_Interfaces.Parallel_Reversible_Iterator Reversible_Iterator'Class
      with Pre  => (Parent /= No_Element 
                      or else raise Constraint_Error) and then
                   (Meaningful_For (Container, Parent)
                      or else raise Program_Error),
           Post => Tampering_With_Cursors_Prohibited (Container)
;
70.1/5
{AI05-0111-1}    package Stable is
70.2/5
{AI05-0111-1}       type Tree (Base : not null access Multiway_Trees.Tree) is
         tagged limited private
         with Constant_Indexing => Constant_Reference,
              Variable_Indexing => Reference,
              Default_Iterator  => Iterate,
              Iterator_Element  => Element_Type,
              Stable_Properties => (Node_Count),
              Global            => null,
              Default_Initial_Condition => Node_Count (Tree) = 1;
      pragma Preelaborable_Initialization(Tree);
70.3/5
{AI05-0111-1}       type Cursor is private;
      pragma Preelaborable_Initialization(Cursor);
70.4/5
{AI05-0111-1}       Empty_Tree : constant Tree;
70.5/5
{AI05-0111-1}       No_Element : constant Cursor;
70.6/5
{AI05-0111-1}       function Has_Element (Position : Cursor) return Boolean
         with Nonblocking, Global => (in alluse null);
70.7/5
{AI05-0111-1}       package Tree_Iterator_Interfaces is new
         Ada.Iterator_Interfaces (Cursor, Has_Element);
70.8/5
{AI05-0111-1}       procedure Assign (Target : in out Multiway_Trees.Tree;
                        Source : in Tree)
         with Post => Node_Count (Source) = Node_Count (Target);
70.9/5
{AI05-0111-1}       function Copy (Source : Multiway_Trees.Tree) return Tree
         with Post => Node_Count (Copy'Result) = Node_Count (Source);
70.10/5
{AI05-0111-1}       type Constant_Reference_Type
            (Element : not null access constant Element_Type) is private
         with Implicit_Dereference => Element,
              Nonblocking, Global => null,
              Default_Initial_Condition => (raise Program_Error);
70.11/5
{AI05-0111-1}       type Reference_Type
            (Element : not null access Element_Type) is private
         with Implicit_Dereference => Element,
              Nonblocking, Global => null,
              Default_Initial_Condition => (raise Program_Error);
70.12/5
{AI05-0111-1}       -- Additional subprograms as described in the text
      -- are declared here.
70.13/5
{AI05-0111-1}    private
70.14/5
{AI05-0111-1}       ... -- not specified by the language
70.15/5
{AI05-0111-1}    end Stable;
71/3
private
   ... -- not specified by the language
end Ada.Containers.Multiway_Trees;
72/3
{AI05-0136-1} 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_Subtree, and "=" on tree values return an unspecified value. The exact arguments and number of calls of this generic formal function by the functions Find, Reverse_Find, Equal_Subtree, and "=" on tree values are unspecified.
73/3
{AI05-0136-1} The type Tree is used to represent trees. The type Tree needs finalization (see 7.6).
74/3
{AI05-0136-1} {AI05-0248-1} Empty_Tree represents the empty Tree object. It contains only the root node (Node_Count (Empty_Tree) returns 1). If an object of type Tree is not otherwise initialized, it is initialized to the same value as Empty_Tree.
75/3
{AI05-0136-1} 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.
76/3
{AI05-0136-1} The predefined "=" operator for type Cursor returns True if both cursors are No_Element, or designate the same element in the same container.
77/3
{AI05-0136-1} Execution of the default implementation of the Input, Output, Read, or Write attribute of type Cursor raises Program_Error.
78/3
{AI05-0136-1} {AI05-0248-1} {AI05-0262-1} Tree'Write for a Tree object T writes Node_Count(T) - 1 elements of the tree to the stream. It also may write additional information about the tree.
79/3
{AI05-0136-1} {AI05-0248-1} {AI05-0262-1} Tree'Read reads the representation of a tree from the stream, and assigns to Item a tree with the same elements and structure as was written by Tree'Write.
79.a/3
Ramification: Streaming more elements than the container holds is wrong. For implementation implications of this rule, see the Implementation Note in A.18.2.
80/5
{AI05-0136-1} {AI12-0111-1} {AI12-0112-1} [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.] When tampering with cursors is prohibited for a particular tree object T, Program_Error is propagated by the finalization of T[, as well as by a call that passes T to certain of the operations of this package, as indicated by the precondition of such an operation]. Similarly, when tampering with elements is prohibited for T, Program_Error is propagated by a call that passes T to certain of other operations of this package, as indicated by the precondition of such an operation.
Paragraphs 81 through 90 are removed as preconditions now describe these rules.
81/5
{AI05-0136-1} {AI12-0111-1} {AI12-0112-1} A subprogram is said to tamper with cursors of a tree object L if:
82/5
it inserts or deletes elements of T, that is, it calls the Clear, Delete_Leaf, Insert_Child, Delete_Children, Delete_Subtree, or Copy_Subtree procedures with T as a parameter; or
82.a/5
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. 
83/5
{AI05-0136-1} {AI05-0248-1} it reorders the elements of T, that is, it calls the Splice_Subtree or Splice_Children procedures with T as a parameter; or
84/5
it finalizes T; or
85/5
it calls Assign with T as the Target parameter; or
85.a.1/3
Ramification: We don't need to explicitly mention assignment_statement, because that finalizes the target object as part of the operation, and finalization of an object is already defined as tampering with cursors.
86/5
it calls the Move procedure with T as a parameter.
86.a/5
Reason: Swap copies elements rather than reordering them, so it doesn't tamper with cursors.
87/5
{AI05-0136-1} {AI12-0111-1} {AI12-0112-1} A subprogram is said to tamper with elements of a tree object T if:
88/5
it tampers with cursors of T; or
89/5
it replaces one or more elements of T, that is, it calls the Replace_Element or Swap procedures with T as a parameter.
89.a/5
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. 
89.a.1/3
Ramification: Assign is defined in terms of Clear and Replace_Element, so we don't need to mention it explicitly. Similarly, we don't need to explicitly mention assignment_statement, because that finalizes the target object as part of the operation, and finalization of an object is already defined as tampering with the element.
90/5
{AI05-0265-1} {AI12-0110-1} {AI12-0111-1} {AI12-0112-1} When tampering with cursors is prohibited for a particular tree object T, Program_Error is propagated by a call of any language-defined subprogram that is defined to tamper with the cursors of T, leaving T unmodified. Similarly, when tampering with elements is prohibited for a particular tree object T, Program_Error is propagated by a call of any language-defined subprogram that is defined to tamper with the elements of T [(or tamper with the cursors of T)], leaving T unmodified. These checks are made before any other defined behavior of the body of the language-defined subprogram.
90.a/5
Proof: Tampering with elements includes tampering with cursors, so we mention it only from completeness in the second sentence. 
91/5
{AI12-0112-1} function Has_Element (Position : Cursor) return Boolean
   with Nonblocking, Global => (in alluse null)
;
92/3
Returns True if Position designates an element, and returns False otherwise. [In particular, Has_Element returns False if the cursor designates a root node or equals No_Element.]
92.a/3
To be honest: {AI05-0005-1} {AI05-0136-1} This function might not detect cursors that designate deleted elements; such cursors are invalid (see below) and the result of calling Has_Element with an invalid cursor is unspecified (but not erroneous). 
92.1/5
function Has_Element (Container : Tree; Position : Cursor)
   return Boolean
   with Nonblocking, Global => null, Use_Formal => null;
92.2/5
{AI12-0112-1} Returns True if Position designates an element in Container, and returns False otherwise. [In particular, Has_Element returns False if the cursor designates a root node or equals No_Element.]
93/3
function Equal_Subtree (Left_Position : Cursor;
                        Right_Position: Cursor) return Boolean;
94/3
{AI05-0136-1} {AI05-0248-1} {AI05-0262-1} {AI05-0264-1} If Left_Position or Right_Position equals No_Element, propagates Constraint_Error. If the number of child nodes of the element designated by Left_Position is different from the number of child nodes of the element designated by Right_Position, the function returns False. If Left_Position designates a root node and Right_Position does not, the function returns False. If Right_Position designates a root node and Left_Position does not, the function returns False. Unless both cursors designate a root node, the elements are compared using the generic formal equality operator. If the result of the element comparison is False, the function returns False. Otherwise, it calls Equal_Subtree on a cursor designating each child element of the element designated by Left_Position and a cursor designating the corresponding child element of the element designated by Right_Position. If any such call returns False, the function returns False; otherwise, it returns True. Any exception raised during the evaluation of element equality is propagated.
94.a/3
Ramification: Left_Position and Right_Position do not need to be from the same tree. 
94.b/3
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_Subtree is called, and thus an implementation can call it as many or as few times as it needs to get the correct answer. Specifically, there is no requirement to call the formal equality or Equal_Subtree additional times once the answer has been determined. 
95/3
function "=" (Left, Right : Tree) return Boolean;
96/3
{AI05-0136-1} {AI05-0262-1} If Left and Right denote the same tree object, then the function returns True. Otherwise, it calls Equal_Subtree with cursors designating the root nodes of Left and Right; the result is returned. Any exception raised during the evaluation of Equal_Subtree is propagated.
96.a/3
Implementation Note: Similar considerations apply here as apply to Equal_Subtree. The actual number of calls performed is unspecified. 
96.1/5
function Tampering_With_Cursors_Prohibited
   (Container : Tree) return Boolean
   with Nonblocking, Global => null, Use_Formal => null;
96.2/5
{AI12-0112-1} Returns True if tampering with cursors or tampering with elements is currently prohibited for Container, and returns False otherwise.
96.b/5
Reason: {AI12-0112-1} Prohibiting tampering with elements also needs to prohibit tampering with cursors, as deleting an element is similar to replacing it. 
96.c/5
Implementation Note: {AI12-0112-1} Various contracts elsewhere in this specification require that this function is implemented with synchronized data. Moreover, it is possible for tampering to be prohibited by multiple operations (sequentiually or in parallel). Therefore, tampering needs to be implemented with an atomic or protected counter. The counter is initialized to zero, and is incremented when tampering is prohibited, and decremented when leaving an area that prohibited tampering. Function Tampering_With_Cursors_Prohibited returns True if the counter is nonzero. (Note that any case where the result is not well-defined for one task is incorrect use of shared variables and would be erroneous by the rules of 9.10, so no special protection is needed to read the counter.) 
96.3/5
function Tampering_With_Elements_Prohibited
   (Container : Tree) return Boolean
   with Nonblocking, Global => null, Use_Formal => null;
96.4/5
{AI12-0112-1} Always returns False[, regardless of whether tampering with elements is prohibited].
96.d/5
Reason: {AI12-0111-1} A definite element cannot change size, so we allow operations that tamper with elements even when tampering with elements is prohibited. That's not true for the indefinite containers, which is why this kind of tampering exists. 
96.5/5
function Is_Empty (Container : Tree) return Boolean
   with Nonblocking, Global => null, Use_Formal => null,
        Post => Is_Empty'Result = (Node_Count (Container) = 1);
96.6/5
{AI05-0136-1} {AI12-0112-1} Returns True if Container is empty.
96.e/5
Ramification: An empty tree contains just the root node. 
97/5
{AI12-0112-1} function Node_Count (Container : Tree) return Count_Type
   with Nonblocking, Global => null, Use_Formal => null
;
98/3
{AI05-0136-1} Node_Count returns the number of nodes in Container.
98.a/3
Ramification: Since all tree objects have a root node, this can never return a value of 0. Node_Count (Some_Tree) should always equal Subtree_Node_Count (Root (Some_Tree)). 
99/5
{AI12-0112-1} function Subtree_Node_Count (Position : Cursor) return Count_Type
   with Nonblocking, Global => in all, Use_Formal => null)
;
100/3
{AI05-0136-1} {AI05-0248-1} If Position is No_Element, Subtree_Node_Count returns 0; otherwise, Subtree_Node_Count returns the number of nodes in the subtree that is rooted by Position.
101/5
function Subtree_Node_Count Is_Empty (Container : Tree; Position : Cursor)
   
return Count_Type
   with Pre => Meaningful_For (Container, Position) 
                   or else raise Program_Error,
        Nonblocking, Global => null, Use_Formal => null
 Boolean;
102/5
{AI05-0136-1} {AI12-0112-1} If Position is No_Element, Subtree_Node_Count returns 0; otherwise, Subtree_Node_Count returns the number of nodes in the subtree of Container that is rooted by Position Equivalent to Node_Count (Container) = 1.
102.a/5
This paragraph was deleted.Ramification: {AI12-0112-1} An empty tree contains just the root node.
102.b/5
Reason: {AI12-0112-1} We raise Program_Error if Position belongs to some other container because we have promised to read only the container passed to this function. Determining the answer requires reading the container that Position belongs to, which we've promised not to do if it is not Container. We don't make this check for functions like Has_Element and Is_Root which do not require reading another container to determine the answer, but we do make it for most functions. 
103/5
{AI12-0112-1} function Depth (Position : Cursor) return Count_Type
   with Nonblocking, Global => (in alluse null)
;
104/3
{AI05-0136-1} {AI05-0248-1} If Position equals No_Element, Depth returns 0; otherwise, Depth returns the number of ancestor nodes of the node designated by Position (including the node itself).
104.a/3
Ramification: Depth (Root (Some_Tree)) = 1. 
104.1/5
function Depth (Container : Tree; Position : Cursor)
   return Count_Type
   with Pre => Meaningful_For (Container, Position) 
                  or else raise Program_Error,
        Nonblocking, Global => null, Use_Formal => null;
104.2/5
{AI12-0112-1} If Position equals No_Element, Depth returns 0; otherwise, Depth returns the number of ancestor nodes of the node of Container designated by Position (including the node itself).
105/5
{AI12-0112-1} function Is_Root (Position : Cursor) return Boolean
   with Nonblocking, Global => (in alluse null)
;
106/3
{AI05-0136-1} {AI05-0248-1} Is_Root returns True if the Position designates the root node of some tree; and returns False otherwise.
106.1/5
function Is_Root (Container : Tree; Position : Cursor)
   return Boolean
   with Nonblocking, Global => null, Use_Formal => null;
106.2/5
{AI12-0112-1} Is_Root returns True if the Position designates the root node of Container; and returns False otherwise.
106.a/5
Ramification: The two parameter Is_Root returns False even if Position is the root of some other tree than Container. 
107/5
{AI12-0112-1} function Is_Leaf (Position : Cursor) return Boolean
   with Nonblocking, Global => (in alluse null)
;
108/3
{AI05-0136-1} Is_Leaf returns True if Position designates a node that does not have any child nodes; and returns False otherwise.
108.a/3
Ramification: Is_Leaf returns False if passed No_Element, since No_Element does not designate a node. Is_Leaf can be passed a cursor that designates the root node; Is_Leaf will return True if passed the root node of an empty tree. 
108.1/5
function Is_Leaf (Container : Tree; Position : Cursor)
   return Boolean
   with Pre => Meaningful_For (Container, Position) 
                  or else raise Program_Error,
        Nonblocking, Global => null, Use_Formal => null;
108.2/5
{AI12-0112-1} Is_Leaf returns True if Position designates a node in Container that does not have any child nodes; and returns False otherwise.
108.3/5
function Is_Ancestor_Of (Container : Tree; Position : Cursor)
       Parent   : Cursor;
       Position : Cursor) return Boolean
   with Pre => (Meaningful_For (Container, Position)
                  or else raise Program_Error) and then
               (Meaningful_For (Container, Parent)
                  or else raise Program_Error),
        Nonblocking, Global => null, Use_Formal => null;
108.4/5
{AI12-0112-1} Is_Ancestor_Of returns True if Parent designates an ancestor node of Position (including Position itself), and returns False otherwise.
109/5
{AI12-0112-1} function Root (Container : Tree) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Post => Root'Result /= No_Element and then
                not Has_Element (Container, Root'Result)
;
110/3
{AI05-0136-1} Root returns a cursor that designates the root node of Container.
110.a/3
Ramification: There is always a root node, even in an empty container, so this function never returns No_Element.
111/5
{AI12-0112-1} procedure Clear (Container : in out Tree)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => Node_Count (Container) = 1
;
112/3
{AI05-0136-1} Removes all the elements from Container.
112.a/3
Ramification: The root node is not removed; all trees have a root node. 
113/5
function Element (Position : Cursor) return Element_Type
   with Pre => (Position /= No_Element or else
                  raise Constraint_Error) and then
               (Has_Element (Position) or else raise Program_Error),
        Nonblocking,
        Global => in all, Use_Formal => Element_Type
;
114/5
{AI05-0136-1} {AI12-0112-1} If Position equals No_Element, then Constraint_Error is propagated; if Position designates the root node of a tree, then Program_Error is propagated. Otherwise, Element returns the element designated by Position.
114.a/3
Ramification: The root node does not contain an element, so that value cannot be read or written. 
114.1/5
function Element (Container : Tree;
                  Position  : Cursor) return Element_Type
   with Pre => (Position /= No_Element
                  or else raise Constraint_Error) and then
               (Has_Element (Container, Position)  
                  or else raise Program_Error),
        Nonblocking, Global => null, Use_Formal => Element_Type;
114.2/5
{AI12-0112-1} Element returns the element designated by Position in Container.
115/5
procedure Replace_Element (Container : in out Tree;
                           Position  : in     Cursor;
                           New_item  : in     Element_Type)
   with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                   or else raise Program_Error) and then
                (Position /= No_Element 
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position) 
                   or else raise Program_Error)
;
116/5
{AI05-0136-1} {AI05-0264-1} {AI12-0112-1} {AI12-0196-1} If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container (including if it designates the root node), then Program_Error is propagated. Otherwise, Replace_Element assigns the value New_Item to the element designated by Position. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object [(including itself)].
117/5
procedure Query_Element
  (Position : in Cursor;
   Process  : not null access procedure (Element : in Element_Type))
   with Pre  => (Position /= No_Element 
                   or else raise Constraint_Error) and then
                (Has_Element (Position) 
                   or else raise Program_Error),
     Global => in all
;
118/5
{AI05-0136-1} {AI05-0265-1} {AI12-0112-1} If Position equals No_Element, then Constraint_Error is propagated; if Position designates the root node of a tree, then Program_Error is propagated. Otherwise, Query_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of the tree that contains the element designated by Position is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
118.1/5
procedure Query_Element
  (Container : in Tree;
   Position  : in Cursor;
   Process   : not null access procedure (Element : in Element_Type))
   with Pre  => (Position /= No_Element 
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position) 
                   or else raise Program_Error);
118.2/5
{AI12-0112-1} Query_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
119/5
procedure Update_Element
  (Container : in out Tree;
   Position  : in     Cursor;
   Process   : not null access procedure
                   (Element : in out Element_Type))
   with Pre  => (Position /= No_Element 
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position) 
                   or else raise Program_Error)
;
120/5
{AI05-0136-1} {AI05-0264-1} {AI05-0265-1} {AI12-0112-1} If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container (including if it designates the root node), then Program_Error is propagated. Otherwise, Update_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
121/3
If Element_Type is unconstrained and definite, then the actual Element parameter of Process.all shall be unconstrained.
121.a/3
Ramification: This means that the elements cannot be directly allocated from the heap; it must be possible to change the discriminants of the element in place. 
122/5
{AI12-0112-1} type Constant_Reference_Type
      (Element : not null access constant Element_Type) is private
   with Implicit_Dereference => Element,
        Nonblocking, Global => in out synchronized,
        Default_Initial_Condition => (raise Program_Error)
;
123/5
{AI12-0112-1} type Reference_Type (Element : not null access Element_Type) is private
   with Implicit_Dereference => Element,
        Nonblocking, Global => in out synchronized,
        Default_Initial_Condition => (raise Program_Error)
;
124/3
{AI05-0212-1} The types Constant_Reference_Type and Reference_Type need finalization.
125/5
This paragraph was deleted.{AI12-0112-1} The default initialization of an object of type Constant_Reference_Type or Reference_Type propagates Program_Error.
125.a/3
Reason: It is expected that Reference_Type (and Constant_Reference_Type) will be a controlled type, for which finalization will have some action to terminate the tampering check for the associated container. If the object is created by default, however, there is no associated container. Since this is useless, and supporting this case would take extra work, we define it to raise an exception. 
126/5
{AI12-0112-1} function Constant_Reference (Container : aliased in Tree;
                             Position  : in Cursor)
   return Constant_Reference_Type
   with Pre  => (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position) 
                   or else raise Program_Error),
        Post   => Tampering_With_Cursors_Prohibited (Container),
        Nonblocking, Global => null, Use_Formal => null
;
127/3
{AI05-0212-1} {AI05-0269-1} This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to an individual element of a tree given a cursor.
128/5
{AI05-0212-1} {AI05-0265-1} {AI12-0112-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. Otherwise, Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Tampering with the elements of Container is prohibited while the object returned by Constant_Reference exists and has not been finalized.
129/5
{AI12-0112-1} function Reference (Container : aliased in out Tree;
                    Position  : in Cursor)
   return Reference_Type
   with Pre  => (Position /= No_Element 
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position) 
                   or else raise Program_Error),
        Post   => Tampering_With_Cursors_Prohibited (Container),
        Nonblocking, Global => null, Use_Formal => null
;
130/3
{AI05-0212-1} {AI05-0269-1} This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to an individual element of a tree given a cursor.
131/5
{AI05-0212-1} {AI05-0265-1} {AI12-0112-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. Otherwise, Reference returns an object whose discriminant is an access value that designates the element designated by Position. Tampering with the elements of Container is prohibited while the object returned by Reference exists and has not been finalized.
132/5
{AI12-0112-1} procedure Assign (Target : in out Tree; Source : in Tree)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error,
        Post => Node_Count (Source) = Node_Count (Target)
;
133/3
{AI05-0136-1} {AI05-0248-1} If Target denotes the same object as Source, the operation has no effect. Otherwise, the elements of Source are copied to Target as for an assignment_statement assigning Source to Target.
133.a/3
Ramification: Each 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. 
133.b/3
Discussion: {AI05-0005-1} This routine exists for compatibility with the bounded tree container. For an unbounded tree, Assign(A, B) and A := B behave identically. For a bounded tree, := will raise an exception if the container capacities are different, while Assign will not raise an exception if there is enough room in the target. 
134/5
{AI12-0112-1} function Copy (Source : Tree) return Tree
   with Post =>
           Node_Count (Copy'Result) = Node_Count (Source) and then
           not Tampering_With_Elements_Prohibited (Copy'Result) and then
           not Tampering_With_Cursors_Prohibited (Copy'Result)
;
135/3
{AI05-0136-1} Returns a tree with the same structure as Source and whose elements are initialized from the corresponding elements of Source.
136/5
{AI12-0112-1} procedure Move (Target : in out Tree;
                Source : in out Tree)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error) and then
                (not Tampering_With_Cursors_Prohibited (Source)
                   or else raise Program_Error),
        Post => (if not Target'Has_Same_Storage (Source) then
               Node_Count (Target) = Node_Count (Source'Old) and then
               Node_Count (Source) = 1)
;
137/3
{AI05-0136-1} {AI05-0248-1} If Target denotes the same object as Source, then the operation has no effect. Otherwise, Move first calls Clear (Target). Then, the nodes other than the root node in Source are moved to Target (in the same positions). After Move completes, Node_Count (Target) is the number of nodes originally in Source, and Node_Count (Source) is 1.
138/5
procedure Delete_Leaf (Container : in out Tree;
                       Position  : in out Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Position /= No_Element 
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error) and then
                (Is_Leaf (Container, Position)
                   or else raise Constraint_Error),
        Post =>
           Node_Count (Container)'Old = Node_Count (Container) + 1 and then
           Position = No_Element
;
139/5
{AI05-0136-1} {AI05-0248-1} {AI12-0112-1} If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container (including if it designates the root node), then Program_Error is propagated. If the element designated by position has any child elements, then Constraint_Error is propagated. Otherwise, Delete_Leaf removes (from Container) the element designated by Position, and. Finally, Position is set to No_Element.
139.a/3
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).
139.b/3
The root node cannot be deleted. 
140/5
procedure Delete_Subtree (Container : in out Tree;
                          Position  : in out Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Position /= No_Element 
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error),
        Post => Node_Count (Container)'Old = Node_Count (Container) +
                   Subtree_Node_Count (Container, Position)'Old and then
                Position = No_Element
;
141/5
{AI05-0136-1} {AI05-0264-1} {AI05-0269-1} {AI12-0112-1} If Position equals No_Element, then Constraint_Error is propagated. If Position does not designate an element in Container (including if it designates the root node), then Program_Error is propagated. Otherwise, Delete_Subtree removes (from Container) the subtree designated by Position (that is, all descendants of the node designated by Position including the node itself), and Position is set to No_Element.
141.a/3
Ramification: The root node cannot be deleted. To delete the entire contents of the tree, call Clear(Container).
142/5
procedure Swap (Container : in out Tree;
                I, J      : in     Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (I /= No_Element or else Constraint_Error) and then
                (J /= No_Element or else Constraint_Error) and then
                (Has_Element (Container, I)
                   or else raise Program_Error) and then
                (Has_Element (Container, J)
                   or else raise Program_Error)
;
143/5
{AI05-0136-1} {AI12-0112-1} If either I or J equals No_Element, then Constraint_Error is propagated. If either I or J do not designate an element in Container (including if either designates the root node), then Program_Error is propagated. Otherwise, Swap exchanges the values of the elements designated by I and J.
143.a/3
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 position of the elements do not change; for instance, the parent node and the first child node of I are unchanged by the operation.
143.b/3
The root nodes do not contain element values, so they cannot be swapped. 
143.c/3
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. 
144/5
{AI12-0112-1} function Find (Container : Tree;
               Item      : Element_Type)
   return Cursor
   with Post => (if Find'Result = No_Element then True
                 else Has_Element (Container, Find'Result))
;
145/3
{AI05-0136-1} {AI05-0262-1} Find searches the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at the root node. The search traverses the tree in a depth-first order. If no equal element is found, then Find returns No_Element. Otherwise, it returns a cursor designating the first equal element encountered.
146/5
function Find_In_Subtree (Position : Cursor;
                          Item     : Element_Type)
   return Cursor
   with Pre  => Position /= No_Element or else raise Constraint_Error,
        Post => (if Find_In_Subtree'Result = No_Element then True
                 else Has_Element (Find_In_Subtree'Result)),
        Global => in all
;
147/5
{AI05-0136-1} {AI05-0248-1} {AI05-0262-1} {AI12-0112-1} If Position equals No_Element, then Constraint_Error is propagated. Find_In_Subtree searches the subtree rooted by Position for an element equal to Item (using the generic formal equality operator). The search starts at the element designated by Position. The search traverses the subtree 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.
147.a/3
Ramification: Find_In_Subtree does not check any siblings of the element designated by Position. The root node does not contain an element, and therefore it can never be returned, but it can be explicitly passed to Position. 
147.1/5
{AI12-0112-1} function Find_In_Subtree (Container : Tree;
                          Position  : Cursor;
                          Item      : Element_Type)
   return Cursor
   with Pre  => (Position = No_Element 
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Position)
                   or else raise Program_Error),
        Post => (if Find_In_Subtree'Result = No_Element then True
                 else Has_Element (Container, Find_In_Subtree'Result));
147.2/5
{AI12-0112-1} Find_In_Subtree searches the subtree of Container rooted by Position for an element equal to Item (using the generic formal equality operator). The search starts at the element designated by Position. The search traverses the subtree 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.
148/5
function Ancestor_Find (Position : Cursor;
                        Item     : Element_Type)
   return Cursor
   with Pre  => Position /= No_Element or else raise Constraint_Error,
        Post => (if Ancestor_Find'Result = No_Element then True
                 else Has_Element (Container, Ancestor_Find'Result)),
        Global => in all
;
149/5
{AI05-0136-1} {AI05-0248-1} {AI12-0112-1} If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Ancestor_Find searches for an element equal to Item (using the generic formal equality operator). The search starts at the node 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. 
149.a/3
Ramification: {AI05-0248-1} No_Element is returned if Position is the root node. 
149.1/5
{AI12-0112-1} function Ancestor_Find (Container : Tree;
                        Position  : Cursor;
                        Item      : Element_Type)
   return Cursor
   with Pre  => (Position = No_Element 
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Position)
                   or else raise Program_Error),
        Post => (if Ancestor_Find'Result = No_Element then True
                 else Has_Element (Container, Ancestor_Find'Result));
149.2/5
{AI12-0112-1} Ancestor_Find searches for an element equal to Item (using the generic formal equality operator). The search starts at the node designated by Position in Container, 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.
150/3
function Contains (Container : Tree;
                   Item      : Element_Type) return Boolean;
151/3
{AI05-0136-1} Equivalent to Find (Container, Item) /= No_Element.
152/5
{AI12-0112-1} procedure Iterate
  (Container : in Tree;
   Process   : not null access procedure (Position : in Cursor))
   with Allows_Exit
;
153/4
{AI05-0136-1} {AI05-0265-1} {AI12-0069-1} Iterate calls Process.all with a cursor that designates each element in Container, starting from with the root node and proceeding in a depth-first order. Tampering with the cursors of Container is prohibited during the execution of a call on Process.all. Any exception raised by Process.all is propagated.
153.a/3
Ramification: Process is not called with the root node, which does not have an associated element. 
153.b/3
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.
153.c/3
See Iterate for vectors (A.18.2) for a suggested implementation of the check. 
154/5
procedure Iterate_Subtree
  (Position  : in Cursor;
   Process   : not null access procedure (Position : in Cursor))
   with Allows_Exit,
        Pre  => Position /= No_Element or else raise Constraint_Error,
        Global => in all
;
155/5
{AI05-0136-1} {AI05-0265-1} {AI12-0069-1} {AI12-0112-1} If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Iterate_Subtree calls Process.all with a cursor that designates each element in the subtree rooted by the node designated by Position, starting from with the node designated by Position and proceeding in a depth-first order. Tampering with the cursors of the tree that contains the element designated by Position is prohibited during the execution of a call on Process.all. Any exception raised by Process.all is propagated.
155.a/3
Ramification: Position can be passed a cursor designating the root node; in that case, Process is not called with the root node, which does not have an associated element. 
155.1/5
procedure Iterate_Subtree
  (Container : in Tree;
   Position  : in Cursor;
   Process   : not null access procedure (Position : in Cursor))
   with Allows_Exit,
        Pre  => (Position /= No_Element 
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Position)
                   or else raise Program_Error);
155.2/5
{AI12-0112-1} Iterate_Subtree calls Process.all with a cursor that designates each element in the subtree rooted by the node designated by Position in Container, starting from the node designated by Position and proceeding in a depth-first order. Tampering with the cursors of the tree that contains the element designated by Position is prohibited during the execution of a call on Process.all. Any exception raised by Process.all is propagated.
156/5
{AI12-0112-1} function Iterate (Container : in Tree)
   return Tree_Iterator_Interfaces.Parallel_Iterator Forward_Iterator'Class
   with Post => Tampering_With_Cursors_Prohibited (Container)
;
157/5
{AI05-0212-1} {AI05-0265-1} {AI05-0269-1} {AI12-0069-1} {AI12-0266-1} Iterate returns an iterator object (see 5.5.1) that will generate a value for a loop parameter (see 5.5.2) designating each element node in Container, starting from with the root node and proceeding in a depth-first order when used as a forward iterator, and processing all nodes concurrently when used as a parallel iterator. Tampering with the cursors of Container is prohibited while the iterator object exists (in particular, in the sequence_of_statements of the loop_statement whose iterator_specification denotes this object). The iterator object needs finalization.
157.a/3
Discussion: Exits are allowed from the loops created using the iterator objects. In particular, to stop the iteration at a particular cursor, just add
157.b/3
exit when Cur = Stop;
157.c/3
in the body of the loop (assuming that Cur is the loop parameter and Stop is the cursor that you want to stop at). 
158/5
function Iterate_Subtree (Position : in Cursor)
   return Tree_Iterator_Interfaces.Parallel_Iterator Forward_Iterator'Class
   with Pre    => Position /= No_Element or else raise Constraint_Error,
        Global => in all
;
159/5
{AI05-0212-1} {AI05-0265-1} {AI05-0269-1} {AI12-0069-1} {AI12-0112-1} {AI12-0266-1} If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Iterate_Subtree returns an iterator object (see 5.5.1) that will generate a value for a loop parameter (see 5.5.2) designating each element in the subtree rooted by the node designated by Position, starting from with the node designated by Position and proceeding in a depth-first order when used as a forward iterator, and processing all nodes in the subtree concurrently when used as a parallel iterator. If Position equals No_Element, then Constraint_Error is propagated. Tampering with the cursors of the container that contains the node designated by Position is prohibited while the iterator object exists (in particular, in the sequence_of_statements of the loop_statement whose iterator_specification denotes this object). The iterator object needs finalization.
159.1/5
function Iterate_Subtree (Container : in Tree; Position : in Cursor)
   return Tree_Iterator_Interfaces.Parallel_Iterator'Class
   with Pre  => (Position /= No_Element 
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Position)
                   or else raise Program_Error),
        Post => Tampering_With_Cursors_Prohibited (Container);
159.2/5
{AI12-0112-1} Iterate_Subtree returns an iterator object (see 5.5.1) that will generate a value for a loop parameter (see 5.5.2) designating each element in the subtree rooted by the node designated by Position in Container, starting from the node designated by Position and proceeding in a depth-first order when used as a forward iterator, and processing all nodes in the subtree concurrently when used as a parallel iterator. Tampering with the cursors of the container that contains the node designated by Position is prohibited while the iterator object exists (in particular, in the sequence_of_statements of the loop_statement whose iterator_specification denotes this object). The iterator object needs finalization.
160/5
{AI12-0112-1} function Child_Count (Parent : Cursor) return Count_Type
   with Post => (if Parent = No_Element then Child_Count'Result = 0
                 else True),
         Nonblocking, Global => (in alluse null)
;
161/3
{AI05-0136-1} Child_Count returns the number of child nodes of the node designated by Parent.
161.1/5
function Child_Count (Container : Tree; Parent : Cursor)
   return Count_Type
   with Pre  => Meaningful_For (Container, Parent) 
                   or else raise Program_Error,
        Post => (if Parent = No_Element then Child_Count'Result = 0
                 else True),
        Nonblocking, Global => null, Use_Formal => null;
161.2/5
{AI12-0112-1} Child_Count returns the number of child nodes of the node designated by Parent in Container.
162/5
function Child_Depth (Parent, Child : Cursor) return Count_Type
   with Pre  => (Parent /= No_Element and then Child /= No_Element)
                   or else raise Constraint_Error,
        Nonblocking, Global => (in alluse null)
;
163/5
{AI05-0136-1} {AI05-0262-1} {AI12-0112-1} If Child or Parent is equal to No_Element, then Constraint_Error is propagated. Otherwise, Child_Depth returns the number of ancestor nodes of Child (including Child itself), up to but not including Parent; Program_Error is propagated if Parent is not an ancestor of Child.
163.a/3
Ramification: Program_Error is propagated if Parent and Child are nodes in different containers.
163.b/3
Child_Depth (Root (Some_Tree), Child) + 1 = Depth (Child) as the root is not counted. 
163.1/5
function Child_Depth (Container : Tree; Parent, Child : Cursor)
   return Count_Type
   with Pre  => ((Parent /= No_Element and then Child /= No_Element)
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error) and then
                (Meaningful_For (Container, Child)
                   or else raise Program_Error),
           Nonblocking, Global => null, Use_Formal => null;
163.2/5
{AI12-0112-1} Child_Depth returns the number of ancestor nodes of Child within Container (including Child itself), up to but not including Parent; Program_Error is propagated if Parent is not an ancestor of Child.
164/5
procedure Insert_Child (Container : in out Tree;
                        Parent    : in     Cursor;
                        Before    : in     Cursor;
                        New_Item  : in     Element_Type;
                        Count     : in     Count_Type := 1)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error) and then
                (Meaningful_For (Container, Before)
                   or else raise Program_Error) and then
                (Before = No_Element or else
                 Container.Parent (Before) = Parent
                   or else raise Constraint_Error),
        Post => Node_Count (Container) =
                Node_Count (Container)'Old + Count
;
165/5
{AI05-0136-1} {AI05-0248-1} {AI05-0262-1} {AI12-0112-1} If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Parent does not designate the parent node of the node designated by Before, then Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes containing copies of New_Item and inserts them as children of Parent. If Parent already has child nodes, then the new nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the new nodes are inserted after the last existing child node of Parent. Any exception raised during allocation of internal storage is propagated, and Container is not modified.
166/5
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)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error) and then
                (Meaningful_For (Container, Before)
                   or else raise Program_Error) and then
                (Before = No_Element or else
                 Container.Parent (Before) = Parent
                   or else raise Constraint_Error),
        Post => (Node_Count (Container) =
                 Node_Count (Container)'Old + Count) and then
                 Has_Element (Container, Position)
;
167/5
{AI05-0136-1} {AI05-0248-1} {AI05-0257-1} {AI05-0262-1} {AI12-0112-1} If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Parent does not designate the parent node of the node designated by Before, then Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes containing copies of New_Item and inserts them as children of Parent. If Parent already has child nodes, then the new nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the new nodes are inserted after the last existing child node of Parent. Position designates the first newly-inserted node, or if Count equals 0, then Position is assigned the value of Before. Any exception raised during allocation of internal storage is propagated, and Container is not modified.
168/5
procedure Insert_Child (Container : in out Tree;
                        Parent    : in     Cursor;
                        Before    : in     Cursor;
                        Position  :    out Cursor;
                        Count     : in     Count_Type := 1)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error) and then
                (Meaningful_For (Container, Before)
                   or else raise Program_Error) and then
                (Before = No_Element or else
                 Container.Parent (Before) = Parent
                   or else raise Constraint_Error),
        Post => (Node_Count (Container) =
                 Node_Count (Container)'Old + Count) and then
                Has_Element (Container, Position)
;
169/5
{AI05-0136-1} {AI05-0257-1} {AI05-0262-1} {AI05-0264-1} {AI12-0112-1} If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Parent does not designate the parent node of the node designated by Before, then Constraint_Error is propagated. Otherwise, Insert_Child allocates Count nodes, the elements contained in the new nodes are initialized by default (see 3.3.1), and the new nodes are inserted as children of Parent. If Parent already has child nodes, then the new nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the new nodes are inserted after the last existing child node of Parent. Position designates the first newly-inserted node, or if Count equals 0, then Position is assigned the value of Before. Any exception raised during allocation of internal storage is propagated, and Container is not modified.
170/5
{AI12-0112-1} procedure Prepend_Child (Container : in out Tree;
                         Parent    : in     Cursor;
                         New_Item  : in     Element_Type;
                         Count     : in     Count_Type := 1)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error),
        Post => Node_Count (Container) =
                Node_Count (Container)'Old + Count
;
171/3
{AI05-0136-1} Equivalent to Insert_Child (Container, Parent, First_Child (Container, Parent), New_Item, Count).
172/5
{AI12-0112-1} procedure Append_Child (Container : in out Tree;
                        Parent    : in     Cursor;
                        New_Item  : in     Element_Type;
                        Count     : in     Count_Type := 1)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error),
        Post => Node_Count (Container) =
                Node_Count (Container)'Old + Count
;
173/3
{AI05-0136-1} {AI05-0269-1} Equivalent to Insert_Child (Container, Parent, No_Element, New_Item, Count).
174/5
procedure Delete_Children (Container : in out Tree;
                           Parent    : in     Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error),
        Post => (Node_Count (Container) = Node_Count (Container)'Old -
                   Child_Count (Container, Parent)'Old) and then
                 Child_Count (Container, Parent) = 0
;
175/5
{AI05-0136-1} {AI12-0112-1} If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, Program_Error is propagated. Otherwise, Delete_Children removes (from Container) all of the descendants of Parent other than Parent itself.
175.a/3
Discussion: This routine deletes all of the child subtrees of Parent at once. Use Delete_Subtree to delete an individual subtree. 
176/5
procedure Copy_Subtree (Target   : in out Tree;
                        Parent   : in     Cursor;
                        Before   : in     Cursor;
                        Source   : in     Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error) and then
                 (Parent /= No_Element
                    or else raise Constraint_Error) and then
                 (Meaningful_For (Target, Parent)
                    or else raise Program_Error) and then
                 (Meaningful_For (Target, Before)
                    or else raise Program_Error) and then
                 (Before = No_Element or else
                    Target.Parent (Before) = Parent
                    or else raise Constraint_Error) and then
                 (not Is_Root (Source)
                    or else raise Constraint_Error),
        Post => Node_Count (Target) =
                Node_Count (Target)'Old + Subtree_Node_Count (Source),
        Global => in all
;
177/5
{AI05-0136-1} {AI05-0248-1} {AI05-0262-1} {AI12-0112-1} If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Target, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Target, then Program_Error is propagated. If Before is not equal to No_Element, and Parent does not designate the parent node of the node designated by Before, then Constraint_Error is propagated. If Source designates a root node, then Constraint_Error is propagated. If Source is equal to No_Element, then the operation has no effect. Otherwise, the subtree rooted by Source (which can be from any tree; it does not have to be a subtree of Target) is copied (new nodes are allocated to create a new subtree with the same structure as the Source subtree, with each element initialized from the corresponding element of the Source subtree) and inserted into Target as a child of Parent. If Parent already has child nodes, then the new nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the new nodes are inserted after the last existing child node of Parent. The parent of the newly created subtree is set to Parent, and the overall count of Target is incremented by Subtree_Node_Count (Source). Any exception raised during allocation of internal storage is propagated, and Container is not modified.
177.a/5
Discussion: {AI12-0112-1} We only need one routine here, as the source object is not modified, so we can use the same routine for both copying within and between containers. However, that requires a contract that allows reading of any container of the correct type, so we provide two other routines wuth more restrictive contracts. 
177.b/3
Ramification: We do not allow copying a subtree that includes a root node, as that would require inserting a node with no value in the middle of the target tree. To copy an entire tree to another tree object, use Copy. 
177.1/5
procedure Copy_Local_Subtree (Target   : in out Tree;
                              Parent   : in     Cursor;
                              Before   : in     Cursor;
                              Source   : in     Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error) and then
                 (Parent /= No_Element
                    or else raise Constraint_Error) and then
                 (Meaningful_For (Target, Parent)
                    or else raise Program_Error) and then
                 (Meaningful_For (Target, Before)
                    or else raise Program_Error) and then
                 (Before = No_Element or else
                    Target.Parent (Before) = Parent
                    or else raise Constraint_Error) and then
                 (Meaningful_For (Target, Source)
                    or else raise Program_Error) and then
                 (not Is_Root (Source)
                    or else raise Constraint_Error),
        Post => Node_Count (Target) = Node_Count (Target)'Old +
                   Subtree_Node_Count (Target, Source);
177.2/5
{AI12-0112-1} If Source is equal to No_Element, then the operation has no effect. Otherwise, the subtree rooted by Source in Target is copied (new nodes are allocated to create a new subtree with the same structure as the Source subtree, with each element initialized from the corresponding element of the Source subtree) and inserted into Target as a child of Parent. If Parent already has child nodes, then the new nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the new nodes are inserted after the last existing child node of Parent. The parent of the newly created subtree is set to Parent. Any exception raised during allocation of internal storage is propagated, and Container is not modified.
177.3/5
procedure Copy_Subtree (Target   : in out Tree;
                        Parent   : in     Cursor;
                        Before   : in     Cursor;
                        Source   : in     Tree;
                        Subtree  : in     Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error) and then
                 (Parent /= No_Element
                    or else raise Constraint_Error) and then
                 (Meaningful_For (Target, Parent)
                    or else raise Program_Error) and then
                 (Meaningful_For (Target, Before)
                    or else raise Program_Error) and then
                 (Before = No_Element or else
                    Target.Parent (Before) = Parent
                    or else raise Constraint_Error) and then
                 (Meaningful_For (Source, Subtree)
                    or else raise Program_Error) and then
                 (not Is_Root (Source, Subtree)
                    or else raise Constraint_Error),
        Post => Node_Count (Target) = Node_Count (Target)'Old +
                   Subtree_Node_Count (Source, Subtree);
177.4/5
{AI12-0112-1} If Subtree is equal to No_Element, then the operation has no effect. Otherwise, the subtree rooted by Subtree in Source is copied (new nodes are allocated to create a new subtree with the same structure as the Subtree, with each element initialized from the corresponding element of the Subtree) and inserted into Target as a child of Parent. If Parent already has child nodes, then the new nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the new nodes are inserted after the last existing child node of Parent. The parent of the newly created subtree is set to Parent. Any exception raised during allocation of internal storage is propagated, and Container is not modified.
178/5
procedure Splice_Subtree (Target   : in out Tree;
                          Parent   : in     Cursor;
                          Before   : in     Cursor;
                          Source   : in out Tree;
                          Position : in out Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error) and then
                (not Tampering_With_Cursors_Prohibited (Source)
                    or else raise Program_Error) and then
                (Parent /= No_Element
                    or else raise Constraint_Error) and then
                (Meaningful_For (Target, Parent)
                    or else raise Program_Error) and then
                (Meaningful_For (Target, Before)
                    or else raise Program_Error) and then
                (Before = No_Element or else
                 Target.Parent (Before) /= Parent
                    or else raise Constraint_Error) and then
                (Position /= No_Element
                    or else raise Constraint_Error) and then
                (Has_Element (Source, Position)
                    or else raise Program_Error) and then
                (Target'Has_Same_Object (Source) or else
                 Position = Before or else
                 Is_Ancestor_Of (Target, Position, Parent)
                    or else raise Constraint_Error),
        Post => (declare
                    Org_Sub_Count renames
                        Subtree_Node_Count (Source, Position)'Old;
                    Org_Target_Count renames Node_Count (Target)'Old;
                 begin
                   (if not Target'Has_Same_Object (Source) then
                       Node_Count (Target) = Org_Target_Count +
                          Org_Sub_Count and then
                       Node_Count (Source) = Node_Count (Source)'Old -
                          Org_Sub_Count and then
                       Has_Element (Target, Position)
                    else
                       Target.Parent (Position) = Parent and then
                       Node_Count (Target) = Org_Target_Count))
;
179/5
{AI05-0136-1} {AI05-0248-1} {AI05-0262-1} {AI05-0269-1} {AI12-0112-1} If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Target, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Target, then Program_Error is propagated. If Before is not equal to No_Element, and Parent does not designate the parent node of the node designated by Before, then Constraint_Error is propagated. If Position equals No_Element, Constraint_Error is propagated. If Position does not designate a node in Source or designates a root node, then Program_Error is propagated. If Source denotes the same object as Target, then: if Position equals Before there is no effect; if Position designates an ancestor of Parent (including Parent itself), Constraint_Error is propagated; otherwise, the subtree rooted by the element designated by Position is moved to be a child of Parent. If Parent already has child nodes, then the moved nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved nodes are inserted after the last existing child node of Parent. In each of these cases, Position and the count of Target are unchanged, and the parent of the element designated by Position is set to Parent.
179.a/3
Reason: We can't allow moving the subtree of Position to a proper descendant node of the subtree, as the descendant node will be part of the subtree being moved. The result would be a circularly linked tree, or one with inaccessible nodes. Thus we have to check Position against Parent, even though such a check is O(Depth(Source)).
180/3
{AI05-0136-1} {AI05-0248-1} Otherwise (if Source does not denote the same object as Target), the subtree designated by Position is removed from Source and moved to Target. The subtree is inserted as a child of Parent. If Parent already has child nodes, then the moved nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved nodes are inserted after the last existing child node of Parent. In each of these cases, the count of Target is incremented by Subtree_Node_Count (Position), and the count of Source is decremented by Subtree_Node_Count (Position), Position is updated to represent an element in Target.
180.a/3
Ramification: If Source is the same as Target, and Position = Before, or Next_Sibling(Position) = Before, Splice_Subtree has no effect, as the subtree does not have to move to meet the postcondition.
180.b/3
We do not allow splicing a subtree that includes a root node, as that would require inserting a node with no value in the middle of the target tree. Splice the children of the root node instead.
180.c/3
For this reason there is no operation to splice an entire tree, as that would necessarily involve splicing a root node.
181/5
procedure Splice_Subtree (Container: in out Tree;
                          Parent   : in     Cursor;
                          Before   : in     Cursor;
                          Position : in     Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error) and then
                (Meaningful_For (Container, Before)
                   or else raise Program_Error) and then
                (Before = No_Element or else
                 Container.Parent (Before) /= Parent
                   or else raise Constraint_Error) and then
                (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error) and then
                (Position = Before or else
                 Is_Ancestor_Of (Container, Position, Parent)
                   or else raise Constraint_Error),
        Post => (Node_Count (Container) =
                   Node_Count (Container)'Old and then
                 Container.Parent (Position) = Parent)
;
182/5
{AI05-0136-1} {AI05-0248-1} {AI05-0262-1} {AI05-0269-1} {AI12-0112-1} If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Parent does not designate the parent node of the node designated by Before, then Constraint_Error is propagated. If Position equals No_Element, Constraint_Error is propagated. If Position does not designate a node in Container or designates a root node, then Program_Error is propagated. If Position equals Before, there is no effect. If Position designates an ancestor of Parent (including Parent itself), Constraint_Error is propagated. Otherwise, the subtree rooted by the element designated by Position is moved to be a child of Parent. If Parent already has child nodes, then the moved nodes are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved nodes are inserted after the last existing child node of Parent. The parent of the element designated by Position is set to Parent.
182.a/3
Reason: We can't allow moving the subtree of Position to a proper descendant node of the subtree, as the descendant node will be part of the subtree being moved. 
183/5
procedure Splice_Children (Target          : in out Tree;
                           Target_Parent   : in     Cursor;
                           Before          : in     Cursor;
                           Source          : in out Tree;
                           Source_Parent   : in     Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error) and then
                (not Tampering_With_Cursors_Prohibited (Source)
                    or else raise Program_Error) and then
                (Target_Parent /= No_Element
                    or else raise Constraint_Error) and then
                (Meaningful_For (Target, Target_Parent)
                    or else raise Program_Error) and then
                (Meaningful_For (Target, Before)
                    or else raise Program_Error) and then
                (Source_Parent /= No_Element
                    or else raise Constraint_Error) and then
                (Meaningful_For (Source, Source_Parent)
                    or else raise Program_Error) and then
                (Before = No_Element or else
                 Parent (Target, Before) /= Target_Parent
                    or else raise Constraint_Error) and then
                (Target'Has_Same_Object (Source) or else
                 Target_Parent = Source_Parent or else
                 Is_Ancestor_Of (Target, Source_Parent, Target_Parent)
                    or else raise Constraint_Error),
        Post => (declare
                    Org_Child_Count renames
                       Child_Count (Source, Source_Parent)'Old;
                    Org_Target_Count renames Node_Count (Target)'Old;
                 begin
                   (if not Target'Has_Same_Object (Source) then
                       Node_Count (Target) = Org_Target_Count +
                          Org_Child_Count and then
                       Node_Count (Source) = Node_Count (Source)'Old -
                          Org_Child_Count
                    else
                       Node_Count (Target) = Org_Target_Count))
;
184/5
This paragraph was deleted.{AI05-0136-1} {AI05-0262-1} {AI12-0112-1} If Target_Parent equals No_Element, then Constraint_Error is propagated. If Target_Parent does not designate a node in Target, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Target, then Program_Error is propagated. If Source_Parent equals No_Element, then Constraint_Error is propagated. If Source_Parent does not designate a node in Source, then Program_Error is propagated. If Before is not equal to No_Element, and Target_Parent does not designate the parent node of the node designated by Before, then Constraint_Error is propagated.
185/3
If Source denotes the same object as Target, then:
186/3
if Target_Parent equals Source_Parent there is no effect; else
187/5
This paragraph was deleted.{AI05-0136-1} {AI05-0269-1} {AI12-0112-1} if Source_Parent is an ancestor of Target_Parent other than Target_Parent itself, then Constraint_Error is propagated; else
188/3
{AI05-0136-1} {AI05-0248-1} {AI05-0269-1} the child elements (and the further descendants) of Source_Parent are moved to be child elements of Target_Parent. If Target_Parent already has child elements, then the moved elements are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved elements are inserted after the last existing child node of Target_Parent. The parent of each moved child element is set to Target_Parent. 
188.a/3
Reason: We can't allow moving the children of Source_Parent to a proper descendant node, as the descendant node will be part of one of the subtrees being moved. 
189/3
{AI05-0136-1} {AI05-0248-1} {AI05-0269-1} Otherwise (if Source does not denote the same object as Target), the child elements (and the further descendants) of Source_Parent are removed from Source and moved to Target. The child elements are inserted as children of Target_Parent. If Target_Parent already has child elements, then the moved elements are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved elements are inserted after the last existing child node of Target_Parent. In each of these cases, the overall count of Target is incremented by Subtree_Node_Count (Source_Parent)-1, and the overall count of Source is decremented by Subtree_Node_Count (Source_Parent)-1.
189.a/3
Ramification: The node designated by Source_Parent is not moved, thus we never need to update Source_Parent.
189.b/3
Move (Target, Source) could be written Splice_Children (Target, Target.Root, No_Element, Source, Source.Root); 
190/5
procedure Splice_Children (Container       : in out Tree;
                           Target_Parent   : in     Cursor;
                           Before          : in     Cursor;
                           Source_Parent   : in     Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Target_Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Target_Parent)
                   or else raise Program_Error) and then
                (Meaningful_For (Container, Before)
                   or else raise Program_Error) and then
                (Source_Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Source_Parent)
                   or else raise Program_Error) and then
                (Before = No_Element or else
                 Parent (Container, Before) /= Target_Parent
                   or else raise Constraint_Error) and then
                (Target_Parent = Source_Parent or else
                 Is_Ancestor_Of (Container, Source_Parent, Target_Parent)
                   or else raise Constraint_Error),
        Post => Node_Count (Container) = Node_Count (Container)'Old
;
191/5
{AI05-0136-1} {AI05-0248-1} {AI05-0262-1} {AI05-0264-1} {AI05-0269-1} {AI12-0112-1} If Target_Parent equals No_Element, then Constraint_Error is propagated. If Target_Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Container, then Program_Error is propagated. If Source_Parent equals No_Element, then Constraint_Error is propagated. If Source_Parent does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Target_Parent does not designate the parent node of the node designated by Before, then Constraint_Error is propagated. If Target_Parent equals Source_Parent there is no effect. If Source_Parent is an ancestor of Target_Parent other than Target_Parent itself, then Constraint_Error is propagated. Otherwise, the child elements (and the further descendants) of Source_Parent are moved to be child elements of Target_Parent. If Target_Parent already has child elements, then the moved elements are inserted prior to the node designated by Before, or, if Before equals No_Element, the moved elements are inserted after the last existing child node of Target_Parent. The parent of each moved child element is set to Target_Parent.
192/5
function Parent (Position : Cursor) return Cursor
   with Nonblocking, Global => (in alluse null),
        Post => (if Position = No_Element or else
                    Is_Root (Position) then Parent'Result = No_Element
                 else True)
;
193/5
{AI05-0136-1} {AI12-0112-1} Returns If Position is equal to No_Element or designates a root node, No_Element is returned. Otherwise, a cursor designating the parent node of the node designated by Position is returned.
193.1/5
function Parent (Container : Tree;
                 Position  : Cursor) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => Meaningful_For (Container, Position) or else raise Program_Error,
        Post => (if Position = No_Element or else
                   Is_Root (Container, Position)
                   then Parent'Result = No_Element
                 else Has_Element (Container, Parent'Result));
193.2/5
{AI12-0112-1} Returns a cursor designating the parent node of the node designated by Position in Container.
194/5
function First_Child (Parent : Cursor) return Cursor
   with Nonblocking, Global => (in alluse null),
        Pre  => Parent /= No_Element or else raise Constraint_Error
;
195/5
{AI05-0136-1} {AI12-0112-1} If Parent is equal to No_Element, then Constraint_Error is propagated. Otherwise, First_Child returns a cursor designating the first child node of the node designated by Parent; if there is no such node, No_Element is returned.
195.1/5
function First_Child (Container : Tree;
                      Parent    : Cursor) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error),
        Post => First_Child'Result = No_Element or else
                Has_Element (Container, First_Child'Result);
195.2/5
{AI12-0112-1} First_Child returns a cursor designating the first child node of the node designated by Parent in Container; if there is no such node, No_Element is returned.
196/5
{AI12-0112-1} function First_Child_Element (Parent : Cursor) return Element_Type
   with Nonblocking,
        Global => in all, Use_Formal => Element_Type,
        Pre  => (Parent /= No_Element and then
                 Last_Child (Parent) /= No_Element)
                     or else raise Constraint_Error
;
197/3
{AI05-0136-1} Equivalent to Element (First_Child (Parent)).
197.1/5
function First_Child_Element (Container : Tree;
                              Parent    : Cursor) return Element_Type
   with Nonblocking, Global => null, Use_Formal => Element_Type,
        Pre  => (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error) and then
                (First_Child (Container, Parent) /= No_Element
                   or else raise Constraint_Error);
197.2/5
{AI12-0112-1} Equivalent to Element (Container, First_Child (Container, Parent)).
198/5
function Last_Child (Parent : Cursor) return Cursor
   with Nonblocking, Global => (in alluse null),
        Pre  => Parent /= No_Element or else raise Constraint_Error
;
199/5
{AI05-0136-1} {AI12-0112-1} If Parent is equal to No_Element, then Constraint_Error is propagated. Otherwise, Last_Child returns a cursor designating the last child node of the node designated by Parent; if there is no such node, No_Element is returned.
199.1/5
function Last_Child (Container : Tree;
                     Parent    : Cursor) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error),
        Post => Last_Child'Result = No_Element or else
                Has_Element (Container, Last_Child'Result);
199.2/5
{AI12-0112-1} Last_Child returns a cursor designating the last child node of the node designated by Parent in Container; if there is no such node, No_Element is returned.
200/5
{AI12-0112-1} function Last_Child_Element (Parent : Cursor) return Element_Type
   with Nonblocking,
        Global => in all, Use_Formal => Element_Type,
        Pre  => (Parent /= No_Element and then
                 Last_Child (Parent) /= No_Element)
                     or else raise Constraint_Error
;
201/3
{AI05-0136-1} Equivalent to Element (Last_Child (Parent)).
201.1/5
function Last_Child_Element (Container : Tree;
                             Parent    : Cursor) return Element_Type
   with Nonblocking, Global => null, Use_Formal => Element_Type,
        Pre  => (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error) and then
                (Last_Child (Container, Parent) /= No_Element
                   or else raise Constraint_Error);
201.2/5
{AI12-0112-1} Equivalent to Element (Container, Last_Child (Container, Parent)).
202/5
{AI12-0112-1} function Next_Sibling (Position : Cursor) return Cursor
   with Nonblocking, Global => (in alluse null),
        Post => (if Position = No_Element
                    then Next_Sibling'Result = No_Element
                 else True)
;
203/3
{AI05-0136-1} If Position equals No_Element or designates the last child node of its parent, then Next_Sibling returns the value No_Element. Otherwise, it returns a cursor that designates the successor (with the same parent) of the node designated by Position.
203.1/5
function Next_Sibling (Container : Tree;
                       Position  : Cursor) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => Meaningful_For (Container, Position)
                   or else raise Program_Error,
        Post => (if Next_Sibling'Result = No_Element then
                   Position = No_Element or else
                   Is_Root (Container, Position) or else
                   Last_Child (Container, Parent (Container, Position))
                      = Position
                 else Has_Element (Container, Next_Sibling'Result));
203.2/5
{AI12-0112-1} Next_Sibling returns a cursor that designates the successor (with the same parent) of the node designated by Position in Container.
204/5
{AI12-0112-1} function Previous_Sibling (Position : in out Cursor)
   with Nonblocking, Global => (in alluse null),
        Post => (if Position = No_Element
                    then Previous_Sibling'Result = No_Element
                 else True)
;
205/3
{AI05-0136-1} If Position equals No_Element or designates the first child node of its parent, then Previous_Sibling returns the value No_Element. Otherwise, it returns a cursor that designates the predecessor (with the same parent) of the node designated by Position.
205.1/5
function Previous_Sibling (Container : Tree;
                           Position  : Cursor) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => Meaningful_For (Container, Position)
                   or else raise Program_Error,
        Post => (if Previous_Sibling'Result = No_Element then
                   Position = No_Element or else
                   Is_Root (Container, Position) or else
                   First_Child (Container, Parent (Container, Position))
                      = Position
                 else Has_Element (Container, Previous_Sibling'Result));
205.2/5
{AI12-0112-1} Previous_Sibling returns a cursor that designates the predecessor (with the same parent) of the node designated by Position in Container.
206/5
{AI12-0112-1} procedure Next_Sibling (Position : in out Cursor)
      with Nonblocking, Global => (in alluse null)
;
207/3
{AI05-0136-1} Equivalent to Position := Next_Sibling (Position);
207.1/5
procedure Next_Sibling (Container : in     Tree;
                        Position  : in out Cursor)
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => Meaningful_For (Container, Position)
                   or else raise Program_Error,
        Post => (if Position /= No_Element
                 then Has_Element (Container, Position));
207.2/5
{AI12-0112-1} Equivalent to Position := Next_Sibling (Container, Position);
208/5
{AI12-0112-1} procedure Previous_Sibling (Position : in out Cursor)
   with Nonblocking, Global => (in alluse null)
;
209/3
{AI05-0136-1} Equivalent to Position := Previous_Sibling (Position);
209.1/5
procedure Previous_Sibling (Container : in     Tree;
                            Position  : in out Cursor)
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => Meaningful_For (Container, Position)
                   or else raise Program_Error,
        Post => (if Position /= No_Element
                 then Has_Element (Container, Position);
209.2/5
{AI12-0112-1} Equivalent to Position := Previous_Sibling (Container, Position);
210/5
{AI12-0112-1} procedure Iterate_Children
  (Parent  : in Cursor;
   Process : not null access procedure (Position : in Cursor))
   with Allows_Exit,
        Pre    => Parent /= No_Element or else raise Constraint_Error,
        Global => (in alluse null)
;
211/5
This paragraph was deleted.{AI05-0136-1} {AI05-0248-1} {AI12-0112-1} If Parent equals No_Element, then Constraint_Error is propagated.
212/3
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.
213/3
{AI05-0265-1} Tampering with the cursors of the tree containing Parent is prohibited during the execution of a call on Process.all. Any exception raised by Process.all is propagated.
213.1/5
{AI12-0112-1} procedure Iterate_Children
     (Container : in Tree;
      Parent    : in Cursor;
      Process   : not null access procedure (Position : in Cursor))
   with Allows_Exit,
        Pre  => (Parent /= No_Element 
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error);
213.2/5
{AI12-0112-1} Iterate_Children calls Process.all with a cursor that designates each child node of Container and Parent, starting with the first child node and moving the cursor as per the Next_Sibling function.
213.3/5
{AI12-0112-1} Tampering with the cursors of the tree containing Parent is prohibited during the execution of a call on Process.all. Any exception raised by Process.all is propagated.
214/5
{AI12-0112-1} procedure Reverse_Iterate_Children
  (Parent  : in Cursor;
   Process : not null access procedure (Position : in Cursor))
   with Allows_Exit,
        Pre  => Parent /= No_Element or else raise Constraint_Error,
        Global => (in alluse null)
;
215/5
This paragraph was deleted.{AI05-0136-1} {AI05-0248-1} {AI12-0112-1} If Parent equals No_Element, then Constraint_Error is propagated.
216/3
Reverse_Iterate_Children calls Process.all with a cursor that designates each child node of Parent, starting with the last child node and moving the cursor as per the Previous_Sibling function.
217/3
{AI05-0265-1} Tampering with the cursors of the tree containing Parent is prohibited during the execution of a call on Process.all. Any exception raised by Process.all is propagated.
217.1/5
{AI12-0112-1} procedure Reverse_Iterate_Children
     (Container : in Tree;
      Parent    : in Cursor;
      Process   : not null access procedure (Position : in Cursor))
   with Allows_Exit,
        Pre  => (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error);
217.2/5
{AI12-0112-1} Reverse_Iterate_Children calls Process.all with a cursor that designates each child node of Container and Parent, starting with the last child node and moving the cursor as per the Previous_Sibling function.
217.3/5
{AI12-0112-1} Tampering with the cursors of the tree containing Parent is prohibited during the execution of a call on Process.all. Any exception raised by Process.all is propagated.
218/5
function Iterate_Children (Container : in Tree; Parent : in Cursor)
   return Tree_Iterator_Interfaces.Parallel_Reversible_Iterator Reversible_Iterator'Class
   with Pre  => (Parent /= No_Element
                   or else raise Constraint_Error) and then
                (Meaningful_For (Container, Parent)
                   or else raise Program_Error),
        Post => Tampering_With_Cursors_Prohibited (Container)
;
219/5
{AI05-0212-1} {AI05-0265-1} {AI12-0112-1} {AI12-0266-1} Iterate_Children returns an a reversible iterator object (see 5.5.1) that will generate a value for a loop parameter (see 5.5.2) designating each child node of Parent. When If Parent equals No_Element, then Constraint_Error is propagated. If Parent does not designate a node in Container, then Program_Error is propagated. Otherwise, when used as a forward iterator, the nodes are designated starting with the first child node and moving the cursor as per the function Next_Sibling; when used as a reverse iterator, the nodes are designated starting with the last child node and moving the cursor as per the function Previous_Sibling; when used as a parallel iterator, processing all child nodes concurrently. Tampering with the cursors of Container is prohibited while the iterator object exists (in particular, in the sequence_of_statements of the loop_statement whose iterator_specification denotes this object). The iterator object needs finalization.
219.1/5
   {AI12-0111-1} The nested package Multiway_Trees.Stable provides a type Stable.tree that represents a stable tree, which is one that cannot grow and shrink. Such a tree can be created by calling the Copy function, or by establishing a stabilized view of a regular tree.
219.2/5
   {AI12-0111-1} The subprograms of package Containers.Multiway_Trees that have a parameter or result of type tree are included in the nested package Stable with the same specification, except that the following are omitted:
219.3/5
Tampering_With_Cursors_Prohibited, Tampering_With_Elements_Prohibited, Assign, Move, Clear, Delete_Leaf, Insert_Child, Delete_Children, Delete_Subtree, Copy_Subtree, Copy_Local_Subtree, Splice_Subtree, and Splice_Children 
219.a.1/5
Ramification: The names Tree and Cursor mean the types declared in the nested package in these subprogram specifications. 
219.a.2/5
Reason: The omitted routines are those that tamper with cursors or elements (or test that state). The model is that it is impossible to tamper with cursors or elements of a stable view since no such operations are included. Thus tampering checks are not needed for a stable view, and we omit the operations associated with those checks. 
219.4/5
   {AI12-0111-1} The operations of this package are equivalent to those for regular trees, except that the calls to Tampering_With_Cursors_Prohibited and Tampering_With_Elements_Prohibited that occur in preconditions are replaced by False, and any that occur in postconditions are replaced by True.
219.5/5
   {AI12-0111-1} If a stable tree is declared with the Base discriminant designating a pre-existing regular tree, the stable tree represents a stabilized view of the underlying regular tree, and any operation on the stable tree is reflected on the underlying regular tree. While a stabilized view exists, any operation that tampers with elements performed on the underlying tree is prohibited. The finalization of a stable tree that provides such a view removes this restriction on the underlying regular tree [(though some other restriction might exist due to other concurrent iterations or stabilized views)].
219.6/5
   {AI12-0111-1} If a stable tree is declared without specifying Base, the object must be initialized. The initializing expression of the stable tree, [typically a call on Copy], determines the Node_Count of the tree. The Node_Count of a stable tree never changes after initialization.

Bounded (Run-Time) Errors

220/3
 {AI05-0136-1} {AI05-0248-1} 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 of 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.
221/3
 {AI05-0136-1} 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.

Erroneous Execution

222/3
 {AI05-0136-1} A Cursor value is invalid if any of the following have occurred since it was created:
223/3
The tree that contains the element it designates has been finalized;
224/3
The tree that contains the element it designates has been used as the Source or Target of a call to Move;
225/3
The tree that contains the element it designates has been used as the Target of a call to Assign or the target of an assignment_statement;
226/3
The element it designates has been removed from the tree that previously contained the element. 
226.a/3
Reason: We talk about which tree the element was removed from in order to handle splicing nodes from one tree to another. The node still exists, but any cursors that designate it in the original tree are now invalid. This bullet covers removals caused by calls to Clear, Delete_Leaf, Delete_Subtree, Delete_Children, Splice_Children, and Splice_Subtree. 
227/3
 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.
227.a/3
Discussion: The list above is intended to be exhaustive. In other cases, a cursor value continues to designate its original element (or the root node). For instance, cursor values survive the insertion and deletion of other nodes.
227.b/3
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. 
228/3
 {AI05-0212-1} Execution is erroneous if the tree associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.
228.a/3
Reason: Each object of Reference_Type and Constant_Reference_Type probably contains some reference to the originating container. If that container is prematurely finalized (which is only possible via Unchecked_Deallocation, as accessibility checks prevent passing a container to Reference that will not live as long as the result), the finalization of the object of Reference_Type will try to access a nonexistent object. This is a normal case of a dangling pointer created by Unchecked_Deallocation; we have to explicitly mention it here as the pointer in question is not visible in the specification of the type. (This is the same reason we have to say this for invalid cursors.) 

Implementation Requirements

229/3
 {AI05-0136-1} No storage associated with a multiway tree object shall be lost upon assignment or scope exit.
230/3
 {AI05-0136-1} {AI05-0262-1} The execution of an assignment_statement for a tree shall have the effect of copying the elements from the source tree object to the target tree object and changing the node count of the target object to that of the source object.
230.a/3
Implementation Note: {AI05-0298-1} An assignment of a Tree is a “deep” copy; that is the elements are copied as well 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. (Note that this implementation would require care, see A.18.2 for more.)

Implementation Advice

231/3
 {AI05-0136-1} 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, Next_Sibling, Previous_Sibling, Insert_Child with Count=1, and Delete should be O(log N). 
231.a/3
Implementation Advice: The worst-case time complexity of the Element, Parent, First_Child, Last_Child, Next_Sibling, Previous_Sibling, Insert_Child with Count=1, and Delete operations of Containers.Multiway_Trees should be O(log N).
231.b/3
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. 
232/3
 {AI05-0136-1} Move should not copy elements, and should minimize copying of internal data structures. 
232.a/3
Implementation Advice: Containers.Multiway_Trees.Move should not copy elements, and should minimize copying of internal data structures.
232.b/3
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. 
233/3
 {AI05-0136-1} 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. 
233.a/3
Implementation Advice: 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.
233.b/3
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.

Extensions to Ada 2005

233.c/3
{AI05-0136-1} {AI05-0257-1} {AI05-0265-1} {AI05-0269-1} The generic package Containers.Multiway_Trees is new. 

Inconsistencies With Ada 2012

233.d/5
{AI12-0111-1} Corrigendum: Tampering with elements is now defined to be equivalent to tampering with cursors for regular containers. If a program requires tampering detection to work, it might fail in Ada 202x. Needless to say, this shouldn't happen outside of test programs. See Inconsistencies With Ada 2012 in A.18.2 for more details. 

Incompatibilities With Ada 2012

233.e/5
{AI12-0111-1} {AI12-0112-1} A number of new subprograms, types, and even a nested package were to Containers.Multiway_Trees to better support contracts and stable views. If an instance of Containers.Hashed_Maps is referenced in a use_clause, and an entity E with the same defining_identifier as a new entity in Containers.Hashed_Maps is defined in a package that is also referenced in a use_clause, the entity E may no longer be use-visible, resulting in errors. This should be rare and is easily fixed if it does occur. 

Extensions to Ada 2012

233.f/5
{AI12-0196-1} Correction: Replace_Element is now defined such that it can be used concurrently so long as it operates on different elements. This allows some container operations to be used in parallel without separate synchronization.
233.g/5
{AI12-0266-1} Most iterators can now return parallel iterators, to be used in parallel constructs. 

Wording Changes from Ada 2012

233.h/4
{AI12-0069-1} Corrigendum: Fixed the function Iterate so it is clear that the root node is never visited.
233.i/4
{AI12-0078-1} Corrigendum: The definition of node is clarified so that it it doesn't appear to say all nodes have an element.
233.j/4
{AI12-0110-1} Corrigendum: Clarified that tampering checks precede all other checks made by a subprogram (but come after those associated with the call).
233.k/5
{AI12-0112-1} Added contracts to this container. This includes describing some of the semantics with pre- and postconditions, rather than English text. Note that the preconditions can be Suppressed (see 11.5). 

Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe