From 8f8d3d1a3c276be4be2e5d2e767ada564c47279a Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Fri, 13 Jan 2023 14:26:28 +0800
Subject: forest seems to be completed

I seem to have finished the implementation of forests.  Now it remains
the implementation of the chain-rule machine, of which I have a rough
plan now.
---
 forest/src/lib.rs | 81 +++++++++++++++++--------------------------------------
 1 file changed, 25 insertions(+), 56 deletions(-)

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

diff --git a/forest/src/lib.rs b/forest/src/lib.rs
index c2f4988..f843bc1 100644
--- a/forest/src/lib.rs
+++ b/forest/src/lib.rs
@@ -11,57 +11,7 @@
 //! out-coming and in-coming plugs.  These plugs are used to join
 //! different fragments of forests together.
 
-use graph::{GraphLabel, LabelGraph, ParentsGraph};
-
-use core::fmt::Display;
-
-// TODO: move this to default
-
-/// The type of errors for forest operations.
-#[derive(Debug)]
-pub enum Error {
-    /// An index is out of bounds.
-    IndexOutOfBounds(usize, usize),
-}
-
-impl Display for Error {
-    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        match self {
-            Error::IndexOutOfBounds(index, bound) => {
-                write!(f, "index {index} is out of bound {bound}")
-            }
-        }
-    }
-}
-
-impl std::error::Error for Error {}
-
-// /// A builder of a forest.
-// pub trait ForestBuilder<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> {
-//     /// The type of the resulting forest.
-//     type Output: Forest<NodeLabel, EdgeLabel>;
-
-//     /// Construct a new builder with only one node with the given
-//     /// label.
-//     fn new_leaf(label: NodeLabel) -> Self;
-
-//     /// Add a child to the builder the given labels for the new node
-//     /// and the added edge.
-//     ///
-//     /// All plug-out nodes within the builder should have a new child
-//     /// with the specified labels, and hence multiple children might
-//     /// be added, and the plug-out nodes should be modified
-//     /// accordingly.
-//     fn add_children(&mut self, vertex_label: NodeLabel, edge_labe: EdgeLabel);
-
-//     /// Build the forest.
-//     fn build(self) -> Self::Output;
-
-//     /// Build the forest from a reference.
-//     fn build_ref(&self) -> Self::Output;
-// }
-
-// FIXME: The trait should be re-designed.
+use graph::{error::Error as GError, GraphLabel, LabelGraph, ParentsGraph};
 
 /// The expected behaviours of a forest.
 ///
@@ -69,19 +19,38 @@ impl std::error::Error for Error {}
 /// labelled graphs.
 pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<T> {
     /// The type of errors for operations on the forest.
-    type Error: std::error::Error + From<graph::error::Error>;
+    type Error: std::error::Error + From<GError>;
+
+    /// Return the root of the forest.
+    ///
+    /// A forest without a root is regarded as empty.
+    fn root(&self) -> Option<usize>;
+
+    /// Construct a forest consisting of one leaf node with the given
+    /// label.
+    fn new_leaf(label: T) -> Self;
 
     /// Detect if the fragment is a prefix of the sub-forest rooted at
     /// `node_id`.
-    fn is_prefix<F: AsRef<Self>>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>;
+    fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>
+    where
+        F: AsRef<Self>;
 
     /// Extend the forest by adjoining another forest at a given node.
-    fn plant<F: AsRef<Self>>(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error>;
+    fn plant<F>(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error>
+    where
+        F: AsRef<Self>;
 
     /// 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.
-    fn clone(&mut self, node_id: usize) -> Result<(), Self::Error>;
+    /// node, and the new node points to the old node.  Return the
+    /// index of the new node.
+    ///
+    /// 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;
 }
 
 pub mod default;
-- 
cgit v1.2.3-18-g5258