I've been writing an algorithm for creating DAWG data structures in an online fashion (more about that in paper "Incremental Construction of Minimal Acyclic Finite-State Automata" by Jan Daciuk & al.).
I've implemented the algorithm in C and arriving at the end the problem I had is memory not getting properly freed because of joint nodes in my DAFSA. Anyway, I'm now trying to implement that in Rust because I know that I can have smart pointers like Rc that will do the trick.
So here are my structs:
type SharedDawgState = Rc<RefCell<DawgState>>;
struct DawgState {
transitions: BTreeMap<char, SharedDawgState>
//...
}
struct Dawg {
start: SharedDawgState,
//...
}
This works pretty much as a Trie, I start that Dawg.start
and follow the transitions in DawgState
. So, to get the longest prefix of a string that is already in the Trie, I do the following:
fn common_prefix(&self, word: &String) -> Option<String> {
if (*self.start).as_ptr().is_null() {
return None;
}
let mut current = self.start.as_ptr();
let mut prefix = String::from("");
for c in word.chars() {
unsafe {
if !(*current).transitions.contains_key(&c) {
break;
}
current = (*current).transitions.get(&c)?.as_ptr();
}
prefix.push(c);
}
Some(prefix)
}
But in my opinion this looks weird. I cannot say if I'm being influenced by the way I write C code (following a pointer through) or if this is a common way to use the Rc<RefCell<>>
.
So, I wanted to know if there is a safe way to go down this Trie and access the ShareDawgState
so that I can either do something like common_prefix
or simply return a reference to the Trie node.