Interfaces and Collection Classes in Delphi

---

Collections (sometimes called containers) are an important foundation for object-oriented programming, but Delphi has traditionally been rather weak in this area. The TList and TStrings classes are useful but limited. The problem until recently has been the difficulty of writing a generic class. Delphi lacks parameterized types, so the TList class, for example, stores untyped pointers. Using interfaces, though, it is now possible to write useful, type-safe collection classes in Delphi. This article examines an interface-based set of collection classes and examines red-black trees as a specific implementation. The suite of interfaces and classes is available online at http://www.tempest-sw.com/.

Interface-Based Programming

Delphi interfaces look a lot like COM or Java interfaces. An interface describes a set of virtual methods but does not provide any storage of fields (Delphi’s term for data members or instance variables) and does not implement any methods. A class implements an interface by listing the interface name in the class declaration and implementing all of the methods of that interface. A class can implement any number of interfaces.

Like classes, an interface can inherit methods from an ancestor interface. All interfaces in Delphi inherit from a root interface, IInterface, which defines the QueryInterface, _AddRef, and _Release methods. If you are familiar with Microsoft’s COM, you will recognize these methods, but don’t let them fool you. Delphi interfaces are not tied to COM in any way. The way interfaces work is very similar to COM, but you can use interfaces for many other uses, as this article explains.

When using interfaces in Delphi, you rarely need to worry about IInterface and its methods. Most often, you will be able to derive a class from TInterfacedObject, which implements IInterface and provides useful implementations of its methods. If you must inherit from a different class, it’s easy to implement these methods.

The QueryInterface method casts an object to a different interface type. As an argument, you pass an interface identifier, and the method determines whether the object’s class implements that interface. If so, a new interface is returned; otherwise an error status is returned. The Delphi Pascal compiler automatically keeps track of which interfaces a class implements, so implementing the QueryInterface method is simply a matter of calling GetInterface, which looks up an interface identifier.

Delphi lacks automatic memory management for ordinary objects, but uses reference counting to manage the lifetimes of interfaced objects. The _AddRef method increments the object’s reference count, and _Release decrements the reference count. When the reference count becomes zero, _Release frees the object. The compiler automatically generates calls to _AddRef and _Release to track assignments of interfaces, passing interfaces to subroutines, and so on. In other words, most of Delphi’s interface handling is transparent to the programmer. To take full advantage of Delphi’s interfaces, you only need to derive a class from TInterfacedObject, and implement any or all the interfaces you want. Whenever your program uses interface references instead of object references, Delphi takes over management of the objects, and uses reference counting to know when it is safe to free them.

One of the tricks when using interfaces in Delphi is that once you cast an object reference to an interface, Delphi owns the interface and will manage its lifetime. Do not call the object’s Free method. This is different from the usual pattern of using objects in Delphi, and it takes getting used to. Delphi will free the object when it is safe to do so, that is, when there are no more references to the object.

The Collection Framework

Figure 1 shows the inheritance tree for the collection interfaces. The root interface, ICollection, defines methods that apply to all kinds of collections. To store an object in a collection, its class must implement the ICollectible interface. Thus the collection classes are not restricted to storing any particular class. If you must store objects whose classes do not implement ICollectible, the framework includes a wrapper class that holds any object and implements the ICollectible interface. Example 1 shows the declaration for the basic interfaces in the collection framework.

Derived from ICollection are several interfaces for particular kinds of collections, namely, IList, IStack, ISet, and IMap. A list is a collection where the elements are arranged in a particular sequence. The sequence is usually the order in which the objects are added to the collection. IList adds a few methods to ICollection — for indexed access to individual elements of the collection. IStack declares methods for pushing, popping, and accessing the top of the stack. A set is a collection of unique elements, but not necessarily in any particular order. A map is a set of key-value associations. IMap adds several methods for working with keys and values as distinct objects.

