/*	MiscStack.m

	Copyright 1995 Christopher J. Kane.

	This notice may not be removed from this source code.
	The use and distribution of this software is governed by the
	terms of the MiscKit license agreement.  Refer to the license
	document included with the MiscKit distribution for the terms.

	Version 1 (1 February 1995)
*/

#import <MiscStack.h>
#import <MiscUtilities.h>
#import <Foundation/Foundation.h>

/**************** Abstract implementation ****************/

@interface MiscConcreteStack : MiscStack
{
    NSMutableArray *_stack;
}
@end

@implementation MiscStack

+ (MiscStack *)allocWithZone:(NSZone *)zone {
    Class class = self;
    if ([MiscStack class] == class)
	class = [MiscConcreteStack class];
    return (MiscStack *)NSAllocateObject(class, 0, zone);
}

- (id)init {
    MiscRequiresConcreteObject(self, _cmd);
    return nil;
}

- (BOOL)isEmpty {
    MiscRequiresConcreteImplementation(self, _cmd, [MiscStack class]);
    return YES;
}

- (id)pop {
    MiscRequiresConcreteImplementation(self, _cmd, [MiscStack class]);
    return nil;
}

- (void)pushObject:(id)anObject {
    MiscRequiresConcreteImplementation(self, _cmd, [MiscStack class]);
}

- (BOOL)isEqual:(id)anObject {
    NSParameterAssert(nil != anObject);
    return (anObject == self) || [self isEqualToStack:anObject];
}

- (id)copyWithZone:(NSZone *)zone {
    MiscStack *newStack = [[isa allocWithZone:zone] init];
    NSAssert(nil != newStack, @"could not create new stack");
    [newStack pushStack:self];
    return newStack;
}

- (Class)classForCoder {
    return [MiscStack class];
}

static void encodeStack(MiscStack *self, NSCoder *encoder) {
    id obj;
    if ([self isEmpty])
	return;
    obj = [self pop];
    encodeStack(self, encoder);
    [encoder encodeObject:obj];
    [self pushObject:obj];
}

- (void)encodeWithCoder:(NSCoder *)encoder {
    unsigned int count = [self count];
    [encoder encodeValueOfObjCType:@encode(int) at:&count];
    if (0 == count)
	return;
    encodeStack(self, encoder);
}

- (id)initWithCoder:(NSCoder *)decoder {
    unsigned int count;
    [self init];
    [decoder decodeValueOfObjCType:@encode(int) at:&count];
    while (count--) {
	id obj;
	[decoder decodeValueOfObjCType:@encode(id) at:&obj];
	[self pushObject:obj];
	[obj autorelease];
    }
    return self;
}

@end

@implementation MiscStack (MiscStackExtensions)

+ (MiscStack *)stack {
    return [[[self alloc] init] autorelease];
}

+ (MiscStack *)stackWithArray:(NSArray *)anArray {
    NSParameterAssert([anArray isKindOfClass:[NSArray class]]);
    return [[[self alloc] initWithEnumerator:[anArray objectEnumerator]] autorelease];
}

+ (MiscStack *)stackWithReversedArray:(NSArray *)anArray {
    NSParameterAssert([anArray isKindOfClass:[NSArray class]]);
    return [[[self alloc] initWithEnumerator:[anArray reverseObjectEnumerator]] autorelease];
}

+ (MiscStack *)stackWithObjects:(id *)objects count:(unsigned int)count {
    NSParameterAssert(objects != NULL);
    return [[[self alloc] initWithObjects:objects count:count] autorelease];
}

+ (MiscStack *)stackWithObjects:(id)firstObj, ... {
    id result = [self stack];
    if (firstObj) {
	va_list args;
	id obj;
	va_start(args, firstObj);
	while ((obj = va_arg(args, id)))
	    [result pushObject:obj];
	va_end(args);
    }
    return result;
}

- (id)initWithEnumerator:(NSEnumerator *)enumerator {
    self = [self init];
    NSAssert(nil != self, @"object super initialization failed");
    [self pushWithEnumerator:enumerator];
    return self;
}

- (id)initWithObjects:(id *)objects count:(unsigned int)count {
    int i;
    NSParameterAssert(objects != NULL);
    self = [self init];
    NSAssert(nil != self, @"object super initialization failed");
    for (i = 0; i < count; i++)
	[self pushObject:objects[i]];
    return self;
}

- (id)initWithObjects:(id)firstObj, ... {
    self = [self init];
    NSAssert(nil != self, @"object super initialization failed");
    if (firstObj) {
	va_list args;
	id obj;
	va_start(args, firstObj);
	while ((obj = va_arg(args, id)))
	    [self pushObject:obj];
	va_end(args);
    }
    return self;
}

