diff options
Diffstat (limited to 'forest/src')
| -rw-r--r-- | forest/src/default.rs | 70 | ||||
| -rw-r--r-- | forest/src/lib.rs | 147 |
2 files changed, 188 insertions, 29 deletions
diff --git a/forest/src/default.rs b/forest/src/default.rs index 9295f1a..b96439f 100644 --- a/forest/src/default.rs +++ b/forest/src/default.rs @@ -24,6 +24,8 @@ pub enum Error { /// Encounter an invalid error in converting from an error of /// graphs. InvalidGraphError(GError), + /// Encounter an error when converting forest labels. + LabelConversion(ForestLabelError), } impl Display for Error { @@ -35,6 +37,7 @@ impl Display for Error { Error::DuplicatedNode(n) => write!(f, "node {n} is duplicated"), Error::InvalidGraphError(ge) => write!(f, "invalid error: {ge}"), Error::NodeNoLabel(n) => write!(f, "node {n} has no labels, but it should have one"), + Error::LabelConversion(le) => write!(f, "fail to convert labels: {le}"), } } } @@ -51,6 +54,12 @@ impl From<GError> for Error { } } +impl From<ForestLabelError> for Error { + fn from(le: ForestLabelError) -> Self { + Self::LabelConversion(le) + } +} + /// A default implementation of forest. #[derive(Debug, Clone)] pub struct DefaultForest<T: GraphLabel> { @@ -193,7 +202,7 @@ impl<T: GraphLabel> LabelGraph<T> for DefaultForest<T> { } } -impl<T: GraphLabel> Forest<T> for DefaultForest<T> { +impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { type Error = Error; fn root(&self) -> Option<usize> { @@ -205,7 +214,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<T> { let mut builder = PLGBuilderMut::from_graph_mut(&mut graph); - let root = Some(builder.add_vertex(label)); + let root = Some(builder.add_vertex(ForestLabel::from(label))); Self { graph, root } } @@ -299,12 +308,12 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<T> { 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. + /// 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) => { { @@ -360,20 +369,37 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<T> { Ok(()) } - fn clone_node<F>(&mut self, node_id: usize, clone_transform: F) -> Result<usize, Self::Error> - where - F: Fn(T) -> T, - { - let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + fn clone_node(&mut self, node_id: usize) -> Result<usize, Self::Error> { + let builder = PLGBuilderMut::from_graph_mut(&mut self.graph); let old_label = builder .vertex_label(node_id)? .ok_or(Error::NodeNoLabel(node_id))?; - let new_label = clone_transform(old_label); + if old_label.is_packed() { + return Err(ForestLabelError::ClonePack.into()); + } + + if old_label.is_cloned().is_some() { + let mut parents = self.parents_of(node_id)?; + + // Make sure it only has one parent, which is the + // representative node. + assert_eq!(parents.len(), 1); + + // We checked its length is 1, so it is safe to unwrap + // here. + return Ok(parents.next().unwrap().node()); + } + + let rep_label = old_label.pack()?; + + let new_label = old_label.clone(self)?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); // Make a new node - let new_index = builder.add_vertex(new_label); + let new_index = builder.add_vertex(rep_label); // Re-direct parents to the new node. // @@ -393,6 +419,10 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<T> { builder.add_edge(new_index, node_id, old_label)?; + // Modify the label of the old node. + + builder.set_label(node_id, new_label)?; + Ok(new_index) } } @@ -403,10 +433,10 @@ mod forest_test { macro_rules! leaf ( ($label:expr, $type:tt) =>{ - DefaultForest::<$type>::new_leaf($label) + DefaultForest::<ForestLabel<$type>>::new_leaf($label) }; ($label:expr) => { - DefaultForest::<usize>::new_leaf($label) + DefaultForest::<ForestLabel<usize>>::new_leaf($label) } ); @@ -479,11 +509,9 @@ mod forest_test { // add a duplicate label forest.plant(3, leaf!(5), false)?; - let len = forest.nodes_len(); - - let clone_transform = |label| label + len; + let _len = forest.nodes_len(); - forest.clone_node(5, clone_transform)?; + forest.clone_node(5)?; assert_eq!(forest.nodes_len(), 7); diff --git a/forest/src/lib.rs b/forest/src/lib.rs index 8c9b918..02c5fcd 100644 --- a/forest/src/lib.rs +++ b/forest/src/lib.rs @@ -13,13 +13,144 @@ use graph::{error::Error as GError, GraphLabel, LabelGraph, ParentsGraph}; +/// An internal type that indicates the status of a node as either a +/// packed, cloned, or plain node. +#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)] +enum ForestLabelType { + Packed, + #[default] + Plain, + Cloned(usize), +} + +impl core::fmt::Display for ForestLabelType { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + match self { + Self::Packed => write!(f, "packed"), + Self::Plain => write!(f, "plain"), + Self::Cloned(index) => write!(f, "the {index}-th clone"), + } + } +} + +/// A type that encodes the properties demanded by a forest. +#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)] +pub struct ForestLabel<T: GraphLabel> { + label: T, + status: ForestLabelType, +} + +impl<T: GraphLabel> core::fmt::Display for ForestLabel<T> { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + writeln!(f, "label: {}, status: {}", self.label, self.status) + } +} + +/// The type of erros for converting forest labels. +#[non_exhaustive] +#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)] +pub enum ForestLabelError { + /// Try to pack a cloned node. + PackClone, + /// Try to clone a packed node. + ClonePack, +} + +impl core::fmt::Display for ForestLabelError { + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { + match self { + Self::PackClone => write!(f, "cannot pack a cloned node"), + Self::ClonePack => write!(f, "cannot clone a packed node"), + } + } +} + +impl std::error::Error for ForestLabelError {} + +impl<T: GraphLabel> ForestLabel<T> { + /// Retrieve the label. + pub fn label(&self) -> T { + self.label + } + + /// Return true if and only if this node is packed. + pub fn is_packed(&self) -> bool { + matches!(self.status, ForestLabelType::Packed) + } + + /// Retrieve the optional clone index. + pub fn is_cloned(&self) -> Option<usize> { + match self.status { + ForestLabelType::Cloned(index) => Some(index), + _ => None, + } + } + + /// Try to clone a node. + pub fn clone<F>(self, forest: &F) -> Result<Self, ForestLabelError> + where + F: Forest<T>, + { + if self.is_packed() { + Err(ForestLabelError::ClonePack) + } else { + let clone_index = if let Some(old_index) = self.is_cloned() { + let mut new_index: usize = old_index + 1; + + let mut new_label = Self { + status: ForestLabelType::Cloned(new_index), + ..self + }; + + while forest.query_label(new_label).is_some() { + new_index += 1; + new_label = Self { + status: ForestLabelType::Cloned(new_index), + ..self + }; + } + + new_index + } else { + 0 + }; + + Ok(Self { + status: ForestLabelType::Cloned(clone_index), + ..self + }) + } + } + + /// Try to pack a node. + pub fn pack(self) -> Result<Self, ForestLabelError> { + if self.is_cloned().is_some() { + Err(ForestLabelError::PackClone) + } else { + let new_label = Self { + status: ForestLabelType::Packed, + ..self + }; + + Ok(new_label) + } + } +} + +impl<T: GraphLabel> From<T> for ForestLabel<T> { + fn from(label: T) -> Self { + let status = ForestLabelType::default(); + Self { label, status } + } +} + /// The expected behaviours of a forest. /// /// Note that it requires only a subset of the functionalities of /// labelled graphs. -pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<T> { +pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> { /// The type of errors for operations on the forest. - type Error: std::error::Error + From<GError>; + type Error: std::error::Error + From<GError> + From<ForestLabelError>; /// Return the root of the forest. /// @@ -44,13 +175,13 @@ pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<T> { /// Clone a node by making a new node and making all the nodes /// that previously pointed to the old node now point to the new /// node, and the new node points to the old node. Return the - /// index of the new node. + /// index of the new node. In addition, if the old node had + /// already been cloned, just return the index of its + /// representitave. /// - /// The label of the new node will be given by the label - /// transformer. - fn clone_node<F>(&mut self, node_id: usize, clone_transform: F) -> Result<usize, Self::Error> - where - F: Fn(T) -> T; + /// The labels of the representing node and of the cloned node + /// will be handled automatically. + fn clone_node(&mut self, node_id: usize) -> Result<usize, Self::Error>; } pub mod default; |