use core::fmt;
use std::collections::HashMap;

use super::{
    byte_range::ByteRange,
    enfa::{ENFA, MultiState},
};

pub type StateId = usize;

pub struct State {
    trans: HashMap<ByteRange, StateId>,
    default_trans: StateId,
    accept: bool,
}

#[allow(clippy::upper_case_acronyms)]
pub struct DFA {
    start: StateId,
    states: Vec<State>,
}

impl fmt::Debug for DFA {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        writeln!(f, "DFA {{")?;
        for (i, s) in self.states.iter().enumerate() {
            if self.start == i {
                write!(f, "-> {i}: ")?;
            } else {
                write!(f, "   {i}: ")?;
            }

            for (chr, to) in s.trans.iter() {
                write!(f, "{chr:?} to {to}, ")?;
            }

            write!(f, "dfl to {}", s.default_trans)?;
            if s.accept {
                write!(f, ", accept")?;
            }
            writeln!(f)?;
        }
        writeln!(f, "}}")
    }
}

impl DFA {
    pub fn matches(&self, x: &[u8]) -> bool {
        let mut state = self.start;
        'next_byte: for &b in x.iter() {
            for (range, &next_state) in self.states[state].trans.iter() {
                if range.contains(b) {
                    state = next_state;
                    continue 'next_byte;
                }
            }
            state = self.states[state].default_trans;
        }
        self.states[state].accept
    }

    pub fn simplify(&mut self) {
        for state in self.states.iter_mut() {
            state.trans.retain(|_, to| *to != state.default_trans);
        }
    }
}

impl From<ENFA> for DFA {
    fn from(mut nfa: ENFA) -> Self {
        nfa.remove_unreachable();

        let mut multi_states = nfa.all_multi_states();
        multi_states.insert(nfa.void_multi_state());
        let mut len = 0;
        let multi_to_dfa: HashMap<MultiState, StateId> = multi_states
            .clone()
            .into_iter()
            .map(|ms| {
                len += 1;
                (ms, len - 1)
            })
            .collect();

        let void = multi_to_dfa[&nfa.void_multi_state()];

        let mut states: Vec<State> = (0..len)
            .map(|_| State {
                trans: HashMap::new(),
                default_trans: void,
                accept: false,
            })
            .collect();

        for ms in multi_states.iter() {
            let i: usize = multi_to_dfa[ms];
            states[i].accept = ms.accept();
            for t in ms.possible_transitions() {
                let k = multi_to_dfa[&ms.transition(t)];
                states[i].trans.insert(t, k);
            }
        }

        let mut this = Self {
            start: multi_to_dfa[&nfa.start_multi_state()],
            states,
        };
        this.simplify();
        this
    }
}