<!--  // Hide this just in case this file is read as HTML

// h * 0.5 ^ (h - 1) * 0.5 ^ h / (4 * 0.5 ^ (2 * h)) not simplified
// i.e. a^b / a^c not simplified


// *****************************************************************
// CALCULUS.JS
// Requires Parser.js, Stack.js, Tree.js, and misc.js
// *****************************************************************
// Code to parse expressions and to do symbolic derivation
// 1-pass parser to do derivation. Also contains simplifcation routines
// Complete parser (no calls to eval() in this version)
// 
// entry points:
// exprParse(str): parse str and return a Tree of the parse (or null)
// exprUnparse(node): convert a Tree back into a string
// ***************************************************************** 

// *****************************************************************
// Constants
// *****************************************************************

// Constants defining some token types
// it really doesn't matter what these are
var T_NUMBER = "NUM";
var T_IDENTIFIER = "ID";
var T_FUNCTION = "FUNCTION"; // this is the token returned by the lexer to represent any function

// some common tokens
var ZERO = new Token(T_NUMBER, 0);
var ONE = new Token(T_NUMBER, 1);
var MINUS_ONE = new Token(T_NUMBER, -1);
var TWO = new Token(T_NUMBER, 2);
var MINUS_TWO = new Token(T_NUMBER, -2);

// This simplifies converting to the above special tokens
var NUMBERS = new Array();
NUMBERS[0] = ZERO;
NUMBERS[1] = ONE;
NUMBERS[-1] = MINUS_ONE;
NUMBERS[2] = TWO;
NUMBERS[-2] = MINUS_TWO;

// Here we don't care what the second argument is (the value of the token)
// But later when we convert back to a string, it makes it easier to just put
// the string representation into the value of the token as with all the functions
// so unary and functions can be easily converted back to strings
// For the type of the token, we don't assign it "-" which we reserve for the binary operator
// This makes it easier to quickly tell when we have a binary operator
var UNARY_MINUS = new Token("UNARY_MINUS", "-");

// These have the string representation of the operator stored 
// directly as its token type
var ADDITION = new Token("+", null);
var SUBTRACTION = new Token("-", null);		// want a different object from UNARY_MINUS
var MULTIPLICATION = new Token("*", null);
var DIVISION = new Token("/", null);
var EXPONENTIATION = new Token("^", null);

// standard function tokens. All are of type T_FUNCTION so that they can be
// treated similarly by the parser as a function and
// we can distinguish them later in the parsing process
// The second argument, the token value, is what will be printed out when 
// we convert nodes back into strings
var SINE = new Token(T_FUNCTION, "sin");
var COSINE = new Token(T_FUNCTION, "cos");
var TANGENT = new Token(T_FUNCTION, "tan");
var SECANT = new Token(T_FUNCTION, "sec");
var COSECANT = new Token(T_FUNCTION, "csc");
var COTANGENT = new Token(T_FUNCTION, "cot");
var ARCSINE = new Token(T_FUNCTION, "asin");
var ARCCOSINE = new Token(T_FUNCTION, "acos");
var ARCTANGENT = new Token(T_FUNCTION, "atan");
var NATURALLOG = new Token(T_FUNCTION, "ln");
var SQUAREROOT = new Token(T_FUNCTION, "sqrt");

/*	maybe someday
var HYPERBOLICSINE = new Token(T_FUNCTION, "sinh");
var HYPERBOLICCOSINE = new Token(T_FUNCTION, "cosh");
var HYPERBOLICTANGENT= new Token(T_FUNCTION, "tanh");
*/

// Define an array with allowable function names to simplify lookup
var FUNCTION_ARRAY = new Array();

// assign FUNCTION_ARRAY[func] to the token for the function
FUNCTION_ARRAY["sin"] = SINE;
FUNCTION_ARRAY["cos"] = COSINE;
FUNCTION_ARRAY["tan"] = TANGENT;
FUNCTION_ARRAY["sec"] = SECANT;
FUNCTION_ARRAY["csc"] = COSECANT;
FUNCTION_ARRAY["cot"] = COTANGENT;
FUNCTION_ARRAY["asin"] = ARCSINE;
FUNCTION_ARRAY["acos"] = ARCCOSINE;
FUNCTION_ARRAY["atan"] = ARCTANGENT;
FUNCTION_ARRAY["ln"] = NATURALLOG;
FUNCTION_ARRAY["sqrt"] = SQUAREROOT;

// These pair up inverse functions where f(g(x)) == x
var INVERSE_FUNCTION = new Array();
INVERSE_FUNCTION[SINE] = ARCSINE;
INVERSE_FUNCTION[ARCSINE] = SINE;
INVERSE_FUNCTION[COSINE] = ARCCOSINE;
INVERSE_FUNCTION[ARCCOSINE] = COSINE;
INVERSE_FUNCTION[TANGENT] = ARCTANGENT;
INVERSE_FUNCTION[ARCTANGENT] = TANGENT;

// These are such that f(x) * g(x) == 1
var RECIPROCAL_FUNCTION = new Array();
RECIPROCAL_FUNCTION[SINE] = COSECANT;
RECIPROCAL_FUNCTION[COSECANT] = SINE;
RECIPROCAL_FUNCTION[COSINE] = SECANT;
RECIPROCAL_FUNCTION[SECANT] = COSINE;
RECIPROCAL_FUNCTION[TANGENT] = COTANGENT;
RECIPROCAL_FUNCTION[COTANGENT] = TANGENT;

// these are pointers to the actual functions
var DO_FUNCTION = new Array();
DO_FUNCTION[SINE] = Math.sin;
DO_FUNCTION[COSINE] = Math.cos;
DO_FUNCTION[TANGENT] = Math.tan;
DO_FUNCTION[SECANT] = calcSecant;
DO_FUNCTION[COSECANT] = calcCosecant;
DO_FUNCTION[COTANGENT] = calcCotangent;
DO_FUNCTION[ARCSINE] = Math.asin;
DO_FUNCTION[ARCCOSINE] = Math.acos;
DO_FUNCTION[ARCTANGENT] = Math.atan;
DO_FUNCTION[NATURALLOG] = Math.log;
DO_FUNCTION[SQUAREROOT] = Math.sqrt;

// This precendence table is only used for converting back to a string
// this is used to determine when parenthesis are needed
var PREC = new Array();
var LOWEST_PREC = 1;
PREC["+"] = LOWEST_PREC;
PREC["-"] = LOWEST_PREC;
PREC["*"] = LOWEST_PREC + 1;
PREC["/"] = LOWEST_PREC + 1;
PREC["^"] = LOWEST_PREC + 2;

// *****************************************************************
// Variables
// *****************************************************************

var exprParser = null;	// parser for expressions

// associative array to associate identifiers with some other expression
// this allows for example, y = x^2
// everywhere y appears, x^2 is substituted
// so the value for each element should be a TreeNode

var definedIdentifiers = new Array();

var builtinConstants = new Array();
builtinConstants["e"] = Math.E;
builtinConstants["pi"] = Math.PI;

// *****************************************************************
// Identifers
// *****************************************************************

function defineIdentifier(identifier, node)
{
    definedIdentifiers[identifier] = node;
}

