1 files changed, 48 insertions, 3 deletions

diff --git a/forest/src/iter/mod.rs b/forest/src/iter/mod.rs
index 49aa4f1..5c55943 100644
--- a/forest/src/iter/mod.rs
+++ b/forest/src/iter/mod.rs
@@ -1,6 +1,6 @@
 //! This module defines the expected behaviours of "iterators of
 //! forests", or "walkers of forests".  Moreover, an implementation
-//! that provides querying capabilities is provided.
+//! with querying capabilities is provided.
 
 use super::*;
 
@@ -30,17 +30,62 @@ impl std::fmt::Display for State {
     }
 }
 
+// TODO: We need a trait to define the behaviours of "queryable"
+// forests: the forests with the three following functionalities:
+//
+// 1. Follow nodes in the depth-first order.
+//
+// 2. Detect if a node is packed.
+//
+// 3. Go to the next "world line" in the forest; that is, go up and
+//   stop before the nearest parent packed node and then go to the
+//   next sibling.
+//
+// We shall call this trait "Queryable".
+
+/// This trait defines the behaviours of data types that can be walked
+/// by walkers specified in this module.
+#[allow(dead_code)]
+pub(in crate::iter) trait Queryable {
+    /// Return the index of the currently visited node.
+    ///
+    /// If it is not visiting nodes, then `None` is returned.
+    fn current(&self) -> Option<usize>;
+
+    /// Go to the next node according to the depth-first order.
+    ///
+    /// If and only if no next node is available, return false.
+    fn next(&mut self) -> bool;
+
+    /// Go to the next branch.  If and only if no next branch to
+    /// explore is available, return false.
+    ///
+    /// By going to the next branch we mean to go up and stop just
+    /// before the nearest parent packed node and then go to the next
+    /// sibling, if any.  If no next sibling is available, repeat the
+    /// above process, until an available branch is found, or until
+    /// every branch is exhausted and we return false.
+    fn next_branch(&mut self) -> bool;
+
+    /// Restrict the forest to the subtree rooted under a specified
+    /// node.
+    ///
+    /// Return whether the currently visited node is rooted under the
+    /// specified node or not.
+    fn restrict(&mut self, node: usize) -> bool;
+}
+
 /// 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.
+    /// Return the currenty visited nodes.
     ///
     /// If the iterator is not visiting any node, return `None`.
     ///
     /// The default implementation always returns `None`.
-    fn current(&self) -> Option<usize> {
+    fn current(&self) -> Option<&[usize]> {
         None
     }