package com.company;

public class Rotate {
    /**
     * 下面是来源于《编程珠玑》的杂耍算法
     * 它仅用了一个临时存储空间，一趟遍历就完成了数组的移动。
     * 他怎么会知道开始指针和终止指针会有相同的时候？
     * 这是什么原理？
     * 其实(offset × arrayLength) % arrayLength = 0。
     * 也就是说只要经过offset和arrayLength的最小公倍数
     * 个数次的轮转偏移后当前指针肯定会和初始指针位置重叠。
     * 但是这并不代表整个数组偏移结束了。
     * 因为达到最小公倍数以后再轮转偏移就是无限循环了
     * 没有意义了
     * 而这个最小公倍数除以offset得到的就是已经移动完的元素个数了。
     * 所以得到的值肯定是小于等于数组元素个数的，因为是最小公倍数嘛。
     * 所以这就有必要改换起始指针
     * 通过实际模拟会发现一趟轮转移动所经过的元素彼此之间间隔的距离数是
     * offset和arrayLength的最小公因子
     * 所以只要最小公因子不是1就代表相邻的2个一趟轮转中的相邻的元素之间
     * 始终是隔着最小公因子-1个元素，所以这样循环下去只能是老死不相往来。
     * 并不会把数组中每个元素都移动完，所以才需要移动起始指针。
     * 那为什么要遍历数组长度那么多次呢？
     * 很简单因为每移动一次只能把一个被移动的元素移动到了相应的位置
     * 而本算法的目的是要所有元素都移动，所以肯定要经过数组长度数次循环才行。
     * @param sourceArray
     * @param offset
     */
    static public void rotateRight(int[] sourceArray,int offset) {
        int arrayLength = sourceArray.length;
        //由于offset极有可能超过数组长度，所以在运算之前还是先对其取模。
        int moduleOffset = offset % arrayLength;
        int startIndex = 0;
        int currentIndex = startIndex;
        int endIndex = (startIndex + moduleOffset) % arrayLength;
        int tempElement = sourceArray[startIndex];
        //现在开始逐个进行移动
        for (int counter = 0;counter < arrayLength;counter++) {
            if (startIndex != endIndex) {
                sourceArray[currentIndex] = sourceArray[endIndex];
                currentIndex = endIndex;
                endIndex = (currentIndex + moduleOffset) % arrayLength;
                for (int element:sourceArray) {
                    System.out.print(element + " ");
                }
                System.out.println("if");
            } else {
                sourceArray[currentIndex] = tempElement;
                currentIndex = ++startIndex;
                endIndex = (currentIndex + moduleOffset) % arrayLength;
                tempElement = sourceArray[startIndex];
                for (int element:sourceArray) {
                    System.out.print(element + " ");
                }
                System.out.println("else");
            }
        }
    }
}