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
|
//! 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::{ExtGraph, GraphLabel};
use core::fmt::Display;
#[derive(Debug)]
pub enum Error {
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;
}
/// The expected behaviours of a forest.
///
/// Note that it contains a "striped down" version of the labelled
/// graphs.
pub trait Forest<NodeLabel: GraphLabel, EdgeLabel: GraphLabel>: ExtGraph {
/// Type of iterator of plug-in nodes.
type PluginIter<'a>: Iterator<Item = usize> + 'a
where
Self: 'a;
/// Type of iterator of plug-out nodes.
type PlugoutIter<'a>: Iterator<Item = usize> + 'a
where
Self: 'a;
/// Return the plug-in nodes
fn plugins(&self) -> Self::PluginIter<'_>;
/// Return the plug-out nodes
fn plugouts(&self) -> Self::PlugoutIter<'_>;
/// Plug another forest onto this forest.
///
/// The plug-out nodes of this forest will be joined onto the
/// plug-in nodes of the joining forest.
///
/// # Performance warning
///
/// It is recommended to only call this function with a "small"
/// `other`, as this function might copy the whole graph
/// individually, node by node and edge by edge.
fn plug(&mut self, other: &Self) -> Result<(), Error>;
/// Return the vertex label.
///
/// A vertex may not have labels.
fn vertex_label(&self, node_id: usize) -> Result<Option<NodeLabel>, Error>;
/// Return the edge label.
///
/// An edge may have no labels. If there is no edge from the
/// given source to the given target, then `Ok(None)` is returned
/// as well.
fn edge_label(&self, source: usize, target: usize) -> Result<Option<EdgeLabel>, Error>;
}
pub mod default;
|
