Volume Number: 15 (1999)
Issue Number: 2
Column Tag: PowerPlant Workshop

Arrays, Iterators, and Comparators... Oh my!

by John C. Daub, Austin, Texas USA

A look at PowerPlant's Array Classes

No matter what you do in life, sooner or later you have to deal with data - it's unavoidable. This is certainly true in software development. We need ways to read and write data, make it persistent, add and remove, examine, and otherwise manipulate information. Without data, there's not much point nor ability to do what we're doing. Since the manipulation of data is so vital to software, it would stand to reason that providing reusable means to work with data would be welcomed by software developers.

There are many different forms of data manipulators available. There are end-user solutions like FileMaker, database engines such as NeoAccess and OOFILE, and simpler solutions such as the C++ Standard Library containers and PowerPlant's Array Classes. If you haven't guessed, that's what this article is about - PowerPlant's Array Classes. These classes provide PowerPlant and you with a Mac-savvy means of working with lists of data. If you look through the PowerPlant sources themselves, you'll see the Array classes used in many key places; chances are good you'll find yourself using them throughout your own code as well. The Array Classes certainly don't fit the needs of every situation, but in order to locate the place for them in your "Programmer's Toolchest" read on to see what they have to offer.

The main purpose of the Array Classes is to provide a means for storing and working with lists of data. The Array Classes are comprised of three components: Arrays, Iterators, and Comparators. Arrays are an ordered collection of items. Iterators are a means of sequentially traversing Arrays. Comparators are a means for comparing Array elements. Used together, these components provide you with a powerful and easy to use data management system - again, it's what PowerPlant uses itself (I'll provide some examples of this throughout the article). Figure 1 shows the classes and class hierarchy for the Array Classes.

One item to note is that a couple classes listed above, LSharableArray and LFastArrayIterator, are not found in the Array Classes folder within the PowerPlant folder of the Metrowerks CodeWarrior Professional installation. These classes came from the Metrowerks Constructor sourcebase, and consequently are found within the Constructor Additions folder in the PowerPlant folder (at least as of this writing, using CodeWarrior Pro 4). Nevertheless, they are still available for your use and worth discussing in this article.

As you might guess, Arrays are the core of the Array Classes, and LArray is the central base class. LArray is an ordered sequence of fixed-sized items, not unlike a regular C/C++ array. However unlike a regular C/C++ array whose size is static and determined at compile time, an LArray is dynamic - you can add and remove items at runtime. This is accomplished by storing the Array data within a Handle, which is resized as data is added or removed using only as much memory as is required at the time. An LArray is also unlike a regular array in that an LArray is one-based and not zero-based; that is, the first item is at index one and not index zero. Other differences between regular arrays and LArray is that an LArray can be iterated and sorted. We'll discuss iteration and sorting later in the article.

One additional item of note is what can be stored within an LArray. The answer is: almost anything. When you add an item to an LArray you do not store that item itself but rather a copy of that item (deep in the bowels of LArray the internal storage Handle is resized and BlockMoveData is called to actually add/copy the item into the LArray). Due to this storage mechanism, you can store just about any type of data: built in data types like char, int, long; other simple data types like Handle, Ptr, OSType; simple data structures like Point, Rect, SPaneInfo; and pointers from NewPtr, malloc, or new/new[]. What cannot be stored are more complex data such as C++ objects. Objects cannot be stored for a few reasons.

First, recall that the internal storage of an LArray is a Handle, which is a relocatable block of memory. C++ objects have some invisible structures attached to it to take care of housekeeping details, such as vtables. These structures contain pointers to specific areas in memory where your object is. If you store your object within a Handle and the Memory Manager moves that Handle, your vtables do not move and update with the object. The vtables are now invalid and chances are good that next time you try to access members of that object you'll crash or have some other sort of unpredictable behavior. Second, it's generally considered evil to perform bitwise copies of objects (Cline 1995, FAQ 208), and that is exactly what BlockMoveData does. This is why we have copy constructors and assignment operators, but unfortunately there is no way to invoke those within LArray's copy mechanisms. But even if they could be invoked, or if there was a case where the bitwise copy would be ok (there certainly are instances of this), you still have problem one to contend with. If you need to store objects in an LArray, you should instead store pointers to the objects. LArray's can only store plain old datatypes (PODs).

