// UnitConversionCode.js

function ConvertUnits (sourceUnits, targetUnits)
{
    var sourceReduced = UnitReduce (sourceUnits);
    var targetReduced = UnitReduce (targetUnits);
    if (AreReducedUnitsCompatible (sourceReduced, targetReduced)) {
        return uq_divide (sourceReduced.factor, targetReduced.factor);
    } else {
        var sourceTypeName = FindTypeForReducedUnit (sourceReduced);
        var targetTypeName = FindTypeForReducedUnit (targetReduced);
        if (sourceTypeName) {
            if (targetTypeName) {
                throw "Cannot convert from " + sourceTypeName + " to " + targetTypeName;
            } else {
                throw "Cannot convert from " + sourceTypeName + " to incompatible units";
            }
        } else {
            if (targetTypeName) {
                throw "Cannot convert to " + targetTypeName + " from incompatible units";
            } else {
                throw "Cannot convert between incompatible units";
            }
        }
    }
}

function AreReducedUnitsCompatible (u1, u2)
{
    if (!u1.is_reduced) {
        throw "Unreduced units found in 'u1'";
    }
    
    if (!u2.is_reduced) {
        throw "Unreduced units found in 'u2'";
    }
    
    for (var i in u1.definition) {
        if (u1.definition[i].exponent != u2.definition[i].exponent) {
            return false;
        }
    }
    
    return true;
}

function Unit (unitString)
{
    // unitString = "m^3*kg^-2/s/s"
    this.symbol = unitString;
    this.factor = uq_exact(1);
    
    var basisArray = unitString.split(/[*\/]/);
    var opArray = GetOpArray (unitString);
    
    this.definition = [];
    
    var exponent;
    var i;
    for (i=0; i < basisArray.length; ++i) {
        var term = basisArray[i].split(/\^/);
        switch (term.length) {
            case 1:
                exponent = 1;
                break;
                
            case 2:
                exponent = parseInt (trim(term[1]));
                break;
                
            default:
                throw "Invalid term '" + basisArray[i] + "' in unit expression";
        }
        var symbol = trim(term[0]);
        LookupUnitSymbol (symbol);     // ignore return value... just check for undefined symbols
        this.definition[i] = { 'exponent':exponent * opArray[i], 'symbol':symbol };
    }
}

function trim (stringToTrim)     // http://www.somacon.com/p355.php
{       
	return stringToTrim.replace(/^\s+|\s+$/g,"");
}

function GetOpArray (unitString)
{
    var opArray = [1];
    for (var i=0; i < unitString.length; ++i) {
        switch (unitString.charAt(i)) {
            case '/':
                opArray[opArray.length] = -1;
                break;
                
            case '*':
                opArray[opArray.length] = 1;
                break;
        }
    }
    return opArray;
}

function UnitReduce (unit)
{
    var exponent = [];
    var i;
    for (i=0; i < FundamentalUnits.length; ++i) {
        exponent[i] = 0;
    }
    
    var factor = uq_copy (unit.factor);    
    for (i=0; i < unit.definition.length; ++i) {
        factor = uq_multiply (factor, UnitReduceFactor (exponent, unit.definition[i]));
    }
    
    var reduced = { 'definition':[], 'symbol':unit.symbol, 'factor':factor, 'is_reduced':true };
    for (i=0; i < FundamentalUnits.length; ++i) {
        reduced.definition[i] = { 'symbol':FundamentalUnits[i], 'exponent':exponent[i] };
    }
    
    return reduced;
}

function UnitReduceFactor (exponent, uf)
{
    var i;
    var unit = LookupUnitSymbol(uf.symbol);
    if (unit.definition == null) {
        // this is a fundamental unit
        exponent[unit.findex] += uf.exponent;
        return uq_exact(1);
    } else {
        // this is a derived unit
        var reduced = UnitReduce (unit);
        for (i=0; i < reduced.definition.length; ++i) {
            exponent[i] += reduced.definition[i].exponent * uf.exponent;
        }
        return uq_power (reduced.factor, uf.exponent);
    }
}

function LookupUnitSymbol (symbol)
{
    var unit = SymbolTable[symbol];
    if (unit == null) {
        throw "Undefined unit symbol '" + symbol + "'";
    } else {
        return unit;
    }
}


function FindTypeForReducedUnit (reduced)
{
    for (var typename in DerivedTypes) {
        var type = DerivedTypes[typename];
        var match = true;
        for (var i=0; i < reduced.definition.length; ++i) {
            if (reduced.definition[i].exponent != type.reduced[i]) {
                match = false;
                break;
            }
        }
        if (match) {
            return typename.replace(/_/g,' ');
        }
    }
    return null;
}


