1// 2// MyTree.m 3// celestia 4// 5// Created by Bob Ippolito on Thu Jun 20 2002. 6// Copyright (C) 2007, Celestia Development Team 7// 8 9#import "MyTree.h" 10// HACK 11#import "CelestiaFavorite.h" 12#import <objc/objc-class.h> 13@implementation MyVector 14-(void)encodeWithCoder:(NSCoder*)coder 15{ 16// NSLog(@"[MyVector encodeWithCoder:%@]",coder); 17 //[super encodeWithCoder:coder]; 18 [coder encodeObject:_array]; 19 //[coder encodeValueOfObjCType:@encode(Class) at:&_myClass]; 20} 21-(id)initWithCoder:(NSCoder*)coder 22{ 23// NSLog(@"[MyVector initWithCoder:%@]",coder); 24 //self = [super initWithCoder:coder]; 25 self = [self init]; 26 _array = [[coder decodeObject] retain]; 27 //[coder decodeValueOfObjCType:@encode(Class) at:&_myClass]; 28 return self; 29} 30-(id)init 31{ 32 self = [super init]; 33 _array = [[NSMutableArray arrayWithCapacity:0] retain]; 34 _myClass = [NSObject class]; 35 return self; 36} 37-(id)initWithClass:(Class)myClass 38{ 39 self = [self init]; 40 _myClass = myClass; 41 return self; 42} 43-(void)dealloc 44{ 45 [_array release]; 46 [super dealloc]; 47} 48-(void)addObject:(id)obj 49{ 50 if (![obj isKindOfClass:_myClass]) 51 [NSException raise:@"TypeError" format:@"%s invalid, only %s allowed",NAMEOF(obj),_myClass->name]; 52 [_array addObject:obj]; 53} 54-(void)insertObject:(id)obj atIndex:(unsigned)idx 55{ 56 if (![obj isKindOfClass:_myClass]) 57 [NSException raise:@"TypeError" format:@"%s invalid, only %s allowed",NAMEOF(obj),_myClass->name]; 58 [_array insertObject:obj atIndex:idx]; 59} 60-(void)removeLastObject 61{ 62 [_array removeLastObject]; 63} 64-(void)removeObjectAtIndex:(unsigned)idx 65{ 66 [_array removeObjectAtIndex:idx]; 67} 68-(void)replaceObjectAtIndex:(unsigned)idx withObject:(id)obj 69{ 70 if (![obj isKindOfClass:_myClass]) 71 [NSException raise:@"TypeError" format:@"%s invalid, only %s allowed",NAMEOF(obj),_myClass->name]; 72 [_array replaceObjectAtIndex:idx withObject:obj]; 73} 74-(unsigned)count 75{ 76 return [_array count]; 77} 78-(id)objectAtIndex:(unsigned)idx 79{ 80 return [_array objectAtIndex:idx]; 81} 82@end 83 84@implementation MyTree 85-(void)encodeWithCoder:(NSCoder*)coder 86{ 87// NSLog(@"[MyTree encodeWithCoder:%@]",coder); 88 //[super encodeWithCoder:coder]; 89 [coder encodeObject:_nodeValue]; 90 [coder encodeObject:_children]; 91} 92-(id)initWithCoder:(NSCoder*)coder 93{ 94// NSLog(@"[MyTree initWithCoder:%@]",coder); 95 //self = [super initWithCoder:coder]; 96 self = [self init]; 97 _parent = nil; 98 _nodeValue = [[coder decodeObject] retain]; 99 _children = [[coder decodeObject] retain]; 100 [_children makeObjectsPerformSelector:@selector(setParent:) withObject:self]; 101 return self; 102} 103-(id)init 104{ 105 self = [super init]; 106 _nodeValue = nil; 107 _children = nil; 108 _parent = nil; 109 return self; 110} 111-(void)dealloc 112{ 113// NSLog(@"[MyTree dealloc]"); 114// NSLog(@"%@",self); 115 if ([self nodeValue] != nil) 116 [[self nodeValue] autorelease]; 117 if ([self children] != nil) 118 [[self children] autorelease]; 119 _nodeValue = nil; 120 _children = nil; 121 _parent = nil; 122 [super dealloc]; 123} 124-(id)initWithNode:(id)obj parent:(MyTree*)parent 125{ 126 self = [self init]; 127 _nodeValue = [obj retain]; 128 _parent = parent; 129 _children = nil; 130 return self; 131} 132-(id)initWithNode:(id)obj parent:(MyTree*)parent children:(NSArray*)children 133{ 134 NSEnumerator* enumerator; 135 self = [self initWithNode:obj parent:parent]; 136 _children = [[MyVector alloc] initWithClass:[MyTree class]]; 137 enumerator = [children objectEnumerator]; 138 while ((obj = [enumerator nextObject]) != nil) 139 [_children addObject:obj]; 140 return self; 141} 142-(id)initWithDictionary:(NSDictionary*)dict parent:(MyTree*)parent 143{ 144 NSMutableArray* children = nil; 145 NSArray* origArray = nil; 146 NSEnumerator* enumerator = nil; 147 NSDictionary* childDict = nil; 148 id <NSCoding> nodeValue = nil; 149 // NSLog(@"[MyTree initWithDictionary:%@ parent:%@]",dict,parent); 150 // this part could use some work 151 nodeValue = [[[CelestiaFavorite alloc] initWithDictionary:[dict objectForKey:@"nodeValue"]] autorelease]; 152 // Leaf 153 if ((origArray = [dict objectForKey:@"children"]) == nil) 154 return [self initWithNode:nodeValue parent:parent]; 155 children = [[[MyVector alloc] initWithClass:[MyTree class]] autorelease]; 156 enumerator = [origArray objectEnumerator]; 157 while ((childDict = [enumerator nextObject]) != nil) 158 [children addObject:[[[MyTree alloc] initWithDictionary:childDict parent:self] autorelease]]; 159 return [self initWithNode:nodeValue parent:parent children:children]; 160} 161-(MyTree*)parent 162{ 163 return _parent; 164} 165-(MyVector*)children 166{ 167 return _children; 168} 169-(id)nodeValue 170{ 171 return _nodeValue; 172} 173-(BOOL)isLeaf 174{ 175 return (([self children] == nil) ? YES : NO); 176} 177-(void)setNode:(id)obj 178{ 179 if ([self nodeValue] != nil) 180 [[self nodeValue] autorelease]; 181 _nodeValue = [obj retain]; 182} 183-(void)setParent:(MyTree*)obj 184{ 185 _parent = obj; 186} 187-(void)setChildren:(NSArray*)children 188{ 189 NSEnumerator *enumerator = nil; 190 id obj = nil; 191 if ([self children] == nil) 192 [[self children] autorelease]; 193 if (children == nil) { 194 _children = nil; 195 return; 196 } 197 enumerator = [children objectEnumerator]; 198 _children = [[MyVector alloc] initWithClass:[MyTree class]]; 199 while ((obj = [enumerator nextObject]) != nil) 200 [_children addObject:obj]; 201} 202-(NSDictionary*)dictionary 203{ 204 return [NSDictionary dictionaryWithObjectsAndKeys:[[self nodeValue] dictionary],@"nodeValue",[NSNumber numberWithBool:[self isLeaf]],@"isLeaf",[self children],@"children",nil,nil]; 205} 206-(NSDictionary*)recursiveDictionary 207{ 208 NSMutableArray* array; 209 NSEnumerator* enumerator; 210 MyTree* obj; 211 if ([self isLeaf]) 212 return [self dictionary]; 213 enumerator = [[self children] objectEnumerator]; 214 array = [NSMutableArray arrayWithCapacity:[[self children] count]]; 215 while ((obj = [enumerator nextObject]) != nil) 216 [array addObject:[obj recursiveDictionary]]; 217 return [NSDictionary dictionaryWithObjectsAndKeys:[[self nodeValue] dictionary],@"nodeValue",[NSArray arrayWithArray:array],@"children",nil,nil]; 218} 219-(NSString*)description 220{ 221 return [[self dictionary] description]; 222} 223-(BOOL)isDescendantOfNode:(MyTree*)node 224{ 225 MyTree* parent = self; 226 if ([self isEqualTo:node]) 227 return YES; 228 while ((parent = [parent parent]) != nil) 229 if ([node isEqualTo:parent]) 230 return YES; 231 return NO; 232} 233-(BOOL)isDescendantOfNodeInArray:(NSArray*)array 234{ 235 NSEnumerator* enumerator = [array objectEnumerator]; 236 MyTree* node = nil; 237 while ((node = [enumerator nextObject]) != nil) 238 if ([self isDescendantOfNode:node] == YES) 239 return YES; 240 return NO; 241} 242 243- (void)insertChild:(MyTree*)child atIndex:(int)index { 244 [[self children] insertObject:child atIndex:index]; 245 [child setParent: self]; 246} 247 248- (void)insertChildren:(NSArray*)children atIndex:(int)index { 249 [[self children] insertObjectsFromArray: children atIndex: index]; 250 [children makeObjectsPerformSelector:@selector(setParent:) withObject:self]; 251} 252 253- (void)_removeChildrenIdenticalTo:(NSArray*)children { 254 MyTree *child; 255 NSEnumerator *childEnumerator = [children objectEnumerator]; 256 [children makeObjectsPerformSelector:@selector(setParent:) withObject:nil]; 257 while ((child = [childEnumerator nextObject]) != nil) { 258 [[self children] removeObjectIdenticalTo:child]; 259 } 260} 261 262- (void)removeChild:(MyTree*)child { 263 [[self children] removeObject:child]; 264/* 265 int index = [self indexOfChild: child]; 266 if (index != NSNotFound) { 267 [self _removeChildrenIdenticalTo: [NSArray arrayWithObject: [self childAtIndex:index]]]; 268 } 269*/ 270} 271 272- (void)removeFromParent { 273 [[self parent] removeChild:self]; 274} 275 276- (int)indexOfChild:(MyTree*)child { 277 return [[self children] indexOfObject:child]; 278} 279 280- (int)indexOfChildIdenticalTo:(MyTree*)child { 281 return [[self children] indexOfObjectIdenticalTo:child]; 282} 283 284- (int)numberOfChildren { 285 return [[self children] count]; 286} 287 288- (MyTree*)firstChild { 289 return [[self children] objectAtIndex:0]; 290} 291 292- (MyTree*)lastChild { 293 return [[self children] lastObject]; 294} 295 296- (MyTree*)childAtIndex:(int)index { 297 return [[self children] objectAtIndex:index]; 298} 299 300// Returns the minimum nodes from 'allNodes' required to cover the nodes in 'allNodes'. 301// This methods returns an array containing nodes from 'allNodes' such that no node in 302// the returned array has an ancestor in the returned array. 303 304// There are better ways to compute this, but this implementation should be efficient for our app. 305+ (NSArray *) minimumNodeCoverFromNodesInArray: (NSArray *)allNodes { 306 NSMutableArray *minimumCover = [NSMutableArray array]; 307 NSMutableArray *nodeQueue = [NSMutableArray arrayWithArray:allNodes]; 308 MyTree *node = nil; 309 while ([nodeQueue count]) { 310 node = [nodeQueue objectAtIndex:0]; 311 [nodeQueue removeObjectAtIndex:0]; 312 while ( [node parent] && [nodeQueue containsObjectIdenticalTo:[node parent]] ) { 313 [nodeQueue removeObjectIdenticalTo: node]; 314 node = [node parent]; 315 } 316 if (![node isDescendantOfNodeInArray: minimumCover]) [minimumCover addObject: node]; 317 [nodeQueue removeObjectIdenticalTo: node]; 318 } 319 return minimumCover; 320} 321 322@end