Designing Objects

By Dave Curtis, Sunnyvale, CA

“Reusable software components” -- that catch phrase gets a lot of use by proponents of object oriented languages. True reusability, however, is more easily achieved in advertising than in real world code. It is possible to design tangled and tortured objects, just as it is possible to write spaghetti code. Good object design requires a new way of thinking.

Some time ago, I started a project to create core objects for common data structures. After all, aren’t you tired of creating (and debugging) a linked list, a queue, a binary tree, etc., for the umpteenth time? I am, for sure. My experience taught me a few lessons, which I have reduced to a set of object design guidelines. While I can’t claim to be a guru of object design, these thumb rules provide a simple, structured approach to designing objects that work well in real world code.

All of the examples shown here are written in MPW Pascal, but you C++ fans shouldn’t turn the page yet. The object design principals apply to any object oriented system, and all of the objects are simple enough that they should be easy to translate.

Object Design Guidelines

The goal of these guidelines is to keep all objects small, simple and re-usable. Small, simple objects are easier to understand and easier to debug. Small, simple objects have less excess baggage and fewer undesirable side effects which make reuse difficult. If, while trying to use an object as the foundation for a more complex structure, you find that the object has too much overhead or does work in excess of your needs, then you have violated the first guideline:

Factor objects by data and operation.

What does it mean to factor an object? Most data structures of any meaningful size are made up of a collection of simpler pieces. With objects, we can carry that statement further and say that the methods are also a collection of simpler pieces. A well factored object has been broken into a collection of smaller, simpler objects that have easy to understand functions. Easily said, but what identifies a good place to start factoring? Guideline two:

Make object families for complex data structures.

All complex data structures can be viewed as a “whole” made up of “parts”. In conventional programming languages the distinction between these two perspectives blurs, and we become used to submerging the personalities of these two views. This is especially true for pointer based structures, where we define a single record type and root the entire structure with a single pointer variable of the record type. In object programming, it pays to think carefully about this distinction, and to create separate object types for the “whole” and the “part”. In an example shown later, a linked list is factored into list-element objects (the part) and list objects (the whole). Both data and methods are then factored by answering the question: “Does this apply to the whole or to the part?”

Many operations on complex data structures require that the elements be traversed. Traversal operations are a good place to factor. Traversal methods, and any data required, can be placed in a separate object as part of the object family used to make up the complex data structure. A family of whole/part/traversal object types is sufficient for many data structures. In fact, if you don’t find this triad in your object family, you should ask yourself why.

Often, the traversal objects will only be used by methods of the “whole” object, and will not be used by outside clients of the object family. It still makes sense to create a separate object in order to minimize the side effects that occur when creating descendant types of any member of the object family. This is really another facet of the third guideline:

Consider the legacy.

After all, our avowed goal is to create reusable objects. After factoring a data structure into a workable family of sub-objects, it is time to consider how each individual object type will be used by its descendants. A good job of factoring into sub-objects and factoring methods among objects can often be accomplished by considering only the data fields. This first pass of factoring, however, often leads to methods that are too large. The “whole/part” question will help us apply a method to the correct object, but doesn’t address issues of inheritance.

To frame your thinking, ask: “How would a descendant object use this method in an INHERITED call?” Depending on the form of the answer, the method might need to be factored into two or more simpler methods attached to the same object. For each step of each method, ask if a descendant wants to inherit or override that step. Method inheritance usually has one of the following patterns:

1) Call to INHERITED method, followed by descendant code (mnemonically: Ic).

2) Descendant code, followed by call to INHERITED method (cI).

3) Some descendant code, an INHERITED call, some more code (cIc).

4) Some INHERITED work, descendant code, more INHERITED work (IcI).

Patterns 1 and 2 (Ic and cI) are great -- no change needed. Initialization methods often have the Ic pattern, and destruction methods often have the cI pattern. If this isn’t true, the method in question should be examined closely to make sure that a deviation from the normal pattern makes sense. Pattern 3, cIc, is less frequent, but is no less natural. The IcI pattern, however, is another story. The IcI pattern is impossible to code in Pascal and indicates the need for better method factoring.

