!standard A.18.18(1) 09-05-28 AI05-0136-1/03 !class Amendment 09-02-04 !status work item 09-02-04 !status received 09-01-27 !priority Medium !difficulty Medium !subject Multiway tree container !summary Add a multiway tree container. !problem One of the most important advantages of using predefined containers over hand-building data structures is that the memory management is handled by the container. This is especially an advantage when the elements are indefinite types such as class-wide types. However, Ada 2005 does not provide any way to create a tree structure out of existing containers without requiring explicit memory management. Consider representing a multiway tree using only the existing containers. Clearly, the list of child nodes of an element can easily be represented as a list container. That list would have to be part of the element as inserted in the tree - which of course is also the type of the elements in the list. Thus, the container has to appear in its own elements; implementing that necesarily includes an incomplete type and an access type (which could be anonymous). (If Ada did not require that, then the implementation of the containers would be significantly constrained; in particular, bounded forms would be incompatible with direct inclusion in the elements). The use of an access type here necessarily requires the use of allocators and thus hand-written memory management. Indeed, it probably harder to use one of the existing container in this way than it is to write the operations directly. This situation cries out for a solution, and the easiest one is to provide one or more appropriate containers. !proposal Add a multiway tree container. A multiway tree allows multiple child elements for each parent element. (Such a tree is sometimes known as parent-child-sibling tree.) A multiway tree is the most general tree; many problems map directly into it (see examples for a number of such cases). !wording A.18.xx The Package Containers.Multiway_Trees The language-defined generic package Containers.Multiway_Trees provides private types List 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 internal nodes, each of which contains an element and pointers to the parent, first child, last child, next (successor) sibling, and previous (predecessor) sibling internal nodes. A cursor designates a particular node within a tree (and by extension the element contained in that node). 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 in 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). A node with no parent node is called an *orphan node*. A particular orphan node can be designated as the *root node* of the tree. The subtree rooted by the designated root node is the *active portion* of the tree; some operations only operate on the active portion of the tree. A node that has no children is called a *leaf node*. The *ancestors* of a node are the parent node, the parent of the parent node, and so on until a node with no parent is reached. Similarly, the *descendants* of a node are the child nodes, the children of each child node, and so on. The nodes of a subtree could be visited in several different orders. For a *depth-first order*, the last step of visiting a node is to visit the nodes of its child list in order, recursively. AARM Ramification: For the depth-first order, when each child node is visited, the child list of the child node is visited before the next sibling of the child node is visited. [Editor's note: I didn't define a breadth-first order. Such an order requires two trips through the child list (one to visit the child nodes, and once to to visit the children of those nodes. It also doesn't make sense for debugging/output applications, so it wasn't clear that it was very useful. Thus I didn't use it in any of the defined operations.] Static Semantics The generic library package Containers.Multiway_Trees has the following declaration: generic type Element_Type is private; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Multiway_Trees is pragma Preelaborate(Multiway_Trees); pragma Remote_Types(Multiway_Trees); type Tree is tagged private; pragma Preelaborable_Initialization(Tree); type Cursor is private; pragma Preelaborable_Initialization(Cursor); Empty_Tree : constant Tree; No_Element : constant Cursor; No_Parent : constant Cursor := No_Element; function Equal_Subtree (Left_Position : Cursor; Right_Position: Cursor) return Boolean; function "=" (Left, Right : Tree) return Boolean; function Is_Empty (Container : Tree) return Boolean; function Count (Container : Tree) return Count_Type; function Overall_Count (Container : Tree) return Count_Type; function Subtree_Count (Container : Tree; Position : Cursor) return Count_Type; function Depth (Position : Cursor) return Count_Type; function Is_Root (Position : Cursor) return Boolean; function Is_Orphan (Position : Cursor) return Boolean; function Is_Leaf (Position : Cursor) return Boolean; function Root (Container : Tree) return Cursor; procedure Set_Root (Container : in out Tree; Position : in Cursor); procedure Clear (Container : in out Tree); function Element (Position : Cursor) return Element_Type; procedure Replace_Element (Container : in out Tree; Position : in Cursor; New_Item : in Element_Type); procedure Query_Element (Position : in Cursor; Process : not null access procedure (Element : in Element_Type)); procedure Update_Element (Container : in out Tree; Position : in Cursor; Process : not null access procedure (Element : in out Element_Type)); procedure Assign (Target : in out Tree; Source : Tree); function Copy (Source : Tree) return Tree; procedure Move (Target : in out Tree; Source : in out Tree); procedure Delete (Container : in out Tree; Position : in out Cursor); procedure Delete_Subtree (Container : in out Tree; Position : in out Cursor); procedure Swap (Container : in out Tree; I, J : in Cursor); function Find (Container : Tree; Item : Element_Type; Position : Cursor := No_Element) return Cursor; function Overall_Find (Container : Tree; Item : Element_Type) return Cursor; function Ancestor_Find (Container : Tree; Item : Element_Type; Position : Cursor) return Cursor; function Contains (Container : Tree; Item : Element_Type) return Boolean; function Overall_Contains (Container : Tree; Item : Element_Type) return Boolean; function Has_Element (Position : Cursor) return Boolean; procedure Iterate (Container : in Tree; Process : not null access procedure (Position : in Cursor)); procedure Overall_Iterate (Container : in Tree; Process : not null access procedure (Position : in Cursor)); function Child_Count (Container : Tree; Parent : Cursor) return Count_Type; function Child_Depth (Parent, Child : Cursor) return Count_Type; procedure Insert_Child (Container : in out Tree; Parent : in Cursor; Before : in Cursor; New_Item : in Element_Type; Count : in Count_Type := 1); procedure Insert_Child (Container : in out Tree; Parent : in Cursor; Before : in Cursor; New_Item : in Element_Type; Position : out Cursor; Count : in Count_Type := 1); procedure Insert_Child (Container : in out Tree; Parent : in Cursor; Before : in Cursor; Position : out Cursor; Count : in Count_Type := 1); procedure Prepend_Child (Container : in out Tree; Parent : in Cursor; New_Item : in Element_Type; Count : in Count_Type := 1); procedure Append_Child (Container : in out Tree; Parent : in Cursor; New_Item : in Element_Type; Count : in Count_Type := 1); procedure Delete_Child_Subtree (Container : in out Tree; Parent : in Cursor; Position : in out Cursor; Count : in Count_Type := 1); procedure Splice_Subtree (Target : in out Tree; Parent : in Cursor; Before : in Cursor; Source : in out Tree); procedure Splice_Subtree (Target : in out Tree; Parent : in Cursor; Before : in Cursor; Source : in out Tree; Position : in out Cursor); procedure Splice_Subtree (Container: in out Tree; Parent : in Cursor; Before : in Cursor; Position : in Cursor); procedure Splice_Children (Target : in out Tree; Target_Parent : in Cursor; Before : in Cursor; Source : in out Tree; Source_Parent : in Cursor); procedure Splice_Children (Container : in out Tree; Target_Parent : in Cursor; Before : in Cursor; Source_Parent : in Cursor); function Parent (Position : Cursor) return Cursor; function First_Child (Container : Tree; Parent : Cursor) return Cursor; function First_Child_Element (Container : Tree; Parent : Cursor) return Element_Type; function Last_Child (Container : Tree; Parent : Cursor) return Cursor; function Last_Child_Element (Container : Tree; 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); procedure Iterate_Children (Container : in Tree; Parent : in Cursor; Process : not null access procedure (Position : in Cursor)); procedure Reverse_Iterate_Children (Container : in Tree; Parent : in Cursor; Process : not null access procedure (Position : in Cursor)); 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_Subtrees, 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_Subtrees, and "=" on tree values are unspecified. The type Tree is used to represent trees. The type List needs finalization (see 7.6). Empty_Tree represents the empty Tree object. It contains no nodes (Count (Empty_Tree) returns 0). 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. No_Parent represents a cursor that represents the parent of an orphan element. The predefined "=" 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. Some operations of this generic package have access-to-subprogram parameters. To ensure such operations are well-defined, they guard against certain actions by the designated subprogram. In particular, some operations check for "tampering with cursors" of a container because they depend on the set of elements of the container remaining constant, and others check for "tampering with elements" of a container because they depend on elements of the container not being replaced. A subprogram is said to tamper with cursors of a tree object T if: * it inserts or deletes elements of T, that is, it calls the Clear, Delete, Insert_Child, or Delete_Child procedures with T as a parameter; or AARM To be honest: Operations which are defined to be equivalent to a call on one of these operations also are included. Similarly, operations which call one of these as part of their definition are included. * it reorders the elements of T, that is, it calls the Splice or Splice_Children procedures; or * it finalizes T; or * it calls Assign with T as the Target parameter; or * it calls the Move procedure with T as a parameter. AARM Reason: Swap copies elements rather than reordering them, so it doesn't tamper with cursors. A subprogram is said to tamper with elements of a tree object T if: * it tampers with cursors of T; or * it replaces one or more elements of T, that is, it calls the Replace_Element or Swap procedures with T as a parameter. AARM Reason: Complete replacement of an element can cause its memory to be deallocated while another operation is holding onto a reference to it. That can't be allowed. However, a simple modification of (part of) an element is not a problem, so Update_Element does not cause a problem. function Equal_Subtree (Left_Position : Cursor; Right_Position: Cursor) return Boolean; If Left_Position or Right_Position equals No_Element, raises Constraint_Error. If the number of child nodes of the element designated by Left_Position is different than the number of child modes of the element designated by Right_Position, the function returns False. If comparing the element designated by Left_Position with the element designated by Right_Position using the generic formal equality operator returns 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 designated the corresponding child element of the element deisgnated 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. [Editor's note: I needed this to define "=" on Trees. We don't support comparing No_Element here, as that doesn't represent a "particular node" and doing so would require passing two container parameters as well. If you need want to compare the entire active tree of a container to some other subtree, pass Root.] AARM Ramification: Left_Position and Right_Position do not need to be from the same container. AARM Implementation Note: This wording describes the canonical semantics. However, the order and number of calls on the formal equality function is unspecified for all of the operations that use it in this package, so an implementation can call it as many or as few times as it needs to get the correct answer. Similarly, a global rule (see the introduction of Annex A) says that language-defined routines are not affected by overriding of other language-defined routines. This means that no reasonable program can tell how many times Equal_Subtrees is called, and thus an implementation can call it as many or as few times as it needs to get the correct answer. Specifically, there is no requirement to call the formal equality or Equal_Subtrees additional times once the answer has been determined. function "=" (Left, Right : Tree) return Boolean; If Left and Right denote the same tree object, then the function returns True. If Child_Count (Left, No_Element) does not equal Child_Count (Right, No_Element), then the function returns False. If Left has a designated root element and Right does not, or vice versa, the function returns False. Otherwise, it calls Equal_Subtree with a cursor designating each orphan element of Left and a cursor designating the corresponding orphan element of Right. 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. AARM Discussion: We test that the number of orphan elements is the same in each container. We also check that either both or neither of the trees has a designated root. Otherwise, we recursively test that all of the orphan subtrees are equivalent. We don't need to explicitly check the contents of the roots, since a designated root (if present) is always the first orphan node. AARM Implementation Note: Similar considerations apply here as apply to Equal_Subtrees. The actual number of calls performed is unspecified. function Count (Container : Tree) return Count_Type; If there is no designated root element of Container, Count returns 0; otherwise Count returns the number of elements in the active subtree of Container. function Overall_Count (Container : Tree) return Count_Type; Overall_Count returns the number of elements in the entire tree Container, including orphan elements and their children. function Subtree_Count (Container : Tree; Position : Cursor) return Count_Type; If Position equals No_Parent, and there is no designated root element, Subtree_Count returns 0; otherwise Subtree_Count returns the number of elements in the subtree rooted by the designated root element of Container. If Position is not No_Parent, Subtree_Count returns the number of elements in the subtree that is rooted by Position. function Is_Empty (Container : Tree) return Boolean; Equivalent to Overall_Count (Container) = 0. AARM Discussion: We use Overall_Count to ensure that all elements are counted; Count (Container) only counts the active subtree. This routine, of course, should be implemented a O(1), while Overall_Count is probably O(N). function Depth (Position : Cursor) return Count_Type; If Position equals No_Element, Depth returns 0; otherwise Depth returns the number of ancestor nodes of the element at Position (including the element itself). [Editor's note: Matt suggests that we have this function as well as Child_Depth because this is the most common case. We can't usefully default the Parent parameter in Child_Depth because it is first; putting the parameters in the other order would be inconsistent with all other routines (where the parent comes first) and thus would be confusing in positional calls.] function Is_Root (Position : Cursor) return Boolean; Is_Root returns True if the Position designates the element that is designated as the root of the tree; and returns False otherwise. function Is_Orphan (Position : Cursor) return Boolean; Is_Orphan returns True if Position designates an element that does not have a parent node; and returns False otherwise. AARM Ramification: Is_Orphan returns False if passed No_Element, as No_Element does not designate an element. function Is_Leaf (Position : Cursor) return Boolean; Is_Leaf returns True if Position designates an element that does not have any child nodes; and returns False otherwise. AARM Ramification: Is_Leaf returns False if passed No_Element, as No_Element does not designate an element. function Root (Container : Tree) return Cursor; Root returns a cursor that designates the element that is the designated root element of Container; it returns No_Element if there is no designated root element of Container. procedure Set_Root (Container : in out Tree; Position : in Cursor); If Position equals No_Element, then Container is set to have no designated root element. If Is_Orphan (Position) is False, Constraint_Error is propagated. Otherwise, the element designated by Position is set as the designated root element designated of Container. The newly designated element becomes the first orphan element of Container. AARM Ramification: If Root (Container) /= No_Element, then First_Child (Container, No_Parent) = Root (Container). procedure Clear (Container : in out Tree); Removes all the elements from Container. function Element (Position : Cursor) return Element_Type; If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Element returns the element designated by Position. procedure Replace_Element (Container : in out Tree; Position : in Cursor; New_Item : in Element_Type); If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise Replace_Element assigns the value New_Item to the element designated by Position. procedure Query_Element (Position : in Cursor; Process : not null access procedure (Element : in Element_Type)); If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Query_Element calls Process.all with the element designated by Position as the argument. Program_Error is propagated if Process.all tampers with the elements of Container. 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)); If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise Update_Element calls Process.all with the element designated by Position as the argument. Program_Error is propagated if Process.all tampers with the elements of Container. 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. procedure Assign (Target : in out Tree; Source : Tree); If Target denotes the same object as Source, the operation has no effect. Otherwise, it clears Target, and then each element of Source is assigned to a corresponding element in Target. AARM To Be Honest: The "corresponding element in Target" has a parent element that corresponds to the parent element of the Source element, and has child elements that correspond to the child elements of the Source element. function Copy (Source : Tree) return Tree; 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); If Target denotes the same object as Source, then Move has no effect. Otherwise, Move first calls Clear (Target). Then, the nodes in Source are moved to Target (in the same positions). After Move completes, Overall_Count(Target) is the number of nodes originally in Source, and Overall_Count(Source) is 0. procedure Delete (Container : in out Tree; Position : in out Cursor); If Position equals No_Element, then Constraint_Error is propagated. If Position does not designate an element in Container, then Program_Error is propagated. If the element designated by position has any child elements, then Constraint_Error is propagated. Otherwise Delete removes (from Container) the element designated by Position. Finally, Position is set to No_Element. AARM Ramification: The check on Position checks that the cursor does not belong to some other Container. This check implies that a reference to the container is included in the cursor value. This wording is not meant to require detection of dangling cursors; such cursors are defined to be invalid, which means that execution is erroneous, and any result is allowed (including not raising an exception). procedure Delete_Subtree (Container : in out Tree; Position : in out Cursor); If Position equals No_Element, then Constraint_Error is propagated. If Position does not designate an element in Container, then Program_Error is propagated. Otherwise Delete removes (from Container) the subtree designated by Position - that is, the element designated by Position along with all of the descendant elements of that element. Finally, Position is set to No_Element. procedure Swap (Container : in out Tree; I, J : in Cursor); If either I or J is No_Element, then Constraint_Error is propagated. If either I or J do not designate an element in Container, then Program_Error is propagated. Otherwise, Swap exchanges the values of the elements designated by I and J. AARM Ramification: After a call to Swap, I designates the element value previously designated by J, and J designates the element value previously designated by I. The elements position do not change; for instance, the parent node and the first child node of I are unchanged by the operation. AARM To be honest: The implementation is not required to actually copy the elements if it can do the swap some other way. But it is allowed to copy the elements if needed. function Find (Container : Tree; Item : Element_Type; Position : Cursor := No_Element) return Cursor; If Position is not No_Element, and does not designate an element in Container, then Program_Error is propagated. Find searches a subtree of the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at the element designated by Position, or at the designated root element if Position equals No_Element. The search checks the subtree rooted by Position 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. AARM Ramification: Find does not check any siblings of the element designated by Position. [Editor's note: This would naturally be called "Find_Subtree", but that is a misleading name, as what this does is Find *in* subtree (not finding a subtree). So we stick with plain "Find".] function Overall_Find (Container : Tree; Item : Element_Type) return Cursor; Overall_Find searches all of the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at the first orphan element. The search checks each orphan subtree (including the active subtree, if any) in a depth-first order. If no equal element is found, then Overall_Find returns No_Element. Otherwise, it returns a cursor designating the first equal element encountered. function Ancestor_Find (Container : Tree; Item : Element_Type; Position : Cursor) return Cursor; If Position is No_Element, then Constraint_Error is propagated. If Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Ancestor_Find searches for an element equal to Item (using the generic formal equality operator). The search starts at the element 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 Contains (Container : Tree; Item : Element_Type) return Boolean; Equivalent to Find (Container, Item) /= No_Element. function Overall_Contains (Container : Tree; Item : Element_Type) return Boolean; Equivalent to Overall_Find (Container, Item) /= No_Element. function Has_Element (Position : Cursor) return Boolean; Returns True if Position designates an element, and returns False otherwise. AARM To be honest: This function may not detect cursors that designate deleted elements; such cursors are invalid (see below) and the result of Has_Element for an invalid cursor is unspecified (but not erroneous). procedure Iterate (Container : in Tree; Process : not null access procedure (Position : in Cursor)); Iterate calls Process.all with a cursor that designates each node in the active portion of Container, starting with the designated root node and proceeding in a depth-first order. Program_Error is propagated if Process.all tampers with the cursors of Container. Any exception raised by Process.all is propagated. AARM Ramification: If there is no designated root node, Iterate does nothing; Process.all will not be called at all. AARM Implementation Note: The purpose of the tamper with cursors check is to prevent erroneous execution from the Position parameter of Process.all becoming invalid. This check takes place when the operations that tamper with the cursors of the container are called. The check cannot be made later (say in the body of Iterate), because that could cause the Position cursor to be invalid and potentially cause execution to become erroneous -- defeating the purpose of the check. See Iterate for vectors (A.18.2) for a suggested implementation of the check. End AARM Implementation Note. procedure Overall_Iterate (Container : in Tree; Process : not null access procedure (Position : in Cursor)); Iterate calls Process.all with a cursor that designates each node in the Container of Container, starting with the first orphan node and proceeding in a depth-first order, visiting each orphan subtree (including the active subtree, if any) in order. Program_Error is propagated if Process.all tampers with the cursors of Container. Any exception raised by Process.all is propagated. function Child_Count (Container : Tree; Parent : Cursor) return Count_Type; If Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Parent is equal to No_Parent, then Child_Count returns the number of orphan elements in Container (including the designated root element, if any). Otherwise, Child_Count returns the number of child elements of the element designated by Parent. function Child_Depth (Parent, Child : Cursor) return Count_Type; If Child is equal to No_Element, then Constraint_Error is propagated. If Child does not designate and element in Container, then Program_Error is propagated. If Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Parent is equal to No_Parent, Child_Depth returns the number of ancestor nodes of Child (including Child itself). Otherwise, Child_Depth returns the number of ancestor nodes of Child (including Child itself), up to but not including Parent; in this case 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); If Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Container.Parent (Before) is not equal to Parent, then Constraint_Error is raised. If Parent is equal to No_Parent, Insert_Child inserts Count orphan copies of New_Item prior to the (orphan) element designated by Before. If Before equals No_Element, the new elements are inserted after the last orphan node (if any). Otherwise, Insert_Child inserts Count copies of New_Item as children of Parent prior to the element designated by Before. If Before equals No_Element, the new elements are inserted after the last child node of Parent (if any). 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); If Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Container.Parent (Before) is not equal to Parent, then Constraint_Error is raised. If Parent is equal to No_Parent, Insert_Child inserts Count orphan copies of New_Item prior to the (orphan) element designated by Before. If Before equals No_Element, the new elements are inserted after the last orphan node (if any). Otherwise, Insert_Child inserts Count copies of New_Item as children of Parent prior to the element designated by Before. If Before equals No_Element, the new elements are inserted after the last child node of Parent (if any). Position designated the first newly-inserted element. 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); If Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Container.Parent (Before) is not equal to Parent, then Constraint_Error is raised. If Parent is equal to No_Parent, Insert_Child inserts Count orphan new elements prior to the (orphan) element designated by Before. If Before equals No_Element, the new elements are inserted after the last orphan node (if any). Otherwise, Insert_Child inserts Count new elements as children of Parent prior to the element designated by Before. If Before equals No_Element, the new elements are inserted after the last child node of Parent (if any). The new elements are initialized by default (see 3.3.1). Position designated the first newly-inserted element. 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); 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); Equivalent to Insert_Child (Container, Parent, Last_Child (Container, Parent), New_Item, Count). procedure Delete_Child_Subtree (Container : in out Tree; Parent : in Cursor; Position : in out Cursor; Count : in Count_Type := 1); If Position equals No_Element, then Constraint_Error is propagated. If Position does not designate an element in Container, then Program_Error is propagated. If Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Position is not equal to No_Element, and Container.Parent (Position) is not equal to Parent, then Constraint_Error is raised. Otherwise Delete removes (from Container) Count elements and their dependent elements starting at the element designated by Position (or all of the elements starting at Position if there are fewer than Count elements starting at Position). Finally, Position is set to No_Element. [Editor's note: The primary difference of this routine is providing of a Count. This allows the deletion of all of the children of a node without having to write a loop with repeated tests. Container.Delete_Child_Subtree (My_Parent, Position => Container.First_Child (My_Parent), Count => 10000); will delete all of the child nodes. We don't provide a Delete_Child that only deletes leaf nodes (as we do for the entire container), as that would require pretesting the nodes to verify that they are leaves before doing any deletions, eliminating any performance advantage.] procedure Splice_Subtree (Target : in out Tree; Parent : in Cursor; Before : in Cursor; Source : in out Tree); If Parent is not equal to No_Parent, and does not designate an element in Target, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Target, then Program_Error is propagated. If Before is not equal to No_Element, and Target.Parent (Before) is not equal to Parent, then Constraint_Error is raised. Otherwise, if Source denotes the same object as Target, or if there is no active subtree in Source, the operation has no effect. Otherwise, Splice_Subtree reorders elements such that the active subtree is removed from Source and moved to Target. The subtree is inserted as a child of Parent (or, if Parent is equal to No_Parent, as an orphan subtree) prior to the element designated by Before. If Before equals No_Element, the subtree is inserted after the last child node of Parent (if any), or if Parent is equal to No_Parent, after the last orphan node (if any). The overall count of Target is incremented by Count (Source), and Source is set to have no designated root element. AARM Ramification: If Source contains non-root orphan nodes, Overall_Count (Source) may not be zero after this operation, as they are not moved. However, the sum of the overall counts for the source and target before Splice_Subtree will be the same as the sum of the overall counts afterwards. [Editor's note: This would naturally be called "Splice_Child", but that name is misleading. I originally used just "Splice", but Matt suggested that "Splice_Subtree" is more evokative of what it does.] procedure Splice_Subtree (Target : in out Tree; Parent : in Cursor; Before : in Cursor; Source : in out Tree; Position : in out Cursor); If Position is equal to No_Element then Constraint_Error is propagated. If Parent is not equal to No_Parent, and does not designate an element in Target, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Target, then Program_Error is propagated. If Position does not equal No_Element, and does not designate a node in Source, then Program_Error is propagated. If Before is not equal to No_Element, and Target.Parent (Before) is not equal to Parent, then Constraint_Error is raised. If Source denotes the same object as Target, then there is no effect if Position equals Before, else the subtree rooted by the element designated by Position is moved immediately prior to Before, or, if Before equals No_Element, after the last child node of Parent (if any) or if Parent is equal to No_Parent, after the last orphan node. In each of these cases, Position and the overall count of Target are unchanged, and the parent of the element designated by Position is set to Parent. Otherwise, the subtree designated by Position is removed from Source and moved to Target. The subtree is inserted as a child of Parent (or, if Parent is equal to No_Parent, as an orphan subtree) prior to the element designated by Before. If Before equals No_Element, the subtree is inserted after the last child node of Parent (if any), or if Parent is equal to No_Parent, after the last orphan node (if any). In each of these cases, the overall count of Target is incremented by Subtree_Count (Position), and overall count of Source is decremented by Subtree_Count (Position), Position is updated to represent an element in Target. AARM Ramification: If Source is the same as Target, and Position = Before, or Next_Sibling(Position) = Before, Splice has no effect, as the subtree does not have to move to meet the postcondition. procedure Splice_Subtree (Container: in out Tree; Parent : in Cursor; Before : in Cursor; Position : in Cursor); If Position is equal to No_Element then Constraint_Error is propagated. If Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Container, then Program_Error is propagated. If Position does not equal No_Element, and does not designate a node in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Container.Parent (Before) is not equal to Parent, then Constraint_Error is raised. If Position equals Before there is no effect. Otherwise, the subtree rooted by the element designated by Position is moved immediately prior to Before, or, if Before equals No_Element, after the last child node of Parent (if any) or if Parent is equal to No_Parent, after the last orphan node. 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); If Target_Parent is not equal to No_Parent, and does not designate an element in Target, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Target, then Program_Error is propagated. If Source_Parent is not equal to No_Parent, and does not designate an element in Source, then Program_Error is propagated. If Before is not equal to No_Element, and Target.Parent (Before) is not equal to Target_Parent, then Constraint_Error is raised. If Source denotes the same object as Target, then: * if Target_Parent equals Source_Parent there is no effect; else * if Source_Parent is equal to No_Parent or Source_Parent is an ancestor of Target_Parent, then Constraint_Error is propagated; else * the child elements (and their descendants) of Source_Parent are moved to be child elements of Target_Parent immediately prior to Before, or, if Before equals No_Element, after the last child node of Target_Parent (if any) or if Target_Parent is equal to No_Parent, after the last orphan node. The parent of each moved child element is set to Target_Parent. AARM Reason: We can't allow moving the children of Source_Parent to an descendant node, as the descendant node will be part of one of the subtrees being moved. Otherwise (if Source does not denote the same object as Target), the child elements (and their descendants) of Source_Parent are removed from Source and moved to Target. If Source_Parent is equal to No_Parent, all of the orphan elements of Source are moved. The child (or orphan) elements are inserted as children of Target_Parent (or, if Target_Parent is equal to No_Parent, as an orphan subtree) prior to the element designated by Before. If Before equals No_Element, the child (or orphan) elements are inserted after the last child node of Target_Parent (if any), or if Parent is equal to No_Parent, after the last orphan node (if any). In each of these cases, the overall count of Target is incremented by Subtree_Count (Source_Parent)-1, and overall count of Source is decremented by Subtree_Count (Source_Parent)-1. AARM Ramification: The node designated by Source_Parent is not moved, thus we never need to update Source_Parent. Move (Target, Source) could be written Splice_Children (Target, No_Parent, No_Element, Source, No_Parent); End AARM Ramification. procedure Splice_Children (Container : in out Tree; Target_Parent : in Cursor; Before : in Cursor; Source_Parent : in Cursor); If Target_Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Before is not equal to No_Element, and does not designate an element in Container, then Program_Error is propagated. If Source_Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Before is not equal to No_Element, and Container.Parent (Before) is not equal to Target_Parent, then Constraint_Error is raised. If Target_Parent equals Source_Parent there is no effect. If Source_Parent is equal to No_Parent or Source_Parent is an ancestor of Target_Parent, then Constraint_Error is propagated. Otherwise the child elements (and their descendants) of Source_Parent are moved to be child elements of Target_Parent immediately prior to Before, or, if Before equals No_Element, after the last child node of Target_Parent (if any) or if Target_Parent is equal to No_Parent, after the last orphan node. The parent of each moved child element is set to Target_Parent. function Parent (Position : Cursor) return Cursor; If Position is equal to No_Element then Constraint_Error is propagated. If the element designated by Position is an orphan element, No_Parent is returned. Otherwise, a cursor designating the parent element of the element designated by Position is returned. function First_Child (Container : Tree; Parent : Cursor) return Cursor; If Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Parent is equal to No_Parent, First_Child returns a cursor designating the first orphan element in Container; if there is no such element, No_Element is returned. Otherwise, First_Child returns a cursor designating the first child element of the element designated by Parent; if ther is no such element, No_Element is returned. function First_Child_Element (Container : Tree; Parent : Cursor) return Element_Type; Equivalent to Element (First_Child (Container, Parent)). function Last_Child (Container : Tree; Parent : Cursor) return Cursor; If Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Parent is equal to No_Parent, Last_Child returns a cursor designating the last orphan element in Container; if there is no such element, No_Element is returned. Otherwise, Last_Child returns a cursor designating the last child element of the element designated by Parent; if there is no such element, No_Element is returned. function Last_Child_Element (Container : Tree; Parent : Cursor) return Element_Type; Equivalent to Element (Last_Child (Container, Parent)). function Next_Sibling (Position : Cursor) return Cursor; If Position equals No_Element or designates the last child element 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 element designated by Position. function Previous_Sibling (Position : Cursor) return Cursor; If Position equals No_Element or designates the last child element of its parent, then Next_Sibling returns the value No_Element. Otherwise, it returns a cursor that designates the predecessor (with the same parent) of the element designated by Position. procedure Next_Sibling (Position : in out Cursor); Equivalent to Position := Next_Sibling (Position); procedure Previous_Sibling (Position : in out Cursor); Equivalent to Position := Previous_Sibling (Position); procedure Iterate_Children (Container : in Tree; Parent : in Cursor; Process : not null access procedure (Position : in Cursor)); If Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Parent is equal to No_Parent, Iterate_Children calls Process.all with a cursor that designates each orphan node in Container, starting with the first orphan node and moving the cursor as per the Next_Sibling function. Otherwise, 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. Program_Error is propagated if Process.all tampers with the cursors of Container. 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)); If Parent is not equal to No_Parent, and does not designate an element in Container, then Program_Error is propagated. If Parent is equal to No_Parent, Iterate_Children calls Process.all with a cursor that designates each orphan node in Container, starting with the last orphan node and moving the cursor as per the Previous_Sibling function. Otherwise, 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. Program_Error is propagated if Process.all tampers with the cursors of Container. Any exception raised by Process.all is propagated. 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 to 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; * A subtree that contains the element it designated has been moved to a different tree by a call to Splice_Children or Splice_Subtree; or * The element it designates has been deleted. [Editor's note: We have to include moving a subtree to a different container as a cause of invalidating a cursor. It appears that the case of a full list splice is missing from the list of A.18.3(153-156), as it should invalidate cursors that point into the source list.] 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. AARM Discussion: The list above is intended to be exhaustive. In other cases, a cursor value continues to designate its original element. For instance, cursor values survive the insertion and deletion of other nodes. While it is possible to check for these cases, in many cases the overhead necessary to make the check is substantial in time or space. Implementations are encouraged to check for as many of these cases as possible and raise Program_Error if detected. 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 list shall have the effect of copying the elements from the source tree object to the target tree object. AARM Implementation Note: An assignment of a Tree is a "deep" copy; that is the elements are copied as well as the data structures. We say "effect of" in order to allow the implementation to avoid copying elements immediately if it wishes. For instance, an implementation that avoided copying until one of the containers is modified would be allowed. Implementation Advice 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, Insert_Child with Count=1, and Delete should be O(log N). AARM Reason: We do not mean to overly constrain implementation strategies here. However, it is important for portability that the performance of large containers has roughly the same factors on different implementations. If a program is moved to an implementation that takes O(N) time to access elements, that program could be unusable when the trees are large. We allow O(log N) access because the proportionality constant and caching effects are likely to be larger than the log factor, and we don't want to discourage innovative implementations. Move should not copy elements, and should minimize copying of internal data structures. AARM Implementation Note: Usually that can be accomplished simply by moving the pointer(s) to the internal data structures from the Source container to the Target container. 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. AARM Reason: This is important so that programs can recover from errors. But we don't want to require heroic efforts, so we just require documentation of cases where this can't be accomplished. A.18.YY The Package Containers.Indefinite_Multiway_Trees The language-defined generic package Containers.Indefinite_Multiway_Trees provides private types Tree and Cursor, and a set of operations for each type. It provides the same operations and semantics as the package Containers.Multiway_Trees (see A.18.xx), with the difference that the generic formal Element_Type is indefinite. Static Semantics The declaration of the generic library package Containers.Indefinite_Multiway_Trees has the same contents as Containers.Multiway_Trees except: * The generic formal Element_Type is indefinite. * The procedure with the profile: procedure Insert_Child (Container : in out Tree; Parent : in Cursor; Before : in Cursor; Position : out Cursor; Count : in Count_Type := 1); is omitted. AARM Discussion: This procedure is omitted because there is no way to create a default-initialized object of an indefinite type. We considered having this routine insert an empty element similar to the empty elements of a vector, but rejected this possibility because the semantics are fairly complex and very different from the existing case. That would make it more error-prone to convert a container from a definite type to an indefinite type; by omitting the routine completely, any problems will be diagnosed by the compiler. The actual Element parameter of access subprogram Process of Update_Element may be constrained even if Element_Type is unconstrained. [** TBD** We need to define a bounded form similarly to the ones in AI05-0001-1. Copy the linked list to the extent possible.] !discussion The author has found that almost all of his large projects contained a least one multiway tree, as it is an ideal structure for representing nesting. Flatter structures such as the existing containers do not handle nesting well. The name "multiway tree" seems to be the most common one for this data structure in the literature. (It sometimes is written "multi-way tree".) We do not provide an indexing method in this tree; this is purely a structuring data structure. If indexing is needed, a set or map container (already provided by the Ada Containers library) is probably more appropriate. Model: The model is that every element in the tree has an associated doubly-linked list of children. Thus we provide almost all of the operations of the list container, each with an added Parent parameter. We did not change the basic names of the operations for familiarity. We added "_Child" to each name in order to describe clearly what is being accessed. We considered leaving the names the same (without the "_Child" suffix), but that seemed confusing, as it would be easy to believe that First always represents the first node of the root of the tree. Having "_Child" as part of the names also opens up the possibility of operations not having the "_Child" suffix. These would naturally operate on the entire tree. We're taken advantage of this to define operations like Find and Iterate over the entire tree. We've added the suffix "_Subtree" to a few operations to make it clear that they operate on entire subtrees, as opposed to a single element. While this isn't strictly necessary, it should enhance readability of code. Elements are stored in internal nodes (as in the linked list container). Nodes which do not have parents are called "orphan elements" (or possibly "orphan nodes", if we need that terminology in the actual wording. These also form a list of elements, and the normal "child" operations can be used on the list of orphan elements. One of the orphan elements can be designated the "root" of the tree. Some operations operate on the tree that starts at the root, but ignore other orphan elements and their children. Orphan elements allow bottom-up tree creation where subtrees are stashed as orphan elements until their parent is created (at which time Slice_Children or Slice_Subtree would be used to make it a subtree of the appropriate parent). Without this capability, bottom up tree creation would require the creation of many container objects (each with overhead) and potentially would require copying of the subtrees and elements from one container to another with each step (this is certainly the case for a bounded tree container). We considered making the tree multirooted rather than designating a particular root node. Some reviewers considered this too weird, in addition, designating a particular root node allows elements to be in the container without being in the primary tree, which can be useful in some circumstances. Most operations that act on the entire tree container only act on the active portion of the tree (that is the subtree rooted by the designated root element); those usually have a counter-part that has the prefix "Overall_" that act on the entire container including all orphan subtrees. Note that we added the Assign and Copy routines here as proposed in AI05-0001-1. If we decide not to do that for the other containers, they should be removed here as well. Similarly, we define a bounded form here; in the unlikely event that we decide not to adopt AI05-0001-1, it should be removed here. For all of the subprograms that take a Parent parameter, if the parameter is No_Element, the node is inserted at the root of the tree. This is consistent with the meaning of the Before parameter in the Insert routines in the existing list containers. Operations that were dropped are: * Delete_First and Delete_Last: These seem unlikely to occur in the context of a tree (as opposed to a sequence like a list), and they're very easy to write yourself if necessary. [Editor's Note: Dropping these are all Matt's idea. :-) Since the names aren't the same anyway (they'd be Delete_First_Child and Delete_Last_Child) the consistency argument doesn't seem to hold much water.] * Swap_Links: Swapping within a single sibling list doesn't seem very useful. Swapping such that the parents get changed on the nodes can be a nightmare to describe and implement correctly: consider swapping two nodes where one is the parent of the other, and additional children are also involved. Exactly which elements end up where?? We do provide Swap, which just swaps the elements and leaves the nodes alone; that doesn't have definitional issues. * Reverse_Find: This is a strange operation, which would be hard to define sensibly. Rather, we provide Ancestor_Find, which has a clear definition. * Reverse_Elements: This seems like a strange operation operating on a single list of children. It makes no sense on the entire container. So we don't provide it. * Sorting operations: It seems weird to sort just a single list of child elements. And it also doesn't make any sense on the entire container. Note that we left the Container parameter in routines like First_Child, because the Parent parameter can be No_Element to represent no parent (an orphan element, including the root), and we need to know in which container to look for that orphan element. An alternative design would be to have a separate set of routines for accessing orphan elements (including the designated root), but that would clutter the package and complicate use (a lot of insertion code would have to explicitly check to see if it is inserting at the root: a scourge of hand-written code that we don't want to duplicate in the containers!). More on the orphan/root model: The inclusion of orphan elements also allows an implementation of the XML DOM to be built directly using one of these tree containers; the XML DOM also includes the capability of inserting elements without including them in the main tree (we call it the active tree). The model as defined means that T.First_Child (No_Parent) [where T is a tree container] returns the designated root node (if any). If there is no designated root node, it returns the first orphan node. Next_Sibling (T.Root) returns a non-root orphan node (if any). This model is slightly annoying, in that T.Last_Child (No_Parent) is unlikely to return the designated root node (unless there are no other orphans in the container). We considered an alternative model where both T.First_Child (No_Parent) and T.Last_Child (No_Parent) always returns the designated root node (or No_Element if there is no root node). In that model, the root node is not an orphan node, and the orphan nodes have their own separate list. For that model, we would need additional functions First_Orphan and Last_Orphan to be able to access the list of non-root orphans. (The list *has* to exist in order to implement operations like "=" and Iterate_All; it would be weird not to provide access to it.) We also would require a full set of _Sibling operations, because T.First_Child (Parent (Some_Element)) would not always return the child list that contains Some_Element. Essentially, any code that could operate on an orphan subtree and needed to look at the parent would have to test for the possibility that the node is an orphan and handle the case of no parent specially. This could be very annoying in programs that do bottom-up tree construction. With either model, (individual) operations directly on elements or that involve the relationships between elements do not care whether they are operating on an orphan subtree or on With the model we selected, most operations do not care if they are working on a node that belongs to the active subtree or to some other node. But many operations on the entire container only operate on the active subtree. Further ideas: * Should we have a function to get the maximum depth of the tree? * Matt thought that we should add some additional sibling handling routines. In particular, he suggested Sibling_Count, Iterate_Siblings, and First_Sibling, among others. These would occasionally be convinient, but are easily written using the existing routines: Sibling_Count (Tree, Position) = Child_Count (Tree, Parent(Position)) First_Sibling (Tree, Position) = First_Child (Tree, Parent(Position)) and so on. These could be added by defining them using the above equivalences, if desired. * More iterators could be useful. One could imagine wanting to visit the child nodes before their parents, as well as a straight breadth-first iteration. One possible way to (re)structure the overall iterator is to have two process routines, one that is called when a node is first visited, and the second after the children are visited. (That would allow a more direct mapping of the HTML example below.) This would look something like: procedure Iterate (Container : in Tree; Process_Before_Children : access procedure (Position : in Cursor); Process_After_Children : access procedure (Position : in Cursor)); (Note that these subprograms are allowed to be null, so that if one or the other isn't needed, it can be skipped.) The biggest objection to such an iterator is that it can't be mapped into for-loop-like syntax (one hopes that some future version of Ada will allow that). Advantages of the multiway tree container over hand-created trees: (1) Complete memory management, including for indefinite elements. (2) Avoidance of linking mistakes during operations like insertions and deletions. (3) More safety than hand-built structures -- tampering checks and possible dangling pointer (cursor) detection. (4) Completely linked (doubly-linked sibling lists; complete parent and child pointers), so walking in any direction in the tree is always O(1). (5) Built-in iterators. (6) Container users get streaming for free; streaming of a tree is fairly hard to do correctly. Disadvantages of the multiway tree container: (1) Not as familiar as some other containers; may not be used as much for that reason. (Authors can help aleviate this situation somewhat.) (2) Not as general as a general graph structure. But a general graph structure is much harder to describe, it is harder to manage memory for, and is not as commonly needed as a tree. (3) More memory management options are available for hand-created code. But that also provides a lot more opportunities for bugs. !examples (1) Representing HTML: (XML is similar) type Root_HTML_Element is tagged private; function Init_Element return Root_HTML_Element; procedure Output_Prefix (Element : Root_Element_Type); procedure Output_Suffix (Element : Root_Element_Type); type Text is Root_HTML_Element with record The_Text : Unbounded_String; end record; procedure Output_Prefix (Element : Bold_Element_Type); -- Writes The_Text procedure Output_Suffix (Element : Bold_Element_Type); -- Writes nothing. type Bold_HTML_Element is new Root_HTML_Element with null record; procedure Output_Prefix (Element : Bold_Element_Type); -- Writes procedure Output_Suffix (Element : Bold_Element_Type); -- Writes -- Similar overridings of Output_Prefix and Output_Suffix for each type; -- we won't show them here. type Italic_HTML_Element is new Root_HTML_Element with null record; type Div_HTML_Element is new Root_HTML_Element with record Class : Class_Name; Style : Style_String; -- other attributes. end record; type Span_HTML_Element is new Root_HTML_Element with record Class : Class_Name; Style : Style_String; -- other attributes. end record; type Header_HTML_Element is new Root_HTML_Element with null record; type Body_HTML_Element is new Root_HTML_Element with null record; -- and so on. package HTML_Tree is new Ada.Containers.Multiway_Trees (Root_HTML_Element'Class); -- The following HTML code: