diff options
Diffstat (limited to 'chain/src/item/default/mod.rs')
-rw-r--r-- | chain/src/item/default/mod.rs | 47 |
1 files changed, 40 insertions, 7 deletions
diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs index 7ecc70d..1a00368 100644 --- a/chain/src/item/default/mod.rs +++ b/chain/src/item/default/mod.rs @@ -267,6 +267,11 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { let mut self_stack = Vec::with_capacity(fragment.nodes_len()); + use std::collections::HashSet; + + 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 { @@ -281,24 +286,46 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { 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); + frag_stack.pop(); self_stack.pop(); if fragment.vertex_label(frag_top)? != self.vertex_label(self_top)? { // not a prefix + dbg!( + frag_top, + self_top, + fragment.vertex_label(frag_top)?, + self.vertex_label(self_top)? + ); return Ok(false); } - let mut self_children = self.children_of(self_top)?; + let self_children = self.children_of(self_top)?; + let frag_children = fragment.children_of(frag_top)?; + + 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); + } - for child in fragment.children_of(frag_top)? { - if let Some(self_child) = self_children.next() { - frag_stack.push(child); - self_stack.push(self_child); - } else { - // too few children + 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!(); return Ok(false); } + + frag_stack.push(frag_child); + self_stack.push(self_child); } } @@ -425,6 +452,8 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { return Err(ForestLabelError::ClonePack.into()); } + let is_root_p = self.root() == Some(node_id); + // We are sure old_label is not packed here, so it is safe to // unwrap. let new_label = old_label @@ -473,6 +502,10 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { // Make a new node let new_index = builder.add_vertex(rep_label); + if is_root_p { + self.root = Some(new_index); + } + // Re-direct parents to the new node. // // This must be done before pointing the new node to the old |