CVS difference for ai05s/ai05-0136-1.txt

Differences between 1.4 and version 1.5
Log of other versions for file ai05s/ai05-0136-1.txt

--- ai05s/ai05-0136-1.txt	2009/06/02 06:22:37	1.4
+++ ai05s/ai05-0136-1.txt	2009/06/08 05:46:57	1.5
@@ -1,4 +1,4 @@
-!standard  A.18.18(1)                                09-05-28    AI05-0136-1/03
+!standard  A.18.18(1)                                09-06-07    AI05-0136-1/04
 !class Amendment 09-02-04
 !status work item 09-02-04
 !status received 09-01-27
@@ -119,7 +119,7 @@
 
    function Overall_Count (Container : Tree) return Count_Type;
 
-   function Subtree_Count (Container : Tree; Position : Cursor) return Count_Type;
+   function Subtree_Count (Position : Cursor) return Count_Type;
 
    function Depth (Position : Cursor) return Count_Type;
 
@@ -237,6 +237,11 @@
                                    Position  : in out Cursor;
                                    Count     : in     Count_Type := 1);
 
+   procedure Copy_Subtree (Target   : in out Tree;
+                           Parent   : in     Cursor;
+                           Before   : in     Cursor;
+                           Source   : in     Cursor);
+
    procedure Splice_Subtree (Target   : in out Tree;
                              Parent   : in     Cursor;
                              Before   : in     Cursor;
@@ -435,13 +440,10 @@
       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;
+   function Subtree_Count (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.
+      If Position is No_Element, Subtree_Count returns 0; otherwise, Subtree_Count
+      returns the number of elements in the subtree that is rooted by Position.
 
    function Is_Empty (Container : Tree) return Boolean;
 
@@ -844,6 +846,35 @@
       verify that they are leaves before doing any deletions, eliminating any
       performance advantage.]
 
+   procedure Copy_Subtree (Target   : in out Tree;
+                           Parent   : in     Cursor;
+                           Before   : in     Cursor;
+                           Source   : in     Cursor);
+
+      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. 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 in Target) is copied (a new subtree is created with
+      the same structure as the Source subtree, with each element initialized
+      from the corresponding element of the Source subtree) and and inserted
+      into Target 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 newly created
+      subtree is set to Parent, and the overall count of Target is incremented
+      by Subtree_Count (Source).
+
+      AARM Discussion: We only need one routine here, as the source object
+      is not modified, so we can use the same routine for both copying within
+      and between containers.
+
+      [Editor's note: Normally, we would call the Source parameter "Position";
+      and Target would be "Container" but that seems to imply that the same
+      container is required for the Source parameter (which it is not).]
+
    procedure Splice_Subtree (Target   : in out Tree;
                              Parent   : in     Cursor;
                              Before   : in     Cursor;
@@ -1361,6 +1392,90 @@
 operations on the entire container only operate on the active subtree.
 
 
+Some reviewers would prefer a "classic" single-rooted tree. Such a model seems
+cleaner on first reflection, but in practice it does not simplify either the wording
+nor the use of the container. In addition, it makes some operations much more complex.
+We want the tree container to allow operations as naturally as possible, extra
+complications are more likely to cause users to abandon the container.
+
+The main definitional problem is how to define the single root. If we used traditional
+node insertion, then we would have to have rules for an empty tree and in addition
+we would need rules to prevent inserting a second root (this would be necessary for
+at least the various Inserts, Splices, Copy_Subtree). But this somewhat silly, given
+that the first operation on every tree object would have to be to insert the one-and-only
+root.
+
+The only sane alternative would be to have a root node that is always present, but can
+be in an empty state. In this case, inserting any node at the root is always illegal
+(and can easily be prevented by simply not allowing the Parent parameter to ever be
+No_Element). But then, we would have to define the idea of an uninitialized element
+for just this one node, and we would probably want a way to "unset" the value of this
+node. This seems like too much complication.
+
+The usage problem comes about because with a single rooted tree, replacing the root
+is impossible. The effect is that a tree transformation that needs to change the root
+is complicated, and a general purpose transformation usually will have to have a
+special case just to handle the root.
+
+One obvious example is the bottom-up tree construction noted earlier. In order to do that
+in a single-rooted tree, we would have to either use many tree objects (each with associated
+overhead, and in the case of bounded trees, each Splice_Subtree would have to copy the
+nodes and elements as well), or we would have to use dummy nodes to construct onto which
+have to be ignored in later operations. (They couldn't be deleted, because the only
+way to delete the root node of a single-rooted tree is to delete all of the contents of
+the tree. You might be able to swap them with the real root node, but deleting the dummy
+after that would require relinking all of the child nodes of the real root before the
+dummy could be deleted, a complex operation.) On example problem is that the dummy nodes
+would get in the way if/when trees are combined. For instance, consider the expression
+trees in an Ada compiler. The default expressions of a procedure are likely to be stored
+in the symbol table; if constructed bottom-up (as they would be using a parser generator
+like YACC) they would have to have a dummy node at the top if the tree is single rooted.
+When the default expression is later spliced into a call tree, the dummy node would end
+up in the middle of the call tree. Care would have to be taken with every operation to
+avoid this happening.
+
+Even more annoying would be the complications for doing tree transformations. Consider
+again the expression trees in an Ada compiler. One common transformation is to change
+a call to "/=" to not "=". (This transformation has to wait until the compiler knows
+that the "/=" has a Boolean type, as otherwise it could just be an ordinary function
+call.) This means that a "not" node has to be inserted before the "=" node. This is
+easily done with the current package:
+
+    procedure Change_Not_Equals (Expr : in out Tree; Position : in Cursor) is
+        My_Not : Cursor;
+    begin
+        Insert_Child (Expr, Parent => Parent (Position), Before => No_Element,
+                      New_Item => (Kind => A_Not), Position => My_Not);
+        Splice_Subtree (Expr, Parent => My_Not, Before => No_Element,
+                        Position => Position);
+        Replace_Element (Position, New_Item => (Kind => Equals));
+    end Change_Not_Equals;
+
+However, this does not work for a single-rooted package if the Position happens to be
+at the root (as it would be for the condition of an if statement that consists of a
+single "/="). That's because inserting a second root is never allowed (else the tree
+would not be single rooted!). Thus the initial Insert_Child would fail.
+
+Instead, the code would have to resort to using unnatural operations like Swap and would
+have to move all of the children of the root node manually:
+
+        Insert_Child (Expr, Parent => Position, Before => No_Element,
+                      New_Item => (Kind => A_Not), Position => My_Not);
+        Swap (Position, My_Not);
+        Splice_Subtree (Expr, Parent => My_Not, Before => No_Element,
+                      Position => First_Child (Position));
+        Splice_Subtree (Expr, Parent => My_Not, Before => No_Element,
+                      Position => First_Child (Position));
+        Replace_Element (My_Not, New_Item => (Kind => Equals));
+
+This is more complex and much less natural than the initial code. (It would be much more
+complex if the number of children were not fixed as in this example - imagine a similar
+transformation on any function call.) It also ends up with the original cursor pointing
+to a different node than the original code (which might be significant).
+ 
+Because of all of these reasons, we prefer a tree with the ability to have orphans.
+
+
 Further ideas:
 
 * Should we have a function to get the maximum depth of the tree?