An IcI pattern arises when generic setup and cleanup work surround type specific actions. There are two approaches to factoring the IcI pattern. One approach is to split the method into two smaller methods, and let descendant types call each separately. This is usually the wrong approach. More often than not, a second generation descendant will have the same problem -- another IcI pattern, only nested this time: I2IcII2. Yuk!

A better approach is to factor the offending method by adding one or more auxiliary methods. The additional method(s) do type specific work, and the original method does the generic setup and cleanup, calling the additional method in between. The additional methods often do very little or even nothing in the foundation object. That’s OK, they are designed to be overloaded. Remember, you can’t overload a method that isn’t there to begin with, so dummy methods are an important part of the foundation. A dummy method provides a clean way for descendant objects to expand the interior of an inherited procedure.

Recognizing and factoring potential IcI patterns is the most difficult part of object design, since to a large extent it requires predicting the future. A simple and innocuous method can easily hide potential IcI problems that won’t show up for most uses of the object. There is no substitute for careful thought. Trace each method step by step. Keep a watchful lookout for validity checks and error handlers, as descendant objects often need to extend them. Give the boolean expression in every test double scrutiny. Break the expression out as a new boolean function method if there is any chance that a descendant might wish to extend the test.

Guideline Summary

Here are the guidelines in summary form:

1) Factor objects by data and operation.

2) Make object families.

a) object for the whole

b) object(s) for the parts

c) object(s) for traversal

Ask: Does method belong to whole or part?

3) Consider the legacy.

a) Examine inheritance patterns for soundness.

b) Provide dummy methods.

Ask: Will this method need interior expansion?

Linked List Example

The linked list data structure unit shown in listing 1 is a prefect illustration of the synergy of object families. Object factoring follows the whole/part/traversal pattern. The “whole” object, listObj, contains the head link of the list, and performs operations that apply to the list as an aggregate data structure. The “parts” are defined by listElementObj, which contains the chaining link and element specific operations. Traversal is provided by the object listIterator, which walks the list from head to tail.

Nowhere in any of the objects is there any space to store data! These objects are designed to be used as foundation building blocks. Descendant types append data fields as needed. The objects defined by the unit have been boiled down to “essence of linked list”. In other words, the linked list concept itself has been factored into “data” and “structure”, and these objects provide the “structure”, while the client defines the “data”. Here is what the objects do:

ListElementObj is the basic building block used for lists. As mentioned above, the only field it defines is the link pointer, which in this case is an object variable of type listElementObj. The init method sets this link to nil, and has been designed for an Ic inheritance pattern. The release method is a do-nothing place holder. Descendant types that define data fields referencing heap storage should override this method.

ListObj defines a list as a whole entity. Again there is no data, just a head link. The init method clears the head link. ListObj.release disposes all of the list elements as well as the list object itself, making use of the dummy method listElementObj.release. ListObj.release illustrates the importance of factoring for maximum reusability. ListObj.release is itself designed for a cI inheritance pattern, and provides for a descendant call back to avoid the dreaded and impossible IcI pattern via listElementObj.release. Without the dummy method listElementObj.release, descendant objects would not be able to cleanly release storage. In anticipation of the potential that some descendant types may keep multiple references to a single list element, listElementObj.release is defined as a boolean function so that the result of a reference count check can be returned to ListObj.release.

So far, all the methods we have talked about exist only for housekeeping. Real linked list operations are provided by the methods append, appendList, insert, and head. Append and insert add a listElementObj to either the tail or the head of the list. AppendList adds another list to the end of the list, and disposes of the storage associated with the first list header. Head nips the first element off the list, returning it through a var parameter.

The head method illustrates one of the severe deficiencies of Pascal as an object oriented programming language. Ideally, head would be a function, not a procedure, and would return a descendant object type. Unfortunately, Pascal provides no mechanism to return a value having a descendant type. We could return a listElementObj, but in that case the caller always needs to perform a type coercion, causing the calling expression to get messy very quickly.

Object data structure factoring often leads to legitimate “uphill” type coercions like these. My (rather ugly) solution is to use var...univ parameters and programmer self discipline. Descendant objects could wrap the var parameter procedure call in a nice looking function, but I prefer to avoid the overhead. This might also be a good place to use the built-in member function, to make sure that the parameter is a descendant of listElementObj.

