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