/*
Flavius Josephus was a famous Jewish historian of the first century,
at the time of the destruction of the Second Temple. According to legend,
during the Jewish-Roman war he was trapped in a cave with a group of
forty soldiers surrounded by Romans. Preferring death to capture,
the Jews decided to form a circle and, proceeding around it, to kill
every third person remaining until no one was left. Josephus found the
safe spot in the circle and thus stayed alive.

Write a function josephus(n,m) that returns a list of n people,
numbered from 0 to n-1, in the order in which they are executed,
every mth person in turn, with the sole survivor as the last person
in the list.

What is the value of josephus(41,3)?
In what position did Josephus survive?
*/

struct Josephus {
    people: Vec<Option<usize>>,
    m: usize,
    current: usize,
    count: usize,
}

impl Iterator for Josephus {
    type Item = usize;
    fn next(&mut self) -> Option<Self::Item> {
        if self.count == 0 {
            return None
        }
        for i in 0..self.m {
            self.current = (self.current + 1) % self.people.len();
            while self.people[self.current].is_none() {
                self.current = (self.current + 1) % self.people.len();
            }
        }
        self.count -= 1;
        self.people[self.current] = None;
        Some(self.current)
    }
}

impl Josephus {
    fn new(size: usize, m: usize) -> Self {
        let mut j = Josephus{ count: size, m: m, current: size - 1, people: vec!() };
        for i in 0..size {
            j.people.push(Some(i));
        }
        j
    }
}

fn main() {
    let mut x = Josephus::new(41, 3).peekable();
    while let Some(p) = x.next() {
        if x.peek().is_none() {
            println!("\nfinal position = {}", p)
        } else {
            print!("{} ", p);
        }
    }
}