Rationale for Ada 2012

John Barnes
Contents   Index   References   Search   Previous   Next 

8.4 Multiway tree containers

Three new containers are added for multiway trees; two correspond to the existing unbounded definite and unbounded indefinite forms for existing structures such as Lists and Maps in Ada 2005. There is also a bounded form corresponding to the newly introduced bounded containers for the existing structures discussed above. As expected their names are
These containers have all the operations required to operate on a tree structure where each node can have multiple child nodes to any depth. Thus there are operations on subtrees, the ability to find siblings, to insert and remove children and so on. It will be noted that many of the operations on trees are similar to corresponding operations on lists.
We will look in detail at the unbounded definite form by giving its specification interspersed with some explanation. It starts with the usual generic parameters.
with Ada.Iterator_Interfaces;
   type Element_Type is private;
   with function "=" (Left, Right: Element_Type)
            return Boolean is <>;
package Ada.Containers.Multiway_Trees is
   pragma Preelaborate(Multiway_Trees);
   pragma Remote_Types(Multiway_Trees);
   type Tree is tagged private
      with Constant_Indexing => Constant_Reference,
              Variable_Indexing => Reference,
              Default_Iterator => Iterate,
              Iterator_Element => Element_Type;
   pragma Preelaborable_Initialization(Tree);
   type Cursor is private;
   pragma Preelaborable_Initialization(Cursor);
   Empty_Tree: constant Tree;
   No_Element: constant Cursor;
   function Has_Element(Position: Cursor) return Boolean;
   package Tree_Iterator_Interfaces is new
            Ada.Iterator_Interfaces(Cursor, Has_Element);
This is much as expected and follows the same pattern as the start of the list container in the previous section.
   function Equal_Subtree
            (Left_Position: Cursor;
             Right_Position: Cursor) return Boolean;
   function "=" (Left, Right: Tree) return Boolean;
   function Is_Empty(Container: Tree) return Boolean;
   function Node_Count(Container: Tree) return Count_Type;
   function Subtree_Node_Count(Position: Cursor) return Count_Type;
   function Depth(Position: Cursor) return Count_Type;
   function Is_Root(Position: Cursor) return Boolean;
   function Is_Leaf(Position: Cursor) return Boolean;
   function Root(Container: Tree) return Cursor;
   procedure Clear(Container: in out Tree);
A tree consists of a set of nodes linked together in a hierarchical manner. Nodes are identified as usual by the value of a cursor. Nodes can have one or more child nodes; the children are ordered so that there is a first child and a last child. Nodes with the same parent are siblings. One node is the root of the tree. If a node has no children then it is a leaf node.
All nodes other than the root node have an associated element whose type is Element_Type. The whole purpose of the tree is of course to give access to these element values in a structured manner.
The function "=" compares two trees and returns true if and only if they have the same structure of nodes and corresponding nodes have the same values as determined by the generic parameter "=" for comparing elements. Similarly, the function Equal_Subtree compares two subtrees.
The function Node_Count gives the number of nodes in a tree. All trees have at least one node, the root node. The function Is_Empty returns true only if the tree consists of just this root node. Note that A_Tree = Empty_Tree, Node_Count(A_Tree) = 1 and Is_Empty(A_Tree) always have the same value. The function Subtree_Node_Count returns the number of nodes in the subtree identified by the cursor. If the cursor value is No_Element then the result is zero.
The functions Is_Root and Is_Leaf indicate whether a node is the root or a leaf respectively. If a tree is empty and so consists of just a root node then that node is both the root and a leaf so both functions return true.
The function Depth returns 1 if the node is the root, and otherwise indicates the number of ancestor nodes. Thus a node which is an immediate child of the root has depth equal to 2. The function Root returns the cursor designating the root of a tree. The procedure Clear removes all elements from the tree so that it consists just of a root node.
   function Element(Position: Cursor) return Element_Type;
   procedure Replace_Element
            (Container: in out Tree;
             Position: in Cursor;
             New_Item: in Element_Type);
   procedure Query_Element
            (Position: in Cursor;
             Process : not null access procedure Element: in Element_Type));
   procedure Update_Element
            (Container: in out Tree;
             Position: in Cursor;
             Process: not null access procedure (Element: in out Element_Type));
