/**
 * class StackCalc
 * Stack Calculator of Big Integers, JDK 1.1 version
 *
 * <applet code="StackCalc.class" width=515 height=400>
 * </applet>
 *
 * I hoped that it would work under Netscape 4.04, but, even if
 * we replace all JDK 1.1 features by deprecated JDK 1.0
 * methods, Netscape couldn't load the class BigInteger. (The
 * file "StCalc.java" contains JDK 1.0 version of this applet.
 * It cannot be performed by Netscape, because it cannot load
 * the class BigInteger.)  :-((
 *
 * The applet works only under HotJava 1.1.2 browser (I tested
 * it with generic HotJava browser under RedHat Linux 4.02.).
 * As I know, HotJava is the only Internet browser that fully
 * supports the Java Developer Kit version 1.1. Hope that
 * future versions of Netscape (if any...) will also support
 * JDK 1.1
 *
 * Applet works well under SUN's appletviewer or as a standalone
 * Java application, in SUN's JDK 1.1.3 or higher environment.
 * The command to run it is
 *     java StackCalc
 * I tested it in RedHat Linux 4.2 (JDK 1.1.3 and 1.1.5) and
 * under Win95, JDK 1.1.5.
 *
 * The implementation of modPow method of class BigInteger
 * contains error -- try, for instance, 2^256 (mod 16). So I use my
 * own implementation of this method: modPower(base, exp, mod).
 *
 * 22-Mar-98 V.Borisenko vvb@mech.math.msu.su
 */

import java.math.BigInteger;
import java.awt.*;
import java.awt.event.*;
import java.applet.Applet;

public class StackCalc extends Applet implements Runnable {
    IntStack stack;
    BigInteger number;
    BigInteger module;

    Button plusButton;
    Button minusButton;
    Button multButton;
    Button divButton;
    Button remButton;
    Button powerButton;
    Button gcdButton;
    Button lcmButton;
    Button pushButton;
    Button popButton;
    Button initButton;

    TextField inputNumber;
    TextField resultNumber;
    Label message;

    Checkbox  moduleCalculations;
    TextField moduleNumber;
    Button stackTopToModule;

    // Layout constants
    static final int leftMargin   = 5;
    static final int topMargin    = 5;
    static final int headSkip     = 30;
    static final int vertSkip     = 5;
    static final int horSkip      = 5;
    static final int buttonWidth  = 50;
    static final int buttonHeight = 30;
    static final int stackDy      = 24;
    static final int numberWidth  = 400;

    public static void main(String[] args) {
        Frame f = new Frame("Stack Calculator of Big Integers");

        WindowAdapter wa = new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        };
        f.addWindowListener(wa);

        f.setFont(new Font("Helvetica", Font.PLAIN, 14));

        // Add menu bar
        final MenuBar mb = new MenuBar();
        f.setMenuBar(mb);
        final Menu fileMenu = new Menu("File");
        final MenuItem quitItem = new MenuItem("Quit");
        fileMenu.add(quitItem);
        mb.add(fileMenu);

