1 files changed, 49 insertions, 67 deletions

diff --git a/forest/src/lib.rs b/forest/src/lib.rs
index 3925bd5..c2f4988 100644
--- a/forest/src/lib.rs
+++ b/forest/src/lib.rs
@@ -1,3 +1,4 @@
+#![warn(missing_docs)]
 //! This file defines the expected behaviours of forests, and provides
 //! a default implementation for forests.
 //!
@@ -10,12 +11,16 @@
 //! out-coming and in-coming plugs.  These plugs are used to join
 //! different fragments of forests together.
 
-use graph::{Graph, GraphLabel};
+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),
 }
 
@@ -31,75 +36,52 @@ impl Display for Error {
 
 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;
-}
+// /// 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.
 
 /// The expected behaviours of a forest.
 ///
-/// Note that it contains a "striped down" version of the labelled
-/// graphs.
-pub trait Forest<NodeLabel: GraphLabel, EdgeLabel: GraphLabel>: Graph {
-    /// Type of iterator of plug-in nodes.
-    type PluginIter<'a>: Iterator<Item = usize> + 'a
-    where
-        Self: 'a;
-
-    /// Type of iterator of plug-out nodes.
-    type PlugoutIter<'a>: Iterator<Item = usize> + 'a
-    where
-        Self: 'a;
-
-    /// Return the plug-in nodes
-    fn plugins(&self) -> Self::PluginIter<'_>;
-
-    /// Return the plug-out nodes
-    fn plugouts(&self) -> Self::PlugoutIter<'_>;
-
-    /// Plug another forest onto this forest.
-    ///
-    /// The plug-out nodes of this forest will be joined onto the
-    /// plug-in nodes of the joining forest.
-    ///
-    /// # Performance warning
-    ///
-    /// It is recommended to only call this function with a "small"
-    /// `other`, as this function might copy the whole graph
-    /// individually, node by node and edge by edge.
-    fn plug(&mut self, other: &Self) -> Result<(), Error>;
-
-    /// Return the vertex label.
-    ///
-    /// A vertex may not have labels.
-    fn vertex_label(&self, node_id: usize) -> Result<Option<NodeLabel>, Error>;
-
-    /// Return the edge label.
-    ///
-    /// An edge may have no labels.  If there is no edge from the
-    /// given source to the given target, then `Ok(None)` is returned
-    /// as well.
-    fn edge_label(&self, source: usize, target: usize) -> Result<Option<EdgeLabel>, Error>;
+/// Note that it requires only a subset of the functionalities of
+/// 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>;
+
+    /// 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>;
+
+    /// 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>;
+
+    /// 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>;
 }
 
 pub mod default;