Recursive Class Design Patterns: Options and Best Practices

Question

Dear all: In advance, thank you for your time.

Lately, I have decided to learn Objective-C (I am a long time C-hacker) and after reading the beautiful text by Kochan and diving into the Apple documentation I am still confused as to the best way to implement a recursive class (ie. a class in which an ivar has the type of the same class). For concreteness, let's assume we wish to implement a Binary Tree class. First we have a basic node class, which I have simplified to:

@interface MMNode : NSObject {
    NSString *label;
}

---

Now we can implement our tree in two different ways. The first (and what I consider the more obvious approach) is placing the recursion in the class itself.

@interface MMTree : NSObject {
    MMNode *root;
    MMTree *leftTree;
    MMTree *rightTree;
}
@property (nonatomic, copy) MMNode *root;
@property (nonatomic, retain) MMTree *leftTree;
@property (nonatomic, retain) MMTree *rightTree;

---

The second method, which is used in the wonderful CHDataStructures.framework, implements this data structure as follows:

typedef struct MMTreeNode {
    MMNode *node;
//  union { 
//      struct { 
            struct MMTreeNode *leftTree;
            struct MMTreeNode *rightTree;
//      };
//  };
} MMTreeNode;


@interface MMTreeStruct : NSObject {
    MMTreeNode *root;
}

Here the solution is more "pointer-riffic", with the recursion pushed into the structure. (As mentioned in the comments, the anonymous structures and unions are not required. However, since many applications will require additional information at each node, I will leave the code as is).

---

I have implemented both solutions and they work well. The former seems more straightforward, more "OO"; the latter, more "C-centric" with slightly, more complicated source.

Is the latter technique preferred? If so, what is an objective reason? All I can determine is maybe the latter is more memory friendly as the structure has a fixed size.

Again, thank you StackOverflow and thank you CocoaHeads.

UPDATE: I should add, it seems that the CoreFoundation object CFTree uses a similar structure implementation.

Answer 1

As the author of CHDataStructures.framework, hopefully I can add a little insight. :-)

My rule of thumb is to use objects unless there is a demonstrable reason to use structs.

Since I'm implementing low-level data structures, I opted to use a struct instead of an object, primarily for performance reasons. Not only do objects require a little more memory per instance, but there is also some overhead for calling methods. This is mitigated if the object only has instance variables declared as @public, but you still have to alloc/init, and Objective-C object variables are zero-filled, whereas structs are not unless you use calloc().

One advantage that Objective-C objects have over structs is automatic integration with garbage collection (10.5+), whereas raw C memory has to jump through a few hoops to get the same benefit. I agree with you that memory management with objects is more familiar (and obvious) to Cocoa developers. That's why I use classes as the interface, and structs for the storage.

Note: The anonymous union and struct in your second code example are extraneous for this particular situation. I use them only to make it possible to write more streamlined yet readable binary search tree algorithms. (Details at http://dysart.cs.byu.edu/CHDataStructures/struct_c_h_binary_tree_node.html) I commented them out to hopefully avoid confusing casual readers, but they remain for future reference.