import java.lang.*;
import java.io.*;
import java.util.Random;
import hj.lang.DataDrivenFuture;

/*
 * HJ version ported from Java version at http://www.csse.monash.edu.au/~lloyd/tildeProgLang/Java2/Exp/.
 *
 * @author Vincent Cave 
 * @author Sanjay Chatterjee
 * @author Max Grossman
 * @author Vivek Sarkar (vsarkar@rice.edu)
 *
 * See below for acknowledgments for original code
 * 
 * L. Allison, September 2001,
 * School of Computer Science and Software Engineering,
 * Monash University, Australia 3800.
 * 
 * Released under the GNU General Public License  Version 2, June 1991.
 */

public class MatrixEvalDDF // The main program
{

    public static class Matrix {
        public final int cols;
        public final int rows;
        public final int[][] data;

        public Matrix(int rows, int cols) {
            this.rows = rows;
            this.cols = cols;
            this.data = new int[rows][cols];
        }
    }

    public static Matrix matrixAdd(Matrix a, Matrix b) {
        int rows = a.rows;
        int cols = a.cols;
        assert (b.rows == rows && b.cols == cols) : "a and b are not conformable for operation +";
        Matrix result = new Matrix(rows,cols);
        for (point[i,j] : [0:rows-1,0:cols-1]) result.data[i][j] = a.data[i][j] + b.data[i][j];
        return result;
    }

    public static Matrix matrixMinus(Matrix a, Matrix b) {
        int rows = a.rows;
        int cols = a.cols;
        assert(b.rows == rows && b.cols == cols) : "a and b are not conformable for operation -";
        Matrix result = new Matrix(rows,cols);
        for (point[i,j] : [0:rows-1,0:cols-1]) result.data[i][j] = a.data[i][j] - b.data[i][j];
        return result;
    }

    public static Matrix matrixMultiply(Matrix a, Matrix b) {
        int arows = a.rows;
        int acols = a.cols;
        int brows = b.rows;
        int bcols = b.cols;
        if (acols != brows) { Expression.error("Invalid dimensions for matrix multiply"); } // a and b are not conformable
        Matrix result = new Matrix(arows,bcols);
        for (point[i,j] : [0:arows-1,0:bcols-1]) {
            result.data[i][j] = 0; 
            for (point[k] : [0:acols-1]) {
                result.data[i][j] += a.data[i][k] * b.data[k][j];
            }
        }
        return result;
    }

    public static Matrix matrixId(Matrix a) {
        int rows = a.rows;
        int cols = a.cols;
        Matrix result = new Matrix(rows,cols);
        for (point[i,j] : [0:rows-1,0:cols-1]) result.data[i][j] = a.data[i][j];
        return result;
    }

    public static Matrix matrixNeg(Matrix a) {
        int rows = a.rows;
        int cols = a.cols;
        Matrix result = new Matrix(rows,cols);
        for (point[i,j] : [0:rows-1,0:cols-1]) result.data[i][j] = -a.data[i][j];
        return result;
    }

    public static void printMatrix(Matrix a) {
        int rows = a.rows;
        int cols = a.cols;
        System.out.println("[");
        for (point[i] : [0:rows-1]) {
            System.out.print(" [ ");
            for (point[j] : [0:cols-1]) System.out.print(a.data[i][j] + " ");
            System.out.println("]");
        }
        System.out.println("]");
    }

    public static void main(String[] argv) {
        if (argv.length != 1) {
            System.out.println("usage: hj MatrixEvalDDF input_file_name");
            return;
        }
        FileInputStream in = null;
        Expression e = null;
        try {
            in = new FileInputStream(argv[0]);
            Syntax syn = new Syntax(new Lexical(in));
            e = syn.exp(); // parse input expression
        } catch (IOException io) {
            io.printStackTrace();
            return;
        }
        System.out.print("Input expression:");
        System.out.println(e.toString()); // print input expression

        long start = System.nanoTime();
        DataDrivenFuture<MatrixEvalDDF.Matrix> result_ddf = new DataDrivenFuture<MatrixEvalDDF.Matrix>();
        async e.eval(result_ddf);
        async await(result_ddf) {
            MatrixEvalDDF.Matrix result = result_ddf.get(); // evaluate input expression
            long end = System.nanoTime();

            System.out.println("result[0][0] = " + result.data[0][0]);
            System.out.println("Time taken for expression evaluation = " + (end-start)/1000000 + " milliseconds");
            // printMatrix(result);
        }
    }// main
}

