use std::collections::BTreeSet;

use itertools::Itertools;

#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Point {
    pub row: usize,
    pub col: usize,
}

pub fn all_coords(width: usize, height: usize) -> impl Iterator<Item = Point> {
    (0..height)
        .cartesian_product(0..width)
        .map(|(row, col)| Point { row, col })
}

///Never Eat Shredded Wheat
pub fn adjacent_cardinal<T: Copy>(grid: &[Vec<T>], coords: Point) -> [Option<T>; 4] {
    let mut retval = [const { None }; 4];
    let (row, col) = (coords.row, coords.col);

    if row > 0 {
        retval[0] = Some(grid[row - 1][col]) //N
    }
    if col < grid[0].len() - 1 {
        retval[1] = Some(grid[row][col + 1]) //E
    }
    if row < grid.len() - 1 {
        retval[2] = Some(grid[row + 1][col]) //S
    }
    if col > 0 {
        retval[3] = Some(grid[row][col - 1]) //N
    }

    retval
}

pub fn adjacent_cardinal_points<T: Copy>(grid: &[Vec<T>], coords: Point) -> Vec<Point> {
    let mut retval = vec![];
    let (row, col) = (coords.row, coords.col);

    if row > 0 {
        retval.push(Point { row: row - 1, col }) //N
    }
    if col < grid[0].len() - 1 {
        retval.push(Point { row, col: col + 1 }) //E
    }
    if row < grid.len() - 1 {
        retval.push(Point { row: row + 1, col }) //S
    }
    if col > 0 {
        retval.push(Point { row, col: col - 1 }) //W
    }

    retval
}

//2d spatial digraph
pub fn flood(digraph: &[Vec<Vec<Point>>], start: Point) -> BTreeSet<Point> {
    let mut reachable = BTreeSet::new();
    let mut frontier = BTreeSet::from_iter([start]);

    while let Some(cursor) = frontier.pop_first() {
        reachable.insert(cursor);
        let next = BTreeSet::from_iter(digraph[cursor.row][cursor.col].iter().cloned());
        for &point in next.difference(&reachable) {
            frontier.insert(point);
        }
    }

    reachable
}

//2d spatial dag
pub fn paths_to_each_point(
    digraph: &[Vec<Vec<Point>>],
    start: Point,
) -> Vec<Vec<BTreeSet<Vec<Point>>>> {
    let mut paths_to_each_point = vec![vec![BTreeSet::new(); digraph.len()]; digraph[0].len()];
    paths_to_each_point[start.row][start.col] = BTreeSet::from_iter([vec![start]]);
    let mut frontier = BTreeSet::from_iter([start]);

    while let Some(cursor) = frontier.pop_first() {
        for point in &digraph[cursor.row][cursor.col] {
            frontier.insert(*point);
            let paths_to_new_point = paths_to_each_point[cursor.row][cursor.col].clone();
            for mut path in paths_to_new_point {
                path.push(*point);
                paths_to_each_point[point.row][point.col].insert(path);
            }
        }
    }

    paths_to_each_point
}