Basic Functionality

If you haven't yet, and you have the ability to do so, open a copy of LArray.cp (I'm using the version from CodeWarrior Pro 4). You'll notice the class is fairly sizable, but it's certainly not unmanagable. Most of the functionality can broken down into a few logical groups, and the ones you'll use most frequently will be the manipulators and the inspectors.

The manipulators allow you to add, remove, and change Array items. To add an item to an Array you can use AddItem() or InsertItemsAt(). AddItem() allows you to add one item to the Array. InsertItemsAt() allows you to insert one or more items into the Array at a specified index; all inserted items are set to the same value, and are inserted contiguously. The difference between AddItem() and InsertItemsAt(), aside from the ability to insert one item versus multiple items, is if the Array is unsorted, AddItem() adds to the end of the Array (if the Array is sorted, AddItem() actually calls through to InsertItemsAt(), and the item is added wherever the sort places it). The bonus of AddItem() is a speed gain as it does not have to contend with index range checking nor the possible overhead of maintaining a sorted Array. If your Array doesn't bother with sorting and/or adding to the end is acceptable, you'll probably want to use AddItem() over InsertItemsAt() for the speed gain.

Since you can add items, you also need to remove items. LArray provides the RemoveItemsAt(), RemoveAllItemsAfter(), and Remove() methods for just this purpose. RemoveItemsAt() removes a specified number of items starting at a given index. RemoveAllItemsAfter() is a variation on RemoveItemsAt() that will remove all items located after the specified index. Finally, given a particular item, Remove() removes that item from the Array.

The remaining manipulators allow you to modify existing Array items. AssignItemsAt() allows you to assign a (new) value to the item(s) you specify. SwapItems() allows you to exchange the values of two items within an unsorted Array. MoveItem() moves an item within an unsorted Array from one position to another. It is important to note that MoveItem() works as if you first removed the item and then inserted it - the index is relative to the Array, not the items within the Array. To illustrate, suppose you have an Array containing five items and you wish to move the item at index two to index four:

   theArray->MoveItem(2, 4);

The action is simple to do, but the results might not be quite what you expect. Before the move your Array might have looked like this:

   Index:         1   2   3   4   5
   Item:          A   B   C   D   E

You might expect after the move for your Array to look like this:

   Index:         1   2   3   4   5
   Item:          A   C   B   D   E

If MoveItem() was item-based, this would be true. It would have taken the second item, "B", and placed it where the fourth item, "D", was, bumping up those after, "D" and "E". But notice a resulting effect: "B" is not at index four but rather index three! This could certainly lead to unexpected behavior as the result doesn't quite match the original intent. Instead, MoveItem() is index based so after the move your Array would actually look like this:

   Index:         1   2   3   4   5
   Item:          A   C   D   B   E

Now item two has been moved to become item four. It was as if item two was first removed and the Array adjusted from that removal, the itermediate step leaving the Array looking like this:

   Index:         1   2   3   4
   Item:          A   C   D   E

And then the item inserted at the new index (four). MoveItem() doesn't actually remove then insert the item, but that's the essence of how the method works.

The other group of methods you'll commonly use will be the inspectors. The inspectors enable you to obtain information about items in the Array or the Array itself. ValidIndex() returns if the given index is valid for the Array or not. GetItemSize() returns the size of the requested item. GetCount() returns the number of items in the Array. FetchIndexOf() returns the index of the given item in the Array, if the item is in the Array. And probably the most commonly used inspector is FetchItemAt(), which returns to you a copy of the item at the given index.

LArray also contains many other methods. The majority of these methods are protected methods used internally by LArray to do the voodoo that it do so well, but there are a few other public methods such as: Sort(), to sort the Array; and GetComparator() and SetComparator(), to access the Array's Comparator object; and of course the various constructors and destructor for the class. Although you do not need to worry yourself with these internal methods to begin using LArray, you should eventually familiarize yourself with how all of the methods work so you can gain a complete and thorough understanding of how LArray operates.

