From e8ea01319b3a9032a3f4f69f65e9ca96562b87b9 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Sun, 22 Jan 2023 11:49:47 +0800
Subject: 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.
---
 forest/src/lib.rs | 147 +++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 139 insertions(+), 8 deletions(-)

(limited to 'forest/src/lib.rs')

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;
-- 
cgit v1.2.3-18-g5258