abstract class Expression // Defines expression parse-trees
{
    public abstract void appendSB(StringBuffer sb); // printing

    public abstract MatrixEvalDDF.Matrix eval(DataDrivenFuture<MatrixEvalDDF.Matrix> d); // evaluate expression


    public static class Ident extends Expression // Ident
    {
        public final String id; // e.g. x
        public int rows, cols, seed;

        public Ident(String id) {
            this.id = id;
            extractDims(id);
        }

        public void appendSB(StringBuffer sb) {
            sb.append(id);
        }

        public void extractDims(String id) {
            int indexOfM = id.indexOf('m');
            if(indexOfM != 0) {error("indexOfM != 0");} // ident must start with 'm'
            int indexOfX = id.indexOf('x');
            if (indexOfX == -1) { // identity matrix case
                rows = Integer.parseInt(id.substring(indexOfM + 1));
                if(rows <= 0) {error("rows <= 0");}
                cols = -1;
                seed = -1;
            }
            else { // random matrix case
                int indexOfS = id.indexOf('s');
                if (indexOfX >= indexOfS) { error("indexOfX >= indexOfS"); }
                rows = Integer.parseInt(id.substring((indexOfM + 1), indexOfX));
                if(rows <= 0) {error("rows <= 0");};
                cols = Integer.parseInt(id.substring((indexOfX + 1), indexOfS));
                if(cols <= 0) {error("cols <= 0");};
                seed = Integer.parseInt(id.substring(indexOfS + 1));
            }
        }

        public MatrixEvalDDF.Matrix eval(DataDrivenFuture<MatrixEvalDDF.Matrix> d) {
            MatrixEvalDDF.Matrix result;
            if (cols == -1) { // identity matrix case
                cols = rows;
                result = new MatrixEvalDDF.Matrix(rows,cols); 
                for (point[i] : [0:rows-1]) result.data[i][i] = 1;
            }
            else { // random matrix case
                Random r = new Random(seed);
                result = new MatrixEvalDDF.Matrix(rows,cols); 
                for (point[i,j] : [0:rows-1,0:cols-1]) result.data[i][j] = r.nextInt();
            }
            d.put(result);
            return null;
        }
    }

    public static class IntCon extends Expression // IntCon
    {
        public final int n; // e.g. 3

        public IntCon(int n) {
            this.n = n;
        }

        public void appendSB(StringBuffer sb) {
            sb.append(String.valueOf(n));
        }

        public MatrixEvalDDF.Matrix eval(DataDrivenFuture<MatrixEvalDDF.Matrix> d) {
            error("Unhandled Integer scalar");
            return null;
        }
    }

    public static class Unary extends Expression // Unary
    {
        public final int opr;
        public final Expression e; // e.g. -7

        public Unary(int opr, Expression e) {
            this.e = e;
            this.opr = opr;
        }

        public void appendSB(StringBuffer sb) {
            sb.append("(" + Lexical.Symbol[opr] + " ");
            e.appendSB(sb);
            sb.append(")");
        }

        public MatrixEvalDDF.Matrix eval(DataDrivenFuture<MatrixEvalDDF.Matrix> d) {
            DataDrivenFuture<MatrixEvalDDF.Matrix> r = new DataDrivenFuture<MatrixEvalDDF.Matrix>();
            async e.eval(r);
            switch (opr) {
            case Lexical.plus:
                async await(r) { MatrixEvalDDF.Matrix result = MatrixEvalDDF.matrixId(r.get());  d.put(result); }
                break;
            case Lexical.minus:
                async await(r) { MatrixEvalDDF.Matrix result = MatrixEvalDDF.matrixNeg(r.get());  d.put(result); }
                break;
            default:
                error("Unhandled Unary operator");
            }
            return null;
        }
    }// Unary

