code wiki / _hdl_build / nx_prefix.nx
nx_prefix.nx source
↩ module page · 49 lines · 2172 B
1// nx_prefix.nx -- R-UX-3 of the onsite-search S-class ladder: SOVEREIGN instant / as-you-type prefix
2// autocomplete (LIBRARY). Typing "div" should instantly suggest "divorce" (cited srch_elastic.raw: autocomplete).
3// Sorted vocab + binary-search lower bound -> the matching terms are a CONTIGUOUS run, so suggest is O(log n + k),
4// not O(n) -- that's what makes it "instant" at vocab scale. Deterministic, integer, no third party.
5//
6// exports: vr_prefix_match, vr_prefix_lower, vr_prefix_collect. license_tier: ORIGINAL
7import "nx_syscalls.nx"
8
9func px_len(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} return n }
10
11// does NUL-terminated `term` start with the first `pl` chars of `pre`?
12func vr_prefix_match(term: *u8, pre: *u8, pl: i64) -> i64 {
13 var i: i64=0
14 while i<pl { if term[i]==(0 as u8) { return 0 } if term[i]!=pre[i] { return 0 } i=i+1 }
15 return 1
16}
17
18// lexicographic compare of NUL-terminated a vs the first `pl` chars of `pre`: <0,0,>0 (a treated up to pl)
19func px_cmp_pre(a: *u8, pre: *u8, pl: i64) -> i64 {
20 var i: i64=0
21 while i<pl {
22 let ca: i64=a[i] as i64
23 if ca==0 { return 0-1 } // a shorter than prefix -> a < pre
24 let cp: i64=pre[i] as i64
25 if ca<cp { return 0-1 }
26 if ca>cp { return 1 }
27 i=i+1
28 }
29 return 0 // a starts with pre
30}
31
32// binary-search lower bound: smallest index whose term is NOT < prefix. terms = *i64 of *u8 (sorted).
33func vr_prefix_lower(terms: *i64, n: i64, pre: *u8, pl: i64) -> i64 {
34 var lo: i64=0; var hi: i64=n
35 while lo<hi {
36 let mid: i64=(lo+hi)/2
37 let t: *u8=terms[mid] as *u8
38 if px_cmp_pre(t, pre, pl) < 0 { lo=mid+1 } else { hi=mid }
39 }
40 return lo
41}
42
43// collect indices of terms starting with `pre` into out[]; returns count. O(log n + k) via lower bound + run.
44func vr_prefix_collect(terms: *i64, n: i64, pre: *u8, pl: i64, out: *i64) -> i64 {
45 var i: i64=vr_prefix_lower(terms, n, pre, pl)
46 var m: i64=0
47 while i<n { let t: *u8=terms[i] as *u8; if vr_prefix_match(t, pre, pl)==1 { out[m]=i; m=m+1; i=i+1 } else { i=n } }
48 return m
49}