//! 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;