renaming core to chain and some other changes

Some changes:

- The core crate is renamed to "chain".

- The crate "viz" is added, which will provide layered graph drawing
  algorithms.

- A function is added to convert from a grammar to the regular
  language of its left-linear closures.

- A function is added to convert from a nondeterministic finite
  automaton to its "null" closure.  A null closure is the same
  automaton with edges added, as if some edges are "null".  Whether an
  edge is null is determined by a function.
  Combined with the previous change, we can convert a grammar to the
  regular language of the null closure of its left-linear closures.

---

Now it remains to test more grammars and add an Atom trait, before
finishing the part about compilations.

1 files changed, 237 insertions, 5 deletions

diff --git a/graph/src/adlist.rs b/graph/src/adlist.rs
index 18ad770..6c1dcd0 100644
--- a/graph/src/adlist.rs
+++ b/graph/src/adlist.rs
@@ -3,8 +3,9 @@
 //! [`Graph`][super::Graph].  This data type represents graphs using
 //! adjacency lists internally.
 
-use super::{ExtGraph, Graph};
-use crate::error::Error;
+use std::ops::{Deref, DerefMut};
+
+use crate::{builder::Builder, error::Error, ExtGraph, Graph};
 
 // #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
 // struct ALEdge {
@@ -80,6 +81,13 @@ impl Graph for ALGraph {
             Ok(self.nodes.get(source).unwrap().children.contains(&target))
         }
     }
+
+    #[inline]
+    fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>) {
+        let graph = builder.build();
+
+        self.nodes = graph.nodes;
+    }
 }
 
 impl ExtGraph for ALGraph {
@@ -102,11 +110,115 @@ impl ExtGraph for ALGraph {
     }
 }
 
-// TODO: Add a way to build a graph by its raw adjacency list representation.
 impl From<Vec<Vec<usize>>> for ALGraph {
     fn from(adlist: Vec<Vec<usize>>) -> Self {
-        let nodes: Vec<ALNode> = adlist.iter().cloned().map(ALNode::new).collect();
-        Self { nodes }
+        Self {
+            nodes: adlist.into_iter().map(ALNode::new).collect(),
+        }
+    }
+}
+
+// Builder for this implementation of graph
+
+/// A builder for adjacency list graphs.
+#[derive(Debug, Default, Clone)]
+pub struct ALGBuilder(ALGraph);
+
+impl Deref for ALGBuilder {
+    type Target = ALGraph;
+
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl DerefMut for ALGBuilder {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.0
+    }
+}
+
+impl Builder for ALGBuilder {
+    type Label = ();
+
+    type Result = ALGraph;
+
+    fn with_capacity(size: usize) -> Self {
+        Self(ALGraph {
+            nodes: Vec::with_capacity(size),
+        })
+    }
+
+    #[inline]
+    fn add_vertex(&mut self) -> usize {
+        self.nodes.push(ALNode::default());
+        self.nodes.len() - 1
+    }
+
+    fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> {
+        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.push(target);
+
+        Ok(())
+    }
+
+    /// Remove an edge from the source to the target.
+    ///
+    /// Since some graphs are labelled, the users are allowed to pass
+    /// a predicate to determine if an edge from the source to the
+    /// target should be removed.
+    ///
+    /// # Performance note
+    ///
+    /// It is possible that the target appears more than once in the
+    /// vector of children, so we have to remove every instance of
+    /// target.
+    ///
+    /// Since I do not think builders should be used for performance
+    /// critical tasks, this is fine.
+    ///
+    /// If one desires more performance, maybe
+    /// [`ASGraph`][crate::ASGraph] is a good choice.
+    ///
+    /// Of course, if one just wants to use adjacency list
+    /// representation and wants a performant builder, one can
+    /// implement a customized builder.
+    fn remove_edge<F>(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error>
+    where
+        F: Fn(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(())
+    }
+
+    fn build(self) -> Self::Result {
+        self.0
+    }
+
+    fn build_ref(&self) -> Self::Result {
+        self.0.clone()
     }
 }
 
@@ -187,3 +299,123 @@ mod algraph_test {
         Ok(())
     }
 }
+
+#[cfg(test)]
+mod test_algraph_builder {
+    use super::*;
+
+    #[test]
+    fn test_builder() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder = ALGBuilder::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        println!("five empty nodes: {builder:?}");
+
+        // Link each node to its successor and link the last node with
+        // the first one to form a cycle.
+        for i in 0..5 {
+            builder.add_edge(i, if i == 4 { 0 } else { i + 1 }, ())?;
+        }
+
+        println!("a cycle of five nodes: {builder:?}");
+
+        // Remove the link from the last node to the first node.
+        builder.remove_edge(4, 0, |_| true)?;
+
+        println!("a line of five nodes: {builder:?}");
+
+        // build a graph
+
+        let graph = builder.build();
+
+        println!("final graph: {graph:?}");
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_errors() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder = ALGBuilder::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        println!("five empty nodes: {builder:?}");
+
+        // Errors in add_edge
+
+        println!();
+        println!("Testing errors in add_edge:");
+        println!();
+
+        assert!(matches!(
+            builder.add_edge(0, 5, ()),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the target");
+
+        assert!(matches!(
+            builder.add_edge(10, 5, ()),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the source");
+
+        assert!(matches!(
+            builder.add_edge(10, 50, ()),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for both indices out of bounds");
+
+        // Errors in remove_edge
+
+        println!();
+        println!("Testing errors in remove_edge:");
+        println!();
+
+        assert!(matches!(
+            builder.remove_edge(0, 5, |_| true),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the target");
+
+        assert!(matches!(
+            builder.remove_edge(10, 5, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the source");
+
+        assert!(matches!(
+            builder.remove_edge(10, 50, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for both indices out of bounds");
+
+        assert!(matches!(builder.remove_edge(0, 1, |_| true), Ok(()),));
+
+        println!("No errors for removing a non-existing edge");
+
+        println!();
+
+        let graph = builder.build();
+
+        println!("final graph: {graph:?}");
+
+        Ok(())
+    }
+}