use crate::tile::MAX_LETTERS;
use alloc::vec::Vec;
use core::fmt;
pub type NodeIdx = u32;
const ACCEPT_BIT: u32 = 1 << 31;
const CHILD_MASK: u32 = !ACCEPT_BIT;
#[derive(Clone, PartialEq, Eq)]
pub struct WordGraph {
data: Vec<u32>,
root: NodeIdx,
node_count: u32,
arc_count: u32,
word_count: u64,
}
impl WordGraph {
pub(crate) fn from_parts(
data: Vec<u32>,
root: NodeIdx,
node_count: u32,
arc_count: u32,
word_count: u64,
) -> WordGraph {
debug_assert!(
!data.is_empty(),
"a graph always has at least a root header"
);
debug_assert!((root as usize) < data.len(), "root is out of range");
WordGraph {
data,
root,
node_count,
arc_count,
word_count,
}
}
pub fn empty() -> WordGraph {
WordGraph {
data: alloc::vec![0],
root: 0,
node_count: 1,
arc_count: 0,
word_count: 0,
}
}
#[inline]
pub const fn root(&self) -> NodeIdx {
self.root
}
#[inline]
pub fn node_count(&self) -> u32 {
self.node_count
}
#[inline]
pub fn arc_count(&self) -> u32 {
self.arc_count
}
#[inline]
pub fn word_count(&self) -> u64 {
self.word_count
}
#[inline]
pub fn size_bytes(&self) -> usize {
self.data.len() * core::mem::size_of::<u32>()
}
#[inline]
pub fn children(&self, node: NodeIdx) -> u32 {
self.data[node as usize] & CHILD_MASK
}
#[inline]
pub fn accepts(&self, node: NodeIdx) -> bool {
self.data[node as usize] & ACCEPT_BIT != 0
}
#[inline]
pub fn header(&self, node: NodeIdx) -> u32 {
self.data[node as usize]
}
#[inline]
pub const fn split_header(header: u32) -> (bool, u32) {
(header & ACCEPT_BIT != 0, header & CHILD_MASK)
}
#[inline]
pub fn degree(&self, node: NodeIdx) -> u32 {
self.children(node).count_ones()
}
#[inline]
pub fn child(&self, node: NodeIdx, letter: u8) -> Option<NodeIdx> {
debug_assert!((letter as usize) < MAX_LETTERS);
let children = self.children(node);
if children & (1 << letter) == 0 {
None
} else {
Some(self.child_for(node, children, letter))
}
}
#[inline]
pub fn child_unchecked(&self, node: NodeIdx, letter: u8) -> NodeIdx {
let children = self.children(node);
debug_assert!(
children & (1 << letter) != 0,
"child_unchecked called for a letter with no arc"
);
self.child_for(node, children, letter)
}
#[inline]
pub fn child_with_mask(&self, node: NodeIdx, children: u32, letter: u8) -> NodeIdx {
debug_assert_eq!(children, self.children(node), "stale child mask");
self.child_for(node, children, letter)
}
#[inline]
fn child_for(&self, node: NodeIdx, children: u32, letter: u8) -> NodeIdx {
let rank = (children & ((1u32 << letter) - 1)).count_ones();
self.data[node as usize + 1 + rank as usize]
}
pub fn reordered(&self) -> WordGraph {
let len = self.data.len();
let mut new_offset = alloc::vec![u32::MAX; len];
let mut visited = alloc::vec![false; len];
let mut order: Vec<NodeIdx> = Vec::with_capacity(self.node_count as usize);
let mut queue = alloc::collections::VecDeque::new();
visited[self.root as usize] = true;
queue.push_back(self.root);
let mut cursor: u32 = 0;
while let Some(node) = queue.pop_front() {
new_offset[node as usize] = cursor;
let degree = (self.data[node as usize] & CHILD_MASK).count_ones();
cursor += 1 + degree;
order.push(node);
for i in 0..degree as usize {
let target = self.data[node as usize + 1 + i];
if !visited[target as usize] {
visited[target as usize] = true;
queue.push_back(target);
}
}
}
let mut data = alloc::vec![0u32; cursor as usize];
let mut arcs = 0u32;
for &node in &order {
let from = node as usize;
let to = new_offset[from] as usize;
data[to] = self.data[from];
let degree = (self.data[from] & CHILD_MASK).count_ones() as usize;
arcs += degree as u32;
for i in 0..degree {
data[to + 1 + i] = new_offset[self.data[from + 1 + i] as usize];
}
}
WordGraph {
data,
root: 0,
node_count: order.len() as u32,
arc_count: arcs,
word_count: self.word_count,
}
}
pub fn walk(&self, node: NodeIdx, letters: impl IntoIterator<Item = u8>) -> Option<NodeIdx> {
let mut cur = node;
for l in letters {
cur = self.child(cur, l)?;
}
Some(cur)
}
pub fn accepts_sequence(&self, letters: impl IntoIterator<Item = u8>) -> bool {
match self.walk(self.root, letters) {
Some(n) => self.accepts(n),
None => false,
}
}
#[inline]
pub fn arcs(&self, node: NodeIdx) -> ArcIter {
ArcIter {
remaining: self.children(node),
}
}
pub fn collect_words(&self) -> Vec<Vec<u8>> {
let mut out = Vec::new();
let mut stack = Vec::new();
self.collect_from(self.root, &mut stack, &mut out);
out
}
fn collect_from(&self, node: NodeIdx, stack: &mut Vec<u8>, out: &mut Vec<Vec<u8>>) {
if self.accepts(node) {
out.push(stack.clone());
}
for letter in self.arcs(node) {
stack.push(letter);
self.collect_from(self.child_unchecked(node, letter), stack, out);
stack.pop();
}
}
#[inline]
pub fn raw(&self) -> &[u32] {
&self.data
}
pub const MAGIC: [u8; 4] = *b"SWG1";
const HEADER_LEN: usize = 28;
pub fn to_bytes(&self) -> Vec<u8> {
let mut out = Vec::with_capacity(Self::HEADER_LEN + self.data.len() * 4);
out.extend_from_slice(&Self::MAGIC);
out.extend_from_slice(&self.node_count.to_le_bytes());
out.extend_from_slice(&self.arc_count.to_le_bytes());
out.extend_from_slice(&(self.data.len() as u32).to_le_bytes());
out.extend_from_slice(&self.root.to_le_bytes());
out.extend_from_slice(&self.word_count.to_le_bytes());
for w in &self.data {
out.extend_from_slice(&w.to_le_bytes());
}
out
}
pub fn from_bytes(bytes: &[u8]) -> Result<WordGraph, GraphFormatError> {
if bytes.len() < Self::HEADER_LEN {
return Err(GraphFormatError::Truncated);
}
if bytes[..4] != Self::MAGIC {
return Err(GraphFormatError::BadMagic);
}
let u32_at =
|i: usize| u32::from_le_bytes([bytes[i], bytes[i + 1], bytes[i + 2], bytes[i + 3]]);
let node_count = u32_at(4);
let arc_count = u32_at(8);
let len = u32_at(12) as usize;
let root = u32_at(16);
let mut wc = [0u8; 8];
wc.copy_from_slice(&bytes[20..28]);
let word_count = u64::from_le_bytes(wc);
if len == 0 || root as usize >= len {
return Err(GraphFormatError::Corrupt);
}
if bytes.len() < Self::HEADER_LEN + len * 4 {
return Err(GraphFormatError::Truncated);
}
let mut data = Vec::with_capacity(len);
for i in 0..len {
data.push(u32_at(Self::HEADER_LEN + i * 4));
}
Ok(WordGraph {
data,
root,
node_count,
arc_count,
word_count,
})
}
pub fn validate(&self) -> Result<(), GraphFormatError> {
let len = self.data.len();
if self.root as usize >= len {
return Err(GraphFormatError::Corrupt);
}
let mut seen = 0usize;
let mut stack = alloc::vec![self.root];
let mut visited = alloc::vec![false; len];
while let Some(node) = stack.pop() {
let n = node as usize;
if n >= len {
return Err(GraphFormatError::Corrupt);
}
if visited[n] {
continue;
}
visited[n] = true;
seen += 1;
let k = (self.data[n] & CHILD_MASK).count_ones() as usize;
if n + k >= len {
return Err(GraphFormatError::Corrupt);
}
for i in 0..k {
let target = self.data[n + 1 + i];
if target as usize >= len {
return Err(GraphFormatError::Corrupt);
}
stack.push(target);
}
}
if seen as u32 != self.node_count {
return Err(GraphFormatError::Corrupt);
}
Ok(())
}
}
impl fmt::Debug for WordGraph {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("WordGraph")
.field("nodes", &self.node_count)
.field("arcs", &self.arc_count)
.field("words", &self.word_count)
.field("bytes", &self.size_bytes())
.finish()
}
}
#[derive(Clone, Debug)]
pub struct ArcIter {
remaining: u32,
}
impl Iterator for ArcIter {
type Item = u8;
#[inline]
fn next(&mut self) -> Option<u8> {
if self.remaining == 0 {
return None;
}
let letter = self.remaining.trailing_zeros() as u8;
self.remaining &= self.remaining - 1;
Some(letter)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let n = self.remaining.count_ones() as usize;
(n, Some(n))
}
}
impl ExactSizeIterator for ArcIter {}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum GraphFormatError {
BadMagic,
Truncated,
Corrupt,
}
impl fmt::Display for GraphFormatError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
GraphFormatError::BadMagic => write!(f, "not a scrabble word graph"),
GraphFormatError::Truncated => write!(f, "word graph data is truncated"),
GraphFormatError::Corrupt => write!(f, "word graph structure is inconsistent"),
}
}
}
#[cfg(feature = "std")]
impl std::error::Error for GraphFormatError {}
#[cfg(test)]
mod tests {
use super::*;
use crate::lexicon::GraphBuilder;
fn graph_of(words: &[&str]) -> WordGraph {
let mut b = GraphBuilder::new();
let mut seqs: Vec<Vec<u8>> = words
.iter()
.map(|w| w.bytes().map(|c| c - b'A').collect())
.collect();
seqs.sort();
for s in &seqs {
b.insert(s).unwrap();
}
b.finish()
}
#[test]
fn empty_graph_accepts_nothing() {
let g = WordGraph::empty();
assert!(!g.accepts(g.root()));
assert_eq!(g.children(g.root()), 0);
assert_eq!(g.word_count(), 0);
assert!(g.collect_words().is_empty());
}
#[test]
fn round_trips_every_inserted_word() {
let words = ["AT", "ATE", "CAT", "CATS", "EAT", "TEA"];
let g = graph_of(&words);
assert_eq!(g.word_count(), words.len() as u64);
for w in words {
let seq: Vec<u8> = w.bytes().map(|c| c - b'A').collect();
assert!(g.accepts_sequence(seq), "{w} should be accepted");
}
for w in ["A", "C", "CA", "CATT", "ZZZ", ""] {
let seq: Vec<u8> = w.bytes().map(|c| c - b'A').collect();
assert!(!g.accepts_sequence(seq), "{w:?} should be rejected");
}
}
#[test]
fn collect_words_returns_lexicographic_order() {
let g = graph_of(&["CAT", "AT", "CATS", "ATE"]);
let got: Vec<Vec<u8>> = g.collect_words();
let want: Vec<Vec<u8>> = ["AT", "ATE", "CAT", "CATS"]
.iter()
.map(|w| w.bytes().map(|c| c - b'A').collect())
.collect();
assert_eq!(got, want);
}
#[test]
fn child_and_child_unchecked_agree() {
let g = graph_of(&["AT", "ATE", "CAT", "CATS"]);
let root = g.root();
for letter in 0..26u8 {
match g.child(root, letter) {
Some(n) => assert_eq!(n, g.child_unchecked(root, letter)),
None => assert_eq!(g.children(root) & (1 << letter), 0),
}
}
}
#[test]
fn arcs_iterates_exactly_the_child_mask() {
let g = graph_of(&["AT", "BE", "CAT", "DO", "EAT"]);
let root = g.root();
let letters: Vec<u8> = g.arcs(root).collect();
assert_eq!(letters, alloc::vec![0, 1, 2, 3, 4], "A B C D E");
assert_eq!(letters.len(), g.degree(root) as usize);
assert_eq!(g.arcs(root).len(), letters.len());
}
#[test]
fn minimisation_shares_common_suffixes() {
let shared = graph_of(&["CREATION", "LOCATION", "STATION", "VACATION"]);
let unshared = graph_of(&["CREATIONX", "LOCATIONY", "STATIONZ", "VACATIONW"]);
assert!(
shared.node_count() < unshared.node_count(),
"shared suffixes ({}) should minimise better than distinct ones ({})",
shared.node_count(),
unshared.node_count()
);
}
#[test]
fn bytes_round_trip() {
let g = graph_of(&["AT", "ATE", "CAT", "CATS", "EAT"]);
let bytes = g.to_bytes();
let back = WordGraph::from_bytes(&bytes).expect("round trip should parse");
assert_eq!(back, g);
assert_eq!(back.collect_words(), g.collect_words());
back.validate().expect("a round-tripped graph is valid");
}
#[test]
fn from_bytes_rejects_bad_input() {
assert_eq!(WordGraph::from_bytes(&[]), Err(GraphFormatError::Truncated));
assert_eq!(
WordGraph::from_bytes(&[0u8; 32]),
Err(GraphFormatError::BadMagic)
);
let g = graph_of(&["AT"]);
let mut bytes = g.to_bytes();
bytes.truncate(bytes.len() - 4);
assert_eq!(
WordGraph::from_bytes(&bytes),
Err(GraphFormatError::Truncated)
);
}
#[test]
fn validate_catches_an_out_of_range_target() {
let g = graph_of(&["AT", "CAT"]);
let mut data = g.raw().to_vec();
data[g.root() as usize + 1] = 9_999;
let broken = WordGraph::from_parts(
data,
g.root(),
g.node_count(),
g.arc_count(),
g.word_count(),
);
assert_eq!(broken.validate(), Err(GraphFormatError::Corrupt));
}
#[test]
fn header_split_matches_accessors() {
let g = graph_of(&["AT", "ATE"]);
let node = g.child(g.root(), 0).and_then(|n| g.child(n, 19)).unwrap();
let (accepts, children) = WordGraph::split_header(g.header(node));
assert_eq!(accepts, g.accepts(node));
assert_eq!(children, g.children(node));
assert!(accepts, "AT is a word");
assert_ne!(children, 0, "ATE extends it");
}
}