summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--chain/src/archive.txt98
-rw-r--r--chain/src/item/default/mod.rs792
-rw-r--r--chain/src/item/default/splone.rs2
3 files changed, 759 insertions, 133 deletions
diff --git a/chain/src/archive.txt b/chain/src/archive.txt
index 7bd6f31..79fe6d8 100644
--- a/chain/src/archive.txt
+++ b/chain/src/archive.txt
@@ -540,3 +540,101 @@
//
// Ok(None)
// }
+
+// let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+// // Just a dummy label for use in adding edges.
+// //
+// // REVIEW: I probably should refactor the API for builder_mut.
+// let root_label = fragment
+// .vertex_label(root)?
+// .ok_or(Error::NodeNoLabel(root))?;
+
+// let nodes_len = fragment.nodes_len();
+
+// /// If the fragment root has a duplicate label, the forest
+// /// will not grow, so we use the label to find the adjoined
+// /// node index.
+// ///
+// /// The nodes hava already been added to the forest, so it is
+// /// safe to call unwrap.
+// macro_rules! conversion (
+// ($node:expr) => {
+// {
+// builder
+// .query_label(
+// fragment
+// .vertex_label($node)?
+// .ok_or(Error::NodeNoLabel($node))?
+// ).unwrap()
+// }
+// }
+// );
+
+// // 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 the relevant nodes and join the edges later.
+
+// let mut used_nodes: Vec<bool> = std::iter::repeat(false).take(nodes_len).collect();
+
+// let mut stack = vec![root];
+
+// while let Some(top) = stack.pop() {
+// if used_nodes.get(top).copied() == Some(true) {
+// continue;
+// }
+
+// *used_nodes
+// .get_mut(top)
+// .ok_or(Error::IndexOutOfBounds(top, nodes_len))? = true;
+
+// stack.extend(fragment.children_of(top)?);
+// }
+
+// let used_nodes = used_nodes;
+
+// for node in (0..nodes_len).filter(|node| used_nodes.get(*node).copied() == Some(true)) {
+// 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.
+
+// builder.add_edge(node_id, conversion!(root), root_label)?;
+
+// // We can try to calculate the depth of fragments, if we need
+// // to lower the memory usage. But in our use cases, we
+// // usually deal with fragments where each node has at most one
+// // child, so the depth is supposed to be equal to the length
+// // in this case.
+// let mut stack = Vec::with_capacity(fragment.nodes_len());
+
+// stack.push(root);
+
+// let mut seen_nodes = std::collections::HashSet::<usize>::new();
+
+// while let Some(top) = stack.pop() {
+// seen_nodes.insert(top);
+
+// for child in fragment.children_of(top)? {
+// builder.add_edge(conversion!(top), conversion!(child), root_label)?;
+
+// if !seen_nodes.contains(&child) {
+// seen_nodes.insert(child);
+// stack.push(child);
+// }
+// }
+// }
+
+// Ok(())
diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index 28bdbee..7b0a843 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -10,8 +10,6 @@ use graph::{
use graph_macro::Graph;
-use std::collections::HashSet;
-
use std::fmt::Display;
/// The type of errors for forest operations.
@@ -216,29 +214,9 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
return Err(Error::IndexOutOfBounds(node_id, self.nodes_len()));
}
- // FIXME: We should take the presence of packed nodes into
- // consideration. That is, the fragment might have already
- // been planted and packed, and we need to account for such
- // possibilities.
- //
- // Moreover, the fragments might also contain packed nodes, in
- // which case we need to check these multiple possibilities
- // are properly contained.
-
- // We do a depth-first traversal to determine if every node
- // encountered has the same set of children (labels taken into
- // the consideration).
-
let fragment = fragment.borrow();
let fragment_nodes_len = fragment.nodes_len();
- let mut frag_stack = Vec::with_capacity(fragment_nodes_len);
-
- let mut self_stack = Vec::with_capacity(fragment_nodes_len);
-
- let mut frag_seen: HashSet<usize> = HashSet::with_capacity(fragment_nodes_len);
- let mut self_seen: HashSet<usize> = HashSet::with_capacity(fragment_nodes_len);
-
let frag_root = if let Some(root) = fragment.root() {
root
} else {
@@ -246,72 +224,181 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
return Ok(true);
};
- frag_stack.push(frag_root);
- self_stack.push(node_id);
+ // We assign to each node in the fragment the node id in the
+ // forest that has a label that corresponds to the label of
+ // the node. One thing to note is that a plain node can also
+ // correspond to a packed node, but a packed node cannot
+ // correspond to a plain node. Denote this correspondence as
+ // A -> f(A).
+ //
+ // After this, we need to check, for each edge from A to B, if
+ // f(A) has an edge to f(B). But there are some caveats: if A
+ // is a packed node and B is a cloned node, we check nothing.
+ // And if f(A) is a packed node, we check every of its cloned
+ // children to see if it has an edge to f(B). Finally, we
+ // evaluate the fragment as a boolean expression, where the
+ // only operation is multiplication and the final value is the
+ // return value of the function.
+ //
+ // I have a marvelous proof that this algorithm works, but my
+ // computer does not have enough memory to contain this proof.
+ // See
+ // <https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem#Fermat's_conjecture>.
- // defer popping
- while let (Some(frag_top), Some(self_top)) =
- (frag_stack.last().copied(), self_stack.last().copied())
- {
- frag_seen.insert(frag_top);
- self_seen.insert(self_top);
+ // The vector of correspondance `f`.
+ let mut correspondance: Vec<usize> =
+ std::iter::repeat(0).take(fragment_nodes_len).collect();
- frag_stack.pop();
- self_stack.pop();
+ for (node, cor_mut) in (0..fragment_nodes_len).zip(correspondance.iter_mut()) {
+ let frag_label = fragment
+ .vertex_label(node)?
+ .ok_or(Error::NodeNoLabel(node))?
+ .label();
- // NOTE: The labels might defer by the status. We test
- // for the equalities of inner labels only.
+ let packed_label = ForestLabel::new(frag_label, ForestLabelType::Packed);
+ let plain_label = ForestLabel::new(frag_label, ForestLabelType::Plain);
- if fragment.vertex_label(frag_top)?.map(|label| label.label())
- != self.vertex_label(self_top)?.map(|label| label.label())
- {
- // not a prefix
- // dbg!(
- // frag_top,
- // self_top,
- // fragment.vertex_label(frag_top)?,
- // self.vertex_label(self_top)?
- // );
+ if let Some(packed_pos) = self.query_label(packed_label) {
+ *cor_mut = packed_pos;
+ } else if let Some(plain_pos) = self.query_label(plain_label) {
+ *cor_mut = plain_pos;
+ } else {
return Ok(false);
}
+ }
- let self_children = self.children_of(self_top)?;
- let frag_children = fragment.children_of(frag_top)?;
+ let correspondance = correspondance;
- if frag_children.len() > self_children.len() {
- // dbg!(
- // frag_top,
- // self_top,
- // fragment.vertex_label(frag_top)?,
- // self.vertex_label(self_top)?
- // );
- return Ok(false);
+ let f_root = correspondance
+ .get(frag_root)
+ .copied()
+ .ok_or(Error::IndexOutOfBounds(frag_root, correspondance.len()))?;
+
+ if f_root != node_id {
+ return Ok(false);
+ }
+
+ 'node_loop: for (node, f_node) in
+ (0..fragment_nodes_len).zip(correspondance.iter().copied())
+ {
+ let node_label = fragment
+ .vertex_label(node)?
+ .ok_or(Error::NodeNoLabel(node))?;
+ let node_degree = fragment.degree(node)?;
+
+ let f_label = self
+ .vertex_label(f_node)?
+ .ok_or(Error::NodeNoLabel(f_node))?;
+
+ if node_label.is_packed() {
+ let value = f_label.is_packed() && self.degree(f_node)? >= node_degree;
+
+ if !value {
+ return Ok(false);
+ }
+
+ continue 'node_loop;
}
- for (frag_child, self_child) in frag_children.zip(self_children) {
- if frag_seen.contains(&frag_child) && self_seen.contains(&self_child) {
- continue;
- } else if frag_seen.contains(&frag_child) || self_seen.contains(&self_child) {
- // dbg!();
+ if f_label.is_packed() {
+ let mut value = false;
+
+ 'f_children_loop: for f_node_child in self.children_of(f_node)? {
+ if self.degree(f_node_child)? < node_degree {
+ continue 'f_children_loop;
+ }
+
+ for (child, f_node_child_child) in fragment
+ .children_of(node)?
+ .zip(self.children_of(f_node_child)?)
+ {
+ let f_child = correspondance
+ .get(child)
+ .copied()
+ .ok_or(Error::IndexOutOfBounds(child, correspondance.len()))?;
+
+ if f_node_child_child != f_child {
+ continue 'f_children_loop;
+ }
+ }
+
+ value = true;
+
+ break 'f_children_loop;
+ }
+
+ if !value {
return Ok(false);
}
- frag_stack.push(frag_child);
- self_stack.push(self_child);
+ continue 'node_loop;
+ }
+
+ if self.degree(f_node)? < node_degree {
+ return Ok(false);
+ }
+
+ for (child, f_node_child) in fragment.children_of(node)?.zip(self.children_of(f_node)?)
+ {
+ let f_child = correspondance
+ .get(child)
+ .copied()
+ .ok_or(Error::IndexOutOfBounds(child, correspondance.len()))?;
+
+ if f_node_child != f_child {
+ return Ok(false);
+ }
}
}
- // Check both stacks are empty at the end.
- Ok(frag_stack.is_empty() && self_stack.is_empty())
+ Ok(true)
}
fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error>
where
F: Borrow<Self>,
{
- // Convert self to a builder_mut, and traverse fragment in a
- // depth-first manner and adjoin corresponding nodes along the
- // way.
+ // As in the method `is_prefix`, we assign a node id of self
+ // to a node in the fragment. Here a plain node can
+ // correspond to a packed node, and a packed node can also
+ // correspond to a plain node. The only restriction is that
+ // if there is a packed node in the self forest, then it must
+ // be corresponded, rather than the plain node with the same
+ // inner label. One thing to note is that this correspondance
+ // is not fixed during the execution of the function.
+ // Instead, the planting of the function will change the
+ // status of nodes. And if the fragment contains nodes that
+ // share children, then the status of nodes need to be
+ // synchronized after each change.
+ //
+ // Another way is to give up calculating the status
+ // beforehand. Rather, we calculate the correspondance
+ // exactly when we need it. This might turn out to be much
+ // simpler and more efficient.
+ //
+ // After this, consider a correspondence pair (node, f(node)),
+ // there are five situations to consider:
+ //
+ // 1. f(node) is non-existent: in this case we just add a new
+ // node f(node) and add edges from f(node) to f(child) for
+ // every child of node.
+ //
+ // 2. node and f(node) are not packed: We need to decide
+ // whether f(node) should be cloned.
+ //
+ // 3. node is packed but f(node) is not: in this case we need
+ // to clone f(node), and for each cloned child of node, we
+ // need to decide whether it needs to be added as a new node.
+ //
+ // 4. node is not packed but f(node) is: in this case we check
+ // if there is a cloned child of f(node) that possesses the
+ // same set of children as node, as a prefix. If, and only
+ // if, this is not the case, we add a new clone with the given
+ // children.
+ //
+ // 5. both node and f(node) are packed: in this case we repeat
+ // the same process as the previous situation, for each cloned
+ // child of node.
if !self.has_node(node_id) {
return Err(Error::IndexOutOfBounds(node_id, self.nodes_len()));
@@ -319,7 +406,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
let fragment = fragment.borrow();
- let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+ let fragment_nodes_len = fragment.nodes_len();
let root = if let Some(root) = fragment.root() {
root
@@ -328,96 +415,388 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
return Ok(());
};
- // Just a dummy label for use in adding edges.
- //
- // REVIEW: I probably should refactor the API for builder_mut.
- let root_label = fragment
- .vertex_label(root)?
- .ok_or(Error::NodeNoLabel(root))?;
+ // A convenient function to calculate the correspondance.
+ fn builder_query<T: GraphLabel>(
+ builder: &PLGBuilderMut<ForestLabel<T>>,
+ label: T,
+ ) -> Option<(usize, ForestLabel<T>, bool)> {
+ let packed_label = ForestLabel::new(label, ForestLabelType::Packed);
+ let plain_label = ForestLabel::new(label, ForestLabelType::Plain);
+
+ if let Some(packed_node) = builder.query_label(packed_label) {
+ Some((packed_node, packed_label, true))
+ } else {
+ builder
+ .query_label(plain_label)
+ .map(|plain_node| (plain_node, plain_label, false))
+ }
+ }
- let nodes_len = fragment.nodes_len();
-
- /// If the fragment root has a duplicate label, the forest
- /// will not grow, so we use the label to find the adjoined
- /// node index.
- ///
- /// The nodes hava already been added to the forest, so it is
- /// safe to call unwrap.
- macro_rules! conversion (
- ($node:expr) => {
- {
- builder
- .query_label(
- fragment
- .vertex_label($node)?
- .ok_or(Error::NodeNoLabel($node))?
- ).unwrap()
+ // A convenient function to decide whether a node in the
+ // fragment matches the corresponding node in the builder.
+ fn children_match_p<T: GraphLabel>(
+ builder: &PLGBuilderMut<ForestLabel<T>>,
+ nodea: usize,
+ fragment: &DefaultForest<ForestLabel<T>>,
+ nodeb: usize,
+ ) -> Result<bool, Error> {
+ if builder.degree(nodea)? < fragment.degree(nodeb)? {
+ return Ok(false);
+ }
+
+ for (frag_child, builder_child) in fragment
+ .children_of(nodeb)?
+ .zip(builder.children_of(nodea)?)
+ {
+ let frag_label = fragment
+ .vertex_label(frag_child)?
+ .ok_or(Error::NodeNoLabel(frag_child))?
+ .label();
+ let builder_label = builder
+ .vertex_label(builder_child)?
+ .ok_or(Error::NodeNoLabel(builder_child))?
+ .label();
+
+ if frag_label != builder_label {
+ return Ok(false);
}
}
- );
+
+ Ok(true)
+ }
// 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 the relevant nodes and join the edges later.
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
- let mut used_nodes: Vec<bool> = std::iter::repeat(false).take(nodes_len).collect();
+ let root_label = fragment
+ .vertex_label(root)?
+ .ok_or(Error::NodeNoLabel(root))?;
- let mut stack = vec![root];
+ let f_root_label_packed = builder_query(&builder, root_label.label());
- while let Some(top) = stack.pop() {
- if used_nodes.get(top).copied() == Some(true) {
- continue;
+ if let Some((f_root, f_label, _)) = f_root_label_packed {
+ if f_root != node_id {
+ builder.add_edge(node_id, f_root, f_label)?;
}
+ } else {
+ let f_root =
+ builder.add_vertex(ForestLabel::new(root_label.label(), ForestLabelType::Plain));
- *used_nodes
- .get_mut(top)
- .ok_or(Error::IndexOutOfBounds(top, nodes_len))? = true;
-
- stack.extend(fragment.children_of(top)?);
+ builder.add_edge(node_id, f_root, root_label)?;
}
- let used_nodes = used_nodes;
+ if planted {
+ return Ok(());
+ }
- for node in (0..nodes_len).filter(|node| used_nodes.get(*node).copied() == Some(true)) {
- let label = fragment
+ 'node_loop: for node in 0..fragment_nodes_len {
+ let node_label = fragment
.vertex_label(node)?
.ok_or(Error::NodeNoLabel(node))?;
- builder.add_vertex(label);
- }
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
- // Don't forget to join the new sub-forest to the original
- // forest, at the specified position.
+ let f_node_label_packed = builder_query(builder.borrow(), node_label.label());
+
+ if let Some((f_node, _f_label, f_packed)) = f_node_label_packed {
+ match (node_label.is_packed(), f_packed) {
+ (false, false) => {
+ // case 2
+
+ if builder.is_empty_node(f_node)? {
+ for child in fragment.children_of(node)? {
+ let child_label = fragment
+ .vertex_label(child)?
+ .ok_or(Error::NodeNoLabel(child))?
+ .label();
+
+ if let Some((f_child, _, _)) =
+ builder_query(builder.borrow(), child_label)
+ {
+ builder.add_edge(f_node, f_child, node_label)?;
+ } else {
+ let f_child = builder.add_vertex(ForestLabel::new(
+ child_label,
+ ForestLabelType::Plain,
+ ));
+ builder.add_edge(f_node, f_child, node_label)?;
+ }
+ }
+ } else if !children_match_p(
+ builder.borrow(),
+ f_node,
+ fragment.borrow(),
+ node,
+ )? {
+ let cloned = self.clone_node(f_node, 0, false)?;
+
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+ for child in fragment.children_of(node)? {
+ let child_label = fragment
+ .vertex_label(child)?
+ .ok_or(Error::NodeNoLabel(child))?
+ .label();
+
+ if let Some((f_child, _, _)) =
+ builder_query(builder.borrow(), child_label)
+ {
+ builder.add_edge(cloned, f_child, node_label)?;
+ } else {
+ let f_child = builder.add_vertex(ForestLabel::new(
+ child_label,
+ ForestLabelType::Plain,
+ ));
+ builder.add_edge(cloned, f_child, node_label)?;
+ }
+ }
+ }
+ }
+ (true, false) => {
+ // case 3
+
+ if builder.is_empty_node(f_node)? {
+ for cloned_child in fragment.children_of(node)? {
+ let cloned = self.clone_node(f_node, 0, false)?;
+
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+ for child in fragment.children_of(cloned_child)? {
+ let child_label = fragment
+ .vertex_label(child)?
+ .ok_or(Error::NodeNoLabel(child))?;
+
+ let f_child =
+ builder_query(builder.borrow(), child_label.label());
+
+ if let Some((f_child, _, _)) = f_child {
+ builder.add_edge(cloned, f_child, child_label)?;
+ } else {
+ let f_child = builder.add_vertex(ForestLabel::new(
+ child_label.label(),
+ ForestLabelType::Plain,
+ ));
+
+ builder.add_edge(cloned, f_child, child_label)?;
+ }
+ }
+ }
+
+ continue 'node_loop;
+ }
+
+ for cloned_child in fragment.children_of(node)? {
+ let builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+ if !children_match_p(
+ builder.borrow(),
+ f_node,
+ fragment.borrow(),
+ cloned_child,
+ )? {
+ let cloned = self.clone_node(f_node, 0, false)?;
+
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+ for child in fragment.children_of(cloned_child)? {
+ let child_label = fragment
+ .vertex_label(child)?
+ .ok_or(Error::NodeNoLabel(child))?;
+
+ let f_child =
+ builder_query(builder.borrow(), child_label.label());
+
+ if let Some((f_child, _, _)) = f_child {
+ builder.add_edge(cloned, f_child, child_label)?;
+ } else {
+ let f_child = builder.add_vertex(ForestLabel::new(
+ child_label.label(),
+ ForestLabelType::Plain,
+ ));
+
+ builder.add_edge(cloned, f_child, child_label)?;
+ }
+ }
+ }
+ }
+ }
+ (false, true) => {
+ // case 4
+
+ let mut f_node_cloned_child = None;
+
+ for f_node_clone in builder.children_of(f_node)? {
+ f_node_cloned_child = Some(f_node_clone);
+
+ if builder.is_empty_node(f_node_clone)? {
+ for child in fragment.children_of(node)? {
+ let child_label = fragment
+ .vertex_label(child)?
+ .ok_or(Error::NodeNoLabel(child))?;
+
+ let f_child =
+ builder_query(builder.borrow(), child_label.label());
+
+ if let Some((f_child, _, _)) = f_child {
+ builder.add_edge(f_node_clone, f_child, child_label)?;
+ } else {
+ let f_child = builder.add_vertex(ForestLabel::new(
+ child_label.label(),
+ ForestLabelType::Plain,
+ ));
+
+ builder.add_edge(f_node_clone, f_child, child_label)?;
+ }
+ }
+
+ continue 'node_loop;
+ }
+
+ if children_match_p(
+ builder.borrow(),
+ f_node_clone,
+ fragment.borrow(),
+ node,
+ )? {
+ continue 'node_loop;
+ }
+ }
+
+ let f_node_cloned_child = if let Some(clone) = f_node_cloned_child {
+ clone
+ } else {
+ continue 'node_loop;
+ };
+
+ let cloned = self.clone_node(f_node_cloned_child, 0, false)?;
+
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+ for child in fragment.children_of(node)? {
+ let child_label = fragment
+ .vertex_label(child)?
+ .ok_or(Error::NodeNoLabel(child))?;
+
+ let f_child = builder_query(builder.borrow(), child_label.label());
+
+ if let Some((f_child, _, _)) = f_child {
+ builder.add_edge(cloned, f_child, child_label)?;
+ } else {
+ let f_child = builder.add_vertex(ForestLabel::new(
+ child_label.label(),
+ ForestLabelType::Plain,
+ ));
+
+ builder.add_edge(cloned, f_child, child_label)?;
+ }
+ }
+ }
+ (true, true) => {
+ // case 5
+
+ 'cloned_loop: for cloned_child in fragment.children_of(node)? {
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+ let mut f_node_cloned_child = None;
+
+ for f_node_clone in builder.children_of(f_node)? {
+ f_node_cloned_child = Some(f_node_clone);
+
+ if builder.is_empty_node(f_node_clone)? {
+ for child in fragment.children_of(cloned_child)? {
+ let child_label = fragment
+ .vertex_label(child)?
+ .ok_or(Error::NodeNoLabel(child))?;
+
+ let f_child =
+ builder_query(builder.borrow(), child_label.label());
+
+ if let Some((f_child, _, _)) = f_child {
+ builder.add_edge(f_node_clone, f_child, child_label)?;
+ } else {
+ let f_child = builder.add_vertex(ForestLabel::new(
+ child_label.label(),
+ ForestLabelType::Plain,
+ ));
+
+ builder.add_edge(f_node_clone, f_child, child_label)?;
+ }
+ }
+
+ continue 'node_loop;
+ }
+
+ if children_match_p(
+ builder.borrow(),
+ f_node_clone,
+ fragment.borrow(),
+ cloned_child,
+ )? {
+ continue 'cloned_loop;
+ }
+ }
+
+ let f_node_cloned_child = if let Some(clone) = f_node_cloned_child {
+ clone
+ } else {
+ continue 'cloned_loop;
+ };
+
+ let cloned = self.clone_node(f_node_cloned_child, 0, false)?;
+
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+ for child in fragment.children_of(cloned_child)? {
+ let child_label = fragment
+ .vertex_label(child)?
+ .ok_or(Error::NodeNoLabel(child))?;
+
+ let f_child = builder_query(builder.borrow(), child_label.label());
+
+ if let Some((f_child, _, _)) = f_child {
+ builder.add_edge(cloned, f_child, child_label)?;
+ } else {
+ let f_child = builder.add_vertex(ForestLabel::new(
+ child_label.label(),
+ ForestLabelType::Plain,
+ ));
+
+ builder.add_edge(cloned, f_child, child_label)?;
+ }
+ }
+ }
+ }
+ }
+ } else {
+ // case 1
- builder.add_edge(node_id, conversion!(root), root_label)?;
+ let f_node = builder
+ .add_vertex(ForestLabel::new(node_label.label(), ForestLabelType::Plain));
- // We can try to calculate the depth of fragments, if we need
- // to lower the memory usage. But in our use cases, we
- // usually deal with fragments where each node has at most one
- // child, so the depth is supposed to be equal to the length
- // in this case.
- let mut stack = Vec::with_capacity(fragment.nodes_len());
+ for child in fragment.children_of(node)? {
+ if child == node {
+ continue;
+ }
- stack.push(root);
+ let child_label_label = fragment
+ .vertex_label(child)?
+ .ok_or(Error::NodeNoLabel(child))?
+ .label();
- let mut seen_nodes = std::collections::HashSet::<usize>::new();
+ let f_child_label_packed = builder_query(builder.borrow(), child_label_label);
- while let Some(top) = stack.pop() {
- seen_nodes.insert(top);
+ if let Some((f_child, _, _)) = f_child_label_packed {
+ builder.add_edge(f_node, f_child, node_label)?;
+ } else {
+ let plain_label =
+ ForestLabel::new(child_label_label, ForestLabelType::Plain);
- for child in fragment.children_of(top)? {
- builder.add_edge(conversion!(top), conversion!(child), root_label)?;
+ let f_child = builder.add_vertex(plain_label);
- if !seen_nodes.contains(&child) {
- seen_nodes.insert(child);
- stack.push(child);
+ builder.add_edge(f_node, f_child, node_label)?;
+ }
}
}
}
@@ -459,7 +838,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
// Make sure it only has one parent, which is the
// representative node.
- // assert_eq!(parents.len(), 1);
+ assert_eq!(parents.len(), 1);
// We checked its length is 1, so it is safe to unwrap
// here.
@@ -899,6 +1278,28 @@ pub(crate) use leaf;
#[cfg(test)]
mod item_test {
use super::*;
+ use graph::Graph;
+
+ fn make_forest_1() -> Result<DefaultForest<ForestLabel<usize>>, Box<dyn std::error::Error>> {
+ let mut result = leaf!(0);
+
+ for i in 1..5 {
+ result.plant(0, leaf!(i), false)?;
+ }
+
+ for i in 5..10 {
+ result.plant(2, leaf!(i), false)?;
+ }
+
+ result.plant(4, leaf!(10), false)?;
+ result.plant(4, leaf!(11), false)?;
+
+ let clone = result.clone_node(4, 1, false)?;
+
+ result.plant(clone, leaf!(12), false)?;
+
+ Ok(result)
+ }
#[test]
fn test_forest_api() -> Result<(), Box<dyn std::error::Error>> {
@@ -963,6 +1364,7 @@ mod item_test {
test_forest.plant(0, leaf!(5), false)?;
assert!(forest.is_prefix(2, &test_forest)?);
+ assert!(!forest.is_prefix(0, &test_forest)?);
// now test cloning
@@ -991,6 +1393,132 @@ mod item_test {
}
#[test]
+ fn test_case_1() -> Result<(), Box<dyn std::error::Error>> {
+ let mut forest = make_forest_1()?;
+
+ let mut test_forest = leaf!(0);
+ test_forest.plant(0, leaf!(13), false)?;
+
+ assert_eq!(forest.is_prefix(0, &test_forest), Ok(false));
+
+ forest.plant(0, leaf!(13), false)?;
+
+ assert_eq!(forest.degree(0), Ok(5));
+
+ Ok(())
+ }
+
+ #[test]
+ fn test_case_2() -> Result<(), Box<dyn std::error::Error>> {
+ let mut forest = make_forest_1()?;
+
+ let mut test_forest = leaf!(0);
+ test_forest.plant(0, leaf!(9), false)?;
+
+ assert_eq!(forest.is_prefix(0, test_forest), Ok(false));
+
+ forest.plant(0, leaf!(9), false)?;
+
+ assert_eq!(forest.degree(0), Ok(5));
+
+ assert_eq!(forest.children_of(0)?.nth(4), Some(9));
+
+ Ok(())
+ }
+
+ #[test]
+ fn test_case_3() -> Result<(), Box<dyn std::error::Error>> {
+ let mut forest = make_forest_1()?;
+
+ let mut test_forest = leaf!(2);
+
+ test_forest.plant(0, leaf!(5), false)?;
+
+ let clone = test_forest.clone_node(0, 0, false)?;
+
+ test_forest.plant(clone, leaf!(6), false)?;
+
+ assert_eq!(forest.is_prefix(0, &test_forest), Ok(false));
+
+ let mut answer = forest.clone();
+
+ forest.plant(0, test_forest, false)?;
+
+ let clone = answer.clone_node(2, 0, false)?;
+
+ answer.plant(clone, leaf!(6), false)?;
+
+ assert_eq!(forest, answer);
+
+ Ok(())
+ }
+
+ #[test]
+ fn test_case_4() -> Result<(), Box<dyn std::error::Error>> {
+ let mut forest = make_forest_1()?;
+
+ let mut test_forest = leaf!(4);
+
+ test_forest.plant(0, leaf!(10), false)?;
+ test_forest.plant(0, leaf!(12), false)?;
+
+ assert_eq!(forest.is_prefix(12, &test_forest), Ok(true));
+
+ let answer = forest.clone();
+
+ forest.plant(0, test_forest, false)?;
+
+ assert_eq!(forest, answer);
+
+ let mut test_forest = leaf!(4);
+
+ test_forest.plant(0, leaf!(10), false)?;
+ test_forest.plant(0, leaf!(9), false)?;
+
+ assert_eq!(forest.is_prefix(12, &test_forest), Ok(false));
+
+ let mut answer = forest.clone();
+
+ forest.plant(0, test_forest, false)?;
+
+ let clone = answer.clone_node(4, 1, false)?;
+
+ answer.plant(clone, leaf!(9), false)?;
+
+ assert_eq!(forest, answer);
+
+ Ok(())
+ }
+
+ #[test]
+ fn test_case_5() -> Result<(), Box<dyn std::error::Error>> {
+ let mut forest = make_forest_1()?;
+
+ let mut test_forest = leaf!(4);
+
+ test_forest.plant(0, leaf!(10), false)?;
+ test_forest.plant(0, leaf!(12), false)?;
+
+ let clone = test_forest.clone_node(0, 1, false)?;
+
+ test_forest.plant(clone, leaf!(9), false)?;
+
+ assert_eq!(forest.is_prefix(12, &test_forest), Ok(false));
+
+ let mut answer = forest.clone();
+
+ forest.plant(0, test_forest, false)?;
+
+ let clone = answer.clone_node(4, 1, false)?;
+
+ answer.plant(clone, leaf!(9), false)?;
+
+ assert_eq!(forest, answer);
+
+ Ok(())
+ }
+
+ #[test]
fn test_eq() -> Result<(), Box<dyn std::error::Error>> {
let mut forest = leaf!(0, usize);
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index da13c56..c9d9c5a 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -657,7 +657,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
} else if labela.clone_index().is_some() {
let mut parentsa = self.parents_of(nodea)?;
- // assert_eq!(parentsa.len(), 1);
+ assert_eq!(parentsa.len(), 1);
let parenta = parentsa.next().unwrap().node();