// 8. hét – A gyakorlati feladatok megoldásai
// Futtatás: java Exercises08.java
import java.util.ArrayDeque;
import java.util.Queue;

public class Exercises08 {

    // F1. Kódkövetés (a régi dolgozatból): mit ír ki n = 10 esetén?
    static void fibonacciQueue(int n) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(0);
        q.offer(1);
        for (int i = 0; i < n; i++) {
            int a = q.poll();
            System.out.print(a + " ");
            int b = q.peek();
            q.offer(a + b);
        }
        System.out.println();
    }

    // F2. Josephus-probléma: n ember körben, minden k-adik kiesik. Ki marad utoljára?
    static int josephus(int n, int k) {
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) q.offer(i);
        StringBuilder order = new StringBuilder();
        while (q.size() > 1) {
            for (int i = 1; i < k; i++) q.offer(q.poll()); // k-1 embert hátraküldünk
            order.append(q.poll()).append(' ');             // a k-adik kiesik
        }
        System.out.print("kiesési sorrend: " + order);
        return q.poll();
    }

    // F3. Round-robin ütemezés: minden folyamat legfeljebb 'quantum' időt kap, utána a sor végére kerül
    static void roundRobin(String[] names, int[] burst, int quantum) {
        Queue<Integer> q = new ArrayDeque<>();
        int[] left = burst.clone();
        for (int i = 0; i < names.length; i++) q.offer(i);
        int time = 0;
        while (!q.isEmpty()) {
            int p = q.poll();
            int run = Math.min(quantum, left[p]);
            time += run;
            left[p] -= run;
            if (left[p] > 0) q.offer(p);
            else System.out.print(names[p] + " kész (t=" + time + ")  ");
        }
        System.out.println();
    }

    // F4. Sor megfordítása verem segítségével
    static Queue<Integer> reverse(Queue<Integer> q) {
        ArrayDeque<Integer> st = new ArrayDeque<>();
        while (!q.isEmpty()) st.push(q.poll());
        while (!st.isEmpty()) q.offer(st.pop());
        return q;
    }

    // F5. Kódkövetés: betű = enqueue, '*' = dequeue és kiírás
    static String trace(String ops) {
        Queue<Character> q = new ArrayDeque<>();
        StringBuilder out = new StringBuilder();
        for (char c : ops.toCharArray()) {
            if (c == '*') out.append(q.poll());
            else if (c != ' ') q.offer(c);
        }
        return out.toString();
    }

    // F6. Az utolsó k elem átlaga folyamatosan (mozgó átlag) sorral – elemenként O(1)
    static void movingAverage(int[] data, int k) {
        Queue<Integer> window = new ArrayDeque<>();
        int sum = 0;
        for (int x : data) {
            window.offer(x);
            sum += x;
            if (window.size() > k) sum -= window.poll();
            System.out.printf("%.1f ", (double) sum / window.size());
        }
        System.out.println();
    }

    public static void main(String[] args) {
        System.out.print("F1. ");
        fibonacciQueue(10);
        System.out.print("F2. ");
        System.out.println("-> túlélő: " + josephus(7, 3));
        System.out.print("F3. ");
        roundRobin(new String[] { "P1", "P2", "P3" }, new int[] { 5, 2, 4 }, 2);
        Queue<Integer> q = new ArrayDeque<>(java.util.List.of(1, 2, 3, 4));
        System.out.println("F4. reverse([1,2,3,4]) = " + reverse(q));
        System.out.println("F5. trace(\"D A T * A * S * T R * U C * T\") = " + trace("D A T * A * S * T R * U C * T"));
        System.out.print("F6. mozgó átlag (k=3): ");
        movingAverage(new int[] { 10, 20, 30, 40, 50, 60 }, 3);
    }
}