These subprograms have the expected behaviour similar to other containers.
   type Constant Reference_Type
            (Element: not null access constant Element_Type) is private
               with Implicit_Dereference => Element;
   type Reference_Type
            (Element: not null access Element_Type) is private
               with Implicit_Dereference => Element;
   function Constant_Reference
            (Container: aliased in Tree;
             Position: in Cursor) return Constant_Reference_Type;
   function Reference
            (Container: aliased in out Tree;
             Position: in Cursor) return Reference_Type;
These types and functions are similar to those for the other containers and were explained in Section 6.3 on iteration and also in the previous section (Section 8.3).
   procedure Assign(Target: in out Tree; Source: in Tree);
   function Copy(Source: Tree) return Tree;
   procedure Move(Target: in out Tree; Source: in out Tree);
The subprograms Assign and Copy behave as expected and were explained in Section 8.2 on Bounded and unbounded containers. The procedure Move moves all the nodes from the source to the target after first clearing the target; it does not make copies of the elements so after the operation the source only has a root node.
   procedure Delete_Leaf(Container: in out Tree; Position: in out Cursor);
   procedure Delete_Subtree(Container: in out Tree; Position: in out Cursor);
   procedure Swap(Container: in out Tree; I, J: in Cursor);
The procedures Delete_Leaf and Delete_Subtree check that the cursor value designates a node of the container and raise Program_Error if it does not. Program_Error is also raised if Position designates the root node and so cannot be removed. In the case of Delete_Leaf, if the node has any children then Constraint_Error is raised. The appropriate nodes are then deleted and Position is set to No_Element.
The procedure Swap interchanges the values in the two elements denoted by the two cursors. The elements must be in the given container (and must not denote the root) otherwise Program_Error is raised.
   function Find(Container: Tree; Item: Element_Type) return Cursor;
   function Find_In_Subtree(Item: Element_Type; Position: Cursor) return Cursor;
   function Ancestor_Find(Item: Element_Type; Position: Cursor) return Cursor;
   function Contains(Container: Tree; Item: Element_Type) return Boolean;
These search for an element in the container with the given value Item. The function Contains returns false if the item is not found; the other functions return No_Element if the item is not found. The function Find searches the whole tree starting at the root node, Find_In_Subtree searches the subtree rooted at the node given by Position including the node itself; these searches are in depth-first order. The function Ancestor_Find searches upwards through the ancestors of the node given by Position including the node itself.
Depth-first order is explained at the end of the section.
   procedure Iterate
            (Container: in Tree;
             Process: not null access procedure (Position: in Cursor));
   procedure Iterate_Subtree
            (Position: in Cursor;
             Process: not null access procedure (Position: in Cursor));
These apply the procedure designated by the parameter Process to each element of the whole tree or the subtree. This includes the node at the subtree but not at the root; iteration is in depth-first order.
   function Iterate(Container: in Tree)
                return Tree_Iterator_Interfaces.Forward_Iterator'Class;
   function Iterate_Subtree(Position: in Cursor)
                return Tree_Iterator_Interfaces.Forward_Iterator'Class;
The first of these is called if we write
for C in The_Tree.Iterate loop
   ...   -- do something via cursor C
end loop;
and iterates over the whole tree in the usual depth-first order. In order to iterate over a subtree we write
for C in The_Tree.Iterate_Subtree(S) loop
   ...   -- do something via cursor C
end loop;
and this iterates over the subtree rooted at the cursor position given by S.
If we use the other new form of loop using of thus
for E of The_Tree loop
   ...   -- do something to element E
end loop;
then this also calls Iterate since the aspect Default_Iterator of the type Tree (see above) is Iterate. However, we cannot iterate over a subtree using this mechanism.
   function Child_Count(Parent: Cursor) return Count_Type;
   function Child_Depth(Parent, Child: Cursor) return Count_Type;
The function Child_Count returns the number of child nodes of the node denoted by Parent. This count covers immediate children only and not grandchildren.
The function Child_Depth indicates how many ancestors there are from Child to Parent. If Child is an immediate child of Parent then the result is 1; if it is a grandchild then 2 and so on.
   procedure Insert_Child
            (Container: in out Tree;
             Parent: in Cursor;
             Before: in Cursor;
             New_Item: in Element_Type;
             Count: in Count_Type := 1);
   procedure Insert_Child
            (Container: in out Tree;
             Parent: in Cursor;
             Before: in Cursor;
             New_Item: in Element_Type;
             Position: out Cursor;
             Count: in Count_Type := 1);
   procedure Insert_Child
            (Container: in out Tree;
             Parent: in Cursor;
             Before: in Cursor;
             Position: out Cursor;
             Count: in Count_Type := 1);
