summaryrefslogtreecommitdiff
path: root/forest/src/default.rs
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-01-11 23:47:26 +0800
committerJSDurand <mmemmew@gmail.com>2023-01-11 23:47:26 +0800
commit1a3d346f413325ed37848a6b2526e8e729269833 (patch)
treeab8812f8094d096c68aee53cf516e986cc9a273a /forest/src/default.rs
parentf27d604d93ce583d4404e1874664e08382ea2f00 (diff)
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".
Diffstat (limited to 'forest/src/default.rs')
-rw-r--r--forest/src/default.rs144
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>,
+// }