summaryrefslogtreecommitdiff
path: root/nfa/src/default/nfa.rs
diff options
context:
space:
mode:
Diffstat (limited to 'nfa/src/default/nfa.rs')
-rw-r--r--nfa/src/default/nfa.rs120
1 files changed, 120 insertions, 0 deletions
diff --git a/nfa/src/default/nfa.rs b/nfa/src/default/nfa.rs
new file mode 100644
index 0000000..3c2bd83
--- /dev/null
+++ b/nfa/src/default/nfa.rs
@@ -0,0 +1,120 @@
+//! This file provides a default implementation of NFA.
+
+// TODO: Store the regular expression in the NFA as well.
+//
+// The current focus of the project is to understand the growth rate
+// of the algorithm, to know whether I made a mistake in the previous
+// iteration of the implementation, or the algorithm is not as fast as
+// the author estimated, which is not quite likely, of course.
+//
+// Thus I shall establish a friendly interface that allows me to view
+// and debug the atomic languages and the languages, transparently.
+
+use graph::{error::Error as GError, DLGraph, Graph, GraphLabel, LabelGraph};
+
+use crate::{error::Error, Nfa, Regex};
+
+use std::fmt::Display;
+
+#[non_exhaustive]
+#[derive(Debug)]
+/// Default NFA implementation.
+pub struct DefaultNFA<T: GraphLabel + Display> {
+ graph: DLGraph<T>,
+}
+
+impl<T: GraphLabel + Display> Default for DefaultNFA<T> {
+ fn default() -> Self {
+ Self {
+ graph: Default::default(),
+ }
+ }
+}
+
+impl<T: GraphLabel + Display> Graph for DefaultNFA<T> {
+ type Iter<'a> = <DLGraph<T> as Graph>::Iter<'a> where T: 'a;
+
+ #[inline]
+ fn is_empty(&self) -> bool {
+ self.graph.is_empty()
+ }
+
+ #[inline]
+ fn nodes_len(&self) -> usize {
+ self.graph.nodes_len()
+ }
+
+ #[inline]
+ fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GError> {
+ self.graph.children_of(node_id)
+ }
+
+ #[inline]
+ fn degree(&self, node_id: usize) -> Result<usize, GError> {
+ self.graph.degree(node_id)
+ }
+
+ #[inline]
+ fn is_empty_node(&self, node_id: usize) -> Result<bool, GError> {
+ self.graph.is_empty_node(node_id)
+ }
+
+ #[inline]
+ fn has_edge(&self, source: usize, target: usize) -> Result<bool, GError> {
+ self.graph.has_edge(source, target)
+ }
+}
+
+impl<T: GraphLabel + Display> LabelGraph<T> for DefaultNFA<T> {
+ type Iter<'a> = <DLGraph<T> as LabelGraph<T>>::Iter<'a> where T: 'a;
+
+ type LabelIter<'a> = <DLGraph<T> as LabelGraph<T>>::LabelIter<'a> where T: 'a;
+
+ // TODO: Return the label from the contained regular language.
+ #[inline]
+ fn vertex_label(&self, node_id: usize) -> Result<Option<T>, GError> {
+ if self.has_node(node_id) {
+ todo!()
+ } else {
+ Err(GError::IndexOutOfBounds(node_id, self.nodes_len()))
+ }
+ }
+
+ #[inline]
+ fn edge_label(&self, source: usize, target: usize) -> Result<Vec<T>, GError> {
+ self.graph.edge_label(source, target)
+ }
+
+ #[inline]
+ fn find_children_with_label(
+ &self,
+ node_id: usize,
+ label: &T,
+ ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, GError> {
+ self.graph.find_children_with_label(node_id, label)
+ }
+
+ #[inline]
+ fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, GError> {
+ self.graph.labels_of(node_id)
+ }
+}
+
+impl<T: GraphLabel + Display> Nfa<T> for DefaultNFA<T> {
+ #[allow(unused)]
+ fn to_nfa(regex: impl Regex<T>) -> Self {
+ todo!()
+ }
+
+ fn remove_epsilon(&mut self) -> Result<(), Error> {
+ todo!()
+ }
+
+ fn remove_dead(&mut self) -> Result<(), Error> {
+ todo!()
+ }
+
+ fn nulling(&mut self) -> Result<(), Error> {
+ todo!()
+ }
+}