chain: a prototype is added.

I have an ostensibly working prototype now.

Further tests are needed to make sure that the algorithm meets the
time complexity requirement, though.

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;