From 18d7955b7d84c00467ede38baae53f4ce1fb6908 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Fri, 20 Jan 2023 13:48:26 +0800
Subject: 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.
---
 forest/src/default.rs | 78 +++++++++++++++++++++++++++++++++------------------
 1 file changed, 51 insertions(+), 27 deletions(-)

(limited to 'forest/src/default.rs')

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();
 
-- 
cgit v1.2.3-18-g5258