        ActionListener al = new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                // System.out.println("Action " + e);
                if (e.getActionCommand().equals("Quit")) {
                    System.exit(0);
                }
            }
        };
        fileMenu.addActionListener(al);

        StackCalc sc = new StackCalc();
        f.add("Center", sc);

        sc.init();
        sc.start();

        // f.pack();
        f.setSize(
            2*leftMargin + 2*buttonWidth + horSkip + numberWidth + 10,
            400
        );
        f.setVisible(true);
    }

    public StackCalc() {
        stack = new IntStack();
    }

    public void init() {
        setLayout(null);

        setFont(new Font("Helvetica", Font.PLAIN, 14));
        setBackground(Color.lightGray);

        Label headline = new Label("Stack Calculator of Big Integers");
        headline.setFont(new Font("TimesRoman", Font.BOLD, 18));
        add(headline);
        headline.setBounds(leftMargin, topMargin, 300, 30);

        Panel stackControls = new Panel();

        plusButton = new Button("+");
        minusButton = new Button("-");
        multButton = new Button("*");
        divButton = new Button("/");
        remButton = new Button("rem");
        powerButton = new Button("pow");
        gcdButton = new Button("gcd");
        lcmButton = new Button("lcm");

        stackControls.setFont(new Font("Helvetica", Font.PLAIN, 14));
        stackControls.setForeground(Color.blue);
        stackControls.setLayout(new GridLayout(2, 4));

        stackControls.add(plusButton);
        stackControls.add(minusButton);
        stackControls.add(multButton);
        stackControls.add(divButton);
        stackControls.add(remButton);
        stackControls.add(powerButton);
        stackControls.add(gcdButton);
        stackControls.add(lcmButton);

        stackControls.setBounds(
            leftMargin, topMargin + headSkip,
            4 * buttonWidth, 2 * buttonHeight
        );
        add(stackControls);

        message = new Label("");
        add(message);
        /*...
        message.setBounds(
            leftMargin, topMargin + headSkip + 3 * buttonHeight,
            4 * buttonWidth, buttonHeight
        );
        ...*/

        popButton = new Button("Delete stack top");
        initButton = new Button("Erase");
        add(popButton);
        add(initButton);
        popButton.setBounds(
            leftMargin, 
            topMargin + headSkip + 2*buttonHeight,
            3*buttonWidth, buttonHeight
        );
        initButton.setBounds(
            leftMargin + 3*buttonWidth,
            topMargin + headSkip + 2*buttonHeight,
            buttonWidth, buttonHeight
        );

        CheckboxListener cl = new CheckboxListener();
        moduleCalculations = new Checkbox("Module calculations", false);
        moduleCalculations.addItemListener(cl);

        TextFieldListener tl = new TextFieldListener();
        moduleNumber = new TextField();
        moduleNumber.addTextListener(tl);
        moduleNumber.setEditable(false);
        stackTopToModule = new Button("Copy Stack top to module");

        add(moduleCalculations);
        Label m = new Label("Mod:");
        add(m);
        add(moduleNumber);
        add(stackTopToModule);

        final int moduleLeft = leftMargin + 4*buttonWidth + horSkip;
        moduleCalculations.setBounds(
            moduleLeft + 50,
            topMargin + headSkip,
            160, buttonHeight
        );
        m.setBounds(
            moduleLeft + horSkip + 5,
            topMargin + headSkip + buttonHeight,
            40, buttonHeight
        );
        final int moduleWidth = numberWidth - 2*buttonWidth;
        moduleNumber.setBounds(
            moduleLeft + 50,
            topMargin + headSkip + buttonHeight,
            moduleWidth - 50,
            buttonHeight
        );
        stackTopToModule.setBounds(
            leftMargin + 4*buttonWidth + horSkip,
            topMargin + headSkip + 2*buttonHeight + 2,
            moduleWidth,
            buttonHeight - 2
        );

        pushButton = new Button("Push");
        Label result = new Label("Result:");
        add(pushButton);
        add(result);
        pushButton.setBounds(
            leftMargin,
            topMargin + headSkip + 3*buttonHeight + vertSkip,
            2*buttonWidth, buttonHeight
        );
        result.setBounds(
            leftMargin + 10,
            topMargin + headSkip + 4*buttonHeight + 2*vertSkip,
            2*buttonWidth - 10, buttonHeight
        );
        result.setForeground(Color.blue);

        inputNumber = new TextField();
        inputNumber.addTextListener(tl);
        resultNumber = new TextField();
        resultNumber.setEditable(false);
        resultNumber.setForeground(Color.blue);
        add(inputNumber);
        add(resultNumber);
        inputNumber.setBounds(
            leftMargin + 2*buttonWidth + horSkip,
            topMargin + headSkip + 3*buttonHeight + vertSkip,
            numberWidth, buttonHeight
        );
        resultNumber.setBounds(
            leftMargin + 2*buttonWidth + horSkip,
            topMargin + headSkip + 4*buttonHeight + 2*vertSkip,
            numberWidth, buttonHeight
        );

        // Add action listener for "Input" text field
        // (only for processing the "Enter" button)
        inputNumber.addActionListener(
            new ActionListener() {
                public void actionPerformed(ActionEvent e) {
                    // System.out.println("Text action " + e);
                    if (number != null) onPush();
                }
            }
        );

        // Add action listener for buttons
        ButtonListener bl = new ButtonListener();

        plusButton.addActionListener(bl);
        minusButton.addActionListener(bl);
        multButton.addActionListener(bl);
        divButton.addActionListener(bl);
        remButton.addActionListener(bl);
        powerButton.addActionListener(bl);
        gcdButton.addActionListener(bl);
        lcmButton.addActionListener(bl);
        pushButton.addActionListener(bl);
        popButton.addActionListener(bl);
        initButton.addActionListener(bl);
        stackTopToModule.addActionListener(bl);
    }

    public void paint(Graphics g) {
        Rectangle r = resultNumber.getBounds();
        int stackTop = r.y + r.height + vertSkip;
        int stackLeft = r.x;
        int stackWidth = 0;
        int stackHeight = vertSkip;
        g.setColor(Color.red);
        g.drawString("Stack:", leftMargin, stackTop + 18);
        g.drawString(
            "Depth = " + stack.depth(),
            leftMargin, stackTop + stackDy + 18
        );

        FontMetrics fm = g.getFontMetrics();

        for (int i = 0; i < stack.depth(); i++) {
            String s = stack.elementAt(i).toString();
            g.drawString(
                s, stackLeft + horSkip, stackTop + stackDy*i + 20
            );
            int w = fm.stringWidth(s);
            if (w > stackWidth) stackWidth = w;
        }

        stackWidth += 2*horSkip;

        if (stack.depth() > 0) {
            stackHeight = stack.depth()*stackDy;
        } else {
            stackTop += vertSkip;
        }

        if (stackWidth < 40) stackWidth = 40;

        g.drawLine(
            stackLeft, stackTop,
            stackLeft, stackTop + stackHeight
        );
        g.drawLine(
            stackLeft, stackTop + stackHeight,
            stackLeft + stackWidth, stackTop + stackHeight
        );
        g.drawLine(
            stackLeft + stackWidth, stackTop + stackHeight,
            stackLeft + stackWidth, stackTop
        );
    }

    public void start() {

    }

    public void run() {

    }

    // Action listeners
    class ButtonListener implements ActionListener {
        public void actionPerformed(ActionEvent e) {
            Object source = e.getSource();
            if (source == plusButton) {
                onPlus();
            } else if (source == minusButton) {
                onMinus();
            } else if (source == multButton) {
                onMult();
            } else if (source == divButton) {
                onDiv();
            } else if (source == remButton) {
                onRem();
            } else if (source == powerButton) {
                onPower();
            } else if (source == gcdButton) {
                onGcd();
            } else if (source == lcmButton) {
                onLcm();
            } else if (source == pushButton) {
                onPush();
            } else if (source == popButton) {
                onPop();
            } else if (source == initButton) {
                onErase();
            } else if (source == stackTopToModule) {
                onStackTopToModule();
            }
        }
    }

    void onPlus() {
        if (stack.depth() < 2) {
            showMessage("Cannot perform operation: Stack depth < 2");
            return;
        }
        try {
            BigInteger x2 = stack.pop();
            BigInteger x1 = stack.pop();
            BigInteger res = x1.add(x2);

            if (moduleCalculations.getState() &&
                module != null &&
                !module.equals(BigInteger.valueOf(0))) {
                res = res.mod(module);
            }

            stack.push(res);
            showResult();
        } catch (StackException e) {
            System.out.println(e.toString());
        }
    }

    void onMinus() {
        if (stack.depth() < 2) {
            showMessage("Cannot perform operation: Stack depth < 2");
            return;
        }
        try {
            BigInteger x2 = stack.pop();
            BigInteger x1 = stack.pop();
            BigInteger res = x1.subtract(x2);

            if (moduleCalculations.getState() &&
                module != null &&
                !module.equals(BigInteger.valueOf(0))) {
                res = res.mod(module);
            }

            stack.push(res);
            showResult();
        } catch (StackException e) {
            System.out.println(e.toString());
        }
    }

    void onMult() {
        if (stack.depth() < 2) {
            showMessage("Cannot perform operation: Stack depth < 2");
            return;
        }
        try {
            BigInteger x2 = stack.pop();
            BigInteger x1 = stack.pop();
            BigInteger res = x1.multiply(x2);

            if (moduleCalculations.getState() &&
                module != null &&
                !module.equals(BigInteger.valueOf(0))) {
                res = res.mod(module);
            }

            stack.push(res);
            showResult();
        } catch (StackException e) {
            System.out.println(e.toString());
        }
    }

    void onDiv() {
        if (stack.depth() < 2) {
            showMessage("Cannot perform operation: Stack depth < 2");
            return;
        }
        try {
            BigInteger res;
            BigInteger x2 = stack.top();
            if (x2.equals(BigInteger.valueOf(0))) {
                System.out.println("Zero divizion");
                showMessage("Zero division");
                return;
            }

            if (moduleCalculations.getState() &&
                module != null &&
                !module.equals(BigInteger.valueOf(0))) {
                try {
                    x2 = x2.modInverse(module);
                } catch (ArithmeticException e) {
                    showMessage(
                        "Number in stack top has no inverse mod m"
                    );
                    return;
                }
                stack.pop();
                BigInteger x1 = stack.pop();
                res = x1.multiply(x2);
                res = res.mod(module);
            } else {
                stack.pop();
                BigInteger x1 = stack.pop();
                res = x1.divide(x2);
            }
            stack.push(res);
            showResult();
        } catch (StackException e) {
            System.out.println(e.toString());
        }
    }

    void onRem() {
        if (stack.depth() < 2) {
            showMessage("Cannot perform operation: Stack depth < 2");
            return;
        }
        try {
            BigInteger x2 = stack.top();
            if (x2.equals(BigInteger.valueOf(0))) {
                System.out.println("Zero divizion");
                showMessage("Zero division");
                return;
            }
            stack.pop();
            BigInteger x1 = stack.pop();
            BigInteger res = x1.remainder(x2);
            stack.push(res);
            showResult();
        } catch (StackException e) {
            System.out.println(e.toString());
        }

    }

    void onPower() {
        if (stack.depth() < 2) {
            showMessage("Cannot perform operation: Stack depth < 2");
            return;
        }

        try {
            if (moduleCalculations.getState() &&
                module != null &&
                !module.equals(BigInteger.valueOf(0))) {

                BigInteger x2 = stack.pop();
                BigInteger x1 = stack.top();
                if (x2.signum() < 0) {
                    try {
                        x1 = x1.modInverse(module);
                    } catch (ArithmeticException e) {
                        showMessage(
                            "Number in stack top has no inverse mod m"
                        );
                        return;
                    }
                    x2 = x2.negate();
                }
                stack.pop();
                //!!! There is an error in modPow in Sun package!!!
                //!!! So we have to use our own method instead...
                //!!! BigInteger res = x1.modPow(x2, module);
                try {
                    BigInteger res = modPower(x1, x2, module);
                    stack.push(res);
                    showResult();
                } catch (ArithmeticException e) {
                    System.out.println(e.toString());
                    showMessage("No multiplicative inverse module m");
                }
            } else {
                BigInteger x2 = stack.top();
                if (x2.signum() < 0) {
                    showMessage("Exponent cannot be < 0, if mod is not used");
                    return;
                }
                stack.pop();
                BigInteger x1 = stack.pop();
                BigInteger res;
                try {
                    res = x1.pow(x2.intValue());
                } catch (Exception e) {
                    showMessage("Too much...");
                    return;
                }
                stack.push(res);
                showResult();
            }
        } catch (StackException e) {
            System.out.println(e.toString());
        }
    }

    void onGcd() {
        if (stack.depth() < 2) {
            showMessage("Cannot perform operation: Stack depth < 2");
            return;
        }
        try {
            BigInteger x2 = stack.pop();
            BigInteger x1 = stack.pop();
            BigInteger res = x1.gcd(x2);
            stack.push(res);
            showResult();
        } catch (StackException e) {
            System.out.println(e.toString());
        }
    }

    void onLcm() {
        if (stack.depth() < 2) {
            showMessage("Cannot perform operation: Stack depth < 2");
            return;
        }
        try {
            BigInteger x2 = stack.pop();
            BigInteger x1 = stack.pop();
            BigInteger res = x1.gcd(x2);
            if (!res.equals(BigInteger.valueOf(0))) {
                res = x1.multiply(x2).divide(res);
            }
            stack.push(res);
            showResult();
        } catch (StackException e) {
            System.out.println(e.toString());
        }
    }

    void onPush() {
        if (number != null) {
            try {
                //... if (moduleCalculations.getState() &&
                //...     module != null &&
                //...     !module.equals(BigInteger.valueOf(0))) {
                //...     number = number.mod(module);
                //... }
                stack.push(number);
                inputNumber.setText("");
                number = null;
                showResult();
            } catch (StackException e) {
                System.out.println(e.toString());
            }
        }
    }

    void onPop() {
        if (stack.depth() > 0) {
            try {
                stack.pop();
                showResult();
            } catch (StackException e) {
                System.out.println(e.toString());
            }
        }
    }

    void onErase() {
        stack.init();
        number = null;
        module = null;

        inputNumber.setText("");
        resultNumber.setText("");

        moduleCalculations.setState(false);
        moduleNumber.setText("");
        moduleNumber.setEditable(false);

        repaint();
    }

    void onStackTopToModule() {
        if (stack.depth() <= 0) return;
        try {
            String text = stack.top().toString();
            moduleNumber.setText(text);
            module = stack.top();
        } catch (StackException e) {
            System.out.println(e.toString());
        }
    }

    class TextFieldListener implements TextListener {
        public void textValueChanged(TextEvent e) {
            // System.out.println("TextEvent=" + e);
            Object source = e.getSource();
            if (source == inputNumber) {
                input();
            } else if (source == moduleNumber) {
                inputModule();
            }
        }
    }

    void input() {
        String text = inputNumber.getText();
        if (text.equals("")) {
            number = null;
            return;
        }

        try {
            number = new BigInteger(text);
        } catch (NumberFormatException e) {
            // System.out.println("Input number: Illegal format: " + e.toString());
            number = null;
        }
    }

    void inputModule() {
        // System.out.println("Module changed");
        String text = moduleNumber.getText();
        if (text.equals("")) {
            module = null;
            return;
        }

        try {
            module = new BigInteger(text);
            if (module.signum() < 0) {
                module = module.negate();
                moduleNumber.setText(module.toString());
            }
        } catch (NumberFormatException e) {
            // System.out.println("Module: Illegal format: " + e.toString());
            module = null;
        }
    }

    class CheckboxListener implements ItemListener {
        public void itemStateChanged(ItemEvent e) {
            Object source = e.getSource();
            if (source == moduleCalculations) {
                onModuleCalculations();
            }
        }
    }

    void onModuleCalculations() {
        if (moduleCalculations.getState()) {
            moduleNumber.setEditable(true);
        } else {
            moduleNumber.setEditable(false);
        }
    }

    void showResult() {
        if (stack.depth() > 0) {
            try {
                resultNumber.setText(stack.top().toString());
            } catch (StackException e) {
                System.out.println(e.toString());
            }
        } else {
            resultNumber.setText("");
        }
        repaint();
    }

    void showMessage(String m) {
        resultNumber.setText(m);
        repaint();
    }

    //!!! There is an error in modPow in Sun package!!!
    //!!! So we have to use our own method instead...
    public static BigInteger modPower(
        BigInteger base, BigInteger exponent, BigInteger modul)
        throws ArithmeticException {

        // System.out.println(
        //     "modPower: base=" + base +
        //     ", exp=" + exponent +
        //     ", mod=" + modul
        // );

        BigInteger power = BigInteger.valueOf(1);
        BigInteger zero = BigInteger.valueOf(0);
        BigInteger unit = BigInteger.valueOf(1);

        if (modul.equals(zero)) {
            throw new ArithmeticException("Zero module");
        } else if (modul.signum() < 0) {
            modul = modul.negate();
        }

        // Handle negative base
        boolean negativeBase = false;
        if (base.signum() < 0) {
            base = base.negate();
            if (!exponent.and(unit).equals(zero)) {
                // Odd exponent
                negativeBase = true;
            }
        }

        // Handle negative exponent
        if (exponent.signum() < 0) {
            // Compute multiplicative inverse of base (module mod)
            // and change the sign of exponent
            // System.out.println("base=" + base +", mod=" + modul);
            if (!base.gcd(modul).equals(unit)) {
                // No inverse...
                throw new ArithmeticException(
                    "The base of negative exponent cannot be inverted module m"
                );
            }
            // System.out.println("gcd=1, computing modInverse");
            base = base.modInverse(modul);
            // System.out.println("modInverse=" + base);
            exponent = exponent.negate();
        }

        // Assertion: base >= 0 && exponent >= 0

        while (!exponent.equals(zero)) {
            // Invariant: base^exponent * power = const
            if (exponent.and(unit).equals(zero)) {
                // Even exponent
                exponent = exponent.shiftRight(1);
                base = base.multiply(base).mod(modul);
            } else {
                exponent = exponent.subtract(unit);
                power = power.multiply(base).mod(modul);
            }
            // System.out.println(
            //     "  base=" + base.toString() +
            //     ", exp=" + exponent.toString() +
            //     ", pow=" + power.toString()
            // );
        }

        if (negativeBase)
            return power.negate();
        else
            return power;
    }
}

