This is MiscTree.m in view mode; [Download] [Up]
/* MiscTree.m
Copyright 1995 Christopher J. Kane.
This notice may not be removed from this source code.
The use and distribution of this software is governed by the
terms of the MiscKit license agreement. Refer to the license
document included with the MiscKit distribution for the terms.
Version 1 (1 February 1995)
*/
#import <MiscTree.h>
#import <MiscUtilities.h>
#import <Foundation/Foundation.h>
/**************** Foundation extensions ****************/
@interface NSArray (MiscTreeNSArrayExtensions)
+ (NSArray *)arrayWithEnumerator:(NSEnumerator *)enumerator;
@end
@implementation NSArray (MiscTreeNSArrayExtensions)
+ (NSArray *)arrayWithEnumerator:(NSEnumerator *)enumerator {
NSMutableArray *newArray = [NSMutableArray array];
id obj;
while ((obj = [enumerator nextObject]))
[newArray addObject:obj];
return newArray;
}
@end
/**************** Enumerators ****************/
@interface _MiscTreeAncestorEnumerator : NSEnumerator
{
MiscTree *_tree;
}
- (id)initWithTree:(MiscTree *)aTree;
@end
@implementation _MiscTreeAncestorEnumerator
- (id)initWithTree:(MiscTree *)aTree {
NSParameterAssert(nil != aTree);
NSParameterAssert([aTree isKindOfClass:[MiscTree class]]);
self = [super init];
NSAssert(nil != self, @"object super initialization failed");
_tree = [aTree retain];
return self;
}
- (id)nextObject {
_tree = [_tree parentTree];
return _tree;
}
- (void)dealloc {
[_tree autorelease];
[super dealloc];
}
@end
@interface _MiscTreeSiblingEnumerator : NSEnumerator
{
MiscTree *_tree;
NSEnumerator *_subEnumerator;
}
- (id)initWithTree:(MiscTree *)aTree;
@end
@implementation _MiscTreeSiblingEnumerator
- (id)initWithTree:(MiscTree *)aTree {
NSParameterAssert(nil != aTree);
NSParameterAssert([aTree isKindOfClass:[MiscTree class]]);
self = [super init];
NSAssert(nil != self, @"object super initialization failed");
_tree = [aTree retain];
_subEnumerator = [[[aTree parentTree] subtreeEnumerator] retain];
return self;
}
- (id)nextObject {
id obj = [_subEnumerator nextObject];
if (obj == _tree)
obj = [_subEnumerator nextObject];
return obj;
}
- (void)dealloc {
[_tree autorelease];
[_subEnumerator release];
[super dealloc];
}
@end
@interface _MiscTreePreorderSubtreeEnumerator : NSEnumerator
{
MiscTree *_tree;
NSEnumerator *_subtreeEnumerator;
NSEnumerator *_subEnumerator;
}
- (id)initWithTree:(MiscTree *)aTree;
@end
@implementation _MiscTreePreorderSubtreeEnumerator
- (id)initWithTree:(MiscTree *)aTree {
NSParameterAssert(nil != aTree);
NSParameterAssert([aTree isKindOfClass:[MiscTree class]]);
self = [super init];
NSAssert(nil != self, @"object super initialization failed");
_tree = [aTree retain];
_subtreeEnumerator = [[aTree subtreeEnumerator] retain];
_subEnumerator = nil;
return self;
}
- (id)nextObject {
id nextSubtree;
if (_tree != nil) {
id t = _tree;
[_tree autorelease];
_tree = nil;
return t;
}
if (_subEnumerator != nil) {
id obj = [_subEnumerator nextObject];
if (obj != nil)
return obj;
[_subEnumerator release];
_subEnumerator = nil;
}
nextSubtree = [_subtreeEnumerator nextObject];
if (nextSubtree == nil)
return nil;
_subEnumerator = [[nextSubtree preorderAllSubtreeEnumerator] retain];
return [self nextObject];
}
- (void)dealloc {
[_tree autorelease];
[_subtreeEnumerator release];
[_subEnumerator release];
[super dealloc];
}
@end
@interface _MiscTreePostorderSubtreeEnumerator : NSEnumerator
{
MiscTree *_tree;
NSEnumerator *_subtreeEnumerator;
NSEnumerator *_subEnumerator;
}
- (id)initWithTree:(MiscTree *)aTree;
@end
@implementation _MiscTreePostorderSubtreeEnumerator
- (id)initWithTree:(MiscTree *)aTree {
NSParameterAssert(nil != aTree);
NSParameterAssert([aTree isKindOfClass:[MiscTree class]]);
self = [super init];
NSAssert(nil != self, @"object super initialization failed");
_tree = [aTree retain];
_subtreeEnumerator = [[aTree subtreeEnumerator] retain];
_subEnumerator = nil;
return self;
}
- (id)nextObject {
id nextSubtree;
if (_tree == nil)
return nil;
if (_subEnumerator != nil) {
id obj = [_subEnumerator nextObject];
if (obj != nil)
return obj;
[_subEnumerator release];
_subEnumerator = nil;
}
nextSubtree = [_subtreeEnumerator nextObject];
if (nextSubtree == nil) {
id t = _tree;
[_tree autorelease];
_tree = nil;
return t;
}
_subEnumerator = [[nextSubtree postorderAllSubtreeEnumerator] retain];
return [self nextObject];
}
- (void)dealloc {
[_tree autorelease];
[_subtreeEnumerator release];
[_subEnumerator release];
[super dealloc];
}
@end
/**************** Abstract implementation ****************/
@interface MiscConcreteTree : MiscTree
{
id _userInfo;
MiscTree *_parentTree;
NSMutableArray *_subtrees;
}
@end
@implementation MiscTree
+ (MiscTree *)allocWithZone:(NSZone *)zone {
Class class = self;
if ([MiscTree class] == class)
class = [MiscConcreteTree class];
return (MiscTree *)NSAllocateObject(class, 0, zone);
}
- (id)init {
MiscRequiresConcreteObject(self, _cmd);
return nil;
}
- (id)userInfo {
MiscRequiresConcreteImplementation(self, _cmd, [MiscTree class]);
return nil;
}
- (void)setUserInfo:(id)anObjectOrNil {
MiscRequiresConcreteImplementation(self, _cmd, [MiscTree class]);
}
- (MiscTree *)parentTree {
MiscRequiresConcreteImplementation(self, _cmd, [MiscTree class]);
return nil;
}
- (void)setParentTree:(MiscTree *)aTreeOrNil {
MiscRequiresConcreteImplementation(self, _cmd, [MiscTree class]);
}
- (void)addSubtree:(MiscTree *)aTree {
MiscRequiresConcreteImplementation(self, _cmd, [MiscTree class]);
}
- (BOOL)isSubtree:(MiscTree *)aTree {
MiscRequiresConcreteImplementation(self, _cmd, [MiscTree class]);
return NO;
}
- (void)removeSubtree:(MiscTree *)aTree {
MiscRequiresConcreteImplementation(self, _cmd, [MiscTree class]);
}
- (unsigned int)subtreeCount {
MiscRequiresConcreteImplementation(self, _cmd, [MiscTree class]);
return 0;
}
- (NSEnumerator *)subtreeEnumerator {
MiscRequiresConcreteImplementation(self, _cmd, [MiscTree class]);
return nil;
}
- (BOOL)isEqual:(id)anObject {
NSParameterAssert(nil != anObject);
return (anObject == self) || [self isEqualToTree:anObject];
}
- (id)copyWithZone:(NSZone *)zone {
MiscTree *newTree = [[isa allocWithZone:zone] init];
NSEnumerator *enumerator = [self subtreeEnumerator];
id obj;
NSAssert(nil != newTree, @"could not create new tree");
while ((obj = [enumerator nextObject])) {
id newSubtree = [obj copyWithZone:zone];
NSAssert(nil != newSubtree, @"could not copy subtree");
[newTree addSubtree:newSubtree];
}
return newTree;
}
- (Class)classForCoder {
return [MiscTree class];
}
- (void)encodeWithCoder:(NSCoder *)encoder {
NSEnumerator *enumerator = [self subtreeEnumerator];
unsigned int count = [self subtreeCount];
id obj, userInfo = [self userInfo];
[encoder encodeValueOfObjCType:@encode(id) at:&userInfo];
[encoder encodeValueOfObjCType:@encode(int) at:&count];
while ((obj = [enumerator nextObject]))
[encoder encodeValueOfObjCType:@encode(id) at:&obj];
}
- (id)initWithCoder:(NSCoder *)decoder {
unsigned int count;
id userInfo;
[self init];
[decoder decodeValueOfObjCType:@encode(id) at:&userInfo];
[self setUserInfo:userInfo];
[userInfo release];
[decoder decodeValueOfObjCType:@encode(int) at:&count];
while (count--) {
id obj;
[decoder decodeValueOfObjCType:@encode(id) at:&obj];
[self addSubtree:obj];
[obj release];
}
return self;
}
@end
@implementation MiscTree (MiscTreeExtensions)
+ (MiscTree *)tree {
return [[[self alloc] init] autorelease];
}
+ (MiscTree *)treeWithSubtreesFromArray:(NSArray *)anArray {
NSParameterAssert([anArray isKindOfClass:[NSArray class]]);
return [[[self alloc] initWithEnumerator:[anArray objectEnumerator]] autorelease];
}
+ (MiscTree *)treeWithSubtrees:(MiscTree *)firstObj, ... {
MiscTree *result = [self tree];
if (firstObj) {
va_list args;
id obj;
va_start(args, firstObj);
while ((obj = va_arg(args, id)))
[result addSubtree:obj];
va_end(args);
}
return result;
}
- (id)initWithEnumerator:(NSEnumerator *)enumerator {
self = [self init];
NSAssert(nil != self, @"object super initialization failed");
[self addSubtreesWithEnumerator:enumerator];
return self;
}
- (id)initWithSubtrees:(MiscTree *)firstObj, ... {
self = [self init];
NSAssert(nil != self, @"object super initialization failed");
if (firstObj) {
va_list args;
id obj;
va_start(args, firstObj);
while ((obj = va_arg(args, id)))
[self addSubtree:obj];
va_end(args);
}
return self;
}
- (BOOL)isLeaf {
return 0 == [self subtreeCount];
}
- (MiscTree *)rootTree {
id currentTree, nextTree;
if (nil == [self parentTree])
return self;
for (currentTree = [self parentTree], nextTree = [currentTree parentTree]; nextTree != nil; currentTree = nextTree, nextTree = [currentTree parentTree]);
return [[currentTree retain] autorelease];
}
- (unsigned int)treeDegree {
unsigned int count = [self subtreeCount];
unsigned int max = count;
if (0 != count) {
NSEnumerator *enumerator = [self subtreeEnumerator];
id obj;
while ((obj = [enumerator nextObject])) {
unsigned int d = [obj treeDegree];
if (max < d)
max = d;
}
}
return max;
}
- (unsigned int)treeHeight {
NSEnumerator *enumerator = [self subtreeEnumerator];
unsigned int max = 0;
id obj;
while ((obj = [enumerator nextObject])) {
unsigned int h = [obj treeHeight];
if (max < h)
max = h;
}
return max + 1;
}
- (unsigned int)treeLevel {
id currentTree;
unsigned int level = 1;
for (currentTree = [self parentTree]; currentTree != nil; level++, currentTree = [currentTree parentTree]);
return level;
}
- (NSArray *)subtrees {
return [NSArray arrayWithEnumerator:[self subtreeEnumerator]];
}
- (void)addSubtreesWithEnumerator:(NSEnumerator *)enumerator {
id obj;
NSParameterAssert([enumerator isKindOfClass:[NSEnumerator class]]);
while ((obj = [enumerator nextObject]))
[self addSubtree:obj];
}
- (void)replaceSubtree:(MiscTree *)subtree withTree:(MiscTree *)aTree {
NSEnumerator *enumerator = [self subtreeEnumerator];
unsigned int count = 0;
id obj;
NSParameterAssert([subtree isKindOfClass:[MiscTree class]]);
NSParameterAssert([aTree isKindOfClass:[MiscTree class]]);
while ((obj = [enumerator nextObject]))
if ([subtree isEqual:obj])
count++;
if (0 != count)
[self removeSubtree:subtree];
while (count--)
[self addSubtree:aTree];
}
- (void)removeAllSubtrees {
NSMutableSet *objSet = [NSMutableSet set];
NSEnumerator *enumerator;
id obj;
enumerator = [self subtreeEnumerator];
while ((obj = [enumerator nextObject]))
[objSet addObject:obj];
enumerator = [objSet objectEnumerator];
while ((obj = [enumerator nextObject]))
[self removeSubtree:obj];
}
- (void)makeSubtreesPerform:(SEL)aSelector {
[[self subtrees] makeObjectsPerform:aSelector];
}
- (void)makeSubtreesPerform:(SEL)aSelector withObject:(id)anObject {
[[self subtrees] makeObjectsPerform:aSelector withObject:anObject];
}
- (NSEnumerator *)ancestorEnumerator {
return [[[_MiscTreeAncestorEnumerator allocWithZone:[self zone]] initWithTree:self] autorelease];
}
- (NSEnumerator *)siblingEnumerator {
return [[[_MiscTreeSiblingEnumerator allocWithZone:[self zone]] initWithTree:self] autorelease];
}
- (NSEnumerator *)preorderAllSubtreeEnumerator {
return [[[_MiscTreePreorderSubtreeEnumerator allocWithZone:[self zone]] initWithTree:self] autorelease];
}
- (NSEnumerator *)postorderAllSubtreeEnumerator {
return [[[_MiscTreePostorderSubtreeEnumerator allocWithZone:[self zone]] initWithTree:self] autorelease];
}
- (BOOL)isAnySubtree:(MiscTree *)aTree {
NSEnumerator *enumerator;
id obj;
NSParameterAssert([aTree isKindOfClass:[MiscTree class]]);
if ([self isSubtree:aTree])
return YES;
enumerator = [self subtreeEnumerator];
while ((obj = [enumerator nextObject]))
if ([obj isAnySubtree:aTree])
return YES;
return NO;
}
- (BOOL)isEqualToTree:(MiscTree *)otherTree {
NSEnumerator *enumerator1, *enumerator2;
id obj1, obj2;
NSParameterAssert(nil != otherTree);
if (![otherTree isKindOfClass:[MiscTree class]])
return NO;
enumerator1 = [self subtreeEnumerator];
enumerator2 = [otherTree subtreeEnumerator];
while ((obj1 = [enumerator1 nextObject])) {
obj2 = [enumerator2 nextObject];
if (obj2 == nil)
return NO;
if (![self isSubtree:obj2] || ![otherTree isSubtree:obj1])
return NO;
}
if ((obj2 = [enumerator2 nextObject]))
return NO;
return YES;
}
- (NSComparisonResult)compare:(id)otherTree {
id userInfo, otherUserInfo;
NSParameterAssert([otherTree isKindOfClass:[MiscTree class]]);
userInfo = [self userInfo];
otherUserInfo = [otherTree userInfo];
if (userInfo == otherUserInfo)
return NSOrderedSame;
if (![userInfo respondsToSelector:_cmd])
[NSException raise:NSInvalidArgumentException format:@"userInfo of receiver does not respond to -compare:"];
if (![otherUserInfo respondsToSelector:_cmd])
[NSException raise:NSInvalidArgumentException format:@"userInfo of argument does not respond to -compare:"];
return [userInfo compare:otherUserInfo];
}
- (NSString *)description {
return [self descriptionWithLocale:nil];
}
- (NSString *)descriptionWithLocale:(NSDictionary *)locale {
NSMutableDictionary *newDictionary = [NSMutableDictionary dictionary];
[newDictionary setObject:[self userInfo] forKey:@"UserInfo"];
[newDictionary setObject:[self subtrees] forKey:@"Subtrees"];
return [newDictionary descriptionWithLocale:locale];
}
@end
/**************** Concrete implementation ****************/
@implementation MiscConcreteTree
- (id)init {
_parentTree = _userInfo = nil;
_subtrees = [[NSMutableArray allocWithZone:[self zone]] init];
return self;
}
- (void)dealloc {
[_userInfo autorelease];
[_parentTree autorelease];
[_subtrees release];
[super dealloc];
}
- (id)userInfo {
return [[_userInfo retain] autorelease];
}
- (void)setUserInfo:(id)anObjectOrNil {
[anObjectOrNil retain];
[_userInfo autorelease];
_userInfo = anObjectOrNil;
}
- (MiscTree *)parentTree {
return [[_parentTree retain] autorelease];
}
- (void)setParentTree:(MiscTree *)aTreeOrNil {
NSParameterAssert(nil == aTreeOrNil || [aTreeOrNil isKindOfClass:[MiscTree class]]);
[aTreeOrNil retain];
[_parentTree autorelease];
_parentTree = aTreeOrNil;
}
- (void)addSubtree:(MiscTree *)aTree {
NSParameterAssert([aTree isKindOfClass:[MiscTree class]]);
[_subtrees addObject:aTree];
[aTree setParentTree:self];
}
- (BOOL)isSubtree:(MiscTree *)aTree {
NSParameterAssert([aTree isKindOfClass:[MiscTree class]]);
return [_subtrees containsObject:aTree];
}
- (void)removeSubtree:(MiscTree *)aTree {
NSParameterAssert([aTree isKindOfClass:[MiscTree class]]);
[aTree setParentTree:nil];
[_subtrees removeObject:aTree];
}
- (unsigned int)subtreeCount {
return [_subtrees count];
}
- (NSEnumerator *)subtreeEnumerator {
return [_subtrees objectEnumerator];
}
/* Methods below implemented only for efficiency */
- (void)removeAllSubtrees {
[_subtrees makeObjectsPerform:@selector(setParentTree:) withObject:nil];
[_subtrees removeAllObjects];
}
- (void)makeSubtreesPerform:(SEL)aSelector {
[_subtrees makeObjectsPerform:aSelector];
}
- (void)makeSubtreesPerform:(SEL)aSelector withObject:(id)anObject {
[_subtrees makeObjectsPerform:aSelector withObject:anObject];
}
@end
/**************** Other Concrete MiscTrees ****************/
/**************** Enumerators ****************/
@interface _MiscBinarySearchTreeSubtreeEnumerator : NSEnumerator
{
MiscBinarySearchTree *_leftSubtree;
MiscBinarySearchTree *_rightSubtree;
}
- (id)initWithTree:(MiscTree *)aTree;
@end
@implementation _MiscBinarySearchTreeSubtreeEnumerator
- (id)initWithTree:(MiscTree *)aTree {
NSParameterAssert(nil != aTree);
NSParameterAssert([aTree isKindOfClass:[MiscBinarySearchTree class]]);
self = [super init];
NSAssert(nil != self, @"object super initialization failed");
_leftSubtree = [[(MiscBinarySearchTree *)aTree leftSubtree] retain];
_rightSubtree = [[(MiscBinarySearchTree *)aTree rightSubtree] retain];
return self;
}
- (id)nextObject {
id result;
if (nil != _leftSubtree) {
result = _leftSubtree;
[_leftSubtree autorelease];
_leftSubtree = nil;
return result;
}
result = _rightSubtree;
[_rightSubtree autorelease];
_rightSubtree = nil;
return result;
}
- (void)dealloc {
[_leftSubtree autorelease];
[_rightSubtree autorelease];
[super autorelease];
}
@end
@interface _MiscTreeInorderSubtreeEnumerator : NSEnumerator
{
MiscBinarySearchTree *_tree;
NSEnumerator *_subEnumerator;
}
- (id)initWithTree:(MiscTree *)aTree;
@end
@implementation _MiscTreeInorderSubtreeEnumerator
- (id)initWithTree:(MiscTree *)aTree {
NSParameterAssert(nil != aTree);
NSParameterAssert([aTree isKindOfClass:[MiscBinarySearchTree class]]);
self = [super init];
NSAssert(nil != self, @"object super initialization failed");
_tree = [aTree retain];
_subEnumerator = [[[_tree leftSubtree] inorderAllSubtreeEnumerator] retain];
return self;
}
- (id)nextObject {
id nextSubtree;
if (_subEnumerator != nil) {
id obj = [_subEnumerator nextObject];
if (obj != nil)
return obj;
[_subEnumerator release];
_subEnumerator = nil;
}
if (nil == _tree)
return nil;
nextSubtree = _tree;
[_tree autorelease];
_tree = nil;
_subEnumerator = [[[_tree rightSubtree] inorderAllSubtreeEnumerator] retain];
return nextSubtree;
}
- (void)dealloc {
[_tree autorelease];
[_subEnumerator release];
[super dealloc];
}
@end
/**************** Concrete implementation ****************/
@implementation MiscBinarySearchTree
- (id)init {
_parentTree = _userInfo = _leftSubtree = _rightSubtree = nil;
return self;
}
- (void)dealloc {
[_userInfo autorelease];
[_parentTree autorelease];
[_leftSubtree autorelease];
[_rightSubtree autorelease];
[super dealloc];
}
- (id)userInfo {
return [[_userInfo retain] autorelease];
}
- (void)setUserInfo:(id)anObject {
NSParameterAssert([anObject respondsToSelector:@selector(compare:)]);
[anObject retain];
[_userInfo autorelease];
_userInfo = anObject;
}
- (MiscTree *)parentTree {
return [[_parentTree retain] autorelease];
}
- (void)setParentTree:(MiscTree *)aTreeOrNil {
NSParameterAssert(nil == aTreeOrNil || [aTreeOrNil isKindOfClass:[MiscBinarySearchTree class]]);
[aTreeOrNil retain];
[_parentTree autorelease];
_parentTree = (MiscBinarySearchTree *)aTreeOrNil;
}
- (void)addSubtree:(MiscTree *)aTree {
NSParameterAssert([aTree isKindOfClass:[MiscBinarySearchTree class]]);
if (nil == _leftSubtree)
_leftSubtree = [aTree retain];
else if (nil == _rightSubtree)
_rightSubtree = [aTree retain];
else
[NSException raise:NSRangeException format:@"Attempt to add a subtree to a tree that has two subtrees"];
}
- (BOOL)isSubtree:(MiscTree *)aTree {
NSParameterAssert([aTree isKindOfClass:[MiscBinarySearchTree class]]);
return ([_leftSubtree isEqualToTree:aTree] || [_rightSubtree isEqualToTree:aTree]);
}
- (void)removeSubtree:(MiscTree *)aTree {
NSParameterAssert([aTree isKindOfClass:[MiscBinarySearchTree class]]);
if ([_rightSubtree isEqualToTree:aTree]) {
[_rightSubtree autorelease];
_rightSubtree = nil;
}
if ([_leftSubtree isEqualToTree:aTree]) {
[_leftSubtree autorelease];
_leftSubtree = nil;
if (nil != _rightSubtree) {
_leftSubtree = _rightSubtree;
_rightSubtree = nil;
}
}
}
- (unsigned int)subtreeCount {
return (nil == _leftSubtree) ? 0 : (nil == _rightSubtree ? 1 : 2);
}
- (NSEnumerator *)subtreeEnumerator {
return [[[_MiscBinarySearchTreeSubtreeEnumerator allocWithZone:[self zone]] initWithTree:self] autorelease];
}
/**************** Methods Added by MiscBinarySearchTree ****************/
- (id)key {
return [self userInfo];
}
- (void)setKey:(id)anObject {
[self setUserInfo:anObject];
}
- (MiscBinarySearchTree *)leftSubtree {
return [[_leftSubtree retain] autorelease];
}
- (void)setLeftSubtree:(MiscBinarySearchTree *)aTreeOrNil {
NSParameterAssert(nil == aTreeOrNil || [aTreeOrNil isKindOfClass:[MiscBinarySearchTree class]]);
if (nil == aTreeOrNil && nil != _rightSubtree)
[NSException raise:NSInvalidArgumentException format:@"Attempt set left subtree to nil, but right subtree is not nil"];
[_leftSubtree autorelease];
_leftSubtree = aTreeOrNil;
}
- (MiscBinarySearchTree *)rightSubtree {
return [[_rightSubtree retain] autorelease];
}
- (void)setRightSubtree:(MiscBinarySearchTree *)aTreeOrNil {
NSParameterAssert(nil == aTreeOrNil || [aTreeOrNil isKindOfClass:[MiscBinarySearchTree class]]);
if (nil != aTreeOrNil && nil == _leftSubtree)
[NSException raise:NSInvalidArgumentException format:@"Attempt set right subtree to non-nil, but left subtree is nil"];
[_rightSubtree autorelease];
_rightSubtree = aTreeOrNil;
}
- (MiscBinarySearchTree *)treeWithKey:(id)aKey {
NSComparisonResult ordering;
NSParameterAssert([aKey respondsToSelector:@selector(compare:)]);
ordering = [[self userInfo] compare:aKey];
while (nil != self && NSOrderedSame != ordering) {
self = (NSOrderedDescending == ordering) ? _leftSubtree : _rightSubtree;
ordering = [[self userInfo] compare:aKey];
}
return [[self retain] autorelease];
}
- (MiscBinarySearchTree *)treeWithMinimumKey {
while (nil != _leftSubtree)
self = _leftSubtree;
return self;
}
- (MiscBinarySearchTree *)treeWithMaximumKey {
while (nil != _rightSubtree)
self = _rightSubtree;
return self;
}
- (MiscBinarySearchTree *)treeSuccessor {
if (nil != _rightSubtree)
return [_rightSubtree treeWithMinimumKey];
while (nil != _parentTree && self == _parentTree->_rightSubtree)
self = _parentTree;
return _parentTree;
}
- (MiscBinarySearchTree *)treePredecessor {
if (nil != _leftSubtree)
return [_leftSubtree treeWithMaximumKey];
while (nil != _parentTree && self == _parentTree->_leftSubtree)
self = _parentTree;
return _parentTree;
}
- (NSEnumerator *)inorderAllSubtreeEnumerator {
return [[[_MiscTreeInorderSubtreeEnumerator allocWithZone:[self zone]] initWithTree:self] autorelease];
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.