// Week 10 – Circular singly linked list with a single End (last) pointer
// Run: java CircularList.java
public class CircularList {

    static class Node {
        int value;
        Node next;
        Node(int v) { value = v; }
    }

    Node last; // the last element; the first one: last.next. Empty list: null.

    // Insertion at the end – O(1)
    void insertLast(int x) {
        Node n = new Node(x);
        if (last == null) {
            n.next = n;          // one-element ring: points to itself
        } else {
            n.next = last.next;  // the new element points to the first one
            last.next = n;
        }
        last = n;
    }

    // Insertion at the beginning – O(1): linked after last, but last does NOT move,
    // so the new element becomes the first one (last.next)
    void insertFirst(int x) {
        Node n = new Node(x);
        if (last == null) {
            n.next = n;
            last = n;
        } else {
            n.next = last.next;
            last.next = n;
        }
    }

    // Traversal: from the first element until we get back (do-while!)
    String str() {
        if (last == null) return "[]";
        StringBuilder sb = new StringBuilder("[");
        Node p = last.next;
        do {
            sb.append(p.value).append(p != last ? " " : "");
            p = p.next;
        } while (p != last.next);
        return sb.append("] (and back to the beginning)").toString();
    }

    // Josephus: every k-th element is removed from the ring
    int josephus(int k) {
        Node prev = last;
        StringBuilder order = new StringBuilder();
        while (prev.next != prev) {
            for (int i = 1; i < k; i++) prev = prev.next;
            Node out = prev.next;
            order.append(out.value).append(' ');
            prev.next = out.next;           // unlink it from the ring
        }
        System.out.print("order of elimination: " + order);
        last = prev;
        return prev.value;
    }

    public static void main(String[] args) {
        CircularList c = new CircularList();
        for (int i = 1; i <= 7; i++) c.insertLast(i);
        System.out.println(c.str());
        c.insertFirst(0);
        System.out.println("insertFirst(0): " + c.str());

        CircularList j = new CircularList();
        for (int i = 1; i <= 7; i++) j.insertLast(i);
        System.out.println(" -> survivor: " + j.josephus(3));
    }
}