LArray Subclasses

Looking back at Figure 1, you see there are five subclasses of LArray provided by Metrowerks in the PowerPlant distribution: TArray, LVariableArray, LRunArray, TRunArray, and LSharableArray.

TArray is a simple template wrapper class that inherits from LArray. Looking in TArray.h, you'll notice only a handful of LArray methods are overridden, and then only those public methods that take items/data as an argument. This is done to provide you with a degree of typesafety in using the Array classes. Notice the LArray methods that take items/data as an argument pass the argument as a void*; this is a necessary evil to allow LArray to store various types of data and be a general-purpose class. However, the use of void* not typesafe and prone to errors. By using TArray you are able to specify the type of data stored within the Array and can avoid errors that can stem from using mismatched types. Furthermore, since the type is known you can pass the item/data by reference instead of by address, which some would contend is a "more C++" way to pass arguments. Moreover, since type information is known you do not need to worry about passing the size of the data since TArray handles that for you. Look again at the overrides in TArray and you'll notice they're actually overloads. There is one side-effect to TArray caused by these overloads/overrides, but it's nothing to worry about. Strictly speaking the TArray methods are hiding the inherited virtual functions from LArray, and if your compiler can notify you of such situations (the Metrowerks C/C++ compilers can do this) then you will receive some compiler warnings to that effect. There is no need to worry about these warnings as the design of TArray will work correctly. You can suppress the warnings by turning off that compiler warning globally (e.g. turn it off in the compiler's preference panel) or on a case by case basis, which is what PowerPlant itself does. Look at the top of any PowerPlant header file for a class that uses a TArray, such as LView.h. You should see a declaration similar to this:

   #pragma warn_hidevirtual off
      template class TArray<LPane*>;
   #pragma warn_hidevirtual reset

The #pragma will temporarily turn off the compiler warning as you explicitly instantiate the template class allowing your code to compile cleanly and quietly.

A feature that TArray has that LArray does not is operator[]. operator[] allows your Array to function, in terms of notation, just like a regular C/C++ array. Don't forget that PowerPlant Array's are one-based, so although the notation might make it look like a C/C++ array, it's still a PowerPlant Array. The benefit of operator[] is a huge speed gain over inspectors like FetchItemAt(), but in exchange for speed you are returned a pointer to the data within the internal storage buffer (instead of a copy) and there is no range checking performed on the given index. These trade-offs can be viewed as positives and/or negatives for using operator[]; it just depends upon the context for use. But regardless of how you view TArray::operator[], tread carefully to avoid any problems.

LVariableArray is similar to LArray in almost every way except instead of storing fixed-sized items, LVariableArray stores items of varying size (but all items must still be of the same type). Probably one of the most popular uses for LVariableArray is to store strings. Did you ever notice that Resources that include a string, like a STR# resource, tend to be a lot smaller than the Str255 you store the string in? This is because in those resources the string is a packed string, storing only what is needed to represent the string: the string characters and the length byte, no more, no less. Storing strings in this manner is much more space efficient than always storing an entire 256 bytes. This is why LVariableArray is well-suited to storing strings - store just what you need and don't waste any space because the class does not have to hold items of a fixed size (your strings can be of whatever length they need to be). You can see LVariableArray used in such places as LGATabsControlImp and LPageController to store the tab titles, and LTextArray and LTextMultiArray which are classes designed specifically for storing strings.

LRunArray is a variant of LArray where consecutive items of the same value are stored as a single entry. That is, if the first ten items in your RunArray are identical, only one instance of that item's data is actually stored within the RunArray. However, you do not need to keep track of this information, LRunArray handles it for you. You use an LRunArray exactly like you use an LArray: if you wish to obtain the eighth item, FetchItemAt(8, &myData) and the eighth item will be returned. The main purpose of LRunArray is an attempt to be more memory efficient and faster than a regular LArray by collapsing like items. But this will only hold true the more items there are and the less runs you have. LRunArray uses a linear search to find the run containing an item, thus the more runs you have the slower it can become (at least compared to the constant LArray). When you have needs that can fit within the bounds and design of LRunArray, it can certainly be a beneficial class to use due to the reduced memory footprint. As an example, LTableMultiGeometry uses LRunArray to manage the heights of the table rows and widths of the table columns. TRunArray is to LRunArray what TArray is to LArray, a template version of LRunArray.

LSharableArray is a special purpose Array class. It's designed to hold a list of LSharable pointers (LSharable is PowerPlant's mixin class for reference counted objects). Why this special class instead of perhaps a TArray<LSharable*>? LSharableArray increments the use count of the sharable while it is in the Array so the Array is not left with any dangling pointers. A little extra housekeeping but certainly welcome functionality.