Enumerators examine the elements of a collection. The base interface is IEnumerator. Every collection implements the Enumerator method, which creates an instance of an enumerator. Each collection can have many enumerator instances, each with its own position in the collection. If an enumerator is active on a collection, you should not modify the collection except by using the enumerator. If you modify a collection with one enumerator, you should reset all other enumerators that are active on the same collection.

The ICollection interface declares the basic methods for accessing a collection. The design of ICollection owes much to the new collection interfaces in Java, the STL in C++, and to the collection classes in Smalltalk. Some of the more important methods are described in Table 1.

Some collection interfaces declare additional methods, which are shown in Example 1. For example, IStack has the methods Push, Pop, and Top, mentioned previously. The IList interface adds methods and a property to facilitate indexed access to the collection, where the index is an integer. IMap also allows indexed access, but the index can be any object that implements ICollectible.

Implementing the Collection Interfaces

Interfaces define behavior, and classes implement that behavior. The separation of interface and implementation facilitates object-oriented programming in Delphi. When designing a program, it’s best to think of the behavior of the objects that make up the program. What matters, for example, is that a compiler’s symbol table can store and retrieve identifiers. Whether the symbol table stores its identifiers in a tree or a hash table is not important during the early design of the compiler. Because each identifier has information associated with it; e.g., type, its declaration, and so on; a map is the appropriate choice for the collection. Armed with the IMap interface, you can design and even implement the compiler, deferring the implementation choice until the very end. Using the IMap interface is just as simple. The shallow inheritance tree means you need to learn the methods of only ICollection and IMap. The symbol table uses Add to add identifiers and FindKey to look them up.

An additional benefit of using interfaces is that Delphi handles the memory management. The compiler probably implements classes such as TVariable or TFunction and stores these objects in the symbol table. Some symbols are needed only during parsing, and others might be needed for code generation; still others stick around through optimization. You don’t need to worry about when these objects are safe to delete. Create IVariable, IFunction, and similar interfaces so you can work entirely in the world of interfaces, and let Delphi handle the ugly details. Creating an interface layer for the compiler’s classes adds only a little bit of complexity, but the gains are enormous because memory-management bugs are among the most common and the most difficult to track down.

When it’s time to give a concrete implementation to the IMap interface, you can choose hash tables, sorted arrays, or red-black trees. If none of the existing classes suit your needs, it’s easy to add new collection classes. The basic kinds of implementations are arrays, linked lists, hash tables, and red-black trees. For more information about red-black trees in general, see “Red-Black Trees,” by Bruce Schneier (Dr. Dobb’s Journal, April 1992).

Arrays are good for small collections or collections that must be kept in order and indexed randomly. Sorted arrays give good performance for smaller sets and maps, but larger ones need the better performance of a tree or hash table. The separation of interface and implementation means you can use a collection interface and change implementations without any other changes to your program.

All the collection classes inherit from TCollection. They could inherit from any other class, but TCollection implements many of the methods of ICollection, so it’s a convenient base class to use. To implement a new collection class, you need to implement only the Add, Enumerator, Find, and Remove methods. TCollection implements all the other methods in terms of those four, but some methods, such as GetCount and Clear should be overridden to improve performance. Example 2 shows the declaration of the TCollection class and the implementations of some of its more interesting methods.

The implementation class hierarchy is more complicated than the interface hierarchy. In order to maximize code reuse, the implementation classes do not always follow strict is-a relationships. This is another benefit to separating interfaces from implementations. For example, all the map implementations inherit from TMap, which implements the map behavior by storing key/value associations in a set. The concrete class that derives from TMap determines the set implementation to use. Thus, TRbTreeMap inherits its map behavior from TMap and delegates the storage to a TRbTreeSet object. Figure 2 shows the inheritance tree for the array, red-black tree, and map collections. Linked lists and hash tables are similar, but are omitted for the sake of brevity.

For very small sets, use TArraySet, and for slightly larger sets, you can use TSortedArraySet. For larger collections, hash tables and trees provide better performance. THashTable implements a generic hash table, and THashSet inherits from it to implement the ISet interface. Hash tables are fast, but store their elements in an unpredictable order. If you want to keep the elements in sorted order, the TRbTree class implements red-black trees, and TRbTreeSet implements ISet using a red-black tree.