The listIterator object is built on a very simple underlying object type, iterator. Listing 2 shows the iterators unit. The iterator object provides a set of common properties for data structure traversal objects. An iterator defines the state information and methods necessary to visit each element of a complex data structure exactly once. When an iterator is used to perform an operation on the aggregate data structure there is usually one instance of an iterator variable per loop nesting level.

The basic iterator object contains fields named subject and i. Subject is the aggregate object being traversed (the “whole”), i is the current element node being visited (current “part”). The init method establishes a connection between the iterator and the traversed object. LoopReset causes the iterator to start over, no matter what the current state. The another method does all of the real work, but in the basic iterator, is just a dummy. Since another needs knowledge of the subject data structure, it must be provided by a descendant type that is part of a data structure family. Notice, however, that client code using the descendant iterator need understand neither the iterator nor the data structure being traversed! Let’s take a closer look:

Suppose we have a complex data structure called mysteriousStuff, made up of mysteriousElements. We want to send method doItToIt to every element of mysteriousStuff. We have an iterator called doingItTo that can traverse mysteriousStuff. We do the following:

{1}

 while doingItTo.another(mysteriousElement) do
 mysteriousElement.doItToIt;

This code works for any data structure of any kind of object. The only requirement is the existence of an another method with understanding of the data structure.

In practice, it turns out that most iterator based loops make one pass over the structure sending the same message to each object. Suppose we could design a method named forAll that had a method parameter, something like:

{2}

type
 mysteriousStuff = object (venerableAncestor)
 procedure forAll 
 (procedure mysteriousElement.m);
end;

The client code could pass in any parameterless method, and forAll could send it to every element of the data structure. This would be simple and elegant from the client code point of view, and often simpler to implement than an iterator object. Unfortunately, MPW Pascal won’t accept method parameter declarations. Apple, if you’re listening, please fix this omission.

With that short digression to discuss iterators, we can complete the lists unit. We simply need to define the listIterator.another method. ListIterator marches down the list from head to tail. The variable i provides sufficient state to keep track of both the reset condition and the mid-loop condition, so listIterator adds no new fields. Once again, we need a couple of uphill type coercions, and might consider screening both the parameter anObject and the field subject with member.

Does the Lists Unit Meet the Guidelines?

The first guideline advocates factoring objects by data and operation. ListObj data roots a list, and provides methods that treat lists as a whole. ListElementObj defines element oriented features. The objects have been factored.

Guideline number two suggests an object family, with members for the whole, the parts, and traversal. The lists unit fits the model exactly.

Finally, guideline number three admonishes us to be aware of inheritance patterns. Because of that, we have carefully factored the release methods to provide for safe destruction of descendant data. Note also that listObj.appendList is careful to use release to destroy the extra listObj, even though within the lists unit a simple dispose would be sufficient. If appendList used dispose directly there would be no opportunity for a descendant of listObj to release its storage.

The Lists Unit in Action

Listing 3 shows testLists, a simple program that puts the lists unit through its paces. It creates descendant types of both listObj and listElementObj, and makes use of the listIterator object. TestLists also uses one other unit we haven’t talked about, the memCheck unit.

One of the nasty realities of life is that new(someObject) won’t always work. Life gets even nastier if we ignore the occurrence of this unwelcome event. The memCheck unit shown in listing 4 provides bare-bones handling for out-of- memory conditions, via an object that can be extended when more sophisticated actions are required. It is a good illustration of how functional factoring is useful even for objects that have trivial data structures.

The memCheck unit defines an object type called memCheckObj. All of the functionality required to deal with an out of memory condition is collected under this object. The key method is memCheckObj.gotObject, which checks for an empty object, invokes garbage collection if needed, and takes an error exit on failure. To use memCheck, all object creation calls using new should be written like this:

{3}

 repeat
 new (anObject)
 until memCheck.gotObject(anObject);

All error trapping clutter is moved out of the client code and into the methods of memCheckObj. The three steps of checking for a valid object -- nil handle test, garbage collection and error exit -- are factored into separate methods. Client code can override memCheck.collectGarbage with a method that understands the application’s data structures. MemCheck.outOfMemExit provides a place to get a “good-bye kiss” so that clean-up work can take place before returning to the shell.