class IntStack {
    final int MAX_DEPTH = 1024;
    BigInteger stack[] = new BigInteger[MAX_DEPTH];
    int depth = 0;

    public IntStack() {
        init();
    }

    public void init() {
        depth = 0;
        for (int i = 0; i < MAX_DEPTH; i++) {
            stack[i] = null;
        }
    }

    int depth() { return depth; }

    BigInteger pop() throws StackException {
        if (depth <= 0) {
            throw new StackException("Stack is empty");
        } else {
            BigInteger ret = stack[depth - 1];
            stack[depth - 1] = null;
            depth--;
            return ret;
        }
    }

    BigInteger top() throws StackException {
        if (depth <= 0) {
            throw new StackException("Stack is empty");
        } else {
            return stack[depth - 1];
        }
    }

    void push(BigInteger x) throws StackException {
        if (depth >= MAX_DEPTH) {
            throw new StackException("Stack overflow");
        } else {
            stack[depth] = x;
            depth++;
        }
    }

    // Return the element at the depth i (zero is a top of stack)
    BigInteger elementAt(int i) {
        if (i >= depth) return null;
        else return stack[depth - 1 - i];
    }
}

class StackException extends Exception {
    String reason = "Stack is empty";
    public StackException() {}
    public StackException(String cause) {
        reason = cause;
    }
    public String toString() {
        return ("StackException: " + reason);
    }
}