function DefineCustomUnit (symbol, description, basis)
{
    DeclareCustomUnit (symbol, description, basis);
    CompileCustomUnit (symbol);
}

function RecompileCustomUnits()
{
    for (var symbol in SymbolTable) {
        var entry = SymbolTable[symbol];
        if (entry != null) {    // watch out for deleted symbols
            if (entry.is_custom) {
                CompileCustomUnit (symbol);
            }
        }
    }
}

function CompileCustomUnit (symbol)
{
    var entry = SymbolTable[symbol];
    if (entry == null) {
        throw "Undefined custom unit symbol '" + symbol + "'";
    }
    
    if (!entry.is_custom) {
        throw "Symbol '" + symbol + "' does not refer to a custom unit";
    }
    
    if (entry.expr == null) {
        throw "Symbol '" + symbol + "' has no cached expression";
    }

    if (entry.original_definition == null) {
        throw "Symbol '" + symbol + "' has no original definition string";
    }
    
    entry.pending = true;   // checks for circularity
    
    // Recursively compile all units we refer to, before we allow this unit to be evaluated.
    var rset = {};
    ExprReferredSymbols (rset, entry.expr);
    for (var refsym in rset) {
        var refunit = SymbolTable[refsym];
        if (refunit == null) {
            throw "Symbol '" + symbol + "' refers to undeclared symbol '" + refsym + "'";
        }
        if (refunit.is_custom) {
            if (refunit.pending) {
                throw "Attempt to compile unit '" + refsym + "' with circular definition";
            }
            CompileCustomUnit (refsym);
        }
    }
    
    entry.pending = false;  // stop checking for circular definition
    
    var unit = entry.expr.eval();
    entry.factor = uq_copy (unit.factor);
    entry.definition = unit.definition;
}

function DeclareCustomUnit (symbol, description, basis)
{
    if (typeof(symbol) != 'string') {
        throw "Unit symbol must be string type";
    }
    
    if (!/^[a-zA-Z_]+$/.test(symbol)) {
        throw "Invalid symbol '" + symbol + "'";
    }
    
    var existing = SymbolTable[symbol];
    if (existing != null) {
        if (existing.is_custom == null) {
            throw "Cannot redefine built-in unit symbol '" + symbol + "'";
        }
    }
    
    var expr = Parse_ExpressionString (basis);

    var entry = {
        'name': description,
        'is_custom': true,
        'original_definition': basis,
        'expr': expr
    };
    
    SymbolTable[symbol] = entry;
    var cycle = ValidateSymbolTable (SymbolTable);
    if (cycle != null) {
        SymbolTable[symbol] = existing;     // put symbol table back the way it was
        throw "Circular definition encountered: " + cycle;
    }
}


function ValidateSymbolTable (table)
{
    var symbol;
    for (symbol in table) {
        if (table[symbol] != null) {    // watch out for deleted symbols
            table[symbol].refby = null;
            table[symbol].symbol = symbol;
        }
    }
    for (symbol in table) {
        if (table[symbol] != null) {    // watch out for deleted symbols
            var cycle = LookForCycles (table, table[symbol], null);
            if (cycle != null) {
                return cycle;
            }
        }
    }
    return null;
}


function LookForCycles (table, x, r)
{
    var i;
    var cycle = null;
    if (x.refby != null) {
        cycle = "";
        for (var c=x; c != null; c = c.refby) {
            if (cycle != "") {
                cycle = " ==> " + cycle;
            }
            cycle = c.symbol + cycle;
            if (c.refby == x) {
                break;
            }
        }
    } else {
        x.refby = r;
        if (x.definition != null) {
            for (i=0; i < x.definition.length; ++i) {
                var ref = x.definition[i].symbol;
                var y = table[ref];
                if (y == null) {
                    throw "Undefined unit symbol '" + ref + "' in reduced definition of '" + x.symbol + "'";
                }
                cycle = LookForCycles (table, y, x);
                if (cycle != null) {
                    break;
                }
            }
        }
        if (cycle == null) {
            // We didn't find any cycles in x.definition, or x.definition is null.
            // So try again with x.expr...
            if (x.expr != null) {
                var rset = {};
                ExprReferredSymbols (rset, x.expr);
                for (var ref in rset) {
                    var y = table[ref];
                    if (y == null) {
                        throw "Undefined unit symbol '" + ref + "' in parsed expression for '" + x.symbol + "'";
                    }
                    cycle = LookForCycles (table, y, x);
                    if (cycle != null) {
                        break;
                    }
                }
            }
        }
        x.refby = null;
    }
    return cycle;
}