With all that data stored in your Array, you of course want some way to access that data. Using an Array inspector such as FetchItemAt() of course works, but there are times when you wish to walk your Array from one point to another, perhaps looking for a specific element or perhaps performing an operation on or with elements in the Array. This is where Iterators come in to play. An Iterator provides you with a means of sequentially traversing an Array. Again you could use a loop and FetchItemAt() to traverse your Array, but consider the following situation:

   {
      // TArray<FooData> *myTArray;
      UInt32      numItems = myTArray->GetCount();
   
      for (UInt32 ii = 1; ii <= numItems; ii++) {
         FooData   myFooData;
         myTArray->FetchItemAt(ii, myFooData);
   
            // targetData is a const FooData that we're
            // looking for.
         if (myFooData == targetData) {
            myTArray->Remove(targetData);
         }
      }
   }

What would happen in the above situation if targetData was found? It would of course be removed from the Array. After removing the item from the Array, the Array is now one less and numItems is no longer valid. When ii == numItems, you could be in for some unexpected results! And if there happened to be more than one instance of targetData in the Array, you could be in for trouble a lot sooner. Instead, try using an Iterator:

   {
                     // myTArray is the same here as above
      TArrayIterator<FooData>      iterator(*myTArray);
   
      FooData   myFooData;
      while (iterator.Next(myFooData)) {
         if (myFooData == targetData) {
            myTArray->Remove(targetData);
         }
      }
   }

The two blocks of code perform the same function, but the latter version is savvier to the Array changing underneath it. The Iterators are not locked to certain numbers as the first example is, but rather to concepts such as "Next" and "Previous" to walk the Array. Additionally, an Array can have multiple Iterators (but an Iterator only one Array). A variant of the above examples could be searching the Array looking for and removing duplicate entries. That code could look something like this (yes, this is based directly upon the example from the PowerPlant Book):

   {
      TArrayIterator<FooData>      outerIter(*myTArray);
      FooData   myFooData;
      while (outerIter.Next(myFooData)) {
         TArrayIterator<FooData>      searcher(*myTArray,
                              myTArray->FetchIndexOf(myFooData));

         FooData   targetData;
         while (searcher.Next(targetData)) {
            if(myFooData == targetData) {
               myTArray->Remove(targetData);
            }
         }
      }
   }

The outerIter walks the Array obtaining items. For each item obtained, look to see if another instance of that item exists in the Array, starting the search from the item after the current search target. If a duplicate is found, remove it, and continue looking for and removing duplicates until the end of the Array is reached. At that time, move to the next item in the Array (note, not necessarily the "second" item in the original Array) and repeat the process until outerIter reaches the end of the Array. The Iterators can be nested and are savvy to the Array changing; in fact, the Array could disappear completely and an Iterator would do the right thing.

Iterator Classes

The above introduction to Iterators demonstrated much of the functionality that iterators have (they are fairly simple objects). LArrayIterator is the base Iterator class and contains the functionality common to all PowerPlant Iterators. Current() allows you to obtain a copy of the current item. Next() returns a copy of the next item, and Previous() a copy of the previous item. These methods actually return a copy the item as an "out" argument and have a Boolean for the return value. This Boolean specifies if the Iterator was successful or not in obtaining the requested item, and is why Next() is called within the conditional statement of the while loops of the above examples. There are also "PtrTo" variants of the accessors: PtrToCurrent(), PtrToNext(), and PtrToPrevious(). They do the same as their non-PtrTo counterparts but instead of returning a copy of the item they return a pointer to the item as stored within the Array's internal storage Handle. Typically you'll want to get a copy of the item if the Array could change while iterating. Aside from a few internal housekeeping methods and ResetTo() (which (re)sets the Current item to the given index), that's all there is to Iterators. But even as simple as this mechanism might be, the utility is great and necessary. For instance, this is how LView::Draw() recursively iterates over its subpanes to draw your user-interface elements; or how LPeriodicals idle and repeat; or LBroadcasters send their message to their Array of LListeners; or how an LCommander walks its subcommanders. Though the mechanism is simple, PowerPlant could not exist without it.

