I have the following C++ code:
#include <vector>
#include <string>
using namespace std;
struct Trie {
bool eow; //end of word
char val;
vector<Trie> chd; //children
void push_word(const string& word){
Trie& trie = *this;
for (char c: word){
if (trie.chd.empty() || trie.chd.back().val != c) {
trie.chd.push_back(Trie{false, c, vector<Trie>{}});
}
trie = trie.chd.back();
}
trie.eow = true;
}
};
It's a trie for strings. push_word
is supposed to only accept strings that are lexicographically greater than any word already contained in the trie; this way the search for the correct child can be skipped at each node. In other words, this allows us to efficiently construct a trie from a sorted vector of words:
Trie from_sorted_vector(const vector<string>& words){
Trie trie{false, '\0', vector<Trie>{}};
for (const auto& word: words) {
trie.push_word(word);
}
return trie;
}
I have the following in Rust:
#[derive(Eq, PartialEq, Debug, Clone)]
struct Trie {
eow: bool,
val: char,
chd: Vec<Trie>,
}
impl Trie {
fn new(eow: bool, val: char, chd: Vec<Trie>) -> Trie {
Trie {
eow: eow,
val: val,
chd: chd,
}
}
fn push_word(&mut self, word: &String) {
let mut trie = self;
for c in word.chars() {
// ???
}
}
}
I can't implement push_word
in an analogous manner to C++. I always get two mutable borrows or one immutable and one mutable borrow, for trie
or trie.chd
, or the last element of trie.chd
. I'd like to get some directions as to how this should be done.