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