err.no Git - sope/blob - sope-core/NGExtensions/NGStack.m

   1 /*
   2   Copyright (C) 2000-2003 SKYRIX Software AG
   3
   4   This file is part of OGo
   5
   6   OGo is free software; you can redistribute it and/or modify it under
   7   the terms of the GNU Lesser General Public License as published by the
   8   Free Software Foundation; either version 2, or (at your option) any
   9   later version.
  10
  11   OGo is distributed in the hope that it will be useful, but WITHOUT ANY
  12   WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  14   License for more details.
  15
  16   You should have received a copy of the GNU Lesser General Public
  17   License along with OGo; see the file COPYING.  If not, write to the
  18   Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19   02111-1307, USA.
  20 */
  21 // $Id$
  22
  23 #include "common.h"
  24 #include "NGStack.h"
  25 #include "NGMemoryAllocation.h"
  26
  27 @interface _NGConcreteStackEnumerator : NSEnumerator
  28 {
  29   NGStack  *stack; // for retain
  30   id       *trace;
  31   unsigned toGo;
  32   BOOL     downWard; // top=>down
  33 }
  34
  35 - (id)initWithStack:(NGStack *)_stack trace:(id *)_ptr count:(int)_size
  36   topDown:(BOOL)_downWard;
  37
  38 - (id)nextObject;
  39
  40 @end
  41
  42 @implementation NGStack
  43
  44 + (id)stackWithCapacity:(unsigned int)_capacity {
  45   return [[[self alloc] initWithCapacity:_capacity] autorelease];
  46 }
  47 + (id)stack {
  48   return [[[self alloc] init] autorelease];
  49 }
  50 + (id)stackWithArray:(NSArray *)_array {
  51   return [[[self alloc] initWithArray:_array] autorelease];
  52 }
  53
  54 - (id)init {
  55   return [self initWithCapacity:256];
  56 }
  57 - (id)initWithCapacity:(unsigned int)_capacity {
  58   if ((self = [super init])) {
  59     stackPointer = 0;
  60     capacity     = (_capacity > 0) ? _capacity : 16;
  61
  62     stack = NGMalloc(sizeof(id) * capacity);
  63   }
  64   return self;
  65 }
  66 - (id)initWithArray:(NSArray *)_array {
  67   register unsigned int count = [_array count];
  68
  69   if ((self = [self initWithCapacity:(count + 1)])) {
  70     unsigned cnt;
  71
  72     for (cnt = 0; cnt < count; cnt++)
  73       [self push:[_array objectAtIndex:cnt]];
  74   }
  75   return self;
  76 }
  77
  78 - (void)dealloc {
  79   if (self->stack) {
  80     [self clear];
  81     NGFree(self->stack);
  82   }
  83   [super dealloc];
  84 }
  85
  86 /* sizing */
  87
  88 - (void)_increaseStack {
  89   if (capacity > 256) capacity += 256;
  90   else capacity *= 2;
  91
  92   stack = NGRealloc(stack, sizeof(id) * capacity);
  93 }
  94
  95 /* state */
  96
  97 - (unsigned int)capacity {
  98   return capacity;
  99 }
 100 - (unsigned int)stackPointer {
 101   return stackPointer;
 102 }
 103 - (unsigned int)count {
 104   return stackPointer;
 105 }
 106 - (BOOL)isEmpty {
 107   return (stackPointer == 0);
 108 }
 109
 110 /* operations */
 111
 112 - (void)push:(id)_obj {
 113   stackPointer++;
 114   if (stackPointer >= capacity) [self _increaseStack];
 115   stack[stackPointer] = [_obj retain];
 116 }
 117
 118 - (id)pop {
 119   id obj = stack[stackPointer];
 120   if (stackPointer <= 0) {
 121     [[[NGStackException alloc] initWithName:@"StackException"
 122       reason:@"tried to pop an object from an empty stack !"
 123       userInfo:nil] raise];
 124   }
 125   stack[stackPointer] = nil;
 126   stackPointer--;
 127   return [obj autorelease];
 128 }
 129
 130 - (void)clear {
 131   unsigned cnt;
 132   for (cnt = 1; cnt <= stackPointer; cnt++) {
 133 #if !LIB_FOUNDATION_BOEHM_GC
 134     [stack[cnt] release];
 135 #endif
 136     stack[cnt] = nil;
 137   }
 138   stackPointer = 0;
 139 }
 140
 141 /* elements */
 142
 143 - (id)elementAtTop {
 144   return (stackPointer == 0) ? nil : stack[stackPointer];
 145 }
 146 - (id)elementAtBottom {
 147   return (stackPointer == 0) ? nil : stack[1];
 148 }
 149
 150 - (NSEnumerator *)topDownEnumerator {
 151   if (stackPointer == 0)
 152     return nil;
 153
 154   return [[[_NGConcreteStackEnumerator alloc]
 155                         initWithStack:self trace:&(stack[stackPointer])
 156                         count:stackPointer topDown:YES] autorelease];
 157 }
 158 - (NSEnumerator *)bottomUpEnumerator {
 159   if (stackPointer == 0)
 160     return nil;
 161
 162   return [[[_NGConcreteStackEnumerator alloc]
 163                         initWithStack:self trace:&(stack[1])
 164                         count:stackPointer topDown:NO] autorelease];
 165 }
 166
 167 /* NSCoding */
 168
 169 - (Class)classForCoder {
 170   return [NGStack class];
 171 }
 172
 173 - (void)encodeWithCoder:(NSCoder *)_encoder {
 174   unsigned cnt;
 175
 176   [_encoder encodeValueOfObjCType:@encode(unsigned int) at:&capacity];
 177   [_encoder encodeValueOfObjCType:@encode(unsigned int) at:&stackPointer];
 178
 179   for (cnt = 1; cnt <= stackPointer; cnt++) {
 180     id obj = stack[cnt];
 181     [_encoder encodeObject:obj];
 182   }
 183 }
 184
 185 - (id)initWithCoder:(NSCoder *)_decoder {
 186   int tmpCapacity;
 187   int tmpStackPointer;
 188
 189   [_decoder decodeValueOfObjCType:@encode(unsigned int) at:&tmpCapacity];
 190   [_decoder decodeValueOfObjCType:@encode(unsigned int) at:&tmpStackPointer];
 191
 192   self = [self initWithCapacity:tmpCapacity];
 193   {
 194     register int cnt;
 195
 196     for (cnt = 1; cnt <= tmpStackPointer; cnt++) {
 197       id obj = [_decoder decodeObject];
 198       stack[cnt] = [obj retain];
 199     }
 200     stackPointer = tmpStackPointer;
 201   }
 202   return self;
 203 }
 204
 205 /* copying */
 206
 207 - (id)copyWithZone:(NSZone *)_zone {
 208   register NGStack *newStack = nil;
 209   register unsigned cnt;
 210
 211   newStack = [[NGStack allocWithZone:(_zone ? _zone : NSDefaultMallocZone())]
 212                        initWithCapacity:[self stackPointer]];
 213
 214   for (cnt = 1; cnt <= stackPointer; cnt++)
 215     [newStack push:stack[cnt]];
 216
 217   return newStack;
 218 }
 219
 220 /* description */
 221
 222 - (NSString *)description {
 223   return [NSString stringWithFormat:
 224                      @"<%@[0x%08X] capacity=%u SP=%u count=%u content=%s>",
 225                      NSStringFromClass([self class]), (unsigned)self,
 226                      [self capacity], [self stackPointer], [self count],
 227                      [[[self toArray] description] cString]];
 228 }
 229
 230 - (NSArray *)toArray {
 231   register NSMutableArray *array = nil;
 232   register unsigned cnt;
 233
 234   array = [[NSMutableArray alloc] initWithCapacity:stackPointer];
 235
 236   for (cnt = 1; cnt <= stackPointer; cnt++)
 237     [array addObject:stack[cnt]];
 238
 239   return [array autorelease];
 240 }
 241
 242 @end /* NGStack */
 243
 244 @implementation _NGConcreteStackEnumerator
 245
 246 - (id)initWithStack:(NGStack *)_stack trace:(id *)_ptr count:(int)_size
 247   topDown:(BOOL)_downWard {
 248
 249   stack    = [_stack retain];
 250   trace    = _ptr;
 251   toGo     = _size;
 252   downWard = _downWard;
 253
 254   return self;
 255 }
 256
 257 - (void)dealloc {
 258   [self->stack release];
 259   trace = NULL;
 260   [super dealloc];
 261 }
 262
 263 - (id)nextObject {
 264   id result = nil;
 265
 266   if (toGo == 0)
 267     return nil;
 268
 269   toGo--;
 270
 271   result = *trace;
 272
 273   if (downWard) trace--; // top=>bottom (downward)
 274   else          trace++; // bottom=>top (upward)
 275
 276   return result;
 277 }
 278
 279 @end /* NGStack */
 280
 281 @implementation NGStackException
 282 @end /* NGStackException */
 283
 284 @implementation NSMutableArray(StackImp)
 285
 286 /* state */
 287
 288 - (unsigned int)stackPointer {
 289   return ([self count] - 1);
 290 }
 291
 292 - (BOOL)isEmpty {
 293   return ([self count] == 0) ? YES : NO;
 294 }
 295
 296 /* operations */
 297
 298 - (void)push:(id)_obj {
 299   [self addObject:_obj];
 300 }
 301 - (id)pop {
 302   unsigned lastIdx = ([self count] - 1);
 303
 304   if (lastIdx >= 0) {
 305     id element = [self objectAtIndex:lastIdx];
 306     [self removeObjectAtIndex:lastIdx];
 307     return element;
 308   }
 309   else {
 310     [[[NGStackException alloc] initWithName:@"StackException"
 311         reason:@"tried to pop an object from an empty stack !"
 312         userInfo:nil] raise];
 313     return nil;
 314   }
 315 }
 316
 317 - (void)clear {
 318   [self removeAllObjects];
 319 }
 320
 321 /* elements */
 322
 323 - (id)elementAtTop {
 324   return [self lastObject];
 325 }
 326
 327 - (NSEnumerator *)topDownEnumerator {
 328   return [self reverseObjectEnumerator];
 329 }
 330 - (NSEnumerator *)bottomUpEnumerator {
 331   return [self objectEnumerator];
 332 }
 333
 334 @end /* NSMutableArray(NGStack) */
 335
 336 void __link_NGExtensions_NGStack() {
 337   __link_NGExtensions_NGStack();
 338 }