forest seems to be completed

I seem to have finished the implementation of forests.  Now it remains
the implementation of the chain-rule machine, of which I have a rough
plan now.

3 files changed, 176 insertions, 14 deletions

diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs
index 67d86f9..bfd8109 100644
--- a/graph/src/labelled/binary.rs
+++ b/graph/src/labelled/binary.rs
@@ -2,7 +2,7 @@
 //! labels and each node knows about its parents.
 
 use super::*;
-use crate::{Parent, ParentsGraph};
+use crate::{Parent, ParentsGraph, RedirectGraph};
 
 use std::{
     collections::{hash_map::Iter as MapIter, HashMap as Map},
@@ -142,6 +142,11 @@ impl<T: GraphLabel> Graph for PLGraph<T> {
     }
 
     #[inline]
+    fn edges_len(&self) -> Option<usize> {
+        Some(self.nodes.iter().map(|node| node.children.len()).sum())
+    }
+
+    #[inline]
     fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error> {
         if let Some(node) = self.nodes.get(node_id) {
             Ok(node.children.iter().copied())
@@ -243,6 +248,76 @@ impl<T: GraphLabel> ParentsGraph for PLGraph<T> {
     }
 }
 
+impl<T: GraphLabel> RedirectGraph for PLGraph<T> {
+    fn redirect(
+        &mut self,
+        node_id: usize,
+        child_index: usize,
+        new_child: usize,
+    ) -> Result<(), Error> {
+        let nodes_len = self.nodes.len();
+
+        if !self.has_node(new_child) {
+            return Err(Error::IndexOutOfBounds(new_child, nodes_len));
+        }
+
+        if let Some(node) = self.nodes.get_mut(node_id) {
+            if node.children.len() <= child_index {
+                return Err(Error::IndexOutOfBounds(child_index, node.children.len()));
+            }
+
+            // Check if `new_child` is already pointed to by the node.
+            if let Some(index) = node.children.indices.get(&new_child) {
+                // This should not happen in our use case, but we
+                // should still do somthing: as the edges cannot
+                // duplicate, we simply remove the original edge,
+                // unless index = child_index, in which case the old
+                // child is equal to the new child, and we have
+                // nothing to do.
+                if *index != child_index {
+                    node.children.remove(new_child);
+                }
+            } else {
+                // The index has been checked above, so it is safe to
+                // call `unwrap` here.
+                let old_child = std::mem::replace(
+                    node.children.children.get_mut(child_index).unwrap(),
+                    new_child,
+                );
+
+                node.children.indices.remove(&old_child);
+
+                node.children.indices.insert(new_child, child_index);
+
+                // Don't forget to remove `node` from the parents of
+                // the old child.
+
+                if let Some(old_child_node) = self.nodes.get_mut(old_child) {
+                    old_child_node.parents.remove(&node_id);
+                } else {
+                    // The node contained an invalid child.
+                    return Err(Error::IndexOutOfBounds(old_child, nodes_len));
+                }
+
+                // Don't forget to add node as a parent to the new
+                // child.
+
+                // new_child has been checked at the beginning of the
+                // function, so it is safe to call `unwrap`.
+                self.nodes
+                    .get_mut(new_child)
+                    .unwrap()
+                    .parents
+                    .insert(node_id, child_index);
+            }
+
+            Ok(())
+        } else {
+            Err(Error::IndexOutOfBounds(node_id, nodes_len))
+        }
+    }
+}
+
 impl<T: GraphLabel> LabelGraph<T> for PLGraph<T> {
     type Iter<'a> = std::iter::Empty<usize>
     where
@@ -299,6 +374,20 @@ pub struct PLGBuilderMut<'a, T: GraphLabel> {
     graph: &'a mut PLGraph<T>,
 }
 
+impl<'a, T: GraphLabel> std::ops::Deref for PLGBuilderMut<'a, T> {
+    type Target = PLGraph<T>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.graph
+    }
+}
+
+impl<'a, T: GraphLabel> std::ops::DerefMut for PLGBuilderMut<'a, T> {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.graph
+    }
+}
+
 impl<'a, T: GraphLabel> BuilderMut for PLGBuilderMut<'a, T> {
     type Label = T;
 
@@ -467,6 +556,8 @@ mod binary_test {
         builder.add_vertex(4);
         builder.add_vertex(5);
 
+        // These labels are not used on edges: they are just place
+        // holders.
         builder.add_edge(1, 0, 0)?;
         builder.add_edge(2, 0, 0)?;
         builder.add_edge(2, 1, 0)?;
@@ -481,43 +572,73 @@ mod binary_test {
         // testing adding a duplicatedly labelled node
         assert_eq!(builder.add_vertex(0), 0);
 
-        let graph = graph;
-
         // ensuring the correct length
-        assert_eq!(graph.nodes_len(), 6);
+        assert_eq!(builder.nodes_len(), 6);
 
         // testing children_of
-        assert_eq!(graph.children_of(5)?.collect::<Set<_>>(), set!(1, 3, 2));
+        assert_eq!(builder.children_of(5)?.collect::<Set<_>>(), set!(1, 3, 2));
 
         // testing parents_of
 
         assert_eq!(
-            graph.parents_of(0)?.collect::<Set<_>>(),
+            builder.parents_of(0)?.collect::<Set<_>>(),
             set!(Parent::new(1, 0), Parent::new(2, 0), Parent::new(3, 0))
         );
 
         assert_eq!(
-            graph.parents_of(1)?.collect::<Set<_>>(),
+            builder.parents_of(1)?.collect::<Set<_>>(),
             set!(Parent::new(2, 1), Parent::new(4, 0), Parent::new(5, 2))
         );
 
-        assert_eq!(graph.parents_of(5)?.len(), 0);
+        assert_eq!(builder.parents_of(5)?.len(), 0);
 
         // testing degree
-        assert_eq!(graph.degree(4)?, 2);
+        assert_eq!(builder.degree(4)?, 2);
 
         // testing is_empty_node
-        assert!(graph.is_empty_node(0)?);
-        assert!(!graph.is_empty_node(1)?);
+        assert!(builder.is_empty_node(0)?);
+        assert!(!builder.is_empty_node(1)?);
 
         // testing has_edge
-        assert!(graph.has_edge(3, 2)?);
-        assert!(!graph.has_edge(3, 1)?);
+        assert!(builder.has_edge(3, 2)?);
+        assert!(!builder.has_edge(3, 1)?);
         assert!(matches!(
-            graph.has_edge(3, 6),
+            builder.has_edge(3, 6),
             Err(Error::IndexOutOfBounds(6, 6))
         ));
 
+        // testing redirect
+        builder.redirect(5, 2, 0)?;
+        assert_eq!(builder.children_of(5)?.collect::<Set<_>>(), set!(0, 3, 2));
+
+        assert_eq!(
+            builder.parents_of(0)?.collect::<Set<_>>(),
+            set!(
+                Parent::new(1, 0),
+                Parent::new(2, 0),
+                Parent::new(3, 0),
+                Parent::new(5, 2)
+            )
+        );
+
+        builder.redirect(5, 0, 1)?;
+
+        assert_eq!(builder.children_of(5)?.collect::<Set<_>>(), set!(1, 0, 3));
+
+        assert_eq!(
+            builder.parents_of(1)?.collect::<Set<_>>(),
+            set!(Parent::new(2, 1), Parent::new(4, 0), Parent::new(5, 0))
+        );
+
+        builder.redirect(5, 0, 1)?; // should be no-op
+
+        assert_eq!(builder.children_of(5)?.collect::<Set<_>>(), set!(1, 0, 3));
+
+        assert_eq!(
+            builder.parents_of(1)?.collect::<Set<_>>(),
+            set!(Parent::new(2, 1), Parent::new(4, 0), Parent::new(5, 0))
+        );
+
         Ok(())
     }
 }
@@ -636,6 +757,28 @@ mod test_plgraph_builder {
 
         // println!();
 
+        // source out of bounds
+        assert!(matches!(
+            builder.redirect(5, 0, 0),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        // child_index out of bounds
+        assert!(matches!(
+            builder.redirect(4, 0, 0),
+            Err(Error::IndexOutOfBounds(0, 0))
+        ));
+
+        // new_child out of bounds
+        assert!(matches!(
+            builder.redirect(4, 0, 10),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        // println!("Correct errors when redirecting");
+
+        // println!();
+
         let graph = graph;
 
         println!("final graph: {graph:?}");
diff --git a/graph/src/labelled/mod.rs b/graph/src/labelled/mod.rs
index fa26bc4..2bbc7ec 100644
--- a/graph/src/labelled/mod.rs
+++ b/graph/src/labelled/mod.rs
@@ -16,5 +16,6 @@ pub mod double;
 pub use double::{DLGBuilder, DLGraph};
 
 pub mod binary;
+pub use binary::{PLGBuilderMut, PLGraph};
 
 // pub use binary::BLGraph;
diff --git a/graph/src/lib.rs b/graph/src/lib.rs
index 6813df3..6af7889 100644
--- a/graph/src/lib.rs
+++ b/graph/src/lib.rs
@@ -23,6 +23,7 @@ pub use adlist::ALGraph;
 pub mod labelled;
 
 pub use labelled::DLGraph;
+pub use labelled::PLGraph;
 
 pub mod builder;
 
@@ -252,6 +253,23 @@ pub trait ParentsGraph: Graph {
     fn parents_of(&self, node_id: usize) -> Result<<Self as ParentsGraph>::Iter<'_>, Error>;
 }
 
+// TODO: Design a trait of graphs which can "replace" a certain child
+// by another child.  To re-direct children, so to speak.
+
+/// An /exended/ graph in the sense that it offers the ability to
+/// "redirect" children of a node to another node.
+pub trait RedirectGraph: Graph {
+    /// Replace the edge that points from `node_id` to the
+    /// `child_index`-th child by a new edge that points to
+    /// `new_child`.
+    fn redirect(
+        &mut self,
+        node_id: usize,
+        child_index: usize,
+        new_child: usize,
+    ) -> Result<(), Error>;
+}
+
 /// A labelled graph is just a graph with labels associated to
 /// vertices and / or edges.
 ///