use {
    anyhow::{
        anyhow,
        Context,
        Result,
    },
    regex::Regex,
    std::{
        collections::HashMap,
        env::args,
        fs::File,
        io::{
            BufRead,
            BufReader,
        },
        path::Path,
    },
};

#[derive(Debug,PartialEq)]
struct FileDetails {
    size: usize,
}

#[derive(Debug,PartialEq)]
struct FileTree {
    tree: HashMap<String, EntryNode>,
}

#[derive(Debug,PartialEq)]
enum EntryNode {
    File(FileDetails),
    Directory(FileTree),
}

impl FileTree {
    fn default() -> Self {
        Self {
            tree: HashMap::new(),
        }
    }

    fn chdir(&mut self, path: &[String]) -> Option<&mut Self> {
        if let Some((i, directory)) = path.iter().enumerate().find(|(_, name)| *name != "/") {
            if let Some(node) = self.tree.get_mut(directory) {
                match node {
                    EntryNode::File(_) => panic!("Tried to chdir into a file."),
                    EntryNode::Directory(tree) => tree.chdir(&path[(i + 1)..]),
                }
            } else {
                None
            }
        } else {
            Some(self)
        }
    }

    fn size(&self) -> usize {
        let mut size = 0;
        for node in self.tree.values() {
            match node {
                EntryNode::File(file) => size += file.size,
                EntryNode::Directory(directory) => size += directory.size(),
            }
        }

        size
    }

    fn traverse(&self) -> TreeTraverse {
        TreeTraverse::new(self)
    }
}

struct TreeTraverse<'a> {
    tree: &'a FileTree,
    visited: Vec<&'a EntryNode>,
}

impl<'a> TreeTraverse<'a> {
    fn new(tree: &'a FileTree) -> Self {
        Self {
            tree,
            visited: vec![],
        }
    }

    fn recurse(&mut self, tree: &'a FileTree) -> Option<&'a EntryNode> {
        for node in tree.tree.values() {
            if self.visited.contains(&node) {
                continue;
            }

            match node {
                EntryNode::File(_) => {
                    self.visited.push(node);
                    return Some(node);
                },
                EntryNode::Directory(subdir) => {
                    return self.recurse(subdir).or_else(|| {
                        self.visited.push(node);
                        Some(node)
                    });
                }
            }
        }
        None
    }
}

impl<'a> Iterator for TreeTraverse<'a> {
    type Item = &'a EntryNode;

    fn next(&mut self) -> Option<&'a EntryNode> {
        self.recurse(self.tree)
    }
}

fn read_input<T: AsRef<Path>>(filename: T) -> Result<FileTree> {
    let reader = BufReader::new(File::open(filename)?);
    let re = Regex::new(r#"(?x)^
        (\$\s+(?P<command>\S+)(\s+(?P<arg>\S+))?)|
        (dir\s+(?P<directory>.+))|
        ((?P<size>[0-9]+)\s+(?P<filename>\S+))
    $"#).context("Could not compile regex.")?;

    let mut root = FileTree::default();
    let mut path = vec![];

    for (lineno, v) in reader.lines().enumerate() {
        let node = root.chdir(&path).ok_or_else(|| anyhow!("Path {path:?} does not exist"))?;
        let s = v?;
        let caps = re.captures(&s)
            .ok_or_else(|| anyhow!("Regex matching failed on line {lineno}: '{s}'"))?;

        if let Some(command) = caps.name("command") {
            match command.as_str() {
                "cd" => {
                    if let Some(arg) = caps.name("arg") {
                        let dir = arg.as_str();
                        if dir == ".." {
                            path.pop();
                        } else if dir == "." {
                            // Remain in current directory.
                        } else {
                            path.push(String::from(dir));
                        }
                    }
                },
                "ls" => { },
                cmd => return Err(anyhow!("Unknown command: '{cmd}'.")),
            }
        } else if let Some(dir_cap) = caps.name("directory") {
            let directory = dir_cap.as_str();
            node.tree.insert(String::from(directory), EntryNode::Directory(FileTree::default()));
        } else if let (Some(cap_f), Some(cap_s)) = (caps.name("filename"), caps.name("size")) {
            let str_s = cap_s.as_str();
            let size = str_s.parse().context("Parse error: {str_s}")?;
            let filename = cap_f.as_str();
            node.tree.insert(String::from(filename), EntryNode::File(FileDetails { size }));
        } else {
            unreachable!();
        }
    }

    Ok(root)
}

fn part1(input: &FileTree) -> Result<usize> {
    Ok(input.traverse().filter_map(|node|
        if let EntryNode::Directory(directory) = node {
            let size = directory.size();
            if size <= 100000 {
                Some(size)
            } else {
                None
            }
        } else {
            None
        }).sum())
}

fn part2(input: &FileTree) -> Result<usize> {
    let capacity = 70000000;
    let required = 30000000;
    let used = input.size();
    let reclaim = required + used - capacity;

    input.traverse().filter_map(|node|
        if let EntryNode::Directory(directory) = node {
            let size = directory.size();
            if size >= reclaim {
                Some(size)
            } else {
                None
            }
        } else {
            None
        }).min().ok_or_else(|| anyhow!("No suitable directory found"))
}

fn main() -> Result<()> {
    let ( do_part_1, do_part_2 ) = aoc::do_parts();

    let filename = args().nth(1).ok_or_else(|| anyhow!("Missing input filename"))?;
    let input = read_input(filename).context("Could not read input")?;
    if do_part_1 {
        let solution = part1(&input).context("No solution for part 1")?;
        println!("Part1, solution found to be: {}", solution);
    }
    if do_part_2 {
        let solution = part2(&input).context("No solution for part 2")?;
        println!("Part2, solution found to be: {}", solution);
    }
    Ok(())
}