use std::collections::HashMap;

enum RegexParseError {

}

/// guaranteed to have at least 2 states
/// state 0 is always the start state
/// state 1 is always the accept state
struct Nfa {
    num_states: usize,
    transitions: HashMap<(usize, char), Vec<usize>>
}

/// Nfa builder using Thompson's construction
/// Invariant: state 0 is always the start state
/// Invariant: state 1 is always the end state
/// Invariant: start state has no incoming edges
/// Invariant: end state has no outgoing edges
impl Nfa {

    fn from_regex(pattern: &str) -> Result<Self, RegexParseError> {
        todo!();
    }

    fn empty() -> Self {
        Self {
            num_states: 2,
            transitions: HashMap::from_iter([ ((0, '\0'), vec![1]) ])
        }
    }
    
    fn from_literals(cs: impl IntoIterator<Item=char>) -> Self {
        Self {
            num_states: 2,
            transitions: HashMap::from_iter(
                cs.into_iter().map(|c| ((0, c), vec![1]))
            )
        }
    }

    fn from_union(lhs: Self, rhs: Self) -> Self {
        let offset_lhs = 2;
        let offset_rhs = 2 + lhs.num_states;

        let new_transitions = [
            ((0, '\0'), vec![offset_lhs, offset_rhs]),
            ((offset_lhs + 1, '\0'), vec![1]),
            ((offset_rhs + 1, '\0'), vec![1])
        ].into_iter();

        let lhs_transitions = lhs.transitions.into_iter()
            .map(|((q_old, c), qs_new)| {
                let new_input = (q_old + offset_lhs, c);
                let new_output = qs_new.into_iter().map(|q| q + offset_lhs).collect();
                (new_input, new_output)
            });

        let rhs_transitions = rhs.transitions.into_iter()
            .map(|((q_old, c), qs_new)| {
                let new_input = (q_old + offset_rhs, c);
                let new_output = qs_new.into_iter().map(|q| q + offset_rhs).collect();
                (new_input, new_output)
            });
        
        Self {
            num_states: lhs.num_states + rhs.num_states + 2,
            transitions: HashMap::from_iter(
                new_transitions.chain(lhs_transitions).chain(rhs_transitions)
            )
        }
    }
    
    fn from_concat(lhs: Self, rhs: Self) -> Self {
        let offset_lhs = 2;
        let offset_rhs = 2 + lhs.num_states;

        let new_transitions = [
            ((0, '\0'), vec![offset_lhs]),
            ((offset_lhs + 1, '\0'), vec![offset_rhs]),
            ((offset_rhs + 1, '\0'), vec![1]),
        ].into_iter();

        let lhs_transitions = lhs.transitions.into_iter()
            .map(|((q_old, c), qs_new)| {
                let new_input = (q_old + offset_lhs, c);
                let new_output = qs_new.into_iter().map(|q| q + offset_lhs).collect();
                (new_input, new_output)
            });

        let rhs_transitions = rhs.transitions.into_iter()
            .map(|((q_old, c), qs_new)| {
                let new_input = (q_old + offset_rhs, c);
                let new_output = qs_new.into_iter().map(|q| q + offset_rhs).collect();
                (new_input, new_output)
            });
        
        Self {
            num_states: lhs.num_states + rhs.num_states + 2,
            transitions: HashMap::from_iter(
                new_transitions.chain(lhs_transitions).chain(rhs_transitions)
            )
        }
    }

    fn from_star(inner: Self) -> Self {
        const INNER_OFFSET: usize = 2;
        
        let new_transitions = [
            ((0, '\0'), vec![1, INNER_OFFSET]),
            ((INNER_OFFSET + 1, '\0'), vec![INNER_OFFSET, 1]),
        ].into_iter();

        let inner_transitions = inner.transitions.into_iter()
            .map(|((q_old, c), qs_new)| {
                let new_input = (q_old + INNER_OFFSET, c);
                let new_output = qs_new.into_iter().map(|q| q + INNER_OFFSET).collect();
                (new_input, new_output)
            });

        Self {
            num_states: inner.num_states + 2,
            transitions: HashMap::from_iter(
                new_transitions.chain(inner_transitions)
            )
        }
    }

    fn from_plus(inner: Self) -> Self {
        const INNER_OFFSET: usize = 2;
        
        let new_transitions = [
            ((0, '\0'), vec![INNER_OFFSET]),
            ((INNER_OFFSET + 1, '\0'), vec![INNER_OFFSET, 1]),
        ].into_iter();

        let inner_transitions = inner.transitions.into_iter()
            .map(|((q_old, c), qs_new)| {
                let new_input = (q_old + INNER_OFFSET, c);
                let new_output = qs_new.into_iter().map(|q| q + INNER_OFFSET).collect();
                (new_input, new_output)
            });

        Self {
            num_states: inner.num_states + 2,
            transitions: HashMap::from_iter(
                new_transitions.chain(inner_transitions)
            )
        }
    }
}