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 +++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 41 insertions(+), 3 deletions(-)

(limited to 'graph/src/labelled/binary.rs')

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
     }
 }
 
-- 
cgit v1.2.3-18-g5258