import java.util.Vector;

public class Expression implements Comparable, Cloneable, ComparableExpression
{
    private boolean isAtomic;
    private Rational myValue;
    private ComparableVector subExpressions;
    private byte positives;
    //private int negatives;
    private boolean isAdditive;
    private byte ones;
    private static Rational one = new Rational(1);
    private static Rational zero = new Rational(0);
    
    private byte negatives() {
        return((byte)(this.subExpressions.size() - this.positives));
    }
    
    public Expression()
    {
        this.ones = 0;
        this.isAtomic = true;
        this.myValue = this.one;
    }
    
    public Expression(Rational r)
    {
        this();
        this.myValue = new Rational(r);
    }

    public Expression(Expression a, ArithOperator o, Expression b) throws ExpressionException, BadOperatorException
    {
        this();
        this.makeExpression(a,o,b);
    }

    public Expression(Rational a, ArithOperator o, Expression b) throws ExpressionException, BadOperatorException
    {
        this();
        this.makeExpression(new Expression(a),o,b);
    }

    public Expression(Expression a, ArithOperator o, Rational b) throws ExpressionException, BadOperatorException
    {
        this();
        this.makeExpression(a,o,new Expression(b));
    }

    public Expression(Rational a, ArithOperator o, Rational b) throws ExpressionException, BadOperatorException
    {
        this();
        this.makeExpression(new Expression(a),o,new Expression(b));
    }

    public boolean atomP()
    {
        return(isAtomic);
    }
    
    public Rational getValue()
    {
        return(this.myValue);
    }

    public String toString()
    {
        String answer = this.toStringNoOnes();
        if (this.ones != 0) {
            answer += " [";
            for (int lcv=0;lcv<this.ones;lcv++) {
                if (lcv !=0) answer += ";";
                answer += "1";
            }
            answer += "]";
        }
        return(answer);
        
        //return(this.toStringDebug());
    }

    private String toStringNoOnes()
    {
        if (this.isAtomic) {
            return(this.myValue.toString());
        } else {
            String answer = "(";
            int lcv;
            for (lcv=0;lcv<this.positives;lcv++) {
                if (lcv != 0) answer += (this.isAdditive ? "+" : "x");
                answer += ((Expression)this.subExpressions.elementAt(lcv)).toStringNoOnes();
            }
            for (lcv=0;lcv<this.negatives();lcv++) {
                answer += (this.isAdditive ? "-" : "/");
                answer += ((Expression)this.subExpressions.elementAt(lcv+this.positives)).toStringNoOnes();
            }
            answer += ")";
            return(answer);
        }
    }

    public int compareTo(Object o) {
        Expression e = (Expression) o;
        int lcv = 0;
        if (lcv == 0) {
            if (lcv == 0)
                lcv = this.compareToNoOnes(e);
        }
        return (lcv);
    }

    public int compareToNoOnes(Object o) {
        Expression e = (Expression) o;
        int lcv = 0;
        if (lcv == 0) {
            // eliminiate the next line for a different metric
            lcv = this.myValue.compareTo(e.myValue);
            if (lcv == 0) {
                if (this.isAtomic && e.isAtomic) lcv = this.myValue.compareTo(e.myValue);
                else if (this.isAtomic && !e.isAtomic) lcv = -1;
                else if (!this.isAtomic && e.isAtomic) lcv = 1;
                else if (this.isAdditive && !e.isAdditive) lcv = -1;
                else if (!this.isAdditive && e.isAdditive) lcv = 1;
                else {
                    lcv = this.subExpressions.size() - e.subExpressions.size();
                    if (lcv == 0) {
                        lcv = e.positives - this.positives;
                        if (lcv == 0) {
                            lcv = this.subExpressions.compareTo(e.subExpressions);
                        }
                    }
                }
            }
        }
        return (lcv);
    }
        
    private void become(Expression e) {
        this.ones = e.ones;
        this.isAtomic = e.isAtomic;
        this.myValue = e.myValue;
        this.positives = e.positives;
        this.isAdditive = e.isAdditive;
        this.subExpressions = e.subExpressions;
    }
    