function resetIdentifiers()
{
    // after this, only builtin identifiers will be defined
    definedIdentifiers = new Array();	// empty this array

    // add in the builtins
    for (var id in builtinConstants)
    {
        definedIdentifiers[id] = new TreeNode(new Token(T_NUMBER, builtinConstants[id]));;
    }
}

// *****************************************************************
// Helpers
// *****************************************************************

function parseError(errMsg)
{
    // can be overriden to do something useful
}

function endExprParse(parseTree)
{
    // what we care about is actually the attribute
    // which contains a TreeNode not the whole parseTree
    return (parseTree.attribute);
}

function calcSecant(num)
{
    return (1/Math.cos(num));
}

function calcCosecant(num)
{
    return (1/Math.sin(num));
}

function calcCotangent(num)
{
    return (1/Math.tan(num));
}

// *****************************************************************
// Lexical analyzer
// *****************************************************************

function ExprLexer(str)
{
    this.str = str;
    this.nextToken = lexNextToken;
}

function lexNextToken()
{
    // returns one token from the string
    // returns false if error occurs
    // returns null if no more input (str == "")

    var token;
    var pos = 0;      // location of end of token
    var ch;           // temporary character holder

    this.str = trim(this.str);  // remove leading and trailing spaces

    if (this.str == "")
        return (null);      // no more input

    ch = this.str.charAt(pos);   // get the first character

    // recognize numbers
    // given by regular expression [0123456789]*'.'?[0123456789]*
    if (".0123456789".indexOf(ch) != -1)
    {
        // is a number
        var seenDecimalPoint = (ch == '.');

        ch = this.str.charAt(++pos);	// get next character
        while (".0123456789".indexOf(ch) != -1)
        {
            if (ch == '.')
            {
                if (seenDecimalPoint)
                {
                    parseError("Invalid number. Two decimal points found.");
                    return (false);
                }
                seenDecimalPoint = true;
            }

            pos++;
            if (pos >= this.str.length)
                break;		// reached end of string
            else
                ch = this.str.charAt(pos);	// continue on
        }

        var numberStr = this.str.substring(0, pos);	// 0 to pos - 1
        var number = parseFloat(numberStr);		// convert it to a number

        if (isNaN(number))
        {
            parseError("Invalid number.");
            return (false);
        }

        token = new Token(T_NUMBER, number);

    }	// token is a number
    else if ("_ABCDEFGHIJKLMNOPQRSTUVWYXZ".indexOf(ch.toUpperCase()) != -1)
    {
        // process other characters

        // we set ch to next character and continue until we hit
        // some unexpected character
        // identifiers can't start with a number or quote
        // and can have underscores and single quotes

        while ("'_ABCDEFGHIJKLMNOPQRSTUVWYXZ0123456789".indexOf(ch.toUpperCase()) != -1)
        {
            // increment pos and find next character

            pos++;
            if (pos >= this.str.length)
                break;      // reached end of string
            else
                ch = this.str.charAt(pos);   // continue testing
        }

        var tokenVal = this.str.substring(0, pos);

        // determine the type of the token
        
        // check if token is a valid function name or a special number
        // lookup the predefined token in an array of functions
        if (FUNCTION_ARRAY[tokenVal])
            token = FUNCTION_ARRAY[tokenVal];
        else
            token = new Token(T_IDENTIFIER, tokenVal);	// call it an identifier
    }
    else	// some other character
    {
        token = new Token(ch, null);
        pos++;
    }

    // remove from the string everything that we have already seen
    this.str = this.str.substring(pos);  // everything else

    return (token);  // success
}

// *****************************************************************
// Parser for expressions
// *****************************************************************
//
// This parser will return a tree representing the input expression
//
// *****************************************************************
// The binary operators are +,-,*,/,^
// All operators have left to right associativity with
// precedence in the normal way
// Unary operators have highest precedence with right to left associativity
//
// This is a (almost) LL(1) parser for the following grammar:
// Note that I added builtin implicit multiplication (T -> TX)
// which I think makes this grammar non-LL(1).
//
// (expr) E -> E + T | E - T | T
// (term) T -> T * X | T / X | TX | X
// (exponentiation) X -> X ^ U | U
// (unary) U -> -U | function U | ( E ) | number | identifier
//
// Removing left recursion/left factoring:
// E -> TE'
// E' -> +TE' | -TE' | $empty$
// T -> XT'
// T' -> *XT' | /XT' | XT' | $empty$
// X -> UX'
// X' -> ^UX' | $empty$
// U -> -U | function U | ( E ) | number | identifier
//
// First(E) = - function ( number identifier
// First(E') = + - $empty$
// First(T) = - function ( number identifier
// First(T') = - * / function ( number identifier $empty$
// First(X) = - function ( number identifier
// First(X') = ^ $empty$
// First(U) = - function ( number identifier
//
// Follow(E) = $ )
// Follow(E') = $ )
// Follow(T) = $ + - )
// Follow(T') = $ + - )
// Follow(X) = $ * / + - function ( ) number identifier
// Follow(X') = $ * / + - function ( ) number identifier
// Follow(U) = $ * / + - ^ function ( ) number identifier
//
// From this we get the following parse table (with e denoting the empty string):
// Note the one conflict for T' and '-'. We resolve it to T'->e which means that
// in something like x-y the '-' should be the binary operator and not stand for x*(-y)
// (Didn't add E->e to ')' so "()" is not valid input)
// 
//      +       -       *       /       ^       function        (       )       number  identifier      $
// E            TE'                             TE'             TE'             TE'     TE'             
// E'   +TE'    -TE'                                                    e                               e
// T            XT'                             XT'             XT'             XT'     XT'
// T'   e       e       *XT'    /XT'            XT'             XT'     e       XT'     XT'             e
//              (XT')
// X            UX'                             UX'             UX'             UX'     UX'
// X'   e       e       e       e       ^UX'    e               e       e       e       e               e
// U            -U                              func U          (E)             number  identifier
//
// *****************************************************************

function setupExprParser()
{
    // setup the parser to parse expressions
    // we generate the above table from the grammar automatically now

    var expr = new ParseNode(NONTERMINAL, "E");
    var term = new ParseNode(NONTERMINAL, "T");
    var exp = new ParseNode(NONTERMINAL, "X");
    var unary = new ParseNode(NONTERMINAL, "U");

    var lparen = new ParseNode(TERMINAL, "(");
    var rparen = new ParseNode(TERMINAL, ")");
    var plus = new ParseNode(TERMINAL, "+");
    var minus = new ParseNode(TERMINAL, "-");
    var times = new ParseNode(TERMINAL, "*");
    var divide = new ParseNode(TERMINAL, "/");
    var caret = new ParseNode(TERMINAL, "^");
    var func = new ParseNode(TERMINAL, T_FUNCTION);
    var number = new ParseNode(TERMINAL, T_NUMBER);
    var identifier = new ParseNode(TERMINAL, T_IDENTIFIER);

    var unary_minus = minus;	// same as minus. just a more descriptive name


    var grammar = new Array();

    grammar[expr] = new Array( 
                              new Array(expr, plus, term, new ParseNode(ACTION, addSubFunc)),
                              new Array(expr, minus, term, new ParseNode(ACTION, addSubFunc)), 
                              new Array(term)
                              );
    grammar[term] = new Array(
                              new Array(term, times, exp, new ParseNode(ACTION, mulFunc)), 
                              new Array(term, divide, exp, new ParseNode(ACTION, divFunc)),  
                              new Array(term, exp, new ParseNode(ACTION, mulFunc)), 
                              new Array(exp)
                              );
    grammar[exp] = new Array( 
                             new Array(exp, caret, unary, new ParseNode(ACTION, expFunc)), 
                             new Array(unary) 
                             );
    grammar[unary] = new Array(
                               new Array(unary_minus, unary, new ParseNode(ACTION, unaryMinusFunc)), 
                               new Array(func, unary, new ParseNode(ACTION, functionFunc)), 
                               new Array(lparen, expr, rparen), 
                               new Array(number, new ParseNode(ACTION, usePrevTokenFunc)),
                               new Array(identifier, new ParseNode(ACTION, usePrevTokenFunc)) 
                               );

    var parseGrammar = new ParseGrammar(grammar, expr);
    parseGrammar.makeLL();
	// create the parse table
    var table = parseGrammar.generateTable(conflictFn);
    exprParser = new Parser(table, parseError, null, endExprParse);    
}


