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

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