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, 214 insertions, 2 deletions

diff --git a/graph/src/adset.rs b/graph/src/adset.rs
index 58fed4c..c225986 100644
--- a/graph/src/adset.rs
+++ b/graph/src/adset.rs
@@ -7,8 +7,9 @@
 //! duplications of languages, so it is more convenient if the
 //! underlying graph type **cannot** represent duplicate edges.
 
-use super::{ExtGraph, Graph};
-use crate::error::Error;
+use std::ops::{Deref, DerefMut};
+
+use crate::{builder::Builder, error::Error, ExtGraph, Graph};
 
 // If one wants to use another implementation for a set, import that
 // as Set, and nothing else needs to be changed, ideally.
@@ -122,6 +123,13 @@ impl Graph for ASGraph {
                 .contains(&ASEdge::new(target)))
         }
     }
+
+    #[inline]
+    fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>) {
+        let graph = builder.build();
+
+        self.nodes = graph.nodes;
+    }
 }
 
 impl ExtGraph for ASGraph {
@@ -144,6 +152,90 @@ impl ExtGraph for ASGraph {
     }
 }
 
+// Builder for this implementation of graph
+
+/// A builder for adjacency set graphs.
+#[derive(Debug, Default, Clone)]
+pub struct ASGBuilder(ASGraph);
+
+impl Deref for ASGBuilder {
+    type Target = ASGraph;
+
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl DerefMut for ASGBuilder {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.0
+    }
+}
+
+impl Builder for ASGBuilder {
+    type Label = ();
+
+    type Result = ASGraph;
+
+    #[inline]
+    fn with_capacity(size: usize) -> Self {
+        Self(ASGraph {
+            nodes: Vec::with_capacity(size),
+        })
+    }
+
+    #[inline]
+    fn add_vertex(&mut self) -> usize {
+        self.nodes.push(ASNode::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.insert(ASEdge::new(target));
+
+        Ok(())
+    }
+
+    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.remove(&ASEdge::new(target));
+
+        Ok(())
+    }
+
+    fn build(self) -> Self::Result {
+        self.0
+    }
+
+    fn build_ref(&self) -> Self::Result {
+        self.0.clone()
+    }
+}
+
 #[cfg(test)]
 mod asgraph_test {
     use super::*;
@@ -227,3 +319,123 @@ mod asgraph_test {
         Ok(())
     }
 }
+
+#[cfg(test)]
+mod test_asgraph_builder {
+    use super::*;
+
+    #[test]
+    fn test_builder() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder = ASGBuilder::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 = ASGBuilder::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(())
+    }
+}