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
|
#![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::{error::Error as GError, GraphLabel, LabelGraph, ParentsGraph};
/// 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<GError>;
/// 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) -> 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.
///
/// The label of the new node will be given by the label
/// transformer.
fn clone_node<F>(&mut self, node_id: usize, clone_transform: F) -> Result<usize, Self::Error>
where
F: Fn(T) -> T;
}
pub mod default;
|
