1 files changed, 153 insertions, 0 deletions
diff --git a/forest/src/default.rs b/forest/src/default.rs
new file mode 100644
index 0000000..36145f4
--- /dev/null
+++ b/forest/src/default.rs
@@ -0,0 +1,153 @@
+//! This file provides a default implementation for the
+//! [`Forest`][crate::Forest] trait.
+
+use super::*;
+use graph::{error::Error as GraphError, ALGraph, Graph};
+
+use std::collections::{hash_set::Iter, HashMap, HashSet};
+
+#[derive(Debug, Clone)]
+pub struct DefaultForest<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> {
+    graph: ALGraph,
+    vertex_labels: HashMap<usize, NodeLabel>,
+    edge_labels: HashMap<(usize, usize), EdgeLabel>,
+    plugins: HashSet<usize>,
+    plugouts: HashSet<usize>,
+}
+
+impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> Default for DefaultForest<NodeLabel, EdgeLabel> {
+    fn default() -> Self {
+        Self {
+            graph: Default::default(),
+            vertex_labels: Default::default(),
+            edge_labels: Default::default(),
+            plugins: Default::default(),
+            plugouts: Default::default(),
+        }
+    }
+}
+
+impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> Graph for DefaultForest<NodeLabel, EdgeLabel> {
+    type Iter<'a> = <ALGraph as Graph>::Iter<'a>
+    where
+        Self: 'a;
+
+    fn is_empty(&self) -> bool {
+        self.graph.is_empty()
+    }
+
+    fn nodes_len(&self) -> usize {
+        self.graph.nodes_len()
+    }
+
+    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GraphError> {
+        self.graph.children_of(node_id)
+    }
+
+    fn degree(&self, node_id: usize) -> Result<usize, GraphError> {
+        self.graph.degree(node_id)
+    }
+
+    fn is_empty_node(&self, node_id: usize) -> Result<bool, GraphError> {
+        self.graph.is_empty_node(node_id)
+    }
+
+    fn has_edge(&self, source: usize, target: usize) -> Result<bool, GraphError> {
+        self.graph.has_edge(source, target)
+    }
+
+    fn replace_by_builder(&mut self, _builder: impl graph::Builder<Result = Self>) {
+        unimplemented!()
+    }
+}
+
+impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> ExtGraph
+    for DefaultForest<NodeLabel, EdgeLabel>
+{
+    fn extend(&mut self, edges: impl IntoIterator<Item = usize>) -> Result<usize, GraphError> {
+        self.graph.extend(edges)
+    }
+}
+
+#[derive(Debug)]
+pub struct LabelIter<'a> {
+    set_iter: Iter<'a, usize>,
+}
+
+impl<'a> Iterator for LabelIter<'a> {
+    type Item = usize;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.set_iter.next().copied()
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.set_iter.size_hint()
+    }
+}
+
+impl<'a> ExactSizeIterator for LabelIter<'a> {
+    fn len(&self) -> usize {
+        let (lower, upper) = self.size_hint();
+        // Note: This assertion is overly defensive, but it checks the
+        // invariant guaranteed by the trait.
+        debug_assert!(upper == Some(lower));
+        lower
+    }
+}
+
+impl<'a> From<Iter<'a, usize>> for LabelIter<'a> {
+    fn from(set_iter: Iter<'a, usize>) -> Self {
+        Self { set_iter }
+    }
+}
+
+impl<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> Forest<NodeLabel, EdgeLabel>
+    for DefaultForest<NodeLabel, EdgeLabel>
+{
+    type PluginIter<'a> = LabelIter<'a>
+    where
+        Self: 'a;
+
+    type PlugoutIter<'a> = LabelIter<'a>
+    where
+        Self: 'a;
+
+    fn plugins(&self) -> Self::PluginIter<'_> {
+        self.plugins.iter().into()
+    }
+
+    fn plugouts(&self) -> Self::PlugoutIter<'_> {
+        self.plugouts.iter().into()
+    }
+
+    fn plug(&mut self, other: &Self) -> Result<(), Error> {
+        // PLAN: Clone the `other` forest to `self`, adjust the
+        // indices for edges, and then add edges between plugs.
+        //
+        // Since I cannot touch the underlying nodes directly, I have
+        // to add the nodes and edges individually.
+
+        todo!()
+    }
+
+    fn vertex_label(&self, node_id: usize) -> Result<Option<NodeLabel>, Error> {
+        if node_id >= self.nodes_len() {
+            return Err(Error::IndexOutOfBounds(node_id, self.nodes_len()));
+        }
+
+        Ok(self.vertex_labels.get(&node_id).copied())
+    }
+
+    fn edge_label(&self, source: usize, target: usize) -> Result<Option<EdgeLabel>, Error> {
+        if source >= self.nodes_len() {
+            return Err(Error::IndexOutOfBounds(source, self.nodes_len()));
+        }
+
+        if target >= self.nodes_len() {
+            return Err(Error::IndexOutOfBounds(target, self.nodes_len()));
+        }
+
+        Ok(self.edge_labels.get(&(source, target)).copied())
+    }
+}