pub mod rectangular;

pub trait CalendarBoardState {
    type Placement;
    fn add_placement(&mut self, placement: &Self::Placement) -> bool;
    fn remove_placement(&mut self, placement: &Self::Placement) -> bool;
}

pub trait CalendarPuzzle {
    type Placement;
    type BoardState: CalendarBoardState<Placement=Self::Placement>;
    fn placements(&self, allow_flips: bool) -> Vec<Vec<Self::Placement>>;
    fn empty_board_state(&self) -> Self::BoardState;
    
    
    fn solve(&self, allow_flips: bool) -> Vec<Vec<usize>> {

        let placements = self.placements(allow_flips);
        let mut state = self.empty_board_state();
        let mut solutions = Vec::new();
        backtrack(&mut state, &mut Vec::new(), &placements, &mut solutions);

        solutions
    }
}

fn backtrack<P, B>(
    board_state: &mut B,
    stack: &mut Vec<usize>,
    placements: &Vec<Vec<P>>,
    solutions: &mut Vec<Vec<usize>>,
)
where B: CalendarBoardState<Placement=P> {
    let piece_index = stack.len();
    println!("{:?}", stack);
    
    if piece_index >= placements.len() {
        solutions.push(stack.clone());
    } else {
        for (i, placement) in placements[piece_index].iter().enumerate() {
            if board_state.add_placement(placement) {
                stack.push(i);
                backtrack(board_state, stack, placements, solutions);
                stack.pop();
                board_state.remove_placement(placement);
            }
        }
    }
}