home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Crawly Crypt Collection 1
/
crawlyvol1.bin
/
program
/
books
/
progem
/
rsrctree.5
< prev
next >
Wrap
Text File
|
1986-11-01
|
25KB
|
484 lines
Permission to reprint or excerpt is granted only if the following line
appears at the top of the article:
ANTIC PUBLISHING INC., COPYRIGHT 1985. REPRINTED BY PERMISSION.
Professional GEM by Tim Oren
Column #5 - Resource Tree Structures
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!
>>>>>>>>>>>>>>>>>>>>>>>>>>> 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 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<