Professional GEM - Part V - Resource tree structures
Professional GEM Part IV 31
S�ST�TA�AY�Y T�TU�UN�NE�ED�D!�!
As well as answers to feedback questions, the next column
will discuss how GEM objects are linked to form trees, and how
to use AES calls and your own code to manipulate them for fun
and profit. In the following installment, we'll look at the VDI
raster operations (also known as "blit" functions).
Professional GEM 32
P�PA�AR�RT�T -�- V�V
R�Re�es�so�ou�ur�rc�ce�e T�Tr�re�ee�e S�St�tr�ru�uc�ct�tu�ur�re�es�s
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 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
Professional GEM Part V 33
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
Professional GEM Part V 34
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.
H�HO�OW�W G�GE�EM�M D�DO�OE�ES�S I�IT�T.�.
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
Professional GEM Part V 35
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
Professional GEM Part V 36
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.
T�TH�HO�OU�UG�GH�HT�T E�EX�XP�PE�ER�RI�IM�ME�EN�NT�TS�S
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.
Professional GEM Part V 37
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�A T�TR�RE�EE�EW�WA�AL�LK�KE�ER�R O�OF�F O�OU�UR�R O�OW�WN�N
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
Professional GEM Part V 38
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!
Back to Professional_GEM