diff options
Diffstat (limited to 'forest')
| -rw-r--r-- | forest/src/default.rs | 78 | ||||
| -rw-r--r-- | forest/src/design.org | 3 | ||||
| -rw-r--r-- | forest/src/lib.rs | 3 |
3 files changed, 55 insertions, 29 deletions
diff --git a/forest/src/default.rs b/forest/src/default.rs index d79c1c7..9295f1a 100644 --- a/forest/src/default.rs +++ b/forest/src/default.rs @@ -69,7 +69,7 @@ impl<T: GraphLabel> Default for DefaultForest<T> { impl<T: GraphLabel> AsRef<DefaultForest<T>> for DefaultForest<T> { fn as_ref(&self) -> &DefaultForest<T> { - &self + self } } @@ -123,9 +123,24 @@ impl<T: GraphLabel> ParentsGraph for DefaultForest<T> { 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> { @@ -252,7 +267,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<T> { Ok(frag_stack.is_empty() && self_stack.is_empty()) } - fn plant<F>(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error> + fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error> where F: AsRef<Self>, { @@ -284,16 +299,6 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<T> { let nodes_len = fragment.nodes_len(); - // 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); - } - // If the fragment root has a duplicate label, the forest will // not grow, so we use the label to find the adjoined node // index. @@ -313,6 +318,25 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<T> { } ); + // 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. @@ -403,7 +427,7 @@ mod forest_test { // add some child - forest.plant(0, leaf!(1))?; + forest.plant(0, leaf!(1), false)?; assert_eq!(forest.nodes_len(), 2); let mut children = forest.children_of(0)?; @@ -412,10 +436,10 @@ mod forest_test { // add more children - forest.plant(0, leaf!(2))?; - forest.plant(0, leaf!(3))?; - forest.plant(0, leaf!(4))?; - forest.plant(2, leaf!(5))?; + 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)?; @@ -428,32 +452,32 @@ mod forest_test { assert_eq!(children.next(), None); let mut test_forest = leaf!(0); - test_forest.plant(0, leaf!(1))?; - test_forest.plant(0, leaf!(2))?; - test_forest.plant(0, leaf!(3))?; - test_forest.plant(2, leaf!(5))?; + 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))?; - test_forest.plant(0, leaf!(2))?; + 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))?; - test_forest.plant(2, leaf!(5))?; + 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))?; + 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))?; + forest.plant(3, leaf!(5), false)?; let len = forest.nodes_len(); diff --git a/forest/src/design.org b/forest/src/design.org index 09db113..c32b1c9 100644 --- a/forest/src/design.org +++ b/forest/src/design.org @@ -112,7 +112,8 @@ The chain-rule operation can be described as follows: 2. Prepare a new forest fragment as follows. 1) For every child \(g\) of \(e\) in the atomic language, if \(g\) is the terminal that appears as the current input \(t\), let the - new fragment be defined as the node moved by \(g\), alone. + new fragment be defined as the node moved by \(g\), followed by + a terminal node, as a single edge. 2) If \(g\) is a non-terminal and its first-set contains \(t\), then for every left-linearly closed child of \(g\) that is labelled \(t\), denoted as \(h\), then let the fragment be diff --git a/forest/src/lib.rs b/forest/src/lib.rs index f843bc1..8c9b918 100644 --- a/forest/src/lib.rs +++ b/forest/src/lib.rs @@ -37,7 +37,7 @@ pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<T> { F: AsRef<Self>; /// Extend the forest by adjoining another forest at a given node. - fn plant<F>(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error> + fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error> where F: AsRef<Self>; @@ -54,3 +54,4 @@ pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<T> { } pub mod default; +pub use default::Error; |