These three procedures enable one or more new child nodes to be inserted. The parent node is given by Parent. If Parent already has children then the new nodes are inserted before the child node identified by Before; if Before is No_Element then the new nodes are inserted after all existing children. The second procedure is similar to the first but also returns a cursor to the first of the added nodes. The third is like the second but the new elements take their default values. Note the default value of one for the number of new nodes.
   procedure Prepend_Child
            (Container: in out Tree;
             Parent: in Cursor;
             New_Item: in Element_Type;
             Count: in Count_Type := 1);
   procedure Append_Child
            (Container: in out Tree;
             Parent: in Cursor;
             New_Item: in Element_Type;
             Count: in Count_Type:= 1);
These insert the new children before or after any existing children.
   procedure Delete_Children(Container: in out Tree; Parent: in Cursor);
This procedure simply deletes all the children, grandchildren, and so on of the node designated by Parent.
   procedure Copy_Subtree
            (Target: in out Tree;
             Parent: in Cursor;
             Before: in Cursor;
             Source: in Cursor);
This copies the complete subtree rooted at Source into the tree denoted by Tree as a subtree of Parent at the place denoted by Before using the same rules as Insert_Child. Note that this makes a complete copy and creates new nodes with values equal to the corresponding existing nodes. Note also that Source might be within Tree but might not. There are the usual various checks.
   procedure Splice_Subtree
            (Target: in out Tree;
             Parent: in Cursor;
             Before: in Cursor;
             Source: in out Tree;
             Position: in out Cursor);
   procedure Splice_Subtree
            (Container: in out Tree;
             Parent: in Cursor;
             Before: in Cursor;
             Position: in Cursor);
   procedure Splice_Children
            (Target: in out Tree;
             Target_Parent: in Cursor;
             Before: in Cursor;
             Source: in out Tree;
             Source_Parent: in Cursor);
   procedure Splice_Children
            (Container: in out Tree;
             Target_Parent: in Cursor;
             Before: in Cursor;
             Source_Parent: in Cursor);
These are similar to the procedures Splice applying to lists. They enable nodes to be moved without copying. The destination is indicated by Parent or Target_Parent together with Before as usual indicating where the moved nodes are to be placed with respect to existing children of Parent or Target_Parent.
The first Splice_Subtree moves the subtree rooted at Position in the tree Source to be a child of Parent in the tree Target. Note that Position is updated to be the appropriate element of Target. We can use this procedure to move a subtree within a tree but an attempt to create circularities raises Program_Error.
The second Slice_Subtree is similar but only moves a subtree within a container. Again, circularities cannot be created.
The procedures Splice_Children are similar but move all the children and their descendants of Source_Parent to be children of Target_Parent.
   function Parent(Position: Cursor) return Cursor;
   function First_Child(Parent: Cursor) return Cursor;
   function First_Child_Element(Parent: Cursor) return Element_Type;
   function Last_Child(Parent: Cursor) return Cursor;
   function Last_Child_Element(Parent: Cursor) return Element_Type;
   function Next_Sibling(Position: Cursor) return Cursor;
   function Previous_Sibling(Position: Cursor) return Cursor;
   procedure Next_Sibling(Position: in out Cursor);
   procedure Previous_Sibling(Position: in out Cursor);
Hopefully, the purpose of these is self-evident.
   procedure Iterate_Children
            (Parent: in Cursor;
             Process: not null access procedure (Position: in Cursor));
   procedure Reverse_Iterate_Children
            (Parent : in Cursor;
             Process: not null access procedure (Position: in Cursor));
These apply the procedure designated by the parameter Process to each child of the node given by Parent. The procedure Iterate_Children starts with the first child and ends with the last child whereas Reverse_Iterate_Children starts with the last child and ends with the first child. Note that these do not iterate over grandchildren.
   function Iterate_Children
            (Container: in Tree;
             Parent: in Cursor) return Tree_Iterator_Interfaces.Reversible_Iterator'Class;
