a prototype of an item derivation forest

It seems to be complete now, but still awaits more tests to see where
the errors are, which should be plenty, haha.

1 files changed, 30 insertions, 96 deletions

diff --git a/graph/src/labelled/double.rs b/graph/src/labelled/double.rs
index 174c8ef..ab2b27c 100644
--- a/graph/src/labelled/double.rs
+++ b/graph/src/labelled/double.rs
@@ -8,13 +8,10 @@
 
 use super::*;
 
-// We use BTreeMap and BTreeSet here as we need to exclude duplicate
-// edge sets, while an ordinary hashmap and hashset do not allow
-// hashing.
 use std::collections::{
-    btree_map::{Iter as MapIter, Keys},
-    btree_set::Iter,
-    BTreeMap as Map, BTreeSet as Set, HashMap as HMap,
+    hash_map::{Iter as MapIter, Keys},
+    hash_set::Iter,
+    HashMap as Map, HashSet as Set,
 };
 
 #[derive(Debug, Clone)]
@@ -48,31 +45,13 @@ impl<T: GraphLabel> DLNode<T> {
     }
 }
 
-/// Mapping a set of edges to an index of node.
-type EdgeMap<T> = HMap<Set<(T, usize)>, usize>;
-
 /// Double direction Labelled Graph.