function conflictFn(nonterm, input, rule1, rule2)
{
    if (nonterm == "T'" && input == "-")
    {
        // for the one conflict
        if (rule1.length == 0)
        {
            return rule1;
        }
        else if (rule2.length == 0)
        {
            return rule2;
        }
    }
    return null;
}

// *****************************************************************
// Core Parsing Functions
// *****************************************************************

// For all these functions, "this" refers to the ParseNode that we're at.
// Fill the attribute field with a TreeNode representing a TreeNode to represent
// the original equation
// These basically convert everything to TreeNodes (getting rid of nonterminals)

function usePrevTokenFunc()
{
    // U->number or
    // U->identifier

    this.attribute = new TreeNode(this.getRelativeSibling(-1).token);
    return (true);
}

function unaryMinusFunc()
{
    // U -> -U
    var operand = this.getRelativeSibling(-1);

    this.attribute = new TreeNode(UNARY_MINUS, operand.attribute);

    return (true);
}

function functionFunc()
{
    // called after U->func U
    var operand = this.getRelativeSibling(-1);
    var func = this.getRelativeSibling(-2);

    this.attribute = new TreeNode(func.token, operand.attribute);

    return (true);
}

function addSubFunc()
{
    // handles binary addition and subtraction
    // comes after the production E'->+T or E'->-T
    // the first operand is whatever just came before the E'
    var operand2 = this.getRelativeSibling(-1);
    var operator = this.getRelativeSibling(-2);
    var operand1 = this.parent.getRelativeSibling(-1);

	// operator.token.type should be a '+' or '-'
    this.attribute = new TreeNode(operator.token.type == "+" ? ADDITION : SUBTRACTION, 
                                  operand1.attribute, operand2.attribute);

    return (true);
}

function mulFunc()
{
    // multiplication
    // T'-> * X, or just T'->X (implicit multiplication)

    var operand2 = this.getRelativeSibling(-1);
    var operand1 = this.parent.getRelativeSibling(-1);

    this.attribute = new TreeNode(MULTIPLICATION, operand1.attribute, operand2.attribute);

    return (true);
}

function divFunc()
{
    // division
    // T'-> / X

    var operand2 = this.getRelativeSibling(-1);
    var operand1 = this.parent.getRelativeSibling(-1);

    this.attribute = new TreeNode(DIVISION, operand1.attribute, operand2.attribute);

    return (true);
}

function expFunc()
{
    // exponentiation
    // X'-> ^ U

    var operand2 = this.getRelativeSibling(-1);
    var operand1 = this.parent.getRelativeSibling(-1);

    this.attribute = new TreeNode(EXPONENTIATION, operand1.attribute, operand2.attribute);

    return (true);
}

// *****************************************************************
// Derivation functions
// These functions take a TreeNode that have a token of a
// specific type (assumes that it really is of the right type!)
// The functions will set the derivative field of the node to the derivative (a TreeNode)
// All of these assume that their operands already have been derived
// The tree should be acyclic but some TreeNodes may have more than one parent
// (i.e. consider the algorithm for exponentiation. One part of the tree is put
//	as the child of more than one node)
// *****************************************************************

function deriveNumber(node)
{
    // derivative of any number is 0
    node.derivative = new TreeNode(ZERO);
}

function deriveIdentifier(node, diffVar)
{
    // check if identifier is the variable that we are
    // differentiating. if not we use something like y'

    var id = node.value.value;

    if (id == diffVar)
        node.derivative = new TreeNode(ONE);
    else
        node.derivative = new TreeNode(new Token(T_IDENTIFIER, id + "'"));
}

function deriveUnaryMinus(node)
{
    node.derivative = new TreeNode(UNARY_MINUS, node.children[0].derivative);
}

function deriveFunction(node)
{
    var operand = node.children[0];

    // use chain rule
    // first put in the derivative of the operand
    node.derivative = new TreeNode(MULTIPLICATION, operand.derivative);

    // now for the derivative for the function
    var child;

    if (node.value == NATURALLOG)
    {
        // derivative of ln x = 1/x
        child = new TreeNode(DIVISION, new TreeNode(ONE), operand);
    }
    else if (node.value == SQUAREROOT)
    {
        // derivative of x^1/2 == 1/(2 * sqrt(x))
        child = new TreeNode(DIVISION, new TreeNode(ONE),
                             new TreeNode(MULTIPLICATION, 
                                          new TreeNode(TWO), new TreeNode(SQUAREROOT, operand)));
    }
    else if (node.value == SINE)
    {
        // derivative of sin x = cos x
        child = new TreeNode(COSINE, operand);
    }
    else if (node.value == COSINE)
    {
        // derivative of cos x = -sin x
        child = new TreeNode(UNARY_MINUS, new TreeNode(SINE, operand));
    }
    else if (node.value == TANGENT)
    {
        // derivative of tan x = (sec x)^2 = (cos x)^(-2)
        child = new TreeNode(EXPONENTIATION, 
                             new TreeNode(SECANT, operand), new TreeNode(TWO));
    }
    else if (node.value == SECANT)
    {
        // derivative of sec x = sec x * tan x
        child = new TreeNode(MULTIPLICATION, 
                             new TreeNode(SECANT, operand.clone()), new TreeNode(TANGENT, operand));
    }
    else if (node.value == COSECANT)
    {
        // derivative of csc x = -cot x * csc x
        child = new TreeNode(MULTIPLICATION, 
                             new TreeNode(UNARY_MINUS, new TreeNode(COTANGENT, operand.clone())), 
                             new TreeNode(COSECANT, operand));
    }
    else if (node.value == COTANGENT)
    {
        // derivative of cot x = -(csc x)^2 = -1/(sin x)^2
        child = new TreeNode(UNARY_MINUS,
                             new TreeNode(EXPONENTIATION, 
                                          new TreeNode(COSECANT, operand), new TreeNode(TWO)));
    }
    else if ((node.value == ARCSINE) || (node.value == ARCCOSINE))
    {
        // derivative of asin x = (1-x^2)^(-1/2) = 1/sqrt(1-x^2)
        // derivative of acos x = -(1-x^2)^(-1/2) = -1/sqrt(1-x^2)
        child = new TreeNode(DIVISION, 
                             node.value == ARCSINE ? new TreeNode(ONE) : new TreeNode(MINUS_ONE),
                             new TreeNode(SQUAREROOT, 
                                          new TreeNode(SUBTRACTION,
                                                       new TreeNode(ONE), 
                                                       new TreeNode(EXPONENTIATION, operand, new TreeNode(TWO)))));
    }
    else if (node.value == ARCTANGENT)
    {
        // derivative of atan x = 1/(1 + x^2)
        child = new TreeNode(DIVISION,
                             new TreeNode(ONE),
                             new TreeNode(ADDITION, 
                                          new TreeNode(ONE),
                                          new TreeNode(EXPONENTIATION, operand, new TreeNode(TWO))));
    }
    else
    {
        assert(0, "deriveFunction", "illegal function");
        return (false);
    }

    // now add this child under the MULTIPLICATION node
    node.derivative.addChild(child);
}

