//! This module defines the expected behaviours of "iterators of
//! forests", or "walkers of forests".  Moreover, an implementation
//! with 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"
            ),
        }
    }
}

// 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 nodes.
    ///
    /// 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;