CVS difference for arm/source/pre_con2.mss
--- arm/source/pre_con2.mss 2011/07/29 05:59:20 1.9
+++ arm/source/pre_con2.mss 2011/07/30 06:31:10 1.10
@@ -1,7 +1,1826 @@
@Part(precontainers-2, Root="ada.mss")
@comment{ $Source: e:\\cvsroot/ARM/Source/pre_con2.mss,v $ }
-@comment{ $Revision: 1.9 $ $Date: 2011/07/29 05:59:20 $ $Author: randy $ }
+@comment{ $Revision: 1.10 $ $Date: 2011/07/30 06:31:10 $ $Author: randy $ }
+@LabeledAddedSubclause{Version=[3],Name=[The Generic Package Containers.Multiway_Trees]}
+
+@begin{Intro}
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[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.]}
+
+@begin{Discussion}
+ @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Discussion}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[A multiway tree container object manages a tree of
+internal @i<nodes>, each of which contains an element and pointers to the parent,
+first child, last child, next (successor) sibling, and previous (predecessor)
+sibling internal nodes.@Defn2{Term=[node],Sec=[of a tree]} 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.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[A @i<subtree> is a particular node (which @i<roots the subtree>) and all of its child
+nodes (including all of the children of the child nodes, recursively).
+@Defn2{Term=[subtree],Sec=[of a tree]}@Defn{roots the subtree}@Defn2{Term=[subtree],Sec=[node which roots]} There is
+a special node, the @i<root>, which is always present and has no associated element
+value. The root node provides a place to add nodes to an otherwise empty tree and
+represents the bottom of the tree.@Defn2{Term=[root],Sec=[of a tree]}@Defn2{Term=[root node],Sec=[of a tree]}]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[A node that has no children is called a
+@i<leaf node>.@Defn2{Term=[leaf node],Sec=[of a tree]} The @i<ancestors> of a node
+are the parent node, the parent of the parent node, and so on until a node with
+no parent is reached.@Defn2{Term=[ancestor],Sec=[of a tree node]} Similarly,
+the @i<descendants> of a node are the child nodes,
+the children of each child node, and so on.@Defn2{Term=[descendant],Sec=[of a tree node]}]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[The nodes of a subtree could be visited in several
+different orders. For a @i<depth-first order>, the last step of visiting a node
+is to visit the nodes of its child list in order, recursively.@Defn{depth-first
+order}]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Ramification}
+@end{Intro}
+
+@begin{StaticSem}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],KeepNext=[T],Type=[Leading],Text=[The generic library
+package Containers.Multiway_Trees has the following declaration:]}
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Text=[@key{with} Ada.Iterator_Interfaces;
+@key{generic}
+ @key{type} Element_Type @key{is private};
+ @key{with function} "=" (Left, Right : Element_Type) @key{return} Boolean @key{is} <>;
+@key{package} Ada.Containers.Multiway_Trees @key{is}@ChildUnit{Parent=[Ada.Containers],Child=[Multiway_Trees]}
+ @key{pragma} Preelaborate(Multiway_Trees);
+ @key{pragma} Remote_Types(Multiway_Trees);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Text=[ @key{type} @AdaTypeDefn{Tree} @key{is tagged private}
+ @key{with} Constant_Indexing => Constant_Reference,
+ Variable_Indexing => Reference,
+ Default_Iterator => Iterate,
+ Iterator_Element => Element_Type;
+ @key{pragma} Preelaborable_Initialization(Tree);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{type} @AdaTypeDefn{Cursor} @key{is private};
+ @key{pragma} Preelaborable_Initialization(Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @AdaObjDefn{Empty_Tree} : @key{constant} Tree;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @AdaObjDefn{No_Element} : @key{constant} Cursor;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Has_Element} (Position : Cursor) @key{return} Boolean;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Text=[ @key{package} @AdaPackDefn{Tree_Iterator_Interfaces} @key{is new}
+ Ada.Iterator_Interfaces (Cursor, Has_Element);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Equal_Subtree} (Left_Position : Cursor;
+ Right_Position: Cursor) @key{return} Boolean;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} "=" (Left, Right : Tree) @key{return} Boolean;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Is_Empty} (Container : Tree) @key{return} Boolean;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Node_Count} (Container : Tree) @key{return} Count_Type;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Subtree_Node_Count} (Position : Cursor) @key{return} Count_Type;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Depth} (Position : Cursor) @key{return} Count_Type;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Is_Root} (Position : Cursor) @key{return} Boolean;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Is_Leaf} (Position : Cursor) @key{return} Boolean;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Root} (Container : Tree) @key{return} Cursor;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Clear} (Container : @key{in out} Tree);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Element} (Position : Cursor) @key{return} Element_Type;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Replace_Element} (Container : @key{in out} Tree;
+ Position : @key{in} Cursor;
+ New_Item : @key{in} Element_Type);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Query_Element}
+ (Position : @key{in} Cursor;
+ Process : @key{not null access procedure} (Element : @key{in} Element_Type));]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Update_Element}
+ (Container : @key{in out} Tree;
+ Position : @key{in} Cursor;
+ Process : @key{not null access procedure}
+ (Element : @key{in out} Element_Type));]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Text=[ @key[type] @AdaTypeDefn{Constant_Reference_Type}
+ (Element : @key[not null access constant] Element_Type) @key[is private]
+ @key[with] Implicit_Dereference => Element;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Text=[ @key[type] @AdaTypeDefn{Reference_Type} (Element : @key[not null access] Element_Type) @key[is private]
+ @key[with] Implicit_Dereference => Element;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Text=[ @key[function] @AdaSubDefn{Constant_Reference} (Container : @key[aliased in] Tree;
+ Position : @key[in] Cursor)
+ @key[return] Constant_Reference_Type;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Text=[ @key[function] @AdaSubDefn{Reference} (Container : @key[aliased in out] Tree;
+ Position : @key[in] Cursor)
+ @key[return] Reference_Type;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Assign} (Target : @key{in out} Tree; Source : @key{in} Tree);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Copy} (Source : Tree) @key{return} Tree;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Move} (Target : @key{in out} Tree;
+ Source : @key{in out} Tree);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Delete_Leaf} (Container : @key{in out} Tree;
+ Position : @key{in out} Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Delete_Subtree} (Container : @key{in out} Tree;
+ Position : @key{in out} Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Swap} (Container : @key{in out} Tree;
+ I, J : @key{in} Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Find} (Container : Tree;
+ Item : Element_Type)
+ @key{return} Cursor;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Find_In_Subtree} (Position : Cursor;
+ Item : Element_Type)
+ @key{return} Cursor;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Ancestor_Find} (Position : Cursor;
+ Item : Element_Type)
+ @key{return} Cursor;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Contains} (Container : Tree;
+ Item : Element_Type) @key{return} Boolean;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Iterate}
+ (Container : @key{in} Tree;
+ Process : @key{not null access procedure} (Position : @key{in} Cursor));]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Iterate_Subtree}
+ (Position : @key{in} Cursor;
+ Process : @key{not null access procedure} (Position : @key{in} Cursor));]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Iterate} (Container : @key{in} Tree)
+ @key{return} Tree_Iterator_Interfaces.Forward_Iterator'Class;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Iterate_Subtree} (Position : @key{in} Cursor)
+ @key{return} Tree_Iterator_Interfaces.Forward_Iterator'Class;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Child_Count} (Parent : Cursor) @key{return} Count_Type;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Child_Depth} (Parent, Child : Cursor) @key{return} Count_Type;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Insert_Child} (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ New_Item : @key{in} Element_Type;
+ Count : @key{in} Count_Type := 1);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Insert_Child} (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ New_Item : @key{in} Element_Type;
+ Position : @key{out} Cursor;
+ Count : @key{in} Count_Type := 1);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Insert_Child} (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Position : @key{out} Cursor;
+ Count : @key{in} Count_Type := 1);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Prepend_Child} (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ New_Item : @key{in} Element_Type;
+ Count : @key{in} Count_Type := 1);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Append_Child} (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ New_Item : @key{in} Element_Type;
+ Count : @key{in} Count_Type := 1);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Delete_Children} (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Copy_Subtree} (Target : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Source : @key{in} Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Splice_Subtree} (Target : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Source : @key{in out} Tree;
+ Position : @key{in out} Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Splice_Subtree} (Container: @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Position : @key{in} Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Splice_Children} (Target : @key{in out} Tree;
+ Target_Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Source : @key{in out} Tree;
+ Source_Parent : @key{in} Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Splice_Children} (Container : @key{in out} Tree;
+ Target_Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Source_Parent : @key{in} Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Parent} (Position : Cursor) @key{return} Cursor;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{First_Child} (Parent : Cursor) @key{return} Cursor;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{First_Child_Element} (Parent : Cursor) @key{return} Element_Type;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Last_Child} (Parent : Cursor) @key{return} Cursor;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Last_Child_Element} (Parent : Cursor) @key{return} Element_Type;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Next_Sibling} (Position : Cursor) @key{return} Cursor;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Previous_Sibling} (Position : Cursor) @key{return} Cursor;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Next_Sibling} (Position : @key{in out} Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Previous_Sibling} (Position : @key{in out} Cursor);]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Iterate_Children}
+ (Parent : @key{in} Cursor;
+ Process : @key{not null access procedure} (Position : @key{in} Cursor));]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[ @key{procedure} @AdaSubDefn{Reverse_Iterate_Children}
+ (Parent : @key{in} Cursor;
+ Process : @key{not null access procedure} (Position : @key{in} Cursor));]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Text=[ @key{function} @AdaSubDefn{Iterate_Children} (Container : @key[in] Tree; Parent : @key[in] Cursor)
+ @key[return] Tree_Iterator_Interfaces.Reversible_Iterator'Class;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[@key{private}
+ ... -- @RI[not specified by the language]
+@key[end] Ada.Containers.Multiway_Trees;]}
+
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[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.@PDefn{unspecified}]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[The type Tree is used to represent trees. The
+type Tree needs finalization@PDefn2{Term=<needs finalization>,Sec=<language-defined type>}
+(see @RefSecNum{Assignment and Finalization}).]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+@ChgAdded{Version=[3],Text=[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.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[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.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[The predefined "=" operator for type Cursor returns
+True if both cursors are No_Element, or designate the same element in the same
+container.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[Execution of the default implementation of the
+Input, Output, Read, or Write attribute of type Cursor raises Program_Error.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+@ChgAdded{Version=[3],Text=[Tree'Write writes Node_Count (Tree) - 1 elements to
+the stream. Tree'Read reads Node_Count (Tree) - 1 elements from the stream.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[@Redundant[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.]]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Type=[Leading],Text=[@Defn2{Term=[tamper with cursors],Sec=[of a tree]}
+A subprogram is said to
+@i{tamper with cursors} of a tree object @i<T> if:]}
+
+@begin{Itemize}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[it inserts or deletes elements of @i<T>, that is,
+ it calls the Clear, Delete_Leaf, Insert_Child, or Delete_Children procedures
+ with @i<T> as a parameter; or]}
+
+@begin{Honest}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Honest}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Text=[it reorders the elements of @i<T>, that is, it
+ calls the Splice_Subtree or Splice_Children procedures with @i<T> as a
+ parameter; or]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[it finalizes @i<T>; or]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[it calls Assign with @i<T> as the Target parameter; or]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[it calls the Move procedure with @i<T> as a parameter.]}
+
+@begin{Reason}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[Swap copies elements rather than reordering
+ them, so it doesn't tamper with cursors.]}
+@end{Reason}
+@end{Itemize}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Type=[Leading],Text=[@Defn2{Term=[tamper with elements],Sec=[of a tree]}
+A subprogram is said to
+@i{tamper with elements} of a tree object @i<T> if:]}
+
+@begin{Itemize}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[it tampers with cursors of @i<T>; or]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[it replaces one or more elements of @i<T>, that is, it calls the Replace_Element or Swap
+ procedures with @i<T> as a parameter.]}
+
+@begin{Reason}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Reason}
+@end{Itemize}
+
+@begin{DescribeCode}
+
+@begin{Example}
+@ChgRef{Version=[2],Kind=[AddedNormal]}
+@ChgRef{Version=[3],Kind=[Deleted]}
+@ChgAdded{Version=[2],KeepNext=[T],Text=[@Chg{Version=[3],New=[],Old=[@key{function} Has_Element (Position : Cursor) @key{return} Boolean;]}]}
+@end{Example}
+
+@ChgRef{Version=[2],Kind=[AddedNormal],ARef=[AI95-00302-03]}
+@ChgRef{Version=[3],Kind=[Deleted],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[2],Type=[Trailing],Text=[@Chg{Version=[3],New=[],Old=[Returns True if Position designates
+an element, and returns False otherwise.]}]}
+
+@begin{Honest}
+ @ChgRef{Version=[2],Kind=[AddedNormal]}
+ @ChgRef{Version=[3],Kind=[Deleted],ARef=[AI05-0212-1]}
+ @ChgAdded{Version=[2],Text=[@Chg{Version=[3],New=[],Old=[This function may 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).]}]}
+@end{Honest}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Equal_Subtree (Left_Position : Cursor;
+ Right_Position: Cursor) @key{return} Boolean;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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 designated the
+ corresponding child element of the element designated by Right_Position. If
+ any such call returns False, the function returns False; otherwise it
+ returns True. Any exception raised during the evaluation of element equality
+ is propagated.]}
+
+@begin{Ramification}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[Left_Position and Right_Position do not need to
+ be from the same tree.]}
+@end{Ramification}
+
+@begin{ImplNote}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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
+ @RefSecNum{Predefined Language Environment})
+ 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.]}
+@end{ImplNote}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} "=" (Left, Right : Tree) @key{return} Boolean;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Left and Right denote the same
+ tree object, then the function returns True. Otherwise, it calls Equal_Subtree
+ with a cursor designating the root node of Left and Right; the result is
+ returned. Any exception raised during the evaluation of Equal_Subtree is
+ propagated.]}
+
+@begin{ImplNote}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[Similar considerations apply here as apply to
+ Equal_Subtree. The actual number of calls performed is unspecified.]}
+@end{ImplNote}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Node_Count (Container : Tree) @key{return} Count_Type;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Node_Count returns the number of
+ nodes in Container.]}
+
+@begin{Ramification}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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)).]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Subtree_Node_Count (Position : Cursor) @key{return} Count_Type;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Is_Empty (Container : Tree) @key{return} Boolean;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Node_Count (Container) = 1.]}
+
+@begin{Ramification}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[An empty tree contains just the root node.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Depth (Position : Cursor) @key{return} Count_Type;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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).]}
+
+@begin{Ramification}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[Depth (Root (Some_Tree)) = 1.]}
+@end{Ramification}
+
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Is_Root (Position : Cursor) @key{return} Boolean;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Is_Root returns True if the
+ Position designates the root node of some tree; and returns False otherwise.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Is_Leaf (Position : Cursor) @key{return} Boolean;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Is_Leaf returns True if Position
+ designates a node that does not have any child nodes; and returns False
+ otherwise.]}
+
+@begin{Ramification}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Root (Container : Tree) @key{return} Cursor;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Root returns a cursor that
+ designates the root node of Container.]}
+
+@begin{Ramification}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[There is always a root node, even in an empty
+ container, so this function never returns No_Element.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Clear (Container : @key{in out} Tree);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Removes all the elements from
+ Container.]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[The root node is not removed; all trees have a
+ root node.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Element (Position : Cursor) @key{return} Element_Type;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[The root node does not contain an element, so
+ that value cannot be read or written.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Replace_Element (Container : @key{in out} Tree;
+ Position : @key{in} Cursor;
+ New_Item : @key{in} Element_Type);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Query_Element
+ (Position : @key{in} Cursor;
+ Process : @key{not null access procedure} (Element : @key{in} Element_Type));]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.@key{all} with the element designated by Position as the argument.
+ Program_Error is propagated if Process.@key{all} tampers with the elements of
+ Container. Any exception raised by Process.@key{all} is propagated.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Update_Element
+ (Container : @key{in out} Tree;
+ Position : @key{in} Cursor;
+ Process : @key{not null access procedure}
+ (Element : @key{in out} Element_Type));]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.@key{all} with the element
+ designated by Position as the argument. Program_Error is propagated if
+ Process.@key{all} tampers with the elements of Container. Any exception raised
+ by Process.@key{all} is propagated.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[If Element_Type is unconstrained and definite,
+ then the actual Element parameter of Process.@key{all} shall be
+ unconstrained.]}
+
+ @begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+ @end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[@key{type} Constant_Reference_Type
+ (Element : @key[not null access constant] Element_Type) @key[is private]
+ @key[with] Implicit_Dereference => Element;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[@key[type] Reference_Type (Element : @key[not null access] Element_Type) @key[is private]
+ @key[with] Implicit_Dereference => Element;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Constant_Reference_Type and
+ Reference_Type need finalization.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[The default initialization of an object of type
+ Constant_Reference_Type or Reference_Type propagates Program_Error.]}
+
+ @begin{Reason}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+ @end{Reason}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] Constant_Reference (Container : @key[aliased in] Tree;
+ Position : @key[in] Cursor)
+ @key[return] Constant_Reference_Type;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[This function (combined with the
+ Constant_Indexing and Implicit_Dereference aspects) provides a convenient way
+ to gain read access to the individual elements of a container starting with a
+ cursor.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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. Program_Error is propagated if any operation
+ tampers with the elements of Container while the object returned by
+ Constant_Reference exists and has not been finalized.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key[function] Reference (Container : @key[aliased in out] Tree;
+ Position : @key[in] Cursor)
+ @key[return] Reference_Type;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[This function (combined with the
+ Variable_Indexing and Implicit_Dereference aspects) provides a convenient way
+ to gain read and write access to the individual elements of a container
+ starting with a cursor.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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. Program_Error is propagated if any operation tampers
+ with the elements of Container while the object returned by Reference exists
+ and has not been finalized.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Assign (Target : @key{in out} Tree; Source : @key{in} Tree);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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 @nt{assignment_statement} assigning Source to
+ Target.]}
+
+@begin{Ramification}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Ramification}
+@begin{Discussion}
+ @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0005-1]}
+ @ChgAdded{Version=[3],Text=[This routine exists for compatibility with the
+ bounded tree container. For an unbounded tree, @exam{Assign(A, B)} and
+ @exam{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.]}
+@end{Discussion}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Copy (Source : Tree) @key{return} Tree;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Returns a tree with the same
+ structure as Source and whose elements are initialized from the corresponding
+ elements of Source.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Move (Target : @key{in out} Tree;
+ Source : @key{in out} Tree);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Delete_Leaf (Container : @key{in out} Tree;
+ Position : @key{in out} Cursor);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element,
+ then Constraint_Error is propagated; if Position does not designate an element
+ in Container (including if it designates the root node), then Program_Error is
+ propagated. If the element designated by position has any child elements, then
+ Constraint_Error is propagated. Otherwise, Delete_Leaf removes (from Container)
+ the element designated by Position. Finally, Position is set to No_Element.]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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).]}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[The root node cannot be deleted.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Delete_Subtree (Container : @key{in out} Tree;
+ Position : @key{in out} Cursor);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element,
+ then Constraint_Error is propagated. If Position does not designate an element
+ in Container (including if it designates the root node), then Program_Error is
+ propagated. Otherwise Delete removes (from Container) the subtree designated
+ by Position (that is, the node designated by Position and all of the
+ descendant nodes of that node), and Position is set to No_Element.]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[The root node cannot be deleted. To delete the
+ entire contents of the tree, call Clear(Container).]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Swap (Container : @key{in out} Tree;
+ I, J : @key{in} Cursor);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[The root nodes do not contain element values, so
+ they cannot be swapped.]}
+@end{Ramification}
+
+@begin{Honest}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Honest}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Find (Container : Tree;
+ Item : Element_Type)
+ @key{return} Cursor;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Find searches the elements of
+ Container for an element equal to Item (using the generic formal equality
+ operator). The search starts at the root node. The search checks the tree in a
+ depth-first order. If no equal element is found, then Find returns No_Element.
+ Otherwise, it returns a cursor designating the first equal element
+ encountered.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Find_In_Subtree (Position : Cursor;
+ Item : Element_Type)
+ @key{return} Cursor;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element,
+ then Constraint_Error is propagated. Find_In_Subtree searches a
+ subtree of the elements of Container for an element equal to Item (using the
+ generic formal equality operator). The search starts at the element designated
+ by Position. The search checks the subtree rooted by Position in a depth-first
+ order. If no equal element is found, then Find returns No_Element. Otherwise,
+ it returns a cursor designating the first equal element encountered.]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Ancestor_Find (Position : Cursor;
+ Item : Element_Type;
+ @key{return} Cursor;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.]}
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Text=[No_Element is returned if Position is the root
+ node.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Contains (Container : Tree;
+ Item : Element_Type) @key{return} Boolean;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Find (Container, Item) /= No_Element.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Iterate
+ (Container : @key{in} Tree;
+ Process : @key{not null access procedure} (Position : @key{in} Cursor));]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Iterate calls Process.@key{all}
+ with a cursor that designates each element in Container, starting with the
+ root node and proceeding in a depth-first order. Program_Error is propagated
+ if Process.@key{all} tampers with the cursors of Container. Any exception
+ raised by Process.@key{all} is propagated.]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[Process is not called with the root node, which
+ does not have an associated element.]}
+@end{Ramification}
+
+@begin{ImplNote}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[The purpose of the tamper with cursors check is
+ to prevent erroneous execution from the Position parameter of
+ Process.@key{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 @em defeating the purpose of the check.]}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[See Iterate for vectors
+ (@RefSecNum{The Generic Package Containers.Vectors}) for a suggested
+ implementation of the check.]}
+@end{ImplNote}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Iterate_Subtree
+ (Position : @key{in} Cursor;
+ Process : @key{not null access procedure} (Position : @key{in} Cursor));]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Position equals No_Element,
+ then Constraint_Error is propagated. Iterate calls Process.@key{all} with a
+ cursor that designates each element in the subtree rooted by the node
+ designated by Position, starting with the node designated by Position and
+ proceeding in a depth-first order. Program_Error is propagated if
+ Process.@key{all} tampers with the cursors of the tree containing Position.
+ Any exception raised by Process.@key{all} is propagated.]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Iterate (Container : @key{in} Tree)
+ @key{return} Tree_Iterator_Interfaces.Forward_Iterator'Class;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Iterate returns an iterator object
+ that will generate a loop parameter designating each node in Container,
+ starting with the root node and proceeding in a depth-first order.
+ Program_Error is propagated if any operation (in particular, the
+ @nt{sequence_of_statements} of the @nt{loop_statement} whose
+ @nt{iterator_specification} denotes this object) tampers with the cursors of
+ Container while the returned object exists. The returned object from Iterate
+ needs finalization.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Iterate_Subtree (Position : @key{in} Cursor)
+ @key{return} Tree_Iterator_Interfaces.Forward_Iterator'Class;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Iterate_Subtree returns an
+ iterator object that will generate a loop parameter designating each element
+ in the subtree rooted by the node designated by Position, starting with the
+ node designated by Position and proceeding in a depth-first order. If Position
+ equals No_Element, then Constraint_Error is propagated. Program_Error is
+ propagated if any operation (in particular, the @nt{sequence_of_statements} of
+ the @nt{loop_statement} whose @nt{iterator_specification} denotes this object)
+ tampers with the cursors of the container in which the node designated by
+ Position exists while the returned object exists. The returned object from
+ Iterate_Subtree needs finalization.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Child_Count (Parent : Cursor) @key{return} Count_Type;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Child_Count returns the number of
+ child nodes of the node designated by Parent.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Child_Depth (Parent, Child : Cursor) @key{return} Count_Type;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Child or Parent is equal to
+ No_Element, then Constraint_Error is propagated. Otherwise, Child_Depth
+ returns the number of ancestor nodes of Child (including Child itself), up to
+ but not including Parent; in this case Program_Error is propagated if Parent
+ is not an ancestor of Child.]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[Program_Error is propagated if Parent and Child
+ are nodes in different containers.]}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[Child_Depth (Root (Some_Tree), Child) + 1 =
+ Depth (Child) as the root is not counted.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Insert_Child (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ New_Item : @key{in} Element_Type;
+ Count : @key{in} Count_Type := 1);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then
+ Constraint_Error is propagated. If Parent does not designate a node in
+ Container, then Program_Error is propagated. If Before is not equal to
+ No_Element, and does not designate a node in Container, then Program_Error is
+ propagated. If Before is not equal to No_Element, and Container.Parent
+ (Before) is not equal to Parent, then Constraint_Error is propagated.
+ Otherwise, Insert_Child allocates Count nodes containing copies of New_Item
+ and inserts them as children of Parent. If Parent already has child nodes, then
+ the new nodes are inserted prior to the node designated by Before, or, if
+ Before equals No_Element, the new nodes are inserted after the last existing
+ child node of Parent. Any exception raised during allocation of internal
+ storage is propagated, and Container is not modified.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Insert_Child (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ New_Item : @key{in} Element_Type;
+ Position : @key{out} Cursor;
+ Count : @key{in} Count_Type := 1);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1],ARef=[AI05-0257-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then
+ Constraint_Error is propagated. If Parent does not designate a node in
+ Container, then Program_Error is propagated. If Before is not equal to
+ No_Element, and does not designate a node in Container, then Program_Error is
+ propagated. If Before is not equal to No_Element, and Container.Parent
+ (Before) is not equal to Parent, then Constraint_Error is propagated.
+ Otherwise, Insert_Child allocates Count nodes containing copies of New_Item
+ and inserts them as children of Parent. If Parent already has child nodes, then
+ the new nodes are inserted prior to the node designated by Before, or, if
+ Before equals No_Element, the new nodes are inserted after the last existing
+ child node of Parent. Position designates the first newly-inserted node, 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.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Insert_Child (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Position : @key{out} Cursor;
+ Count : @key{in} Count_Type := 1);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0257-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then
+ Constraint_Error is propagated. If Parent does not designate a node in
+ Container, then Program_Error is propagated. If Before is not equal to
+ No_Element, and does not designate a node in Container, then Program_Error is
+ propagated. If Before is not equal to No_Element, and Container.Parent
+ (Before) is not equal to Parent, then Constraint_Error is propagated.
+ Otherwise, Insert_Child allocates Count nodes, the elements contained in the
+ new nodes are initialized by default (see @RefSecNum{Object Declarations}),
+ 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.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Prepend_Child (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ New_Item : @key{in} Element_Type;
+ Count : @key{in} Count_Type := 1);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Insert_Child
+ (Container, Parent, First_Child (Container, Parent), New_Item, Count).]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Append_Child (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ New_Item : @key{in} Element_Type;
+ Count : @key{in} Count_Type := 1);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Insert_Child
+ (Container, Parent, Last_Child (Container, Parent), New_Item, Count).]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Delete_Children (Container : @key{in out} Tree;
+ Parent : @key{in} Cursor);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then
+ Constraint_Error is propagated. If Parent does not designate a node in
+ Container, Program_Error is propagated. Otherwise, Delete_Children removes
+ (from Container) all of the child elements of Parent along with their
+ dependent elements.]}
+
+@begin{Discussion}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[This routine deletes all of the child subtrees
+ of Parent at once. Use Delete_Subtree to delete an individual subtree.]}
+@end{Discussion}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Copy_Subtree (Target : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Source : @key{in} Cursor);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then
+ Constraint_Error is propagated. If Parent does not designate a node in Target,
+ then Program_Error is propagated. If Before is not equal to No_Element, and
+ does not designate a node in Target, then Program_Error is propagated. If
+ Before is not equal to No_Element, and Target.Parent (Before) is not equal to
+ Parent, then Constraint_Error is propagated. If Source designates a root node,
+ then Constraint_Error is propagated. If Source is equal to No_Element, then
+ the operation has no effect. Otherwise, the subtree rooted by Source (which
+ can be from any tree; it does not have to be a subtree of Target) is copied
+ (new nodes are allocated to create a new subtree with the same structure as
+ the Source subtree, with each element initialized from the corresponding
+ element of the Source subtree) and 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.]}
+
+@begin{Discussion}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Discussion}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Splice_Subtree (Target : @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Source : @key{in out} Tree;
+ Position : @key{in out} Cursor);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then
+ Constraint_Error is propagated. If Parent does not designate a node in Target,
+ then Program_Error is propagated. If Before is not equal to No_Element, and
+ does not designate a node in Target, then Program_Error is propagated. If
+ Before is not equal to No_Element, and Target.Parent (Before) is not equal to
+ Parent, then Constraint_Error is propagated. If Position equals No_Element,
+ Constraint_Error is propagated. If Position does not designate a node in
+ Source or designates a root node, then Program_Error is propagated. If Source
+ denotes the same object as Target, then:
+ if Position equals Before there is no effect; if Position designates an
+ ancestor of Parent or is equal to Parent, Constraint_Error is propagated;
+ otherwise, the subtree rooted by the element designated by Position is
+ moved to be a child of Parent. If Parent already has child nodes, then the
+ moved nodes are inserted prior to the node designated by Before, or, if Before
+ equals No_Element, the moved nodes are inserted after the last existing child
+ node of Parent. 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.]}
+
+@begin{Reason}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[We can't allow moving the subtree of Position to
+ a descendant node of the subtree, as the descendant node will be part of the
+ subtree being moved. 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 @i<O>(Depth(Source)).]}
+@end{Reason}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Text=[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.]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[For this reason there is no operation to splice
+ an entire tree, as that would necessarily involve splicing a root node.]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Splice_Subtree (Container: @key{in out} Tree;
+ Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Position : @key{in} Cursor);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then
+ Constraint_Error is propagated. If Parent does not designate a node in
+ Container, then Program_Error is propagated. If Before is not equal to
+ No_Element, and does not designate a node in Container, then Program_Error is
+ propagated. If Before is not equal to No_Element, and Target.Parent (Before)
+ is not equal to Parent, then Constraint_Error is propagated. If Position
+ equals No_Element, 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 or is equal to Parent, Constraint_Error is
+ propagated. Otherwise, the subtree rooted by the element designated by
+ Position is moved to be a child of Parent. If Parent already has child nodes,
+ then the moved nodes are inserted prior to the node designated by Before, or,
+ if Before equals No_Element, the moved nodes are inserted after the last
+ existing child node of Parent. The parent of the element designated by
+ Position is set to Parent.]}
+
+@begin{Reason}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[We can't allow moving the subtree of Position to
+ a descendant node of the subtree, as the descendant node will be part of the
+ subtree being moved.]}
+@end{Reason}
+
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Splice_Children (Target : @key{in out} Tree;
+ Target_Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Source : @key{in out} Tree;
+ Source_Parent : @key{in} Cursor);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[If Target_Parent equals
+ No_Element, then Constraint_Error is propagated. If Target_Parent does not
+ designate a node in Target, then Program_Error is propagated. If Before is not
+ equal to No_Element, and does not designate an element in Target, then
+ Program_Error is propagated. If Source_Parent equals No_Element, then
+ Constraint_Error is propagated. If Source_Parent does not designate a node in
+ Source, then Program_Error is propagated. If Before is not equal to
+ No_Element, and Target.Parent (Before) is not equal to Target_Parent, then
+ Constraint_Error is propagated.]}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Type=[Leading],Text=[If Source denotes the same object as Target, then:]}
+
+@begin{Itemize}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[if Target_Parent equals Source_Parent there is
+ no effect; else]}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[if Source_Parent is an ancestor of
+ Target_Parent, then Constraint_Error is propagated; else]}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Text=[the child elements (and their descendants) of
+ Source_Parent are moved to be child elements of Target_Parent. If
+ Target_Parent already has child elements, then the moved elements are
+ inserted prior to the node designated by Before, or, if Before equals
+ No_Element, the moved elements are inserted after the last existing child
+ node of Target_Parent. The parent of each moved child element is set to
+ Target_Parent.]}
+@end{Itemize}
+
+@begin{Reason}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[We can't allow moving the children of Source_Parent to a
+ descendant node, as the descendant node will be part of one of the
+ subtrees being moved.]}
+@end{Reason}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Text=[Otherwise (if Source does not denote the same
+ object as Target), the child elements (and their descendants) of Source_Parent
+ are removed from Source and moved to Target. The child elements are inserted
+ as children of Target_Parent. If Target_Parent already has child elements, then
+ the moved elements are inserted prior to the node designated by Before, or, if
+ Before equals No_Element, the moved elements are inserted after the last
+ existing child node of Target_Parent. In each of these cases, the overall
+ count of Target is incremented by Subtree_Count (Source_Node_Parent)-1, and
+ the overall count of Source is decremented by Subtree_Count
+ (Source_Node_Parent)-1.]}
+
+@begin{Ramification}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[The node designated by Source_Parent is not
+ moved, thus we never need to update Source_Parent.]}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[Move (Target, Source) could be written
+ Splice_Children (Target, Target.Root, No_Element, Source, Source.Root);]}
+@end{Ramification}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Splice_Children (Container : @key{in out} Tree;
+ Target_Parent : @key{in} Cursor;
+ Before : @key{in} Cursor;
+ Source_Parent : @key{in} Cursor);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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 Container.Parent (Before) is not equal to Target_Parent, then
+ Constraint_Error is propagated. If Target_Parent equals Source_Parent there is
+ no effect. If Source_Parent is an ancestor of Target_Parent, then
+ Constraint_Error is propagated. Otherwise the child elements (and their
+ descendants) of Source_Parent are moved to be child elements of Target_Parent.
+ If Target_Parent already has child elements, then the moved elements are
+ inserted prior to the node designated by Before, or, if Before equals
+ No_Element, the moved elements are inserted after the last existing child node
+ of Target_Parent. The parent of each moved child element is set to
+ Target_Parent.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Parent (Position : Cursor) @key{return} Cursor;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} First_Child (Parent : Cursor) @key{return} Cursor;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} First_Child_Element (Parent : Cursor) @key{return} Element_Type;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Element (First_Child (Parent)).]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Last_Child (Parent : Cursor) @key{return} Cursor;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Last_Child_Element (Parent : Cursor) @key{return} Element_Type;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Element (Last_Child (Parent)).]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Next_Sibling (Position : Cursor) @key{return} Cursor;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Previous_Sibling (Position : Cursor) @key{return} Cursor;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[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.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Next_Sibling (Position : @key{in out} Cursor);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Position := Next_Sibling (Position);]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Previous_Sibling (Position : @key{in out} Cursor);]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+ @ChgAdded{Version=[3],Type=[Trailing],Text=[Equivalent to Position := Previous_Sibling (Position);]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Iterate_Children
+ (Parent : @key{in} Cursor;
+ Process : @key{not null access procedure} (Position : @key{in} Cursor));]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+@ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then
+Constraint_Error is propagated.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[Iterate_Children calls Process.@key{all} with a
+cursor that designates each child node of Parent, starting with the first child
+node and moving the cursor as per the function Next_Sibling.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[Program_Error is propagated if Process.@key{all}
+tampers with the cursors of the tree containing Parent. Any exception raised by
+Process.@key{all} is propagated.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{procedure} Reverse_Iterate_Children
+ (Parent : @key{in} Cursor;
+ Process : @key{not null access procedure} (Position : @key{in} Cursor));]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+@ChgAdded{Version=[3],Type=[Trailing],Text=[If Parent equals No_Element, then
+Constraint_Error is propagated.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[Reverse_Iterate_Children calls Process.@key{all}
+with a cursor that designates each child node of Parent, starting with the last
+child node and moving the cursor as per the function Previous_Sibling.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[Program_Error is propagated if Process.@key{all}
+tampers with the cursors of the tree containing Parent. Any exception raised by
+Process.@key{all} is propagated.]}
+
+@begin{Example}
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],KeepNext=[T],Text=[@key{function} Iterate_Children (Container : @key[in] Tree; Parent : @key[in] Cursor)
+ @key[return] Tree_Iterator_Interfaces.Reversible_Iterator'Class;]}
+@end{Example}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Type=[Trailing],Text=[Iterate_Children returns a
+reversible iterator object that will generate a loop parameter designating each
+child node of Parent. If Parent equals No_Element, then Constraint_Error is
+propagated. If Parent does not designate a node in Container, then Program_Error
+is propagated. 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. Program_Error is propagated if any operation (in particular,
+the @nt{sequence_of_statements} of the @nt{loop_statement} whose
+@nt{iterator_specification} denotes this object) tampers with the cursors of
+Container while the returned object exists. The returned object from
+Iterate_Children needs finalization.]}
+
+@end{DescribeCode}
+
+@end{StaticSem}
+
+@begin{Bounded}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0248-1]}
+@ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)}
+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.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[@PDefn2{Term=(bounded error),Sec=(cause)}
+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 @key[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.]}
+@end{Bounded}
+
+@begin{Erron}
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Type=[Leading],Text=[A Cursor
+value is @i<invalid> if any of the following have occurred since
+it was created:@Defn2{Term=[invalid cursor],Sec=[of a tree]}
+@PDefn2{Term=[cursor],Sec=[invalid]}]}
+@begin{Itemize}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[The tree that contains the element it designates has
+been finalized;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[The tree that contains the element it designates has
+been used as the Source or Target of a call to Move;]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[The tree that contains the element it designates has
+been used as the Target of a call to Assign or the target of an
+@nt{assignment_statement};]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[The element it designates has been removed from the
+tree that previously contained the element.]}
+@begin{Reason}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Reason}
+
+@end{Itemize}
+
+@ChgRef{Version=[3],Kind=[AddedNormal]}
+@ChgAdded{Version=[3],Text=[The result of "=" or Has_Element is unspecified if
+it is called with an invalid cursor parameter.@PDefn{unspecified} Execution is
+erroneous if any other subprogram declared in Containers.Multiway_Trees is
+called with an invalid cursor parameter.]}
+
+@begin{Discussion}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Discussion}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
+@ChgAdded{Version=[3],Text=[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.]}
+@begin{Reason}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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 non-existent
+ 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.)]}
+@end{Reason}
+@end{Erron}
+
+@begin{ImplReq}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[No storage associated with a multiway tree object
+shall be lost upon assignment or scope exit.]}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[The execution of an @nt{assignment_statement} for
+a tree shall have the effect of copying the elements from the source tree
+object to the target tree object.]}
+
+@begin{ImplNote}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[An assignment of a Tree is a @lquotes@;deep@rquotes
+ copy; that is the elements are copied as well as the data structures.
+ We say @lquotes@;effect of@rquotes 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.]}
+@end{ImplNote}
+@end{ImplReq}
+
+@begin{ImplAdvice}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[Containers.Multiway_Trees should be implemented
+similarly to a multiway tree. In particular, if @i{N} is the overall number of nodes
+for a particular tree, then the worst-case time complexity of Element, Parent,
+First_Child, Last_Child, Insert_Child with Count=1, and Delete should be @i{O}(log
+@i{N}).]}
+@ChgImplAdvice{Version=[3],Kind=[AddedNormal],Text=[@ChgAdded{Version=[3],
+Text=[The worst-case time complexity of the Element, Parent,
+First_Child, Last_Child, Insert_Child with Count=1, and Delete
+operations of Containers.Multiway_Trees should be @i{O}(log @i<N>).]}]}
+
+@begin{Reason}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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 @i{O}(@i<N>) time to access
+ elements, that program could be unusable when the trees are large. We allow
+ @i{O}(log @i<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.]}
+@end{Reason}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[Move should not copy elements, and should minimize
+copying of internal data structures.]}
+@ChgImplAdvice{Version=[3],Kind=[AddedNormal],Text=[@ChgAdded{Version=[3],
+Text=[Containers.Multiway_Trees.Move should not copy elements, and should
+minimize copying of internal data structures.]}]}
+
+@begin{ImplNote}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[Usually that can be accomplished simply by
+ moving the pointer(s) to the internal data structures from the Source
+ container to the Target container.]}
+@end{ImplNote}
+
+@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1]}
+@ChgAdded{Version=[3],Text=[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.]}
+@ChgImplAdvice{Version=[3],Kind=[AddedNormal],Text=[@ChgAdded{Version=[3],
+Text=[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.]}]}
+
+@begin{Reason}
+ @ChgRef{Version=[3],Kind=[AddedNormal]}
+ @ChgAdded{Version=[3],Text=[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.]}
+@end{Reason}
+@end{ImplAdvice}
+
+@begin{Extend2005}
+ @ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0136-1],ARef=[AI05-0257-1]}
+ @ChgAdded{Version=[3],Text=[@Defn{extensions to Ada 2005}
+ The generic package Containers.Multiway_Trees is new.]}
+@end{Extend2005}
+
+
@LabeledAddedSubclause{Version=[2],Name=[The Generic Package Containers.Indefinite_Vectors]}
@begin{Intro}
@@ -2826,9 +4645,6 @@
@ChgRef{Version=[3],Kind=[AddedNormal],ARef=[AI05-0212-1]}
@ChgAdded{Version=[3],Text=[This example of container use is new.]}
@end{DiffWord2005}
-
-
-
Questions? Ask the ACAA Technical Agent