function deriveAddSub(node)
{
    // handle derivative of addition and subtraction
    var operand1 = node.children[0];
    var operand2 = node.children[1];

    // derivative for addition of subtraction is just to take
    // derivatives of both operands and put whatever operator
    // back in
    node.derivative = new TreeNode(node.value, operand1.derivative, operand2.derivative);
}

function deriveMulDivHelper(operand1, operand2)
{
    // operand1, operand2 are TreeNodes.
    // will return a TreeNode of D(operand1)*operand2
    return(new TreeNode(MULTIPLICATION, operand1.derivative, operand2.clone()));
}

function deriveMultiplication(node)
{
    var operand1 = node.children[0];
    var operand2 = node.children[1];

    // derivative of f(x)*g(x) = f'(x)*g(x) + g'(x)*f(x)
    node.derivative = new TreeNode(ADDITION, 
                                   deriveMulDivHelper(operand1, operand2),
                                   deriveMulDivHelper(operand2, operand1));
}

function deriveDivision(node)
{
    var operand1 = node.children[0];
    var operand2 = node.children[1];

    // derivative of f(x)/g(x) = (f'(x)*g(x) - g'(x)*f(x))/g(x)^2
    node.derivative = new TreeNode(DIVISION, 
                                   new TreeNode(SUBTRACTION,
                                                deriveMulDivHelper(operand1, operand2),
                                                deriveMulDivHelper(operand2, operand1)),
                                   new TreeNode(EXPONENTIATION,
                                                operand2.clone(), new TreeNode(TWO)));
}

function deriveExponentiation(node)
{
    var operand1 = node.children[0];
    var operand2 = node.children[1];

    // derivative of f(x)^g(x) = g(x)*f(x)^(g(x)-1)*f'(x) + f(x)^g(x)*ln(f(x))*g'(x)
    var child1 = null;

    // first mess
    // don't calculate out the whole mess if the term will drop out
    if (operand1.derivative.value != ZERO)
    {
        child1 = new TreeNode(MULTIPLICATION, 
                              new TreeNode(MULTIPLICATION, 
                                           operand2.clone(), // g(x)
                                           new TreeNode(EXPONENTIATION,
                                                        operand1.clone(), // f(x)
                                                        new TreeNode(SUBTRACTION,	// g(x) - 1
                                                                     operand2.clone(),
                                                                     new TreeNode(ONE)))),
                              operand1.derivative);	// f'(x)
    }


    // now the second half of the mess
    var child2 = null;
    if (operand2.derivative.value != ZERO)
    {
        child2 = new TreeNode(MULTIPLICATION,
                              new TreeNode(MULTIPLICATION,
                                           new TreeNode(EXPONENTIATION, 
                                                        operand1.clone(),		// f(x)
                                                        operand2.clone()),		// g(x)
                                           new TreeNode(NATURALLOG, operand1.clone())),	// ln(f(x))
                              operand2.derivative);		// g'(x)
    }

    // combine the two messes
    if ((child1 != null) && (child2 != null))
        node.derivative = new TreeNode(ADDITION, child1, child2);
    else if ((child1 == null) && (child2 != null))
        node.derivative = child2;
    else if ((child2 == null) && (child1 != null))
        node.derivative = child1;
    else
    {
        // they are both null
        // essentially we would have 0 + 0
        node.derivative = new TreeNode(ZERO);
    }
}

// *****************************************************************
// Guessing functions
// These take something like 3.1415926 and return the symbol pi.
// *****************************************************************

// some constants that affect the way guessing work
var GUESS_TOO_LARGE_INT = 1E7;
var GUESS_LARGEST_DENOMINATOR = 100;
var GUESS_LARGEST_EXPONENT = 4
var ZERO_THRESHOLD = 1E-7;      // number less than this can be treated as zero

var guessNumbers = false;       // whether guessing is on or not

function setGuessNumbers(value)
{
    // if guessNumbers is true then we try to return expressions in
    // terms of easier to understand constants
    // i.e. 1.41421356237309504880 is returned as sqrt(2) during simplification
    guessNumbers = value;
}

function guessNumber(token)
{
    // returns a TreeNode if we guessed something. otherwise returns null

    var num = token.value;
    var guess;

    if (guessOutOfRange(num))
        return (null);

    guess = guessBasic(num);
    if (guess != null)
        return (guess);

    guess = guessSqrt(num);
    if (guess != null)
        return (guess);

    guess = guessLog(num);
    if (guess != null)
        return (guess);

    guess = guessConstantPower(num);
    if (guess != null)
        return (guess);

    guess = guessConstantFactor(num);
    if (guess != null)
        return (guess);

    return (null);
}

function guessBasic(num)
{
    // makes simple guesses of what num is

    var guess;

    if (guessOutOfRange(num))
        return (null);

    guess = guessIsInt(num);
    if (guess != null)
        return (guess);

    guess = guessConstant(num);
    if (guess != null)
        return (guess);

    guess = guessFraction(num);
    if (guess != null)
        return (guess);

    return (null);
}

function guessIsZero(num)
{
    if (Math.abs(num) < ZERO_THRESHOLD)
        return (true);
    else
        return (false);
}

function guessOutOfRange(num)
{
    if (Math.abs(num) > GUESS_TOO_LARGE_INT)
        return (true);
    else
        return (false);
}

function guessIsInt(num)
{
    var round = Math.round(num);
    if (guessIsZero(num - round))
        return (new TreeNode(getNumberToken(round)));
    else
        return (null);
}

function guessFraction(num)
{
    // tries to convert a number into a rational fraction
    var tmp;
    var top;
    for (var i = 2; i < GUESS_LARGEST_DENOMINATOR; i++)
    {
        tmp = num * i;
        top = guessIsInt(tmp);
        if (top != null)
        {
            return (new TreeNode(DIVISION, top, new TreeNode(getNumberToken(i))));
        }
    }

    return (null);
}

function guessConstant(num)
{
    for (var i in builtinConstants)
    {
        if (guessIsZero(num - builtinConstants[i]))
        {
            return (new TreeNode(new Token(T_IDENTIFIER, i)));
        }
    }
    return (null);
}