The testLists program illustrates how to use memCheck, and also shows a very simple linked list. Each list element has an integer data cell, which is defined in testListElementObj. The method dump prints it out. TestListObj also has a dump method, which prints out the entire list. TestListObj.dump is a good illustration of an iterator object in action.

TestLists shows that the lists unit works, and shows how to use it to create a stand-alone linked list. If we’ve done our job well, we should also be able to use the lists unit as a building block for other more complex data structure units. We still apply the same object design guidelines to our new structures. Now, however, we have the lists unit in our code inventory so linked list functionality can be had without tedious re-invention. In the next section we do just that -- the lists unit is the foundation for a stack data structure object family.

The Ultimate Stack

Stacks are a very useful data structure, but often a thorny storage allocation issue. Allocating a fixed amount of storage implies not only a hard limit on the maximum depth of the stack, but also requires that the program allocate enough storage to contain the maximum expected stack. The excess space is often wasted. It is true that a stack can be implemented as a linked list, but a linked list implementation is not a very efficient use of space because the linked list overhead is so large compared to the data. The optimum stack would use an efficient, but expandable data structure.

One way to make a stack expandable is to break the stack into frames. Each frame is mini-stack with a moderate number of cells. When one frame overflows, another frame is added to the structure. The stack can grow as large as heap space allows, but at no time does the stack consume greatly more space than required.

Can we derive an efficient stack data structure using the idea of segmented stack frames? Let’s apply the object design guidelines to this concept and see where they lead.

The client program’s view of a stack is that it is a place to put things for retrieval in last-in-first-out (LIFO) order. What are the “things”? Since we are object oriented programming fanatics, the things are objects, of course. The commonly accepted stack operations are ‘push’, which adds an object to the top of the stack, and ‘pop’, which retrieves an object from the top of the stack. Cheaters also sometimes use the ‘pick’ operation, which reaches down into the stack for an object.

The first object design guideline tells us to factor operations and data. But a stack provides such a limited view of its contents that the clients view of a stack is all operations! That is easy to factor. We can serve a client program’s needs with an object having push, pop and pick operations and no client visible data. Data representation details can be completely hidden in another object without loss of functionality. This is good, since it means our stack frame scheme can easily be made transparent to the client program.

We already have a family of objects, so the second guideline is at least partially met. We have a client visible stack object, and a potentially private implementation object. We know object families often consist of whole/part/iterator triads. Do we need an iterator for the stack family? Under normal operation, a stack is rarely swept with a loop. One could argue that the stack is a data structure that needs no iterator. On the other hand, it is handy to be able to dump the contents of the stack during debugging, so for completeness we should toss in an iterator.

The third guideline causes us to pause and think about how derivative objects will use this object family. One thing that comes to mind is that stacks are usually homogeneous; in other words, all elements of a stack have the same type. To be generic, our stack structure needs to allow any type of object to be pushed. A client program might wish to limit this “open door” policy. One way a client program could screen pushes would be to override ‘push’ with a type screening method making use of the object Pascal built-in member function. A cleaner solution is to let the generic push do the screening, but factor out the type screening function as a separate method. For completeness, we can also provide an error handling method to be called when the screen fails.

Let’s review the design decisions so far: We have the familiar whole/part/iterator object family. The client interface routines provided by the stack are push, pop, pick, a push screening function (let’s call it okToPush), and a procedure to handle failed screens (we’ll call it rejectPush). The stack element object is transparent to the user. The stack iterator provides generic functionality. Looks like we are ready to implement the stack.

As mentioned above, the stack will be implemented as a group of frames. A linked list is a perfect way to manage the frames, since the linked list will keep the frames in order, and since most stack accesses use the most recently created frame. Luckily, we happen to have an object family that implements linked lists already, so we can build the stack object family on top of the lists unit.

Listing 4 shows the completed stacks unit. The stackObj type is built on the listObj type. All of the new client interface methods are attached to stackObj. Pop and pick are implemented as procedures using var...univ parameters rather than as functions, because, as discussed earlier, object Pascal lacks sufficient type inheritance semantics. StackFrameObj is a descendant of listElementObj. Since stackFrameObj contains a field that must be initialized, stackFrameObj overrides the init method. StackSweepObj is a descendant of the generic iteratorObj, not listIteratorObj, because stackSweepObj needs to visit every cell in the stack, not just every frame.

