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