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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
#![warn(missing_docs)]
//! This file defines the expected behaviours of forests, and provides
//! a default implementation for forests.
//!
//! The default forest actually implements the so-called shared packed
//! parse forest, or SPPF. It packs sub-trees with the same parents
//! under the same branch, and lets nodes from different branches
//! share the same children, and hence the name.
use graph::{error::Error as GError, GraphLabel, LabelGraph, ParentsGraph};
/// An internal type that indicates the status of a node as either a
/// packed, cloned, or plain node.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
enum ForestLabelType {
Packed,
#[default]
Plain,
Cloned(usize),
}
impl core::fmt::Display for ForestLabelType {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
Self::Packed => write!(f, "packed"),
Self::Plain => write!(f, "plain"),
Self::Cloned(index) => write!(f, "the {index}-th clone"),
}
}
}
/// A type that encodes the properties demanded by a forest.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct ForestLabel<T: GraphLabel> {
label: T,
status: ForestLabelType,
}
impl<T: GraphLabel> core::fmt::Display for ForestLabel<T> {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
writeln!(f, "label: {}, status: {}", self.label, self.status)
}
}
/// The type of erros for converting forest labels.
#[non_exhaustive]
#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub enum ForestLabelError {
/// Try to pack a cloned node.
PackClone,
/// Try to clone a packed node.
ClonePack,
}
impl core::fmt::Display for ForestLabelError {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
Self::PackClone => write!(f, "cannot pack a cloned node"),
Self::ClonePack => write!(f, "cannot clone a packed node"),
}
}
}
impl std::error::Error for ForestLabelError {}
impl<T: GraphLabel> ForestLabel<T> {
/// Retrieve the label.
pub fn label(&self) -> T {
self.label
}
/// Return true if and only if this node is packed.
pub fn is_packed(&self) -> bool {
matches!(self.status, ForestLabelType::Packed)
}
/// Retrieve the optional clone index.
pub fn is_cloned(&self) -> Option<usize> {
match self.status {
ForestLabelType::Cloned(index) => Some(index),
_ => None,
}
}
/// Try to clone a node.
pub fn clone<F>(self, forest: &F) -> Result<Self, ForestLabelError>
where
F: Forest<T>,
{
if self.is_packed() {
Err(ForestLabelError::ClonePack)
} else {
let clone_index = if let Some(old_index) = self.is_cloned() {
let mut new_index: usize = old_index + 1;
let mut new_label = Self {
status: ForestLabelType::Cloned(new_index),
..self
};
while forest.query_label(new_label).is_some() {
new_index += 1;
new_label = Self {
status: ForestLabelType::Cloned(new_index),
..self
};
}
new_index
} else {
0
};
Ok(Self {
status: ForestLabelType::Cloned(clone_index),
..self
})
}
}
/// Try to pack a node.
pub fn pack(self) -> Result<Self, ForestLabelError> {
if self.is_cloned().is_some() {
Err(ForestLabelError::PackClone)
} else {
let new_label = Self {
status: ForestLabelType::Packed,
..self
};
Ok(new_label)
}
}
}
impl<T: GraphLabel> From<T> for ForestLabel<T> {
fn from(label: T) -> Self {
let status = ForestLabelType::default();
Self { label, status }
}
}
/// The expected behaviours of a forest.
///
/// Note that it requires only a subset of the functionalities of
/// labelled graphs.
pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> {
/// The type of errors for operations on the forest.
type Error: std::error::Error + From<GError> + From<ForestLabelError>;
/// Return the root of the forest.
///
/// A forest without a root is regarded as empty.
fn root(&self) -> Option<usize>;
/// Construct a forest consisting of one leaf node with the given
/// label.
fn new_leaf(label: T) -> Self;
/// Detect if the fragment is a prefix of the sub-forest rooted at
/// `node_id`.
fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>
where
F: AsRef<Self>;
/// Extend the forest by adjoining another forest at a given node.
fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error>
where
F: AsRef<Self>;
/// Clone a node by making a new node and making all the nodes
/// that previously pointed to the old node now point to the new
/// node, and the new node points to the old node. Return the
/// index of the new node. In addition, if the old node had
/// already been cloned, just return the index of its
/// representitave.
///
/// The labels of the representing node and of the cloned node
/// will be handled automatically.
fn clone_node(&mut self, node_id: usize) -> Result<usize, Self::Error>;
}
pub mod default;
pub use default::Error;
|