All of the stack objects are clean descendants of their respective ancestor objects. All of the overridden methods are ones we expected to override, and the override methods inherit ancestor functionality as expected. This is good verification of sound design in the linked list object family.

Stack Implementation High Lights

The stacks unit has been designed so that the push method only adds a frame when the current frame overflows, and pop only discards an empty frame on under flow. This minimizes thrashing near frame boundaries. Still, push and pop are almost as simple as in a normal stack implementation. There is a small amount of extra code to insert and delete frames, and of course push calls the dummy okToPush method which allows descendant objects to define type screening.

Because the stack is split into frames, pick is more complex than in the usual stack implementation. Pick first calculates how many frames it must walk back to find the requested element, walks to the correct frame, then selects the correct element from within that frame.

StackFrameObj adds two fields to its base type, listElementObj. An array called cell holds objects pushed onto the stack, and framePointer indicates the topmost element of the local frame. Since framePointer must be initialized, stackFrameObj overrides listElementObj.init.

Stack Operational Details

As mentioned above, push only adds a frame when the current frame overflows. This condition happens in one of two ways, either the stack is completely empty, or the topmost frame of the stack is completely full. In either case, a new frame is inserted at the head of the frame list. Since each frame is a listElementObj the actual list insertion is done by an inherited method.

OkToPush guards the entire push operation. The default okToPush method always returns true, allowing any type of object (or in truth, any long word) into the stack. Descendant objects can override it to create selective stacks. The companion method rejectPush doesn’t do anything, so unless descendant objects override rejectPush along with okToPush, rejected objects will disappear almost without a trace. Unfortunately, the storage referenced by the rejected object handle will never be freed unless rejectPush is augmented to dispose of the object.

Pop must watch out for the empty stack condition, but is straightforward otherwise. Since pop only discards an empty frame on under flow, the empty stack condition can come up two ways. Either there are no frames, or the topmost frame is empty. After making these two tests, pop simply returns the topmost element after decrementing the frame pointer.

Pick is quite interesting. In a normal stack implementation this would be a very simple operation. After range checking the index, a simple subtract would yield the array index of the requested element. The frame based implementation makes the pick operation much more complex in general. Also, deep picks pay a performance penalty, although shallow picks are not much worse than in a simple stack. Pick must calculate which frame in the frame list contains the required element. After that, it must calculate the element offset in the target frame. While walking back along the frame links pick must be careful not to run off the end. Since pick doesn’t know the depth of the stack at the outset, there is no way to range check before walking the list.

StackSweekObj.another also has a few kinks. Two new pieces of state are added to the generic iterator object so that another can keep track of where it is. SubjectFrame is a pointer to the current frame, and subjectPointer is the current index within subjectFrame. The large size (for a method) of another might seem a little surprising. After all, what‘s so hard about sweeping down a stack? A lot of the code tests end-case conditions. The fact that another is so large is a good argument for using iterator objects instead of main line program code. Without a predefined iterator, every client code loop would need to include this code. By using an iterator, the client code is simple, straightforward, readable, and more likely to be correct.

Conclusion

The acid test for any object definition is reusability. Well thought out data and method factoring aids reusability. The object design guidelines presented here aid the development of reusable objects. I hope you find them to be a good starting point as you develop your own set of guidelines and your own object library.

Listing 1

unit lists;
interface
uses
 ObjIntf, iterators;

type
 listObj = object (TObject)
 first : listElementObj;
 procedure init;
 procedure append (e : listElementObj);
 procedure appendList (l : listObj);
 procedure insert (e : listElementObj);
 procedure head (var e : univ listElementObj);
 procedure release;
 end;
 
 listElementObj = object (TObject)
 next : listElementObj;
 procedure init;
 function release : boolean;
 end;

 listIterator = object (iterator)
 function another 
 (var anObject : univ TObject) : boolean;
 override;
 end;
 
implementation

procedure listObj.init;
begin
 first := nil end;

procedure listObj.append 
 (e : listElementObj);
var
 t : listElementObj;
begin
 if first = nil
 then first := e
 else begin
 t := first;
 while t.next <> nil do t := t.next;
 t.next := e end end;
 