function guessConstantFactor(num)
{
    // guess that num = x * constant^n
    // for n = 1 to GUESS_LARGEST_EXPONENT or
    // guess that num = x/constant^n

    var guess, tmp, i;
    var constantValue;
    for (var constant in builtinConstants)
    {
        constantValue = builtinConstants[constant];

        // guess that num = x * constant^n
        tmp = num;
        for (i = 1; i < GUESS_LARGEST_EXPONENT; i++)
        {
            tmp = tmp / constantValue;
            guess = guessBasic(tmp);
            if (guess != null)
            {
                if (i == 1)
                {
                    tmp = new TreeNode(new Token(T_IDENTIFIER, constant));
                }
                else
                {
                    tmp = new TreeNode(EXPONENTIATION, 
                                       new TreeNode(new Token(T_IDENTIFIER, constant)),
                                       new TreeNode(getNumberToken(i)));
                }

                return (new TreeNode(MULTIPLICATION, guess, tmp));
            }
        }

        // guess that num = x / constant^n
        tmp = num;
        for (i = 1; i < GUESS_LARGEST_EXPONENT; i++)
        {
            tmp = tmp * constantValue;
            guess = guessBasic(tmp);
            if (guess != null)
            {
                if (i == 1)
                {
                    tmp = new TreeNode(new Token(T_IDENTIFIER, constant));
                }
                else
                {
                    tmp = new TreeNode(EXPONENTIATION, 
                                       new TreeNode(new Token(T_IDENTIFIER, constant)),
                                       new TreeNode(getNumberToken(i)));
                }

                return (new TreeNode(DIVISION, guess, tmp));
            }
        }        
    }
}

function guessConstantPower(num)
{
    // guess that num = constant^(something simple)
    // or num = (something simple)^constant

    var guess;
    for (var constant in builtinConstants)
    {
        // try constant^x
        // take logarithm to base constant
        guess = guessBasic(Math.log(num) / Math.log(builtinConstants[constant]));

        if (guess != null)
        {
            return (new TreeNode(EXPONENTIATION, 
                                 new TreeNode(new Token(T_IDENTIFIER, constant)),
                                 guess));
        }
        
        // try x^constant
        guess = guessBasic(Math.pow(num, 1 / builtinConstants[constant]));
        if (guess != null)
        {
            return (new TreeNode(EXPONENTIATION, 
                                 guess,
                                 new TreeNode(new Token(T_IDENTIFIER, constant))));
        }
    }
    return (null);
}

function guessSqrt(num)
{
    // guess that num = sqrt(x)
    var x = num * num;
    var guess = guessBasic(x);
    if (guess != null)
        return (new TreeNode(SQUAREROOT, guess));
    else
        return (null);
}

function guessLog(num)
{
    // guess that num = ln(x)
    var x = Math.exp(num);
    var guess = guessBasic(x);
    if (guess != null)
        return (new TreeNode(NATURALLOG, guess));
    else
        return (null);
}

// *****************************************************************
// Simplification functions
// These take a TreeNode of the correct type
// and return a TreeNode to represent simplified version
// These assume that all children have already been simplified to
// the maximum possible extent. Only if the entire structure of the
// tree is changed is it necessary to recursively simplify
// *****************************************************************

function getNumberToken(num)
{
    // returns a token for the given number
    // we want to use standard tokens for special numbers
    // to make comparisons elsewhere easier
    // so if we have a token that is equivalent to 0 for example,
    // we want to replace it with ZERO

    var token = NUMBERS[num];

    if (token)
        return (token);
    else
        return (new Token(T_NUMBER, num));
}

function addSelfAsTerm(node)
{
    node.top = new Array();
    node.top[0] = node;
}

function getCommonTerms(array1, array2)
{
    // array1 and array2 are arrays of TreeNodes
    // performs an intersection of the two arrays
    // returns a new array where the elements come in pairs
    // i.e. element 0 will be from array1, element1 will be the
    // same node from array2
    // will modify the two arrays to replace the elements that are
    // returned (the ones that are in both) with null

    var match;
    var common = new Array();

    if (!array1 || !array2)
        return common;

    for (var i = 0; i < array1.length; i++)
    {
        // factoring out ONEs will get us into trouble...
        // ONE isn't really a term
        if (array1[i] && array1[i].value != ONE)
        {
                match = arraylookup(array2, array1[i], treeEqual);
                if (match != -1)
                {
                        // add this match
                        common[common.length] = array1[i];
                        common[common.length] = array2[match];

                        // remove the common terms from original array
                        // need this to prevent duplicate terms from messing us up
                        array1[i] = null;
                        array2[match] = null;
                }
        }
    }

    return (common);
}

function removeCommonTerms(terms1, terms2)
{
    // finds the common terms in the two arrays
    // and replaces them with ONE. if there are no
    // common terms, then this returns NULL. otherwise
    // it returns a node that represents the common terms removed

    var common = getCommonTerms(terms1, terms2);
    var removed;

    if (common.length == 0)
        return null;

    removed = new TreeNode(ONE);

    for (var i = 0; i < common.length; i += 2)
    {
        // multiply all the common terms together
        removed = new TreeNode(MULTIPLICATION, removed, common[i].clone());
        
        common[i].replaceWith(new TreeNode(ONE));
        common[i+1].replaceWith(new TreeNode(ONE));
    }

    return (removed);
}

function handleMulDivTerms(node, top, bottom)
{
    // for multiplication and division. cancel out terms that appear
    // on top and bottom and factor out common terms.
    // the top and bottom arguments refer to the arrays in the second operand
    // for multiplication, they should just be the corresponding top/bottom array.
    // for division, they are reversed

    var commonTop, commonBottom;
    var changed = false;

    // find terms that match on the top and the bottom to cancel each other out
    changed = removeCommonTerms(node.children[0].top, bottom);
    changed = removeCommonTerms(node.children[0].bottom, top) || changed;

    // factor out common terms
    commonTop = removeCommonTerms(node.children[0].top, top);
    commonBottom = removeCommonTerms(node.children[0].bottom, bottom);

    if (commonTop || commonBottom)
    {
        var factored;

        // each term that was removed has a power of two on it
        if (!commonTop)
            factored = new TreeNode(ONE);
        else
            factored = new TreeNode(EXPONENTIATION, commonTop, new TreeNode(TWO));;

        // check if the bottom exists
        if (commonBottom)
            factored = new TreeNode(DIVISION, factored, 
                                    new TreeNode(EXPONENTIATION, commonBottom, new TreeNode(TWO)));

        // multiply the factored out term with the original
        node = new TreeNode(MULTIPLICATION, factored, node);
        
        changed = true;
    }


    if (changed)
        return (simplifyNode(node));
    else
    {
        // consolidate terms on top and bottom
        node.top = arrayappend(node.children[0].top, top);
        node.bottom = arrayappend(node.children[0].bottom, bottom);
        return (node);
    }
}

function handleAddSubTerms(node)
{
    // for addition and subtraction, factor out common terms
    var factored;
    var commonTop, commonBottom;

    // find common top and bottom terms. get the intersection of the arrays
    commonTop = removeCommonTerms(node.children[0].top, node.children[1].top);
    commonBottom = removeCommonTerms(node.children[0].bottom, node.children[1].bottom);

    if (!commonTop && !commonBottom)
    {
        addSelfAsTerm(node);
        return (node);          // no common terms
    }

    if (!commonTop)
        factored = new TreeNode(ONE);
    else
        factored = commonTop;

    // check if the bottom exists
    if (commonBottom)
        factored = new TreeNode(DIVISION, factored, commonBottom);

    // multiply the factored out term with the original
    factored = new TreeNode(MULTIPLICATION, factored, node);

    // now simplify
    return (simplifyNode(factored));
}

