summaryrefslogtreecommitdiff
path: root/forest/src
diff options
context:
space:
mode:
Diffstat (limited to 'forest/src')
-rw-r--r--forest/src/default.rs78
-rw-r--r--forest/src/design.org3
-rw-r--r--forest/src/lib.rs3
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;