Minimization Algorithm

pub fn minimize(&self) -> Self {
        // table filling algorithm

        // 1. Remove unreachable states
        let mut reachable_states = HashSet::new();
        reachable_states.insert(self.starting_state.clone());

        for state in &self.states {
            for symbol in &self.alphabet {
                if let Some(out_state) = (self.transition_function)(state.clone(), symbol.clone()) {
                    reachable_states.insert(out_state);
                }
            }
        }

        // 2. Mark final AND non-final states
        let mut mark_table = Table::new();
        for state1 in &reachable_states {
            for state2 in &reachable_states {
                let is_final1 = self.final_states.contains(state1);
                let not_is_final2 = !self.final_states.contains(state2);
                mark_table.set(state1.id, state2.id, is_final1 && not_is_final2);
            }
        }

        // Some states in the upper triangle maybe marked, could potentially be harmful to the algorithm
        mark_table.drop(|key1, key2, _| {
            key2 >= key1
        });

        // 3. Mark pairs of states
        loop {
            let mut has_marked = false;

            // for all pairs of states (p, q) in reachable_states X alphabet
            for state1 in &reachable_states {
                for state2 in &reachable_states {
                    if *mark_table.get(&state1.id, &state2.id).unwrap() {
                        continue;
                    }

                    for symbol in &self.alphabet {
                        // if (s1, s2) where s1 = delta(p, a) and s2 = delta(q, a) is marked
                        // then mark (p, q)

                        let out_state1 = (self.transition_function)(state1.clone(), symbol.clone());
                        let out_state2 = (self.transition_function)(state2.clone(), symbol.clone());

                        if let (Some(out_state1), Some(out_state2)) = (out_state1, out_state2) {
                            if *mark_table.get(&out_state1.id, &out_state2.id).unwrap() {
                                mark_table.set(state1.id, state2.id, true);
                                has_marked = true;
                            }
                        }
                    }
                }
            }

            mark_table.drop(|key1, key2, _| {
                key2 >= key1
            });

            if !has_marked {
                break;
            }
        }

        // 4. Create equivalence classes
        let mut equivalence_classes = Vec::new();
        let mut available_states = reachable_states.clone();

        while !available_states.is_empty() {
            let state = available_states.iter().next().unwrap().clone();

            let mut equivalence_class = HashSet::new();
            equivalence_class.insert(state.clone());

            for state2 in &available_states {
                if !mark_table.get(&state.id, &state2.id).unwrap() {
                    equivalence_class.insert(state2.clone());
                }
            }

            equivalence_classes.push(equivalence_class.clone());
            available_states = available_states.difference(&equivalence_class).cloned().collect();
        }

        let dfa_states = st_range_hash!(0..(equivalence_classes.len() as u32));
        let dfa_initial_state = equivalence_classes
            .iter()
            .position(|equivalence_class| equivalence_class.contains(&self.starting_state))
            .unwrap();
        let dfa_final_states = equivalence_classes
            .iter()
            .enumerate()
            .filter(|(_, equivalence_class)| 
                equivalence_class
                .iter()
                .any(|state| self.final_states.contains(state)))
            .map(|(i, _)| State::new(i as u32))
            .collect::<HashSet<_>>();

        let mut dfa_transition_function = Table::new();
        
        for equivalence_class in &equivalence_classes {
            for symbol in &self.alphabet {
                // pick a state from the equivalence class
                let state = equivalence_class.iter().next().unwrap().clone();

                // find delta[state, symbol]
                let out_state = (self.transition_function)(state.clone(), symbol.clone());
                // ? is it guaranteed that out_state is always a Some()?
                let out_state = out_state.unwrap();

                // find the equivalence class of out_state
                let out_equivalence_class = equivalence_classes
                    .iter()
                    .find(|equivalence_class| equivalence_class.contains(&out_state))
                    .unwrap();

                // find the index of the equivalence class
                let out_equivalence_class_index = equivalence_classes
                    .iter()
                    .position(|equivalence_class| equivalence_class == out_equivalence_class)
                    .unwrap();

                // set the transition function
                dfa_transition_function.set(state.id, symbol.symbol.clone(), Some(out_equivalence_class_index as u32));
            }
        }

        Self {
            states: dfa_states,
            alphabet: self.alphabet.clone(),
            starting_state: State::new(dfa_initial_state as u32),
            final_states: dfa_final_states,
            transition_function: transition_function_from_table(dfa_transition_function),
        }
    }