package other;

public class interview_arrayshift_space_rolloinghash {
    /**
     * n = 5
     * [1,2,3,4,5] or [5,4,3,2,1]
     * [1,2,3,4,5]: true
     * [3,4,5,1,2]: true
     * *[4,5,1,2,3]: true
     * [5,1,2,3,4]: true
     * [5,4,1,2,3]: false
     * *[3,2,1,5,4]: true
     *
     *
     * Time BigO: n
     * Space BigO: n
     *
     */

    public static void main (String[] args) {


//        int[] ary = {1,2,3,4,5};
//        int[] ary = {5,1,2,3,4};
        int[] ary = {4,5,1,2,3};
//        int[] ary = {5,4,1,2,3}; // false
//        int[] ary = {4,5,6,7,8,1,2,3};
//        int[] ary = {7,8,4,5,6,1,2,3}; // wrong: double downs

//        int[] ary = {5,4,3,2,1};
//        int[] ary = {3,2,1,5,4};
//        int[] ary = {7,6,5,4,3,2,1,9,8};
//        int[] ary = {3,2,1,7,6,5,9,8}; // wrong: double ups

        // append the exact same array to the end
//        int[] ary_2 = new int[ary.length * 2];
//        for (int i = 0; i < ary.length; i++) {
//            ary_2[i] = ary[i];
//            ary_2[i + ary.length] = ary[i];
//        }

        int hash_power = 31;

        // ascending
        boolean is_asce_ok = check_asec(ary, hash_power);
        System.out.println("is_asce_ok: " + is_asce_ok);

        // descending
        boolean is_desc_ok = check_desc(ary, hash_power);
        System.out.println("is_desc_ok: " + is_desc_ok);

    }

    private static long hash(int[] ary, int hash_power) {
        long hash = 0l;
        for (int i = 0; i < ary.length; i++) {
            hash = hash * hash_power + ary[i]; // 左大右小
        }
        return hash;
    }

    private static boolean check_asec(int[] ary, int hash_power) {
        // create asec ary
        int[] ary_asec_ok_ary =  new int[ary.length];
        for (int i = 0; i < ary_asec_ok_ary.length; i++) {
            ary_asec_ok_ary[i] = i + 1;
        }
        // calculate hash
        long hash_asec_ok_value = hash(ary_asec_ok_ary, hash_power);
        // check it
        boolean is_asce_ok = check_result(ary, hash_asec_ok_value, "asec", hash_power);
        return is_asce_ok;
    }

    private static boolean check_desc(int[] ary, int hash_power) {
        // create desc ary
        int[] ary_desc_ok_ary =  new int[ary.length];
        for (int i = 0; i < ary_desc_ok_ary.length; i++) {
            ary_desc_ok_ary[i] = ary_desc_ok_ary.length - i; // ex. [5,4,3,2,1]
        }
        // calculate hash
        long hash_desc_ok_value = hash(ary_desc_ok_ary, hash_power);
        // check it
        boolean is_desc_ok = check_result(ary, hash_desc_ok_value, "desc", hash_power);
        return is_desc_ok;
    }

    private static boolean check_result(int[] ary, long target_hash, String direction, int hash_power) {
        boolean isAsecOK = false;
        Long hash_val = null;
        for (int i = 0; i < ary.length; i++) {
            // calculate hash value
            if (hash_val == null) {
                hash_val = hash(ary, hash_power);
            }else {
                hash_val -= (long)(ary[i-1] * Math.pow(hash_power,ary.length-1)); // step01: remove the lest-most number
                hash_val *= hash_power; // step02: more ALL left
                hash_val += ary[i-1]; // step03: add the to the right-most place
            }

            // check hash
            if (hash_val == target_hash) {
                // if hash matched, check in details
                int i_ary_count = 0;
                int i_ary_tmp = i;
                while (true) {
                    if (i_ary_count >= ary.length) {
                        isAsecOK = true;
                        break;
                    }
                    if (i_ary_tmp >= ary.length) {
                        // % go around the array to the start
                        i_ary_tmp = 0;
                    };

                    /** main logic here **/
                    if (direction.equals("asec")) {
                        int val = i_ary_count + 1;
                        if (ary[i_ary_tmp] != val) {
                            isAsecOK = false;
                            break;
                        }
                    }else if (direction.equals("desc")) {
                        int val = ary.length - i_ary_count;
                        if (ary[i_ary_tmp] != val) {
                            isAsecOK = false;
                            break;
                        }
                    }

                    i_ary_count++;
                    i_ary_tmp++;

                } // end of while
            } // hash matched
            if (isAsecOK) break;
        }
        return isAsecOK;
    }

}