Last modified 27 June 2003 by jdavis@math.wisc.edu
Inherits from SMKBinaryTree : NSObject
Conforms to NSCoding, NSCopying
SMKTree implements an arbitrary tree data structure. Each node can have an unlimited number of children, and the tree can even have multiple disconnected components (which are stored as siblings of the root node). The tree is a recursive data structure; each node in the tree is itself a tree, possessing any number of children, all of which are retained by the tree.
The semantics of an arbitrary tree are implemented atop the binary tree structure provided by SMKBinaryTree using the standard "first child, next sibling" trick. This implies that children of a node are accessed in linear time rather than constant time; however, in typical applications all of the children are traversed in order anyway, so there is no penalty. Here are the two standard traversal methods:
- (id)firstChild;Returns the first child of the receiver.
Returns the next sibling (the "eldest younger sibling") of the receiver.
The following methods are used to add and remove children, when order is not important.
- (id)addChild:(SMKTree *)tree;Attaches the indicated tree as a child of the receiver, and returns the receiver. If the tree already has (younger) siblings, then these are also added as children of the receiver.
- (id)addSibling:(SMKTree *)tree;
Attaches the indicated tree as a sibling of the receiver, and returns the receiver. If the tree already has (younger) siblings, then these are also added as siblings of the receiver.
- (id)removeChild:(SMKTree *)tree;
Detaches the indicated subtree from the tree (if it was indeed a child), and returns the subtree.
- (id)removeSibling:(SMKTree *)tree;
Detaches the indicated subtree from the tree (if it was indeed a sibling), and returns the subtree.
The children of an SMKTree node are indexed from 0. These methods give you access using indices:
- (id)insertChild:(SMKTree *)tree atIndex:(unsigned int)index;Inserts the tree at the given index, shifting the current occupant and later ones over. If no child is currently at the index, then the tree is simply added as the last child (as in addChild:). If the tree already has (younger) siblings, then these are inserted immediately after it.
- (id)childAtIndex:(unsigned int)index;
Returns the child at the given index, or nil if there is no child there.
Constructs and returns an NSMutableArray containing a list of the receiver's children. Because this is not the storage mechanism for the tree itself, adding objects to, and removing objects from, this array has no effect on the structure of the tree.
A path through an SMKTree corresponds to a list of nonnegative integers, as follows. Use the first integer to select a child of the root (as in childAtIndex:), the second integer to select a child of that, and so on, until the list is exhausted. By convention, all paths implicitly contain the root. For example, the path {1, 3, 0}, which has length three, includes four nodes: the root, its child of index 1, that node's child of index 3, and that node's child of index 0. Of course, if the list is too long, or one of its integers is too big, then the corresponding path does not actually exist in the tree, because the tree is not deep or wide enough to hold it.
The remaining SMKTree methods perform a variety of operations based on such paths. In each of them, you specify the array of integers and another integer giving its length. Each method returns the last found node along the path (except in the case of nodesAlongPath:ofLength:), and updates the length to reflect the number of unused entries. If the tree was deep and wide enough to hold the path, then the node returned is the end of the path, and the unused length is zero. The array of integers is always left unaltered.
- (id)endOfPath:(unsigned int *)path ofLength:(unsigned int *)length;Returns the node at the end of the path.
- (id)nodesAlongPath:(unsigned int *)path ofLength:(unsigned int *)length;
Returns an NSMutableArray containing the nodes along the path, in order, starting with the root. Because this is not the storage mechanism for the tree itself, adding objects to, and removing objects from, this array has no effect on the structure of the tree.
These path methods descend through the tree along the specified path, invoking variants of NSObject's performSelector: at each node. Remember that these return the last found node in the path, along with the unused length.
- (id)iterateSelector:(SEL)aSelector alongPath:(unsigned int *)path ofLength:(unsigned int *)length;Invokes performSelector: at each path node.
Invokes performSelector:withObject: at each path node.
Invokes performSelector:withObject:withObject: at each path node.
At each path node, invokes performSelector:, and then invokes performSelector: on that result.
At each path node, invokes performSelector:, and then invokes performSelector:withObject: on that result.
At each path node, invokes performSelector:, and then invokes performSelector:withObject:withObject: on that result.