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
|
#![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.
//!
//! What is special here is that the forests are marked with some
//! out-coming and in-coming plugs. These plugs are used to join
//! different fragments of forests together.
use graph::{GraphLabel, LabelGraph, ParentsGraph};
use core::fmt::Display;
// TODO: move this to default
/// The type of errors for forest operations.
#[derive(Debug)]
pub enum Error {
/// An index is out of bounds.
IndexOutOfBounds(usize, usize),
}
impl Display for Error {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Error::IndexOutOfBounds(index, bound) => {
write!(f, "index {index} is out of bound {bound}")
}
}
}
}
impl std::error::Error for Error {}
// /// A builder of a forest.
// pub trait ForestBuilder<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> {
// /// The type of the resulting forest.
// type Output: Forest<NodeLabel, EdgeLabel>;
// /// Construct a new builder with only one node with the given
// /// label.
// fn new_leaf(label: NodeLabel) -> Self;
// /// Add a child to the builder the given labels for the new node
// /// and the added edge.
// ///
// /// All plug-out nodes within the builder should have a new child
// /// with the specified labels, and hence multiple children might
// /// be added, and the plug-out nodes should be modified
// /// accordingly.
// fn add_children(&mut self, vertex_label: NodeLabel, edge_labe: EdgeLabel);
// /// Build the forest.
// fn build(self) -> Self::Output;
// /// Build the forest from a reference.
// fn build_ref(&self) -> Self::Output;
// }
// FIXME: The trait should be re-designed.
/// 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<T> {
/// The type of errors for operations on the forest.
type Error: std::error::Error + From<graph::error::Error>;
/// Detect if the fragment is a prefix of the sub-forest rooted at
/// `node_id`.
fn is_prefix<F: AsRef<Self>>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>;
/// Extend the forest by adjoining another forest at a given node.
fn plant<F: AsRef<Self>>(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error>;
/// 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.
fn clone(&mut self, node_id: usize) -> Result<(), Self::Error>;
}
pub mod default;
|
