June 94 - Displaying Hierarchical Lists
Displaying Hierarchical Lists
MARTIN MINOW
Much of the data you manage on a Macintosh has a hierarchical nature. This article
shows how your application can provide a clear, coherent data organization with a
user-controlled display by using classic linked lists, storing the list data in handles,
and displaying it with the List Manager. A triangular button mechanism, similar to
that used in the Finder to open and close folders in list views, lets the user decide how
much data to view on the screen.
If your application makes its hierarchical data accessible but not overwhelming, it
will have an advantage over applications that provide only two alternatives -- "throw
it all on the screen" or "hide everything." You can find many examples of flexible
organization: The Finder presents file and folder information in a variety of display
formats revealing more or less information according to the user's own desires.
Document-based applications such as NewsWatcher provide a hierarchy of text
information. The JMP statistical application provides buttons that reveal more
detailed information about an analysis. Programming languages such as Frontier allow
the programmer to display as much of a module's code as is needed.
This article shows how to do the following:
• store hierarchical data in a linked list along with the information needed
to display it properly
• extend the List Manager by storing a button object in a List Manager cell
that controls how the data hierarchy is displayed
• build the data hierarchy and display it
• let the user manipulate the buttons to view more or less of the data
The accompanying code on this issue's CD includes a sample library that stores data,
displays it, and manages the buttons, and a simple application that uses the library.
The techniques described in the article are appropriate for displaying and organizing
moderate amounts of data; they're less useful for static data or large amounts of data
and are inefficient with small amounts of data.
Figure 1 shows a Finder-like window that was created with this library; the files
displayed are from the sample library. I've called the libraryTwistDown to emphasize
how the display acts when you click the buttons. The Finder development team calls the
buttonstriangular buttons .
Figure 1. Window created with TwistDown library
STORING DATA IN A LINKED LIST
There isn't much in this article on linked lists or handles; I assume you struggled with
"classical" list processing when you learned to program and have done enough
programming on the Macintosh to understand how handle-based storage operates. Keep
in mind that two kinds of lists are discussed here: linked lists and Macintosh List
Manager display lists. To keep confusion to a minimum,element refers to a component
of a linked list andcell refers to a component of a List Manager list. Note also that
linked lists contain the data, while the List Manager list only controls the appearance
of that data. A good understanding of the List Manager is needed to follow the code
examples later in the article. (For details on the List Manager, seeInside Macintosh:
More Macintosh Toolbox , or Inside Macintosh Volume IV.)
In the context of this article, a list element is a chunk of data, a few flags, and two
linkages. This section discusses the linkages, which connect list elements into
sequences and hierarchies, and the creation and disposal of list elements. The flags,
which simplify formatting the data, are discussed later in the section "Controlling Data
Appearance.
Figure 2 illustrates the linkages that connect list elements. The important thing to
remember about the hierarchical linked lists we're using is that any element may have
asuccessor -- the sibling element that follows it -- and adescendant -- a child
element that begins a lower level of the hierarchy. For example, a document outline
has a sequence of chapters (siblings) and each chapter has, as its descendants, a
sequence of sections.
In the sample code, each list element is stored in a handle. This allows the Memory
Manager to reorganize memory to store data efficiently. However, don't forget that the
application program is responsible for disposing of data that's no longer needed.
Two library functions manage the list elements: MakeTwistDownElement creates an
element and connects it to the list hierarchy and DisposeTwistDownElement deletes an
element along with its descendants and successors.
Figure 2. List element organization
CREATING A LIST ELEMENT
Listing 1 shows the definition of our element structure, TwistDownRecord. Each field
of this structure will be explained as it's encountered in the sample code.
Listing 1. TwistDownRecord
struct TwistDownRecord {
struct TwistDownRecord **nextElement; /* -> successor element */
struct TwistDownRecord **subElement; /* -> descendant element */
short indentLevel; /* Indentation depth */
unsigned short flag; /* Control flags */
unsigned short dataLength; /* Actual data length */
unsigned char data[1]; /* Data to display */
};
typedef struct TwistDownRecord TwistDownRecord,
*TwistDownPtr, **TwistDownHandle;
MakeTwistDownElement (Listing 2) is called with the data to store in the element and
a handle to its predecessor. The predecessor is either NULL or the previous (elder)
sibling element. For example, when creating element 3 in the list shown in Figure 2,
the previous element is element 1.
TwistDownRecord is a variable-length structure and NewHandle creates an instance
that's large enough to hold the caller's data record. The structure definition, however,
contains one bit of trickery that's required by the ANSI C standard -- it must specify
at least one byte for the data [] placeholder. This is why the parameter to NewHandle
adjusts the handle size to eliminate the extra byte.
DISPOSING OF A LIST ELEMENT
The DisposeTwistDownHandle function disposes of a list element and then disposes of
its descendant and successor lists. To dispose of an entire list, call this function with
the first list element.
A simplified version of DisposeTwistDownHandle is shown in Listing 3. The library
implementation allows the application developer to specify a function that's called
when disposing of each element in the list. This is needed if an application has to store
complex structures -- themselves containing Ptr or Handle references -- in a
TwistDownHandle.
Listing 2. MakeTwistDownElement
OSErr MakeTwistDownElement(TwistDownHandle previousElement,
short indentLevel,
unsigned short dataLength,
Ptr dataPtr,
TwistDownHandle *result)
{
TwistDownHandle twistDownHandle;
twistDownHandle =
(TwistDownHandle) NewHandle(sizeof(TwistDownRecord)
- sizeof(unsigned char) + dataLength);
*result = twistDownHandle;
if (twistDownHandle != NULL) {
if (previousElement != NULL)
(**previousElement).nextElement = twistDownHandle;
(**twistDownHandle).nextElement = NULL;
(**twistDownHandle).subElement = NULL;
(**twistDownHandle).indentLevel = indentLevel;
(**twistDownHandle).flag = 0;
(**twistDownHandle).dataLength = dataLength;
if (dataPtr != NULL)
BlockMove(dataPtr, (**twistDownHandle).data, dataLength);
}
return (MemError());
}
Listing 3. DisposeTwistDownHandle
void DisposeTwistDownHandle(TwistDownHandle twistDownHandle)
{
TwistDownHandle nextElement, subElement;
while (twistDownHandle != NULL) {
nextElement = (**twistDownHandle).nextElement;
subElement = (**twistDownHandle).subElement;
DisposeHandle((Handle) twistDownHandle);
if (subElement != NULL)
DisposeTwistDownHandle(subElement);
twistDownHandle = nextElement;
}
}
Note that DisposeTwistDownHandle is a recursive function; it calls itself to dispose of
the descendants of a hierarchy. If it's called with the list shown in Figure 2, it disposes
of elements in the order 1, 2, and 3.
Using recursion simplifies the list-management algorithms in the TwistDown
function library. However, it's not without its pitfalls in the real world. Each time a
function such as DisposeTwistDownHandle encounters a subelement list, it calls itself
to dispose of that list, and each of these calls uses stack space. While this isn't usually
a problem for applications, you should avoid recursive algorithms in device drivers or
other nonapplication code segments because they must work within the constraints of
some other application's stack.*
CONTROLLING DATA APPEARANCE
Once the data is organized as a hierarchical list, the application could simply display
the whole list by just storing handles to the list elements in List Manager cells.
However, if your application lets the user control how much of the data is displayed,
there must be a way for the user to browse through the data and to specify which
elements are visible and which are hidden.
A familiar mechanism for doing this exists in the Finder, where small buttons indicate
which cells have subhierarchies and whether the subhierarchy is visible. These
triangular buttons have two stable states: one for closed (invisible) hierarchies and
one for open (visible) hierarchies. There are also three transient states: an
intermediate button is displayed briefly when the user clicks a triangular button to
change between the open and closed states; and the closed and open buttons are drawn
filled when a mouse-down event is located on the button. To manage these buttons and
the display of visible data, each list element needs a few flags and an indentation
variable. These are stored in the TwistDownRecord structure.
The indentation variable -- indentLevel -- specifies the hierarchical depth of an
element and is used to display sublists so that the data for an element appears under its
parent, but indented to show its place in the hierarchy.
The bits in the flag field are used to record the record's state and to communicate
between the application and the List Manager's list definition function (LDEF):
/* These are the values that can appear in the flag word. */
#define kHasTwistDown 0x0001 /* This element has a sublist */
#define kShowSublist 0x0002 /* Display the sublist content */
#define kOldShowSublist 0x0004 /* Saved kShowSublist state */
#define kSelectedElement 0x0008 /* Copy "selected" from list */
#define kDrawButtonFilled 0x0010 /* Signal "mouseDown" in button */
#define kOnlyRedrawButton 0x0020 /* Signal "tracking mouse" */
#define kDrawIntermediate 0x0040 /* Draw the animation polygon */
#define kEraseButtonArea 0x0080 /* Need complete button redraw */
The flag field is defined as an unsigned short with explicitly defined bits rather
than as a bitfield, which would have made the program slightly easier to read.
However, the ANSI C standard doesn't specify how the bits in a bitfield are arranged,
and different compilers are free to choose their own organization of the bits. This
means that if you write parts of your code using several compilers, or distribute
modules in object form for others to use, you may cause a debugging nightmare. This is
especially true if you use bitfields to construct data records that are sent in network
messages between different systems. The flag bits could have been defined as an enum,
but this can also cause portability problems. Using explicit bit definitions will also
make it easier to convert your code to run on the Power Macintosh. *
The first four flag bits have the following meanings:
• kHasTwistDown is set if the element should have a triangular button when
it's drawn. While you might assume that the existence of a non-null
subElement pointer would be sufficient, the Finder illustrates a better design:
it displays triangular buttons for all folders, even if there are no files in a
folder. This immediately tells the user that the line on the display represents
a folder, rather than a file.
• kShowSublist is set if the sublist should be displayed. This is normally
controlled by the user clicking a triangular button, which changes the
kShowSublist state.
• kOldShowSublist is used to save the old kShowSublist setting in case you
need to temporarily change the display hierarchy. This lets you undo a display