summaryrefslogtreecommitdiff
path: root/forest/src/default.rs
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-01-20 13:48:26 +0800
committerJSDurand <mmemmew@gmail.com>2023-01-20 13:48:26 +0800
commit18d7955b7d84c00467ede38baae53f4ce1fb6908 (patch)
tree97d0746b82816a21d980636e50f8cdbeb804b518 /forest/src/default.rs
parent8f8d3d1a3c276be4be2e5d2e767ada564c47279a (diff)
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.
Diffstat (limited to 'forest/src/default.rs')
-rw-r--r--forest/src/default.rs78
1 files changed, 51 insertions, 27 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();