From 9a317e56f8a6126583f7d0c431bf878d9b1fe7b1 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Sat, 8 Jul 2023 12:30:21 +0800
Subject: Finished the Emacs binding.

Now the binding part is finished.

What remains is a bug encountered when planting a fragment to the
forest which intersects a packed node, which would lead to invalid
forests.  This will also cause problem when planting a packed
fragment, but until now my testing grammars do not produce packed
fragments, so this problem is not encountered yet.

I am still figuring out efficient ways to solve this problem.
---
 graph/src/adlist.rs          | 104 ++++++++++++++++++++++++++++++++++++++++++-
 graph/src/builder.rs         |   5 +++
 graph/src/labelled/binary.rs |   4 +-
 3 files changed, 110 insertions(+), 3 deletions(-)

(limited to 'graph')

diff --git a/graph/src/adlist.rs b/graph/src/adlist.rs
index ba3077e..d36b250 100644
--- a/graph/src/adlist.rs
+++ b/graph/src/adlist.rs
@@ -3,9 +3,16 @@
 //! [`Graph`][super::Graph].  This data type represents graphs using
 //! adjacency lists internally.
 
-use std::ops::{Deref, DerefMut};
+use std::{
+    borrow::{Borrow, BorrowMut},
+    ops::{Deref, DerefMut},
+};
 
-use crate::{builder::Builder, error::Error, ExtGraph, Graph};
+use crate::{
+    builder::{Builder, BuilderMut},
+    error::Error,
+    ExtGraph, Graph,
+};
 
 // #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
 // struct ALEdge {
@@ -118,6 +125,99 @@ impl From<Vec<Vec<usize>>> for ALGraph {
     }
 }
 
+/// A builder that modifies ALGraph in place.
+#[derive(Debug)]
+pub struct ALGBuilderMut<'a> {
+    graph: &'a mut ALGraph,
+}
+
+impl<'a> std::ops::Deref for ALGBuilderMut<'a> {
+    type Target = ALGraph;
+
+    fn deref(&self) -> &Self::Target {
+        self.graph.borrow()
+    }
+}
+
+impl<'a> std::ops::DerefMut for ALGBuilderMut<'a> {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        self.graph.borrow_mut()
+    }
+}
+
+impl<'a> BuilderMut for ALGBuilderMut<'a> {
+    type Label = ();
+
+    type Graph = ALGraph;
+
+    type ResultBuilder<'b> = ALGBuilderMut<'b>
+    where
+        Self::Label: 'b;
+
+    fn from_graph_mut(graph: &mut Self::Graph) -> Self::ResultBuilder<'_> {
+        ALGBuilderMut { graph }
+    }
+
+    fn add_vertex(&mut self, _label: Self::Label) -> usize {
+        self.nodes.push(Default::default());
+
+        self.nodes.len() - 1
+    }
+
+    fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> {
+        if self.graph.has_edge(source, target)? {
+            return Ok(());
+        }
+
+        self.graph
+            .nodes
+            .get_mut(source)
+            .unwrap()
+            .children
+            .push(target);
+
+        Ok(())
+    }
+
+    fn append(&mut self, other: Self::Graph) {
+        let self_len = self.nodes_len();
+
+        self.graph
+            .nodes
+            .extend(other.nodes.into_iter().map(|mut node| {
+                for child in node.children.iter_mut() {
+                    *child += self_len;
+                }
+
+                node
+            }));
+    }
+
+    fn set_label(&mut self, _node_id: usize, _label: Self::Label) -> Result<(), Error> {
+        Ok(())
+    }
+
+    fn remove_edge<F>(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error>
+    where
+        F: FnMut(Self::Label) -> bool,
+    {
+        let nodes_len = self.nodes.len();
+
+        let source_children = self
+            .nodes
+            .get_mut(source)
+            .ok_or(Error::IndexOutOfBounds(source, nodes_len))?;
+
+        if !(0..nodes_len).contains(&target) {
+            return Err(Error::IndexOutOfBounds(target, nodes_len));
+        }
+
+        source_children.children.retain(|child| *child != target);
+
+        Ok(())
+    }
+}
+
 // Builder for this implementation of graph
 
 /// A builder for adjacency list graphs.
diff --git a/graph/src/builder.rs b/graph/src/builder.rs
index c5f9252..1278e26 100644
--- a/graph/src/builder.rs
+++ b/graph/src/builder.rs
@@ -82,6 +82,11 @@ pub trait BuilderMut {
     /// Add an edge from the source to the target.
     fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error>;
 
+    /// Append another graph to this builder.
+    fn append(&mut self, _other: Self::Graph) {
+        unimplemented!()
+    }
+
     /// Set the label of an existing node to a new label.
     fn set_label(&mut self, node_id: usize, label: Self::Label) -> Result<(), Error>;
 
diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs
index 9f3afa8..ccbd5cb 100644
--- a/graph/src/labelled/binary.rs
+++ b/graph/src/labelled/binary.rs
@@ -214,9 +214,11 @@ impl<T: GraphLabel> Graph for PLGraph<T> {
 
         let mut post = String::new();
 
-        // FIXME: Find a way to print only used nodes.  Maybe remove
+        // SOLVED: Find a way to print only used nodes.  Maybe remove
         // unwanted edges from unwanted nodes, so that we can print
         // out only those used nodes.
+        //
+        // This is solved as we can extract the forest out.
 
         for node in self.nodes() {
             post.push_str(&format!(
-- 
cgit v1.2.3-18-g5258