GEMini Atari/GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso/files/program/progem/gem5.asc

Text File | 1987-10-10 | 16.9 KB | 335 lines

                        *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!