summaryrefslogtreecommitdiff
path: root/forest
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-01-22 11:49:47 +0800
committerJSDurand <mmemmew@gmail.com>2023-01-22 11:49:47 +0800
commite8ea01319b3a9032a3f4f69f65e9ca96562b87b9 (patch)
tree674e7337dce0b9433b9ddfe745b0cf82f528d3ec /forest
parent973c789dae479dd8383b0f7f9cfa5f167fdf3d38 (diff)
forest: clone correctly
Now the forest can detect if a node is packed or cloned, and correctly clones a node in those circumstances. But it still needs to be tested.
Diffstat (limited to 'forest')
-rw-r--r--forest/src/default.rs70
-rw-r--r--forest/src/lib.rs147
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;