diff options
| -rw-r--r-- | chain/src/archive.txt | 98 | ||||
| -rw-r--r-- | chain/src/item/default/mod.rs | 792 | ||||
| -rw-r--r-- | chain/src/item/default/splone.rs | 2 |
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(); |