automaton

commit f1dea359d2176a141bd7e9895aa183a24b723a87
parent 994f86650d03433ed3ca4ec9c649c335eee25f96
Author: Ethan Long <ethan@Ethans-MacBook-Pro.local>
Date:   Wed, 29 Nov 2023 16:26:43 +1100

Aquired the ability to print NFA's transition tables!

Diffstat:
M
src/bin/dfa.rs
 | 
2
+-
M
src/bin/nfa.rs
 | 
4
++--
M
src/lib/nfa.rs
 | 
48
++++++++++++++++++++++++++++++++++++++++++++++--

3 files changed, 49 insertions(+), 5 deletions(-)
diff --git a/src/bin/dfa.rs b/src/bin/dfa.rs
@@ -41,7 +41,7 @@ fn main() -> Result<(), Box<dyn Error>> {
         .ok_or(CommandLineError::cause("No input string provided!"))?;
 
     let dfa: DFA = DFA::parse(dfa_json.as_str())?;
-    println!("DFA:\n{dfa}\n");
+    println!("DFA:\n{dfa}");
     println!("Running on the following input:\n{input_string}");
     println!("Accepts: {}", dfa.accepts(input_string));
 
diff --git a/src/bin/nfa.rs b/src/bin/nfa.rs
@@ -41,12 +41,12 @@ fn main() -> Result<(), Box<dyn Error>> {
         .ok_or(CommandLineError::cause("No input string provided!"))?;
 
     let nfa: NFA = NFA::parse(nfa_json.as_str())?;
-    println!("NFA:\n{nfa}\n");
+    println!("NFA:\n{nfa}");
     println!("Running on the following input:\n{input_string}");
     println!("Accepts: {}", nfa.accepts(input_string));
     let dfa: DFA = DFA::convert(Box::new(nfa))?;
     println!("Converted to DFA, accepts: {}", dfa.accepts(input_string));
-    println!("DFA:\n{dfa}\n");
+    println!("DFA:\n{dfa}");
 
     Ok(())
 }
diff --git a/src/lib/nfa.rs b/src/lib/nfa.rs
@@ -191,6 +191,7 @@ impl FiniteStateAutomaton for NFA {
 }
 
 impl Display for NFA {
+    // FIXME: This is incomplete
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         let mut alphabet_vec: Vec<char> = self.alphabet.iter().copied().collect();
         let mut states_vec: Vec<u64> = self.states.iter().copied().collect();
@@ -225,6 +226,8 @@ impl Display for NFA {
                 format!("{str}{c}{ending}")
             });
 
+        let initial_state_str: String = self.initial_state.to_string();
+
         let final_states_str =
             final_states_vec
                 .iter()
@@ -238,9 +241,50 @@ impl Display for NFA {
                     format!("{str}{c}{ending}")
                 });
 
-        let initial_state_str: String = self.initial_state.to_string();
+        let transition_table_hdr: String = alphabet_vec
+            .iter()
+            .map(|c| format!("\t{c}\t|"))
+            .fold("\t|".to_owned(), |str, substr| format!("{str}{substr}"));
+
+        let mut transition_map: HashMap<u64, Vec<Vec<u64>>> = HashMap::new();
+
+        let index_map: HashMap<char, usize> = alphabet_vec
+            .iter()
+            .enumerate()
+            .map(|(index, char)| (char.to_owned(), index))
+            .collect();
+
+        for ((from, input), to) in self.transition_table.iter() {
+            let mut new_vec: Vec<Vec<u64>> = transition_map
+                .get(from)
+                .unwrap_or(&vec![Vec::new(); self.alphabet.len()])
+                .to_owned();
+            let new_index = index_map.get(&input).ok_or(fmt::Error)?;
+            new_vec[*new_index] = to.to_owned();
+            transition_map.insert(from.to_owned(), new_vec);
+        }
+
+        let transition_table_str: String =
+            transition_map
+                .iter()
+                .fold(transition_table_hdr, |str, (input, state_sets)| {
+                    let dests = state_sets.into_iter().fold("".to_owned(), |acc, dsts| {
+                        let dest_sets_str: String = if dsts.len() == 0 {
+                            "∅".to_owned()
+                        } else {
+                            dsts.iter()
+                                .enumerate()
+                                .fold("{".to_owned(), |acc, (index, dst)| {
+                                    let end = if index == dsts.len() - 1 { "}" } else { ", " };
+                                    format!("{}{}{}", acc, dst, end)
+                                })
+                        };
+                        format!("{acc}{}\t|\t", dest_sets_str)
+                    });
+                    format!("{str}\n{input}\t|\t{dests}")
+                });
 
-        writeln!(f, "Alphabet: {alphabet_str}\nStates: {states_str}\nInitial State: {initial_state_str}\nFinal States: {final_states_str}")
+        writeln!(f, "Alphabet: {alphabet_str}\nStates: {states_str}\nInitial State: {initial_state_str}\nFinal States: {final_states_str}\nTransition Table:\n{transition_table_str}")
     }
 }