use crate::direction6::Direction6;
use crate::generators::{
    HexGenerationStep, HexGenerationSteps, HexGenerationVisitor, MazeGenerator6D,
    VecHexGenerationVisitor,
};
use crate::hex_coord::HexCoord;
use crate::wall6_grid::Wall6Grid;
use rand::SeedableRng;
use rand::prelude::IndexedRandom;
use rand::rngs::StdRng;

pub struct RecursiveBacktracker6 {
    rng_seed: u64,
}

impl Default for RecursiveBacktracker6 {
    fn default() -> Self {
        Self::new_random()
    }
}

impl RecursiveBacktracker6 {
    pub fn new_random() -> Self {
        Self {
            rng_seed: rand::random(),
        }
    }

    pub fn new_from_seed(rng_seed: u64) -> Self {
        if rng_seed == 0 {
            Self::new_random()
        } else {
            Self { rng_seed }
        }
    }

    pub fn generate(&self, width: usize, height: usize) -> Wall6Grid {
        self.generate_with_steps(width, height).0
    }

    pub fn generate_steps(&self, width: usize, height: usize) -> HexGenerationSteps {
        HexGenerationSteps::new(self.generate_with_steps(width, height).1)
    }

    fn generate_with_steps(
        &self,
        width: usize,
        height: usize,
    ) -> (Wall6Grid, Vec<HexGenerationStep>) {
        let mut cells = Wall6Grid::new(width, height);
        let mut visitor = VecHexGenerationVisitor::default();

        if width == 0 || height == 0 {
            visitor.on_step(&HexGenerationStep::Complete);
            return (cells, visitor.into_steps());
        }

        let mut visit_map = vec![false; width * height];
        let start = HexCoord::new(0, 0);
        let mut backtrace: Vec<HexCoord> = Vec::new();
        let mut rng = StdRng::seed_from_u64(self.rng_seed);

        let mut current = start;
        loop {
            let idx = (current.r as usize) * width + current.q as usize;
            if !visit_map[idx] {
                visitor.on_step(&HexGenerationStep::Visit { cell: current });
            }
            visit_map[idx] = true;

            if let Some(next) =
                Self::select_random_unvisited_neighbor(&mut rng, &visit_map, current, width, height)
            {
                backtrace.push(current);
                visitor.on_step(&HexGenerationStep::AddToFrontier { cell: current });
                cells.remove_wall_between(current, next);
                visitor.on_step(&HexGenerationStep::Carve {
                    from: current,
                    to: next,
                });
                current = next;
                continue;
            }

            if let Some(cell) = backtrace.pop() {
                current = cell;
                visitor.on_step(&HexGenerationStep::Backtrack { to: cell });
            } else {
                break;
            }
        }

        visitor.on_step(&HexGenerationStep::Complete);
        (cells, visitor.into_steps())
    }

    fn select_random_unvisited_neighbor(
        rng: &mut StdRng,
        visit_map: &[bool],
        current: HexCoord,
        width: usize,
        height: usize,
    ) -> Option<HexCoord> {
        let mut candidates = Vec::with_capacity(6);
        for &dir in &Direction6::CARDINALS {
            if let Some(n) = current.try_neighbor(dir, width, height) {
                let idx = (n.r as usize) * width + n.q as usize;
                if !visit_map[idx] {
                    candidates.push(n);
                }
            }
        }

        if candidates.is_empty() {
            return None;
        }

        candidates.choose(rng).copied()
    }
}

impl MazeGenerator6D for RecursiveBacktracker6 {
    fn new_random() -> Self {
        RecursiveBacktracker6::new_random()
    }

    fn new_from_seed(rng_seed: u64) -> Self {
        RecursiveBacktracker6::new_from_seed(rng_seed)
    }

    fn generate(&self, width: usize, height: usize) -> Wall6Grid {
        self.generate(width, height)
    }

    fn generate_steps(&self, width: usize, height: usize) -> HexGenerationSteps {
        self.generate_steps(width, height)
    }

    fn name(&self) -> &'static str {
        "hex-recursive-backtracker"
    }

    fn description(&self) -> &'static str {
        "Depth-first backtracking generator for hexagonal grids creating long corridors"
    }
}
