package algorithm.math;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Str_Math {
  
    private List<Byte> add_byte_list(List<byte[]> byte_arr_List) {
      
        boolean it_over = false;
        List<Byte> add_result_list = new ArrayList<Byte>();
      
        int carry = 0;
        int add_index = 1;
        while (!it_over) {
            int add_r = 0;
            it_over = true;
            for (int i = 0; i < byte_arr_List.size(); i++) {
                byte[] arr = byte_arr_List.get(i);
                if (arr.length < add_index) continue;
                else {
                    it_over = false;
                    add_r += arr[arr.length - add_index];
                }
            }
            add_r += carry;
            add_result_list.add(0, (byte)(add_r % 10));
            carry = add_r / 10;
            add_index++;
        }
        while (carry > 0) {
            byte m = (byte)(carry % 10);
            add_result_list.add(0, m);
            carry /= 10;
        }
        return add_result_list;
    }
  
    private List<Byte> multi_byteArr(byte[] arr1, byte[] arr2) {
        List<byte[]> byte_arr_list = new ArrayList<byte[]>();
        for (int i = arr1.length - 1; i >= 0; i-- ) {
            byte[] product = new byte[arr2.length + arr1.length - i];
            for (int p = 0; p < product.length; p++) product[p] = 0;
            byte a = arr1[i];
            byte carry = 0;
            for (int j = arr2.length - 1; j >= 0; j--) {
                byte b = arr2[j];
                int p = a * b;
                p += carry;
                carry = (byte)(p / 10);
                product[j + 1] = (byte)(p % 10);
            }
            product[0] = carry;
            byte_arr_list.add(product);
        }
      
        return add_byte_list(byte_arr_list);
    }
  
    private byte[] str_to_byte_arr(String s) {
        int len = s.length();
        byte[] b_arr = new byte[len];
        for (int i = 0; i < len; i++) b_arr[i] = (byte)(s.charAt(i) - 0x30);
        return b_arr;
    }
  
    private String bytearr_to_str(byte[] byte_arr) {
        String r = "";
        boolean begin_0 = true;
        for (int i = 0; i < byte_arr.length; i++) {
            byte b = byte_arr[i];
            if (b == 0 && begin_0) continue;
            else {
                r += (char)(byte_arr[i] + 0x30);
                begin_0 = false;
            }
        }
        return r;
    }
  
    private String bytelist_to_str(List<Byte> byte_list) {
        String r = "";
        boolean begin_0 = true;
        for (int i = 0; i < byte_list.size(); i++) {
            byte b = byte_list.get(i);
            if (b == 0 && begin_0) continue;
            else {
                r += (char)(byte_list.get(i) + 0x30);
                begin_0 = false;
            }
        }
        return r;
    }
  
    public String multi_str(String mult1, String mult2) {
        if ("0".equals(mult1) || "0".equals(mult2)) return "0";
      
        byte mult_arr1[] = str_to_byte_arr(mult1);
        byte mult_arr2[] = str_to_byte_arr(mult2);
      
        List<Byte> mult_result = null;
        if (mult_arr1.length <= mult_arr2.length) mult_result = multi_byteArr(mult_arr1, mult_arr2);
        else mult_result = multi_byteArr(mult_arr2, mult_arr1);
      
        return bytelist_to_str(mult_result);
    }
  
    private boolean is_all_zero(byte[] b_arr) {
        boolean all_zero = true;
        for (byte b : b_arr)
            if (b != 0) {
                all_zero = false;
                break;
            }
        return all_zero;
    }
  
    private void minus_one(byte[] b_arr) {
      
        for (int i = b_arr.length - 1; i >= 0; i--) {
            if (b_arr[i] == 0) b_arr[i] = 9;
            else {
                b_arr[i] -= 1;
                break;
            }
        }
    }
   
    public String add_str(String add1, String add2) {
        byte[] add1_byte_arr = str_to_byte_arr(add1);
        byte[] add2_byte_arr = str_to_byte_arr(add2);
        List<byte[]> byte_arr_list = new ArrayList<byte[]>();
        byte_arr_list.add(add1_byte_arr);
        byte_arr_list.add(add2_byte_arr);
       
        List<Byte> combine = add_byte_list(byte_arr_list);
        return bytelist_to_str(combine);
    }
  
    public String pow_str(String bottom, String expr) {
        byte[] expr_byte_arr = str_to_byte_arr(expr);
        String b1 = "1";
        while (!is_all_zero(expr_byte_arr)) {
            b1 = multi_str(bottom, b1);
            minus_one(expr_byte_arr);
        }
        return b1;
    }
  
    public boolean is_big(String s1, String s2) {
        if (s1.length() > s2.length()) return true;
        else if (s1.length() < s2.length()) return false;
        else {
            for (int i = 0; i < s1.length(); i++) {
                char c1 = s1.charAt(i);
                char c2 = s2.charAt(i);
                if (c1 > c2) return true;
                else if (c1 < c2) return false;
            }
        }
        return false;
    }
  
    public String minus(String s1, String s2) {
        if (s1.equals(s2)) return "0";
      
        byte[] b_arr_1 = str_to_byte_arr(s1);
        byte[] b_arr_2 = str_to_byte_arr(s2);
      
        boolean is_carry = false, nine_carry = false;
        int leave_index = -1;
      
        for (int b1_index = b_arr_1.length - 1; b1_index >= 0; b1_index--) {
            int b2_index = b_arr_2.length - (b_arr_1.length - b1_index);
            if (b2_index < 0) {
                leave_index = b1_index;
                break;
            }
            if (is_carry) {
                if (b_arr_1[b1_index] == 0) {
                    b_arr_1[b1_index] = 9;
                    nine_carry = true;
                    is_carry = true;
                } else {
                    b_arr_1[b1_index] -= 1;
                    is_carry = false;
                }
            }
            byte b1 = b_arr_1[b1_index];
                byte b2 = b_arr_2[b2_index];
                if (b1 < b2) {
                    b_arr_1[b1_index] = (byte)(b1 + 10 - b2);
                    is_carry = true;
                } else {
                    b_arr_1[b1_index] = (byte)(b1 - b2);
                    is_carry = false;
                    if (nine_carry) {
                        is_carry = true;
                        nine_carry = false;
                    }
                }
        }
        if (is_carry && leave_index >= 0) {
            for (int i = leave_index; i >= 0; i--) {
                if (b_arr_1[i] == 0) b_arr_1[i] = 9;
                else {
                    b_arr_1[i] -= 1;
                    break;
                }
            }
        }
        return bytearr_to_str(b_arr_1);
    }
  
    public String remainder(String s1, String s2) {
        if (s1.equals(s2)) return "0";
      
        while (is_big(s1, s2)) s1 = minus(s1, s2);
        if (s1.equals(s2)) return "0";
        return s1;
    }
  
    //String[0] division /String[1] remainder
    public String[] division(String s1, String s2) {
        String[] div_remain = new String[2];
      
        String multi_s2 = "0";
        String remainder = s1, add_result = "0";
        while (is_big(remainder, s2)) {
            int remain_len = remainder.length();
            int s2_len = s2.length();
            if (remain_len - s2_len > 1) {
                int expr = remain_len - s2_len - 1;
                String multi_ten = pow_str("10", String.valueOf(expr));
                String s2_multi = multi_str(s2, multi_ten);
                multi_s2 = add_str(multi_s2, multi_ten);
                add_result = add_str(add_result, s2_multi);
                remainder = minus(s1, add_result);
            } else {
                multi_s2 = add_str(multi_s2, "1");
                add_result = add_str(add_result, s2);
                remainder = minus(s1, add_result);
            }
        }
        if (remainder.equals(s2)) {
            multi_s2 = add_str(multi_s2, "1");
            remainder = "0";
        }
        div_remain[0] = multi_s2;
        div_remain[1] = remainder;
        return div_remain;
    }
  
    private void test_division() {
        Str_Math en = new Str_Math();
        Random rand = new Random();
        boolean has_err = false;
        for (int i = 0; i < 1000; i++) {
            int m1 = rand.nextInt(1000000000);
            int m2 = rand.nextInt(1000) + 1;
            int m, remain;
          
            String s1 = String.valueOf(m1);
            String s2 = String.valueOf(m2);
            if (m1 > m2) {
                m = m1 / m2;
                remain = m1 % m2;
            }
            else {
                s1 = String.valueOf(m2);
                s2 = String.valueOf(m1);
                m = m2 / m1;
                remain = m2 % m1;
            }
            System.out.print(s1 + "/" + s2 + "=");
            String[] div = en.division(s1, s2);
            String m_r = String.valueOf(m);
            if (div[0].equals(m_r) || div[1].equals(remain)) System.out.println(div[0] + " " + div[1]);
            else {
                System.out.println(div[0] + " " + div[1] + "___" + m_r + " " + remain);
                has_err = true;
            }
        }
        System.out.println("========= result ========");
        if (has_err) System.out.println("has_err");
//        System.out.println(28080874 % 5413);
        String[] div = en.division("8630136386301363863013638630136386301363863013638630136386301363863013638630136386301363863013638630136386301363863013638630136386301363863013638630136386301363863013638630136386301363863013638630136386301363", "27");  //295 543___38752 659
        System.out.println(div[0] + " " + div[1]); //28080874T13=0___3643
    }
  
    private void test_remainder() {
        Str_Math en = new Str_Math();
        Random rand = new Random();
        boolean has_err = false;
        for (int i = 0; i < 1000; i++) {
            int m1 = rand.nextInt(100000000);
            int m2 = rand.nextInt(10000);
            int m;
            String s1 = String.valueOf(m1);
            String s2 = String.valueOf(m2);
            if (m1 > m2) {
                m = m1 % m2;
            }
            else {
                s1 = String.valueOf(m2);
                s2 = String.valueOf(m1);
                m = m2 % m1;
            }
          
            String r = en.remainder(s1, s2);
            String m_r = String.valueOf(m);
            if (r.equals(m_r)) System.out.println(s1 + "%" + s2 + "=" + r);
            else {
                System.out.println(s1 + "%" + s2 + "=" + r + "___" + m_r);
                has_err = true;
            }
        }
        System.out.println("========= result ========");
        if (has_err) System.out.println("has_err");
//        System.out.println(28080874 % 5413);
//        System.out.println(en.remainder("28080874", "5413")); //28080874T13=0___3643
    }
  
    private void test_minus() {
        Str_Math en = new Str_Math();
//        Random rand = new Random();
//        boolean has_err = false;
//        for (int i = 0; i < 1000; i++) {
//            int m1 = rand.nextInt(100000000);
//            int m2 = rand.nextInt(100000000);
//            int m;
//            String s1 = String.valueOf(m1);
//            String s2 = String.valueOf(m2);
//            if (m1 > m2) {
//                m = m1 - m2;
//            }
//            else {
//                s1 = String.valueOf(m2);
//                s2 = String.valueOf(m1);
//                m = m2 - m1;
//            }
//          
//            String r = en.minus(s1, s2);
//            String m_r = String.valueOf(m);
//            if (r.equals(m_r)) System.out.println(s1 + "-" + s2 + "=" + r);
//            else {
//                System.out.println(s1 + "-" + s2 + "=" + r + "___" + m_r);
//                has_err = true;
//            }
//        }
        System.out.println("========= result ========");
//        if (has_err) System.out.println("has_err");
        System.out.println(en.minus("23225413", "5413"));
    }
  
    private void test_multi() {
        Str_Math en = new Str_Math();
        Random rand = new Random();
        boolean has_err = false;
        for (int i = 0; i < 1000; i++) {
            int m1 = rand.nextInt(10000);
            int m2 = rand.nextInt(10000);
            String s1 = String.valueOf(m1);
            String s2 = String.valueOf(m2);
            String r = en.multi_str(s1, s2);
            int m = m1 * m2;
            String m_r = String.valueOf(m);
            if (r.equals(m_r)) System.out.println(s1 + "*" + s2 + "=" + r);
            else {
                System.out.println(s1 + "*" + s2 + "=" + r + "___" + m_r);
                has_err = true;
            }
        }
        System.out.println("========= result ========");
        if (has_err) System.out.println("has_err");
    }
  
    private void test_minus_one() {
        Str_Math en = new Str_Math();
        byte[] b_arr = new byte[2];
        b_arr[0] = 1;
        b_arr[1] = 0;
        en.minus_one(b_arr);
        System.out.println(b_arr[0] + "" + b_arr[1]);
    }
  
    private void test_pow() {
        Str_Math en = new Str_Math();
        Random rand = new Random();
        boolean has_err = false;
        for (int i = 0; i < 1000; i++) {
            int m1 = rand.nextInt(10);
            int m2 = rand.nextInt(10);
            String s1 = String.valueOf(m1);
            String s2 = String.valueOf(m2);
            String r = en.pow_str(s1, s2);
            int m = (int)Math.pow(m1, m2);
            String m_r = String.valueOf(m);
            if (r.equals(m_r)) System.out.println(s1 + "^" + s2 + "=" + r);
            else {
                System.out.println(s1 + "^" + s2 + "=" + r + "___" + m_r);
                has_err = true;
            }
        }
        System.out.println("========= result ========");
        if (has_err) System.out.println("has_err");
    }
  
    public static void main(String args[]) {
        Str_Math sm = new Str_Math();
        sm.test_division();
    }
  
}