// 第 3 周 – 数组操作：插入、删除、逆置、循环移位
// 运行：java ArrayOps.java
import java.util.Arrays;

public class ArrayOps {

    // 在下标 pos 处插入。数组中有 n 个元素，容量为 a.length。
    // 从后往前把元素右移 – O(n)。
    //   伪代码（从 1 开始）：
    //     For i ← n down to pos : A[i + 1] ← A[i]
    //     A[pos] ← x ; n ← n + 1
    static int insert(int[] a, int n, int pos, int x) {
        if (n == a.length) throw new IllegalStateException("the array is full");
        for (int i = n - 1; i >= pos; i--) {
            a[i + 1] = a[i];
        }
        a[pos] = x;
        return n + 1; // 新的元素个数
    }

    // 删除下标 pos 处的元素：从前往后把元素左移 – O(n)。
    static int delete(int[] a, int n, int pos) {
        for (int i = pos; i < n - 1; i++) {
            a[i] = a[i + 1];
        }
        a[n - 1] = 0; // 不是必需的，只是为了清楚
        return n - 1;
    }

    // 用两个下标原地逆置 – O(n),O(1) 空间。
    static void reverse(int[] a) {
        int i = 0, j = a.length - 1;
        while (i < j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
        }
    }

    // 循环左移 k 位，三次逆置 – O(n),O(1) 空间。
    // [1 2 3 4 5], k=2 -> [3 4 5 1 2]
    static void rotateLeft(int[] a, int k) {
        int n = a.length;
        k = k % n;
        reverseRange(a, 0, k - 1);
        reverseRange(a, k, n - 1);
        reverseRange(a, 0, n - 1);
    }

    static void reverseRange(int[] a, int i, int j) {
        while (i < j) {
            int t = a[i];
            a[i++] = a[j];
            a[j--] = t;
        }
    }

    public static void main(String[] args) {
        int[] a = new int[6];
        int n = 0;
        for (int v : new int[] { 5, 8, 13, 21, 34 }) a[n++] = v;
        System.out.println("initially:       " + Arrays.toString(a) + " n=" + n);

        n = insert(a, n, 2, 99);
        System.out.println("insert(2, 99):   " + Arrays.toString(a) + " n=" + n);

        n = delete(a, n, 1);
        System.out.println("delete(1):       " + Arrays.toString(a) + " n=" + n);

        int[] r = { 1, 2, 3, 4, 5 };
        reverse(r);
        System.out.println("reverse:         " + Arrays.toString(r));

        int[] q = { 1, 2, 3, 4, 5 };
        rotateLeft(q, 2);
        System.out.println("rotateLeft(2):   " + Arrays.toString(q));
    }
}