diff options
Diffstat (limited to 'forest/src/iter/archive.txt')
| -rw-r--r-- | forest/src/iter/archive.txt | 991 |
1 files changed, 991 insertions, 0 deletions
diff --git a/forest/src/iter/archive.txt b/forest/src/iter/archive.txt new file mode 100644 index 0000000..dcdae7f --- /dev/null +++ b/forest/src/iter/archive.txt @@ -0,0 +1,991 @@ +/// Archive of failed attempts + +/// The label of a query graph. +/// +/// Such a label is responsible for matching forest labels. +pub trait QueryLabel: GraphLabel { + /// The type of labels this matches against. + type Obj: GraphLabel; + + /// Determine whether or not a label matches this query label. + fn matches(&self, label: Self::Obj, status: ForestLabelType) -> bool { + let _ = label; + let _ = status; + + false + } + + /// Perform the query for one single query label. + fn run<F>( + &self, + forest: &F, + node: usize, + packs: &mut Vec<(usize, usize)>, + ) -> Result<Option<usize>, QRError> + where + F: LabelGraph<ForestLabel<<Self as QueryLabel>::Obj>>, + { + let mut dfs_stack: Vec<usize> = vec![node]; + + let nodes_len = forest.nodes_len(); + + while let Some(node) = dfs_stack.pop() { + let label = match forest.vertex_label(node) { + Ok(None) => return Err(QRError::NodeNoLabel(node)), + Err(_) => return Err(QRError::IndexOutOfBounds(node, nodes_len)), + Ok(Some(label)) => label, + }; + + let status = label.status(); + let label = label.label(); + + if status == ForestLabelType::Packed { + packs.push((node, 0)); + + dfs_stack.extend(forest.children_of(node).unwrap().take(1)); + + continue; + } + + if self.matches(label, status) { + return Ok(Some(node)); + } + + dfs_stack.extend( + forest + .children_of(node) + .unwrap() + .collect::<Vec<_>>() + .into_iter() + .rev(), + ); + } + + Ok(None) + } +} + +/// How should the current query skip nodes +#[derive(Debug, Clone, Copy, Default, Ord, PartialOrd, Hash, Eq, PartialEq)] +pub enum SkipState { + /// Skip anything in the depth-first search + Any, + /// Skip siblings + Sibling, + /// Do not skip + #[default] + None, +} + +impl std::fmt::Display for SkipState { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Self::Any => write!(f, "skip anything"), + Self::Sibling => write!(f, "skip siblings"), + Self::None => write!(f, "no skipping"), + } + } +} + +impl From<bool> for SkipState { + fn from(value: bool) -> Self { + if value { + Self::Sibling + } else { + Self::None + } + } +} + +/// A branch switch is of the form (n, m, v), where n means the n-th +/// node in the forest and m means the m-th child, and v is the vector +/// of children of the packed node. +#[derive(Debug, Clone, Default)] +pub struct BranchSwitch { + n: usize, + m: usize, + v: Vec<usize>, +} + +impl BranchSwitch { + #[allow(dead_code)] + fn new(n: usize, m: usize, v: Vec<usize>) -> Self { + Self { n, m, v } + } + + #[allow(dead_code)] + fn node(&self) -> usize { + self.n + } + + #[allow(dead_code)] + fn child(&self) -> Option<usize> { + self.v.get(self.m).copied() + } + + #[allow(dead_code)] + fn advance(&mut self) -> bool { + if self.m < self.v.len() { + self.m += 1; + + return true; + } + + false + } +} + +// REVIEW: Change the types into boxed slices so that we can guarantee +// no capacity is ever wasted. + +/// The type of forests that would be walked. +/// +/// In plain terms this is a preprocessed graph that provides some +/// extra information than a plain graph, which will be useful in +/// walking. +#[derive(Debug, Clone)] +#[allow(unused)] +pub struct QForest { + current: Option<usize>, + /// Just for example uses. + pub dfs_next: Vec<usize>, + /// Just for example uses. + pub subtree_ranges: Vec<std::ops::RangeInclusive<usize>>, + // /// Just for example uses. + // pub next_branch: Vec<Option<usize>>, + num_seen_switches: usize, + /// Switches of branches are packed nodes along with the current + /// index of the child. One can switch to use a different child + /// to "switch branches". + pub branch_switches: Vec<BranchSwitch>, + /// Map ordinary node numbering to depth-first numbering. + ord_to_dfs: Vec<usize>, + /// Map depth-first numbering to ordinary node numbering. + dfs_to_ord: Vec<usize>, + restriction: Option<usize>, +} + +impl QForest { + fn new( + dfs_next: Vec<usize>, + subtree_ranges: Vec<std::ops::RangeInclusive<usize>>, + // next_branch: Vec<Option<usize>>, + branch_switches: Vec<BranchSwitch>, + ord_to_dfs: Vec<usize>, + dfs_to_ord: Vec<usize>, + ) -> Self { + let current: Option<usize> = None; + let restriction: Option<usize> = None; + let num_seen_switches = 0usize; + + Self { + current, + dfs_next, + subtree_ranges, + // next_branch, + num_seen_switches, + branch_switches, + restriction, + ord_to_dfs, + dfs_to_ord, + } + } + + /// Translate the node index from ordinary index to depth-first + /// index. + pub fn translate_to_dfs(&self, id: usize) -> Option<usize> { + self.ord_to_dfs.get(id).copied() + } + + /// Translate the node index from depth-first index to ordinary + /// index. + pub fn translate_from_dfs(&self, id: usize) -> Option<usize> { + self.dfs_to_ord.get(id).copied() + } +} + +impl Default for QForest { + fn default() -> Self { + let current = Default::default(); + let dfs_next = Default::default(); + let subtree_ranges = Default::default(); + // let next_branch = Default::default(); + let branch_switches = Default::default(); + let restriction = Default::default(); + let num_seen_switches = 0usize; + + let ord_to_dfs = Default::default(); + let dfs_to_ord = Default::default(); + + Self { + current, + dfs_next, + subtree_ranges, + // next_branch, + num_seen_switches, + branch_switches, + restriction, + ord_to_dfs, + dfs_to_ord, + } + } +} + +impl Queryable for QForest { + fn current(&self) -> Option<usize> { + self.current + } + + fn next(&mut self) -> bool { + let current = if let Some(current) = self.current { + current + } else { + return false; + }; + + let mut next = if let Some(next) = self.dfs_next.get(current) { + *next + } else { + return false; + }; + + match self.branch_switches.get(self.num_seen_switches) { + Some(switch) if switch.node() == next => { + if let Some(child) = switch.child() { + next = child; + } + + self.num_seen_switches += 1; + } + _ => {} + } + + let dfs_len = self.dfs_next.len(); + + if (0..dfs_len).contains(&next) { + self.current.replace(next); + + true + } else { + false + } + } + + fn next_branch(&mut self) -> bool { + self.branch_switches.iter_mut().any(BranchSwitch::advance) + + // let current = if let Some(current) = self.current { + // current + // } else { + // return false; + // }; + + // let next = if let Some(next) = self.next_branch.get(current).copied().flatten() { + // next + // } else { + // return false; + // }; + + // self.current.replace(next); + + // true + } + + fn restrict(&mut self, node: usize) -> bool { + let range = if let Some(range) = self.subtree_ranges.get(node) { + range + } else { + return false; + }; + + self.restriction.replace(node); + + let current = if let Some(current) = &self.current { + current + } else { + return false; + }; + + range.contains(current) + } +} + +/// Calculate some extra information for later processing. +pub fn preprocess_forest<T, F>(forest: F, root: usize) -> Result<QForest, GError> +where + T: GraphLabel, + F: LabelGraph<ForestLabel<T>>, +{ + let forest_len = forest.nodes_len(); + + // let current: Option<usize> = None; + + let mut dfs_next: Vec<usize> = (0..forest_len).map(|i| i + 1).collect(); + + let mut subtree_ranges: Vec<std::ops::RangeInclusive<usize>> = + (0..forest_len).map(|i| i..=i).collect(); + + // let next_branch: Vec<Option<usize>> = std::iter::repeat(None).take(forest_len).collect(); + + let mut branch_switches: Vec<BranchSwitch> = Vec::with_capacity(forest_len); + + // let restriction: Option<usize> = None; + + let mut dfs_to_ord: Vec<usize> = (0..forest_len).collect(); + let mut ord_to_dfs: Vec<usize> = (0..forest_len).collect(); + + if forest.is_empty_node(root).unwrap_or(true) { + if let Some(root_item) = dfs_next.get_mut(root) { + *root_item = forest_len; // out of bounds + } + + return Ok(QForest::new( + // current, + dfs_next, + subtree_ranges, + // next_branch, + // restriction, + branch_switches, + ord_to_dfs, + dfs_to_ord, + )); + } + + #[derive(Debug, Clone, Copy)] + enum StackItem { + Normal(usize), + Reflection(usize), + } + + impl From<usize> for StackItem { + fn from(value: usize) -> Self { + Self::Normal(value) + } + } + + impl StackItem { + fn is_normal(&self) -> bool { + matches!(self, Self::Normal(_)) + } + + fn get_value(&self) -> usize { + match *self { + StackItem::Normal(item) => item, + StackItem::Reflection(item) => item, + } + } + + fn reflect(&self) -> Self { + match self { + StackItem::Normal(item) => Self::Reflection(*item), + StackItem::Reflection(_) => *self, + } + } + } + + let mut stack: Vec<StackItem> = Vec::with_capacity(forest_len); + + let mut prev = root; + + let mut children_vec: Vec<usize> = Vec::with_capacity(forest_len); + + stack.extend({ + children_vec.extend(forest.children_of(root)?); + + children_vec.iter().copied().rev().map(StackItem::from) + }); + + let mut seen_nodes: HashMap<usize, Option<usize>> = HashMap::with_capacity(forest_len); + + seen_nodes.insert(root, None); + + let mut dfs_order = 1usize; + + while let Some(top) = stack.pop() { + let top_value = top.get_value(); + let top_label = forest + .vertex_label(top_value)? + .expect("node without label: {top_value}"); + if top.is_normal() { + if let Some(prev_item) = dfs_next.get_mut(prev) { + *prev_item = top_value; + } + + if let std::collections::hash_map::Entry::Vacant(e) = seen_nodes.entry(top_value) { + if let Some(item) = dfs_to_ord.get_mut(dfs_order) { + *item = top_value; + } + + if let Some(item) = ord_to_dfs.get_mut(top_value) { + *item = dfs_order; + } + + dfs_order += 1; + + stack.push(top.reflect()); + + e.insert(top_label.clone_index().map(|_| prev)); + + children_vec.clear(); + + children_vec.extend(forest.children_of(top_value)?); + + stack.extend(children_vec.iter().copied().rev().map(StackItem::from)); + } + + prev = top_value; + } else { + if let Some(range) = subtree_ranges.get_mut(top_value) { + let top_dfs = ord_to_dfs.get(top_value).copied().unwrap(); + let prev_dfs = ord_to_dfs.get(prev).copied().unwrap(); + + *range = top_dfs..=prev_dfs; + } + + // if top_is_cloned { + // if let Some(next) = stack.iter().rev().copied().find(StackItem::is_normal) { + // // update branches + // let top_dfs = ord_to_dfs.get(top_value).copied().unwrap(); + // let prev_dfs = ord_to_dfs.get(prev).copied().unwrap(); + + // for i in (top_dfs + 1)..=prev_dfs { + // let j = dfs_to_ord.get(i).copied().unwrap(); + + // match next_branch.get_mut(j) { + // Some(branch) if branch.is_none() => { + // *branch = Some(next.get_value()); + // } + + // _ => {} + // } + // } + // } + // } + + if !top_label.is_packed() { + continue; + } + + let top_children: Vec<usize> = forest.children_of(top_value)?.collect(); + + if let Some(next) = stack.iter().rev().copied().find(StackItem::is_normal) { + for child in top_children.iter() { + let child_prev = if let Some(Some(item)) = seen_nodes.get(child) { + *item + } else { + continue; + }; + + if let Some(prev_item) = dfs_next.get_mut(child_prev) { + *prev_item = next.get_value(); + + // dbg!(child_prev, next.get_value(), child); + } + } + } + + branch_switches.push(BranchSwitch::new(top_value, 0, top_children)); + } + } + + Ok(QForest::new( + // current, + dfs_next, + subtree_ranges, + // next_branch, + // restriction, + branch_switches, + ord_to_dfs, + dfs_to_ord, + )) +} + +// TODO: The query graph needs the ability to jump to a parent and +// restore the querying contexts. + +/// The type that represents queries as dependency graphs of query +/// labels. +/// +/// The labels of vertices are query labels that match against forest +/// labels, whereas the labels of graphs indicate whether or not the +/// edge should allow skipping siblings before matching. +#[derive(Debug, Clone, Graph)] +pub struct Query<T: QueryLabel> { + graph: SLGraph<SkipState>, + vertex_labels: Vec<T>, + root: Option<usize>, +} + +impl<T: QueryLabel> Query<T> { + /// Construct a new query from raw fields. + pub fn new(graph: SLGraph<SkipState>, vertex_labels: Vec<T>, root: Option<usize>) -> Self { + Self { + graph, + vertex_labels, + root, + } + } + + /// Return the root of this query. + /// + /// This returns `None` if and only if the graph is empty. + pub fn root(&self) -> Option<usize> { + self.root + } + + /// Return the label of the given node. + /// + /// This cannot be implemented as a method of the `LabelGraph` + /// trait as the type differs from that of the labels. + #[inline] + pub fn label_of_vertex(&self, node: usize) -> Result<T, GError> { + self.vertex_labels + .get(node) + .copied() + .ok_or(GError::IndexOutOfBounds(node, self.vertex_labels.len())) + } +} + +impl<T: QueryLabel> Default for Query<T> { + fn default() -> Self { + let graph = Default::default(); + let vertex_labels = Vec::new(); + let root = None; + + Self { + graph, + vertex_labels, + root, + } + } +} + +// delegation of labelgraph + +impl<T: QueryLabel> LabelGraph<SkipState> for Query<T> { + type Iter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::Iter<'a> + where + Self: 'a; + + type TupleIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::TupleIter<'a> + where + Self: 'a; + + type LabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::LabelIter<'a> + where + Self: 'a; + + type EdgeLabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::EdgeLabelIter<'a> + where + Self: 'a; + + #[inline] + fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, GError> { + self.graph.edge_label(source, target) + } + + fn find_children_with_label( + &self, + _node_id: usize, + _label: &SkipState, + ) -> Result<<Self as LabelGraph<SkipState>>::Iter<'_>, GError> { + unimplemented!("Unsupported operation") + } + + fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> { + unimplemented!("Unsupported operation") + } + + #[inline] + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> { + self.graph.tuples_of(node_id) + } + + #[inline] + fn has_edge_label( + &self, + node_id: usize, + label: &SkipState, + target: usize, + ) -> Result<bool, GError> { + self.graph.has_edge_label(node_id, label, target) + } +} + +#[derive(Debug, Clone)] +/// The type of errors that can occur when querying forests. +pub enum QRError { + /// An index is out of bounds. + IndexOutOfBounds(usize, usize), + /// A node has no labels while it is required to have one. + NodeNoLabel(usize), + /// Encounter an invalid error in converting from an error of + /// graphs. + InvalidGraphError(GError), + /// Not enough memory for vectors. + NoMemory(std::collections::TryReserveError), +} + +impl std::fmt::Display for QRError { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + QRError::IndexOutOfBounds(n, b) => { + write!(f, "index {n} out of bound {b}") + } + QRError::NodeNoLabel(n) => write!(f, "the node {n} has no label but should have one"), + QRError::InvalidGraphError(g) => { + write!(f, "an invalid error for forest iterators: {g}") + } + QRError::NoMemory(e) => write!(f, "not enough memory: {e}"), + } + } +} + +impl std::error::Error for QRError {} + +impl From<GError> for QRError { + fn from(value: GError) -> Self { + match value { + GError::IndexOutOfBounds(n, b) => Self::IndexOutOfBounds(n, b), + _ => Self::InvalidGraphError(value), + } + } +} + +impl From<std::collections::TryReserveError> for QRError { + fn from(value: std::collections::TryReserveError) -> Self { + Self::NoMemory(value) + } +} + +/// An implementation of the forest iterator for querying purposes. +#[derive(Debug, Clone)] +pub struct QRun<T: QueryLabel> { + /// The currently visited node. + current: Option<Vec<usize>>, + /// The queries dependency graph. + query: Query<T>, + /// The nodes of the query graph, in the depth-first order. + query_dfs: Vec<usize>, + /// The nodes of the forest, in the depth-first order. + forest_dfs: Vec<usize>, + /// The packed nodes that can be used to change to another branch + /// if needed. + /// + /// The tuple is in the following format + /// + /// (forest_index, query_index), + /// + /// where the indicies are the indices of nodes, in the + /// depth-first order, of the respective graphs. + packs: Vec<(usize, usize)>, +} + +impl<T: QueryLabel> Default for QRun<T> { + fn default() -> Self { + let current = Default::default(); + let query = Default::default(); + let packs = Default::default(); + + let query_dfs = Default::default(); + let forest_dfs = Default::default(); + + Self { + current, + query, + query_dfs, + forest_dfs, + packs, + } + } +} + +impl<T: QueryLabel> ForestIter for QRun<T> { + #[inline] + fn current(&self) -> Option<&[usize]> { + self.current.as_ref().map(|v| &v[..]) + } + + type ForestLabel = <T as QueryLabel>::Obj; + + type Item<'a> = Option<&'a [usize]> + where + Self: 'a; + + type Error = QRError; + + #[allow(unused)] + #[allow(clippy::collapsible_if)] + fn next<F>(&mut self, forest: &F, root: usize) -> Result<State, Self::Error> + where + F: LabelGraph<ForestLabel<Self::ForestLabel>>, + { + #[derive(Debug, Clone, Copy, Default)] + enum QueryIndex { + /// A normal index + Normal(usize), + #[default] + /// This means the query is now accepting anything. + Empty, + } + + macro_rules! query_match ( + ($index:expr, $label:expr, $status:expr) => { + if let QueryIndex::Normal($index) = index { + self.query + .label_of_vertex(qtop) + .map(|q| q.matches($label, $status)) + } else { + Ok(true) + } + } + ); + + #[derive(Debug, Clone, Copy)] + enum ForestIndex { + /// A normal index + Normal(usize), + /// How many times we fallback in the query graph + FallbackTimes(usize), + } + + impl ForestIndex { + fn is_normal(&self) -> bool { + matches!(self, Self::Normal(_)) + } + + // /// Increment the index if it is normal, decrement it otherwise. + // /// + // /// Return `None` if the advanced index would be out of bounds. + // fn advance_forest_index(&self, forest_len: usize) -> Option<Self> { + // match self { + // ForestIndex::Normal(index) => { + // if *index + 1 >= forest_len { + // None + // } else { + // Some(Self::Normal(*index + 1)) + // } + // } + // ForestIndex::FallbackTimes(time) => { + // if *time == 0 { + // None + // } else { + // Some(Self::FallbackTimes(*time - 1)) + // } + // } + // } + // } + + fn get_index(&self, current_indices: &[usize]) -> Result<usize, QRError> { + match self { + ForestIndex::Normal(index) => Ok(*index), + ForestIndex::FallbackTimes(time) => current_indices + .get(*time) + .copied() + .ok_or(QRError::IndexOutOfBounds(*time, current_indices.len())), + } + } + + fn get_query_index(&self) -> usize { + match self { + ForestIndex::Normal(_) => 0, + ForestIndex::FallbackTimes(time) => *time, + } + } + } + + let query_empty_p = self.query.is_empty(); + + let query_len = self.query.nodes_len(); + let forest_len = forest.nodes_len(); + + let query_root = if let Some(r) = self.query.root() { + r + } else { + return Ok(State::Finish); + }; + + let orig_top: ForestIndex = match &self.current { + Some(current) => { + // re-starting search + ForestIndex::FallbackTimes(current.len() - 1) + } + None => { + // fresh new search + ForestIndex::Normal(0) + } + }; + + let mut top = orig_top.get_index(if let Some(current) = &self.current { + ¤t[..] + } else { + &[] + })?; + + let mut qtop = orig_top.get_query_index(); + + let mut candidate_captures: Vec<usize> = self + .current + .clone() + .unwrap_or_else(|| std::iter::repeat(0).take(query_len).collect()); + + 'search: loop { + let top_index = self + .forest_dfs + .get(top) + .copied() + .ok_or(QRError::IndexOutOfBounds(top, forest_len))?; + let top_label = forest + .vertex_label(top_index)? + .ok_or(QRError::NodeNoLabel(top_index))?; + + if top_label.is_packed() { + if forest.is_empty_node(top_index)? { + if self.packs.is_empty() { + return Ok(State::Finish); + } else { + return Ok(State::ChangeBranch); + } + } + + top = forest.children_of(top_index)?.next().unwrap(); + + continue 'search; + } + + let query_label = self + .query_dfs + .get(qtop) + .copied() + .and_then(|ind| self.query.label_of_vertex(ind).ok()); + + if query_label + .map(|label| label.matches(top_label.label(), top_label.status())) + .unwrap_or(true) + { + if let Some(captured_value) = candidate_captures.get_mut(qtop) { + *captured_value = top; + } + + top += 1; + qtop += 1; + + if query_empty_p || qtop >= query_len { + self.current.replace(candidate_captures); + + return Ok(State::Continue); + } + } else if qtop == 0 { + if self.packs.is_empty() { + return Ok(State::Finish); + } else { + return Ok(State::ChangeBranch); + } + } else { + qtop -= 1; + } + } + } + + #[inline] + fn clear(&mut self) { + self.current.take(); + self.packs.clear(); + } +} + +#[cfg(test)] +mod test_forest_query { + use std::io::Write; + + use super::*; + + #[test] + fn test_read_forest() -> Result<(), Box<dyn std::error::Error>> { + let mut file = std::fs::OpenOptions::new().read(true).open("forest.rep")?; + + use std::io::Read; + + let mut source: Vec<u8> = Vec::new(); + + file.read_to_end(&mut source)?; + + use crate::bytes::BytesForest; + + let bytes_forest = BytesForest::try_from(source)?; + + dbg!( + bytes_forest.nodes_len(), + bytes_forest.children_of(0)?.collect::<Vec<_>>() + ); + + #[cfg(feature = "test-print-viz")] + bytes_forest.print_viz("test forest.gv")?; + + let preprocessed = preprocess_forest(bytes_forest, 0)?; + + // dbg!(&preprocessed); + + use std::io::BufRead; + + println!("Input a query:"); + std::io::stdout().flush()?; + + for line in std::io::stdin().lock().lines() { + let line = line?; + + if line == "q" { + break; + } + + let qtype = if line.starts_with('s') { + 1u8 + } else if line.starts_with('n') { + 2u8 + } else { + 0u8 + }; + + let type_str: &str; + + let q = if line.starts_with('s') || line.starts_with('n') { + if let Ok(n) = line[1..].parse::<usize>() { + n + } else { + continue; + } + } else if let Ok(n) = line.parse::<usize>() { + n + } else { + continue; + }; + + let ans = match qtype { + 0 => { + type_str = "dfs"; + format!("{:?}", preprocessed.dfs_next.get(q).copied()) + } + 1 => { + type_str = "subtree range"; + format!("{:?}", preprocessed.subtree_ranges.get(q)) + } + _ => { + type_str = "next branch"; + format!("{:?}", "haha") + } + }; + + println!("answer for {type_str} = {ans}"); + + println!("Input a query:"); + std::io::stdout().flush()?; + } + + Ok(()) + } + + #[test] + fn test_preprocess() -> Result<(), Box<dyn std::error::Error>> { + Ok(()) + } +} |