Inside Macintosh: Programmer's Guide to MacApp / Part 2 - Working With MacApp

Chapter 25 - Working With Lists and Iteration

Overview

A list is a data structure that stores a variable number of items of similar types. MacApp provides classes for creating and manipulating lists, allowing your application to use lists without having to implement the low-level details. MacApp's list classes and methods are shown in Figure 25-1.

Figure 25-1 List classes and methods

MacApp's list classes use a dynamic array model. Each item in a list has a unique index--you can access the items in a list by index or by standard list-traversal methods. The TSortedList class and its descendants can store only references to items that descend from the TObject class. Other MacApp-defined list classes, such as THandleList, store generic references that can be used to deal with a variety of developer-defined data types.

Iteration is a general-purpose mechanism for traversing the items in a list. MacApp provides the CIterator class and many specialized subclasses that operate on various types of lists. Iteration classes can traverse the items in a list without knowing the exact details of the data structures involved.

Figure 25-2 shows MacApp's iteration classes and methods.

Figure 25-2 Iteration classes and methods

Working With Lists of Objects

MacApp's TSortedList and TList classes provide extensive capabilities for working with lists of objects that descend from TObject. The TSortedList class includes methods and fields for processing an ordered list in which each element is a reference to an object. The TList class is a subclass of TSortedList that doesn't sort the objects. TList is used widely by MacApp, and it can be a valuable tool in your application as well.

Note

This section describes the TSortedList and TList classes, which refer to objects. The TSortedHandleList and THandleList provide virtually identical operations on handles.

Creating a List

MacApp provides the NewList routine to create and initialize a new TList object. The convenience routine NewAllocatedList lets you create a new TList object and at the same time specify the number of elements for which storage should be allocated. Each of these routines calls Failure if the list cannot be allocated.

Adding an Object to a List

You add an object to a TList with a method that inserts a reference to the specified object into the list. The insertion method calls Failure if an attempt is made to insert the reference at an index that is out of range.

The following insertion methods are available:

AtPut

The AtPut method replaces the object reference at the specified position with a reference to the new object, without freeing the old object.

Insert

For the TList class, the Insert method inserts the object reference at the end of the list. For the TSortedList class, the parent class of TList, Insert adds the object reference in sorted order, based on the list's Compare method.

InsertBefore

The InsertBefore method inserts the object reference before the reference at the specified index. If the index is equal to 1, the object reference is inserted at the head of the list.

InsertFirst

The InsertFirst method inserts the object reference at the front of the list and makes its index equal to 1.

InsertLast

The InsertLast method inserts the object reference at the end of the list.

MacApp's iteration mechanism, described beginning on page 576, allows you to iterate over a list correctly, even as items are added to the list.

Deleting an Object From a List

MacApp's list classes provide a number of methods for deleting an item from a list--not all are available in every list class:

AtDelete

The AtDelete method deletes the object reference at the specified index position.

Delete

The Delete method deletes the first reference to the object in the list. The object itself is not freed. Delete does nothing if the object is not found in the list.

DeleteAll

The DeleteAll method deletes every element from the list, but does not free any of the objects.

IMPORTANT

These methods delete a reference from the list--they do not free any memory occupied by the referred-to item itself. See the section "Freeing a List" (page 576) for more information on freeing a list and the items it references.

MacApp's iteration mechanism, described beginning on page 576, allows list iteration to proceed correctly, even as items are deleted from the list.

Finding an Object in a List

The TList class provides a number of methods for finding an object in a list. You can find an object that is the same as another object, or find a specific object by its position in the list.

The following methods are available:

At

The At method returns the object reference at the specified index.

First

The First method returns the first object reference in the list. It returns NULL if the list is empty.

Last

The Last method returns the last object reference in the list. It returns NULL if the list is empty.

GetEqualItemNo

The GetEqualItemNo method uses the object's CompareObject method to test for equality. This allows object equality to be determined by the object. An "equal" object may be found, even though the object being looked for is not, in fact, identical to the one found.

GetIdentityItemNo

The GetIdentityItemNo method uses the operator== function to compare items in the list to the item being searched for. The operator== function is overloaded in TObject, where it calls the IsEqual method, which does nothing in TObject. As a result, GetIdentityItemNo does nothing unless you override the IsEqual method.

IMPORTANT

To use the GetIdentityItemNo method, you must override the IsEqual method with a version that can identify equality between the items stored in your list.

Freeing a List

The TDynamicArray::Free method frees the memory occupied by a list itself but does not free the items referred to. You can call the FreeAll method to free each of the objects in a list of object references (TSortedList and descendants) or each of the handles in a list of handle references (TSortedHandleList and descendants). The list itself becomes empty but is not freed. You can call the FreeList method to free each object in the list and then free the list as well.

Iteration

Iteration allows you to traverse an array or list and perform some operation on each element. MacApp provides the CIterator class and several specialized subclasses for this purpose. For example, the CArrayIterator class iterates through an array of indexed items, the cMenuIterator class iterates through the menu handles in a menu list, the CBehaviorIterator class iterates through the behaviors that are associated with an event handler, and the CSubViewIterator class iterates through a list of subviews belonging to a view.

Each iterator class is defined for use with a specific kind of list (for example, CObjectIterator works with TSortedList) and can iterate correctly over the items in the list. This allows iteration to continue correctly, even as items are added to or deleted from a list. Iteration can be performed with both sorted and nonsorted lists and can be performed in either the forward or backward direction.

The most important base class for iterators is the CArrayIterator class. Like several of its subclasses, the CArrayIterator class provides multiple constructor methods for your convenience. The constructor methods of CArrayIterator call the initialization method, IArrayIterator, which sets the iterator's fields, including the following:

fCurrentIndex

The fCurrentIndex field specifies the current index during iteration.

fDynamicArray

The fDynamicArray field refers to the dynamic array for the list that is iterated through.

fHighBound

The fHighBound field is the upper bound for forward iteration through the list.

fIterateForward

The fIterateForward field is set to TRUE for forward iteration through the list and to FALSE for backward iteration.

fLowBound

The fLowBound field is the lower bound for backward iteration through the list.

The CArrayIterator class also provides methods for inserting and deleting items in the list during iteration so that the iteration process is not invalidated by the change to the list. It includes the following methods:

DeleteElementAt

The DeleteElementAt method adjusts the iteration index to account for the deleted element.

InsertElementBefore

The InsertElementBefore method adjusts the iteration index to account for the added element.