Trie Autocomplete with Ranked Results

use std::collections::HashMap;

#[derive(Default)]
struct Node {
    children: HashMap<char, Node>,
    weight: Option<u32>,
}

struct Trie {
    root: Node,
}

impl Trie {
    fn new() -> Self {
        Self {
            root: Node::default(),
        }
    }

    fn insert(&mut self, word: &str, weight: u32) {
        let mut node = &mut self.root;
        for character in word.chars() {
            node = node.children.entry(character).or_default();
        }
        node.weight = Some(weight);
    }

    fn complete(&self, prefix: &str, limit: usize) -> Vec<(String, u32)> {
        if limit == 0 {
            return Vec::new();
        }
        let mut node = &self.root;
        for character in prefix.chars() {
            match node.children.get(&character) {
                Some(next) => node = next,
                None => return Vec::new(),
            }
        }

        let mut matches = Vec::new();
        collect(node, prefix.to_string(), &mut matches);
        matches.sort_by(|left, right| {
            right
                .1
                .cmp(&left.1)
                .then_with(|| left.0.cmp(&right.0))
        });
        matches.truncate(limit);
        matches
    }
}

fn collect(node: &Node, prefix: String, matches: &mut Vec<(String, u32)>) {
    if let Some(weight) = node.weight {
        matches.push((prefix.clone(), weight));
    }
    for (character, child) in &node.children {
        collect(child, format!("{prefix}{character}"), matches);
    }
}

fn main() {
    let mut trie = Trie::new();
    for (word, weight) in [
        ("rust", 10),
        ("runner", 7),
        ("runtime", 5),
        ("ruby", 3),
        ("go", 9),
    ] {
        trie.insert(word, weight);
    }
    println!("{:?}", trie.complete("ru", 3));
    println!("{:?}", trie.complete("xyz", 3));
}