Rate my solution to >>68704428
#![feature(nll)]
use std::io::{self, BufRead};
use std::cmp;
#[derive(Clone, Default)]
struct Node {
c: char,
valid: bool,
nodes: Vec<Node>,
}
impl Node {
fn insert(&mut self, s: &str) {
let mut curr = self;
let mut chars = s.chars();
let mut index = 0;
let mut saved = None;
for c in chars.by_ref() {
match curr.nodes.binary_search_by_key(&c, |v| v.c) {
Ok(i) => curr = &mut curr.nodes[i],
Err(i) => {
saved = Some(c);
index = i;
break;
}
}
}
for c in saved.iter().cloned().chain(chars) {
curr.nodes.insert(index, Node { c, ..Default::default() });
curr = &mut curr.nodes[index];
index = 0;
}
curr.valid = true;
}
fn merge(&mut self, other: &Node) {
for c in other.nodes.iter() {
match self.nodes.binary_search_by_key(&c.c, |v| v.c) {
Ok(i) => {
if c.valid {
self.nodes[i].valid = true;
}
self.nodes[i].merge(&c);
},
Err(i) => self.nodes.insert(i, c.clone()),
}
}
}
fn add_xform(&mut self, xform: &(char, char)) {
let (o, n) = xform;
for c in self.nodes.iter_mut() {
c.add_xform(xform);
}
let old = self.nodes.binary_search_by_key(o, |v| v.c);
let new = self.nodes.binary_search_by_key(n, |v| v.c);
match (old, new) {
(Ok(i), Err(j)) => {
let mut node = self.nodes[i].clone();
node.c = *n;
self.nodes.insert(j, node);
},
(Ok(i), Ok(j)) => {
let (l, r) = self.nodes.split_at_mut(cmp::max(i, j));
let (o, n) = if i < j { (&l[i], &mut r[0]) } else { (&r[0], &mut l[j]) };
n.merge(o);
},
_ => {},
}
}
fn print_r(&self, buf: &mut String) {
if self.valid {
println!("{}", buf);
}
for c in self.nodes.iter() {
buf.push(c.c);
c.print_r(buf);
buf.pop();
}
}
fn print(&self) {
let mut buf = String::new();
self.print_r(&mut buf);
}
}
This barely can't fit in a single 4chan post, so I'll post the main function separately.