function ExprReferredSymbols (rset, expr)
{
    var i;

    // Returns the set of symbols referred to in this expression.
    if (expr == null) {
        throw "ExprReferredSymbols:  expr == null";
    }
    
    switch (expr.type) {
        case "operator":
            for (i=0; i < expr.arg.length; ++i) {
                ExprReferredSymbols (rset, expr.arg[i]);
            }
            break;
            
        case "identifier":
            rset[expr.value] = true;
            break;
        
        case null:
            throw "ExprReferredSymbols: expr.type == null";                    
    }
}

function FindReferringSymbols (symset, symbol)
{
    for (var othersym in SymbolTable) {
        var unit = SymbolTable[othersym];
        if (unit && unit.is_custom) {
            if (ExprRefersTo (unit.expr, symbol)) {
                symset[othersym] = true;
                FindReferringSymbols (symset, othersym);
            }
        }
    }
}

function SetToArray (s)
{
    var a = [];
    for (var x in s) {
        a.push (x);
    }
    return a;
}

function ExprRefersTo (expr, symbol)
{
    var i;

    if (expr == null) {
        throw "ExprRefersTo:  expr == null";
    }
    
    switch (expr.type) {
        case "operator":
            for (i=0; i < expr.arg.length; ++i) {
                if (ExprRefersTo (expr.arg[i], symbol)) {
                    return true;
                }
            }
            break;
            
        case "identifier":
            return expr.value == symbol;
    
        case null:
            throw "ExprRefersTo:  expr.type == null";
    }
    
    return false;
}

//------------------------------------------------------------

function UncertainQuantity (value, uncertainty)     // represents (value +/- uncertainty)
{
    this.value = value;
    this.uncertainty = Math.abs (uncertainty);  // (a +/- b) means the same thing as (a +/- (-b)).
}

function uq_exact (x)
{
    return new UncertainQuantity (x, 0);
}

function uq_copy (a)
{
    uq_test (a);
    return new UncertainQuantity (a.value, a.uncertainty);
}

function uq_test (x)
{
    if (x.value == null || x.uncertainty == null || x.uncertainty < 0) {
        throw "Expected an UncertainQuantity";
    }
}

function uq_test_strict (x)
{
    uq_test (x);
    if (x.value != 0 && x.uncertainty >= Math.abs(x.value)) {
        throw "UncertainQuantity fails multiplication/division test: uncertainty has greater/equal magnitude than value.";
    }
}

function uq_add (a, b)
{
    uq_test (a);
    uq_test (b);
    return new UncertainQuantity (a.value + b.value, a.uncertainty + b.uncertainty);
}

function uq_subtract (a, b)
{
    uq_test (a);
    uq_test (b);
    return new UncertainQuantity (a.value - b.value, a.uncertainty + b.uncertainty);
}

function uq_multiply (a, b)
{
    uq_test_strict (a);
    uq_test_strict (b);
    return uq_from_list (
        (a.value + a.uncertainty) * (b.value + b.uncertainty),
        (a.value + a.uncertainty) * (b.value - b.uncertainty),
        (a.value - a.uncertainty) * (b.value + b.uncertainty),
        (a.value - a.uncertainty) * (b.value - b.uncertainty)
    );
}

function uq_divide (a, b)
{
    uq_test_strict (a);
    uq_test_strict (b);
    if (b.value == 0) {
        throw "UncertainQuantity: division by zero";
    }
    return uq_from_list (
        (a.value + a.uncertainty) / (b.value + b.uncertainty),
        (a.value + a.uncertainty) / (b.value - b.uncertainty),
        (a.value - a.uncertainty) / (b.value + b.uncertainty),
        (a.value - a.uncertainty) / (b.value - b.uncertainty)
    );
}

function uq_from_list ()
{
    if (arguments.length == 0) {
        throw "uq_from_list called with zero arguments!";
    }
    
    var min = arguments[0];
    var max = arguments[0];
    for (var i=1; i < arguments.length; ++i) {
        if (arguments[i] < min) {
            min = arguments[i];
        }
        if (arguments[i] > max) {
            max = arguments[i];
        }
    }
    
    return new UncertainQuantity ((max+min)/2, (max-min)/2);
}

function uq_power (u, n)
{
    uq_test_strict (u);
    if (u.value - u.uncertainty <= 0) {
        throw "UncertainQuantity:  cannot raise possibly negative number to a power";
    }
    return uq_from_list (
        Math.pow (u.value - u.uncertainty, n),
        Math.pow (u.value + u.uncertainty, n)
    );
}