/// --- Part Two ---
///
/// Now, you're ready to choose a directory to delete.
///
/// The total disk space available to the filesystem is 70000000.  To run the update, you need
/// unused space of at least 30000000.  You need to find a directory you can delete that will free
/// up enough space to run the update.
///
/// In the example above, the total size of the outermost directory (and thus the total amount of
/// used space) is 48381165; this means that the size of the unused space must currently be
/// 21618835, which isn't quite the 30000000 required by the update.  Therefore, the update still
/// requires a directory with total size of at least 8381165 to be deleted before it can run.
///
/// To achieve this, you have the following options:
///
///     Delete directory e, which would increase unused space by 584.
///     Delete directory a, which would increase unused space by 94853.
///     Delete directory d, which would increase unused space by 24933642.
///     Delete directory /, which would increase unused space by 48381165.
///
/// Directories e and a are both too small; deleting them would not free up enough space. However,
/// directories d and / are both big enough!  Between these, choose the smallest: d, increasing
/// unused space by 24933642.
///
/// Find the smallest directory that, if deleted, would free up enough space on the filesystem to
/// run the update.  What is the total size of that directory?
use clap::Parser;
use nom::branch::alt;
use nom::bytes::streaming::tag;
use nom::character::streaming::{char, newline, not_line_ending, space1, u64};
use nom::combinator::{map, peek};
use nom::error::{context, ContextError, ErrorKind as NomErrorKind, ParseError};
use nom::multi::many_till;
use nom::sequence::{delimited, preceded, terminated, tuple};
use nom::IResult;

use std::collections::HashMap;
use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
use std::iter::*;
use std::path::PathBuf;

