1 files changed, 105 insertions, 0 deletions
diff --git a/forest/src/lib.rs b/forest/src/lib.rs
new file mode 100644
index 0000000..527a78c
--- /dev/null
+++ b/forest/src/lib.rs
@@ -0,0 +1,105 @@
+//! This file defines the expected behaviours of forests, and provides
+//! a default implementation for forests.
+//!
+//! The default forest actually implements the so-called shared packed
+//! parse forest, or SPPF.  It packs sub-trees with the same parents
+//! under the same branch, and lets nodes from different branches
+//! share the same children, and hence the name.
+//!
+//! What is special here is that the forests are marked with some
+//! out-coming and in-coming plugs.  These plugs are used to join
+//! different fragments of forests together.
+
+use graph::{ExtGraph, GraphLabel};
+
+use core::fmt::Display;
+
+#[derive(Debug)]
+pub enum Error {
+    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;
+}
+
+/// 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>: ExtGraph {
+    /// 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>;
+}
+
+pub mod default;