//! Expression evaluator.

//! Evaluate arithmetic expressions encoded as a tree in an array

//! of tagged union nodes. Build expression trees, evaluate them recursively,

//! and verify results.

/// An expression node. Leaf nodes hold a number. Interior nodes hold an

/// operator and indices (into the nodes array) of their left and right children.

union Expr {

    Num(i32),

    Add(BinOp),

    Sub(BinOp),

    Mul(BinOp),

    Div(BinOp),

    Neg(u32),

}

/// Binary operator: indices of left and right child nodes.

record BinOp {

    left: u32,

    right: u32,

}

/// A pool of expression nodes with a count of allocated nodes.

record Pool {

    nodes: [Expr; 64],

    count: u32,

}

/// Evaluation error.

union EvalError {

    DivByZero

}

/// Allocate a new node, returning its index.

fn newNode(pool: *mut Pool, expr: Expr) -> u32 {

    let idx = pool.count;

    pool.nodes[idx] = expr;

    pool.count += 1;

    return idx;

}

/// Convenience constructors.

fn num(pool: *mut Pool, n: i32) -> u32 {

    return newNode(pool, Expr::Num(n));

}

fn add(pool: *mut Pool, left: u32, right: u32) -> u32 {

    return newNode(pool, Expr::Add(BinOp { left, right }));

}

fn sub(pool: *mut Pool, left: u32, right: u32) -> u32 {

    return newNode(pool, Expr::Sub(BinOp { left, right }));

}

fn mul(pool: *mut Pool, left: u32, right: u32) -> u32 {

    return newNode(pool, Expr::Mul(BinOp { left, right }));

}

fn div(pool: *mut Pool, left: u32, right: u32) -> u32 {

    return newNode(pool, Expr::Div(BinOp { left, right }));

}

fn neg(pool: *mut Pool, child: u32) -> u32 {

    return newNode(pool, Expr::Neg(child));

}

/// Recursively evaluate the expression tree rooted at nodes[idx].

fn eval(nodes: *[Expr], idx: u32) -> i32 throws (EvalError) {

    let node = nodes[idx];

    match node {

        case Expr::Num(n) => {

            return n;

        }

        case Expr::Add(op) => {

            return try eval(nodes, op.left) + try eval(nodes, op.right);

        }

        case Expr::Sub(op) => {

            return try eval(nodes, op.left) - try eval(nodes, op.right);

        }

        case Expr::Mul(op) => {

            return try eval(nodes, op.left) * try eval(nodes, op.right);

        }

        case Expr::Div(op) => {

            let l = try eval(nodes, op.left);

            let r = try eval(nodes, op.right);

            if r == 0 {

                throw EvalError::DivByZero;

            }

            return l / r;

        }

        case Expr::Neg(child) => {

            return 0 - try eval(nodes, child);

        }

    }

}

/// Count the total number of nodes in the tree rooted at idx.

fn countNodes(nodes: *[Expr], idx: u32) -> u32 {

    let node = nodes[idx];

    match node {

        case Expr::Num(_) => {

            return 1;

        }

        case Expr::Add(op) => {

            return 1 + countNodes(nodes, op.left) + countNodes(nodes, op.right);

        }

        case Expr::Sub(op) => {

            return 1 + countNodes(nodes, op.left) + countNodes(nodes, op.right);

        }

        case Expr::Mul(op) => {

            return 1 + countNodes(nodes, op.left) + countNodes(nodes, op.right);

        }

        case Expr::Div(op) => {

            return 1 + countNodes(nodes, op.left) + countNodes(nodes, op.right);

        }

        case Expr::Neg(child) => {

            return 1 + countNodes(nodes, child);

        }

    }

}

/// Reset the node pool.

fn reset(pool: *mut Pool) {

    pool.count = 0;

}

/// Test 1: Simple addition: 3 + 4 = 7

fn testSimpleAdd(pool: *mut Pool) -> i32 {

    reset(pool);

    let root = add(pool, num(pool, 3), num(pool, 4));

    assert try! eval(&pool.nodes[..], root) == 7;

    return 0;

}

/// Test 2: Nested expression: (2 + 3) * (4 - 1) = 5 * 3 = 15

fn testNested(pool: *mut Pool) -> i32 {

    reset(pool);

    let left = add(pool, num(pool, 2), num(pool, 3));

    let right = sub(pool, num(pool, 4), num(pool, 1));

    let root = mul(pool, left, right);

    assert try! eval(&pool.nodes[..], root) == 15;

    assert countNodes(&pool.nodes[..], root) == 7;

    return 0;

}

/// Test 3: Complex expression: ((10 + 5) * 2 - 6) / 4 = (30 - 6) / 4 = 24 / 4 = 6

fn testComplex(pool: *mut Pool) -> i32 {

    reset(pool);

    let a = add(pool, num(pool, 10), num(pool, 5));

    let b = mul(pool, a, num(pool, 2));

    let c = sub(pool, b, num(pool, 6));

    let root = div(pool, c, num(pool, 4));

    assert try! eval(&pool.nodes[..], root) == 6;

    return 0;

}

/// Test 4: Negation: -(3 + 4) = -7

fn testNeg(pool: *mut Pool) -> i32 {

    reset(pool);

    let root = neg(pool, add(pool, num(pool, 3), num(pool, 4)));

    assert try! eval(&pool.nodes[..], root) == -7;

    return 0;

}

/// Test 5: Deep tree: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36

fn testDeep(pool: *mut Pool) -> i32 {

    reset(pool);

    let mut root = num(pool, 1);

    let values: [i32; 7] = [2, 3, 4, 5, 6, 7, 8];

    for v in values {

        root = add(pool, root, num(pool, v));

    }

    assert try! eval(&pool.nodes[..], root) == 36;

    assert countNodes(&pool.nodes[..], root) == 15;

    return 0;

}

/// Test 6: Mixed operations: (100 - 3 * (2 + 8)) / 7 = (100 - 30) / 7 = 70 / 7 = 10

fn testMixed(pool: *mut Pool) -> i32 {

    reset(pool);

    let inner = add(pool, num(pool, 2), num(pool, 8));

    let product = mul(pool, num(pool, 3), inner);

    let diff = sub(pool, num(pool, 100), product);

    let root = div(pool, diff, num(pool, 7));

    assert try! eval(&pool.nodes[..], root) == 10;

    return 0;

}

/// Test 7: Single number.

fn testSingleNum(pool: *mut Pool) -> i32 {

    reset(pool);

    let root = num(pool, 42);

    assert try! eval(&pool.nodes[..], root) == 42;

    assert countNodes(&pool.nodes[..], root) == 1;

    return 0;

}

@default fn main() -> i32 {

    let mut pool: Pool = Pool { nodes: [Expr::Num(0); 64], count: 0 };

    let r1 = testSimpleAdd(&mut pool);

    if r1 != 0 {

        return 10 + r1;

    }

    let r2 = testNested(&mut pool);

    if r2 != 0 {

        return 20 + r2;

    }

    let r3 = testComplex(&mut pool);

    if r3 != 0 {

        return 30 + r3;

    }

    let r4 = testNeg(&mut pool);

    if r4 != 0 {

        return 40 + r4;

    }

    let r5 = testDeep(&mut pool);

    if r5 != 0 {

        return 50 + r5;

    }

    let r6 = testMixed(&mut pool);

    if r6 != 0 {

        return 60 + r6;

    }

    let r7 = testSingleNum(&mut pool);

    if r7 != 0 {

        return 70 + r7;

    }

    return 0;

}