1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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;
|
