Recursive classroom design: options and best practices

Question

Dear everyone: in advance, thanks for your time.

Recently, I decided to learn Objective-C (I was a C-hacker for a long time), and after reading Kochan’s beautiful text and plunging into the Apple documentation, I was still confused about the best way to implement a recursive class (i.e. a class in which ivar has the same class type). For concreteness, suppose we want to implement a binary tree class. First we have the base class node, which I simplified:

@interface MMNode : NSObject { NSString *label; } 

---

Now we can implement our tree in two different ways. The first (and what I consider more obvious) puts 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 than "pointer-riffic", with the recursion being inserted into the structure. (As mentioned in the comments, anonymous structures and unions are not required. However, since many applications will require additional information on each node, I will leave the code as is).

---

I implemented both solutions and they work well. The first seems simpler, more "OO"; the latter, more "C-oriented" with a slightly more complex source.

Is the latter method preferred? If so, what is the objective reason? All I can determine is perhaps the last one more memory friendly, as the structure has a fixed size.

Thanks again to StackOverflow and thanks to CocoaHeads.

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

Answer 1

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

My rule is to use objects unless there is an obvious reason to use structures.

Since I implement low-level data structures, I decided to use a structure 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 method calls. This is mitigated if the object only has instance variables declared as @public, but you still have to highlight / init and the variables of the Objective-C object are filled with zeros, whereas structures are not unless you use calloc() .

One of the advantages that Objective-C objects have over structures is its automatic integration with garbage collection (10.5+), while the raw C memory must jump over several hoops to get the same benefit. I agree with you that memory management with objects is more familiar (and obvious) for Cocoa developers. Therefore, I use classes as an interface and structures for storage.

Note. The anonymous union and structure in the second code example are outsiders for this particular situation. I use them only so that I can write more ordered but readable binary search tree algorithms. (Details at http://dysart.cs.byu.edu/CHDataStructures/struct_c_h_binary_tree_node.html ) I commented on them, I hope to avoid confusing random readers, but they will remain for future reference.