    public static class Binary extends Expression // Binary
    {
        public final int opr;
        public final Expression lft, rgt; // e.g. x+3

        public Binary(int opr, Expression lft, Expression rgt) {
            this.opr = opr;
            this.lft = lft;
            this.rgt = rgt;
        }

        public void appendSB(StringBuffer sb) {
            sb.append("(");
            lft.appendSB(sb);
            sb.append(" " + Lexical.Symbol[opr] + " ");
            rgt.appendSB(sb);
            sb.append(")");
        }

        public MatrixEvalDDF.Matrix eval(DataDrivenFuture<MatrixEvalDDF.Matrix> d) {
            DataDrivenFuture<MatrixEvalDDF.Matrix> lft_ddf = new DataDrivenFuture<MatrixEvalDDF.Matrix>();
            DataDrivenFuture<MatrixEvalDDF.Matrix> rgt_ddf = new DataDrivenFuture<MatrixEvalDDF.Matrix>();
            async lft.eval(lft_ddf);
            async rgt.eval(rgt_ddf);

            switch (opr) {
            case Lexical.plus:
                async await(lft_ddf, rgt_ddf) { MatrixEvalDDF.Matrix result = MatrixEvalDDF.matrixAdd(lft_ddf.get(), rgt_ddf.get()); d.put(result); }
                break;
            case Lexical.minus:
                async await(lft_ddf, rgt_ddf) { MatrixEvalDDF.Matrix result = MatrixEvalDDF.matrixMinus(lft_ddf.get(), rgt_ddf.get()); d.put(result); }
                break;
            case Lexical.times:
                async await(lft_ddf, rgt_ddf) { MatrixEvalDDF.Matrix result = MatrixEvalDDF.matrixMultiply(lft_ddf.get(), rgt_ddf.get()); d.put(result); }
                break;
            default:
                error("Unhandled binary operator");
            }
            return null;
        }
    }// Binary


    /* Using a StringBuffer gives linear rather than quadratic complexity. */
    public String toString() {
        StringBuffer sb = new StringBuffer(); // efficiency!
        appendSB(sb);
        return sb.toString();
    }// toString

    public static void error(String msg) {
        System.out.println("\nError: " + msg);
        System.exit(1);
    }// error

}// Expression class

class Lexical // Lexical processor of symbols
{
    InputStream inp;

    int sy = -1; // lexical state variables
    char ch = ' ';
    byte[] buffer = new byte[1];
    boolean eof = false;
    String theWord = "<?>";
    int theInt = 666;

    public static final int // symbol codes...
    word = 0,
    numeral = 1, open = 2, // (
    close = 3, // )
    plus = 4, // +
    minus = 5, // -
    times = 6, // *
    over = 7, // /
    eofSy = 8;

    public static final String[] Symbol = new String[] { "<word>", "<numeral>",
        "(", ")", "+", "-", "*", "/", "<eof>" };// Symbol

    public Lexical(InputStream inp) // constructor
    {
        this.inp = inp;
        insymbol();
    }// constructor

    public int sy() {
        return sy;
    } // Define

    public boolean eoi() {
        return sy == eofSy;
    } // what a

    public String theWord() {
        return theWord;
    } // Lexical

    public int theInt() {
        return theInt;
    } // object is

    public void insymbol() // insymbol
    // get the next symbol from the input stream
    {
        if (sy == eofSy)
            return;
        while (ch == ' ')
            getch(); // skip white space

        if (eof)
            sy = eofSy;

        else if (Character.isLetter(ch)) // words
        {
            StringBuffer w = new StringBuffer();
            while (Character.isLetterOrDigit(ch)) {
                try {
                    //Workaround compiler bug
                    if (false) {
                        throw new java.io.IOException();
                    } 
                    w.append(ch);
                } catch (java.io.IOException e) {

                }
                getch();
            }
            theWord = w.toString();
            sy = word;
        }

        else if (Character.isDigit(ch)) // numbers
        {
            theInt = 0;
            while (Character.isDigit(ch)) {
                theInt = theInt * 10 + ((int) ch) - ((int) '0');
                getch();
            }
            sy = numeral;
        }

        else // special symbols
        {
            int ch2 = ch;
            getch();
            switch (ch2) {
            case '+':
                sy = plus;
                break;
            case '-':
                sy = minus;
                break;
            case '*':
                sy = times;
                break;
                // case '/': sy = over; break;
            case '(':
                sy = open;
                break;
            case ')':
                sy = close;
                break;
            default:
                error("bad symbol");
            }
        }
    }// insymbol

