From 18d7955b7d84c00467ede38baae53f4ce1fb6908 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Fri, 20 Jan 2023 13:48:26 +0800
Subject: chain: a prototype is added.

I have an ostensibly working prototype now.

Further tests are needed to make sure that the algorithm meets the
time complexity requirement, though.
---
 graph/src/labelled/binary.rs | 44 +++++++++++++++++++++++++++++++++++++++++---
 graph/src/labelled/double.rs | 14 ++++++++------
 2 files changed, 49 insertions(+), 9 deletions(-)

(limited to 'graph/src/labelled')

diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs
index bfd8109..e3e1943 100644
--- a/graph/src/labelled/binary.rs
+++ b/graph/src/labelled/binary.rs
@@ -19,18 +19,22 @@ struct PLChildren {
 }
 
 impl PLChildren {
+    #[inline]
     fn iter(&self) -> Iter<'_, usize> {
         self.children.iter()
     }
 
+    #[inline]
     fn len(&self) -> usize {
         self.children.len()
     }
 
+    #[inline]
     fn is_empty(&self) -> bool {
         self.children.is_empty()
     }
 
+    #[inline]
     fn contains(&self, key: &usize) -> bool {
         self.indices.contains_key(key)
     }
@@ -73,6 +77,15 @@ impl PLChildren {
 
         self.children.remove(key_index);
     }
+
+    /// Retrieve the `n`-th child.
+    #[inline]
+    fn nth(&self, n: usize) -> Result<usize, Error> {
+        self.children
+            .get(n)
+            .copied()
+            .ok_or(Error::IndexOutOfBounds(n, self.children.len()))
+    }
 }
 
 /// A node has some children, some parents, and a label.
@@ -187,7 +200,7 @@ impl<T: GraphLabel> Graph for PLGraph<T> {
     }
 
     fn replace_by_builder(&mut self, _builder: impl Builder<Result = Self>) {
-        todo!()
+        unimplemented!("use a `PLGBuilderMut` instead")
     }
 
     fn print_viz(&self, _filename: &str) -> Result<(), std::io::Error> {
@@ -246,6 +259,31 @@ impl<T: GraphLabel> ParentsGraph for PLGraph<T> {
             Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
         }
     }
+
+    #[inline]
+    fn nth_child(&self, node_id: usize, n: usize) -> Result<usize, Error> {
+        if let Some(node) = self.nodes.get(node_id) {
+            node.children.nth(n)
+        } else {
+            Err(Error::IndexOutOfBounds(node_id, self.nodes_len()))
+        }
+    }
+
+    #[inline]
+    fn edge_to_parent(&self, source: usize, target: usize) -> Result<Option<Parent>, Error> {
+        if !self.has_edge(source, target)? {
+            return Ok(None);
+        }
+
+        Ok(self
+            .nodes
+            .get(source)
+            .unwrap()
+            .children
+            .indices
+            .get(&target)
+            .map(|index| Parent::new(source, *index)))
+    }
 }
 
 impl<T: GraphLabel> RedirectGraph for PLGraph<T> {
@@ -378,13 +416,13 @@ impl<'a, T: GraphLabel> std::ops::Deref for PLGBuilderMut<'a, T> {
     type Target = PLGraph<T>;
 
     fn deref(&self) -> &Self::Target {
-        &self.graph
+        self.graph
     }
 }
 
 impl<'a, T: GraphLabel> std::ops::DerefMut for PLGBuilderMut<'a, T> {
     fn deref_mut(&mut self) -> &mut Self::Target {
-        &mut self.graph
+        self.graph
     }
 }
 
diff --git a/graph/src/labelled/double.rs b/graph/src/labelled/double.rs
index 4ab8a38..174c8ef 100644
--- a/graph/src/labelled/double.rs
+++ b/graph/src/labelled/double.rs
@@ -150,6 +150,8 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
     }
 
     fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> {
+        let filename = format!("output/{filename}");
+
         let preamble = "digraph nfa {
     fontname=\"Helvetica,Arial,sans-serif\"
     node [fontname=\"Helvetica,Arial,sans-serif\"]
@@ -170,14 +172,14 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
 
         let result = format!("{preamble}{post}");
 
-        if std::fs::metadata(filename).is_ok() {
-            std::fs::remove_file(filename)?;
+        if std::fs::metadata(&filename).is_ok() {
+            std::fs::remove_file(&filename)?;
         }
 
         let mut file = std::fs::File::options()
             .write(true)
             .create(true)
-            .open(filename)?;
+            .open(&filename)?;
 
         use std::io::Write;
 
@@ -206,7 +208,7 @@ impl<'a> Iterator for LabelIndexIter<'a> {
 
     #[inline]
     fn next(&mut self) -> Option<Self::Item> {
-        self.iter.as_mut().and_then(|iterator| iterator.next())
+        self.iter.as_mut().and_then(Iterator::next)
     }
 
     #[inline]
@@ -242,7 +244,7 @@ impl<'a> From<&'a Set<usize>> for LabelIndexIter<'a> {
     }
 }
 
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 /// A delegation of iterators.
 ///
 /// This is used to avoid a boxed pointer to an iterator.
@@ -278,7 +280,7 @@ impl<'a, T> Iterator for LabelIter<'a, T> {
 }
 
 /// This is used to avoid a boxed pointer to an iterator.
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub struct EdgeLabelIter<'a, T> {
     iter: Option<Iter<'a, T>>,
 }
-- 
cgit v1.2.3-18-g5258