/*
 Oaxaca: Useful Cocoa Library
 Copyright (C) 2006, Niko Matsakis (niko@alum.mit.edu)
 
 This program is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 2
 of the License, or (at your option) any later version.
 
 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#import "OACategories.h"
#import "OAExpressionEvaluator.h"
#import "OAExpressionOperations.h"
#import "OAExpressionToken.h"
#import "OADebug.h"

#define IS(A,B) (((A) & (B)) != 0)
#define ISNOT(A,B) (((A) & (B)) == 0)

@interface OAExpressionEvaluator : NSObject {
    OAExpressionOperations *m_operations;  /* defines the set of operators and their effects */
    OAExpressionToken *m_token;            /* current token */
    NSString *m_original;                  /* original version of expression we are parsing */
    NSString *m_remaining;                 /* remainder of expression we are parsing */    
    NSMutableArray *m_valueStack;          /* stack of NSNumbers */
    NSMutableArray *m_operatorStack;       /* stack of OAExpressionTokens representing operations */
}

// external:
- initWithOperations:(OAExpressionOperations*)ops;
- evaluateExpression:(NSString*)expr;

// internal:
- (void) peekToken;
- (void) skipSpace;
- (void) parseError:(NSString*)reason;
- (void) popOperators:(int)priority;
- (void) parseValue;
- (void) parseBinaryOperator;

@end

@implementation OAExpressionEvaluator

- initWithOperations:(OAExpressionOperations*)ops
{
    if ((self = [super init])) {
        m_operations = [ops retain];
        m_operatorStack = [[NSMutableArray alloc] init];
        m_valueStack = [[NSMutableArray alloc] init];
    }
    return self;
}

- (void) dealloc
{
    [m_operations release];
    [m_operatorStack release];
    [m_valueStack release];
    [super dealloc];
}

- (void) parseError:(NSString*)reason
{
    OALog(@"Parse error %@ with original %@ remaining %@", reason, m_original, m_remaining);
    int consumed = [m_original length] - [m_remaining length];
    @throw [NSException exceptionWithName:@"ExpressionEvaluationError" 
                                   reason:[NSString stringWithFormat:@"%@ at position %d: %@[*]%@",
                                       reason, consumed, [m_original substringToIndex:consumed],
                                       [m_original substringFromIndex:consumed]]
                                 userInfo:nil];
}

- (void) skipSpace
{
    // we ignore whitespace between tokens by default
    m_remaining = [m_remaining strip];
}

- (void) peekToken
{
    [self skipSpace];
    OALog(@"Peeking for next token of %@", m_remaining);
    if ([m_remaining length] == 0)
        m_token = nil;
    else {
        m_token = [m_operations tokenize:m_remaining];
        if (m_token == nil) 
            [self parseError:@"Unrecognized token"];
        OALog(@"  Token is %@", [m_token text]);
    }
}

- (void) consumeToken
{
    m_remaining = [m_remaining substringFromIndex:[[m_token text] length]];
}

/* Parses the expression beginning at the current cursor. */
- (void) parseValue
{
    OAINDENTED(@"parseValue value %d oper %d", [m_valueStack count], [m_operatorStack count])
    {    
        // Pop the next token off of the string.
        [self peekToken];
        
        // React appropriately.
        id result;
        int kind = [m_token kind];
        if (IS(kind, OAEXPRVALUE)) {
            [self consumeToken];
            result = [m_token value];
        } else if (IS(kind, OAEXPRUNARYOP)) {
            OAExpressionToken *oper = m_token;
            [self consumeToken];
            [self parseValue];            
            result = [m_valueStack popObject];
            result = [m_operations apply:oper to:result];
        } else if (IS(kind, OAEXPROPENPAREN)) {
            [self consumeToken];
            [self parseValue];
                
            // check that there is a close paren afterwards:
            [self peekToken];
            if (m_token == nil || ISNOT([m_token kind], OAEXPRCLOSEPAREN))
                [self parseError:@"Expected closing parenthesis here"];
            [self consumeToken];
        } else {
            [self parseError:@"Invalid expression"];
        }
        
        // in the non-error case, push the result onto the stack and look for a binary 
        // operator afterwards 
        OALog(@"Pushing result: %@", result);
        [m_valueStack pushObject:result];            
    } OAUNDENTED;
    [self parseBinaryOperator];
}

- (void) parseBinaryOperator
{
    OAINDENTED(@"parseBinaryOperator value %d oper %d", [m_valueStack count], [m_operatorStack count]) {
        // Pop the next token off of the string.
        [self peekToken];
        
        // end of string is legal
        if (m_token == nil)
            return;
        
        // right parenthesis is legal
        int kind = [m_token kind];
        if (IS(kind, OAEXPRCLOSEPAREN))
            return;

        // otherwise, only a binary operator is legal
        if (ISNOT(kind, OAEXPRBINARYOP))
            [self parseError:@"Expected binary operator here"];
        
        // Consume the operator...
        [self consumeToken];
        
        // push the binary operator onto the stack if its
        // precedence.
        OALog(@"Pushing oper %@", m_token);
        [self popOperators:[m_token priority]];
        [m_operatorStack pushObject:m_token];
    } OAUNDENTED;    
    [self parseValue];
}

- (void) popOperators:(int)priority
{
    OAINDENTED(@"popping operators of priority greater than %d", priority) {
        while ([m_operatorStack count] > 0) {
            OAExpressionToken *token = [m_operatorStack peekObject];
            if ([token priority] < priority) 
                return;
            
            [m_operatorStack popObject];
            id rvalue = [m_valueStack popObject];
            id lvalue = [m_valueStack popObject];
            id result = [m_operations apply:token left:lvalue right:rvalue];
            OALog(@"Popped oper: %@ == %@ %@ %@", result, lvalue, token, rvalue);
            [m_valueStack pushObject:result];
        } 
    } OAUNDENTED;
}

- evaluateExpression:(NSString*)expr
{
    OAINDENTED(@"Evaluate expression: %@", expr) {
        m_original = expr;
        m_remaining = expr;
        
        // parse and evaluate the expression:
        [self parseValue];
        [self popOperators:0];

        // did we consume the entire string?
        [self skipSpace];
        if ([m_remaining length] != 0)
            [self parseError:@"Extra text after end of expression"];

        // that should leave us with just one value and no operators:
        NSAssert1 ([m_operatorStack count] == 0, @"Still %d items on operator stack!", [m_operatorStack count]);
        NSAssert1 ([m_valueStack count] == 1, @"Value Stack ended up with %d values on it!", [m_valueStack count]);
        
        m_original = m_remaining = nil;
    } OAUNDENTED;
    
    return [m_valueStack popObject];
}

@end

id evaluateExpression(NSString *expr, OAExpressionOperations *ops)
{
    OAExpressionEvaluator *eval = [[[OAExpressionEvaluator alloc] initWithOperations:ops] autorelease];
    return [eval evaluateExpression:expr];
}

id evaluateExpressionUsingNSNumber(NSString *expr)
{
    return evaluateExpression(expr, [OAExpressionOperations operationsOnNSNumber]);
}

id evaluateExpressionUsingNSDecimalNumber(NSString *expr)
{
    return evaluateExpression(expr, [OAExpressionOperations operationsOnNSDecimalNumber]);
}
