package com.fngn.bt.nodes;

import java.util.*;

/**
 * Created by RyanZhu on 20/08/2017.
 */
public class GCD {
    private int gcd;
    private Stack<Wrapper> stack1 = new Stack<>();
    private Stack<Wrapper> stack2 = new Stack<>();
    private static class Wrapper {
        int val;
        int symbol;

        public Wrapper(int val) {
            this.val = Math.abs(val);
            this.symbol = val > 0 ? 1 : -1;
        }

        @Override
        public String toString() {
            return String.valueOf(val * symbol);
        }
    }

    private void gcd (int a, int b) {
        if (a % b == 0) {
            gcd = b;
        } else {
            gcd(b, a % b);
            int mod = a % b;
            int n = a / b;
            if (stack1.isEmpty() && stack2.isEmpty()) {
                stack1.push(new Wrapper(a));
                for (int i = 0; i < n; i++) {
                    stack1.push(new Wrapper(-b));
                }
                printStack();
            } else if (stack2.isEmpty()) {
                processStack(a, b, mod, n, stack1, stack2);
            } else {
                processStack(a, b, mod, n, stack2, stack1);
            }
        }
    }

    private void processStack(int a, int b, int mod, int n, Stack<Wrapper> st1, Stack<Wrapper> st2) {
        while (!st1.isEmpty()) {
            Wrapper top = st1.pop();
            if (top.val == mod) {
                st2.push(new Wrapper(a * top.symbol));
                for (int i = 0; i < n; i++) {
                    st2.push(new Wrapper(-b * top.symbol));
                }
            } else {
                st2.push(top);
            }
        }
        printStack();
    }

    private void end() {
        Stack<Wrapper> results = stack1.isEmpty() ? stack2 : stack1;
        Map<Integer, Integer> map = new HashMap<>();
        while(!results.isEmpty()) {
            Wrapper top = results.pop();
            if (!map.containsKey(top.val)) {
                map.put(top.val, 0);
            }
            map.put(top.val, map.get(top.val) + top.symbol);
        }
        List<Integer> keys = new ArrayList<>(map.keySet());
        System.out.println(String.format("gcd: %d, %d * %d + %d * %d",
                gcd, keys.get(0), map.get(keys.get(0)), keys.get(1), map.get(keys.get(1))));
    }

    public void execute(int a, int b) {
        gcd(a, b);
        end();
    }

    public static void main(String[] args) {
        GCD gcd = new GCD();
        gcd.execute(13,25);
    }

    void printStack() {
        System.out.println("print stack1");
        stack1.forEach(wrapper -> System.out.println(wrapper.toString()));
        System.out.println("print stack2");
        stack2.forEach(wrapper -> System.out.println(wrapper.toString()));
    }
}