1// 2// TreeIterator.m 3// ANTLR 4// 5// Created by Ian Michell on 26/04/2010. 6// Copyright (c) 2010 Ian Michell 2010 Alan Condit 7// All rights reserved. 8// 9// Redistribution and use in source and binary forms, with or without 10// modification, are permitted provided that the following conditions 11// are met: 12// 1. Redistributions of source code must retain the above copyright 13// notice, this list of conditions and the following disclaimer. 14// 2. Redistributions in binary form must reproduce the above copyright 15// notice, this list of conditions and the following disclaimer in the 16// documentation and/or other materials provided with the distribution. 17// 3. The name of the author may not be used to endorse or promote products 18// derived from this software without specific prior written permission. 19// 20// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 21// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 22// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 23// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 24// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 25// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 29// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31 32#import "TreeIterator.h" 33#import "CommonTreeAdaptor.h" 34 35@implementation TreeIterator 36 37+ (TreeIterator *) newANTRLTreeIterator 38{ 39 return [[TreeIterator alloc] init]; 40} 41 42+ (TreeIterator *) newANTRLTreeIteratorWithAdaptor:(CommonTreeAdaptor *)adaptor 43 andTree:(id<BaseTree>)tree 44{ 45 return [[TreeIterator alloc] initWithTreeAdaptor:adaptor andTree:tree]; 46} 47 48- (id) init 49{ 50 self = [super init]; 51 if ( self != nil ) { 52 firstTime = YES; 53 nodes = [[FastQueue newFastQueue] retain]; 54 down = [[adaptor createTree:TokenTypeDOWN Text:@"DOWN"] retain]; 55 up = [[adaptor createTree:TokenTypeUP Text:@"UP"] retain]; 56 eof = [[adaptor createTree:TokenTypeEOF Text:@"EOF"] retain]; 57 tree = eof; 58 root = eof; 59 } 60 return self; 61} 62 63-(id) initWithTree:(id<BaseTree>) t 64{ 65 self = [super init]; 66 if ( self != nil ) { 67 firstTime = YES; 68 adaptor = [[CommonTreeAdaptor newTreeAdaptor] retain]; 69 tree = [t retain]; 70 root = t; 71 nodes = [[FastQueue newFastQueue] retain]; 72 down = [[adaptor createTree:TokenTypeDOWN Text:@"DOWN"] retain]; 73 up = [[adaptor createTree:TokenTypeUP Text:@"UP"] retain]; 74 eof = [[adaptor createTree:TokenTypeEOF Text:@"EOF"] retain]; 75 } 76 return self; 77} 78 79-(id) initWithTreeAdaptor:(id<TreeAdaptor>)a andTree:(id<BaseTree>)t 80{ 81 self = [super init]; 82 if ( self != nil ) { 83 firstTime = YES; 84 adaptor = [a retain]; 85 tree = [t retain]; 86 root = t; 87 nodes = [[FastQueue newFastQueue] retain]; 88 down = [[adaptor createTree:TokenTypeDOWN Text:@"DOWN"] retain]; 89 up = [[adaptor createTree:TokenTypeUP Text:@"UP"] retain]; 90 eof = [[adaptor createTree:TokenTypeEOF Text:@"EOF"] retain]; 91 } 92 return self; 93} 94 95- (void)dealloc 96{ 97#ifdef DEBUG_DEALLOC 98 NSLog( @"called dealloc in TreeIterator" ); 99#endif 100 if ( adaptor ) [adaptor release]; 101 if ( nodes ) [nodes release]; 102 if ( tree && tree != eof ) [tree release]; 103 if ( root && root != eof && root != tree ) [root release]; 104 if ( down ) [down release]; 105 if ( up ) [up release]; 106 if ( eof ) [eof release]; 107 [super dealloc]; 108} 109 110- (void)reset 111{ 112 firstTime = YES; 113 tree = root; 114 [nodes clear]; 115} 116 117-(BOOL) hasNext 118{ 119 if ( firstTime ) { 120 return root != nil; 121 } 122 if ( nodes && [nodes size] > 0) { 123 return YES; 124 } 125 if ( tree == nil ) { 126 return NO; 127 } 128 if ( [adaptor getChildCount:tree] > 0 ) { 129 return YES; 130 } 131 return [adaptor getParent:tree] != nil; 132} 133 134-(id) nextObject 135{ 136 // is this the first time we are using this method? 137 if ( firstTime ) { 138 firstTime = NO; 139 if ( [adaptor getChildCount:tree] == 0 ) { 140 [nodes addObject:eof]; 141 return tree; 142 } 143 return tree; 144 } 145 // do we have any objects queued up? 146 if ( nodes && [nodes size] > 0 ) { 147 return [nodes remove]; 148 } 149 // no nodes left? 150 if ( tree == nil ) { 151 return eof; 152 } 153 if ( [adaptor getChildCount:tree] > 0 ) { 154 tree = [adaptor getChild:tree At:0]; 155 [nodes addObject:tree]; // real node is next after down 156 return self.down; 157 } 158 // if no children, look for next sibling of ancestor 159 id<BaseTree> parent = [adaptor getParent:tree]; 160 while (parent != nil && ([adaptor getChildIndex:tree] + 1) >= [adaptor getChildCount:parent]) { 161 [nodes addObject:up]; 162 tree = parent; 163 parent = [adaptor getParent:tree]; 164 } 165 if ( parent == nil ) { 166 tree = nil; 167 [nodes addObject:self.eof]; 168 return [nodes remove]; 169 } 170 // must have found a node with an unvisited sibling 171 // move to it and return it 172 NSInteger nextSiblingIndex = [adaptor getChildIndex:tree] + 1; 173 tree = [adaptor getChild:parent At:nextSiblingIndex]; 174 [nodes addObject:tree]; 175 return [nodes remove]; 176} 177 178-(NSArray *) allObjects 179{ 180 AMutableArray *array = [AMutableArray arrayWithCapacity:10]; 181 while ( [self hasNext] ) { 182 [array addObject:[self nextObject]]; 183 } 184 return array; 185} 186 187- (void)remove 188{ 189 @throw [RuntimeException newException:@"UnsupportedOperationException"]; 190} 191 192@synthesize firstTime; 193@synthesize adaptor; 194@synthesize root; 195@synthesize tree; 196@synthesize nodes; 197 198@synthesize up; 199@synthesize down; 200@synthesize eof; 201 202@end 203