#![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;