1/* 2 * TRArray.m vi:ts=4:sw=4:expandtab: 3 * Simple linked list 4 * 5 * Author: Landon Fuller <landonf@threerings.net> 6 * 7 * Copyright (c) 2006 Three Rings Design, Inc. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. Neither the name of the copyright holder nor the names of any contributors 19 * may be used to endorse or promote products derived from this 20 * software without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 23 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 26 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 28 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 29 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 30 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 31 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 32 * POSSIBILITY OF SUCH DAMAGE. 33 */ 34 35#import <stdlib.h> 36 37#import "TRArray.h" 38#import "xmalloc.h" 39 40typedef struct _TRArrayStack { 41 id object; 42 struct _TRArrayStack *prev; 43 struct _TRArrayStack *next; 44} TRArrayStack; 45 46/** 47 * Array enumerator. 48 */ 49@interface TRArrayObjectEnumerator : TREnumerator { 50 TRArray *_array; 51 TRArrayStack *_stack; 52} 53- (id) initWithArray: (TRArray *) array; 54@end 55 56/** 57 * Reverse array enumerator. 58 */ 59@interface TRArrayReverseObjectEnumerator : TRArrayObjectEnumerator 60@end 61 62/* 63 * We need to declare prototypes for our private methods, as some 64 * versions of gcc won't pick them up from the implementation. 65 */ 66@interface TRArray (TRArrayPrivate) 67- (TRArrayStack *) _privateArrayContext: (BOOL) top; 68@end 69 70/** 71 * A simple array implementation, provides forward and reverse 72 * enumerators. 73 */ 74@implementation TRArray 75 76- (id) init { 77 self = [super init]; 78 if (!self) 79 return self; 80 81 _count = 0; 82 83 /* Initialize our linked list */ 84 _stack = xmalloc(sizeof(TRArrayStack)); 85 _stack->object= nil; 86 _stack->next = NULL; 87 _stack->prev= NULL; 88 _stackBottom = _stack; 89 90 return self; 91} 92 93- (void) dealloc { 94 TRArrayStack *node; 95 96 /* Clean up our stack */ 97 for (node = _stack; _stack; node = _stack) { 98 /* Release the associated object */ 99 [node->object release]; 100 _stack = node->next; 101 free(node); 102 } 103 [super dealloc]; 104} 105 106- (unsigned int) count { 107 return _count; 108} 109 110/** 111 * Add anObject to the array. 112 * @param anObject: Object to add; 113 */ 114- (void) addObject: (id) anObject { 115 TRArrayStack *node; 116 117 /* Allocate, initialize, and push the new node on to the stack */ 118 node = xmalloc(sizeof(TRArrayStack)); 119 node->object = [anObject retain]; 120 node->prev = NULL; 121 node->next = _stack; 122 _stack->prev = node; 123 124 _stack = node; 125 _count++; 126} 127 128/** 129 * Remove top-most object from the array (LIFO). 130 */ 131- (void) removeObject { 132 TRArrayStack *node; 133 134 /* Pop the stack */ 135 node = _stack; 136 _stack = _stack->next; 137 _stack->prev = NULL; 138 139 /* Dealloc the removed node */ 140 [node->object release]; 141 free(node); 142 _count--; 143} 144 145/** 146 * Return the last object added to the array. 147 * @return Last object added to the array. 148 */ 149- (id) lastObject { 150 /* Return the last object on the stack */ 151 return _stack->object; 152} 153 154/** 155 * Test if the array contains anObject. 156 * Implemented by calling isEqual on all objects in the array. 157 * @param anObject: Object to test for equality. 158 * @return YES if the array contains anObject, NO otherwise. 159 */ 160- (BOOL) containsObject: (id) anObject { 161 TRArrayStack *node; 162 163 /* Anything claim to be equal with anObject? */ 164 for (node = _stack; node; node = node->next) { 165 if ([node->object isEqual: anObject]) 166 return YES; 167 } 168 169 return NO; 170} 171 172- (TRArrayStack *) _privateArrayContext: (BOOL) top { 173 if (top) 174 return _stack; 175 else 176 return _stackBottom; 177} 178 179/** 180 * Return a object enumerator. 181 * This enumerater walks the stack, 182 * implementing a LIFO interface. 183 * 184 * Due to our lack of an autorelease pool, 185 * it is the caller's responsibility to release 186 * the returned value. 187 */ 188- (TREnumerator *) objectEnumerator { 189 return [[[TRArrayObjectEnumerator alloc] initWithArray: self] autorelease]; 190} 191 192/** 193 * Return a object enumerator. 194 * This enumerater walks the stack in reverse, 195 * implementing a FIFO interface. 196 * 197 * Due to our lack of an autorelease pool, 198 * it is the caller's responsibility to release 199 * the returned value. 200 */ 201- (TREnumerator *) objectReverseEnumerator { 202 return [[[TRArrayReverseObjectEnumerator alloc] initWithArray: self] autorelease]; 203} 204 205 206 207@end /* TRArray */ 208 209@implementation TRArrayObjectEnumerator 210 211- (void) dealloc { 212 [_array release]; 213 [super dealloc]; 214} 215 216- (id) initWithArray: (TRArray *) array { 217 self = [super init]; 218 if (!self) 219 return self; 220 221 _array = [array retain]; 222 _stack = [array _privateArrayContext: YES]; 223 224 return self; 225} 226 227- (id) nextObject { 228 TRArrayStack *next; 229 230 if (!_stack) 231 return nil; 232 233 /* Pop the next node from the stack */ 234 next = _stack; 235 _stack = _stack->next; 236 237 /* Return the next node */ 238 return (next->object); 239} 240 241@end /* TRArrayObjectEnumerator */ 242 243@implementation TRArrayReverseObjectEnumerator 244 245- (id) initWithArray: (TRArray *) array { 246 self = [super init]; 247 if (!self) 248 return self; 249 250 /* We want the bottom-most element of the stack, 251 * skipping the NULL terminator */ 252 _stack = [array _privateArrayContext: NO]->prev; 253 254 return self; 255} 256 257- (id) nextObject { 258 TRArrayStack *prev; 259 260 if (!_stack) 261 return nil; 262 263 /* Walk the stack in reverse */ 264 prev = _stack; 265 _stack = _stack->prev; 266 267 /* Return the previous node */ 268 return (prev->object); 269} 270 271@end /* TRArrayObjectEnumerator */ 272