1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
//! This file provides a structure that implements the trait
//! [`NFA`][super::Nfa].
//!
//! It is used as the default implementation.
use graph::{error::Error as GError, DLGraph, Graph, GraphLabel, LabelGraph};
use super::{error::Error, Nfa, Regex};
// 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.
#[non_exhaustive]
#[derive(Debug)]
/// Default NFA implementation.
pub struct DefaultNFA<T: GraphLabel> {
graph: DLGraph<T>,
}
impl<T: GraphLabel> Default for DefaultNFA<T> {
fn default() -> Self {
let graph = Default::default();
Self { graph }
}
}
impl<T: GraphLabel> 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> 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> 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!()
}
}
#[cfg(test)]
mod default_nfa_test {}
|