-///
-/// Each node is supposed to have a unique edge set.  Constructing
-/// methods such as from the trait
-/// [`LabelExtGraph`][super::LabelExtGraph] already handles the
-/// elimination of duplication.
 #[derive(Debug, Clone)]
 pub struct DLGraph<T: GraphLabel> {
     nodes: Vec<DLNode<T>>,
-    edges_table: EdgeMap<T>,
 }
 
 impl<T: GraphLabel> DLGraph<T> {
-    #[inline]
-    /// Return an empty graph.
-    pub fn new() -> Self {
-        Self {
-            nodes: Vec::new(),
-            edges_table: HMap::default(),
-        }
-    }
-
     /// Return a builder.
     #[inline]
     pub fn builder(self) -> DLGBuilder<T> {
@@ -89,7 +68,9 @@ impl<T: GraphLabel> DLGraph<T> {
 impl<T: GraphLabel> Default for DLGraph<T> {
     #[inline]
     fn default() -> Self {
-        Self::new()
+        let nodes = Vec::new();
+
+        Self { nodes }
     }
 }
 
@@ -160,11 +141,9 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
 
         let mut post = String::new();
 
-        use std::fmt::Write as FWrite;
-
         for (source, target) in self.edges() {
             for label in self.edge_label(source, target).unwrap() {
-                let _ = writeln!(post, "    {source} -> {target} [label = \"{label}\"]");
+                post.push_str(&format!("    {source} -> {target} [label = \"{label}\"]\n"));
             }
         }
 
@@ -191,7 +170,6 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
         let new_graph = builder.build();
 
         self.nodes = new_graph.nodes;
-        self.edges_table = new_graph.edges_table;
     }
 }
 
@@ -336,10 +314,10 @@ impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> {
 
     type LabelIter<'a> = LabelIter<'a,T> where T: 'a;
 
-    type EdgeLabelIter<'a> = EdgeLabelIter<'a,T>
+    type EdgeLabelIter<'a> = EdgeLabelIter<'a, T>
     where
         Self: 'a,
-        T: 'a + Copy + Clone;
+        T: 'a;
 
     fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> {
         if self.has_edge(source, target)? {
@@ -438,19 +416,12 @@ impl<T: GraphLabel> LabelExtGraph<T> for DLGraph<T> {
             }
         }
 
-        match self.edges_table.get(&edges_set) {
-            Some(old_index) => Ok(*old_index),
-            None => {
-                let new_node = DLNode::new(by_target, by_label, flat);
-                let new_index = self.nodes_len();
-
-                self.edges_table.insert(edges_set, new_index);
+        let new_node = DLNode::new(by_target, by_label, flat);
+        let new_index = self.nodes_len();
 
-                self.nodes.push(new_node);
+        self.nodes.push(new_node);
 
-                Ok(new_index)
-            }
-        }
+        Ok(new_index)
     }
 }
 
@@ -489,7 +460,6 @@ impl<T: GraphLabel> Builder for DLGBuilder<T> {
     fn with_capacity(size: usize) -> Self {
         Self(DLGraph {
             nodes: Vec::with_capacity(size),
-            edges_table: Default::default(),
         })
     }
 
@@ -526,8 +496,6 @@ impl<T: GraphLabel> Builder for DLGBuilder<T> {
         );
 
         if new_edge_p {
-            let old_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
-
             source_node
                 .by_target
                 .entry(target)
@@ -541,16 +509,6 @@ impl<T: GraphLabel> Builder for DLGBuilder<T> {
                 .insert(target);
 
             source_node.flat.push((label, target));
-
-            let new_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
-
-            // When source_node is in use, we cannot borrow self
-            // mutably again, so we move the following two statements
-            // to after all uses of source_node.
-
-            self.edges_table.remove(&old_children_set);
-
-            self.edges_table.insert(new_children_set, source);
         }
 
         Ok(())
@@ -586,8 +544,6 @@ impl<T: GraphLabel> Builder for DLGBuilder<T> {
             }
 
             if !to_remove.is_empty() {
-                let old_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
-
                 for label in to_remove.iter().copied() {
                     // This must be "Some", as the outer "if" checks
                     source_node
@@ -605,41 +561,19 @@ impl<T: GraphLabel> Builder for DLGBuilder<T> {
                     });
                 }
 
-                // If after removal no labels remain for the target,
-                // we remove the edge entirely, to avoid false empty
-                // edges.
-
-                if let Some(set) = source_node.by_target.get(&target) {
-                    if set.is_empty() {
-                        source_node.by_target.remove(&target);
-                    }
+                if matches!(source_node.by_target.get(&target),
+                            Some(set) if set.is_empty())
+                {
+                    source_node.by_target.remove(&target);
                 }
 
                 for label in to_remove.iter() {
-                    if let Some(set) = source_node.by_label.get(label) {
-                        if set.is_empty() {
-                            source_node.by_label.remove(label);
-                        }
+                    if matches!(source_node.by_label.get(label),
+                                Some(set) if set.is_empty())
+                    {
+                        source_node.by_label.remove(label);
                     }
                 }
-
-                // if source_node.flat.is_empty() {
-                //     source_node.by_target.remove(&target);
-
-                //     for label in to_remove.iter() {
-                //         source_node.by_label.remove(label);
-                //     }
-                // }
-
-                let new_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
-
-                // When source_node is in use, we cannot borrow self
-                // mutably again, so we move the following two
-                // statements to after all uses of source_node.
-
-                self.edges_table.remove(&old_children_set);
-
-                self.edges_table.insert(new_children_set, source);
             }
         }
 
@@ -703,13 +637,13 @@ mod label_test {
         assert_eq!(graph.extend([(2, 1), (3, 2), (2, 3)].iter().copied())?, 5);
 
         // testing adding a duplicated edge set
-        assert_eq!(graph.extend([(2, 1), (2, 3), (3, 2)].iter().copied())?, 5);
-        assert_eq!(graph.extend([(3, 2), (3, 0)].iter().copied())?, 3);
+        assert_eq!(graph.extend([(2, 1), (2, 3), (3, 2)].iter().copied())?, 6);
+        assert_eq!(graph.extend([(3, 2), (3, 0)].iter().copied())?, 7);
 
         let graph = graph;
 
         // ensuring the correct length
-        assert_eq!(graph.nodes_len(), 6);
+        assert_eq!(graph.nodes_len(), 8);
 
         // testing children_of
         assert_eq!(graph.children_of(5)?.collect::<Set<_>>(), set!(1, 3, 2));
@@ -723,8 +657,8 @@ mod label_test {
         // testing edge_label
         assert_eq!(graph.edge_label(5, 2)?.collect::<Set<_>>(), set!(3));
         assert!(matches!(
-            graph.edge_label(6, 2),
-            Err(Error::IndexOutOfBounds(6, 6))
+            graph.edge_label(8, 2),
+            Err(Error::IndexOutOfBounds(8, 8))
         ));
 
         // testing degree
@@ -738,8 +672,8 @@ mod label_test {
         assert!(graph.has_edge(3, 2)?);
         assert!(!graph.has_edge(3, 1)?);
         assert!(matches!(
-            graph.has_edge(3, 6),
-            Err(Error::IndexOutOfBounds(6, 6))
+            graph.has_edge(3, 8),
+            Err(Error::IndexOutOfBounds(8, 8))
         ));
 
         // testing labels_of
@@ -754,8 +688,8 @@ mod label_test {
         assert_eq!(label_map, compare_map);
 
         assert!(matches!(
-            graph.labels_of(6),
-            Err(Error::IndexOutOfBounds(6, 6))
+            graph.labels_of(8),
+            Err(Error::IndexOutOfBounds(8, 8))
         ));
 
         Ok(())