1 files changed, 84 insertions, 14 deletions

diff --git a/chain/src/lib.rs b/chain/src/lib.rs
index 745ad5a..a7740c2 100644
--- a/chain/src/lib.rs
+++ b/chain/src/lib.rs
@@ -64,12 +64,59 @@ impl core::fmt::Display for Edge {
     }
 }
 
-// TODO: Define an enumeration that stands for either an edge or a
-// "phantom" edge.
-//
-// A phantom edge will be ignored when adding edges.  The phantom
-// edges will be used to determine the acceptance of a node, when and
-// only when that new node turns out to have no children.
+/// A Real Or Imaginary edge.
+///
+/// An imaginary edge will be ignored when adding edges.  The
+/// imaginary edges will be used to determine the acceptance of a
+/// node, when and only when that new node turns out to have no
+/// children.
+///
+/// # Note
+///
+/// Non, je ne suis pas un roi.  Je ne sais pas qu'est-ce que vous
+/// parlez.
+#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
+pub enum Roi {
+    /// A real edge is an ordinary edge.
+    Re(Edge),
+    /// The label of an imaginary edge is not important, so we only
+    /// record its target.
+    Im(usize),
+}
+
+// Some convenient conversions
+
+impl From<Edge> for Roi {
+    fn from(edge: Edge) -> Self {
+        Self::Re(edge)
+    }
+}
+
+impl From<usize> for Roi {
+    fn from(target: usize) -> Self {
+        Self::Im(target)
+    }
+}
+
+impl Roi {
+    /// Return the real part if it is a real edge.
+    fn real_part(self) -> Option<Edge> {
+        if let Self::Re(edge) = self {
+            Some(edge)
+        } else {
+            None
+        }
+    }
+
+    /// Return the imaginary part if it is an imaginary edge.
+    fn imaginary_part(self) -> Option<usize> {
+        if let Self::Im(target) = self {
+            Some(target)
+        } else {
+            None
+        }
+    }
+}
 
 /// Each derivation is a concatenation of two items, so there are two
 /// layers.  But some items have no children and are accepting, in
@@ -81,7 +128,7 @@ impl core::fmt::Display for Edge {
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub enum TwoLayers {
     /// One layer has no children.
-    One(Edge, usize),
+    One(Roi, usize),
     // REVIEW: Maybe we do not need to store an edge in the forest: we
     // only need the source of the edge?
     /// Both layers have children.
@@ -90,7 +137,7 @@ pub enum TwoLayers {
     /// the source of the associated forest edge of the second layer,
     /// and the third is a list of edges, which are the common first
     /// layers.
-    Two(usize, PaSe, bool, Vec<(Edge, usize)>),
+    Two(usize, PaSe, bool, Vec<(Roi, usize)>),
 }
 
 /// The type of a collapsed iterator.
@@ -122,7 +169,7 @@ where
     I: Iterator<Item = TwoLayers>,
     C: Chain<DerIter = I>,
 {
-    type Item = Result<(Edge, usize), <C as Chain>::Error>;
+    type Item = Result<(Roi, usize), <C as Chain>::Error>;
 
     fn next(&mut self) -> Option<Self::Item> {
         if self.stop {
@@ -133,7 +180,11 @@ where
             match two_layer {
                 TwoLayers::One(edge, to) => Some(Ok((edge, to))),
                 TwoLayers::Two(label, forest_source, accepting, edges) => {
-                    let new_index = match self.chain.extend(edges.into_iter()) {
+                    let new_index = match self.chain.extend(
+                        edges
+                            .into_iter()
+                            .filter_map(|(roi, target)| roi.real_part().map(|edge| (edge, target))),
+                    ) {
                         Ok(new) => new,
                         Err(error) => {
                             // Prevent further iterations.
@@ -143,7 +194,10 @@ where
                         }
                     };
 
-                    Some(Ok((Edge::new(label, forest_source, accepting), new_index)))
+                    Some(Ok((
+                        Edge::new(label, forest_source, accepting).into(),
+                        new_index,
+                    )))
                 }
             }
         } else {
@@ -174,6 +228,14 @@ pub trait Chain: LabelExtGraph<Edge> {
     /// Update the history
     fn update_history(&mut self, new: usize);
 
+    /// Update the acceptance of a node, when and only when that node
+    /// turns out to have no children.
+    fn update_epsilon(
+        &mut self,
+        node_id: usize,
+        edges: impl Iterator<Item = (Roi, usize)>,
+    ) -> Result<(), Self::Error>;
+
     /// An iterator that iterates all layers that need to be merged.
     type DerIter: Iterator<Item = TwoLayers>;
 
@@ -181,10 +243,10 @@ pub trait Chain: LabelExtGraph<Edge> {
     fn derive(&mut self, t: usize, pos: usize) -> Result<Self::DerIter, Self::Error>;
 
     /// Take the union of all derivatives.
-    fn union(&mut self, der_iter: Self::DerIter) -> Result<Vec<(Edge, usize)>, Self::Error> {
+    fn union(&mut self, der_iter: Self::DerIter) -> Result<Vec<(Roi, usize)>, Self::Error> {
         // REVIEW: Find a way to avoid allocations.
         Collapsed::<_, Self>::collapse(der_iter, self)
-            .collect::<Result<Vec<(Edge, usize)>, Self::Error>>()
+            .collect::<Result<Vec<(Roi, usize)>, Self::Error>>()
             .map(|mut v| {
                 v.retain(|(_, target)| {
                     *target == 0 || matches!(self.degree(*target), Ok(deg) if deg != 0)
@@ -200,7 +262,15 @@ pub trait Chain: LabelExtGraph<Edge> {
 
         let edges = self.union(der_iter)?;
 
-        let new_index = self.extend(edges)?;
+        let new_index = self.extend(
+            edges
+                .iter()
+                .filter_map(|(roi, target)| roi.real_part().map(|edge| (edge, *target))),
+        )?;
+
+        if self.is_empty_node(new_index)? {
+            self.update_epsilon(new_index, edges.into_iter())?;
+        }
 
         self.update_history(new_index);