This is called if we write
for C in Parent.Iterate_Children loop
   ...   -- do something via cursor C
end loop;
and iterates over all the children from Parent.First_Child to Parent.Last_Child. Note that we could also insert reverse thus
for C in reverse Parent.Iterate_Children loop
   ...   -- do something via cursor C
end loop;
in which case the iteration goes in reverse from Parent.Last_Child to Parent.First_Child. The observant reader will note that this function returns Reversible_Iterator'Class and so can go in either direction whereas the functions Iterate and Iterate_Subtree described earlier use Forward_Iterator'Class and cannot be reversed.
   ...   -- not specified by the language
end Ada.Containers.Multiway_Trees;
The above descriptions have not described all the situations in which something can go wrong and so raise Constraint_Error or Program_Error. Generally, the former is raised if a source or target is No_Element; the latter is raised if a cursor does not belong to the appropriate tree. In particular, as mentioned above, an attempt to create an illegal tree such as one with circularities using Splice_Subtree raises Program_Error. Remember also that every tree has a root node but the root node has no element value; attempts to remove the root node or read its value or assign a value similarly raise Program_Error.
The containers for indefinite and bounded trees are much as expected.
In the case of the indefinite tree container the generic formal type is
type Element_Type(<>) is private;
The other significant difference is that the procedure Insert_Child without the parameter New_Item is omitted; this is because indefinite types do not have a default value.
In the case of the bounded tree container the changes are similar to those for the other containers. One change is that the package has pragma Pure; the other changes concern the capacity. The type Tree is
type Tree(Capacity: Count_Type) is tagged private;
and the function Copy is
function Copy(Source: Tree; Capacity: Count_Type := 0) return Tree;
And of course the exception Capacity_Error is raised in various circumstances.
Applications of trees are usually fairly complex. The tree structure for depicting the analysis of a program for a whole language such as even Ada 83 has an enormous variety of nodes corresponding to the various syntactic structures. And trees depicting human relationships are complex because of multiple marriages, divorces, illegitimacy and so on. So we content ourselves with a couple of small examples.
A tree representing a simple algebraic expression involving just the binary operations of addition, subtraction, multiplication and division applied to simple variables and real literals is straightforward. Nodes are of three kinds, those representing operations have two children giving the two operands, and those representing variables and literals have no children and so are leaf nodes.
We can declare the element type thus
type Operator is ('+', '–', '×', '/');
type Kind is (Op, Var, Lit);
type El(K: Kind) is
      case K is
         when Op =>
            Fn: Operator;
         when Var =>
            V: Character;
         when Lit =>
            Val: Float;
      end case;
   end record;
Note that the variables are (as typically in mathematics) represented by single letters. So the expression
(x + 3) × (y – 4) 
is represented by nodes with elements such as
(Op, '×')
(Var, 'x')
(Lit, 3.0)
So now we can declare a suitable tree thus
package Expression_Trees is
   new Ada.Containers.Multiway_Trees(El);
use Expression_Trees;
My_Tree: Tree := Empty_Tree;
C: Cursor;
and then build it by the following statements
C := Root(My_Tree);
            (Container => My_Tree,
             Parent => C,
             Before => No_Element,
             New_Item => (Op, '×'),
             Position => C);
