package com.codewars.josephus;

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * MIT License
 * (c) 2017 Ricardo Constantino
 */

public class Josephus {
    public static void main(String[] args) {
        List<Integer> test1 = new LinkedList<>();
        Collections.addAll(test1, 1, 2, 3, 4, 5, 6, 7);
        josephusPermutation(test1, 3);
    }

    public static <T> List<T> josephusPermutation(final List<T> items, final int k) {

        LinkedList<T> list = new LinkedList<>();

        if (items.size() == 0) {
            return list;
        }
        if (items.size() == 1) {
            list.add(items.get(0));
            return list;
        }

        int size = items.size();

        int i = 0;
        Iterator<T> it = items.iterator();
        while (list.size() < size) {
            while (++i < k) {
                if (!it.hasNext()) {
                    it = items.iterator();
                }
                it.next();
            }
            if (!it.hasNext()) {
                it = items.iterator();
            }
            T tokill = it.next();
            list.add(tokill);
            it.remove();
            i = 0;
        }
        return list;
    }

    public static int josephusSurvivor(final int n, final int k) {
        List<Integer> items = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            items.add(i);
        }

        LinkedList<Integer> list = new LinkedList<>();

        int size = n;

        int i = 0;
        Iterator<Integer> it = items.iterator();
        while (list.size() < size) {
            while (++i < k) {
                if (!it.hasNext()) {
                    it = items.iterator();
                }
                it.next();
            }
            if (!it.hasNext()) {
                it = items.iterator();
            }
            Integer tokill = it.next();
            list.add(tokill);
            it.remove();
            i = 0;
        }
        return list.get(list.size()-1);
    }
}
