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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
//! 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;
|
