use super::super::memory::bytes_of;
use crate::hash::HashMap;
use crate::linear::occurrences::OccId;
const SEPARATOR: OccId = OccId::new(u32::MAX);
#[derive(Debug, Default)]
pub(super) struct Trie {
children: HashMap<(u32, OccId), u32>,
ends: HashMap<u32, Vec<u32>>,
nodes: u32,
lists: usize,
looked: std::cell::Cell<u64>,
}
impl Trie {
fn child(&mut self, node: u32, o: OccId) -> Option<u32> {
if let Some(&child) = self.children.get(&(node, o)) {
return Some(child);
}
self.nodes = self.nodes.checked_add(1)?;
self.children.insert((node, o), self.nodes);
Some(self.nodes)
}
pub(super) fn insert(&mut self, gamma: &[OccId], theta: &[OccId], id: u32) -> bool {
let mut node = 0;
for &o in gamma.iter().chain([&SEPARATOR]).chain(theta) {
match self.child(node, o) {
Some(child) => node = child,
None => return false,
}
}
let list = self.ends.entry(node).or_default();
let before = bytes_of(list);
list.push(id);
self.lists += bytes_of(list) - before;
true
}
fn walk(&self, start: u32, zone: &[OccId], mut each: impl FnMut(u32) -> bool) -> bool {
let mut stack = vec![(start, 0usize)];
while let Some((node, from)) = stack.pop() {
if each(node) {
return true;
}
for j in from..zone.len() {
if j > from && zone[j] == zone[j - 1] {
continue;
}
self.looked.set(self.looked.get() + 1);
if let Some(&child) = self.children.get(&(node, zone[j])) {
stack.push((child, j + 1));
}
}
}
false
}
fn ends_within(&self, node: u32, theta: &[OccId], hit: &mut impl FnMut(u32) -> bool) -> bool {
self.walk(node, theta, |n| {
self.ends
.get(&n)
.is_some_and(|ids| ids.iter().any(|&id| hit(id)))
})
}
pub(super) fn same_within(
&self,
gamma: &[OccId],
theta: &[OccId],
mut hit: impl FnMut(u32) -> bool,
) -> bool {
let mut node = 0;
for &o in gamma.iter().chain([&SEPARATOR]) {
self.looked.set(self.looked.get() + 1);
match self.children.get(&(node, o)) {
Some(&child) => node = child,
None => return false,
}
}
self.ends_within(node, theta, &mut hit)
}
pub(super) fn within(
&self,
gamma: &[OccId],
theta: &[OccId],
mut hit: impl FnMut(u32) -> bool,
) -> bool {
self.walk(0, gamma, |node| {
self.children
.get(&(node, SEPARATOR))
.is_some_and(|&split| self.ends_within(split, theta, &mut hit))
})
}
pub(super) fn lookups(&self) -> u64 {
self.looked.take()
}
pub(super) fn bytes(&self) -> usize {
self.children.capacity() * (size_of::<((u32, OccId), u32)>() + 1)
+ self.ends.capacity() * (size_of::<(u32, Vec<u32>)>() + 1)
+ self.lists
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn finds_zones_within_and_refuses_past_its_names() {
let o = OccId::new;
let mut trie = Trie::default();
assert!(trie.insert(&[o(1), o(1), o(3)], &[o(7)], 0));
assert!(trie.insert(&[o(2)], &[], 1));
let found = |gamma: &[OccId], theta: &[OccId]| {
let mut ids = Vec::new();
trie.within(gamma, theta, |id| {
ids.push(id);
false
});
ids.sort_unstable();
ids
};
assert_eq!(found(&[o(1), o(1), o(2), o(3)], &[o(7)]), vec![0, 1]);
assert_eq!(
found(&[o(1), o(2), o(3)], &[o(7)]),
vec![1],
"one 1 too few"
);
assert_eq!(found(&[o(1), o(1), o(3)], &[]), Vec::<u32>::new());
assert!(trie.same_within(&[o(2)], &[o(5)], |_| true));
assert!(!trie.same_within(&[o(1), o(1), o(3)], &[], |_| true));
let mut full = Trie {
nodes: u32::MAX - 1,
..Trie::default()
};
assert!(!full.insert(&[o(1)], &[], 2), "two nodes past the names");
assert!(!full.within(&[o(1)], &[], |_| true));
}
}