This puts in the first real node as a child of the root which is designated by the cursor C. There are no existing children so Before is No_Element. The New_Item is as mentioned earlier. Finally, the cursor C is changed to designate the position of the newly inserted node.
We can then insert the two children of this node which represent the mathematical operations + and –.
Insert_Child(My_Tree, C, No_Element, (Op, '+'));
Insert_Child(My_Tree, C, No_Element, (Op, '–'));
These calls are to a different overloading of Insert_Child and have not changed the cursor. The second call also has Before equal to No_Element and so the second child goes after the first child. We now change the cursor to that of the first newly inserted child and then insert its children which represent x and 3. Thus
C := First_Child(C);
Insert_Child(My_Tree, C, No_Element, (Var, 'x'));
Insert_Child(My_Tree, C, No_Element, (Lit, 3.0));
And then we can complete the tree by inserting the final two nodes thus
C := Next_Sibling(C);
Insert_Child(My_Tree, C, No_Element, (Var, 'y'));
Insert_Child(My_Tree, C, No_Element, (Lit, 4.0));
Of course a compiler will do all this recursively and keep track of the cursor rather more neatly than we have in this manual illustration.
The resulting tree should be as in Figure 1.
The expression tree
Figure 1 The expression tree
We can assume that the variables are held in an array which might be as follows
subtype Variable_Name is Character range 'a' .. 'z';
Variables: array (Variable_Name) of Float;
We can then evaluate the tree by a recursive function such as
function Eval(C: Cursor) return Float is
   E: El := Element(C);
   L, R: Float;
   case E.K is
      when Op =>
         L := Eval(First_Child(C));
         R := Eval(Last_Child(C));
         case E.Fn is
            when '+' => return (L+R);
            when '–' => return (L–R);
            when '×' => return (L*R);
            when '/' => return (L/R);
         end case;
      when Var =>
         return Variables(E.V);
      when Lit =>
         return E.Val;
   end case;
end Eval;
Finally, we obtain the value of the tree by
X := Eval(First_Child(Root(My_Tree)));
Remember that the node at the root has no element so hence the call of First_Child.
An alternative approach would be to use tagged types with a different type for each kind of node rather than the variant record. This would be much more flexible and would have required the use of the unbounded indefinite container Ada.Containers.Indefinite_Multiway_Trees.
As a more human example we can consider the family tree of the Tudor Kings and Queens of England. We start with Henry VII, who had four children, Arthur, Margaret, Henry VIII and Mary. See Figure 2.
The Tutor tree
Figure 2 The Tudor tree
Arthur died young, Margaret married James IV of Scotland and had James (who was thus James V of Scotland), Henry VIII had three children, namely Edward VI, Mary I and Elizabeth I. And Mary had Frances. Henry VII was succeeded by Henry VIII and he was succeeded by his three children.
Remember the rules of primogeniture. The heir is the eldest son if there are sons; if not then the heir is the eldest daughter. If there are no offspring at all then we go back a generation and try again. Hence Edward VI became king despite being younger than Mary.
Since Edward, Mary and Elizabeth had no children we go back to the descendants of the other children of Henry VII. Margaret, her son James, and his daughter Mary Queen of Scots were all dead by then, so the throne of England went to the son of Mary who became James I of England and VI of Scotland and thus united the two thrones. So the Tudor line died with Elizabeth (Good Queen Bess).
Incidentally, Frances, the daughter of Mary, the fourth child of Henry VII, had a daughter, Lady Jane Grey; she was Queen for 9 days but lost her head over a row with Mary I.
Representing this is tricky, especially with people such as Henry VIII having so many wives. But the essence could be represented by a tree with a simple element type thus
type Person is
      Name: String(1 .. 10);
      Sex: Gender;
      Birth: Date;
      Death: Date;
   end record;
With such a structure and the dates, starting from Henry VII and using the rules of primogeniture, one should be able to trace the monarchs (apart from poor Lady Jane Grey who would I am sure much rather not have been involved).
The overall tree structure is shown in Figure 2.
With the obvious connections we can define useful functions such as
function Are_Cousins(A, B: Cursor) return Boolean is
   (Parent(A) /= Parent (B) and then
    Parent(Parent(A)) = Parent(Parent(B)));
More of a challenge is to define a function Is_Successor using the rules described above. The reader can contemplate these and other family relationships and attempt to construct the Tudor tree.
Finally, an explanation of depth-first order. The general principle is that child nodes are visited in order before their parent. We can symbolically write this as
procedure Do_Node(N) is
   for CN in N.First_Child .. N.Last_Child loop
   end loop;
   if not N.Is_Root then
   end if;
end Do_Node;
and the whole thing is triggered by calling Do_Node(Root). Remember that the root node has no element. The result is that the first element to be processed is that of the leftmost leaf.
Thus in the tree illustrated below in Figure 3, the elements are visited in order A, B, C, D, and so on. Note that the root has no element and so is not visited.
A tree showing depth-first order
Figure 3 A tree showing depth-first order

Contents   Index   References   Search   Previous   Next 
© 2011, 2012, 2013 John Barnes Informatics.
Sponsored in part by:
The Ada Resource Association:


and   Ada-Europe: