diff options
Diffstat (limited to 'forest/src/default.rs')
| -rw-r--r-- | forest/src/default.rs | 523 |
1 files changed, 0 insertions, 523 deletions
diff --git a/forest/src/default.rs b/forest/src/default.rs deleted file mode 100644 index b96439f..0000000 --- a/forest/src/default.rs +++ /dev/null @@ -1,523 +0,0 @@ -//! This file provides a default implementation for the -//! [`Forest`][crate::Forest] trait. - -use super::*; -use graph::{ - builder::BuilderMut, labelled::binary::PLGBuilderMut, Graph, LabelGraph, PLGraph, RedirectGraph, -}; - -use core::fmt::Display; - -/// The type of errors for forest operations. -#[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd)] -pub enum Error { - /// An index is out of bounds. - /// - /// The first component is the index that is out of bounds, and - /// the second component is the current length of nodes. - IndexOutOfBounds(usize, usize), - /// The forest does not permit duplicate nodes but encounters a - /// repeated node. - DuplicatedNode(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), - /// Encounter an error when converting forest labels. - LabelConversion(ForestLabelError), -} - -impl Display for Error { - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - match self { - Error::IndexOutOfBounds(index, bound) => { - write!(f, "index {index} is out of bound {bound}") - } - Error::DuplicatedNode(n) => write!(f, "node {n} is duplicated"), - Error::InvalidGraphError(ge) => write!(f, "invalid error: {ge}"), - Error::NodeNoLabel(n) => write!(f, "node {n} has no labels, but it should have one"), - Error::LabelConversion(le) => write!(f, "fail to convert labels: {le}"), - } - } -} - -impl std::error::Error for Error {} - -impl From<GError> for Error { - fn from(ge: GError) -> Self { - match ge { - GError::IndexOutOfBounds(index, bound) => Self::IndexOutOfBounds(index, bound), - GError::DuplicatedNode(n) => Self::DuplicatedNode(n), - _ => Self::InvalidGraphError(ge), - } - } -} - -impl From<ForestLabelError> for Error { - fn from(le: ForestLabelError) -> Self { - Self::LabelConversion(le) - } -} - -/// A default implementation of forest. -#[derive(Debug, Clone)] -pub struct DefaultForest<T: GraphLabel> { - graph: PLGraph<T>, - root: Option<usize>, -} - -impl<T: GraphLabel> Default for DefaultForest<T> { - fn default() -> Self { - let graph = Default::default(); - let root = None; - - Self { graph, root } - } -} - -impl<T: GraphLabel> AsRef<DefaultForest<T>> for DefaultForest<T> { - fn as_ref(&self) -> &DefaultForest<T> { - self - } -} - -impl<T: GraphLabel> Graph for DefaultForest<T> { - type Iter<'a> = <PLGraph<T> as Graph>::Iter<'a> - where - Self: 'a; - - #[inline] - fn is_empty(&self) -> bool { - self.graph.is_empty() - } - - #[inline] - fn nodes_len(&self) -> usize { - self.graph.nodes_len() - } - - #[inline] - fn edges_len(&self) -> Option<usize> { - self.graph.edges_len() - } - - #[inline] - fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GError> { - self.graph.children_of(node_id) - } - - #[inline] - fn degree(&self, node_id: usize) -> Result<usize, GError> { - self.graph.degree(node_id) - } - - #[inline] - fn is_empty_node(&self, node_id: usize) -> Result<bool, GError> { - self.graph.is_empty_node(node_id) - } - - #[inline] - fn has_edge(&self, source: usize, target: usize) -> Result<bool, GError> { - self.graph.has_edge(source, target) - } - - fn replace_by_builder(&mut self, _builder: impl graph::Builder<Result = Self>) { - unimplemented!() - } -} - -impl<T: GraphLabel> ParentsGraph for DefaultForest<T> { - type Iter<'a>= <PLGraph<T> as ParentsGraph>::Iter<'a> - where - Self:'a; - - #[inline] - fn parents_of(&self, node_id: usize) -> Result<<Self as ParentsGraph>::Iter<'_>, GError> { - self.graph.parents_of(node_id) - } - - #[inline] - fn nth_child(&self, node_id: usize, n: usize) -> Result<usize, GError> { - self.graph.nth_child(node_id, n) - } - - #[inline] - fn edge_to_parent( - &self, - source: usize, - target: usize, - ) -> Result<Option<graph::Parent>, GError> { - self.graph.edge_to_parent(source, target) - } -} - -impl<T: GraphLabel> LabelGraph<T> for DefaultForest<T> { - type Iter<'a> = std::iter::Empty<usize> - where - Self: 'a; - - type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)> - where - Self: 'a, - T: 'a; - - type EdgeLabelIter<'a> = std::iter::Empty<T> - where - Self: 'a, - T: 'a; - - #[inline] - fn query_label(&self, label: T) -> Option<usize> { - self.graph.query_label(label) - } - - #[inline] - fn vertex_label(&self, node_id: usize) -> Result<Option<T>, GError> { - self.graph.vertex_label(node_id) - } - - fn edge_label( - &self, - _source: usize, - _target: usize, - ) -> Result<Self::EdgeLabelIter<'_>, GError> { - unimplemented!("edges have no labels") - } - - fn find_children_with_label( - &self, - _node_id: usize, - _label: &T, - ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, GError> { - unimplemented!("edges have no labels") - } - - fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> { - unimplemented!("edges have no labels") - } - - fn has_edge_label(&self, _node_id: usize, _label: &T, _target: usize) -> Result<bool, GError> { - unimplemented!("edges have no labels") - } -} - -impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { - type Error = Error; - - fn root(&self) -> Option<usize> { - self.root - } - - fn new_leaf(label: T) -> Self { - let mut graph = PLGraph::default(); - - let mut builder = PLGBuilderMut::from_graph_mut(&mut graph); - - let root = Some(builder.add_vertex(ForestLabel::from(label))); - - Self { graph, root } - } - - fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error> - where - F: AsRef<Self>, - { - if !self.has_node(node_id) { - return Err(Error::IndexOutOfBounds(node_id, self.nodes_len())); - } - - // We do a depth-first traversal to determine if every node - // encountered has the same set of children (labels taken into - // the consideration). - - let fragment = fragment.as_ref(); - - let mut frag_stack = Vec::with_capacity(fragment.nodes_len()); - - let mut self_stack = Vec::with_capacity(fragment.nodes_len()); - - let frag_root = if let Some(root) = fragment.root() { - root - } else { - // an empty forest is a prefix of any forest. - return Ok(true); - }; - - frag_stack.push(frag_root); - self_stack.push(node_id); - - // defer popping - while let (Some(frag_top), Some(self_top)) = - (frag_stack.last().copied(), self_stack.last().copied()) - { - frag_stack.pop(); - self_stack.pop(); - - if fragment.vertex_label(frag_top)? != self.vertex_label(self_top)? { - // not a prefix - return Ok(false); - } - - let mut self_children = self.children_of(self_top)?; - - for child in fragment.children_of(frag_top)? { - if let Some(self_child) = self_children.next() { - frag_stack.push(child); - self_stack.push(self_child); - } else { - // too few children - return Ok(false); - } - } - } - - // Check both stacks are empty at the end. - Ok(frag_stack.is_empty() && self_stack.is_empty()) - } - - fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error> - where - F: AsRef<Self>, - { - // Convert self to a builder_mut, and traverse fragment in a - // depth-first manner and adjoin corresponding nodes along the - // way. - - if !self.has_node(node_id) { - return Err(Error::IndexOutOfBounds(node_id, self.nodes_len())); - } - - let fragment = fragment.as_ref(); - - let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); - - let root = if let Some(root) = fragment.root() { - root - } else { - // Nothing to do to plant an empty forest. - return Ok(()); - }; - - // Just a dummy label for use in adding edges. - // - // REVIEW: I probably should refactor the API for builder_mut. - let root_label = fragment - .vertex_label(root)? - .ok_or(Error::NodeNoLabel(root))?; - - let nodes_len = fragment.nodes_len(); - - /// If the fragment root has a duplicate label, the forest - /// will not grow, so we use the label to find the adjoined - /// node index. - /// - /// The nodes hava already been added to the forest, so it is - /// safe to call unwrap. - macro_rules! conversion ( - ($node:expr) => { - { - builder - .query_label( - fragment - .vertex_label($node)? - .ok_or(Error::NodeNoLabel($node))? - ).unwrap() - } - } - ); - - // If the fragment has been planted before, we just add an - // edge. - - if planted { - builder.add_edge(node_id, conversion!(root), root_label)?; - - return Ok(()); - } - - // First adjoin those nodes and join the edges later. - - for node in 0..nodes_len { - let label = fragment - .vertex_label(node)? - .ok_or(Error::NodeNoLabel(node))?; - - builder.add_vertex(label); - } - - // Don't forget to join the new sub-forest to the original - // forest, at the specified position. - - builder.add_edge(node_id, conversion!(root), root_label)?; - - // We can try to calculate the depth of fragments, if we need - // to lower the memory usage. But in our use cases, we - // usually deal with fragments where each node has at most one - // child, so the depth is supposed to be equal to the length - // in this case. - let mut stack = Vec::with_capacity(fragment.nodes_len()); - - stack.push(root); - - while let Some(top) = stack.pop() { - for child in fragment.children_of(top)? { - builder.add_edge(conversion!(top), conversion!(child), root_label)?; - } - } - - Ok(()) - } - - fn clone_node(&mut self, node_id: usize) -> Result<usize, Self::Error> { - let builder = PLGBuilderMut::from_graph_mut(&mut self.graph); - - let old_label = builder - .vertex_label(node_id)? - .ok_or(Error::NodeNoLabel(node_id))?; - - if old_label.is_packed() { - return Err(ForestLabelError::ClonePack.into()); - } - - if old_label.is_cloned().is_some() { - let mut parents = self.parents_of(node_id)?; - - // Make sure it only has one parent, which is the - // representative node. - assert_eq!(parents.len(), 1); - - // We checked its length is 1, so it is safe to unwrap - // here. - return Ok(parents.next().unwrap().node()); - } - - let rep_label = old_label.pack()?; - - let new_label = old_label.clone(self)?; - - let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); - - // Make a new node - let new_index = builder.add_vertex(rep_label); - - // Re-direct parents to the new node. - // - // This must be done before pointing the new node to the old - // node, otherwise that edge will be redirected as well. - - // Unfortunately I cannot loop through parents and mutate them - // at the same time, so I first collect them into a vector. - let parents: Vec<_> = builder.parents_of(node_id)?.collect(); - - for parent in parents.into_iter() { - builder.redirect(parent.node(), parent.edge(), new_index)?; - } - - // Point the new node to the old node. OLD_LABEL is just a - // place holder. - - builder.add_edge(new_index, node_id, old_label)?; - - // Modify the label of the old node. - - builder.set_label(node_id, new_label)?; - - Ok(new_index) - } -} - -#[cfg(test)] -mod forest_test { - use super::*; - - macro_rules! leaf ( - ($label:expr, $type:tt) =>{ - DefaultForest::<ForestLabel<$type>>::new_leaf($label) - }; - ($label:expr) => { - DefaultForest::<ForestLabel<usize>>::new_leaf($label) - } - ); - - #[test] - fn test_forest_api() -> Result<(), Box<dyn std::error::Error>> { - let forest: DefaultForest<usize> = Default::default(); - - // empty forest - - assert!(forest.is_empty()); - - // leaf forest - - let mut forest = leaf!(0, usize); - - assert_eq!(forest.nodes_len(), 1); - assert_eq!(forest.root(), Some(0)); - - // add some child - - forest.plant(0, leaf!(1), false)?; - - assert_eq!(forest.nodes_len(), 2); - let mut children = forest.children_of(0)?; - assert_eq!(children.next(), Some(1)); - assert_eq!(children.next(), None); - - // add more children - - forest.plant(0, leaf!(2), false)?; - forest.plant(0, leaf!(3), false)?; - forest.plant(0, leaf!(4), false)?; - forest.plant(2, leaf!(5), false)?; - - assert_eq!(forest.nodes_len(), 6); - let mut children = forest.children_of(0)?; - assert_eq!(children.next(), Some(1)); - assert_eq!(children.next(), Some(2)); - assert_eq!(children.next(), Some(3)); - assert_eq!(children.next(), Some(4)); - let mut children = forest.children_of(2)?; - assert_eq!(children.next(), Some(5)); - assert_eq!(children.next(), None); - - let mut test_forest = leaf!(0); - test_forest.plant(0, leaf!(1), false)?; - test_forest.plant(0, leaf!(2), false)?; - test_forest.plant(0, leaf!(3), false)?; - test_forest.plant(2, leaf!(5), false)?; - - assert!(forest.is_prefix(0, &test_forest)?); - - let mut test_forest = leaf!(0); - test_forest.plant(0, leaf!(1), false)?; - test_forest.plant(0, leaf!(2), false)?; - // this child of the root should have label 3 in order to be a - // prefix. - test_forest.plant(0, leaf!(4), false)?; - test_forest.plant(2, leaf!(5), false)?; - - assert!(!forest.is_prefix(0, &test_forest)?); - - let mut test_forest = leaf!(2); - test_forest.plant(0, leaf!(5), false)?; - - assert!(forest.is_prefix(2, &test_forest)?); - - // now test cloning - - // add a duplicate label - forest.plant(3, leaf!(5), false)?; - - let _len = forest.nodes_len(); - - forest.clone_node(5)?; - - assert_eq!(forest.nodes_len(), 7); - - #[cfg(feature = "test-print-viz")] - forest.print_viz("forest.gv")?; - - Ok(()) - } -} |