pub type Input<'a> = &'a str;
pub type Result<'a, T> = IResult<Input<'a>, T, Error<Input<'a>>>;

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ErrorKind {
    Nom(NomErrorKind),
    Context(&'static str),
    Custom(String),
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Error<I> {
    pub errors: Vec<(I, ErrorKind)>,
}

impl<I> ParseError<I> for Error<I> {
    fn from_error_kind(input: I, kind: NomErrorKind) -> Self {
        let errors = vec![(input, ErrorKind::Nom(kind))];
        Self { errors }
    }

    fn append(input: I, kind: NomErrorKind, mut other: Self) -> Self {
        other.errors.push((input, ErrorKind::Nom(kind)));
        other
    }
}

impl<I> ContextError<I> for Error<I> {
    fn add_context(input: I, ctx: &'static str, mut other: Self) -> Self {
        other.errors.push((input, ErrorKind::Context(ctx)));
        other
    }
}

const FILEPATH: &'static str = "examples/input.txt";
const EOF_CHAR: char = '\0';
const TOTALSPACE: u64 = 70000000;
const NEEDEDSPACE: u64 = 30000000;

#[derive(Parser, Debug)]
#[clap(author, version, about, long_about = None)]
struct Cli {
    #[clap(short, long, default_value = FILEPATH)]
    file: PathBuf,
}

#[derive(Clone, Debug)]
enum Commands {
    ChangeDir(String),
    List(Vec<ListEntry>),
}

#[derive(Clone, Debug)]
enum ListEntry {
    File(FileEntry),
    Folder(String),
}

#[derive(Clone, Debug)]
struct FileEntry {
    name: String,
    size: u64,
}

#[derive(Clone, Debug)]
struct Arena(Vec<Node>);

#[derive(Clone, Debug)]
struct Node {
    size: u64,
    parent: Option<usize>,
    children: HashMap<String, usize>,
}

impl Node {
    fn new() -> Self {
        Node {
            size: 0,
            parent: None,
            children: HashMap::new(),
        }
    }

    fn with_parent(idx: usize) -> Self {
        Node {
            size: 0,
            parent: Some(idx),
            children: HashMap::new(),
        }
    }
}

impl Arena {
    // NOTE: only call this once per node
    fn consume(&mut self, idx: usize, ls: Vec<ListEntry>) {
        for le in ls.into_iter() {
            match le {
                ListEntry::File(f) => {
                    let mut iteridx = idx;
                    loop {
                        self.0[iteridx].size += f.size;
                        iteridx = if let Some(pidx) = self.0[iteridx].parent {
                            pidx
                        } else {
                            break;
                        };
                    }
                }
                ListEntry::Folder(f) => {
                    let fidx = self.0.len();
                    self.0.push(Node::with_parent(idx));
                    self.0[idx].children.insert(f, fidx);
                }
            }
        }
    }

    fn get(&mut self, idx: usize) -> &mut Node {
        &mut self.0[idx]
    }
}

fn parse_cd(input: &str) -> Result<Commands> {
    context(
        "parse_cd",
        map(
            delimited(tuple((tag("cd"), space1)), not_line_ending, newline),
            |s: &str| Commands::ChangeDir(s.to_string()),
        ),
    )(input)
}

fn end_of_file_or_ls(input: &str) -> Result<char> {
    alt((char(EOF_CHAR), peek(char('$'))))(input)
}

fn parse_ls(input: &str) -> Result<Commands> {
    let (input, _) = context("parse_ls", terminated(tag("ls"), newline))(input)?;
    let (input, (lsv, _)) = many_till(parse_ls_entry, end_of_file_or_ls)(input)?;
    Ok((input, Commands::List(lsv)))
}

fn parse_ls_entry(input: &str) -> Result<ListEntry> {
    context("parse_ls_entry", alt((parse_file, parse_folder)))(input)
}

fn parse_file(input: &str) -> Result<ListEntry> {
    map(
        terminated(tuple((u64, preceded(tag(" "), not_line_ending))), newline),
        |(size, name): (u64, &str)| {
            ListEntry::File(FileEntry {
                name: name.to_string(),
                size,
            })
        },
    )(input)
}

fn parse_folder(input: &str) -> Result<ListEntry> {
    map(
        delimited(tag("dir "), not_line_ending, newline),
        |s: &str| ListEntry::Folder(s.to_string()),
    )(input)
}

fn parse_cmd(input: &str) -> Result<Commands> {
    context(
        "parse_cmd",
        preceded(tuple((tag("$"), space1)), alt((parse_cd, parse_ls))),
    )(input)
}

fn main() {
    let args = Cli::parse();

    let file = File::open(&args.file).unwrap();
    let mut reader = BufReader::new(file);

    let mut buf = String::new();
    let mut cmds = Vec::new();
    'block: loop {
        let len = reader.read_line(&mut buf).unwrap();
        if len == 0 {
            buf.push(EOF_CHAR);
        }
        loop {
            match parse_cmd(buf.as_str()) {
                Ok((input, cmd)) => {
                    cmds.push(cmd);
                    if len == 0 && input.len() == 0 {
                        break 'block;
                    }
                    let _ = buf.drain(..(buf.len() - input.len()));
                }
                Err(err) => match err {
                    nom::Err::Incomplete(_) => continue 'block,
                    e @ _ => panic!("buf={} err={}", buf, e),
                },
            }
        }
    }

    let mut loc = 0;
    let mut arena = Arena(Vec::new());
    arena.0.push(Node::new());
    for cmd in cmds.into_iter() {
        match cmd {
            Commands::ChangeDir(dir) => match dir.as_str() {
                "/" => loc = 0,
                ".." => loc = arena.get(loc).parent.unwrap(),
                _ => loc = arena.get(loc).children[&dir],
            },
            Commands::List(lsv) => arena.consume(loc, lsv),
        }
    }

    let rmdir_minsize = NEEDEDSPACE - (TOTALSPACE - arena.get(0).size);
    let res: u64 = arena
        .0
        .into_iter()
        .filter(|n| n.size >= rmdir_minsize)
        .map(|n| n.size)
        .min().unwrap();
    println!("{res:?}");
}