@@ -1375,6 +1490,26 @@
 
   These could be added by defining them using the above equivalences, if desired.
 
+* Should No_Parent be the same as No_Element? Or should it be a function?
+  The problem with No_Parent being the same as No_Element is that No_Element
+  does not include an indication of the container for which there is no parent.
+  That means that an extra Tree parameter is needed on operations that have to
+  be able to work on the list of orphan nodes: First_Child, Last_Child, Find,
+  Overall_Find, etc. (Any routine with an "in" mode Tree and a Cursor parameter
+  probably belongs in this list.) Even if we didn't have orphan nodes, it is
+  convinent that First_Child(Parent(Any_Element)) equals the node itself if
+  Any_Element has no siblings (which of course includes the root).
+
+  An alternative would be for No_Parent to be a function:
+     function No_Parent (Container : Tree) return Cursor;
+  In that case, those extra Tree parameters can be removed. However, since
+  No_Parent does not represent an element and does not have a value, we would
+  need additional wording to prevent reading/setting the value of No_Parent. We
+  also could not use it as a default parameter (but we aren't doing that currently).
+
+  Note that if we allowed reading and setting of the value of No_Parent, we then
+  would essentially be back to the single root model. We discussed the problems with
+  this model above.
 
 * 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.

Questions? Ask the ACAA Technical Agent