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/3
{
AI05-0136-1}
A multiway tree container object manages a tree
of internal nodes, each of which contains an element and pointers
to the parent, first child, last child, next (successor) sibling, and
previous (predecessor) sibling internal nodes. A
cursor designates a particular node within a tree (and by extension the
element contained in that node, 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/3
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).
There is a special node, the root, which is always present and
has neither an associated element value nor any parent node. The root
node provides a place to add nodes to an otherwise empty tree and represents
the bottom of the tree.
4/3
A node that has no children
is called a leaf node. The ancestors
of a node are the parent node, the parent of the parent node, and so
on until a node with no parent is reached. Similarly,
the descendants of a node are the child nodes, the children of
each child node, and so on.
5/3
The nodes of a subtree can
be visited in several different orders. For a depth-first order,
the last step of visiting a node is to visit the nodes of its child list
in order, recursively.
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/3
{
AI05-0136-1}
{
AI05-0212-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
pragma Preelaborate(Multiway_Trees);
pragma Remote_Types(Multiway_Trees);8/3
{
AI05-0136-1}
{
AI05-0212-1}
type Tree is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
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;
12/3
function Has_Element (Position : Cursor) return Boolean;
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;
16/3
function Is_Empty (Container : Tree) return Boolean;
17/3
function Node_Count (Container : Tree) return Count_Type;
18/3
function Subtree_Node_Count (Position : Cursor) return Count_Type;
19/3
function Depth (Position : Cursor) return Count_Type;
20/3
function Is_Root (Position : Cursor) return Boolean;
21/3
function Is_Leaf (Position : Cursor) return Boolean;
22/3
function Root (Container : Tree) return Cursor;
23/3
procedure Clear (Container : in out Tree);
24/3
function Element (Position : Cursor) return Element_Type;
25/3
procedure Replace_Element (Container : in out Tree;
Position : in Cursor;
New_Item : in Element_Type);
26/3
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
27/3
procedure Update_Element
(Container : in out Tree;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
28/3
{
AI05-0212-1}
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;29/3
{
AI05-0212-1}
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;30/3
{
AI05-0212-1}
function Constant_Reference (Container : aliased in Tree;
Position : in Cursor)
return Constant_Reference_Type;31/3
{
AI05-0212-1}
function Reference (Container : aliased in out Tree;
Position : in Cursor)
return Reference_Type;32/3
procedure Assign (Target : in out Tree; Source : in Tree);
33/3
function Copy (Source : Tree) return Tree;
34/3
procedure Move (Target : in out Tree;
Source : in out Tree);
35/3
procedure Delete_Leaf (Container : in out Tree;
Position : in out Cursor);
36/3
procedure Delete_Subtree (Container : in out Tree;
Position : in out Cursor);
37/3
procedure Swap (Container : in out Tree;
I, J : in Cursor);
38/3
function Find (Container : Tree;
Item : Element_Type)
return Cursor;
39/3
function Find_In_Subtree (Position : Cursor;
Item : Element_Type)
return Cursor;
40/3
function Ancestor_Find (Position : Cursor;
Item : Element_Type)
return Cursor;
41/3
function Contains (Container : Tree;
Item : Element_Type) return Boolean;
42/3
procedure Iterate
(Container : in Tree;
Process : not null access procedure (Position : in Cursor));
43/3
procedure Iterate_Subtree
(Position : in Cursor;
Process : not null access procedure (Position : in Cursor));
44/3
{
AI05-0212-1}
function Iterate (Container : in Tree)
return Tree_Iterator_Interfaces.Forward_Iterator'Class;45/3
{
AI05-0212-1}
function Iterate_Subtree (Position : in Cursor)
return Tree_Iterator_Interfaces.Forward_Iterator'Class;46/3
function Child_Count (Parent : Cursor) return Count_Type;
47/3
function Child_Depth (Parent, Child : Cursor) return Count_Type;
48/3
procedure Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
49/3
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);
50/3
procedure Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
51/3
procedure Prepend_Child (Container : in out Tree;
Parent : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
52/3
procedure Append_Child (Container : in out Tree;
Parent : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
53/3
procedure Delete_Children (Container : in out Tree;
Parent : in Cursor);
54/3
procedure Copy_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Cursor);
55/3
procedure Splice_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Position : in out Cursor);
56/3
procedure Splice_Subtree (Container: in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : in Cursor);
57/3
procedure Splice_Children (Target : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Source_Parent : in Cursor);
58/3
procedure Splice_Children (Container : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source_Parent : in Cursor);
59/3
function Parent (Position : Cursor) return Cursor;
60/3
function First_Child (Parent : Cursor) return Cursor;
61/3
function First_Child_Element (Parent : Cursor) return Element_Type;
62/3
function Last_Child (Parent : Cursor) return Cursor;
63/3
function Last_Child_Element (Parent : Cursor) return Element_Type;
64/3
function Next_Sibling (Position : Cursor) return Cursor;
65/3
function Previous_Sibling (Position : Cursor) return Cursor;
66/3
procedure Next_Sibling (Position : in out Cursor);
67/3
procedure Previous_Sibling (Position : in out Cursor);
68/3
procedure Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor));
69/3
procedure Reverse_Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor));
70/3
{
AI05-0212-1}
function Iterate_Children (Container : in Tree; Parent : in Cursor)
return Tree_Iterator_Interfaces.Reversible_Iterator'Class;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}
Tree'Write writes exactly Node_Count (Tree) - 1
elements of the tree to the stream. It may write additional information
about the tree as well. Tree'Read reads exactly Node_Count (Tree) - 1
elements of Tree from the stream and consumes any additional information
written by Tree'Write.78.a/3
Ramification: Streaming
more elements than the container length is wrong. For implementation
implications of this rule, see the Implementation Note in A.18.2.
79/3
{
AI05-0136-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.]80/3
{
AI05-0136-1}
A subprogram is said to tamper
with cursors of a tree object T if:81/3
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
81.a/3
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.
82/3
{
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; or83/3
it finalizes T; or
84/3
it calls Assign with T
as the Target parameter; or
85/3
it calls the Move procedure
with T as a parameter.
85.a/3
Reason: Swap copies
elements rather than reordering them, so it doesn't tamper with cursors.
86/3
{
AI05-0136-1}
A subprogram is said to tamper
with elements of a tree object T if:87/3
it tampers with cursors of
T; or
88/3
it replaces one or more elements
of T, that is, it calls the Replace_Element or Swap procedures
with T as a parameter.
88.a/3
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/3
{
AI05-0265-1}
If tampering
with cursors is prohibited for a particular tree object T,
Program_Error is propagated by any language-defined subprogram that is
defined to tamper with the cursors of T. Similarly, if tampering
with elements is prohibited for a particular tree object T,
Program_Error is propagated by any language-defined subprogram that is
defined to tamper with the elements of T.90/3
function Has_Element (Position : Cursor) return Boolean;
91/3
Returns
True if Position designates an element, and returns False otherwise.
91.a/3
To be honest: 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).
92/3
function Equal_Subtree (Left_Position : Cursor;
Right_Position: Cursor) return Boolean;
93/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.93.a/3
Ramification: Left_Position
and Right_Position do not need to be from the same tree.
93.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.
94/3
function "=" (Left, Right : Tree) return Boolean;
95/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.95.a/3
Implementation Note:
Similar considerations apply here as apply to Equal_Subtree. The
actual number of calls performed is unspecified.
96/3
function Node_Count (Container : Tree) return Count_Type;
97/3
{
AI05-0136-1}
Node_Count returns the number of nodes in Container.97.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)).
98/3
function Subtree_Node_Count (Position : Cursor) return Count_Type;
99/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.100/3
function Is_Empty (Container : Tree) return Boolean;
101/3
{
AI05-0136-1}
Equivalent to Node_Count (Container) = 1.101.a/3
Ramification: An
empty tree contains just the root node.
102/3
function Depth (Position : Cursor) return Count_Type;
103/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).103.a/3
Ramification: Depth
(Root (Some_Tree)) = 1.
104/3
function Is_Root (Position : Cursor) return Boolean;
105/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/3
function Is_Leaf (Position : Cursor) return Boolean;
107/3
{
AI05-0136-1}
Is_Leaf returns True if Position designates a node
that does not have any child nodes; and returns False otherwise.107.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/3
function Root (Container : Tree) return Cursor;
109/3
{
AI05-0136-1}
Root returns a cursor that designates the root
node of Container.109.a/3
Ramification: There
is always a root node, even in an empty container, so this function never
returns No_Element.
110/3
procedure Clear (Container : in out Tree);
111/3
111.a/3
Ramification: The
root node is not removed; all trees have a root node.
112/3
function Element (Position : Cursor) return Element_Type;
113/3
{
AI05-0136-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.113.a/3
Ramification: The
root node does not contain an element, so that value cannot be read or
written.
114/3
procedure Replace_Element (Container : in out Tree;
Position : in Cursor;
New_Item : in Element_Type);
115/3
{
AI05-0136-1}
{
AI05-0264-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.116/3
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
117/3
{
AI05-0136-1}
{
AI05-0265-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 Process.all. Any exception
raised by Process.all is propagated.118/3
procedure Update_Element
(Container : in out Tree;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
119/3
{
AI05-0136-1}
{
AI05-0264-1}
{
AI05-0265-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 Process.all. Any exception
raised by Process.all is propagated.120/3
If Element_Type is unconstrained
and definite, then the actual Element parameter of Process.all
shall be unconstrained.
120.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.
121/3
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
122/3
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
123/3
{
AI05-0212-1}
The types Constant_Reference_Type and Reference_Type
need finalization.124/3
The default initialization
of an object of type Constant_Reference_Type or Reference_Type propagates
Program_Error.
124.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.
125/3
function Constant_Reference (Container : aliased in Tree;
Position : in Cursor)
return Constant_Reference_Type;
126/3
{
AI05-0212-1}
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.127/3
{
AI05-0212-1}
{
AI05-0265-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.128/3
function Reference (Container : aliased in out Tree;
Position : in Cursor)
return Reference_Type;
129/3
{
AI05-0212-1}
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.130/3
{
AI05-0212-1}
{
AI05-0265-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.131/3
procedure Assign (Target : in out Tree; Source : in Tree);
132/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.132.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.
132.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.
133/3
function Copy (Source : Tree) return Tree;
134/3
{
AI05-0136-1}
Returns a tree with the same structure as Source
and whose elements are initialized from the corresponding elements of
Source.135/3
procedure Move (Target : in out Tree;
Source : in out Tree);
136/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.137/3
procedure Delete_Leaf (Container : in out Tree;
Position : in out Cursor);
138/3
{
AI05-0136-1}
{
AI05-0248-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. Finally, Position is set to No_Element.138.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).
138.b/3
The root node cannot be
deleted.
139/3
procedure Delete_Subtree (Container : in out Tree;
Position : in out Cursor);
140/3
{
AI05-0136-1}
{
AI05-0264-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, the node designated by Position and all of the
descendant nodes of that node), and Position is set to No_Element.140.a/3
Ramification: The
root node cannot be deleted. To delete the entire contents of the tree,
call Clear(Container).
141/3
procedure Swap (Container : in out Tree;
I, J : in Cursor);
142/3
{
AI05-0136-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.142.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.
142.b/3
The root nodes do not
contain element values, so they cannot be swapped.
142.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.
143/3
function Find (Container : Tree;
Item : Element_Type)
return Cursor;
144/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.145/3
function Find_In_Subtree (Position : Cursor;
Item : Element_Type)
return Cursor;
146/3
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0262-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.146.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/3
function Ancestor_Find (Position : Cursor;
Item : Element_Type)
return Cursor;
148/3
{
AI05-0136-1}
{
AI05-0248-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. 148.a/3
Ramification: {
AI05-0248-1}
No_Element is returned if Position is the root
node.
149/3
function Contains (Container : Tree;
Item : Element_Type) return Boolean;
150/3
{
AI05-0136-1}
Equivalent to Find (Container, Item) /= No_Element.151/3
procedure Iterate
(Container : in Tree;
Process : not null access procedure (Position : in Cursor));
152/3
{
AI05-0136-1}
{
AI05-0265-1}
Iterate calls Process.all with a cursor
that designates each element in Container, starting with the root node
and proceeding in a depth-first order. Tampering with the cursors of
Container is prohibited during the execution of Process.all. Any
exception raised by Process.all is propagated.152.a/3
Ramification: Process
is not called with the root node, which does not have an associated element.
152.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.
152.c/3
See Iterate for vectors
(A.18.2) for a suggested implementation
of the check.
153/3
procedure Iterate_Subtree
(Position : in Cursor;
Process : not null access procedure (Position : in Cursor));
154/3
{
AI05-0136-1}
{
AI05-0265-1}
If Position equals No_Element, then Constraint_Error
is propagated. Iterate_Subtree calls Process.all with a cursor
that designates each element in the subtree rooted by the node designated
by Position, starting with the node designated by Position and proceeding
in a depth-first order. Tampering with the cursors of the tree containing
Position is prohibited during the execution of Process.all. Any
exception raised by Process.all is propagated.154.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/3
function Iterate (Container : in Tree)
return Tree_Iterator_Interfaces.Forward_Iterator'Class;
156/3
{
AI05-0212-1}
{
AI05-0265-1}
Iterate returns an iterator object that will generate
a value for the loop parameter designating each node in Container, starting
with the root node and proceeding in a depth-first order. 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/3
function Iterate_Subtree (Position : in Cursor)
return Tree_Iterator_Interfaces.Forward_Iterator'Class;
158/3
{
AI05-0212-1}
{
AI05-0265-1}
Iterate_Subtree returns an iterator object that
will generate a value for the 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. 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/3
function Child_Count (Parent : Cursor) return Count_Type;
160/3
{
AI05-0136-1}
Child_Count returns the number of child nodes of
the node designated by Parent.161/3
function Child_Depth (Parent, Child : Cursor) return Count_Type;
162/3
{
AI05-0136-1}
{
AI05-0262-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.162.a/3
Ramification: Program_Error
is propagated if Parent and Child are nodes in different containers.
162.b/3
Child_Depth (Root (Some_Tree),
Child) + 1 = Depth (Child) as the root is not counted.
163/3
procedure Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
164/3
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0262-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.165/3
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);
166/3
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0257-1}
{
AI05-0262-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.167/3
procedure Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
168/3
{
AI05-0136-1}
{
AI05-0257-1}
{
AI05-0262-1}
{
AI05-0264-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.169/3
procedure Prepend_Child (Container : in out Tree;
Parent : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
170/3
{
AI05-0136-1}
Equivalent to Insert_Child (Container, Parent,
First_Child (Container, Parent), New_Item, Count).171/3
procedure Append_Child (Container : in out Tree;
Parent : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
172/3
{
AI05-0136-1}
Equivalent to Insert_Child (Container, Parent,
Last_Child (Container, Parent), New_Item, Count).173/3
procedure Delete_Children (Container : in out Tree;
Parent : in Cursor);
174/3
{
AI05-0136-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 child nodes of Parent along with their descendant nodes.174.a/3
Discussion: This
routine deletes all of the child subtrees of Parent at once. Use Delete_Subtree
to delete an individual subtree.
175/3
procedure Copy_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Cursor);
176/3
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0262-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.176.a/3
Discussion: We
only need one routine here, as the source object is not modified, so
we can use the same routine for both copying within and between containers.
176.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/3
procedure Splice_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Position : in out Cursor);
178/3
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0262-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 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.178.a/3
Reason: We can't
allow moving the subtree of Position to a descendant node of the subtree,
as the descendant node will be part of the subtree being moved. 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)).
179/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.179.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.
179.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.
179.c/3
For this reason there
is no operation to splice an entire tree, as that would necessarily involve
splicing a root node.
180/3
procedure Splice_Subtree (Container: in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : in Cursor);
181/3
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0262-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 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.181.a/3
Reason: We can't
allow moving the subtree of Position to a descendant node of the subtree,
as the descendant node will be part of the subtree being moved.
182/3
procedure Splice_Children (Target : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Source_Parent : in Cursor);
183/3
{
AI05-0136-1}
{
AI05-0262-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.184/3
If
Source denotes the same object as Target, then:
185/3
if Target_Parent
equals Source_Parent there is no effect; else
186/3
if Source_Parent
is an ancestor of Target_Parent, then Constraint_Error is propagated;
else
187/3
{
AI05-0136-1}
{
AI05-0248-1}
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.
187.a/3
Reason: We can't
allow moving the children of Source_Parent to a descendant node, as the
descendant node will be part of one of the subtrees being moved.
188/3
{
AI05-0136-1}
{
AI05-0248-1}
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.188.a/3
Ramification: The
node designated by Source_Parent is not moved, thus we never need to
update Source_Parent.
188.b/3
Move (Target, Source)
could be written Splice_Children (Target, Target.Root, No_Element, Source,
Source.Root);
189/3
procedure Splice_Children (Container : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source_Parent : in Cursor);
190/3
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0262-1}
{
AI05-0264-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, 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.191/3
function Parent (Position : Cursor) return Cursor;
192/3
{
AI05-0136-1}
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/3
function First_Child (Parent : Cursor) return Cursor;
194/3
{
AI05-0136-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/3
function First_Child_Element (Parent : Cursor) return Element_Type;
196/3
{
AI05-0136-1}
Equivalent to Element (First_Child (Parent)).197/3
function Last_Child (Parent : Cursor) return Cursor;
198/3
{
AI05-0136-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/3
function Last_Child_Element (Parent : Cursor) return Element_Type;
200/3
{
AI05-0136-1}
Equivalent to Element (Last_Child (Parent)).201/3
function Next_Sibling (Position : Cursor) return Cursor;
202/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/3
function Previous_Sibling (Position : Cursor) return Cursor;
204/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/3
procedure Next_Sibling (Position : in out Cursor);
206/3
{
AI05-0136-1}
Equivalent to Position := Next_Sibling (Position);207/3
procedure Previous_Sibling (Position : in out Cursor);
208/3
{
AI05-0136-1}
Equivalent to Position := Previous_Sibling (Position);209/3
procedure Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor));
210/3
211/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.
212/3
{
AI05-0265-1}
Tampering with the cursors of the tree containing
Parent is prohibited during the execution of Process.all. Any
exception raised by Process.all is propagated.213/3
procedure Reverse_Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor));
214/3
215/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.
216/3
{
AI05-0265-1}
Tampering with the cursors of the tree containing
Parent is prohibited during the execution of Process.all. Any
exception raised by Process.all is propagated.217/3
function Iterate_Children (Container : in Tree; Parent : in Cursor)
return Tree_Iterator_Interfaces.Reversible_Iterator'Class;
218/3
{
AI05-0212-1}
{
AI05-0265-1}
Iterate_Children returns a reversible iterator
object that will generate a value for the 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. 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.Bounded (Run-Time) Errors
219/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.220/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
221/3
{
AI05-0136-1}
A Cursor value is invalid if any of the
following have occurred since it was created: 222/3
The tree that contains the
element it designates has been finalized;
223/3
The tree that contains the
element it designates has been used as the Source or Target of a call
to Move;
224/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;
225/3
The element it designates
has been removed from the tree that previously contained the element.
225.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.
226/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.
226.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.
226.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.
227/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. 227.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 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.)
Implementation Requirements
228/3
{
AI05-0136-1}
No storage associated with a multiway tree object
shall be lost upon assignment or scope exit.229/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.229.a/3
Implementation Note:
An assignment of a Tree is a “deep” copy; that is the
elements are copied as well as the data structures. We say “effect
of” in order to allow the implementation to avoid copying elements
immediately if it wishes. For instance, an implementation that avoided
copying until one of the containers is modified would be allowed.
Implementation Advice
230/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).
230.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).
230.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.
231/3
{
AI05-0136-1}
Move should not copy elements, and should minimize
copying of internal data structures. 231.a/3
Implementation Advice:
Containers.Multiway_Trees.Move should
not copy elements, and should minimize copying of internal data structures.
231.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.
232/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. 232.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.
232.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
232.c/3
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