- (NSArray *)multipop:(unsigned int)number {
    int i;
    NSMutableArray *result = [[[NSMutableArray alloc] initWithCapacity:number] autorelease];
    NSAssert(nil != result, @"could not create new array");
    for (i = 0; i < number; i++)
	[result addObject:[self pop]];
    return result;
}

- (id)npop:(unsigned int)number {
    id obj = nil;
    int i;
    for (i = 0; i < number; i++)
	obj = [self pop];
    return obj;
}

- (void)popAllObjects {
    while (![self isEmpty])
	[self pop];
}

- (id)top {
    id obj;
    if ([self isEmpty])
	return nil;
    obj = [self pop];
    [self pushObject:obj];
    return obj;
}

static unsigned int countStack(MiscStack *self) {
    id obj;
    unsigned int result;
    if ([self isEmpty])
	return 0;
    obj = [self pop];
    result = countStack(self) + 1;
    [self pushObject:obj];
    return result;
}

- (unsigned int)count {
    return countStack(self);
}

static void pushStack(MiscStack *self, MiscStack *aStack) {
    id obj;
    if ([aStack isEmpty])
	return;
    obj = [aStack pop];
    pushStack(self, aStack);
    [self pushObject:obj];
}

- (void)pushStack:(MiscStack *)aStack {
    NSParameterAssert(nil != aStack);
    pushStack(self, [aStack copy]);
}

- (void)pushWithEnumerator:(NSEnumerator *)enumerator {
    id obj;
    NSParameterAssert([enumerator isKindOfClass:[NSEnumerator class]]);
    while ((obj = [enumerator nextObject]))
	[self pushObject:obj];
}

static BOOL equalStacks(MiscStack *stack1, MiscStack *stack2) {
    BOOL result;
    id obj1, obj2;
    if ([stack1 isEmpty] && [stack2 isEmpty])
	return YES;
    if (([stack1 isEmpty] && ![stack2 isEmpty]) || (![stack1 isEmpty] && [stack2 isEmpty]))
	return NO;
    obj1 = [stack1 pop];
    obj2 = [stack2 pop];
    result = [obj1 isEqual:obj2] && equalStacks(stack1, stack2);
    [stack1 pushObject:obj1];
    [stack2 pushObject:obj2];
    return result;
}

- (BOOL)isEqualToStack:(MiscStack *)otherStack {
    NSParameterAssert(nil != otherStack);
    if (![otherStack isKindOfClass:[MiscStack class]])
	return NO;
    return equalStacks(self, otherStack);
}

- (NSString *)description {
    return [self descriptionWithLocale:nil];
}

- (NSString *)descriptionWithLocale:(NSDictionary *)locale {
    return [[[[self copy] autorelease] multipop:[self count]] descriptionWithLocale:locale];
}

@end

/**************** Concrete implementation ****************/

@implementation MiscConcreteStack

- (id)init {
    _stack = [[NSMutableArray allocWithZone:[self zone]] init];
    return self;
}

- (void)dealloc {
    [_stack release];
    [super dealloc];
}

- (BOOL)isEmpty {
    return [_stack count] == 0;
}

- (id)pop {
    id obj;
    unsigned int count = [_stack count];
    if (0 == count)
	[NSException raise:NSRangeException format:@"Attempt to pop from an empty stack"];
    obj = [[[_stack objectAtIndex:count - 1] retain] autorelease];
    [_stack removeLastObject];
    return obj;
}

- (void)pushObject:(id)anObject {
    [_stack addObject:anObject];
}

/* Methods below implemented only for efficiency */

- (NSArray *)multipop:(unsigned int)number {
    int i, index = [_stack count] - 1;
    NSMutableArray *result = [[[NSMutableArray alloc] initWithCapacity:number] autorelease];
    NSAssert(nil != result, @"could not create new array");
    for (i = 0; i < number; i++) {
	if (index < 0)
	    [NSException raise:NSRangeException format:@"Attempt to pop from an empty stack"];
	[result addObject:[_stack objectAtIndex:index--]];
	[_stack removeLastObject];
    }
    return result;
}

- (id)npop:(unsigned int)number {
    int i;
    id obj = nil;
    if (0 == number)
	return nil;
    for (i = 0; i < number - 1; i++) {
	if ([_stack count] == 0)
	    [NSException raise:NSRangeException format:@"Attempt to pop from an empty stack"];
	[_stack removeLastObject];
    }
    if ([_stack count] == 0)
	[NSException raise:NSRangeException format:@"Attempt to pop from an empty stack"];
    obj = [[[_stack lastObject] retain] autorelease];
    [_stack removeLastObject];
    return obj;
}

- (void)popAllObjects {
    [_stack removeAllObjects];
}

- (id)top {
    return [[[_stack lastObject] retain] autorelease];
}

- (unsigned int)count {
    return [_stack count];
}

@end
