Autocomplete

use trie.qweruse trie_add, trie_complete from trie      // Quillo 0.6: only these

// City type-ahead for a search box: the most populous matches first, with an id to link to.////   quillo run trie.qwe      then open http://localhost:8080/complete?q=sanuse "trie.qwer"let cities = [    { text: "San Francisco", weight: 808, data: { id: 1 } }, { text: "San Diego", weight: 1386, data: { id: 2 } },    { text: "San Jose", weight: 971, data: { id: 3 } }, { text: "Santa Fe", weight: 88, data: { id: 4 } },    { text: "New York", weight: 8258, data: { id: 5 } }, { text: "York", weight: 210, data: { id: 6 } },    { text: "Sacramento", weight: 525, data: { id: 7 } }, "Salem",]fn index() = trie_add("cities", cities)?route GET /complete ? { q: str, n: int = 5 } {    if !trie_has("cities", "San Diego") { index() }    trie_complete("cities", q, n, false) | map((c) => { city: c.text, id: c.data?.id })}route GET /anyword ? { q: str = "york" } {    if !trie_has("cities", "San Diego") { index() }    trie_complete("cities", q, 5, true) | map((c) => c.text)}

//! A prefix index for autocomplete and type-ahead, kept in memory by name for all requests: words or phrases added with a weight, the best completions of what was typed found in microseconds.//! version: 1.0.0//!//! [dependencies]use serde_json::{json, Value};use std::collections::{BTreeMap, HashMap};use std::sync::Mutex;/// An index: each entry's key (folded to lower case) to its text as given and its weight. A/// BTreeMap keeps keys in order, so the keys with a prefix are one range of it.#[derive(Default)]struct Index {    entries: BTreeMap<String, (String, f64, Value)>,}static INDEXES: Mutex<Option<HashMap<String, Index>>> = Mutex::new(None);fn fold(s: &str) -> String {    s.trim().to_lowercase().split_whitespace().collect::<Vec<_>>().join(" ")}/// Adds entries to the index `name` (made on first use; up to 1,000 indexes and a million entries each): each a map `{ text, weight, data }`, or plain text with weight 1. `weight` ranks completions (popularity, sales); `data` (any value, such as an id or a URL) comes back with them. An entry already there is replaced. Gives the index's size.pub fn trie_add(name: &str, entries: Vec<serde_json::Value>) -> Result<i64, String> {    if entries.len() > 100_000 {        return Err("up to 100,000 entries a call".into());    }    let mut g = INDEXES.lock().unwrap_or_else(|e| e.into_inner());    let all = g.get_or_insert_with(HashMap::new);    if !all.contains_key(name) && all.len() >= 1000 {        return Err("up to 1,000 indexes: trie_clear old ones".into());    }    let idx = all.entry(name.to_string()).or_default();    for e in entries {        let (text, weight, data) = match e {            Value::String(s) => (s, 1.0, Value::Null),            Value::Object(m) => (                m.get("text").and_then(|t| t.as_str()).ok_or("each entry is text, or a map with text")?.to_string(),                m.get("weight").and_then(|w| w.as_f64()).unwrap_or(1.0),                m.get("data").cloned().unwrap_or(Value::Null),            ),            _ => return Err("each entry is text, or a map with text".into()),        };        let key = fold(&text);        if key.is_empty() || key.len() > 1000 {            continue;        }        if idx.entries.len() >= 1_000_000 && !idx.entries.contains_key(&key) {            return Err("up to a million entries an index".into());        }        idx.entries.insert(key, (text, weight, data));    }    Ok(idx.entries.len() as i64)}/// The best `limit` completions (up to 100) of `prefix` in index `name`, as `[{ text, weight, data }]`, heaviest first, then in alphabetical order. Case and repeated spaces are ignored; a prefix also matches the start of a later word ("york" finds "New York") when `any_word` is true.pub fn trie_complete(name: &str, prefix: &str, limit: i64, any_word: bool) -> Vec<Value> {    let g = INDEXES.lock().unwrap_or_else(|e| e.into_inner());    let Some(idx) = g.as_ref().and_then(|a| a.get(name)) else { return vec![] };    let p = fold(prefix);    let n = limit.clamp(0, 100) as usize;    let mut hits: Vec<&(String, f64, Value)> = if any_word && !p.is_empty() {        // Every entry with a word starting with the prefix: a scan, fine for tens of thousands.        idx.entries.iter().filter(|(k, _)| k.starts_with(&p) || k.contains(&format!(" {}", p))).map(|(_, v)| v).collect()    } else {        idx.entries.range(p.clone()..).take_while(|(k, _)| k.starts_with(&p)).map(|(_, v)| v).collect()    };    hits.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal).then_with(|| a.0.cmp(&b.0)));    hits.into_iter().take(n).map(|(t, w, d)| json!({ "text": t, "weight": w, "data": d })).collect()}/// Whether index `name` holds exactly `text` (case and spaces ignored).pub fn trie_has(name: &str, text: &str) -> bool {    let g = INDEXES.lock().unwrap_or_else(|e| e.into_inner());    g.as_ref().and_then(|a| a.get(name)).map_or(false, |i| i.entries.contains_key(&fold(text)))}/// Takes `text` out of index `name`; whether it was there.pub fn trie_remove(name: &str, text: &str) -> bool {    let mut g = INDEXES.lock().unwrap_or_else(|e| e.into_inner());    g.as_mut().and_then(|a| a.get_mut(name)).map_or(false, |i| i.entries.remove(&fold(text)).is_some())}/// Forgets index `name` and all its entries.pub fn trie_clear(name: &str) {    if let Some(a) = INDEXES.lock().unwrap_or_else(|e| e.into_inner()).as_mut() {        a.remove(name);    }}