5 - Resource Tree Structures
*PROFESSIONAL GEM*
Part 5 -- Resource Tree Structures
By Tim Oren
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 OB_NEXT, OB_HEAD, and OB_TAIL, which is the order in which 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 OB_HEAD will point to its first (or "leftmost") "child", while the OB_TAIL will point to the last ("rightmost") of its offspring. The OB_NEXT pointer links the children together, with the OB_NEXT of the first pointing to the second, and so on, until the OB_NEXT 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 OB_NEXT 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 OB_HEAD is 1 and the OB_TAIL is 3, showing that there are at least two different children.
Following OB_HEAD down to the next line, we can trace through the OB_NEXT 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 OB_HEAD and OB_TAILs, indicating that they have no further offspring.
However, node three, the last child of the ROOT, does have the value 4 for both its OB_HEAD and OB_TAIL. 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 OB_NEXT leads immediately back to node three. Additionally, it has no further offspring because its OB_HEAD and OB_TAIL 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 rs_object in the download. You will see that the ROOT has an OB_HEAD of 1 and an OB_TAIL 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: OB_X, OB_Y, OB_WIDTH, and OB_HEIGHT. 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 OB_WIDTH of 10 and OB_HEIGHT of 2 (for instance) would define a screen area 10 characters wide and 2 high.
When the resource is read into memory with an rsrc_load 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 rsrc_load 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 OB_X and OB_Y 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 objc_offset, which returns the actual screen X and Y of an object. We can see now that simply loading the OB_X and OB_Y fields of the object does not suffice: they only give the offset relative to the parent object. So, objc_offset 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 OB_NEXT links from the chosen object. Whenever OB_NEXT points to an object whose OB_TAIL points right back to the same location, then the new node is another level, or "parent" in the tree, and objc_offset adds its OB_X and OB_Y into the running totals. When OB_NEXT becomes NIL, then the ROOT has been reached and the totals are the values to return. (By the way, remember that the OB_X and OB_Y of the ROOT are undefined until form_center has been called for the tree. They are shown as zeroes in the sample trees.)
We can also figure out objc_draw. 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 OB_HEAD), 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 objc_draw. Simply by changing the OB_X and/or OB_Y 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.)
Objc_draw also gives us an example of the uses of visual hierarchy. Recall that a clipping rectangle is specified when calling objc_draw. 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 objc_find. It starts out by setting its "object found" variable to NIL. It begins a "walk" through the entire object tree, following OB_HEAD and OB_NEXT links, and keeping a current X and Y, just like objc_draw.
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! Objc_find moves on to the OB_NEXT of the rejected object.
THOUGHT EXPERIMENTS
Thinking about the objc_find 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 objc_find 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 objc_find 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 objc_find 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 form_do must use objc_find, 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 OUR 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 map_tree(). 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 map_tree() 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 rsrc_gaddr. "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 map_tree() 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.
Map_tree() 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 OB_TAIL 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 OB_HEAD 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 OB_NEXT 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 map_tree(), you can deselect EVERY OBJECT in the tree by using map_tree(tree, ROOT, NIL, desel_obj); You must use a slightly modified version of desel_obj() (included in the download) which always returns TRUE. Be sure to define or declare desel_obj() in your code BEFORE making the map_tree call!
In future columns, I will return to map_tree() and show how it can be used for advanced techniques such as animated dialogs. In the meantime, experiment and enjoy!
GEMCL5.C
>>>>>>>>>>>>>>>>>>>>>>>>>>> Sample object trees <<<<<<<<<<<<<<<<<<<<<<<<
OBJECT rs_object[] = {
-1, 1, 3, G_BOX, NONE, OUTLINED, 0x21100L, 0,0, 18,12, /* Tree # 1 */
2, -1, -1, G_STRING, NONE, NORMAL, 0x0L, 3,1, 12,1,
3, -1, -1, G_BUTTON, 0x7, NORMAL, 0x1L, 5,9, 8,1,
0, 4, 4, G_BOX, NONE, NORMAL, 0xFF1172L, 3,3, 12,5,
3, -1, -1, G_IMAGE, LASTOB, NORMAL, 0x0L, 3,1, 6,3,
-1, 1, 6, G_BOX, NONE, OUTLINED, 0x21100L, 0,0, 23,12, /* Tree # 2 */
2, -1, -1, G_TEXT, NONE, NORMAL, 0x0L, 0,1, 23,1,
6, 3, 5, G_IBOX, NONE, NORMAL, 0x1100L, 6,3, 11,5,
4, -1, -1, G_BUTTON, 0x11, NORMAL, 0x5L, 0,0, 11,1,
5, -1, -1, G_BUTTON, 0x11, NORMAL, 0x6L, 0,2, 11,1,
2, -1, -1, G_BOXCHAR, 0x11, NORMAL, 0x43FF1400L, 0,4, 11,1,
0, -1, -1, G_BOXTEXT, 0x27, NORMAL, 0x1L, 5,9, 13,1,
-1, 1, 3, G_BOX, NONE, OUTLINED, 0x21100L, 0,0, 32,11, /* Tree # 3 */
2, -1, -1, G_ICON, NONE, NORMAL, 0x0L, 4,1, 6,4,
3, -1, -1, G_FTEXT, EDITABLE, NORMAL, 0x2L, 12,2, 14,1,
0, 4, 4, G_FBOXTEXT, 0xE, NORMAL, 0x3L, 3,5, 25,4,
3, -1, -1, G_ICON, LASTOB, NORMAL, 0x1L, 1,0, 6,4};
>>>>>>>>>>>>>>>>>>>>>>>>>> Object tree walk utility <<<<<<<<<<<<<<<<<<<<<<
VOID
map_tree(tree, this, last, routine)
LONG tree;
WORD this, last;
WORD (*routine)();
{
WORD tmp1;
tmp1 = this; /* Initialize to impossible value: */
/* TAIL won't point to self! */
/* Look until final node, or off */
/* the end of tree */
while (this != last && this != NIL)
/* Did we 'pop' into this node */
/* for the second time? */
if (LWGET(OB_TAIL(this)) != tmp1)
{
tmp1 = this; /* This is a new node */
this = NIL;
/* Apply operation, testing */
/* for rejection of sub-tree */
if ((*routine)(tree, tmp1))
this = LWGET(OB_HEAD(tmp1));
/* Subtree path not taken, */
/* so traverse right */
if (this == NIL)
this = LWGET(OB_NEXT(tmp1));
}
else /* Revisiting parent: */
/* No operation, move right */
{
tmp1 = this;
this = LWGET(OB_NEXT(tmp1));
}
}
>>>>>>>>>>>>>>>>>> Sample routine to use with map_tree() <<<<<<<<<<<<<<<
VOID
undo_obj(tree, which, bit) /* clear specified bit in object state */
LONG tree;
WORD which, bit;
{
WORD state;
state = LWGET(OB_STATE(which));
LWSET(OB_STATE(which), state & ~bit);
}
VOID
desel_obj(tree, which) /* turn off selected bit of spcfd object*/
LONG tree;
WORD which;
{
undo_obj(tree, which, SELECTED);
return (TRUE);
}
>>>>>>>>>>>>>>>>>>>>>>>>>> Sample .ICN Files <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
>>>>>>>>>> Save everything between >>><<< lines as CLOCK.ICN <<<<<<<<<<<<<<
/* GEM Icon Definition: */
#define ICON_W 0x0030
#define ICON_H 0x0018
#define DATASIZE 0x0048
UWORD clock[DATASIZE] =
{ 0x0000, 0x0000, 0x0000, 0x0000,
0x3FFC, 0x0000, 0x000F, 0xC003,
0xF000, 0x0078, 0x0180, 0x1E00,
0x0180, 0x0180, 0x0180, 0x0603,
0x0180, 0xC060, 0x1C00, 0x0006,
0x0038, 0x3000, 0x018C, 0x000C,
0x60C0, 0x0198, 0x0306, 0x6000,
0x01B0, 0x0006, 0x4000, 0x01E0,
0x0002, 0xC000, 0x01C0, 0x0003,
0xCFC0, 0x0180, 0x03F3, 0xC000,
0x0000, 0x0003, 0x4000, 0x0000,
0x0002, 0x6000, 0x0000, 0x0006,
0x60C0, 0x0000, 0x0306, 0x3000,
0x0000, 0x000C, 0x1C00, 0x0000,
0x0038, 0x0603, 0x0180, 0xC060,
0x0180, 0x0180, 0x0180, 0x0078,
0x0180, 0x1E00, 0x000F, 0xC003,
0xF000, 0x0000, 0x3FFC, 0x0000
};
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End of CLOCK.ICN <<<<<<<<<<<<<<<<<<<<<<<<<<
>>>>>>>>> Save everything between >>>><<<<< lines as CLOCKM.ICN <<<<<<<<<<
/* GEM Icon Definition: */
#define ICON_W 0x0030
#define ICON_H 0x0018
#define DATASIZE 0x0048
UWORD clockm[DATASIZE] =
{ 0x0000, 0x0000, 0x0000, 0x0000,
0x7FFE, 0x0000, 0x001F, 0xFFFF,
0xFC00, 0x00FF, 0xFFFF, 0xFF00,
0x03FF, 0xFFFF, 0xFFC0, 0x0FFF,
0xFFFF, 0xFFF0, 0x3FFF, 0xFFFF,
0xFFFC, 0x7FFF, 0xFFFF, 0xFFFE,
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
0xFFFF, 0xFFFF, 0xFFFF, 0x7FFF,
0xFFFF, 0xFFFE, 0x3FFF, 0xFFFF,
0xFFFC, 0x0FFF, 0xFFFF, 0xFFF0,
0x03FF, 0xFFFF, 0xFFC0, 0x00FF,
0xFFFF, 0xFF00, 0x001F, 0xFFFF,
0xF800, 0x0000, 0x7FFE, 0x0000
};
>>>>>>>>>>>>>>>>>>>>>>>>> End of CLOCKM.ICN <<<<<<<<<<<<<<<<<<<<<<<<<<<<<
