Professional GEM - Part V - Resource tree structures
Introduction
This is the fifth issue of ST PROFESSIONAL GEM, concluding our trek through GEM dialogs and resources with a look at the internal structure of object trees. Also, I'll answer a number of questions of general interest which have been received via the ANTIC ONLINE FEEDBACK. As always, there is a download file associated with this column: GEMCL5.C, which you will find in DL3 of the new Atari 16-bit SIG (type GO PCS-58 or GO ATARI16).
Even if you have no immediate use for this issue's code, be sure to take the download anyway; some of the routines will be used in later articles.
In the last installment, we established that resources trees are pointed to by the tree index, and that they are composed of objects which contain pointers onward to other structures. However, we passed over the issue of linkage among the objects within a tree. It is now time to go back and cure this omission.
The technical term for the linkage scheme of an object tree is a "right-threaded binary tree". If you already know what this is, you can skim over the next few paragraphs. If you happen to have access to a copy of the book "FUNDAMENTAL ALGORITHMS", which is part of the series THE ART OF COMPUTER PROGRAMMING by Donald E. Knuth, you might want to read his excellent discussion of binary trees beginning on page 332.
For the following discussion, you should have a listing of the C image of a resource tree in front of you. For those who do not have the listing from the last column, I have included a fragment at the beginning of the download. Before we begin, I should warn you of one peculiarity of "computer trees": They grow upside-down! That is, when they are diagrammed or described, their root is at the top, and the "leaves" grow downward. You will see this both in the listing, and in the way the following discussion talks about moving through trees.
Each GEM object tree begins at its ROOT object, numbered zero, which is the object pointed at by the tree index. There are three link fields at the beginning of each object. They are called OBNEXT, OBHEAD, and OBTAIL, which is the order inwhich they appear.
Each of the links is shown as an index relative to the root of the current tree. This means that the link '0' would refer to the root of the tree, while '2' would indicate the object two lines below it. The special link -1 is called NIL, and means that there is no link in the given direction.
Each object, or node, in a tree may have "offspring" or nodes which are nested below it. If it does, then its OBHEAD will point to its first (or "leftmost") "child", while the OBTAIL will point to the last ("rightmost") of its offspring. The OBNEXT pointer links the children together, with the OBNEXT of the first pointing to the second, and so on, until the OBNEXT of the last finally points back to its parent, the object at which we started.
Remember that each of these children may in turn have offspring of their own, so that the original "parent" may have a large and complex collection of "descendents".
Let's look at the first tree in the download to see an example of this structure. The very first object is the ROOT. Note that its OBNEXT is NIL, meaning that there are no more objects in the tree: the ROOT is both the beginning and the end of the tree. In this case, the OBHEAD is 1 and the OBTAIL is 3, showing that there are at least two different children.
Following OBHEAD down to the next line, we can trace through the OBNEXT links (2, 3, 0) as they lead through a total of three children and back to the ROOT. You will notice that the first two children have NIL for the OBHEAD and OBTAILs, indicating that they have no further offspring.
However, node three, the last child of the ROOT, does have the value 4 for both its OBHEAD and OBTAIL. By this we can tell that it has one, and only one, offspring. Sure enough, when we look at node four, we see that its OBNEXT leads immediately back to node three. Additionally, it has no further offspring because its OBHEAD and OBTAIL are NIL.
You will find that object trees are always written out by the Resource Construction Set in "pre-order". (Again, see Knuth if you have a copy.) This means that the ROOT is always written first, then its offspring left to right. This rule is applied recursively, that is, we go down to the next level and write out each of these nodes, then THEIR children left to right, and so on.
For a further example, look at the next tree in rsobject in the download. You will see that the ROOT has an OBHEAD of 1 and an OBTAIL of 6, but that it actually has only three offspring (nodes 1, 2 and 6). We see that node 2 itself had children, and applying the rule given above, they were written out before continuing with the next child of the ROOT.
Why was this seemingly complex structure chosen for GEM? The reason has do with the tasks of drawing objects in their proper locations on the screen, and determining which object was "hit" when a mouse click is detected.
To find out how this works, we must look at four more fields found in each object: OBX, OBY, OBWIDTH, and OBHEIGHT. These fields are the last four on each line in the sample trees.
Each object in a tree "owns" a rectangle on the screen. These fields define that rectangle. When a resource is stored "outside" the program the fields are in character units, so that an object with OBWIDTH of 10 and OBHEIGHT of 2 (for instance) would define a screen area 10 characters wide and 2 high.
When the resource is read into memory with an rsrcload call, GEM multiplies the appropriate character dimension in pixels into each of these fields. In this way portability is achieved: the same resource file works for any of the ST's three resolutions. Knowing how rsrcload works, your code should treat these fields as pixel coordinates.
I have committed one oversimplification above. If an object is not created on a character boundary in the RCS, then the external storage method described will not work. In this case, the lower byte of each rectangle field is used to store the nearest character position, while the upper byte stores the pixel remainder to be added after the character size is multiplied in. Non-character-boundary objects may only be created in the "FREE" tree mode of the Resource Construction Set (also called "PANEL" in RCS 2.0). You should use them only in programs which will run in a single ST screen mode, because pixel coordinates are not portable between resolutions.
The first real secret of object rectangles is that each OBX and OBY is specified RELATIVE to the X and Y coordinate of its parent object within the tree. This is the first property we have seen that is actually "inherited" from level to level within the tree.
The second secret is more subtle: Every object's rectangle must be entirely contained within the rectangle of its parent. This principle goes by the names "bounding rectangles" or "visual hierarchy". We'll see in a moment how useful it is when detecting mouse/object collisions.
How GEM does it
Knowing these secrets, and the linkage structure of object trees, we can deduce how a number of the GEM operations must work. For instance, consider objcoffset, which returns the actual screen X and Y of an object. We can see now that simply loading the OBX and OBY fields of the object does not suffice: they only give the offset relative to the parent object. So, objcoffset must BEGIN with these values, and then work its way back up to the ROOT of the tree, adding in the offsets found at each level.
This can be done by following the OBNEXT links from the chosen object. Whenever OBNEXT points to an object whose OBTAIL points right back to the same location, then the new node is another level, or "parent" in the tree, and objcoffset adds its OBX and OBY into the running totals. When OBNEXT becomes NIL, then the ROOT has been reached and the totals are the values to return. (By the way, remember that the OBX and OBY of the ROOT are undefined until formcenter has been called for the tree. They are shown as zeroes in the sample trees.)
We can also figure out objcdraw. It works its way DOWN the tree, drawing each object as it comes to it. It, too, must keep a running X and Y variable, adding in object offsets as it descends tree levels (using OBHEAD), and subtracting them again as it returns from each level. Since the larger objects are nearer the ROOT, we can now see why they are drawn first, with smaller objects drawn later or "on top of" them.
If you write an application which needs to move portions of a dialog or screen with respect to each other, you can take advantage of inheritance of screen position in objcdraw. Simply by changing the OBX and/or OBY of an object, you can move it and its entire sub-tree to a new location in the dialog. For instance, changing the coordinates of the parent box of a set of radio buttons will cause all of the buttons to move along with it.
Objcdraw also gives us an example of the uses of visual hierarchy. Recall that a clipping rectangle is specified when calling objcdraw. At each level of the tree we know that all objects below are contained in the screen rectangle of the current object. If the current rectangle falls completely outside the specified clipping rectangle, we know immediately that we need not draw the object, or any of its descendents! This ability to ignore an entire subtree is called "trivial rejection".
Now it's rather easy to figure out objcfind. It starts out by setting its "object found" variable to NIL. It begins a "walk" through the entire object tree, following OBHEAD and OBNEXT links, and keeping a current X and Y, just like objcdraw.
At each node visited, it simply checks to see if the "mouse" X,Y specified in the call are inside the current object's rectangle. If they are, that object becomes the found object, and the tree walk continues with the object's offspring, and then siblings. Notice how this checking of offspring makes sure that a smaller object nested within, i.e., below, a larger object is found correctly.
If the mouse X,Y position is not within the object being checked, then by visual hierarchy it cannot be within any of its offspring, either. Trivial rejection wins again, and the entire sub-tree is skipped! Objcfind moves on to the OBNEXT of the rejected object.
Thought experiments
Thinking about the objcfind algorithm reveals some information about its performance, and a few tricks we may use in improving the appearance of dialogs and other object trees.
First consider the problem of a dialog which contains many objects. If we lay them all out "side-by-side", then they will all be immediate offspring of the ROOT object. In this situation, the trivial rejection method will gain nothing. The time objcfind takes to complete will vary linearly with the total number of objects. This is called an "Order N" process.
Suppose that instead we broke up the dialog into two areas with invisible boxes, then broke up each of these areas in a like fashion, and so on until we got down to the size of the individual selectable objects. The number of bottom level objects in this scheme is a power of two equal to the depth of the tree. Trivial rejection is used to its fullest in this case. It is called an "Order Log N" process, and is much more efficient for large numbers of objects.
In practice, the speed of the ST will allow you to ignore this distinction for most dialogs and other trees. But if you get into a situation when speed is critical in searching a large tree, remember that nesting objects can improve performance dramatically.
If you have been following closely, you may have also noticed a hole in the visual hierarchy rule. It says that all of a node's children must lie within its rectangle, but it does NOT guarantee that the children's rectangles will be disjoint, that is, not overlap one another. This peculiarity is the basis of several useful tricks.
First, remember that objcfind always tries to scan the entire tree. That is, it doesn't quit when it finds the first object on the given coordinates. As mentioned above, this normally guarantees that nested objects will be found. Consider, however, what happens when the mouse coordinates are on a point where two or more objects AT THE SAME LEVEL overlap: they will replace one another as the "found object" until objcfind returns with the one which is "last", that is, rightmost in the tree.
This quirk can be used to advantage in a number of cases. Suppose that you have in a dialog an image and a string which you would like to be selected together when either is clicked. Nesting within a common parent achieves nothing in this case. Instead, knowing that formdo must use objcfind, you could use our trick.
You have to know that the Resource Construction Set normally adds objects in a tree left to right, in the order in which you inserted them. You proceed to build the dialog in the following order: insert the image first, the string next, then carefully add an invisible box which is not nested within either, and size it to cover them both. Set the SELECTABLE attribute for the box, and the dialog manager will find it, and invert the whole area, when either the image or string is clicked.
By the way, remember that the SORT option in the RCS will change the order of an object's offspring. If you are going to try this trick, don't use SORT! It will undo all of your careful work.
A treewalker of out own
Since the GEM system gets so much mileage out of walking object trees, it seems reasonable that the same method should be useful in application programs. In the download you will find maptree(). As many LISP veterans might guess from the name, this code will traverse all or part of an object tree, applying a function to each node. It also allows the function to return a true/false value specifying whether the sub-tree below a particular node should be ignored. Let's examine maptree() in more detail as a final review of object tree structure.
First, look at the parameters. "tree" is the long address of the object tree of interest, as retrieved by rsrcgaddr. "this" is the node at which to begin the traverse, and "last" is the node at which to terminate.
In most cases, the beginning node will be ROOT, and the final value will be NIL. This will result in the entire tree being traversed. You may use other values, but be sure that you CAN get to "last" from "this" by following tree links! Although maptree() includes a safety check to prevent "running off" the tree, you could get some very strange results from incorrect parameters.
The declaration for the final parameter, "routine", makes use of C construct which may be new to some. It is a pointer to a subroutine which returns a WORD as a result.
Maptree() begins by initializing a temporary variable, tmp1, which is used to store the number of the last node visited. Since no node will follow itself, setting tmp1 to the starting node is safe.
The main loop of the routine simply repeats visiting a new node until the last value is reached, or the safety check for end of tree is satisfied.
At any node visited, we can be in one of two conditions. Either we are at a node which is "new", that is, not previously visited, or else we are returning to a parent node which has already been processed. We can detect the latter condition by comparing the last node visited (tmp1) with the OBTAIL pointer of the current node. If the node is "old", it is not processed a second time, we simply update tmp1 and continue.
If the node is new, we call "routine" to process it, sending the tree address and object number as parameters. If a FALSE is returned, we will ignore any subtree below this node. On a TRUE return, we load up the OBHEAD pointer and follow it if a subtree exists. (If you don't care about rejecting subtrees, simply remove the if condition.) Finally, if the new node had no subtree, or was rejected by "routine", we follow along its OBNEXT link to the next node.
A simple application of our new tool shows its power. From a previous column you may recall the tedium of deselecting every button inside a dialog after it was completed. Using maptree(), you can deselect EVERY OBJECT in the tree by using maptree(tree, ROOT, NIL, deselobj); You must use a slightly modified version of deselobj() (included in the download) which always returns TRUE. Be sure to define or declare deselobj() in your code BEFORE making the maptree call!
In future columns, I will return to maptree() and show how it can be used for advanced techniques such as animated dialogs. In the meantime, experiment and enjoy!