    void getch() // getch
    // NB. changes variable ch as a side-effect.
    {
        ch = '.';
        if (sy == eofSy)
            return;
        try {
            int n = 0;
            if (inp.available() > 0)
                n = inp.read(buffer);
            if (n <= 0)
                eof = true;
            else
                ch = (char) buffer[0];
        } catch (Exception e) {
        }
        if (ch == '\n' || ch == '\t')
            ch = ' ';
    }// getch

    void skipRest() {
        if (!eof)
            System.out.print("skipping to end of input...");
        int n = 0;
        while (!eof) {
            if (n % 80 == 0)
                System.out.println(); // break line
            System.out.print(ch);
            n++;
            getch();
        }
        System.out.println();
    }// skipRest

    public void error(String msg) // error
    {
        System.out.println("\nError: " + msg + " sy=" + sy + " ch=" + ch
                + " theWord=" + theWord + " theInt=" + theInt);
        skipRest();
        System.exit(1);
    }// error

}// Lexical class

class Syntax {
    private final Lexical lex;

    private final long // useful Symbol Sets
    unOprs = (1L << Lexical.minus),

    binOprs = (1L << Lexical.plus) | (1L << Lexical.minus)
    | (1L << Lexical.times) | (1L << Lexical.over),

    startsExp = unOprs | (1L << Lexical.word) | (1L << Lexical.numeral)
    | (1L << Lexical.open);

    int[] oprPriority = new int[Lexical.eofSy];

    void init() {
        for (int i = 0; i < oprPriority.length; i++)
            oprPriority[i] = 0;
        oprPriority[Lexical.plus] = 1;
        oprPriority[Lexical.minus] = 1;
        oprPriority[Lexical.times] = 2;
        oprPriority[Lexical.over] = 2;
    }// init

    public Syntax(Lexical lex) // constructor
    {
        this.lex = lex;
        init();
    }

    private boolean syIs(int sym) // test and skip symbol
    {
        if (lex.sy() == sym) {
            lex.insymbol();
            return true;
        }
        return false;
    }// syIs

    private void check(int sym) // check and skip a particular symbol
    {
        if (lex.sy() == sym)
            lex.insymbol();
        else
            error(Lexical.Symbol[sym] + " Expected");
    }// check

    public Expression exp() // exp()
    {
        Expression e = exp(1);
        check(Lexical.eofSy);
        return e;
    }

    private Expression exp(int priority) // exp(...)
    {
        Expression e = null;
        if (priority < 3) {
            e = exp(priority + 1);
            int sym = lex.sy();

            while (member(sym, binOprs) && oprPriority[sym] == priority) {
                lex.insymbol(); // e.g. 1+2+3
                e = new Expression.Binary(sym, e, exp(priority + 1));
                sym = lex.sy();
            }
        }

        else if (member(lex.sy(), unOprs)) // unary op, e.g. -3
        {
            int sym = lex.sy();
            lex.insymbol();
            e = new Expression.Unary(sym, exp(priority));
        }

        else // operand
        {
            switch (lex.sy()) {
            case Lexical.word:
                e = new Expression.Ident(lex.theWord);
                lex.insymbol();
                break;
            case Lexical.numeral:
                e = new Expression.IntCon(lex.theInt);
                lex.insymbol();
                break;
            case Lexical.open: // e.g. (e)
                lex.insymbol();
                e = exp(1);
                check(Lexical.close);
                break;
            default:
                error("bad operand");
            }// switch
        }// if

        return e;
    }// exp(...)

    boolean member(int n, long s) // ? is n a member of the "set" s ?
    {
        return ((1L << n) & s) != 0;
    }

    void error(String msg) {
        lex.error("Syntax: " + msg);
    } // error

}// Syntax class