function simplifyNumber(node)
{
    var token;
    var retval = null;

    token = getNumberToken(node.value.value);

    if (guessNumbers)
    {
        retval = guessNumber(token);
    }

    if (retval == null)
        retval = new TreeNode(token);

    // number by itself is a top-level term
    addSelfAsTerm(retval);

    return (retval);
}

function simplifyIdentifier(node)
{
    // we have to prevent infinite recursion (e.g. x = x)
    // to prevent this, we only expand each variable once

    var value = definedIdentifiers[node.value.value];

    addSelfAsTerm(node);

    if (value)
    {
        var expanded = (node.expandedIdentifiers ? node.expandedIdentifiers : new Array());

        if (expanded[node.value.value])
        {
            parseError("infinite loop while expanding identifiers.");
            return (node);
        }
        else
        {
            // haven't expanded this identifier before
            expanded[node.value.value] = true;

            value.expandedIdentifiers = expanded;
            var answer = simplifyNode(value);
            value.expandedIdentifiers = null;

            expanded[node.value.value] = null;

            return (answer);
        }
    }
    else
        return (node);
}

function simplifyUnaryMinus(node)
{
    var operand = node.children[0];

    if (operand.value == UNARY_MINUS)
    {
        // have something like -(-(..)). get rid of both minuses
        return (operand.children[0]);
    }
    else if (operand.value.type == T_NUMBER)
    {
        // replace with -NUMBER
        return (simplifyNumber(new TreeNode(new Token(T_NUMBER, -operand.value.value))));
    }
	
    node.top = operand.top;
    node.bottom = operand.bottom;

    // nothing to do
    return (node);
}

function simplifyFunction(node)
{
    var operand = node.children[0];

    if (operand.value.type == T_NUMBER)
    {
        // can simplify this
        // lookup a function that can do the actual calculation
        return (simplifyNumber(new TreeNode(new Token(T_NUMBER, 
                                                      DO_FUNCTION[node.value](operand.value.value)))));
    }
    else if (operand.value.type == T_FUNCTION)
    {
        // some functions have inverses
        if (INVERSE_FUNCTION[node.value] == operand.value)
        {
            // functions cancel each other out
            return (operand.children[0]);
        }
    }
    else if ((node.value == SQUAREROOT) && (operand.value == EXPONENTIATION) &&
             (operand.children[1].value == TWO))
    {
        // sqrt(x^2) == x
        return (operand.children[0]);
    }

    // a function hides all terms inside of it
    addSelfAsTerm(node);

    return (node);
}

function simplifyAddition(node)
{
    var operand1 = node.children[0];
    var operand2 = node.children[1];

    if (operand1.value == ZERO)
        return (operand2);
    else if (operand2.value == ZERO)
        return (operand1);
    else if ((operand1.value.type == T_NUMBER) && (operand2.value.type == T_NUMBER))
        return (simplifyNumber(new TreeNode(new Token(T_NUMBER, 
                                                      operand1.value.value + operand2.value.value))));

    // reorder the two operands if it seems appropriate
    if (operand1.value.type == T_NUMBER)
    {
        // put numbers at the end
        // this allows numbers to collect together and simplify
        // swap the two children
        node.setChild(0, operand2);
        node.setChild(1, operand1);

        operand1 = node.children[0];
        operand2 = node.children[1];
    }

    if (operand2.value == UNARY_MINUS)
    {
        // a + (-b) == a - b
        return (simplifySubtraction(new TreeNode(SUBTRACTION, operand1, operand2.children[0])));
    }
    else if (operand1.value == UNARY_MINUS)
    {
        // (-a) + b == b - a
        return (simplifySubtraction(new TreeNode(SUBTRACTION, operand2, operand1.children[0])));
    }
    else if ((operand2.value.type == T_NUMBER) && (operand1.value == ADDITION) &&
             (operand1.children[1].value.type == T_NUMBER))
    {
        // (a + b) + c == a + (b + c)
        return (simplifyAddition(new TreeNode(ADDITION, 
                                              operand1.children[0],
                                              simplifyNumber(new TreeNode(new Token(T_NUMBER, 
                                                                                    operand1.children[1].value.value + operand2.value.value))))));
    }
    else if ((operand2.value.type == T_NUMBER) && (operand1.value == SUBTRACTION) &&
             (operand1.children[1].value.type == T_NUMBER))
    {
        // (a - b) + c == a + (c - b)
        return (simplifyAddition(new TreeNode(ADDITION, 
                                              operand1.children[0], 
                                              simplifyNumber(new TreeNode(new Token(T_NUMBER, 
                                                                                    operand2.value.value - operand1.children[1].value.value))))));
    }

    return (handleAddSubTerms(node));
}

function simplifySubtraction(node)
{
    var operand1 = node.children[0];
    var operand2 = node.children[1];

    if (operand2.value == ZERO)
        return (operand1);
    else if (operand1.value == ZERO)
    {
        // 0 - x = -x
        return (simplifyUnaryMinus(new TreeNode(UNARY_MINUS, operand2)));
    }
    else if ((operand1.value.type == T_NUMBER) && (operand2.value.type == T_NUMBER))
    {
        return (simplifyNumber(new TreeNode(new Token(T_NUMBER, 
                                                      operand1.value.value - operand2.value.value))));
    }

    if (operand2.value == UNARY_MINUS)
    {
        // a - (-b) = a + b
        return (simplifyAddition(new TreeNode(ADDITION, operand1, operand2.children[0])));
    }

    return (handleAddSubTerms(node));
}