LArrayIterator is the base Iterator class, and as Figure 1 illustrates, there are a few subclasses provided. TArrayIterator follows the same concept as TArray - a templated version of LArrayIterator. LLockedArrayIterator is a simple subclass of LArrayIterator in which the constructor locks the Array and the destructor unlocks the Array. You can probably guess what TLockedArrayIterator does. The functionality provided by LLockedArrayIterator is useful if your Array will not change while iterating and you wish to access pointer to Array elements instead of copies. You do not want to use LLockedArrayIterator if your Array could change during iteration as locking the Array could prevent adequate resizing of the internal storage Handle (the same set of limitations that exist when locking any Mac OS Memory Manager Handle). LFastArrayIterator is a version of LArrayIterator that you can use to gain a little speed if you know your Array will not change while iterating.

One final member of the Iterator group is not an Iterator at all. StArrayLocker (located in LArray.h) is a stack-based class whose constructor locks the given Array and whose destructor unlocks the Array. This is very useful in iteration if you wish to directly access Array elements by pointer (alternatively you can use LLockedArrayIterator). StArrayLocker can also be used any time you need to lock an Array and desire exception-safety to ensure the Array is always properly unlocked.

The third and final component of the Array Classes are Comparators. Comparators are objects that know how to compare two objects or data structures. They can be use independent of the rest of the Array classes, but their use within the Array classes is their primary purpose as the Comparator is used when searching or sorting an Array. You can assign a Comparator to an LArray when you create the Array, or call LArray::SetComparator() after Array creation. If the Array is to be kept sorted or you force a sort by calling LArray::Sort(), the Comparator is used to determine the ordering of the items by comparing two items as the sort algorithm executes.

LComparator only has a few member functions. Compare() is the main function that subclasses will implement to compare items. Compare() will return a value less than zero if item one is less than item two, zero if the items are equal, and a value greater than zero if item one is greater than item two. The comparison is generally a bitwise comparison (as is the default implementation of LComparator::Compare()), but you are welcome to perform the comparison of data as you wish in your subclasses so long as you maintain the proper logic when returning the result of the compare. IsEqualTo() returns true or false if the two items are equal to each other or not. LComparator also has CompareToKey() and IsEqualToKey() methods which behave like their non-Key counterparts except the comparison is against a given key instead of another item. Rounding out LComparator is Clone(), which returns a copy of the Comparator object, and the static GetComparator() which returns the single instance of the Comparator object creating it if necessary.

LLongComparator is a subclass of LComparator which compares items as 32-bit integer values instead of the default bitwise comparison. LLongComparator is used by URegistrar and UValidPPob since the ClassIDTs in the class registration table are 32-bit values.

That's a good question. You've seen what makes up the PowerPlant Array classes, not only the three major components of Arrays, Iterators, and Comparators, but also what makes up each of those components, both subclasses and member functions. But how do you actually put all of this stuff to use? One of the nifty features introduced in Mac OS 8.5 was Sherlock. I'm sure by the time you're reading this article you've at least heard about, if not used, Sherlock, but in case you haven't just consider it a really neat Find application. I do not know how Sherlock stores its data, and the following illustration is not meant to imply what Sherlock does or not not use for data storage. I just wish to use the concept of Sherlock's (or any Find application's) Results window to illustrate how one could use the Array Classes.

