A.18.10 The Generic Package Containers.Multiway_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).
Static Semantics
The generic library
package Containers.Multiway_Trees has the following declaration:
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
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Iterator_View => Stable.Tree,
Stable_Properties => (Node_Count,
Tampering_With_Cursors_Prohibited,
Tampering_With_Elements_Prohibited),
Default_Initial_Condition =>
Node_Count (Tree) = 1
and then
(
not Tampering_With_Cursors_Prohibited (Tree))
and then
(
not Tampering_With_Elements_Prohibited (Tree)),
Preelaborable_Initialization;
type Cursor
is private
with Preelaborable_Initialization;
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
with Nonblocking, Global =>
in all, Use_Formal =>
null;
function Has_Element (Container : Tree; Position : Cursor)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
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
with Nonblocking, Global =>
null, Use_Formal =>
null;
function Tampering_With_Elements_Prohibited
(Container : Tree)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
function Empty
return Tree
is (Empty_Tree)
with Post =>
not Tampering_With_Elements_Prohibited (Empty'Result)
and then
not Tampering_With_Cursors_Prohibited (Empty'Result)
and then
Node_Count (Empty'Result) = 1;
function Is_Empty (Container : Tree)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null,
Post => Is_Empty'Result = (Node_Count (Container) = 1);
function Node_Count (Container : Tree)
return Count_Type
with Nonblocking, Global =>
null, Use_Formal =>
null;
function Subtree_Node_Count (Position : Cursor)
return Count_Type
with Nonblocking, Global =>
in all, Use_Formal =>
null;
function Subtree_Node_Count (Container : Tree; Position : Cursor)
return Count_Type
with Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Nonblocking, Global =>
null, Use_Formal =>
null;
function Depth (Position : Cursor)
return Count_Type
with Nonblocking, Global =>
in all, Use_Formal =>
null;
function Depth (Container : Tree; Position : Cursor)
return Count_Type
with Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Nonblocking, Global =>
null, Use_Formal =>
null;
function Is_Root (Position : Cursor)
return Boolean
with Nonblocking, Global =>
in all, Use_Formal =>
null;
function Is_Root (Container : Tree; Position : Cursor)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
function Is_Leaf (Position : Cursor)
return Boolean
with Nonblocking, Global =>
in all, Use_Formal =>
null;
function Is_Leaf (Container : Tree; Position : Cursor)
return Boolean
with Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Nonblocking, Global =>
null, Use_Formal =>
null;
function Is_Ancestor_Of (Container : Tree;
Parent : Cursor;
Position : Cursor)
return Boolean
with Pre => (Meaningful_For (Container, Position)
or else raise Program_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Nonblocking, Global =>
null, Use_Formal =>
null;
function Root (Container : Tree)
return Cursor
with Nonblocking, Global =>
null, Use_Formal =>
null,
Post => Root'Result /= No_Element
and then
not Has_Element (Container, Root'Result);
function Meaningful_For (Container : Tree; Position : Cursor)
return Boolean
is
(Position = No_Element
or else
Is_Root (Container, Position)
or else
Has_Element (Container, Position))
with Nonblocking, Global =>
null, Use_Formal =>
null;
procedure Clear (Container :
in out Tree)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Node_Count (Container) = 1;
function Element (Position : Cursor)
return Element_Type
with Pre => (Position /= No_Element
or else
raise Constraint_Error)
and then
(Has_Element (Position)
or else raise Program_Error),
Nonblocking, Global =>
in all, Use_Formal => Element_Type;
function Element (Container : Tree;
Position : Cursor)
return Element_Type
with Pre => (Position /= No_Element
or else
raise Constraint_Error)
and then
(Has_Element (Container, Position)
or else raise Program_Error),
Nonblocking, Global =>
null, Use_Formal => Element_Type;
procedure Replace_Element (Container :
in out Tree;
Position :
in Cursor;
New_item :
in Element_Type)
with Pre => (
not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error)
and then
(Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Container, Position)
or else raise Program_Error);
procedure Query_Element
(Position :
in Cursor;
Process :
not null access procedure (Element :
in Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Position)
or else raise Program_Error),
Global =>
in all;
procedure Query_Element
(Container :
in Tree;
Position :
in Cursor;
Process :
not null access procedure (Element :
in Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Container, Position)
or else raise Program_Error);
procedure Update_Element
(Container :
in out Tree;
Position :
in Cursor;
Process :
not null access procedure
(Element :
in out Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Container, Position)
or else raise Program_Error);
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
type Reference_Type (Element :
not null access Element_Type)
is private
with Implicit_Dereference => Element,
Nonblocking, Global =>
in out synchronized,
Default_Initial_Condition => (
raise Program_Error);
function Constant_Reference (Container :
aliased in Tree;
Position :
in Cursor)
return Constant_Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global =>
null, Use_Formal =>
null;
function Reference (Container :
aliased in out Tree;
Position :
in Cursor)
return Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global =>
null, Use_Formal =>
null;
procedure Assign (Target :
in out Tree; Source :
in Tree)
with Pre =>
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Node_Count (Source) = Node_Count (Target);
function Copy (Source : Tree)
return Tree
with Post =>
Node_Count (Copy'Result) = Node_Count (Source)
and then
not Tampering_With_Elements_Prohibited (Copy'Result)
and then
not Tampering_With_Cursors_Prohibited (Copy'Result);
procedure Move (Target :
in out Tree;
Source :
in out Tree)
with Pre => (
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error)
and then
(
not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error),
Post => (
if not Target'Has_Same_Storage (Source)
then
Node_Count (Target) = Node_Count (Source'Old)
and then
Node_Count (Source) = 1);
procedure Delete_Leaf (Container :
in out Tree;
Position :
in out Cursor)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Container, Position)
or else raise Program_Error)
and then
(Is_Leaf (Container, Position)
or else raise Constraint_Error),
Post =>
Node_Count (Container)'Old = Node_Count (Container)+1
and then
Position = No_Element;
procedure Delete_Subtree (Container :
in out Tree;
Position :
in out Cursor)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Node_Count (Container)'Old = Node_Count (Container) +
Subtree_Node_Count (Container, Position)'Old
and then
Position = No_Element;
procedure Swap (Container :
in out Tree;
I, J :
in Cursor)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(I /= No_Element
or else Constraint_Error)
and then
(J /= No_Element
or else Constraint_Error)
and then
(Has_Element (Container, I)
or else raise Program_Error)
and then
(Has_Element (Container, J)
or else raise Program_Error);
function Find (Container : Tree;
Item : Element_Type)
return Cursor
with Post => (
if Find'Result /= No_Element
then Has_Element (Container, Find'Result));
function Find_In_Subtree (Position : Cursor;
Item : Element_Type)
return Cursor
with Pre => Position /= No_Element
or else raise Constraint_Error,
Post => (
if Find_In_Subtree'Result = No_Element
then Has_Element (Find_In_Subtree'Result)),
Global =>
in all;
function Find_In_Subtree (Container : Tree;
Position : Cursor;
Item : Element_Type)
return Cursor
with Pre => (Position /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Position)
or else raise Program_Error),
Post => (
if Find_In_Subtree'Result /= No_Element
then Has_Element (Container, Find_In_Subtree'Result));
function Ancestor_Find (Position : Cursor;
Item : Element_Type)
return Cursor
with Pre => Position /= No_Element
or else raise Constraint_Error,
Post => (
if Ancestor_Find'Result = No_Element
then Has_Element (Ancestor_Find'Result)),
Global =>
in all;
function Ancestor_Find (Container : Tree;
Position : Cursor;
Item : Element_Type)
return Cursor
with Pre => (Position /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Position)
or else raise Program_Error),
Post => (
if Ancestor_Find'Result = No_Element
then Has_Element (Container, Ancestor_Find'Result));
function Contains (Container : Tree;
Item : Element_Type)
return Boolean;
procedure Iterate
(Container :
in Tree;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit;
procedure Iterate_Subtree
(Position :
in Cursor;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit,
Pre => Position /= No_Element
or else raise Constraint_Error,
Global =>
in all;
procedure Iterate_Subtree
(Container :
in Tree;
Position :
in Cursor;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit,
Pre => (Position /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Position)
or else raise Program_Error);
function Iterate (Container :
in Tree)
return Tree_Iterator_Interfaces.Parallel_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
function Iterate_Subtree (Position :
in Cursor)
return Tree_Iterator_Interfaces.Parallel_Iterator'Class
with Pre => Position /= No_Element
or else raise Constraint_Error,
Global =>
in all;
function Iterate_Subtree (Container :
in Tree; Position :
in Cursor)
return Tree_Iterator_Interfaces.Parallel_Iterator'Class
with Pre => (Position /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
function Child_Count (Parent : Cursor)
return Count_Type
with Post => (
if Parent = No_Element
then Child_Count'Result = 0),
with Nonblocking, Global =>
in all, Use_Formal =>
null;
function Child_Count (Container : Tree; Parent : Cursor)
return Count_Type
with Pre => Meaningful_For (Container, Parent)
or else raise Program_Error,
Post => (
if Parent = No_Element
then Child_Count'Result = 0),
Nonblocking, Global =>
null, Use_Formal =>
null;
function Child_Depth (Parent, Child : Cursor)
return Count_Type
with Pre => (Parent = No_Element
and then Child = No_Element)
or else raise Constraint_Error,
with Nonblocking, Global =>
in all, Use_Formal =>
null;
function Child_Depth (Container : Tree; Parent, Child : Cursor)
return Count_Type
with Pre => ((Parent = No_Element
and then Child = No_Element)
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error)
and then
(Meaningful_For (Container, Child)
or else raise Program_Error),
Nonblocking, Global =>
null, Use_Formal =>
null;
procedure Insert_Child (Container :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
New_Item :
in Element_Type;
Count :
in Count_Type := 1)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error)
and then
(Meaningful_For (Container, Before)
or else raise Program_Error)
and then
(Before = No_Element
or else
Container.Parent (Before) = Parent
or else raise Constraint_Error),
Post => Node_Count (Container) =
Node_Count (Container)'Old + Count;
procedure Insert_Child (Container :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
New_Item :
in Element_Type;
Position :
out Cursor;
Count :
in Count_Type := 1)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error)
and then
(Meaningful_For (Container, Before)
or else raise Program_Error)
and then
(Before = No_Element
or else
Container.Parent (Before) = Parent
or else raise Constraint_Error),
Post => (Node_Count (Container) =
Node_Count (Container)'Old + Count)
and then
Has_Element (Container, Position);
procedure Insert_Child (Container :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
Position :
out Cursor;
Count :
in Count_Type := 1)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error)
and then
(Meaningful_For (Container, Before)
or else raise Program_Error)
and then
(Before = No_Element
or else
Container.Parent (Before) = Parent
or else raise Constraint_Error),
Post => (Node_Count (Container) =
Node_Count (Container)'Old + Count)
and then
Has_Element (Container, Position);
procedure Prepend_Child (Container :
in out Tree;
Parent :
in Cursor;
New_Item :
in Element_Type;
Count :
in Count_Type := 1)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Node_Count (Container) =
Node_Count (Container)'Old + Count;
procedure Append_Child (Container :
in out Tree;
Parent :
in Cursor;
New_Item :
in Element_Type;
Count :
in Count_Type := 1)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Node_Count (Container) =
Node_Count (Container)'Old + Count;
procedure Delete_Children (Container :
in out Tree;
Parent :
in Cursor)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => (Node_Count (Container) = Node_Count (Container)'Old -
Child_Count (Container, Parent)'Old)
and then
Child_Count (Container, Parent) = 0;
procedure Copy_Subtree (Target :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
Source :
in Cursor)
with Pre => (
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error)
and then
(Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Target, Parent)
or else raise Program_Error)
and then
(Meaningful_For (Target, Before)
or else raise Program_Error)
and then
(Before = No_Element
or else
Target.Parent (Before) = Parent
or else raise Constraint_Error)
and then
(
not Is_Root (Source)
or else raise Constraint_Error),
Post => Node_Count (Target) =
Node_Count (Target)'Old + Subtree_Node_Count (Source),
Global =>
in all;
procedure Copy_Local_Subtree (Target :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
Source :
in Cursor)
with Pre => (
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error)
and then
(Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Target, Parent)
or else raise Program_Error)
and then
(Meaningful_For (Target, Before)
or else raise Program_Error)
and then
(Before = No_Element
or else
Target.Parent (Before) = Parent
or else raise Constraint_Error)
and then
(Meaningful_For (Target, Source)
or else raise Program_Error)
and then
(
not Is_Root (Source)
or else raise Constraint_Error),
Post => Node_Count (Target) = Node_Count (Target)'Old +
Subtree_Node_Count (Target, Source);
procedure Copy_Subtree (Target :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
Source :
in Tree;
Subtree :
in Cursor)
with Pre => (
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error)
and then
(Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Target, Parent)
or else raise Program_Error)
and then
(Meaningful_For (Target, Before)
or else raise Program_Error)
and then
(Before = No_Element
or else
Target.Parent (Before) = Parent
or else raise Constraint_Error)
and then
(Meaningful_For (Source, Subtree)
or else raise Program_Error)
and then
(
not Is_Root (Source, Subtree)
or else raise Constraint_Error),
Post => Node_Count (Target) = Node_Count (Target)'Old +
Subtree_Node_Count (Source, Subtree);
procedure Splice_Subtree (Target :
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
Source :
in out Tree;
Position :
in out Cursor)
with Pre => (
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error)
and then
(
not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error)
and then
(Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Target, Parent)
or else raise Program_Error)
and then
(Meaningful_For (Target, Before)
or else raise Program_Error)
and then
(Before = No_Element
or else
Target.Parent (Before) /= Parent
or else raise Constraint_Error)
and then
(Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Source, Position)
or else raise Program_Error)
and then
(Target'Has_Same_Storage (Source)
or else
Position = Before
or else
Is_Ancestor_Of (Target, Position, Parent)
or else raise Constraint_Error),
Post => (
declare
Org_Sub_Count
renames
Subtree_Node_Count (Source, Position)'Old;
Org_Target_Count
renames Node_Count (Target)'Old;
begin
(
if not Target'Has_Same_Storage (Source)
then
Node_Count (Target) = Org_Target_Count +
Org_Sub_Count
and then
Node_Count (Source) = Node_Count (Source)'Old -
Org_Sub_Count
and then
Has_Element (Target, Position)
else
Target.Parent (Position) = Parent
and then
Node_Count (Target) = Org_Target_Count));
procedure Splice_Subtree (Container:
in out Tree;
Parent :
in Cursor;
Before :
in Cursor;
Position :
in Cursor)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error)
and then
(Meaningful_For (Container, Before)
or else raise Program_Error)
and then
(Before = No_Element
or else
Container.Parent (Before) /= Parent
or else raise Constraint_Error)
and then
(Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Container, Position)
or else raise Program_Error)
and then
(Position = Before
or else
Is_Ancestor_Of (Container, Position, Parent)
or else raise Constraint_Error),
Post => (Node_Count (Container) =
Node_Count (Container)'Old
and then
Container.Parent (Position) = Parent);
procedure Splice_Children (Target :
in out Tree;
Target_Parent :
in Cursor;
Before :
in Cursor;
Source :
in out Tree;
Source_Parent :
in Cursor)
with Pre => (
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error)
and then
(
not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error)
and then
(Target_Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Target, Target_Parent)
or else raise Program_Error)
and then
(Meaningful_For (Target, Before)
or else raise Program_Error)
and then
(Source_Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Source, Source_Parent)
or else raise Program_Error)
and then
(Before = No_Element
or else
Parent (Target, Before) /= Target_Parent
or else raise Constraint_Error)
and then
(Target'Has_Same_Storage (Source)
or else
Target_Parent = Source_Parent
or else
Is_Ancestor_Of (Target, Source_Parent, Target_Parent)
or else raise Constraint_Error),
Post => (
declare
Org_Child_Count
renames
Child_Count (Source, Source_Parent)'Old;
Org_Target_Count
renames Node_Count (Target)'Old;
begin
(
if not Target'Has_Same_Storage (Source)
then
Node_Count (Target) = Org_Target_Count +
Org_Child_Count
and then
Node_Count (Source) = Node_Count (Source)'Old -
Org_Child_Count
else
Node_Count (Target) = Org_Target_Count));
procedure Splice_Children (Container :
in out Tree;
Target_Parent :
in Cursor;
Before :
in Cursor;
Source_Parent :
in Cursor)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Target_Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Target_Parent)
or else raise Program_Error)
and then
(Meaningful_For (Container, Before)
or else raise Program_Error)
and then
(Source_Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Source_Parent)
or else raise Program_Error)
and then
(Before = No_Element
or else
Parent (Container, Before) /= Target_Parent
or else raise Constraint_Error)
and then
(Target_Parent = Source_Parent
or else
Is_Ancestor_Of (Container, Source_Parent, Target_Parent)
or else raise Constraint_Error),
Post => Node_Count (Container) = Node_Count (Container)'Old;
function Parent (Position : Cursor)
return Cursor
with Nonblocking, Global =>
in all, Use_Formal =>
null,
Post => (
if Position = No_Element
or else
Is_Root (Position)
then Parent'Result = No_Element);
function Parent (Container : Tree;
Position : Cursor)
return Cursor
with Nonblocking, Global =>
null, Use_Formal =>
null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (
if Position = No_Element
or else
Is_Root (Container, Position)
then Parent'Result = No_Element
else Has_Element (Container, Parent'Result));
function First_Child (Parent : Cursor)
return Cursor
with Nonblocking, Global =>
in all, Use_Formal =>
null,
Pre => Parent /= No_Element
or else raise Constraint_Error;
function First_Child (Container : Tree;
Parent : Cursor)
return Cursor
with Nonblocking, Global =>
null, Use_Formal =>
null,
Pre => (Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => First_Child'Result = No_Element
or else
Has_Element (Container, First_Child'Result);
function First_Child_Element (Parent : Cursor)
return Element_Type
with Nonblocking, Global =>
in all, Use_Formal => Element_Type,
Pre => (Parent /= No_Element
and then
Last_Child (Parent) /= No_Element)
or else raise Constraint_Error;
function First_Child_Element (Container : Tree;
Parent : Cursor)
return Element_Type
with Nonblocking, Global =>
null, Use_Formal => Element_Type,
Pre => (Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error)
and then
(First_Child (Container, Parent) /= No_Element
or else raise Constraint_Error);
function Last_Child (Parent : Cursor)
return Cursor
with Nonblocking, Global =>
in all, Use_Formal =>
null,
Pre => Parent /= No_Element
or else raise Constraint_Error;
function Last_Child (Container : Tree;
Parent : Cursor)
return Cursor
with Nonblocking, Global =>
null, Use_Formal =>
null,
Pre => (Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Last_Child'Result = No_Element
or else
Has_Element (Container, Last_Child'Result);
function Last_Child_Element (Parent : Cursor)
return Element_Type
with Nonblocking, Global =>
in all, Use_Formal => Element_Type,
Pre => (Parent /= No_Element
and then
Last_Child (Parent) /= No_Element)
or else raise Constraint_Error;
function Last_Child_Element (Container : Tree;
Parent : Cursor)
return Element_Type
with Nonblocking, Global =>
null, Use_Formal => Element_Type,
Pre => (Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error)
and then
(Last_Child (Container, Parent) /= No_Element
or else raise Constraint_Error);
function Next_Sibling (Position : Cursor)
return Cursor
with Nonblocking, Global =>
in all, Use_Formal =>
null,
Post => (
if Position = No_Element
then Next_Sibling'Result = No_Element);
function Next_Sibling (Container : Tree;
Position : Cursor)
return Cursor
with Nonblocking, Global =>
null, Use_Formal =>
null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (
if Next_Sibling'Result = No_Element
then
Position = No_Element
or else
Is_Root (Container, Position)
or else
Last_Child (Container, Parent (Container, Position))
= Position
else Has_Element (Container, Next_Sibling'Result));
procedure Next_Sibling (Position :
in out Cursor)
with Nonblocking, Global =>
in all, Use_Formal =>
null;
procedure Next_Sibling (Container :
in Tree;
Position :
in out Cursor)
with Nonblocking, Global =>
null, Use_Formal =>
null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (
if Position /= No_Element
then Has_Element (Container, Position));
function Previous_Sibling (Position : Cursor)
return Cursor
with Nonblocking, Global =>
in all, Use_Formal =>
null,
Post => (
if Position = No_Element
then Previous_Sibling'Result = No_Element);
function Previous_Sibling (Container : Tree;
Position : Cursor)
return Cursor
with Nonblocking, Global =>
null, Use_Formal =>
null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (
if Previous_Sibling'Result = No_Element
then
Position = No_Element
or else
Is_Root (Container, Position)
or else
First_Child (Container, Parent (Container, Position))
= Position
else Has_Element (Container, Previous_Sibling'Result));
procedure Previous_Sibling (Position :
in out Cursor)
with Nonblocking, Global =>
in all, Use_Formal =>
null;
procedure Previous_Sibling (Container :
in Tree;
Position :
in out Cursor)
with Nonblocking, Global =>
null, Use_Formal =>
null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (
if Position /= No_Element
then Has_Element (Container, Position));
procedure Iterate_Children
(Parent :
in Cursor;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit,
Pre => Parent /= No_Element
or else raise Constraint_Error,
Global =>
in all, Use_Formal =>
null;
procedure Iterate_Children
(Container :
in Tree;
Parent :
in Cursor;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit,
Pre => (Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error);
procedure Reverse_Iterate_Children
(Parent :
in Cursor;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit,
Pre => Parent /= No_Element
or else raise Constraint_Error,
Global =>
in all, Use_Formal =>
null;
procedure Reverse_Iterate_Children
(Container :
in Tree;
Parent :
in Cursor;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit,
Pre => (Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error);
function Iterate_Children (Container :
in Tree; Parent :
in Cursor)
return Tree_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
with Pre => (Parent /= No_Element
or else raise Constraint_Error)
and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
type Tree (Base :
not null access Multiway_Trees.Tree)
is
tagged limited private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Node_Count),
Global =>
null,
Default_Initial_Condition => Node_Count (Tree) = 1,
Preelaborable_Initialization;
type Cursor
is private
with Preelaborable_Initialization;
Empty_Tree :
constant Tree;
No_Element :
constant Cursor;
function Has_Element (Position : Cursor)
return Boolean
with Nonblocking, Global =>
in all, Use_Formal =>
null;
package Tree_Iterator_Interfaces
is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
procedure Assign (Target :
in out Multiway_Trees.Tree;
Source :
in Tree)
with Post => Node_Count (Source) = Node_Count (Target);
function Copy (Source : Multiway_Trees.Tree)
return Tree
with Post => Node_Count (Copy'Result) = Node_Count (Source);
type Constant_Reference_Type
(Element :
not null access constant Element_Type)
is private
with Implicit_Dereference => Element,
Nonblocking, Global =>
null,
Default_Initial_Condition => (
raise Program_Error);
type Reference_Type
(Element :
not null access Element_Type)
is private
with Implicit_Dereference => Element,
Nonblocking, Global =>
null,
Default_Initial_Condition => (
raise Program_Error);
-- Additional subprograms as described in the text
-- are declared here.
private
... -- not specified by the language
end Stable;
private
... -- not specified by the language
end Ada.Containers.Multiway_Trees;
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.
The type Tree is used to represent trees. The type
Tree needs finalization
(see
7.6).
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.
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.
The primitive "=" operator for type Cursor
returns True if both cursors are No_Element, or designate the same element
in the same container.
Execution of the default implementation of the Input,
Output, Read, or Write attribute of type Cursor raises Program_Error.
Tree'Write for a Tree object T writes Node_Count(T)
- 1 elements of the tree to the stream. It may also write additional
information about the tree.
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.
Some operations
check for “tampering with cursors” of a container because
they depend on the set of elements of the container remaining constant,
and others check for “tampering with elements” of a container
because they depend on elements of the container not being replaced.
When tampering with cursors is
prohibited
for a particular tree object
T, Program_Error
is propagated by the finalization of
T, as well as by a call that
passes
T to certain of the operations of this package, as indicated
by the precondition of such an operation. Similarly, when tampering with
elements is
prohibited for
T, Program_Error is propagated
by a call that passes
T to certain of the other operations of
this package, as indicated by the precondition of such an operation.
Paragraphs 81 through
90 are removed as preconditions now describe these rules.
function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
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.
function Has_Element (Container : Tree; Position : Cursor)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
Returns True if
Position designates an element in Container, and returns False otherwise.
In particular, Has_Element returns False if the cursor designates a root
node or equals No_Element.
function Equal_Subtree (Left_Position : Cursor;
Right_Position: Cursor) return Boolean;
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.
function "=" (Left, Right : Tree) return Boolean;
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.
function Tampering_With_Cursors_Prohibited
(Container : Tree) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Returns True if
tampering with cursors or tampering with elements is currently prohibited
for Container, and returns False otherwise.
function Tampering_With_Elements_Prohibited
(Container : Tree) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Always returns False,
regardless of whether tampering with elements is prohibited.
function Is_Empty (Container : Tree) return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Node_Count (Container) = 1);
Returns True if
Container is empty.
function Node_Count (Container : Tree) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
Node_Count returns
the number of nodes in Container.
function Subtree_Node_Count (Position : Cursor) return Count_Type
with Nonblocking, Global => in all, Use_Formal => null);
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 Subtree_Node_Count (Container : Tree; Position : Cursor)
return Count_Type
with Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Nonblocking, Global => null, Use_Formal => null;
If Position is No_Element,
Subtree_Node_Count returns 0; otherwise, Subtree_Node_Count returns the
number of nodes in the subtree of Container that is rooted by Position.
function Depth (Position : Cursor) return Count_Type
with Nonblocking, Global => in all, Use_Formal => null;
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).
function Depth (Container : Tree; Position : Cursor)
return Count_Type
with Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Nonblocking, Global => null, Use_Formal => null;
If Position equals
No_Element, Depth returns 0; otherwise, Depth returns the number of ancestor
nodes of the node of Container designated by Position (including the
node itself).
function Is_Root (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
Is_Root returns
True if the Position designates the root node of some tree; and returns
False otherwise.
function Is_Root (Container : Tree; Position : Cursor)
return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Is_Root returns
True if the Position designates the root node of Container; and returns
False otherwise.
function Is_Leaf (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
Is_Leaf returns
True if Position designates a node that does not have any child nodes;
and returns False otherwise.
function Is_Leaf (Container : Tree; Position : Cursor)
return Boolean
with Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Nonblocking, Global => null, Use_Formal => null;
Is_Leaf returns
True if Position designates a node in Container that does not have any
child nodes; and returns False otherwise.
function Is_Ancestor_Of (Container : Tree;
Parent : Cursor;
Position : Cursor) return Boolean
with Pre => (Meaningful_For (Container, Position)
or else raise Program_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => null;
Is_Ancestor_Of returns
True if Parent designates an ancestor node of Position (including Position
itself), and returns False otherwise.
function Root (Container : Tree) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Post => Root'Result /= No_Element and then
not Has_Element (Container, Root'Result);
Root returns a cursor
that designates the root node of Container.
procedure Clear (Container : in out Tree)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Node_Count (Container) = 1;
Removes all the
elements from Container.
function Element (Position : Cursor) return Element_Type
with Pre => (Position /= No_Element or else
raise Constraint_Error) and then
(Has_Element (Position) or else raise Program_Error),
Nonblocking, Global => in all, Use_Formal => Element_Type;
Element returns
the element designated by Position.
function Element (Container : Tree;
Position : Cursor) return Element_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => Element_Type;
Element returns
the element designated by Position in Container.
procedure Replace_Element (Container : in out Tree;
Position : in Cursor;
New_item : in Element_Type)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
Replace_Element
assigns the value New_Item to the element designated by Position. For
the purposes of determining whether the parameters overlap in a call
to Replace_Element, the Container parameter is not considered to overlap
with any object (including itself).
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Position)
or else raise Program_Error),
Global => in all;
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 Query_Element
(Container : in Tree;
Position : in Cursor;
Process : not null access procedure (Element : in Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
Query_Element calls
Process.all with the element designated by Position as the argument.
Tampering with the elements of Container is prohibited during the execution
of the call on Process.all. Any exception raised by Process.all
is propagated.
procedure Update_Element
(Container : in out Tree;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
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.
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
The types Constant_Reference_Type
and Reference_Type need finalization.
This paragraph
was deleted.
function Constant_Reference (Container : aliased in Tree;
Position : in Cursor)
return Constant_Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
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.
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
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
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.
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)
with Pre => not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Node_Count (Source) = Node_Count (Target);
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.
function Copy (Source : Tree) return Tree
with Post =>
Node_Count (Copy'Result) = Node_Count (Source) and then
not Tampering_With_Elements_Prohibited (Copy'Result) and then
not Tampering_With_Cursors_Prohibited (Copy'Result);
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error),
Post => (if not Target'Has_Same_Storage (Source) then
Node_Count (Target) = Node_Count (Source'Old) and then
Node_Count (Source) = 1);
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error) and then
(Is_Leaf (Container, Position)
or else raise Constraint_Error),
Post =>
Node_Count (Container)'Old = Node_Count (Container) + 1 and then
Position = No_Element;
Delete_Leaf removes
(from Container) the element designated by Position, and Position is
set to No_Element.
procedure Delete_Subtree (Container : in out Tree;
Position : in out Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Node_Count (Container)'Old = Node_Count (Container) +
Subtree_Node_Count (Container, Position)'Old and then
Position = No_Element;
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.
procedure Swap (Container : in out Tree;
I, J : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(I /= No_Element or else Constraint_Error) and then
(J /= No_Element or else Constraint_Error) and then
(Has_Element (Container, I)
or else raise Program_Error) and then
(Has_Element (Container, J)
or else raise Program_Error);
Swap exchanges the
values of the elements designated by I and J.
function Find (Container : Tree;
Item : Element_Type)
return Cursor
with Post => (if Find'Result /= No_Element
then Has_Element (Container, Find'Result));
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
with Pre => Position /= No_Element or else raise Constraint_Error,
Post => (if Find_In_Subtree'Result = No_Element
then Has_Element (Find_In_Subtree'Result)),
Global => in all;
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.
function Find_In_Subtree (Container : Tree;
Position : Cursor;
Item : Element_Type)
return Cursor
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Position)
or else raise Program_Error),
Post => (if Find_In_Subtree'Result = No_Element
then Has_Element (Container, Find_In_Subtree'Result));
Find_In_Subtree
searches the subtree of Container rooted by Position for an element equal
to Item (using the generic formal equality operator). The search starts
at the element designated by Position. The search traverses the subtree
in a depth-first order. If no equal element is found, then Find returns
No_Element. Otherwise, it returns a cursor designating the first equal
element encountered.
function Ancestor_Find (Position : Cursor;
Item : Element_Type)
return Cursor
with Pre => Position /= No_Element or else raise Constraint_Error,
Post => (if Ancestor_Find'Result = No_Element
then Has_Element (Container, Ancestor_Find'Result)),
Global => in all;
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.
function Ancestor_Find (Container : Tree;
Position : Cursor;
Item : Element_Type)
return Cursor
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Position)
or else raise Program_Error),
Post => (if Ancestor_Find'Result = No_Element
then Has_Element (Container, Ancestor_Find'Result));
Ancestor_Find searches
for an element equal to Item (using the generic formal equality operator).
The search starts at the node designated by Position in Container, and
checks each ancestor proceeding toward the root of the subtree. If no
equal element is found, then Ancestor_Find returns No_Element. Otherwise,
it returns a cursor designating the first equal element encountered.
function Contains (Container : Tree;
Item : Element_Type) return Boolean;
Equivalent to Find
(Container, Item) /= No_Element.
procedure Iterate
(Container : in Tree;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
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.
procedure Iterate_Subtree
(Position : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => Position /= No_Element or else raise Constraint_Error,
Global => in all;
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.
procedure Iterate_Subtree
(Container : in Tree;
Position : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Position)
or else raise Program_Error);
Iterate_Subtree
calls Process.all with a cursor that designates each element in
the subtree rooted by the node designated by Position in Container, starting
from the node designated by Position and proceeding in a depth-first
order. Tampering with the cursors of the tree that contains the element
designated by Position is prohibited during the execution of a call on
Process.all. Any exception raised by Process.all is propagated.
function Iterate (Container : in Tree)
return Tree_Iterator_Interfaces.Parallel_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
Iterate returns
an iterator object (see
5.5.1) that will
generate a value for a loop parameter (see
5.5.2)
designating each element in Container, starting from the root node and
proceeding in a depth-first order when used as a forward iterator, and
processing all nodes concurrently when used as a parallel iterator. Tampering
with the cursors of Container is prohibited while the iterator object
exists (in particular, in the
sequence_of_statements
of the
loop_statement
whose
iterator_specification
denotes this object). The iterator object needs finalization.
function Iterate_Subtree (Position : in Cursor)
return Tree_Iterator_Interfaces.Parallel_Iterator'Class
with Pre => Position /= No_Element or else raise Constraint_Error,
Global => in all;
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 when used as a forward iterator, and processing
all nodes in the subtree concurrently when used as a parallel iterator.
Tampering with the cursors of the container that contains the node designated
by Position is prohibited while the iterator object exists (in particular,
in the
sequence_of_statements
of the
loop_statement
whose
iterator_specification
denotes this object). The iterator object needs finalization.
function Iterate_Subtree (Container : in Tree; Position : in Cursor)
return Tree_Iterator_Interfaces.Parallel_Iterator'Class
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
Iterate_Subtree
returns an iterator object (see
5.5.1) that
will generate a value for a loop parameter (see
5.5.2)
designating each element in the subtree rooted by the node designated
by Position in Container, starting from the node designated by Position
and proceeding in a depth-first order when used as a forward iterator,
and processing all nodes in the subtree concurrently when used as a parallel
iterator. Tampering with the cursors of the container that contains the
node designated by Position is prohibited while the iterator object exists
(in particular, in the
sequence_of_statements
of the
loop_statement
whose
iterator_specification
denotes this object). The iterator object needs finalization.
function Child_Count (Parent : Cursor) return Count_Type
with Post => (if Parent = No_Element then Child_Count'Result = 0),
Nonblocking, Global => in all, Use_Formal => null;
Child_Count returns
the number of child nodes of the node designated by Parent.
function Child_Count (Container : Tree; Parent : Cursor)
return Count_Type
with Pre => Meaningful_For (Container, Parent)
or else raise Program_Error,
Post => (if Parent = No_Element then Child_Count'Result = 0),
Nonblocking, Global => null, Use_Formal => null;
Child_Count returns
the number of child nodes of the node designated by Parent in Container.
function Child_Depth (Parent, Child : Cursor) return Count_Type
with Pre => (Parent /= No_Element and then Child /= No_Element)
or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => null;
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.
function Child_Depth (Container : Tree; Parent, Child : Cursor)
return Count_Type
with Pre => ((Parent /= No_Element and then Child /= No_Element)
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error) and then
(Meaningful_For (Container, Child)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => null;
Child_Depth returns
the number of ancestor nodes of Child within Container (including Child
itself), up to but not including Parent; Program_Error is propagated
if Parent is not an ancestor of Child.
procedure Insert_Child (Container : in out Tree;
Parent : in Cursor;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error) and then
(Meaningful_For (Container, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Container.Parent (Before) = Parent
or else raise Constraint_Error),
Post => Node_Count (Container) =
Node_Count (Container)'Old + Count;
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error) and then
(Meaningful_For (Container, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Container.Parent (Before) = Parent
or else raise Constraint_Error),
Post => (Node_Count (Container) =
Node_Count (Container)'Old + Count) and then
Has_Element (Container, Position);
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error) and then
(Meaningful_For (Container, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Container.Parent (Before) = Parent
or else raise Constraint_Error),
Post => (Node_Count (Container) =
Node_Count (Container)'Old + Count) and then
Has_Element (Container, Position);
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Node_Count (Container) =
Node_Count (Container)'Old + Count;
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Node_Count (Container) =
Node_Count (Container)'Old + Count;
Equivalent to Insert_Child
(Container, Parent, No_Element, New_Item, Count).
procedure Delete_Children (Container : in out Tree;
Parent : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => (Node_Count (Container) = Node_Count (Container)'Old -
Child_Count (Container, Parent)'Old) and then
Child_Count (Container, Parent) = 0;
Delete_Children
removes (from Container) all of the descendants of Parent other than
Parent itself.
procedure Copy_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Target, Parent)
or else raise Program_Error) and then
(Meaningful_For (Target, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Target.Parent (Before) = Parent
or else raise Constraint_Error) and then
(not Is_Root (Source)
or else raise Constraint_Error),
Post => Node_Count (Target) =
Node_Count (Target)'Old + Subtree_Node_Count (Source),
Global => in all;
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.
procedure Copy_Local_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Target, Parent)
or else raise Program_Error) and then
(Meaningful_For (Target, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Target.Parent (Before) = Parent
or else raise Constraint_Error) and then
(Meaningful_For (Target, Source)
or else raise Program_Error) and then
(not Is_Root (Source)
or else raise Constraint_Error),
Post => Node_Count (Target) = Node_Count (Target)'Old +
Subtree_Node_Count (Target, Source);
If Source is equal
to No_Element, then the operation has no effect. Otherwise, the subtree
rooted by Source in Target is copied (new nodes are allocated to create
a new subtree with the same structure as the Source subtree, with each
element initialized from the corresponding element of the Source subtree)
and inserted into Target as a child of Parent. If Parent already has
child nodes, then the new nodes are inserted prior to the node designated
by Before, or, if Before equals No_Element, the new nodes are inserted
after the last existing child node of Parent. The parent of the newly
created subtree is set to Parent. Any exception raised during allocation
of internal storage is propagated, and Container is not modified.
procedure Copy_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in Tree;
Subtree : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Target, Parent)
or else raise Program_Error) and then
(Meaningful_For (Target, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Target.Parent (Before) = Parent
or else raise Constraint_Error) and then
(Meaningful_For (Source, Subtree)
or else raise Program_Error) and then
(not Is_Root (Source, Subtree)
or else raise Constraint_Error),
Post => Node_Count (Target) = Node_Count (Target)'Old +
Subtree_Node_Count (Source, Subtree);
If Subtree is equal
to No_Element, then the operation has no effect. Otherwise, the subtree
rooted by Subtree in Source is copied (new nodes are allocated to create
a new subtree with the same structure as the Subtree, with each element
initialized from the corresponding element of the Subtree) and inserted
into Target as a child of Parent. If Parent already has child nodes,
then the new nodes are inserted prior to the node designated by Before,
or, if Before equals No_Element, the new nodes are inserted after the
last existing child node of Parent. The parent of the newly created subtree
is set to Parent. Any exception raised during allocation of internal
storage is propagated, and Container is not modified.
procedure Splice_Subtree (Target : in out Tree;
Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Position : in out Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Target, Parent)
or else raise Program_Error) and then
(Meaningful_For (Target, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Target.Parent (Before) /= Parent
or else raise Constraint_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Source, Position)
or else raise Program_Error) and then
(Target'Has_Same_Storage (Source) or else
Position = Before or else
Is_Ancestor_Of (Target, Position, Parent)
or else raise Constraint_Error),
Post => (declare
Org_Sub_Count renames
Subtree_Node_Count (Source, Position)'Old;
Org_Target_Count renames Node_Count (Target)'Old;
begin
(if not Target'Has_Same_Storage (Source) then
Node_Count (Target) = Org_Target_Count +
Org_Sub_Count and then
Node_Count (Source) = Node_Count (Source)'Old -
Org_Sub_Count and then
Has_Element (Target, Position)
else
Target.Parent (Position) = Parent and then
Node_Count (Target) = Org_Target_Count));
If Source denotes
the same object as Target, then: if Position equals Before there is no
effect; 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.
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.
procedure Splice_Subtree (Container: in out Tree;
Parent : in Cursor;
Before : in Cursor;
Position : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error) and then
(Meaningful_For (Container, Before)
or else raise Program_Error) and then
(Before = No_Element or else
Container.Parent (Before) /= Parent
or else raise Constraint_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error) and then
(Position = Before or else
Is_Ancestor_Of (Container, Position, Parent)
or else raise Constraint_Error),
Post => (Node_Count (Container) =
Node_Count (Container)'Old and then
Container.Parent (Position) = Parent);
If Position equals
Before, there is no effect. 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.
procedure Splice_Children (Target : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source : in out Tree;
Source_Parent : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error) and then
(Target_Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Target, Target_Parent)
or else raise Program_Error) and then
(Meaningful_For (Target, Before)
or else raise Program_Error) and then
(Source_Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Source, Source_Parent)
or else raise Program_Error) and then
(Before = No_Element or else
Parent (Target, Before) /= Target_Parent
or else raise Constraint_Error) and then
(Target'Has_Same_Storage (Source) or else
Target_Parent = Source_Parent or else
Is_Ancestor_Of (Target, Source_Parent, Target_Parent)
or else raise Constraint_Error),
Post => (declare
Org_Child_Count renames
Child_Count (Source, Source_Parent)'Old;
Org_Target_Count renames Node_Count (Target)'Old;
begin
(if not Target'Has_Same_Storage (Source) then
Node_Count (Target) = Org_Target_Count +
Org_Child_Count and then
Node_Count (Source) = Node_Count (Source)'Old -
Org_Child_Count
else
Node_Count (Target) = Org_Target_Count));
This
paragraph was deleted.
If Source denotes
the same object as Target, then:
if Target_Parent equals Source_Parent
there is no effect; else
This paragraph
was deleted.
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.
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.
procedure Splice_Children (Container : in out Tree;
Target_Parent : in Cursor;
Before : in Cursor;
Source_Parent : in Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Target_Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Target_Parent)
or else raise Program_Error) and then
(Meaningful_For (Container, Before)
or else raise Program_Error) and then
(Source_Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Source_Parent)
or else raise Program_Error) and then
(Before = No_Element or else
Parent (Container, Before) /= Target_Parent
or else raise Constraint_Error) and then
(Target_Parent = Source_Parent or else
Is_Ancestor_Of (Container, Source_Parent, Target_Parent)
or else raise Constraint_Error),
Post => Node_Count (Container) = Node_Count (Container)'Old;
If Target_Parent
equals Source_Parent there is no effect. 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
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element or else
Is_Root (Position) then Parent'Result = No_Element);
Returns a cursor
designating the parent node of the node designated by Position.
function Parent (Container : Tree;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element or else
Is_Root (Container, Position)
then Parent'Result = No_Element
else Has_Element (Container, Parent'Result));
Returns a cursor
designating the parent node of the node designated by Position in Container.
function First_Child (Parent : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Pre => Parent /= No_Element or else raise Constraint_Error;
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 (Container : Tree;
Parent : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => First_Child'Result = No_Element or else
Has_Element (Container, First_Child'Result);
First_Child returns
a cursor designating the first child node of the node designated by Parent
in Container; if there is no such node, No_Element is returned.
function First_Child_Element (Parent : Cursor) return Element_Type
with Nonblocking, Global => in all, Use_Formal => Element_Type,
Pre => (Parent /= No_Element and then
Last_Child (Parent) /= No_Element)
or else raise Constraint_Error;
Equivalent to Element
(First_Child (Parent)).
function First_Child_Element (Container : Tree;
Parent : Cursor) return Element_Type
with Nonblocking, Global => null, Use_Formal => Element_Type,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error) and then
(First_Child (Container, Parent) /= No_Element
or else raise Constraint_Error);
Equivalent to Element
(Container, First_Child (Container, Parent)).
function Last_Child (Parent : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Pre => Parent /= No_Element or else raise Constraint_Error;
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 (Container : Tree;
Parent : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Last_Child'Result = No_Element or else
Has_Element (Container, Last_Child'Result);
Last_Child returns
a cursor designating the last child node of the node designated by Parent
in Container; if there is no such node, No_Element is returned.
function Last_Child_Element (Parent : Cursor) return Element_Type
with Nonblocking, Global => in all, Use_Formal => Element_Type,
Pre => (Parent /= No_Element and then
Last_Child (Parent) /= No_Element)
or else raise Constraint_Error;
Equivalent to Element
(Last_Child (Parent)).
function Last_Child_Element (Container : Tree;
Parent : Cursor) return Element_Type
with Nonblocking, Global => null, Use_Formal => Element_Type,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error) and then
(Last_Child (Container, Parent) /= No_Element
or else raise Constraint_Error);
Equivalent to Element
(Container, Last_Child (Container, Parent)).
function Next_Sibling (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element
then Next_Sibling'Result = No_Element);
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 Next_Sibling (Container : Tree;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (if Next_Sibling'Result = No_Element then
Position = No_Element or else
Is_Root (Container, Position) or else
Last_Child (Container, Parent (Container, Position))
= Position
else Has_Element (Container, Next_Sibling'Result));
Next_Sibling returns
a cursor that designates the successor (with the same parent) of the
node designated by Position in Container.
function Previous_Sibling (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element
then Previous_Sibling'Result = No_Element);
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.
function Previous_Sibling (Container : Tree;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (if Previous_Sibling'Result = No_Element then
Position = No_Element or else
Is_Root (Container, Position) or else
First_Child (Container, Parent (Container, Position))
= Position
else Has_Element (Container, Previous_Sibling'Result));
Previous_Sibling
returns a cursor that designates the predecessor (with the same parent)
of the node designated by Position in Container.
procedure Next_Sibling (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
Equivalent to Position
:= Next_Sibling (Position);
procedure Next_Sibling (Container : in Tree;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
Equivalent to Position
:= Next_Sibling (Container, Position);
procedure Previous_Sibling (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
Equivalent to Position
:= Previous_Sibling (Position);
procedure Previous_Sibling (Container : in Tree;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Meaningful_For (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position);
Equivalent to Position
:= Previous_Sibling (Container, Position);
procedure Iterate_Children
(Parent : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => Parent /= No_Element or else raise Constraint_Error,
Global => in all, Use_Formal => null;
This
paragraph was deleted.
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.
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 Iterate_Children
(Container : in Tree;
Parent : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error);
Iterate_Children calls Process.all with
a cursor that designates each child node of Container and Parent, starting
with the first child node and moving the cursor as per the Next_Sibling
function.
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))
with Allows_Exit,
Pre => Parent /= No_Element or else raise Constraint_Error,
Global => in all, Use_Formal => null;
This
paragraph was deleted.
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.
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
(Container : in Tree;
Parent : in Cursor;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit,
Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error);
Reverse_Iterate_Children calls Process.all
with a cursor that designates each child node of Container and Parent,
starting with the last child node and moving the cursor as per the Previous_Sibling
function.
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.Parallel_Reversible_Iterator'Class
with Pre => (Parent /= No_Element
or else raise Constraint_Error) and then
(Meaningful_For (Container, Parent)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
Iterate_Children
returns an iterator object (see
5.5.1) that
will generate a value for a loop parameter (see
5.5.2)
designating each child node of Parent. When used as a forward iterator,
the nodes are designated starting with the first child node and moving
the cursor as per the function Next_Sibling; when used as a reverse iterator,
the nodes are designated starting with the last child node and moving
the cursor as per the function Previous_Sibling; when used as a parallel
iterator, processing all child nodes concurrently. Tampering with the
cursors of Container is prohibited while the iterator object exists (in
particular, in the
sequence_of_statements
of the
loop_statement
whose
iterator_specification
denotes this object). The iterator object needs finalization.
The nested package Multiway_Trees.Stable provides
a type Stable.Tree that represents a
stable tree,
which is one that cannot grow and shrink. Such a tree can be created
by calling the Copy function, or by establishing a
stabilized view
of an ordinary tree.
The subprograms
of package Containers.Multiway_Trees that have a parameter or result
of type tree are included in the nested package Stable with the same
specification, except that the following are omitted:
Tampering_With_Cursors_Prohibited, Tampering_With_Elements_Prohibited,
Assign, Move, Clear, Delete_Leaf, Insert_Child, Delete_Children, Delete_Subtree,
Copy_Subtree, Copy_Local_Subtree, Splice_Subtree, and Splice_Children
The operations of this package are equivalent
to those for ordinary trees, except that the calls to Tampering_With_Cursors_Prohibited
and Tampering_With_Elements_Prohibited that occur in preconditions are
replaced by False, and any that occur in postconditions are replaced
by True.
If a stable tree is declared with the Base discriminant
designating a pre-existing ordinary tree, the stable tree represents
a stabilized view of the underlying ordinary tree, and any operation
on the stable tree is reflected on the underlying ordinary tree. While
a stabilized view exists, any operation that tampers with elements performed
on the underlying tree is prohibited. The finalization of a stable tree
that provides such a view removes this restriction on the underlying
ordinary tree (though some other restriction can exist due to other concurrent
iterations or stabilized views).
If a stable tree is declared without specifying
Base, the object is necessarily initialized. The initializing expression
of the stable tree, typically a call on Copy, determines the Node_Count
of the tree. The Node_Count of a stable tree never changes after initialization.
Bounded (Run-Time) Errors
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 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.
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.
Implementation Requirements
No storage associated with a multiway tree object
shall be lost upon assignment or scope exit.
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 Advice
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).
Move should not copy elements, and should minimize
copying of internal data structures.
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.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