function simplifyMultiplication(node)
{
    var operand1 = node.children[0];
    var operand2 = node.children[1];

    if ((operand1.value == ZERO) || (operand2.value == ZERO))
        return (new TreeNode(ZERO));
    else if (operand1.value == ONE)
    {
        return (operand2);
    }
    else if (operand2.value == ONE)
    {
        return (operand1);
    }
    else if (operand1.value == MINUS_ONE)
    {
        return (simplifyUnaryMinus(new TreeNode(UNARY_MINUS, operand2)));
    }
    else if (operand2.value == MINUS_ONE)
    {
        return (simplifyUnaryMinus(new TreeNode(UNARY_MINUS, operand1)));
    }
    else if ((operand1.value.type == T_NUMBER) && (operand2.value.type == T_NUMBER))
    {
        return (simplifyNumber(new TreeNode(new Token(T_NUMBER, 
                                                      operand1.value.value * operand2.value.value))));
    }
    else if ((operand1.value.type == T_FUNCTION) && (operand2.value.type == T_FUNCTION) &&
             (RECIPROCAL_FUNCTION[operand1.value] == operand2.value))
    {
        // equals one
        return (new TreeNode(ONE));
    }

    // do some reordering
    if ((operand2.value.type == T_NUMBER) || (operand1.value == DIVISION))
    {
        // push simple types to the front by making them the first operand
        // also change a / b * c to c * a / b so that we can below simplify to (c * a) / b
        node.setChild(0, operand2); 
        node.setChild(1, operand1);

        // continue with below
        operand1 = node.children[0];
        operand2 = node.children[1];
    }

    if ((operand1.value == UNARY_MINUS) || (operand2.value == UNARY_MINUS))
    {
        // a * -b = -(a * b)
        // or -a * b = -(a * b)
        // idea is to put unary minus signs towards the front

        var a;
        var b;

        if (operand1.value == UNARY_MINUS)
        {
            a = operand1.children[0];
            b = operand2;
        }
        else
        {
            // operand2.value == UNARY_MINUS
            a = operand1;
            b = operand2.children[0];
        }

        return (simplifyUnaryMinus(new TreeNode(UNARY_MINUS, 
                                                simplifyMultiplication(new TreeNode(MULTIPLICATION, a, b)))));
    }
    else if (operand2.value == DIVISION)
    {
        // a * (b / c) == (a * b) / c
        return (simplifyDivision(new TreeNode(DIVISION,
                                              simplifyMultiplication(new TreeNode(MULTIPLICATION, 
                                                                                  operand1, 
                                                                                  operand2.children[0])),
                                              operand2.children[1])));
    }
    else if (operand2.value == MULTIPLICATION)
    {
        // a * (b * c) == (a * b) * c
        // associate to the left when possible
        // this allows numbers to be pushed towards the front also

        return (simplifyMultiplication(new TreeNode(MULTIPLICATION, 
                                                    simplifyMultiplication(new TreeNode(MULTIPLICATION, 
                                                                                        operand1, 
                                                                                        operand2.children[0])),
                                                    operand2.children[1])));
    }
    else
    {
        // some things that I doubt would be very useful
        if (operand1.value == EXPONENTIATION)
        {
            // swap the two operands (multiplication is commutative)
            // I like a * b^c more than b^c * a
            node.setChild(0, operand2);
            node.setChild(1, operand1);
            operand1 = node.children[0];
            operand2 = node.children[1];
        }

        if ((operand2.value == EXPONENTIATION) &&
            (treeEqual(operand1, operand2.children[0])) &&
            (operand1.value.type == T_NUMBER))
        {
            // a * a^b == a^(b+1) if a is not a number
            return (simplifyExponentiation(new TreeNode(EXPONENTIATION, 
                                                        operand1, 
                                                        simplifyAddition(new TreeNode(ADDITION, 
                                                                                      operand2.children[1], 
                                                                                      new TreeNode(ONE))))));
        }
    }

    return (handleMulDivTerms(node, node.children[1].top, node.children[1].bottom));
}

function simplifyDivision(node)
{
    var operand1 = node.children[0];
    var operand2 = node.children[1];

    if (operand1.value == ZERO)
        return (new TreeNode(ZERO));
    else if (operand2.value == ZERO)
    {
        alert("Division by zero!");
        return (new TreeNode(ZERO));		// something better to return??
    }
    else if (operand2.value == ONE)
        return (operand1);
    else if (operand2.value == MINUS_ONE)
        return (simplifyUnaryMinus(new TreeNode(UNARY_MINUS, operand1)));
    else if ((operand1.value.type == T_NUMBER) && (operand2.value.type == T_NUMBER))
        return (simplifyNumber(new TreeNode(new Token(T_NUMBER, 
                                                      operand1.value.value / operand2.value.value))));

    // deal with moving constants to front
    if (operand2.value.type == T_NUMBER)
    {
        // push constant to front
        // a/c == 1/c * a where c is constant
        return simplifyMultiplication(new TreeNode(MULTIPLICATION,
                                                   new TreeNode(new Token(T_NUMBER, 1/operand2.value.value)),
                                                   operand1));
    }
    else if ((operand2.value == MULTIPLICATION) &&
             (operand2.children[0].value.type == T_NUMBER))
    {
        // a / (b * c) where b is constant
        // change to 1/b * a/c
        return simplifyMultiplication(new TreeNode(MULTIPLICATION,
                                                   new TreeNode(new Token(T_NUMBER, 1/operand2.children[0].value.value)),
                                                   new TreeNode(DIVISION, operand1, operand2.children[1])));
    }

    if ((operand1.value == UNARY_MINUS) || (operand2.value == UNARY_MINUS))
    {
        // replace a/(-b) with -(a/b)
        // and -a/b with -(a/b)
        // pushes the unary minuses all to the front (so they can cancel out)

        var a, b;

        if (operand1.value == UNARY_MINUS)
        {
            a = operand1.children[0];
            b = operand2;
        }
        else
        {
            // operand2.value == UNARY_MINUS
            a = operand1;
            b = operand2.children[0];
        }

        return (simplifyUnaryMinus(new TreeNode(UNARY_MINUS, 
                                                simplifyDivision(new TreeNode(DIVISION, a, b)))));
    }
    else if ((operand1.value == EXPONENTIATION) && 
             (treeEqual(operand1.children[0], operand2)))
    {
        // x ^ a / x == x ^ (a-1)
        return (simplifyExponentiation(new TreeNode(EXPONENTIATION, 
                                                    operand2,
                                                    simplifySubtraction(new TreeNode(SUBTRACTION, 
                                                                                     operand1.children[1], 
                                                                                     new TreeNode(ONE))))));
    }
    else if ((operand1.value == EXPONENTIATION) && (operand2.value == EXPONENTIATION) &&
             (treeEqual(operand1.children[0], operand2.children[0])))
    {
        // x ^ a / x ^ b == x ^ (a-b)
        return (simplifyExponentiation(new TreeNode(EXPONENTIATION, 
                                                    operand1.children[0],
                                                    simplifySubtraction(new TreeNode(SUBTRACTION, 
                                                                                     operand1.children[1], 
                                                                                     operand2.children[1])))));
    }
    else if (operand1.value == DIVISION)
    {
        // (a/b) / c == (a / (b * c))
        return (simplifyDivision(new TreeNode(DIVISION, 
                                              operand1.children[0], 
                                              simplifyMultiplication(new TreeNode(MULTIPLICATION, 
                                                                                  operand1.children[1], 
                                                                                  operand2)))));
    }
    else if (operand2.value == DIVISION)
    {
        // a/(b/c) == a * c / b
        return (simplifyDivision(new TreeNode(DIVISION, 
                                              simplifyMultiplication(new TreeNode(MULTIPLICATION, 
                                                                                  operand1, 
                                                                                  operand2.children[1])),
                                              operand2.children[0])));
    }

    return (handleMulDivTerms(node, node.children[1].bottom, node.children[1].top));
}

