// Week 8 – Solutions of the practice exercises
// Run: java Exercises08.java
import java.util.ArrayDeque;
import java.util.Queue;

public class Exercises08 {

    // E1. Code tracing (from the old test): what does it print for n = 10?
    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();
    }

    // E2. Josephus problem: n people in a circle, every k-th is eliminated. Who remains last?
    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()); // send k-1 people to the rear
            order.append(q.poll()).append(' ');             // the k-th is eliminated
        }
        System.out.print("order of elimination: " + order);
        return q.poll();
    }

    // E3. Round-robin scheduling: every process gets at most 'quantum' time, then goes to the rear
    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] + " done (t=" + time + ")  ");
        }
        System.out.println();
    }

    // E4. Reversing a queue with the help of a stack
    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;
    }

    // E5. Code tracing: letter = enqueue, '*' = dequeue and print
    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();
    }

    // E6. The average of the last k items, continuously (moving average) with a queue – O(1) per item
    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("E1. ");
        fibonacciQueue(10);
        System.out.print("E2. ");
        System.out.println("-> survivor: " + josephus(7, 3));
        System.out.print("E3. ");
        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("E4. reverse([1,2,3,4]) = " + reverse(q));
        System.out.println("E5. 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("E6. moving average (k=3): ");
        movingAverage(new int[] { 10, 20, 30, 40, 50, 60 }, 3);
    }
}