    private void makeExpression(Expression a, ArithOperator o, Expression b) 
        throws ExpressionException, BadOperatorException
    {
        // Set some fields
        this.ones = (byte)(a.ones + b.ones);
        this.isAtomic = false;
        this.subExpressions = new ComparableVector();
        this.isAdditive = (o.is(ArithOperator.PLUS) || o.is(ArithOperator.MINUS));
        
        // Ward off negative situations
        boolean doubleNeg = false;
        if (!this.isAdditive) {
            if (a.isNegative() && b.isNegative()) {
                a = a.additiveInverse();
                b = b.additiveInverse();
            }
        } else {
            if (b.isNegative()) {
                b = b.additiveInverse();
                if (o.is(ArithOperator.MINUS))
                    o = ArithOperator.ADD;
                else
                    o = ArithOperator.SUB;
            }
            if (a.isNegative()) {
                if (o.is(ArithOperator.PLUS)) {
                    Expression temp = b;
                    b = a.additiveInverse();
                    a = temp;
                } else {
                    // a = a.additiveInverse();
                    // doubleNeg = true;
                }
                o = ArithOperator.SUB;
            }
        }
        
        // make the Expression
        if (doubleNeg) {
            this.positives = 0;
            this.myValue = a.myValue.additiveInverse().op(o,b.myValue);
        } else if (o.is(ArithOperator.PLUS) || o.is(ArithOperator.TIMES)) {
            this.positives = 2;
            this.myValue = a.myValue.op(o,b.myValue);
        } else {
            this.positives = 1;
            this.myValue = a.myValue.op(o,b.myValue);
        }
        this.subExpressions.addElement(a);
        this.subExpressions.addElement(b);
        
        // do some simplification
        
        // check if we're of the form Rx1, 1xR, or R/1
        if (!this.isAdditive && b.isAtomicOne()) {
            this.become(a);
            this.ones = (byte)(a.ones + b.ones + 1);
        } else if (o.is(ArithOperator.TIMES) && a.isAtomicOne()) {
            this.become(b);
            this.ones = (byte)(a.ones + b.ones + 1);
        } else {
            // try to absorb
            int lcv;
            for (lcv=0;lcv<this.subExpressions.size();lcv++) {
                Expression se = (Expression) this.subExpressions.elementAt(lcv);
                if (!se.isAtomic) {
                    if (se.isAdditive == this.isAdditive) {
                        this.absorb(lcv);
                        lcv = -1;
                    } 
                } 
            }
            resort();
        }
    }
    
    private void resort() {
        int lcv;
        ComparableVector nn = new ComparableVector(this.negatives());
        while (this.negatives()>0) {
            nn.addElement(this.subExpressions.elementAt(this.positives));
            this.subExpressions.removeElementAt(this.positives);
        }
        this.subExpressions.sort();
        nn.sort();
        for (lcv=0;lcv<nn.size();lcv++)
            this.subExpressions.addElement(nn.elementAt(lcv));
    }
    
    public boolean isAtomicOne() {
        return(this.isAtomic && (this.myValue.equals(this.one)));
    }

    private void absorb(int term) {
        Expression se = (Expression) this.subExpressions.elementAt(term);
        Vector seSubs = (Vector) se.subExpressions.clone();
        int sePos = se.positives;
        boolean seIsPositive = term < this.positives;
        this.subExpressions.removeElementAt(term);
        if (seIsPositive)
            this.positives--;
        while (seSubs.size() > 0) {
            Expression subsub = (Expression) seSubs.elementAt(0);
            boolean isPositive = (0<sePos) ^ !seIsPositive;
            seSubs.removeElementAt(0);
            if (0<sePos)
                sePos--;
            if (isPositive) {
                this.subExpressions.insertElementAt(subsub, 0);
                this.positives ++;
            } else {
                this.subExpressions.addElement(subsub);
            }
        }
    }
    
    private boolean isNegative() {
        return(this.myValue.compareTo(this.zero) < 0);
    }
    
    private int negTerms() {
        int answer = 0;
        for (int lcv=0;lcv<this.subExpressions.size();lcv++) {
            Expression sub = (Expression)this.subExpressions.elementAt(lcv);
            if (sub.myValue.compareTo(this.zero) < 0) answer++;
        }
        return(answer);
    }
    
    private Expression additiveInverse() throws ExpressionException {
        Expression answer = null;
        if (this.isAtomic) {
            throw new ExpressionException();
        } else {
            answer = new Expression();
            answer.isAtomic = false;
            answer.myValue = this.myValue.additiveInverse();
            answer.isAdditive = this.isAdditive;
            answer.ones = this.ones;
            answer.subExpressions = new ComparableVector(this.subExpressions.size());
            int lcv;
            Expression sub;
            if (this.isAdditive) {
                if (this.positives == this.subExpressions.size()) throw new ExpressionException();
                answer.positives = this.negatives();
                for (lcv=0;lcv<this.negatives();lcv++) {
                    sub = (Expression)this.subExpressions.elementAt(this.positives+lcv);
                    if (sub.isNegative()) {
                        answer.positives--;
                        answer.subExpressions.addElement(sub.additiveInverse());
                    } else {
                        answer.subExpressions.insertElementAt(sub,lcv - this.negatives() + answer.positives);
                    }
                }
                for (lcv=0;lcv<this.positives;lcv++) {
                    sub = (Expression)this.subExpressions.elementAt(lcv);
                    answer.subExpressions.insertElementAt(sub,answer.positives);
                }
            } else {
                if ((this.negTerms() % 2) == 0) throw new ExpressionException();
                answer.positives = this.positives;
                for (lcv=0;lcv<this.subExpressions.size();lcv++) {
                    sub = (Expression)this.subExpressions.elementAt(lcv);
                    if (sub.isNegative()) sub = sub.additiveInverse();
                    answer.subExpressions.addElement(sub);
                }
            }
        }
        return(answer);
    }
}