// 3. hét – Tömbműveletek: beszúrás, törlés, megfordítás, forgatás
// Futtatás: java ArrayOps.java
import java.util.Arrays;

public class ArrayOps {

    // Beszúrás a pos indexre. A tömbben n elem van, a kapacitás a.length.
    // Hátulról kezdve jobbra toljuk az elemeket – O(n).
    //   Pszeudokód (1-től):
    //     Ciklus i ← n-től pos-ig visszafelé : 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("a tömb megtelt");
        for (int i = n - 1; i >= pos; i--) {
            a[i + 1] = a[i];
        }
        a[pos] = x;
        return n + 1; // az új elemszám
    }

    // Törlés a pos indexről: elölről kezdve balra toljuk az elemeket – 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; // nem kötelező, csak a szemléletesség kedvéért
        return n - 1;
    }

    // Megfordítás helyben, két mutatóval – O(n), O(1) tárigény.
    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--;
        }
    }

    // Forgatás balra k hellyel, három megfordítással – O(n), O(1) tárigény.
    // [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("kezdetben:       " + 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));
    }
}