function simplifyExponentiation(node)
{
    var operand1 = node.children[0];
    var operand2 = node.children[1];

    if (operand1.value == ZERO)
    {
        if (operand2.value == ZERO)
        {
            alert("0^0 is not defined!");
            // we return zero anyway
        }
        return (operand1);	// 0
    }
    else if (operand2.value == ZERO)
    {
        // anything^0 = 1
        return (new TreeNode(ONE));
    }
    else if ((operand1.value == ONE) || (operand2.value == ONE))
        return (operand1);		// 1^x = 1 and x^1 = x
    else if ((operand1.value.type == T_NUMBER) && (operand2.value.type == T_NUMBER))
    {
        return (simplifyNumber(new TreeNode(new Token(T_NUMBER, 
                                                      Math.pow(operand1.value.value, 
                                                               operand2.value.value)))));
    }
    else if (operand1.value == EXPONENTIATION)
    {
        // (a^b)^c == (a^(b*c))
        return (simplifyExponentiation(new TreeNode(EXPONENTIATION, 
                                                    operand1.children[0], 
                                                    simplifyMultiplication(new TreeNode(MULTIPLICATION, 
                                                                                        operand1.children[1],
                                                                                        operand2)))));
    }
    else if (operand2.value == MINUS_ONE)
    {
        // x^-1 = 1/x
        return (simplifyDivision(new TreeNode(DIVISION, new TreeNode(ONE), operand1)));
    }
    else if ((operand1.value == MULTIPLICATION) || (operand1.value == DIVISION))
    {
        // (a*b)^c == a^c * b^c and same with division
        var term1 = simplifyExponentiation(new TreeNode(EXPONENTIATION, 
                                                        operand1.children[0],
                                                        operand2.clone()));
        var term2 = simplifyExponentiation(new TreeNode(EXPONENTIATION, 
                                                        operand1.children[1],
                                                        operand2));

        if (operand1.value == MULTIPLICATION)
            return (simplifyMultiplication(new TreeNode(MULTIPLICATION, term1, term2)));
        else
            return (simplifyDivision(new TreeNode(DIVISION, term1, term2)));
    }
    else if ((operand2.value == TWO) && (operand1.value == SQUAREROOT))
    {
        // sqrt(x)^2 == x
        return (operand1.children[0]);
    }

    // don't currently handle multiplicity of terms.
    // i.e. x^2 + x^3 won't be simplified
    addSelfAsTerm(node);
    return (node);
}

// *****************************************************************
// Entry points
// deriveNode calls appropriate derivation functions 
//	and returns the derivative. assumes everything needs to be derived
// simplifyNode is similar but does simiplification
// *****************************************************************

function deriveNode(node, diffVar)
{
    // node is a TreeNode
    // diffVar is variable to differentiate with respect to
    var token = node.value;

    if (token.type == T_NUMBER)
        deriveNumber(node);
    else if (token.type == T_IDENTIFIER)
        deriveIdentifier(node, diffVar);
    else if (token.type == T_FUNCTION)
    {
        deriveNode(node.children[0], diffVar);
        deriveFunction(node);
    }
    else if (token == UNARY_MINUS)
    {
        deriveNode(node.children[0], diffVar);
        deriveUnaryMinus(node);
    }
    else
    {
        // binary operator

        // derive each operand
        deriveNode(node.children[0], diffVar);
        deriveNode(node.children[1], diffVar);

        if ((token == ADDITION) || (token == SUBTRACTION))
            deriveAddSub(node);
        else if (token == MULTIPLICATION)
            deriveMultiplication(node);
        else if (token == DIVISION)
            deriveDivision(node);
        else if (token == EXPONENTIATION)
            deriveExponentiation(node);
        else
            assert(0, "deriveNode", "unknown token: " + token);
    }

    return (node.derivative);
}

function simplifyNode(node)
{
    var token = node.value;

    if (token.type == T_NUMBER)
        node = simplifyNumber(node);
    else if (token.type == T_IDENTIFIER)
        node = simplifyIdentifier(node);
    else if (token.type == T_FUNCTION)
    {
            node.setChild(0, simplifyNode(node.children[0]));
            node = simplifyFunction(node);
    }
    else if (token == UNARY_MINUS)
    {
        node.setChild(0, simplifyNode(node.children[0]));
        node = simplifyUnaryMinus(node);
    }
    else
    {
        // binary operator

        // simplify each operand
        node.setChild(0, simplifyNode(node.children[0]));
        node.setChild(1, simplifyNode(node.children[1]));

        if (token == ADDITION)
            node = simplifyAddition(node);
        else if (token == SUBTRACTION)
            node = simplifySubtraction(node);
        else if (token == MULTIPLICATION)
            node = simplifyMultiplication(node);
        else if (token == DIVISION)
            node = simplifyDivision(node);
        else if (token == EXPONENTIATION)
            node = simplifyExponentiation(node);
        else
            assert(0, "simplifyNode", "unknown token: " + token);
    }

    return (node);
}

// *****************************************************************
// exprUnparse(node): Function to convert the Tree back into a string
// *****************************************************************

function unparseHelper(node, operator, onLeft)
{
    // helper for exprUnparse()
    // will take a node and return the string representation of it
    // and also will add parenthesis around the node if it needs it

    // the precedence of all operators is given by the PREC table
    // all operators have left-right associativity

    // get the top token type of the node
    var type = node.value.type;

    // if the token is NOT an operator then PREC[..] will be undefined
    // We've defined it so that PREC[x] will only be defined when x is
    // a binary operator (UNARY_MINUS has a different token type than "-")

    var precNode = PREC[type];
    var needParens;

    if (!precNode || (precNode > PREC[operator]))
    {
        // either this node doesn't start with a binary operator
        // in which case it is either just a number or identifier
        // or is a unary or function.
        // or the precedence is greater than the surroundings
        // In any case, parenthesis aren't needed
        needParens = false;
    }
    else if (precNode < PREC[operator])
    {
        // need parenthesis here
        needParens = true;
    }
    else
    {
        // precedence are the same
        // now look at associativity
        // operators of same precedence associate from left to right

        // if we're on the left of the given operator then by the normal
        // rules we will associate correctly
        // if we're on the right, then we need parenthesis
        if (onLeft)
            needParens = false;
        else
            needParens = true;
    }

    if (needParens)
        return ("(" +  exprUnparse(node) + ")");
    else
        return (exprUnparse(node));
}	// unparseHelper

function exprUnparse(node)
{
    // does the opposite of exprParse
    // take a TreeNode and returns a string
    // does an inorder traversal
    // each node should have at most 2 children

    var num = node.children.length;
    var token = node.value;

    if (num == 0)
    {
        // only token types that shouldn't have any children are
        // numbers and identifiers. The value we want to return is
        // in the value of the token
        return (token.value);
    }
    else if (num == 1)
    {
        // unary and functions
        // string representations of unary and functions
        // are in the value of the token

        // for complex subexpressions (i.e. subexpression contains children itself)
        // then we add parenthesis around the whole expression
        var needParens = (node.children[0].children.length != 0);

        // also for unary minus we don't add a space after the operator
        // but for all the functions we add a space so -x but sin x
        return (token.value + (needParens ? "(" : (token == UNARY_MINUS ? "" : " ")) + 
                exprUnparse(node.children[0]) + (needParens ? ")" : ""));
    }
    else if (num == 2)
    {
        // binary operator

        var lhs = node.children[0];
        var rhs = node.children[1];

        // string representation of operator is in the type of the token
        var operator = token.type;

        return (unparseHelper(lhs, operator, true) + " " + operator + 
                " " + unparseHelper(rhs, operator, false));
    }
}	// exprUnparse

// *****************************************************************
// exprParseWithLexer(lexer): parse using the given lexer. 
// returns a TreeNode.
// *****************************************************************

function exprParseWithLexer(lexer)
{
    return (exprParser.parse(lexer));
}

// *****************************************************************
// exprParse(str): parse str and returns a TreeNode
// *****************************************************************

function exprParse(str)
{
    return (exprParser.parse(new ExprLexer(str)));
}

// Initialization code
resetIdentifiers();
setupExprParser();

// Stop hiding -->