トライ木 in Rust

trie.rs

use std::{collections::VecDeque, process::id};

struct ValueNode {
    value: char,
    child_nodes: Vec<Box<ValueNode>>,
    is_leaf: bool,
    pos: usize,
}

impl ValueNode {
    fn new(value: char) -> Self {
        ValueNode {
            value,
            child_nodes: Vec::<Box<ValueNode>>::new(),
            is_leaf: false,
            pos: 0,
        }
    }

    fn print(&self) {
        let mut queue = VecDeque::<&Box<ValueNode>>::new();
        for node in self.child_nodes.iter() {
            queue.push_back(node);
        }
        let mut words = Vec::<(usize, Vec<char>)>::new();
        let mut acc = Vec::<char>::new();
        let mut shift = 0;
        while !queue.is_empty() {
            let back = queue.pop_back().unwrap();
            for node in back.child_nodes.iter() {
                queue.push_back(node);
            }
            if acc.is_empty() {
                shift = back.pos;
            }
            acc.push(back.value);
            if back.is_leaf {
                words.push((shift, acc.clone()));
                acc.clear();
                shift = 0;
            }
        }
        for (shift, word) in words.iter() {
            for _ in 0..*shift {
                print!(" ");
            }
            for c in word.iter() {
                print!("{}", c);
            }
            println!();
        }
    }
}

fn build(word: &str, idx: usize, node: &mut Box<ValueNode>) {
    if word.len() <= idx {
        return;
    }
    for child_node in node.child_nodes.iter_mut() {
        if child_node.value == word.chars().nth(idx).unwrap() {
            build(word, idx + 1, child_node);
            return;
        }
    }
    let mut new_node = Box::new(ValueNode::new(word.chars().nth(idx).unwrap()));
    if idx == word.len()-1 {
        new_node.is_leaf = true;
    }
    new_node.pos = idx;
    &mut node.child_nodes.push(new_node);
    build(word, idx+1, node.child_nodes.last_mut().unwrap());
}

fn build_trie(words: Vec<&str>) -> Box<ValueNode> {
    let mut root_node = Box::new(ValueNode::new('o'));
    for word in words.iter() {
        build(word, 0, &mut root_node);
    }
    root_node
}

fn main() {
    let words = &[
        "gomi",
        "unko",
        "unkoooooooooooooooo",
    ];
    let trie = build_trie(words.to_vec());
    trie.print();
}