procedure listObj.appendList (l : listObj);
var
 p : listElementObj;
begin
 append (l.first);
 l.first := nil;
 l.release end;
 
procedure listObj.insert
 (e : listElementObj);
begin
 e.next := first;
 first := e end;

procedure listObj.head
 (var e : univ listElementObj);
begin
 e := first;
 if first <> nil { guards both potential nil references, e and first 
}
 then begin
 first := first.next;
 e.next := nil end end;

procedure listObj.release;
var
 t, t2 : listElementObj;
begin
 t := first;
 while t <> nil do begin
 t2 := t;
 t := t.next;
 {release list element storage, if it has any}
 if t2.release 
 then dispose (t2) end;
 dispose (self) end;

procedure listElementObj.init;
begin
 next := nil end;

{ Override this if your list element must release
 storage before being disposed of.  Return true
 if the element can be disposed of. If other
 references to the element still exist, return
 false.  This generic release assumes that only 1 
 reference to any element exist.}
function listElementObj.release : boolean;
begin 
 release := true end;
 
function listIterator.another 
 (var anObject : univ TObject) : boolean;
begin
 if i = nil
 then i := listObj(subject).first
 else i := listElementObj(i).next;
 anObject := i;
 another := i <> nil end;
 
end.

Listing 2

unit iterators;
interface
uses
 ObjIntf;

type
 iterator = object (TObject)
 subject, { the subject data structure }
 i {the loop variable, updated by method 
 'another'}
 : TObject;
 procedure init (theSubject : TObject);
 procedure loopReset;
 function another
 (var anObject : univ TObject) : boolean;
 end;

implementation

{ the iterator must be associated with a data structure that will be 
the loop subject }
procedure iterator.init
 (theSubject : TObject);
begin
 subject := theSubject;
 i := nil end;

{ generic loop reset just clears out the iteration variable }  
procedure iterator.loopReset;
begin
 i := nil end;

{Method 'another' serves up each element of the subject data structure 
exactly once, one at a
 time.  Override this function with the following
 behavior:
  1) if iterator.i is nil, start a loop by setting
 i to the first operand
  2) if iterator.i is not nil, advance i to next
 operand
  3) return i in anObject
  4) return true if anObject is non-nil
  5) when there are no more operands:
   a) set i to nil (exit in reset condition)
 b) return nil in anObject
 c) return false }
function iterator.another
 (var anObject : univ TObject) : boolean;
begin end;

end.

Listing 3

{$SETC compileForMPW := true }
{ if false, then compile for application }
{ How to use:
 1) create a memCheckObj (or a descendant) with
 new(aMemCheckObj) (this can be 'new(memCheck)'
 if you don't override any methods)
 2) initialize before making any more 
 'new(someObject)' or 'newHandle' calls
 3) loop on gotObject until new(someObject) 
 succeeds, as in:
 repeat
 new (obj)
 until memCheck.gotObject (obj);

 Advanced features:
 1) override collectGarbage with application 
 dependant code to free up space (optional)
 2) override outOfMemExit to do any clean up 
 before exiting through inherited outOfMemExit
 (optional) 
 
 Note:
 The outOfMemAlertId parameter to initMemCheck is
 the id of an alert that will be posted before
 the program is halted.  It is ignored in MPW
 mode. }
 
unit memErr;
interface
uses
 {$IFC compileForMPW}
 PasLibIntf,
 IntEnv,
 {$ELSEC}
 Dialogs,
 {$ENDC}
 ObjIntf;

type
 memCheckObj = object (TObject) 
 memRetryCount : integer;
 procedure init;
 function gotObject (o : TObject) : boolean;
 function collectGarbage : boolean;
 procedure outOfMemExit;
 end;
 
procedure initMemCheck
 (mc : memCheckObj; outOfMemAlertId : integer);

var
 memCheck : memCheckObj;
 { reference this object in your code }


implementation

var
 theAlertId : integer;

procedure memCheckObj.init;
begin
 memRetryCount := 0 end;

function memCheckObj.gotObject
 (o : TObject) : boolean;
begin
 if o <> nil { was newHandle successful? }
 then begin
 gotObject := true;
 memRetryCount := 0 end
 else begin
 gotObject := false;
 if collectGarbage { could we make any space? }
 then memRetryCount := succ (memRetryCount)
 else outOfMemExit end end;

