A.18.10 The Generic Package Containers.Multiway_Trees
{
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.
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.
{
AI05-0136-1}
{
AI12-0078-1}
{
AI12-0159-1}
A multiway tree container object manages a tree of
nodes, consisting
of a
root node and a set
of
internal nodes; each internal node 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.
{
AI05-0136-1}
{
AI05-0269-1}
{
AI12-0078-1}
A
subtree is a particular node (which
roots the subtree)
and all of its child nodes (including all of the children of the child
nodes, recursively).
The
root node is always present and has neither an associated element value
nor any parent node; it has pointers to its first child and its last
child, if any. The root node provides a place to add nodes to an otherwise
empty tree and represents the base of the tree.
{
AI05-0136-1}
{
AI05-0269-1}
A node that has no children is called a
leaf node.
The
ancestors of a node are the node itself, its parent node,
the parent of the parent node, and so on until a node with no parent
is reached.
Similarly, the
descendants of
a node are the node itself, its child nodes, the children of each child
node, and so on.
{
AI05-0136-1}
{
AI05-0262-1}
{
AI05-0269-1}
The nodes of a subtree can be visited in several different orders. For
a
depth-first order, after visiting a node, the nodes of its child
list are each visited in depth-first order, with each child node visited
in natural order (first child to last child).
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
{
AI05-0136-1}
The generic library package Containers.Multiway_Trees has the following
declaration:
{
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);
{
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);
type Cursor
is private;
pragma Preelaborable_Initialization(Cursor);
Empty_Tree :
constant Tree;
No_Element :
constant Cursor;
function Has_Element (Position : Cursor)
return Boolean;
{
AI05-0212-1}
package Tree_Iterator_Interfaces
is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
function Equal_Subtree (Left_Position : Cursor;
Right_Position: Cursor)
return Boolean;
function "=" (Left, Right : Tree) return Boolean;
function Is_Empty (Container : Tree)
return Boolean;
function Node_Count (Container : Tree)
return Count_Type;
function Subtree_Node_Count (Position : Cursor)
return Count_Type;
function Depth (Position : Cursor)
return Count_Type;
function Is_Root (Position : Cursor)
return Boolean;
function Is_Leaf (Position : Cursor)
return Boolean;
function Root (Container : Tree)
return Cursor;
procedure Clear (Container :
in out Tree);
function Element (Position : Cursor)
return Element_Type;
procedure Replace_Element (Container :
in out Tree;
Position :
in Cursor;
New_Item :
in Element_Type);
procedure Query_Element
(Position :
in Cursor;
Process :
not null access procedure (Element :
in Element_Type));
procedure Update_Element
(Container :
in out Tree;
Position :
in Cursor;
Process :
not null access procedure
(Element :
in out Element_Type));
{
AI05-0212-1}
type Constant_Reference_Type
(Element :
not null access constant Element_Type)
is private
with Implicit_Dereference => Element;
{
AI05-0212-1}
type Reference_Type (Element :
not null access Element_Type)
is private
with Implicit_Dereference => Element;
{
AI05-0212-1}
function Constant_Reference (Container :
aliased in Tree;
Position :
in Cursor)
return Constant_Reference_Type;
{
AI05-0212-1}
function Reference (Container :
aliased in out Tree;
Position :
in Cursor)
return Reference_Type;
procedure Assign (Target :
in out Tree; Source :
in Tree);
function Copy (Source : Tree)
return Tree;
procedure Move (Target :
in out Tree;
Source :
in out Tree);
procedure Delete_Leaf (Container :
in out Tree;
Position :
in out Cursor);
procedure Delete_Subtree (Container :
in out Tree;
Position :
in out Cursor);
procedure Swap (Container :
in out Tree;
I, J :
in Cursor);
function Find (Container : Tree;
Item : Element_Type)
return Cursor;
function Contains (Container : Tree;
Item : Element_Type)
return Boolean;
procedure Iterate
(Container :
in Tree;
Process :
not null access procedure (Position :
in Cursor));
procedure Iterate_Subtree
(Position :
in Cursor;
Process :
not null access procedure (Position :
in Cursor));
{
AI05-0212-1}
function Iterate (Container :
in Tree)
return Tree_Iterator_Interfaces.Forward_Iterator'Class;
{
AI05-0212-1}
function Iterate_Subtree (Position :
in Cursor)
return Tree_Iterator_Interfaces.Forward_Iterator'Class;
function Child_Count (Parent : Cursor)
return Count_Type;
function Child_Depth (Parent, Child : Cursor)
return Count_Type;
procedure Insert_Child (Container :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Insert_Child (Container :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
New_Item :
in Element_Type;
Position :
out Cursor;
Count :
in Count_Type := 1);
procedure Insert_Child (Container :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
Position :
out Cursor;
Count :
in Count_Type := 1);
procedure Prepend_Child (Container :
in out Tree;
Parent :
in Cursor;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Append_Child (Container :
in out Tree;
Parent :
in Cursor;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Delete_Children (Container :
in out Tree;
Parent :
in Cursor);
procedure Copy_Subtree (Target :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
Source :
in Cursor);
procedure Splice_Subtree (Target :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
Source :
in out Tree;
Position :
in out Cursor);
procedure Splice_Subtree (Container:
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
Position :
in Cursor);
procedure Splice_Children (Target :
in out Tree;
Target_Parent :
in Cursor;
Before :
in Cursor;
Source :
in out Tree;
Source_Parent :
in Cursor);
procedure Splice_Children (Container :
in out Tree;
Target_Parent :
in Cursor;
Before :
in Cursor;
Source_Parent :
in Cursor);
function Parent (Position : Cursor)
return Cursor;
function First_Child (Parent : Cursor)
return Cursor;
function First_Child_Element (Parent : Cursor)
return Element_Type;
function Last_Child (Parent : Cursor)
return Cursor;
function Last_Child_Element (Parent : Cursor)
return Element_Type;
function Next_Sibling (Position : Cursor)
return Cursor;
function Previous_Sibling (Position : Cursor)
return Cursor;
procedure Next_Sibling (Position :
in out Cursor);
procedure Previous_Sibling (Position :
in out Cursor);
{
AI05-0136-1}
{
AI05-0248-1}
procedure Iterate_Children
(Parent :
in Cursor;
Process :
not null access procedure (Position :
in Cursor));
{
AI05-0136-1}
{
AI05-0248-1}
procedure Reverse_Iterate_Children
(Parent :
in Cursor;
Process :
not null access procedure (Position :
in Cursor));
{
AI05-0212-1}
function Iterate_Children (Container :
in Tree; Parent :
in Cursor)
return Tree_Iterator_Interfaces.Reversible_Iterator'Class;
private
... -- not specified by the language
end Ada.Containers.Multiway_Trees;
{
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.
{
AI05-0136-1}
The type Tree is used to represent trees. The type Tree needs finalization
(see
7.6).
{
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.
{
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.
{
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.
{
AI05-0136-1}
Execution of the default implementation of the Input, Output, Read, or
Write attribute of type Cursor raises Program_Error.
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0262-1}
Tree'Write for a Tree object
T writes Node_Count(
T) - 1
elements of the tree to the stream. It also may write additional information
about the tree.
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0262-1}
Tree'Read reads the representation of a tree from the stream, and assigns
to
Item a tree with the same elements and structure as was written
by Tree'Write.
Ramification: Streaming more elements
than the container holds is wrong. For implementation implications of
this rule, see the Implementation Note in
A.18.2.
{
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.]
{
AI05-0136-1}
A subprogram is said to
tamper with cursors
of a tree object
T if:
it inserts or deletes elements of T, that
is, it calls the Clear, Delete_Leaf, Insert_Child, Delete_Children, Delete_Subtree,
or Copy_Subtree procedures with T as a parameter; or
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.
{
AI05-0136-1}
{
AI05-0248-1}
it reorders the elements of
T, that is, it calls the Splice_Subtree
or Splice_Children procedures with
T as a parameter; or
it finalizes T; or
it calls Assign with T as the Target parameter;
or
Ramification: We don't need to explicitly
mention
assignment_statement,
because that finalizes the target object as part of the operation, and
finalization of an object is already defined as tampering with cursors.
it calls the Move procedure with T as a
parameter.
Reason: Swap copies elements rather than
reordering them, so it doesn't tamper with cursors.
{
AI05-0136-1}
A subprogram is said to
tamper with elements
of a tree object
T if:
it tampers with cursors of T; or
it replaces one or more elements of T, that
is, it calls the Replace_Element or Swap procedures with T as
a parameter.
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.
Ramification: Assign is defined in terms
of Clear and Replace_Element, so we don't need to mention it explicitly.
Similarly, we don't need to explicitly mention
assignment_statement,
because that finalizes the target object as part of the operation, and
finalization of an object is already defined as tampering with the element.
{
AI05-0265-1}
{
AI12-0110-1}
When tampering with cursors is
prohibited for a particular tree object
T, Program_Error
is propagated by a call of any language-defined subprogram that is defined
to tamper with the cursors of
T, leaving
T unmodified.
Similarly, when tampering with elements is
prohibited for a particular
tree object
T, Program_Error is propagated by a call of any language-defined
subprogram that is defined to tamper with the elements of
T [(or
tamper with the cursors of
T)], leaving
T unmodified. These
checks are made before any other defined behavior of the body of the
language-defined subprogram.
Proof: Tampering with elements includes
tampering with cursors, so we mention it only from completeness in the
second sentence.
function Has_Element (Position : Cursor) return Boolean;
Returns True if
Position designates an element, and returns False otherwise. [In particular,
Has_Element returns False if the cursor designates a root node or equals
No_Element.]
To be honest: {
AI05-0005-1}
{
AI05-0136-1}
This function might not detect cursors that designate deleted elements;
such cursors are invalid (see below) and the result of calling Has_Element
with an invalid cursor is unspecified (but not erroneous).
function Equal_Subtree (Left_Position : Cursor;
Right_Position: Cursor) return Boolean;
{
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.
Ramification: Left_Position and Right_Position
do not need to be from the same tree.
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.
function "=" (Left, Right : Tree) return Boolean;
{
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.
Implementation Note: Similar considerations
apply here as apply to Equal_Subtree. The actual number of calls performed
is unspecified.
function Node_Count (Container : Tree) return Count_Type;
{
AI05-0136-1}
Node_Count returns the number of nodes in Container.
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)).
function Subtree_Node_Count (Position : Cursor) return Count_Type;
{
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.
function Is_Empty (Container : Tree) return Boolean;
{
AI05-0136-1}
Equivalent to Node_Count (Container) = 1.
Ramification: An empty tree contains
just the root node.
function Depth (Position : Cursor) return Count_Type;
{
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).
Ramification: Depth (Root (Some_Tree))
= 1.
function Is_Root (Position : Cursor) return Boolean;
{
AI05-0136-1}
{
AI05-0248-1}
Is_Root returns True if the Position designates the root node of some
tree; and returns False otherwise.
function Is_Leaf (Position : Cursor) return Boolean;
{
AI05-0136-1}
Is_Leaf returns True if Position designates a node that does not have
any child nodes; and returns False otherwise.
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.
function Root (Container : Tree) return Cursor;
{
AI05-0136-1}
Root returns a cursor that designates the root node of Container.
Ramification: There is always a root
node, even in an empty container, so this function never returns No_Element.
procedure Clear (Container : in out Tree);
Ramification: The root node is not removed;
all trees have a root node.
function Element (Position : Cursor) return Element_Type;
{
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.
Ramification: The root node does not
contain an element, so that value cannot be read or written.
procedure Replace_Element (Container : in out Tree;
Position : in Cursor;
New_Item : in Element_Type);
{
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.
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
{
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 the call on Process.
all. Any exception raised
by Process.
all is propagated.
procedure Update_Element
(Container : in out Tree;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
{
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 the call on Process.
all. Any
exception raised by Process.
all is propagated.
If Element_Type is unconstrained and definite,
then the actual Element parameter of Process.all shall be unconstrained.
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.
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
{
AI05-0212-1}
The types Constant_Reference_Type and Reference_Type need finalization.
The default initialization of an object of type
Constant_Reference_Type or Reference_Type propagates Program_Error.
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.
function Constant_Reference (Container : aliased in Tree;
Position : in Cursor)
return Constant_Reference_Type;
{
AI05-0212-1}
{
AI05-0269-1}
This function (combined with the Constant_Indexing and Implicit_Dereference
aspects) provides a convenient way to gain read access to an individual
element of a tree given a cursor.
{
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.
function Reference (Container : aliased in out Tree;
Position : in Cursor)
return Reference_Type;
{
AI05-0212-1}
{
AI05-0269-1}
This function (combined with the Variable_Indexing and Implicit_Dereference
aspects) provides a convenient way to gain read and write access to an
individual element of a tree given a cursor.
{
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.
procedure Assign (Target : in out Tree; Source : in Tree);
{
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.
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.
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.
function Copy (Source : Tree) return Tree;
{
AI05-0136-1}
Returns a tree with the same structure as Source and whose elements are
initialized from the corresponding elements of Source.
procedure Move (Target : in out Tree;
Source : in out Tree);
{
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.
procedure Delete_Leaf (Container : in out Tree;
Position : in out Cursor);
{
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.
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).
The root node cannot be deleted.
procedure Delete_Subtree (Container : in out Tree;
Position : in out Cursor);
{
AI05-0136-1}
{
AI05-0264-1}
{
AI05-0269-1}
If Position equals No_Element, then Constraint_Error is propagated. If
Position does not designate an element in Container (including if it
designates the root node), then Program_Error is propagated. Otherwise,
Delete_Subtree removes (from Container) the subtree designated by Position
(that is, all descendants of the node designated by Position including
the node itself), and Position is set to No_Element.
Ramification: The root node cannot be
deleted. To delete the entire contents of the tree, call Clear(Container).
procedure Swap (Container : in out Tree;
I, J : in Cursor);
{
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.
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.
The root nodes do not contain element values,
so they cannot be swapped.
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.
function Find (Container : Tree;
Item : Element_Type)
return Cursor;
{
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.
function Find_In_Subtree (Position : Cursor;
Item : Element_Type)
return Cursor;
{
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.
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.
function Ancestor_Find (Position : Cursor;
Item : Element_Type)
return Cursor;
{
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.
Ramification: {
AI05-0248-1}
No_Element is returned if Position is the root node.
function Contains (Container : Tree;
Item : Element_Type) return Boolean;
{
AI05-0136-1}
Equivalent to Find (Container, Item) /= No_Element.
procedure Iterate
(Container : in Tree;
Process : not null access procedure (Position : in Cursor));
{
AI05-0136-1}
{
AI05-0265-1}
{
AI12-0069-1}
Iterate calls Process.
all with a cursor that designates each element
in Container, starting from the root node and proceeding in a depth-first
order. Tampering with the cursors of Container is prohibited during the
execution of a call on Process.
all. Any exception raised by Process.
all
is propagated.
Ramification: Process is not called with
the root node, which does not have an associated element.
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.
See Iterate for vectors (
A.18.2)
for a suggested implementation of the check.
procedure Iterate_Subtree
(Position : in Cursor;
Process : not null access procedure (Position : in Cursor));
{
AI05-0136-1}
{
AI05-0265-1}
{
AI12-0069-1}
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Iterate_Subtree calls Process.
all with a cursor that designates
each element in the subtree rooted by the node designated by Position,
starting from the node designated by Position and proceeding in a depth-first
order. Tampering with the cursors of the tree that contains the element
designated by Position is prohibited during the execution of a call on
Process.
all. Any exception raised by Process.
all is propagated.
Ramification: Position can be passed
a cursor designating the root node; in that case, Process is not called
with the root node, which does not have an associated element.
function Iterate (Container : in Tree)
return Tree_Iterator_Interfaces.Forward_Iterator'Class;
Discussion:
Exits are allowed from the loops created using the iterator objects.
In particular, to stop the iteration at a particular cursor, just add
exit when Cur = Stop;
in the body of
the loop (assuming that Cur is the loop parameter and Stop
is the cursor that you want to stop at).
function Iterate_Subtree (Position : in Cursor)
return Tree_Iterator_Interfaces.Forward_Iterator'Class;
{
AI05-0212-1}
{
AI05-0265-1}
{
AI05-0269-1}
{
AI12-0069-1}
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Iterate_Subtree returns an iterator object (see
5.5.1)
that will generate a value for a loop parameter (see
5.5.2)
designating each element in the subtree rooted by the node designated
by Position, starting from 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.
function Child_Count (Parent : Cursor) return Count_Type;
{
AI05-0136-1}
Child_Count returns the number of child nodes of the node designated
by Parent.
function Child_Depth (Parent, Child : Cursor) return Count_Type;
{
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.
Ramification: Program_Error is propagated
if Parent and Child are nodes in different containers.
Child_Depth (Root (Some_Tree), Child) + 1 =
Depth (Child) as the root is not counted.
procedure Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
{
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.
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);
{
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.
procedure Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
{
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.
procedure Prepend_Child (Container : in out Tree;
Parent : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
{
AI05-0136-1}
Equivalent to Insert_Child (Container, Parent, First_Child (Container,
Parent), New_Item, Count).
procedure Append_Child (Container : in out Tree;
Parent : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
procedure Delete_Children (Container : in out Tree;
Parent : in Cursor);
{
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 descendants
of Parent other than Parent itself.
Discussion: This routine deletes all
of the child subtrees of Parent at once. Use Delete_Subtree to delete
an individual subtree.
procedure Copy_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Cursor);
{
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.
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.
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.
procedure Splice_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Position : in out Cursor);
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0262-1}
{
AI05-0269-1}
If Parent equals No_Element, then Constraint_Error is propagated. If
Parent does not designate a node in Target, then Program_Error is propagated.
If Before is not equal to No_Element, and does not designate a node in
Target, then Program_Error is propagated. If Before is not equal to No_Element,
and Parent does not designate the parent node of the node designated
by Before, then Constraint_Error is propagated. If Position equals No_Element,
Constraint_Error is propagated. If Position does not designate a node
in Source or designates a root node, then Program_Error is propagated.
If Source denotes the same object as Target, then: if Position equals
Before there is no effect; if Position designates an ancestor of Parent
(including Parent itself), Constraint_Error is propagated; otherwise,
the subtree rooted by the element designated by Position is moved to
be a child of Parent. If Parent already has child nodes, then the moved
nodes are inserted prior to the node designated by Before, or, if Before
equals No_Element, the moved nodes are inserted after the last existing
child node of Parent. In each of these cases, Position and the count
of Target are unchanged, and the parent of the element designated by
Position is set to Parent.
Reason: We can't allow moving the subtree
of Position to a proper descendant node of the subtree, as the descendant
node will be part of the subtree being moved. The result would be a circularly
linked tree, or one with inaccessible nodes. Thus we have to check Position
against Parent, even though such a check is O(Depth(Source)).
{
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.
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.
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.
For this reason there is no operation to splice
an entire tree, as that would necessarily involve splicing a root node.
procedure Splice_Subtree (Container: in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : in Cursor);
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0262-1}
{
AI05-0269-1}
If Parent equals No_Element, then Constraint_Error is propagated. If
Parent does not designate a node in Container, then Program_Error is
propagated. If Before is not equal to No_Element, and does not designate
a node in Container, then Program_Error is propagated. If Before is not
equal to No_Element, and Parent does not designate the parent node of
the node designated by Before, then Constraint_Error is propagated. If
Position equals No_Element, Constraint_Error is propagated. If Position
does not designate a node in Container or designates a root node, then
Program_Error is propagated. If Position equals Before, there is no effect.
If Position designates an ancestor of Parent (including Parent itself),
Constraint_Error is propagated. Otherwise, the subtree rooted by the
element designated by Position is moved to be a child of Parent. If Parent
already has child nodes, then the moved nodes are inserted prior to the
node designated by Before, or, if Before equals No_Element, the moved
nodes are inserted after the last existing child node of Parent. The
parent of the element designated by Position is set to Parent.
Reason: We can't allow moving the subtree
of Position to a proper descendant node of the subtree, as the descendant
node will be part of the subtree being moved.
procedure Splice_Children (Target : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Source_Parent : in Cursor);
{
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.
If Source denotes
the same object as Target, then:
if Target_Parent equals Source_Parent
there is no effect; else
{
AI05-0136-1}
{
AI05-0269-1}
if Source_Parent is an ancestor of Target_Parent other than Target_Parent
itself, then Constraint_Error is propagated; else
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0269-1}
the child elements (and the further descendants) of Source_Parent are
moved to be child elements of Target_Parent. If Target_Parent already
has child elements, then the moved elements are inserted prior to the
node designated by Before, or, if Before equals No_Element, the moved
elements are inserted after the last existing child node of Target_Parent.
The parent of each moved child element is set to Target_Parent.
Reason: We can't allow moving the children
of Source_Parent to a proper descendant node, as the descendant node
will be part of one of the subtrees being moved.
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0269-1}
Otherwise (if Source does not denote the same object as Target), the
child elements (and the further descendants) of Source_Parent are removed
from Source and moved to Target. The child elements are inserted as children
of Target_Parent. If Target_Parent already has child elements, then the
moved elements are inserted prior to the node designated by Before, or,
if Before equals No_Element, the moved elements are inserted after the
last existing child node of Target_Parent. In each of these cases, the
overall count of Target is incremented by Subtree_Node_Count (Source_Parent)-1,
and the overall count of Source is decremented by Subtree_Node_Count
(Source_Parent)-1.
Ramification: The node designated by
Source_Parent is not moved, thus we never need to update Source_Parent.
Move (Target, Source) could be written Splice_Children
(Target, Target.Root, No_Element, Source, Source.Root);
procedure Splice_Children (Container : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source_Parent : in Cursor);
{
AI05-0136-1}
{
AI05-0248-1}
{
AI05-0262-1}
{
AI05-0264-1}
{
AI05-0269-1}
If Target_Parent equals No_Element, then Constraint_Error is propagated.
If Target_Parent does not designate a node in Container, then Program_Error
is propagated. If Before is not equal to No_Element, and does not designate
an element in Container, then Program_Error is propagated. If Source_Parent
equals No_Element, then Constraint_Error is propagated. If Source_Parent
does not designate a node in Container, then Program_Error is propagated.
If Before is not equal to No_Element, and Target_Parent does not designate
the parent node of the node designated by Before, then Constraint_Error
is propagated. If Target_Parent equals Source_Parent there is no effect.
If Source_Parent is an ancestor of Target_Parent other than Target_Parent
itself, then Constraint_Error is propagated. Otherwise, the child elements
(and the further descendants) of Source_Parent are moved to be child
elements of Target_Parent. If Target_Parent already has child elements,
then the moved elements are inserted prior to the node designated by
Before, or, if Before equals No_Element, the moved elements are inserted
after the last existing child node of Target_Parent. The parent of each
moved child element is set to Target_Parent.
function Parent (Position : Cursor) return Cursor;
{
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.
function First_Child (Parent : Cursor) return Cursor;
{
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.
function First_Child_Element (Parent : Cursor) return Element_Type;
{
AI05-0136-1}
Equivalent to Element (First_Child (Parent)).
function Last_Child (Parent : Cursor) return Cursor;
{
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.
function Last_Child_Element (Parent : Cursor) return Element_Type;
{
AI05-0136-1}
Equivalent to Element (Last_Child (Parent)).
function Next_Sibling (Position : Cursor) return Cursor;
{
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.
function Previous_Sibling (Position : Cursor) return Cursor;
{
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.
procedure Next_Sibling (Position : in out Cursor);
{
AI05-0136-1}
Equivalent to Position := Next_Sibling (Position);
procedure Previous_Sibling (Position : in out Cursor);
{
AI05-0136-1}
Equivalent to Position := Previous_Sibling (Position);
procedure Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor));
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.
{
AI05-0265-1}
Tampering with the cursors of the tree containing Parent is prohibited
during the execution of a call on Process.
all. Any exception raised
by Process.
all is propagated.
procedure Reverse_Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor));
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.
{
AI05-0265-1}
Tampering with the cursors of the tree containing Parent is prohibited
during the execution of a call on Process.
all. Any exception raised
by Process.
all is propagated.
function Iterate_Children (Container : in Tree; Parent : in Cursor)
return Tree_Iterator_Interfaces.Reversible_Iterator'Class;
{
AI05-0212-1}
{
AI05-0265-1}
Iterate_Children returns a reversible iterator object (see
5.5.1)
that will generate a value for a loop parameter (see
5.5.2)
designating each child node of Parent. 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
{
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.
{
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
{
AI05-0136-1}
A Cursor value is
invalid if any of the following have occurred
since it was created:
The tree that contains the element it designates
has been finalized;
The tree that contains the element it designates
has been used as the Source or Target of a call to Move;
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;
The element it designates has been removed from
the tree that previously contained the element.
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.
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.
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.
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.
{
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.
Reason: Each object of Reference_Type
and Constant_Reference_Type probably contains some reference to the originating
container. If that container is prematurely finalized (which is only
possible via Unchecked_Deallocation, as accessibility checks prevent
passing a container to Reference that will not live as long as the result),
the finalization of the object of Reference_Type will try to access a
nonexistent object. This is a normal case of a dangling pointer created
by Unchecked_Deallocation; we have to explicitly mention it here as the
pointer in question is not visible in the specification of the type.
(This is the same reason we have to say this for invalid cursors.)
Implementation Requirements
{
AI05-0136-1}
No storage associated with a multiway tree object shall be lost upon
assignment or scope exit.
{
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.
Implementation Note: {
AI05-0298-1}
An assignment of a Tree is a “deep” copy; that is the elements
are copied as well the data structures. We say “effect of”
in order to allow the implementation to avoid copying elements immediately
if it wishes. For instance, an implementation that avoided copying until
one of the containers is modified would be allowed. (Note that this implementation
would require care, see
A.18.2 for more.)
Implementation Advice
{
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).
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).
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.
{
AI05-0136-1}
Move should not copy elements, and should minimize copying of internal
data structures.
Implementation Advice: Containers.Multiway_Trees.Move
should not copy elements, and should minimize copying of internal data
structures.
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.
{
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.
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.
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
Wording Changes from Ada 2012
{
AI12-0069-1}
Corrigendum: Fixed the function Iterate so it is clear that the
root node is never visited.
{
AI12-0078-1}
Corrigendum: The definition of
node is clarified so that
it it doesn't appear to say all nodes have an element.
{
AI12-0110-1}
Corrigendum: Clarified that tampering checks precede all other
checks made by a subprogram (but come after those associated with the
call).
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
