1 files changed, 91 insertions, 0 deletions
diff --git a/forest/src/iter/mod.rs b/forest/src/iter/mod.rs
new file mode 100644
index 0000000..49aa4f1
--- /dev/null
+++ b/forest/src/iter/mod.rs
@@ -0,0 +1,91 @@
+//! This module defines the expected behaviours of "iterators of
+//! forests", or "walkers of forests".  Moreover, an implementation
+//! that provides querying capabilities is provided.
+
+use super::*;
+
+/// The state of the iterator.
+#[derive(Debug, Copy, Clone, Eq, PartialEq)]
+pub enum State {
+    /// The iterator goes to the next state.
+    Continue,
+    /// The iterator cannot proceed anymore.
+    Finish,
+    /// The iterator finishes for this tree, but there are trees not
+    /// visited yet.
+    ChangeBranch,
+}
+
+impl std::fmt::Display for State {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
+        use State::*;
+        match self {
+            Continue => write!(f, "next"),
+            Finish => write!(f, "finished"),
+            ChangeBranch => write!(
+                f,
+                "this branch is finished, but there are unvisited branches"
+            ),
+        }
+    }
+}
+
+/// An iterator is able to walk any forest, so no forest type is
+/// associated with iterators.  Essentially speaking, an iterator just
+/// provides the abilities to iterate through nodes of forests which
+/// meet certain conditions, in certain orders.
+pub trait ForestIter: Default {
+    /// Return the currenty visited node.
+    ///
+    /// If the iterator is not visiting any node, return `None`.
+    ///
+    /// The default implementation always returns `None`.
+    fn current(&self) -> Option<usize> {
+        None
+    }
+
+    /// The type of labels that can be iterated by this iterator.
+    type ForestLabel: GraphLabel;
+
+    /// The type of objects of iteration.
+    type Item<'a>: Default
+    where
+        Self: 'a;
+
+    /// The type of iteration errors.
+    type Error: std::error::Error + From<graph::error::Error>;
+
+    /// Walk to the next node according to this iterator.
+    ///
+    /// `forest` is any type that implements the `Forest` trait.
+    /// Theoretically, the forest can be different in two calls of
+    /// this method.  This makes it somehow more flexible.
+    ///
+    /// `root` specifies the root of the sub-forest to iterate.
+    ///
+    /// Of course this flexibility is not the main reason for the
+    /// design.  My purpose is to decouple the iterator from the
+    /// forest, so that the iterator can be as simple as a wrapper of
+    /// a vector of unsigned integers.
+    ///
+    /// The default implementation is lazy and always returns
+    /// "finished".
+    fn next<F>(&mut self, forest: &F, root: usize) -> Result<State, Self::Error>
+    where
+        F: LabelGraph<ForestLabel<Self::ForestLabel>>,
+    {
+        // just to silence the compiler
+        let _f = forest;
+        let _r = root;
+
+        Ok(State::Finish)
+    }
+
+    /// Reset the progress of this iterator so that it can be used to
+    /// iterate any forest again.
+    ///
+    /// The default implementation does nothing.
+    fn clear(&mut self) {}
+}
+
+pub mod query;