{ If your data structures can be garbage 
 collected, override this method.
 1) return true if any space was made
 2) use memRetryCount to detect multiple
 collectGarbage calls for the same 'new()'.
 memRetryCount = 0 on first call. }
function memCheckObj.collectGarbage :
 boolean;
begin
 collectGarbage := false end;

{ override with clean-up routine, if necessary }
procedure memCheckObj.outOfMemExit;
{$IFC compileForMPW}
begin
 writeln (diagnostic, 'out of memory');
 halt end;
{$ELSEC}
var
 dummy : integer;
begin
 dummy := StopAlert (theAlertId);
 halt end;
{$ENDC}

procedure initMemCheck
 (mc : memCheckObj; outOfMemAlertId : integer);
begin
 if mc <> nil
 then begin
 memCheck := mc;
 theAlertId := outOfMemAlertId;
 {$IFC not compileForMPW}
 { do this now, while we have the memory! }
 CouldAlert(theAlertId);
 {$ENDC}
 memCheck.init end
 else halt end;

end.

program testLists (input, output);
uses
 ObjIntf, iterators, lists, memCheck, PasLibIntf;
 
type
 testListObj = object (listObj)
 procedure dump;
 end;
 
 testListElementObj = object (listElementObj)
 data : integer;
 procedure dump;
 end;
 
var
 { some lists to test with }
 testList, testList2 : testListObj;
 { a temporary }
 t : testListElementObj;

procedure testListObj.dump;
var
 dumping : listIterator;
 dumperand : testListElementObj;
begin
 repeat new (dumping)
 until memCheck.gotObject(dumping);
 dumping.init(self);
 writeln (output, 'Dump:');
 while dumping.another(dumperand) do
 dumperand.dump;
 writeln (output) end;

procedure testListElementObj.dump;
begin 
 writeln (output, data) end;

begin { Main program }
 PLSetHeapType(true); { allow dispose }
 
 { start up the allocation checker }
 new (memCheck);
 initMemCheck (memCheck, 0);
 
 repeat new (testList)
 until memCheck.gotObject(testList);
 testList.init;
 
 write (output, 'Should be empty -- '); 
 testList.dump;
 
 repeat new (t)
 until memCheck.gotObject(t);
 t.init;
 t.data := 1;
 testList.insert(t);
 write (output, 'One element(1) -- '); 
 testList.dump;

 repeat new (t)
 until memCheck.gotObject(t);
 t.init;
 t.data := 2;
 testList.insert(t);
 write (output, 'Two elements(2 1) -- '); 
 testList.dump;
 
 repeat new (t)
 until memCheck.gotObject(t);
 t.init;
 t.data := 3;
 testList.append(t);
 write (output, 'Three elements(2 1 3) -- '); 
 testList.dump;
 
 testList.head(t);
 write (output, 'Two elements(1 3) -- '); 
 testList.dump;
 
 repeat new (testList2)
 until memCheck.gotObject(testList2); 
 testList2.init;
 testList2.append(t); {append to an empty list}
 write (output, 'List 2, one element (2) -- '); 
 testList2.dump;
 
 {disposes testList2 }  testList.appendList (testList2); 
 write (output, 'Three elements (1 3 2) -- ');
 testList.dump;
 
 testList.release;
 
 end.

Listing 4

unit stacks;
interface
uses
 ObjIntf, iterators, lists, memCheck;

const
 stackFrameDepth = 15; {(cells per frame) - 1}
 stackFrameFull = stackFrameDepth + 1;
 
type
 stackObj = object (listObj)
 procedure push (o : TObject);
 procedure pop (var o : univ TObject);
 procedure pick 
 (n : integer; var o : univ TObject);
 function okToPush (o : TObject) : boolean;
 procedure rejectPush (o : TObject);
 end;

 framePointerType = 0..stackFrameFull;
 
 stackFrameObj = object (listElementObj)
 framePointer : framePointerType; 
 { points to next empty cell }
 cell : array [0..stackFrameDepth] of TObject;
 procedure init; override;
 end;
 
 stackSweepObj = object (iterator)
 subjectFrame : stackFrameObj;
 subjectPointer : framePointerType;
 function another
 (var anObject : univ TObject) : boolean; 
 override;
 end;
 
