Mutliway Trees#
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.
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.
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.
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.
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).
with Ada.Iterator_Interfaces;
generic
type Element_Type is private;
with function "="(Left, Right: Element_Type) return Boolean is <>;
package Ada.Containers.Multiway_Trees
with Preelaborate, Remote_Types, Nonblocking, Global => in out synchronized is
type Tree is tagged private;
type Cursor is private;
Empty_Tree: constant Tree;
No_Element: constant Cursor;
function Equal_Element(Left, Right: Element_Type) return Boolean renames "=";
function Has_Element( Position: Cursor) return Boolean;
function Has_Element(Container: Tree; Position: Cursor) return Boolean;
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 Tampering_With_Cursors_Prohibited (Container: Tree) return Boolean;
function Tampering_With_Elements_Prohibited(Container: Tree) return Boolean;
function Empty return Tree is
(Empty_Tree);
procedure Clear(Container: in out Tree);
function Root (Container: Tree) return Cursor;
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 Subtree_Node_Count(Container: Tree; Position: Cursor) return Count_Type;
function Depth( Position: Cursor) return Count_Type;
function Depth(Container: Tree; Position: Cursor) return Count_Type;
function Is_Root( Position: Cursor) return Boolean;
function Is_Root(Container: Tree; Position: Cursor) return Boolean;
function Is_Leaf( Position: Cursor) return Boolean;
function Is_Leaf(Container: Tree; Position: Cursor) return Boolean;
function Is_Ancestor_Of(Container: Tree; Parent: Cursor; Position: Cursor) return Boolean;
function Meaningful_For(Container: Tree; Position: Cursor) return Boolean is
(Position = No_Element or else
Is_Root(Container, Position) or else
Has_Element(Container, Position));
function Element( Position: Cursor) return Element_Type;
function Element(Container: Tree; Position: Cursor) return Element_Type;
procedure Replace_Element(Container: in out Tree; Position: Cursor; New_item: Element_Type);
procedure Query_Element(Position: Cursor; Process: not null access procedure(Element: Element_Type));
procedure Query_Element(Container: Tree;
Position : Cursor;
Process : not null access procedure(Element: Element_Type));
procedure Update_Element(Container: in out Tree;
Position : Cursor;
Process : not null access procedure(Element: in out Element_Type));
type Constant_Reference_Type(Element: not null access constant Element_Type) is private;
type Reference_Type (Element: not null access Element_Type) is private;
function Constant_Reference(Container: aliased Tree; Position: Cursor) return Constant_Reference_Type;
function Reference (Container: aliased in out Tree; Position: Cursor) return Reference_Type;
function Copy(Source: Tree) return Tree;
procedure Assign(Target: in out Tree; Source: Tree);
procedure Move (Target: in out Tree; Source: in out Tree);
procedure Swap(Container: in out Tree; I, J: Cursor);
procedure Delete_Leaf (Container: in out Tree; Position: in out Cursor);
procedure Delete_Subtree(Container: in out Tree; Position: in out Cursor);
function Find (Container: Tree; Item: Element_Type) return Cursor;
function Find_In_Subtree(Container: Tree; Position: Cursor; Item: Element_Type) return Cursor;
function Find_In_Subtree( Position: Cursor; Item: Element_Type) return Cursor;
function Ancestor_Find( Position: Cursor; Item: Element_Type) return Cursor;
function Ancestor_Find(Container: Tree; Position: Cursor; Item: Element_Type) return Cursor;
function Contains (Container: Tree; Item: Element_Type) return Boolean;
procedure Iterate_Subtree(Position: Cursor; Process: not null access procedure(Position: Cursor));
procedure Iterate (Container: Tree; Process: not null access procedure(Position: Cursor));
procedure Iterate_Subtree(Container: Tree;
Position : Cursor;
Process : not null access procedure(Position: Cursor));
function Iterate (Container: Tree) return Tree_Iterator_Interfaces.Parallel_Iterator'Class;
function Iterate_Subtree(Container: Tree; Position: Cursor) return Tree_Iterator_Interfaces.Parallel_Iterator'Class;
function Iterate_Subtree(Position: Cursor) return Tree_Iterator_Interfaces.Parallel_Iterator'Class;
function Child_Count( Parent: Cursor) return Count_Type;
function Child_Count(Container: Tree; Parent: Cursor) return Count_Type;
function Child_Depth( Parent, Child: Cursor) return Count_Type;
function Child_Depth(Container: Tree; Parent, Child: Cursor) return Count_Type;
procedure Insert_Child(Container: in out Tree;
Parent : Cursor;
Before : Cursor;
New_Item : Element_Type;
Count : Count_Type := 1);
procedure Insert_Child(Container: in out Tree;
Parent : Cursor;
Before : Cursor;
New_Item : Element_Type;
Position : out Cursor;
Count : Count_Type := 1);
procedure Insert_Child(Container: in out Tree;
Parent : Cursor;
Before : Cursor;
Position : out Cursor;
Count : Count_Type := 1);
procedure Prepend_Child(Container: in out Tree;
Parent : Cursor;
New_Item : Element_Type;
Count : Count_Type := 1);
procedure Append_Child(Container: in out Tree;
Parent : Cursor;
New_Item : Element_Type;
Count : Count_Type := 1);
procedure Delete_Children(Container: in out Tree; Parent: Cursor);
procedure Copy_Subtree (Target: in out Tree; Parent: Cursor; Before: Cursor; Source: Cursor);
procedure Copy_Local_Subtree(Target: in out Tree; Parent: Cursor; Before: Cursor; Source: Cursor);
procedure Copy_Subtree(Target : in out Tree;
Parent : Cursor;
Before : Cursor;
Source : Tree;
Subtree: Cursor);
procedure Splice_Subtree(Target : in out Tree;
Parent : Cursor;
Before : Cursor;
Source : in out Tree;
Position: in out Cursor);
procedure Splice_Subtree(Container: in out Tree; Parent: Cursor; Before: Cursor; Position: Cursor);
procedure Splice_Children(Target : in out Tree;
Target_Parent: Cursor;
Before : Cursor;
Source : in out Tree;
Source_Parent: Cursor);
procedure Splice_Children(Container : in out Tree;
Target_Parent: Cursor;
Before : Cursor;
Source_Parent: Cursor);
function Parent( Position: Cursor) return Cursor;
function Parent(Container: Tree; Position: Cursor) return Cursor;
function First_Child( Parent: Cursor) return Cursor;
function First_Child(Container: Tree; Parent: Cursor) return Cursor;
function First_Child_Element( Parent: Cursor) return Element_Type;
function First_Child_Element(Container: Tree; Parent: Cursor) return Element_Type;
function Last_Child( Parent: Cursor) return Cursor;
function Last_Child(Container: Tree; Parent: Cursor) return Cursor;
function Last_Child_Element( Parent: Cursor) return Element_Type;
function Last_Child_Element(Container: Tree; Parent: Cursor) return Element_Type;
function Next_Sibling( Position: Cursor) return Cursor;
function Next_Sibling(Container: Tree; Position: Cursor) return Cursor;
procedure Next_Sibling( Position: in out Cursor);
procedure Next_Sibling(Container: Tree; Position: in out Cursor);
function Previous_Sibling( Position: Cursor) return Cursor;
function Previous_Sibling(Container: Tree; Position: Cursor) return Cursor;
procedure Previous_Sibling( Position: in out Cursor);
procedure Previous_Sibling(Container: Tree; Position: in out Cursor);
procedure Iterate_Children( Parent: Cursor; Process: not null access procedure(Position: Cursor));
procedure Iterate_Children(Container: Tree; Parent: Cursor; Process: not null access procedure(Position: Cursor));
procedure Reverse_Iterate_Children(Parent: Cursor; Process: not null access procedure(Position: Cursor));
procedure Reverse_Iterate_Children(Container: Tree;
Parent : Cursor;
Process : not null access procedure(Position: Cursor));
function Iterate_Children(Container: Tree;
Parent : Cursor) return Tree_Iterator_Interfaces.Parallel_Reversible_Iterator'Class;
package Stable is
type Tree(Base: not null access Multiway_Trees.Tree) is tagged limited private;
type Cursor is private;
Empty_Tree: constant Tree;
No_Element: constant Cursor;
function Has_Element(Position: Cursor) return Boolean;
package Tree_Iterator_Interfaces is new Ada.Iterator_Interfaces(Cursor, Has_Element);
procedure Assign(Target: in out Multiway_Trees.Tree; Source: Tree);
function Copy(Source: Multiway_Trees.Tree) return Tree;
type Constant_Reference_Type(Element: not null access constant Element_Type) is private;
type Reference_Type (Element: not null access Element_Type) is private;
end Stable;
end Ada.Containers.Multiway_Trees;
Bounded (Run-Time) Errors
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.
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
A `#!Ada 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
SourceorTargetof a call toMove. - The tree that contains the element it designates has been used as the
Targetof a call toAssignor the target of an assignment_statement. - The element it designates has been removed from the tree that previously contained the element.
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.
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.
Bounded Multiway Trees#
The language-defined generic package Containers.Bounded_Multiway_Trees provides a private type Tree and
a set of operations. It provides the same operations as the package Containers.Multiway_Trees (see A.18.10),
with the difference that the maximum storage is bounded.
type Tree(Capacity: Count_Type) is tagged private;
Bounded (Run-Time) Errors
It is a bounded error to assign from a bounded tree object while tampering with elements [or cursors] of that object
is prohibited. Either Program_Error is raised by the assignment, execution proceeds with the target object
prohibiting tampering with elements [or cursors], or execution proceeds normally.
Erroneous Execution
When a bounded tree object T is finalized, if tampering with cursors is prohibited for T other than
due to an assignment from another tree, then execution is erroneous.
Indefinite Multiway Trees#
The language-defined generic package Containers.Indefinite_Multiway_Trees provides a multiway tree with the same
operations as the package Containers.Multiway_Trees (see A.18.10), with the difference that the generic
formal Element_Type is indefinite.
procedure Insert_Child(Container: in out Tree;
Parent : Cursor;
Before : Cursor;
Position : out Cursor;
Count : Count_Type := 1);