Record left-linear expansion and forest format

Now the grammar will record the left-linear expansions when generating
the nondeterministic finite automaton frmo its rules, and will record
whether an edge in the nondeterministic finite automaton comes from a
left-linear expansion.  The latter is needed because while performing
a chain-rule derivation, we do not need the left-linear expanded
derivations in the "first layer".  This might well have been the root
cause of the bad performance of the previous version of this package.

Also I have figured out how to properly generate and handle parse
forests while manipulating the "chain-rule machine".

1 files changed, 12 insertions, 132 deletions

diff --git a/forest/src/default.rs b/forest/src/default.rs
index 5e438d4..d3970e9 100644
--- a/forest/src/default.rs
+++ b/forest/src/default.rs
@@ -1,141 +1,21 @@
 //! This file provides a default implementation for the
 //! [`Forest`][crate::Forest] trait.
 
+#[allow(unused_imports)]
 use super::*;
+#[allow(unused_imports)]
 use graph::{error::Error as GraphError, ALGraph, Graph};
 
+#[allow(unused_imports)]
 use std::collections::{hash_set::Iter, HashMap, HashSet};
 
-#[derive(Debug, Clone)]
-pub struct DefaultForest<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> {
-    graph: ALGraph,
-    vertex_labels: HashMap<usize, NodeLabel>,
-    edge_labels: HashMap<(usize, usize), EdgeLabel>,
-    plugins: HashSet<usize>,
-    plugouts: HashSet<usize>,
-}
+// TODO: Use PLGraph instead.
 
-impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> Default for DefaultForest<NodeLabel, EdgeLabel> {
-    fn default() -> Self {
-        Self {
-            graph: Default::default(),
-            vertex_labels: Default::default(),
-            edge_labels: Default::default(),
-            plugins: Default::default(),
-            plugouts: Default::default(),
-        }
-    }
-}
-
-impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> Graph for DefaultForest<NodeLabel, EdgeLabel> {
-    type Iter<'a> = <ALGraph as Graph>::Iter<'a>
-    where
-        Self: 'a;
-
-    fn is_empty(&self) -> bool {
-        self.graph.is_empty()
-    }
-
-    fn nodes_len(&self) -> usize {
-        self.graph.nodes_len()
-    }
-
-    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GraphError> {
-        self.graph.children_of(node_id)
-    }
-
-    fn degree(&self, node_id: usize) -> Result<usize, GraphError> {
-        self.graph.degree(node_id)
-    }
-
-    fn is_empty_node(&self, node_id: usize) -> Result<bool, GraphError> {
-        self.graph.is_empty_node(node_id)
-    }
-
-    fn has_edge(&self, source: usize, target: usize) -> Result<bool, GraphError> {
-        self.graph.has_edge(source, target)
-    }
-
-    fn replace_by_builder(&mut self, _builder: impl graph::Builder<Result = Self>) {
-        unimplemented!()
-    }
-}
-
-#[derive(Debug)]
-pub struct LabelIter<'a> {
-    set_iter: Iter<'a, usize>,
-}
-
-impl<'a> Iterator for LabelIter<'a> {
-    type Item = usize;
-
-    fn next(&mut self) -> Option<Self::Item> {
-        self.set_iter.next().copied()
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.set_iter.size_hint()
-    }
-}
-
-impl<'a> ExactSizeIterator for LabelIter<'a> {
-    fn len(&self) -> usize {
-        self.set_iter.len()
-    }
-}
-
-impl<'a> From<Iter<'a, usize>> for LabelIter<'a> {
-    fn from(set_iter: Iter<'a, usize>) -> Self {
-        Self { set_iter }
-    }
-}
-
-impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> Forest<NodeLabel, EdgeLabel>
-    for DefaultForest<NodeLabel, EdgeLabel>
-{
-    type PluginIter<'a> = LabelIter<'a>
-    where
-        Self: 'a;
-
-    type PlugoutIter<'a> = LabelIter<'a>
-    where
-        Self: 'a;
-
-    fn plugins(&self) -> Self::PluginIter<'_> {
-        self.plugins.iter().into()
-    }
-
-    fn plugouts(&self) -> Self::PlugoutIter<'_> {
-        self.plugouts.iter().into()
-    }
-
-    fn plug(&mut self, other: &Self) -> Result<(), Error> {
-        // PLAN: Produce a BuilderMut, adjust the indices for edges,
-        // and then add edges between plugs.
-        //
-        // Since I cannot touch the underlying nodes directly, I have
-        // to add the nodes and edges individually.
-
-        todo!()
-    }
-
-    fn vertex_label(&self, node_id: usize) -> Result<Option<NodeLabel>, Error> {
-        if node_id >= self.nodes_len() {
-            return Err(Error::IndexOutOfBounds(node_id, self.nodes_len()));
-        }
-
-        Ok(self.vertex_labels.get(&node_id).copied())
-    }
-
-    fn edge_label(&self, source: usize, target: usize) -> Result<Option<EdgeLabel>, Error> {
-        if source >= self.nodes_len() {
-            return Err(Error::IndexOutOfBounds(source, self.nodes_len()));
-        }
-
-        if target >= self.nodes_len() {
-            return Err(Error::IndexOutOfBounds(target, self.nodes_len()));
-        }
-
-        Ok(self.edge_labels.get(&(source, target)).copied())
-    }
-}
+// #[derive(Debug, Clone)]
+// pub struct DefaultForest<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> {
+//     graph: ALGraph,
+//     vertex_labels: HashMap<usize, NodeLabel>,
+//     edge_labels: HashMap<(usize, usize), EdgeLabel>,
+//     plugins: HashSet<usize>,
+//     plugouts: HashSet<usize>,
+// }