use super::graph::{NodeIdx, WordGraph};
use crate::tile::MAX_LETTERS;
use alloc::vec::Vec;
use core::fmt;
#[cfg(feature = "std")]
type Register = std::collections::HashMap<u64, Vec<NodeIdx>>;
#[cfg(not(feature = "std"))]
type Register = alloc::collections::BTreeMap<u64, Vec<NodeIdx>>;
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum BuildError {
NotSorted { got: Vec<u8>, after: Vec<u8> },
LetterOutOfRange(u8),
EmptySequence,
}
impl fmt::Display for BuildError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
BuildError::NotSorted { got, after } => {
write!(f, "input must be sorted: {got:?} arrived after {after:?}")
}
BuildError::LetterOutOfRange(l) => {
write!(
f,
"letter index {l} is at or above the maximum of {MAX_LETTERS}"
)
}
BuildError::EmptySequence => write!(f, "the empty sequence cannot be a word"),
}
}
}
#[cfg(feature = "std")]
impl std::error::Error for BuildError {}
#[derive(Clone, Debug)]
struct BuildNode {
accepts: bool,
children: Vec<(u8, NodeIdx)>,
}
impl BuildNode {
fn new() -> BuildNode {
BuildNode {
accepts: false,
children: Vec::new(),
}
}
}
pub struct GraphBuilder {
data: Vec<u32>,
register: Register,
path: Vec<BuildNode>,
letters: Vec<u8>,
prev: Vec<u8>,
word_count: u64,
node_count: u32,
arc_count: u32,
}
impl GraphBuilder {
pub fn new() -> GraphBuilder {
GraphBuilder {
data: Vec::new(),
register: Register::new(),
path: alloc::vec![BuildNode::new()],
letters: Vec::new(),
prev: Vec::new(),
word_count: 0,
node_count: 0,
arc_count: 0,
}
}
pub fn with_capacity(words: usize) -> GraphBuilder {
let mut b = GraphBuilder::new();
b.data.reserve(words * 4);
#[cfg(feature = "std")]
b.register.reserve(words);
b
}
#[inline]
pub fn word_count(&self) -> u64 {
self.word_count
}
pub fn insert(&mut self, seq: &[u8]) -> Result<(), BuildError> {
if seq.is_empty() {
return Err(BuildError::EmptySequence);
}
if let Some(&bad) = seq.iter().find(|&&l| l as usize >= MAX_LETTERS) {
return Err(BuildError::LetterOutOfRange(bad));
}
match seq.cmp(&self.prev[..]) {
core::cmp::Ordering::Less => {
return Err(BuildError::NotSorted {
got: seq.to_vec(),
after: self.prev.clone(),
})
}
core::cmp::Ordering::Equal if !self.prev.is_empty() => return Ok(()),
_ => {}
}
let prefix = common_prefix(seq, &self.prev);
self.collapse_to(prefix);
for &letter in &seq[prefix..] {
self.letters.push(letter);
self.path.push(BuildNode::new());
}
self.path
.last_mut()
.expect("the path always holds at least the root")
.accepts = true;
self.prev.clear();
self.prev.extend_from_slice(seq);
self.word_count += 1;
Ok(())
}
pub fn extend_sorted<'a>(
&mut self,
seqs: impl IntoIterator<Item = &'a [u8]>,
) -> Result<(), BuildError> {
for s in seqs {
self.insert(s)?;
}
Ok(())
}
pub fn finish(mut self) -> WordGraph {
self.collapse_to(0);
let root_node = self.path.pop().expect("the root is always present");
let root = self.commit(root_node);
WordGraph::from_parts(
self.data,
root,
self.node_count,
self.arc_count,
self.word_count,
)
.reordered()
}
fn collapse_to(&mut self, depth: usize) {
while self.path.len() > depth + 1 {
let node = self.path.pop().expect("checked by the loop condition");
let letter = self.letters.pop().expect("one letter per non-root node");
let id = self.commit(node);
self.path
.last_mut()
.expect("popping never empties the path")
.children
.push((letter, id));
}
}
fn commit(&mut self, mut node: BuildNode) -> NodeIdx {
node.children.sort_unstable_by_key(|&(l, _)| l);
debug_assert!(
node.children.windows(2).all(|w| w[0].0 < w[1].0),
"a node cannot have two arcs for the same letter"
);
let mut mask = 0u32;
for &(l, _) in &node.children {
mask |= 1 << l;
}
let header = if node.accepts { mask | (1 << 31) } else { mask };
let hash = structural_hash(header, &node.children);
if let Some(candidates) = self.register.get(&hash) {
for &offset in candidates {
if self.matches(offset, header, &node.children) {
return offset;
}
}
}
let offset = self.data.len() as NodeIdx;
self.data.push(header);
for &(_, target) in &node.children {
self.data.push(target);
}
self.node_count += 1;
self.arc_count += node.children.len() as u32;
self.register.entry(hash).or_default().push(offset);
offset
}
fn matches(&self, offset: NodeIdx, header: u32, children: &[(u8, NodeIdx)]) -> bool {
let base = offset as usize;
if self.data[base] != header {
return false;
}
self.data[base + 1..base + 1 + children.len()]
.iter()
.zip(children.iter())
.all(|(&got, &(_, want))| got == want)
}
}
impl Default for GraphBuilder {
fn default() -> Self {
GraphBuilder::new()
}
}
fn common_prefix(a: &[u8], b: &[u8]) -> usize {
a.iter().zip(b.iter()).take_while(|(x, y)| x == y).count()
}
fn structural_hash(header: u32, children: &[(u8, NodeIdx)]) -> u64 {
let mut h: u64 = 0xcbf2_9ce4_8422_2325;
let mut mix = |v: u64| {
h ^= v;
h = h.wrapping_mul(0x0100_0000_01b3);
};
mix(header as u64);
for &(_, target) in children {
mix(target as u64);
}
h
}
#[cfg(test)]
mod tests {
use super::*;
fn seq(w: &str) -> Vec<u8> {
w.bytes().map(|c| c - b'A').collect()
}
fn build(words: &[&str]) -> WordGraph {
let mut sorted: Vec<Vec<u8>> = words.iter().map(|w| seq(w)).collect();
sorted.sort();
let mut b = GraphBuilder::new();
for s in &sorted {
b.insert(s).unwrap();
}
b.finish()
}
#[test]
fn accepts_exactly_the_input() {
let words = ["AB", "ABC", "ABCD", "BC", "CD", "CDE"];
let g = build(&words);
let got: Vec<Vec<u8>> = g.collect_words();
let mut want: Vec<Vec<u8>> = words.iter().map(|w| seq(w)).collect();
want.sort();
assert_eq!(got, want);
assert_eq!(g.word_count(), words.len() as u64);
}
#[test]
fn a_single_word_graph_is_a_chain() {
let g = build(&["CAT"]);
assert!(g.accepts_sequence(seq("CAT")));
assert!(!g.accepts_sequence(seq("CA")));
assert_eq!(g.node_count(), 4);
assert_eq!(g.arc_count(), 3);
}
#[test]
fn duplicates_are_ignored() {
let mut b = GraphBuilder::new();
b.insert(&seq("CAT")).unwrap();
b.insert(&seq("CAT")).unwrap();
b.insert(&seq("CATS")).unwrap();
let g = b.finish();
assert_eq!(g.word_count(), 2);
assert_eq!(g.collect_words().len(), 2);
}
#[test]
fn unsorted_input_is_rejected() {
let mut b = GraphBuilder::new();
b.insert(&seq("CAT")).unwrap();
let err = b.insert(&seq("AT")).unwrap_err();
assert!(matches!(err, BuildError::NotSorted { .. }));
}
#[test]
fn bad_letters_and_empty_sequences_are_rejected() {
let mut b = GraphBuilder::new();
assert_eq!(b.insert(&[]), Err(BuildError::EmptySequence));
assert_eq!(b.insert(&[0, 99]), Err(BuildError::LetterOutOfRange(99)));
assert_eq!(b.word_count(), 0);
}
#[test]
fn an_empty_builder_finishes_into_an_empty_graph() {
let g = GraphBuilder::new().finish();
assert_eq!(g.word_count(), 0);
assert!(g.collect_words().is_empty());
assert!(!g.accepts_sequence(seq("A")));
}
#[test]
fn the_result_is_actually_minimal() {
let g = build(&["DOING", "GOING", "SUING", "TAKING"]);
assert!(
g.node_count() <= 16,
"expected suffix sharing, got {} nodes",
g.node_count()
);
let a = build(&["AB", "AC", "BB", "BC"]);
let b = build(&["BC", "BB", "AC", "AB"]);
assert_eq!(a.node_count(), b.node_count());
assert_eq!(a.collect_words(), b.collect_words());
}
#[test]
fn equivalent_subtrees_are_shared_not_duplicated() {
let g = build(&["XY", "ZY"]);
let root = g.root();
let x = g.child(root, seq("X")[0]).unwrap();
let z = g.child(root, seq("Z")[0]).unwrap();
assert_eq!(x, z, "identical subtrees must be the same node");
}
#[test]
fn prefix_words_are_marked_accepting() {
let g = build(&["A", "AB", "ABC"]);
assert!(g.accepts_sequence(seq("A")));
assert!(g.accepts_sequence(seq("AB")));
assert!(g.accepts_sequence(seq("ABC")));
assert_eq!(g.collect_words().len(), 3);
}
#[test]
fn handles_the_full_letter_range() {
let wide: Vec<u8> = (0..MAX_LETTERS as u8).collect();
let mut b = GraphBuilder::new();
b.insert(&wide).unwrap();
let single: Vec<u8> = alloc::vec![MAX_LETTERS as u8 - 1];
b.insert(&single).unwrap();
let g = b.finish();
assert!(g.accepts_sequence(wide));
assert!(g.accepts_sequence(single));
assert_eq!(g.degree(g.root()), 2);
}
#[test]
fn a_larger_graph_validates_and_round_trips() {
let mut words: Vec<Vec<u8>> = Vec::new();
for a in 0..12u8 {
for b in 0..12u8 {
for c in 0..8u8 {
words.push(alloc::vec![a, b, c]);
}
}
}
words.sort();
let mut builder = GraphBuilder::with_capacity(words.len());
for w in &words {
builder.insert(w).unwrap();
}
let g = builder.finish();
assert_eq!(g.word_count(), words.len() as u64);
g.validate()
.expect("builder output must be structurally valid");
assert_eq!(g.collect_words(), words);
}
}