Something went wrong. Try again.
forked from evanpurkhiser/things3-cloud
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253use std::collections::HashMap;
use crate::ids::{ThingsId, things_id::base58_encode_fixed};
/// the shortest unique prefix of every id////// each id is encoded once into a stack buffer/// the sort and the common prefix scan run on byte slices/// only the result allocates a string per entry/// duplicate ids in the input collapse into one entrypub fn shortest_unique_prefixes(ids: &[ThingsId]) -> HashMap<ThingsId, String> { if ids.is_empty() { return HashMap::new(); }
let mut pairs: Vec<(ThingsId, [u8; 22], usize)> = ids .iter() .map(|id| { let (buf, len) = base58_encode_fixed(id.as_bytes()); (id.clone(), buf, len) }) .collect(); pairs.sort_unstable_by(|a, b| a.1[..a.2].cmp(&b.1[..b.2]));
let n = pairs.len(); let mut result = HashMap::with_capacity(n); for i in 0..n { let enc = &pairs[i].1[..pairs[i].2]; let left = if i > 0 { lcp_len_bytes(enc, &pairs[i - 1].1[..pairs[i - 1].2]) } else { 0 }; let right = if i + 1 < n { lcp_len_bytes(enc, &pairs[i + 1].1[..pairs[i + 1].2]) } else { 0 }; // one character past the shared prefix // clamped to the full encoding // when one encoding is a prefix of another, the whole string is the shortest unique prefix let need = (left.max(right) + 1).min(pairs[i].2); let prefix = std::str::from_utf8(&enc[..need]) .expect("base58 output must be ASCII") .to_owned(); result.insert(pairs[i].0.clone(), prefix); }
result}
/// the width that shows every id of a group unique, the longest of their shortest unique prefixespub fn longest_shortest_unique_prefix_len(ids: &[ThingsId]) -> usize { if ids.is_empty() { return 0; }
shortest_unique_prefixes(ids) .values() .map(|s| s.len()) .max() .unwrap_or(1)}
#[inline]fn lcp_len_bytes(a: &[u8], b: &[u8]) -> usize { let max = a.len().min(b.len()); for i in 0..max { if a[i] != b[i] { return i; } } max}
/// every id whose base58 form starts with `prefix`, in the order given////// ids sorted by their bytes stop being contiguous by textual prefix once their encoded lengths differ/// the whole list is therefore scanned rather than stopped at the first miss after a matchpub fn prefix_matches<'a>(sorted_ids: &'a [ThingsId], prefix: &str) -> Vec<&'a ThingsId> { let prefix = prefix.as_bytes(); if prefix.is_empty() { return sorted_ids.iter().collect(); }
sorted_ids .iter() .filter(|id| { let (buf, len) = base58_encode_fixed(id.as_bytes()); buf[..len].starts_with(prefix) }) .collect()}
#[cfg(test)]mod tests { use super::*;
#[test] fn shortest_unique_prefixes_are_actually_unique() { // every prefix of a random set matches exactly one of its ids let ids: Vec<ThingsId> = (0..200).map(|_| ThingsId::random()).collect(); let prefixes = shortest_unique_prefixes(&ids);
assert_eq!(prefixes.len(), ids.len());
for (id, prefix) in &prefixes { let matches: Vec<&ThingsId> = ids .iter() .filter(|other| other.to_string().starts_with(prefix.as_str())) .collect(); assert_eq!( matches.len(), 1, "prefix {:?} for {:?} matched {} IDs: {:?}", prefix, id.to_string(), matches.len(), matches.iter().map(|m| m.to_string()).collect::<Vec<_>>() ); assert_eq!(matches[0], id); } }
#[test] fn shortest_unique_prefixes_are_minimal() { // every prefix is minimal // one character less matches more than one id let ids: Vec<ThingsId> = (0..200).map(|_| ThingsId::random()).collect(); let prefixes = shortest_unique_prefixes(&ids);
for prefix in prefixes.values() { if prefix.len() <= 1 { continue; // can't shorten a 1-char prefix } let shorter = &prefix[..prefix.len() - 1]; let matches: Vec<&ThingsId> = ids .iter() .filter(|other| other.to_string().starts_with(shorter)) .collect(); assert!( matches.len() > 1, "prefix {:?} is not minimal, {:?} is one char shorter and still matches 1 ID alone", prefix, shorter ); } }
#[test] fn every_id_with_the_prefix_is_found_whatever_its_encoded_length() { // byte order puts both 21 character ids before the 22 character one // that order separates the two ids starting with A by the one starting with z let short_a = "A11111111111111111111"; let short_z = "z11111111111111111111"; let long_a = "A111111111111111111111"; let mut sorted: Vec<ThingsId> = [short_a, short_z, long_a] .iter() .map(|id| id.parse().expect("a valid id")) .collect(); sorted.sort(); assert_eq!( sorted.iter().map(ToString::to_string).collect::<Vec<_>>(), vec![short_a, short_z, long_a] );
let matches = prefix_matches(&sorted, "A"); assert_eq!( matches.iter().map(ToString::to_string).collect::<Vec<_>>(), vec![short_a, long_a] ); assert_eq!(prefix_matches(&sorted, "z").len(), 1); assert_eq!(prefix_matches(&sorted, "A1111111111111111111111").len(), 0); }
#[test] fn single_id() { let ids = vec![ThingsId::random()]; let prefixes = shortest_unique_prefixes(&ids); assert_eq!(prefixes.len(), 1); let prefix = prefixes.values().next().unwrap(); assert_eq!(prefix.len(), 1, "single ID should have 1-char prefix"); }
#[test] fn empty_input() { let prefixes = shortest_unique_prefixes(&[]); assert!(prefixes.is_empty()); }
#[test] fn longest_shortest_prefix_len_drives_fixed_width_unique_rendering() { fn find_case_ids() -> Vec<ThingsId> { let mut a: Option<ThingsId> = None; let mut b_left: Option<ThingsId> = None; let mut b_right: Option<ThingsId> = None;
for _ in 0..1_000_000 { let id = ThingsId::random(); let (buf, len) = base58_encode_fixed(id.as_bytes()); let s = std::str::from_utf8(&buf[..len]).unwrap().to_owned();
if s.starts_with('A') { if a.is_none() { a = Some(id); } continue; }
if s.starts_with('B') { let second = s.chars().nth(1).unwrap_or('1'); if let Some(left) = b_left.as_ref() { let left_second = left.to_string().chars().nth(1).unwrap_or('1'); if second != left_second { b_right = Some(id); } } else { b_left = Some(id); } }
if a.is_some() && b_left.is_some() && b_right.is_some() { break; } }
vec![ a.expect("must find an A* id"), b_left.expect("must find first B* id"), b_right.expect("must find second B* id with different second char"), ] }
let ids = find_case_ids(); let width = longest_shortest_unique_prefix_len(&ids); assert_eq!(width, 2);
for id in &ids { let prefix = id.to_string().chars().take(width).collect::<String>(); let matches: Vec<&ThingsId> = ids .iter() .filter(|other| other.to_string().starts_with(prefix.as_str())) .collect(); assert_eq!( matches.len(), 1, "prefix {prefix:?} should identify exactly one id" ); assert_eq!(matches[0], id); } }}