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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
// /// 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)]
// pub enum ForestLabelType {
// /// A packed node
// Packed,
// /// A plain node
// #[default]
// Plain,
// /// A cloned node
// Cloned(usize),
// }
//
// impl std::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, "clone({index})"),
// }
// }
// }
//
// /// 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> std::fmt::Display for ForestLabel<T> {
// fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
// if !matches!(self.status, ForestLabelType::Plain) {
// write!(f, "{}, {}", self.label, self.status)
// } else {
// write!(f, "{}", self.label)
// }
// }
// }
//
// /// The type of erros for converting forest labels.
// #[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 std::fmt::Display for ForestLabelError {
// fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::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> {
// /// Construct a new label with the inner `label` and `status`.
// pub fn new(label: T, status: ForestLabelType) -> Self {
// Self { label, status }
// }
//
// /// 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 {
// self.status == ForestLabelType::Packed
// }
//
// /// Retrieve the optional clone index.
// pub fn clone_index(&self) -> Option<usize> {
// match self.status {
// ForestLabelType::Cloned(index) => Some(index),
// _ => None,
// }
// }
//
// /// Return true if and only if this node is a plain node.
// pub fn is_plain(&self) -> bool {
// self.status == ForestLabelType::Plain
// }
//
// /// Try to clone a node.
// pub fn clone<F>(self, forest: &F) -> Result<Self, ForestLabelError>
// where
// F: LabelGraph<ForestLabel<T>>,
// {
// if self.is_packed() {
// dbg!();
// Err(ForestLabelError::ClonePack)
// } else {
// let clone_index = if let Some(old_index) = self.clone_index() {
// 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.clone_index().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 }
// }
// }
//
// // REVIEW: Should we move this trait (and only this trait) to a
// // separate crate, or is it enough to keep it here?
//
// /// The expected behaviours of an item derivation 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;
//
// /// Transform the label at the given node.
// fn transform_label(
// &mut self,
// node_id: usize,
// transform: impl FnOnce(T) -> T,
// ) -> Result<(), Self::Error>;
//
// /// 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: Borrow<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: Borrow<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. However, if, and only if,
// /// `no_new_clone` is `true`, do not make a new clone; instead
// /// return the clone index that would be used if a new clone was
// /// made.
// ///
// /// Also, `preserved_edges_num` many edges out of the old node
// /// will be copied to be the children of the new node.
// ///
// /// The labels of the representing node and of the cloned node
// /// will be handled automatically.
// fn clone_node(
// &mut self,
// node_id: usize,
// preserved_edges_num: usize,
// no_new_clone: bool,
// ) -> Result<usize, Self::Error>;
// }
//
|