Creating a new collection class is easy. The hardest work is implementing the logic to manage the basic collection; e.g., the hash table or the red-black tree.

Red-Black Trees

In a red-black tree, each node stores three references: a parent, a left child, and a right child. Each node also holds a reference to an ICollectible interface, which is the user’s object. A node also needs to store a color (red or black). Instead of reserving an entire integer for a single bit, The TRbNode class stores the color as the least significant bit of the parent pointer.

Tricky code is often a sign of muddled thinking, but this particular trick pays off in time and space. Storing one bit of information ordinarily requires an entire integer. Delphi has the Boolean type, which it can store in one byte, but modern architectures, such as the Pentium, prefer to fetch and store information as entire words. Therefore, Delphi and other modern compilers align fields on integer boundaries. Thus, storing a single bit ends up occupying 32 bits, thereby wasting 31 bits. Because of the same alignment restrictions, Delphi’s memory allocator aligns memory on integer boundaries. This means the least significant bits of every pointer are always set to zero.

The lowest bit of a pointer is always zero, so why not store the color there? When treating the field as a pointer, force the bit to zero; when treating the field as a color, mask off the pointer part of the field to leave only the color bit. The implementation of the Color and Parent properties is hidden in the TRbNode class, so changing from the clear, direct approach to the packed, tricky approach requires no changes to the rest of the collection package. Example 3 shows the TRbNode class. The color trick is entirely encapsulated by this class, so the bulk of the code for managing the tree (in class TRbTree) does not need to know about it.

The TRbTree class handles the logic for rotating subtrees and all the other fun stuff that makes a red-black tree what it is. Because TRbTree inherits from TCollection, it doesn’t have to do much to implement the ICollection interface. Like any other class that inherits from TCollection, TRbTree implements the Add, Enumerator, Find, and Remove methods. For performance reasons, it also overrides Clear and GetCount. You could squeeze even more performance by overriding a few other methods, such as RetainAll, but that is left as an exercise for the reader. Example 4 shows the Find and Remove methods as examples. Download the collection suite to see the implementations of the other methods.

The collection suite comes with a test program that lets you play around with the basic interfaces. You can add items, remove items, look up items, and even run a simple performance test. For red-black trees, you can pop up a window that displays the tree structure — an invaluable aid when debugging the TRbTree class. Figure 3 shows an example of the debugging window in action. Naturally, the structure of the tree is not important when using the TRbTree collection classes, but the debug window needs to get to the protected members of TRbTree. To do that, it uses another trick: derive TExposeTree from TRbTree and cast every TRbTree instance to TExposeTree. This is a dangerous trick because you are casting an object to the “wrong” type, but if you do not add any virtual methods or fields to TExposeTree, you can use this trick safely. This trick works because Delphi lets all classes that are defined in a single unit access each other’s private and protected members. TExposeTree is declared in the same unit as the debugging form, so the form class can access the protected members of TExposeTree, which it inherits from TRbTree. Example 5 shows the method that constructs the tree view representation of the red-black tree.

Conclusion

Interfaces are a powerful way to program in an object-oriented world. By separating type hierarchies as interfaces from code-reuse hierarchies as classes, you can write better programs that are easier to read and maintain. The collection framework demonstrates how easy it is to work with interfaces in Delphi. Any class can implement the ICollectible interface, so it can be stored in a collection. A collection class must implement ICollection and any one or more of the collection interfaces: IList, ISet, IStack, and IMap.

The TCollection class implements most of the methods of ICollection, so concrete collection classes are easy to implement. The suite comes with array, linked list, hash table, and red-black tree implementations of the collection interfaces. This article takes a closer look at the red-black trees. The entire suite is freely available online.

About the Author

Ray Lischner is the author of Delphi in a Nutshell (O’Reilly), plus other books and articles about Delphi. He is also a co-author of Shakespeare for Dummies, proving that literature and computers can coexist happily. You can contact him at [email protected].