Initial commit

Basic GNU standard files are added, and we now stop worrying about
monadic anamorphisms.

The current focus is on testing the correctness of the algorithm, so I
need convenient support for manipulating, interpreting, examining, and
per chance animating nondeterministic automata.

1 files changed, 229 insertions, 0 deletions

diff --git a/graph/src/adset.rs b/graph/src/adset.rs
new file mode 100644
index 0000000..58fed4c
--- /dev/null
+++ b/graph/src/adset.rs
@@ -0,0 +1,229 @@
+#![warn(missing_docs)]
+//! This file implements a data type that implements the trait
+//! [`Graph`][super::Graph].  This data type represents graphs using
+//! adjacency sets internally.
+//!
+//! I need this because the derivatives languages should not allow
+//! 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;
+
+// If one wants to use another implementation for a set, import that
+// as Set, and nothing else needs to be changed, ideally.
+use std::collections::{hash_set::Iter, HashSet as Set};
+
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
+struct ASEdge {
+    to: usize,
+}
+
+impl ASEdge {
+    fn new(to: usize) -> Self {
+        Self { to }
+    }
+}
+
+#[derive(Debug, Clone, Default)]
+struct ASNode {
+    children: Set<ASEdge>,
+}
+
+impl ASNode {
+    fn new(children: Set<ASEdge>) -> Self {
+        Self { children }
+    }
+}
+
+/// The graph implemented using adjacency sets.
+#[derive(Debug, Clone, Default)]
+pub struct ASGraph {
+    nodes: Vec<ASNode>,
+}
+
+/// A delegation of iterators.
+///
+/// This is here to avoid using a boxed pointer, in order to save some
+/// allocations.
+pub struct ASIter<'a> {
+    iter: Iter<'a, ASEdge>,
+}
+
+impl<'a> Iterator for ASIter<'a> {
+    type Item = usize;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().map(|edge| edge.to)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+impl<'a> ExactSizeIterator for ASIter<'a> {
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl Graph for ASGraph {
+    type Iter<'a> = ASIter<'a>;
+
+    #[inline]
+    fn is_empty(&self) -> bool {
+        self.nodes.is_empty()
+    }
+
+    #[inline]
+    fn nodes_len(&self) -> usize {
+        self.nodes.len()
+    }
+
+    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error> {
+        match self.nodes.get(node_id) {
+            Some(node) => {
+                let iter = node.children.iter();
+                Ok(Self::Iter { iter })
+            }
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
+        }
+    }
+
+    #[inline]
+    fn degree(&self, node_id: usize) -> Result<usize, Error> {
+        match self.nodes.get(node_id) {
+            Some(node) => Ok(node.children.len()),
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
+        }
+    }
+
+    #[inline]
+    fn is_empty_node(&self, node_id: usize) -> Result<bool, Error> {
+        match self.nodes.get(node_id) {
+            Some(node) => Ok(node.children.is_empty()),
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
+        }
+    }
+
+    #[inline]
+    fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> {
+        if !self.has_node(source) {
+            Err(Error::IndexOutOfBounds(source, self.nodes_len()))
+        } else if !self.has_node(target) {
+            Err(Error::IndexOutOfBounds(target, self.nodes_len()))
+        } else {
+            Ok(self
+                .nodes
+                .get(source)
+                .unwrap()
+                .children
+                .contains(&ASEdge::new(target)))
+        }
+    }
+}
+
+impl ExtGraph for ASGraph {
+    fn extend(&mut self, edges: impl IntoIterator<Item = usize>) -> Result<usize, Error> {
+        let mut new_node_children = Set::default();
+
+        for edge_to in edges.into_iter() {
+            if !self.has_node(edge_to) {
+                return Err(Error::IndexOutOfBounds(edge_to, self.nodes_len()));
+            }
+
+            new_node_children.insert(ASEdge::new(edge_to));
+        }
+
+        let new_node = ASNode::new(new_node_children);
+
+        self.nodes.push(new_node);
+
+        Ok(self.nodes.len() - 1)
+    }
+}
+
+#[cfg(test)]
+mod asgraph_test {
+    use super::*;
+
+    #[test]
+    fn test_graph_apis() -> Result<(), Error> {
+        let mut graph = ASGraph::default();
+
+        assert!(graph.is_empty());
+
+        graph.extend(std::iter::empty())?;
+
+        graph.extend([0].iter().copied())?;
+        graph.extend([0, 1].iter().copied())?;
+        graph.extend([0, 2].iter().copied())?;
+        graph.extend([1, 2].iter().copied())?;
+        graph.extend([1, 2, 3].iter().copied())?;
+
+        let graph = graph;
+
+        assert_eq!(graph.nodes_len(), 6);
+
+        assert_eq!(graph.children_of(5)?.collect::<Set<_>>(), {
+            let mut set = Set::default();
+            set.insert(1);
+            set.insert(3);
+            set.insert(2);
+            set
+        });
+
+        assert_eq!(graph.degree(4)?, 2);
+
+        assert!(graph.is_empty_node(0)?);
+        assert!(!graph.is_empty_node(1)?);
+
+        assert!(graph.has_edge(3, 2)?);
+        assert!(!graph.has_edge(3, 1)?);
+        assert_eq!(graph.has_edge(3, 6), Err(Error::IndexOutOfBounds(6, 6)));
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_extending_algraph_normal() -> Result<(), Error> {
+        let mut graph = ASGraph::default();
+
+        let new = graph.extend(std::iter::empty())?;
+
+        println!("new index = {new}");
+
+        println!("new graph = {graph:?}");
+
+        let new = graph.extend([0].iter().copied())?;
+
+        println!("new index = {new}");
+
+        println!("new graph = {graph:?}");
+
+        let new = graph.extend([0, 1].iter().copied())?;
+
+        println!("new index = {new}");
+
+        println!("new graph = {graph:?}");
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_extending_algraph_error() -> Result<(), Error> {
+        let mut graph = ASGraph::default();
+
+        graph.extend(std::iter::empty())?;
+
+        graph.extend([0].iter().copied())?;
+
+        assert_eq!(
+            graph.extend([2].iter().copied()),
+            Err(Error::IndexOutOfBounds(2, 2))
+        );
+
+        Ok(())
+    }
+}