implementation

{ A stack is stored in a list of stack frames.
 push and pop only add/delete a frame when
 absolutely necessary, in order to avoid
 duplicating work when successive push/pop or
 pop/push operations occur at stack frame
 boundaries. }

procedure stackObj.push (o : TObject);
 
 procedure addAFrame;
 var
 f : stackFrameObj;
 begin
 repeat
 new (f)
 until memCheck.gotObject (f);
 f.init;
 self.insert (f) end;

begin
 if okToPush (o)
 then begin
 { don't combine these next two tests! 
 MUST guard second test with first! }
 if first = nil
 then addAFrame; { stack is empty }
 if stackFrameObj(first).framePointer 
 = stackFrameFull
 then addAFrame; { last frame is full -- start
 a new one }
 stackFrameObj(first).cell
 [stackFrameObj(first).framePointer] := o;
 stackFrameObj(first).framePointer
 := succ (stackFrameObj(first).framePointer)
 end
 else rejectPush (o) end;

procedure stackObj.pop (var o : univ TObject);
var
 f : stackFrameObj;
begin
 if first = nil
 then { stack is empty }
 o := nil
 else begin
 if stackFrameObj(first).framePointer = 0
 then begin { roll back a frame }
 self.head(f);
 if f.release then dispose (f) end;
 if first = nil
 then { stack is empty }
 o := nil
 else begin { pluck out an object }
 stackFrameObj(first).framePointer
  := pred(stackFrameObj(first).framePointer);
 o := stackFrameObj(first).cell
 [stackFrameObj(first).framePointer]
 end end end;

{ Pick 0 = top of stack, nil returned in o if we
 run off the end. Pick makes no modification to
 the stack's contents. }
procedure stackObj.pick
 (n : integer; var o : univ TObject);
var
 frameNum : integer; { counts down to frame that
 contains the cell we want }
 frame : stackFrameObj;
begin
 if first = nil
 then
 o := nil
 else begin
 if n < stackFrameObj(first).framePointer
 then { cell is in first frame }
 o := stackFrameObj(first).cell
 [stackFrameObj(first).framePointer - (n+1)]
 else begin { chase links to correct frame; start with second frame }
 frameNum :=
 ((n - stackFrameObj(first).framePointer)
 div stackFrameFull) - 1;
 frame := stackFrameObj(first.next);
 while frameNum > 0 do begin
 if frame <> nil { did we go off the end? }
 then frame := stackFrameObj(frame.next)
 else frameNum := 0; { off end - bail out }
 frameNum := pred(frameNum) end;
 if frame <> nil
 then
 o := stackFrameObj(frame).cell
 [stackFrameDepth - 
 ((n - stackFrameObj(first).framePointer)
 mod stackFrameFull)]
 else o := nil end end end;

{ default screen passes anything }
function stackObj.okToPush 
 (o : TObject) : boolean;
begin
 okToPush := true end;

{ default exception trap is an ostrich -- it
 ignores the problem. }
procedure stackObj.rejectPush (o : TObject);
begin end;

procedure stackFrameObj.init; override;
begin
 inherited init;
 framePointer := 0 end;
 
function stackSweepObj.another
 (var anObject : univ TObject) : boolean;
 override;
begin
 { test for loop reset condition }
 if i = nil
 then begin
 { start at the top }
 subjectFrame
 := stackFrameObj(stackObj(subject).first);
 if subjectFrame <> nil
 then 
 subjectPointer
 := subjectFrame.framePointer end;

 { test for end of frame condition }
 if subjectFrame <> nil
 then begin
 if subjectPointer = 0
 then begin
 { access next frame }
 subjectFrame
 := stackFrameObj(subjectFrame.next);
 if subjectFrame <> nil
 then
 subjectPointer := subjectFrame.framePointer
 end end;

 { return an element }
 if subjectFrame <> nil
 then begin
 subjectPointer := pred (subjectPointer);
 i := subjectFrame.cell[subjectPointer] end
 else
 { stack is empty }
 i := nil;
 
 { exit }
 anObject := i;
 another := anObject <> nil end;

end.