我想为整数索引序列实现一个trie。为了提高效率，重要的是节点的子节点通过索引序列而不是某种映射与节点相关联。为了说明这个基本思想，下面是Ruby中的一个实现：
require 'virtus'
class TrieNode
include Virtus.model
attribute :terminal, Boolean, default: false
attribute :children, Array, default: []
def add(i, vec)
if i == vec.length
terminal = true
else
( children[vec[i]] ||= TrieNode.new ).add i + 1, vec
end
end
end
Perl中也有相同的东西：
package TrieNode;
use Moo;
has terminal => ( is => 'rw' );
has children => ( is => 'ro', default => sub { [] } );
sub add {
my ( $self, $i, $vec ) = @_;
if ( $i == @$vec ) {
$self->terminal(1);
}
else {
( $self->children->[ $vec->[$i] ] //= TrieNode->new )->add( ++$i, $vec );
}
}
'wheee!!!';
以下是我在Rust:中实现这一点的各种尝试之一
struct TrieNode {
children: Vec<Option<TrieNode>>,
terminal: bool
}
impl TrieNode {
fn new() -> TrieNode { TrieNode { children: vec![], terminal: false } }
fn add(&mut self, i: usize, s: &Vec<usize>) {
if s.len() == i {
self.terminal = true;
} else {
let j = s[i];
let k = j - 1;
let ref mut c = self.children;
while c.len() < k {
c.push(None);
}
if c.len() < j {
let mut n = TrieNode::new();
n.add( i + 1, s );
c.push(Some(n));
} else {
let ref o = c[j];
match o {
Some(ref mut n) => {
n.add( i + 1, s );
},
None => {
let mut n = TrieNode::new();
n.add( i + 1, s );
c.remove(j);
c.insert(j, Some(n));
}
}
}
}
}
}
值得一提的是，以下是该尝试的编译错误：
file_toy (master #) $ cargo build
Compiling file_toy v0.1.0 (file:///Users/houghton/playground/file_toy)
src/main.rs:27:21: 27:36 error: mismatched types:
expected `&_`,
found `core::option::Option<_>`
(expected &-ptr,
found enum `core::option::Option`) [E0308]
src/main.rs:27 Some(ref mut n) => {
^~~~~~~~~~~~~~~
src/main.rs:27:21: 27:36 help: run `rustc --explain E0308` to see a detailed explanation
src/main.rs:30:21: 30:25 error: mismatched types:
expected `&_`,
found `core::option::Option<_>`
(expected &-ptr,
found enum `core::option::Option`) [E0308]
src/main.rs:30 None => {
^~~~
src/main.rs:30:21: 30:25 help: run `rustc --explain E0308` to see a detailed explanation
src/main.rs:28:27: 28:30 error: the type of this value must be known in this context
src/main.rs:28 n.add( i + 1, s );
^~~
error: aborting due to 3 previous errors
error: Could not compile `file_toy`.
它的预期用途是它的Rust实现。trie一旦充满了序列，就将是不可变的，并将在程序的整个生命周期中存在。我这样做是为了学习Rust，所以你越能击倒我的愚蠢越好。谢谢
您的控制流有点复杂，并且有很多嵌套。通过减少嵌套和展开控制流，我们可以得到更美味的东西。我也希望避免所有的冗余。
#[derive(Clone, Debug, Default)]
struct TrieNode {
children: Vec<Option<TrieNode>>,
terminal: bool
}
impl TrieNode {
pub fn add(&mut self, element: &[usize]) {
if element.len() == 0 {
self.terminal = true;
return;
}
let ref mut c = self.children;
let value = element[0];
// Ensure there is at least "value" children
if c.len() < value { c.resize(value, None); }
// Ensure the "value"th child is a full TrieNode
if c[value - 1].is_none() {
c[value - 1] = Some(TrieNode::default());
}
c[value - 1].as_mut().unwrap().add(&element[1..]);
}
}
fn main() {
let mut t = TrieNode::default();
t.add(&[1, 2]);
println!("{:?}", t);
}
令人讨厌的比特是add的后6行。match在概念上更优雅，但是您不能在match期间借用c[value - 1]并在None分支中修改它，因为借用检查不是"路径感知"的，而是"范围感知"的（这一限制将来可能会取消，但我们现在必须应对）。
建议：
- 尽可能多地检查现有方法。例如，使用
Vec::resize而不是while循环可以更准确地传达意图 - 检查现有特性，当
new()不带参数时，最好实现Default特性（打开更多的门）；此外，Default可以定期派生，这样您甚至不必键入它 - 当不需要
String/Vec的所有权时，请使用切片。除了使代码更通用（任何对切片不可引用的类型都可以使用）之外，这里我们还受益于索引符号[1..]，它可以廉价地截断第一个元素，从而避免携带额外的索引
所有这些都会使代码变得更短，而更少的代码通常意味着错误进入的机会更少。尤其是在避免重复的情况下。
另一方面，如果你愿意为儿童使用HashMap或BTreeMap，你可以免费获得"稀疏性"和更容易的添加方法。例如，用use std::collections::HashMap:修订的add方法
impl TrieNode {
pub fn add(&mut self, element: &[usize]) {
if element.len() == 0 {
self.terminal = true;
return;
}
self.children
.entry(element[0])
.or_insert(TrieNode::default())
.add(&element[1..]);
}
}
很多，很多，更简单，不是吗？
错误表明o是引用（&），但您匹配的是Option值（不是引用）。
如果添加一个引用（&Some(ref mut n)），您将得到另一个错误，因为您正在获取对n的可变引用，但o是不可变的。
如果使o可变（let o = &mut c[j]），则无法更改None分支中的c，因为o具有c的可变借用。
一种解决方案是取得c[j]的所有权（这会很烦人如果c值不是Option），并在Some分支中将其返回。
impl TrieNode {
fn new() -> TrieNode { TrieNode { children: vec![], terminal: false } }
fn add(&mut self, i: usize, s: &Vec<usize>) {
if s.len() == i {
self.terminal = true;
} else {
let j = s[i];
let k = j - 1;
let ref mut c = self.children;
while c.len() < k {
c.push(None);
}
if c.len() < j {
let mut n = TrieNode::new();
n.add( i + 1, s );
c.push(Some(n));
} else {
match c[j].take() {
Some(mut n) => {
n.add( i + 1, s );
c[j] = Some(n)
},
None => {
let mut n = TrieNode::new();
n.add( i + 1, s );
c[j] = Some(n);
}
}
}
}
}
}