While performing your search, you need to store found items and a TArray can provide you with that storage. As you find an item you add it to the list with a call to TArray::AddItem(), as speed is important and sorting can be deferred until later. After all items have been found, perhaps you have an option in your application to remove duplicate entries (perhaps not needed for files, but what if you're searching websites?). Using a TArrayIterator as was done in previous examples should provide you with the way to remove those duplicates. Now your data is almost ready for display, but since your Results window can display the data in many ways (sorted by name, date, URL, order of magnitude, and from A-Z or Z-A) you need to sort your data accordingly. So you call TArray::SetComparator() passing a pointer to your CNameComparator object, followed by a call to TArray::Sort(), which sorts your Array based upon the names of the items within your Array. Finally you display your window and the user is quite happy to see their results. But unfortunately their not quite happy enough because they want to see the results sorted by date. They click on the column header for Date, to which you respond by again calling TArray::SetComparator(), but this time you pass a pointer to your CDateComparator object followed by another Sort() and a refresh of your window. Now the search results are displayed by date, the user is happy, and hopefully you've seen what the Array Classes can do for you.

Among other things, the C++ standard library provides a set of eleven container classes (bitset, deque, list, map, multimap, multiset, priority_queue, queue, set, stack, and vector). A container is a unit that can hold values, and by that definition the Array components of the PowerPlant Array classes (LArray, LRunArray, LSharableArray, LVariableArray, TArray, TRunArray) are containers as well. So why would you want to use a Standard Library container instead of a PowerPlant container, or vice versa?

First, there is nothing that says you must use one over the other. Each container class has specific strengths, weaknesses, form, and function, and often your needs will dictate what container will perform better in the given situation. Picking the most appropriate tool for the task at hand is a good, general rule to follow. But there are certainly some differences between the two types of containers that you should be aware of:

• LArray is Mac-savvy by virtue of being Handle-based. The C++ standard library containers are pointer-based.
• The Standard Library containers can store objects. LArray can only store pointers to objects.
• PowerPlant uses the Array Classes internally, so unless you have specific needs for Standard Library containers, avoiding their use can reduce the size of your end binary (the Array Classes are already linked in, so just tap into that existing resource).
• The Standard Library is quite portable to other platforms. PowerPlant requires the Mac OS API.
• The Array Classes are more suited for working within a PowerPlant and Mac environment, with classes such as LSharableArray and LVariableArray.

There is no cut-and-dry answer as to which type of container you should use, so just keep adding to your toolset. As problems arise, you'll be able to find the best solution to the problem at hand.

With data being central to software it is important that we have ways to manage that data. All application frameworks worth their salt provide tools for working with data, and PowerPlant is no exception with its Array Classes. The combination of classes for dynamic lists (Arrays), classes to walk those lists (Iterators), and classes to compare and order the data within those lists (Comparators) provides you with an effective set of tools for data manipulation.

If you'd like to learn more about the Array Classes, look on your CodeWarrior Professional CD's. On the Tools CD you can look at the PowerPlant code and see how PowerPlant itself uses the Array Classes. On the Reference CD, demo applications like the Array Demo and Muscle Demo should provide you with a good starting point and workarea for tinkering and experimentation. And of course don't forget the official Metrowerks documentation for PowerPlant, both the PowerPlant Book and PowerPlant Reference (also known as PowerPlant Revealed).

Until next time... Happy programming!

• Cline, Marshall P. & Greg A. Lomow. C++ FAQs: Frequently Asked Questions. Addison-Wesley Publishing Co., Inc., Reading, Massachusetts. 1995.
• Metrowerks Corporation. PowerPlant Book. 1998.
• Metrowerks Corporation. PowerPlant Reference. 1998.
• Prata, Stephen. Mitchell Waite Signature Series: C++ Primer Plus. 3rd ed. Waite Group Press, Corte Madera, California. 1998.
• Stroustrup, Bjarne. The C++ Programming Language. 3rd edn. Addison-Wesley Publishing Company, Reading, Massachusetts. 1997.

John C. Daub is one of Metrowerks Corporation's PowerPlant engineers. In addition to enjoying framework authoring, John enjoys a good cartoon at any possible opportunity. He'd like to thank Greg Dow and Howard Hinnant for their help. You can reach John via email at hsoi@metrowerks.com.